From 7ad4aedc49e97a2a62de08c89b47a877adf9e076 Mon Sep 17 00:00:00 2001 From: Sébastien Dailly Date: Thu, 7 Mar 2024 10:54:37 +0100 Subject: calculette_aoo: updated the way to evaluate the odds --- calculette_aoo/lib/build.ml | 2 +- calculette_aoo/lib/roll.ml | 85 +++++++++++++++++++++++++++++++-------------- 2 files changed, 59 insertions(+), 28 deletions(-) (limited to 'calculette_aoo/lib') diff --git a/calculette_aoo/lib/build.ml b/calculette_aoo/lib/build.ml index 5c2ac0b..2119fb6 100644 --- a/calculette_aoo/lib/build.ml +++ b/calculette_aoo/lib/build.ml @@ -80,7 +80,7 @@ let repr : env -> Format.formatter -> build -> unit = let score : env -> build -> float = fun env build -> - let d, v = eval build env in + let d, _ = eval build env in d (* Upgrade each caracteristic and keep only the values in range *) diff --git a/calculette_aoo/lib/roll.ml b/calculette_aoo/lib/roll.ml index 00d8465..14488e6 100644 --- a/calculette_aoo/lib/roll.ml +++ b/calculette_aoo/lib/roll.ml @@ -1,24 +1,52 @@ open StdLabels -(** Evaluate the coefficient for the product of two polynamials *) -let mul p1 p2 = - let n1 = Array.length p1 and n2 = Array.length p2 in - let n = n1 + n2 in - let res = Array.make n 0 in - for i = 0 to n1 - 1 do - for j = 0 to n2 - 1 do - res.(i + j + 1) <- res.(i + j + 1) + (p1.(i) * p2.(j)) - done - done; - res +(** Build the frequencies table for the given number of dices to roll. The + function return a table with the number of occurences for the each index. + + Example : + table[2] = 1 + table[3] = 4 + + Tell us than there the probabily to get the value 3 is 4× higher to get the + value 2. + *) +let build_frequencies n = + let length = n * 3 in + + let arr_source = Array.init length ~f:(fun i -> if i < 3 then 1 else 0) in + + (* Recursive function, evaluate the odd by adding a new dice to the previous + distribution. + + The probabily to get the value V with N dice is equal to : + - The probabilyt to get the value V - 1 with N - 1 dices and having 1 with + the new dice + - The probabilyt to get the value V - 2 with N - 1 dices and having 2 with + the new dice + - The probabilyt to get the value V - 3 with N - 1 dices and having 3 with + the new dice -(** Apply a power function over a polynomial *) -let pow p1 n = - let result = ref p1 in - for _ = 1 to n - 1 do - result := mul !result p1 - done; - !result + As the dice is fair, the probability to get the new value is equal in each + case, and we can just ignore this part. + + This give us this formula : + + P(V)_N = P(V - 1)_(N-1) + P(V - 2)_(N-1) + P(V - 3)_(N-1) + *) + let rec apply level arr_source = + match level with + | 0 -> arr_source + | _ -> + let arr_target = Array.init length ~f:(fun _ -> 0) in + let depth = n - level + 1 in + for index = max 1 (depth - 1) to (3 * depth) - 1 do + for j = max 0 (index - 3) to index - 1 do + arr_target.(index) <- arr_target.(index) + arr_source.(j) + done + done; + apply (level - 1) arr_target + in + apply (n - 1) arr_source (** Evaluate the odd to win agains a give difficulty *) let against : int -> int array -> Q.t array = @@ -26,18 +54,19 @@ let against : int -> int array -> Q.t array = match n with | 0 -> Array.map ~f:(fun _ -> Q.zero) difficulties | _ -> - (* Create the polynomial with the odd ratio for the given caracteristic *) - let arr = Array.make 3 1 in - let frequencies = pow arr n in + (* Create the polynomial with the odd ratio for the given + caracteristic *) + let frequencies = build_frequencies n in let ratio = Z.(of_int 3 ** n) in let get_chances difficulty = (* Evaluate the ratio to win the roll *) let chances = ref Z.zero in for i = difficulty - 1 to Array.length frequencies - 1 do - (* The index in the table is the odd to get exactly this value in the roll. - Here, we just add every value in the array from the index strarting from - the given difficulty. *) + (* The index in the table is the odd to get exactly this value in the + roll. + Here, we just add every value in the array from the index + strarting from the given difficulty. *) chances := Z.(!chances + of_int frequencies.(i)) done; Q.make !chances ratio @@ -51,7 +80,6 @@ let against : int -> int array -> Q.t array = In case of equality, the win is given to [v1] *) let compare : int -> int -> Q.t = fun carac1 carac2 -> - let arr = Array.make 3 1 in let z3 = Z.of_int 3 in let ordinal1 = Z.(z3 ** carac1) @@ -63,8 +91,11 @@ let compare : int -> int -> Q.t = (* The number of iterations to do is elements1 × elements2. For every iteration of elements2, we have ordinal1 points to get. *) let cases = Z.(ordinal1 * ordinal2) in - let frequencies_1 = pow arr carac1 |> Array.map ~f:(fun v -> Z.(of_int v)) - and frequencies_2 = pow arr carac2 |> Array.map ~f:(fun v -> Z.(of_int v)) in + let frequencies_1 = + build_frequencies carac1 |> Array.map ~f:(fun v -> Z.(of_int v)) + and frequencies_2 = + build_frequencies carac2 |> Array.map ~f:(fun v -> Z.(of_int v)) + in (* Now, compare for each values the probabily to win *) let res = ref Z.zero in -- cgit v1.2.3