a day ago
- The post presents novel techniques that solve almost all Quoridor board configurations with area ≤ 28 (e.g., 5x5, 8x3, 7x4) for most wall counts on a consumer laptop.
- Key results include: odd-height boards are not always 2nd player wins (they become 1st player wins with sufficient walls), even-height boards are uniformly 1st player wins, and forced draws exist (e.g., 8x3 with 3 walls).
- The game's complexity stems from the rule that walls cannot fully block a pawn's goal, causing high branching factor and difficult evaluation; the author uses bitboards, transposition tables, and a wall legality heuristic to optimize.
- A breakthrough optimization precomputes all possible wall configurations (2.5 million for 5x5) and legality bitboards, enabling cheap legality checks and solving 5x5 in minutes.
- The author accidentally re-invented proof-number search by modifying negamax with iterative deepening and (0,∞) alpha-beta bounds, and suggests future work like enumerating wall frontiers or divide-and-conquer tiles.