engine choice MxN and fraction probability data

engine.diff

diff --git a/src/test/fuzz.zig b/src/test/fuzz.zig
index 803469c4..8f69dfaa 100644
--- a/src/test/fuzz.zig
+++ b/src/test/fuzz.zig
@@ -21,7 +21,11 @@ var frames: ?std.ArrayList(Frame) = null;
 const debug = false; // DEBUG

 const showdown = pkmn.options.showdown;
-const chance = pkmn.options.chance and debug;
+const chance = pkmn.options.chance; // and debug;
+
+var UNREDUCED = [_]usize{0} ** 128;
+var REDUCED = [_]usize{0} ** 128;
+var SIZE: [9][9]usize = .{([_]usize{0} ** 9)} ** 9;

 pub fn main() !void {
     var gpa = std.heap.GeneralPurposeAllocator(.{}){};
@@ -57,6 +61,8 @@ pub fn main() !void {
     };

     try fuzz(allocator, seed, duration);
+
+    std.debug.print("unreduced: {any}\nreduced: {any}\nchoices: {any}\n", .{UNREDUCED, REDUCED, SIZE});
 }

 pub fn fuzz(allocator: std.mem.Allocator, seed: u64, duration: usize) !void {
@@ -131,10 +137,12 @@ fn run(
     while (result.type == .None) : (result = update(battle, c1, c2, &options, allocator)) {
         var n = battle.choices(.P1, result.p1, &choices);
         if (n == 0) break;
-        c1 = choices[p1.range(u8, 0, n)];
+        const m = n;
+        c1 = choose(&p1, choices[0..n]);
         n = battle.choices(.P2, result.p2, &choices);
         if (n == 0) break;
-        c2 = choices[p2.range(u8, 0, n)];
+        c2 = choose(&p2, choices[0..n]);
+        SIZE[m - 1][n - 1] += 1;

         if (save) {
             std.debug.assert(buf.?.items.len <= max);
@@ -151,6 +159,7 @@ fn run(
     std.debug.assert(!showdown or result.type != .Error);
 }

+
 pub fn update(
     battle: anytype,
     c1: pkmn.Choice,
@@ -162,7 +171,19 @@ pub fn update(
     const writer = std.io.null_writer;
     // const writer = std.io.getStdErr().writer();
     return switch (gen) {
-        1 => pkmn.gen1.calc.update(battle, c1, c2, options, allocator, writer, true),
+        1 => {
+            _ = .{ allocator, writer };
+
+            options.chance.reset();
+            const result = battle.update(c1, c2, options) catch unreachable;
+
+            UNREDUCED[std.math.log2_int_ceil(u128, options.chance.probability.q)] += 1;
+            options.chance.probability.reduce();
+            REDUCED[std.math.log2_int_ceil(u128, options.chance.probability.q)] += 1;
+
+            return result;
+        },
+        // 1 => pkmn.gen1.calc.update(battle, c1, c2, options, allocator, writer, true),
         else => unreachable,
     } catch unreachable;
 }
@@ -222,6 +243,16 @@ fn dump() !void {
     try bw.flush();
 }

+fn choose(rng: *pkmn.PSRNG, choices: []pkmn.Choice) pkmn.Choice {
+    if (!rng.chance(u8, 50, 100)) return choices[rng.range(u8, 0, @intCast(choices.len))];
+    var i: u8 = 0;
+    for (choices) |choice| {
+        if (choice.type == .Move) break;
+        i += 1;
+    }
+    return choices[rng.range(u8, if (i == choices.len) 0 else i, @intCast(choices.len))];
+}
+
 pub fn panic(
     msg: []const u8,
     error_return_trace: ?*std.builtin.StackTrace,
kjs@scheibo(main)$

generate.ts

class Random {
  seed: number;

  static seed(n = 4 /* https://xkcd.com/221/ */) {
    // Hash: https://burtleburtle.net/bob/hash/integer.html
    n = n ^ 61 ^ (n >>> 16);
    n = n + (n << 3);
    n = n ^ (n >>> 4);
    n = Math.imul(n, 0x27d4eb2d);
    n = n ^ (n >>> 15);
    return n >>> 0;
  }

  constructor(seed = Random.seed()) {
    this.seed = seed;
  }

  // Mulberry32: https://gist.github.com/tommyettinger/46a874533244883189143505d203312c
  next(min?: number, max?: number) {
    if (min) min = Math.floor(min);
    if (max) max = Math.floor(max);

    let z = (this.seed += 0x6d2b79f5 | 0);
    z = Math.imul(z ^ (z >>> 15), z | 1);
    z = z ^ (z + Math.imul(z ^ (z >>> 7), z | 61));
    z = (z ^ (z >>> 14)) >>> 0;
    const n = z / 2 ** 32;

    if (min === undefined) return n;
    if (!max) return Math.floor(n * min);
    return Math.floor(n * (max - min)) + min;
  }

  shuffle<T>(arr: T[]) {
    for (let i = arr.length - 1; i > 0; i--) {
      const j = Math.floor(this.next() * (i + 1));
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr;
  }

  sample<T>(arr: T[], remove = false) {
    if (arr.length === 0) throw new RangeError('Cannot sample an empty array');
    const index = this.next(arr.length);
    const val = arr[index];
    if (remove) {
      arr[index] = arr[arr.length - 1];
      arr.pop();
    }
    if (val === undefined && !Object.prototype.hasOwnProperty.call(arr, index)) {
      throw new RangeError('Cannot sample a sparse array');
    }
    return val;
  }
}

const SIZE = [
  0.0249, 0.0366, 0.1135, 0.1037, 0.0938, 0.0821, 0.0563, 0.0228,
  0.0373, 0.0677, 0.2194, 0.1818, 0.1503, 0.1313, 0.0964, 0.0437,
  0.1126, 0.2189, 1.9275, 1.8664, 1.7012, 1.3847, 0.8881, 0.3582,
  0.1030, 0.1806, 1.8609, 2.0923, 2.1131, 1.9675, 1.4675, 0.6951,
  0.0930, 0.1506, 1.6988, 2.1054, 2.5531, 2.7673, 2.4363, 1.5374,
  0.0819, 0.1321, 1.3817, 1.9662, 2.7667, 3.6171, 3.9472, 2.5671,
  0.0565, 0.0963, 0.8899, 1.4688, 2.4384, 3.9436, 6.1599, 6.2097,
  0.0228, 0.0431, 0.3574, 0.6934, 1.5369, 2.5646, 6.2106, 17.107,
];

const BITS = [
  24.003, 0.7847, 2.3503, 2.7924, 0.2737, 1.7332, 2.0515, 1.6754,
  6.8707, 0.9852, 2.3179, 0.6381, 0.7723, 0.8467, 1.0383, 1.9236,
  2.6151, 2.8837, 2.8266, 4.0021, 7.1337, 2.5668, 2.7578, 1.6082,
  1.4638, 1.6996, 1.7099, 2.2664, 2.5866, 0.9215, 0.9209, 0.5213,
  0.5381, 0.5767, 0.6324, 0.8283, 0.8043, 0.6783, 0.7182, 0.7805,
  0.7736, 0.4576, 0.4308, 0.4195, 0.4011, 0.4164, 0.4447, 0.4712,
  0.3372, 0.1534, 0.1194, 0.0907, 0.0826, 0.0826, 0.0853, 0.0739,
  0.0389, 0.0126, 0.0057, 0.0019, 0.0013, 0.0009, 0.0009, 0.0005,
];

const gcd = (a: number, b: number): number => b ? gcd(b, a % b) : a;

const random = new Random(Date.now());
const weighted = (table: number[], val = random.next() * 100) => {
  let i = 0;
  for (let sum = 0; i < table.length && sum + table[i] < val; sum += table[i++]);
  return i;
};

const size = weighted(SIZE);
const m = Math.floor(size / 8) + 2;
const n = (size % 8) + 2;

for (let i = 0; i < m; i++) {
  const a = [];
  for (let j = 0; j < n; j++) {
    const bits = weighted(BITS);
    const q = random.next(Math.pow(2, bits), Math.pow(2, bits + 1));
    const p = random.next(1, q);
    const f = gcd(p, q);
    a.push(q === 1 ? '1' : `${p / f}/${q / f}`);
  }
  console.log(a.join(' '));
}

results.txt

unreduced: { 123320226, 3987916, 11607359, 14366294, 1173838, 1106374, 177609, 18465, 55307371, 3359596, 12632237, 8893349, 1223977, 871367, 1468925, 124837, 12650201, 1301190, 3399761, 495519, 302602, 205717, 94261618, 5275280, 13669179, 10359663, 1260973, 1476995, 230049, 745663, 50968912, 3094266, 9187329, 3754180, 724883, 1377165, 112665, 1054180, 9954221, 766752, 1997592, 215300, 115646, 15205679, 1346530, 2797328, 3619331, 391646, 521543, 280466, 208345, 12742177, 843717, 1590996, 1661804, 132392, 178730, 23146, 149925, 2910109, 198802, 281126, 49349, 10616, 3906, 451, 35282, 1886, 3234, 676, 108, 68, 11, 3, 100, 63, 17, 12, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
reduced: { 123320226, 4031808, 12075637, 14346988, 1406018, 8904740, 10540230, 8607883, 35300526, 5061695, 11909010, 3278396, 3968199, 4350243, 5334774, 9883069, 13435819, 14816183, 14522788, 20561613, 36652106, 13187797, 14169171, 8262832, 7520875, 8732404, 8785114, 11644634, 13289696, 4734787, 4731706, 2678438, 2764513, 2963076, 3249216, 4255900, 4132272, 3484775, 3690039, 4009878, 3974445, 2350963, 2213400, 2155505, 2060895, 2139463, 2284565, 2420992, 1732482, 788394, 613352, 466117, 424230, 424348, 438156, 380448, 200086, 64643, 29515, 9863, 6489, 5223, 4380, 2415, 823, 351, 78, 31, 28, 21, 20, 12, 9, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
choices: { { 9831579, 4606604, 5261478, 7361496, 7798259, 3048509, 3796889, 5045325, 6389779 }, { 4611955, 102402, 150662, 466583, 426187, 385671, 337497, 231310, 93585 }, { 5264422, 153487, 278357, 901988, 747360, 617958, 539674, 396324, 179681 }, { 7369992, 462957, 899798, 7924810, 7673552, 6994155, 5693104, 3651427, 1472889 }, { 7813405, 423571, 742556, 7650787, 8602351, 8687616, 8089015, 6033287, 2857838 }, { 3051786, 382338, 619005, 6984502, 8655875, 10496832, 11377488, 10016465, 6320747 }, { 3806348, 336634, 543221, 5680871, 8083826, 11374946, 14871353, 16228547, 10554301 }, { 5057999, 232318, 395826, 3658640, 6038905, 10025086, 16213722, 25325447, 25530384 }, { 6397634, 93906, 177127, 1469514, 2850856, 6318753, 10543953, 25531465, 70335279 } }