Solving the board game Quoridor

Solving Quoridor This post significantly improves the state of the art in solving the board game Quoridor. I describe novel techniques that enable fully solving almost all board configurations with area ≤ 28 (e.g. 5x5, 8x3, 7x4, etc) for most wall counts on a consumer laptop. Background I was introduced to the board game Quoridor back in 2014 and was immediately taken by it. I usually spend a weekend returning to Quoridor once every couple years, writing different forms of AI bots to play it. This last weekend, I made a breakthrough that enables both much stronger bots, and much more complete solving. Rules The game is pretty simple: Pawns start on opposite sides of the 9x9 board Your goal is to get your pawn to the far side You have 10 walls On your turn, you can move your pawn 1 square, or place a wall You can jump over the opponent's pawn You can't place a wall that makes it impossible for a pawn to get to its goal That last rule is where all the performance complexity comes from.…