C99 - 3x3 board in 0.084s
2020 edit/disclaimer: See comments section. It looks like there may have been errors in the original code. Proceed to the remainder of this answer with some skepticism until it is fixed.
Edit: I refactored my code and did some deeper analysis on the results.
Further Edits: Added pruning by symmetries. This makes 4 algorithm configurations: with or without symmetries X with or without alpha-beta pruning
Furthest Edits: Added memoization using a hash table, finally achieving the impossible: solving a 3x3 board!
- straightforward implementation of minimax with alpha-beta pruning
- very little memory management (maintains dll of valid moves; O(1) updates per branch in the tree search)
- second file with pruning by symmetries. Still achieves O(1) updates per branch (technically O(S) where S is the number of symmetries. This is 7 for square boards and 3 for non-square boards)
- third and fourth files add memoization. You have control over the hashtable's size (
#define HASHTABLE_BITWIDTH). When this size is greater than or equal to the number of walls, it guarantees no collisions and O(1) updates. Smaller hashtables will have more collisions and be slightly slower.
- compile with
-DDEBUG for printouts
fix small memory leak fixed in first edit
alpha/beta pruning added in 2nd edit
prune symmetries added in 3rd edit (note that symmetries are not handled by memoization, so that remains a separate optimization.)
memoization added in 4th edit
- currently memoization uses an indicator bit for each wall. A 3x4 board has 31 walls, so this method couldn't handle 4x4 boards regardless of time constraints. the improvement would be to emulate X-bit integers, where X is at least as large as the number of walls.
Due to lack of organization, the number of files has grown out of hand. All code has been moved to this Github Repository. In the memoization edit, I added a makefile and testing script.
Notes on Complexity
Brute-force approaches to dots and boxes blow up in complexity very quickly.
Consider a board with
R rows and
C columns. There are
R*(C+1) vertical walls, and
C*(R+1) horizontal walls. That is a total of
W = 2*R*C + R + C.
Because Lembik asked us to solve the game with minimax, we need to traverse to the leaves of the game tree. Let's ignore pruning for now, because what matters is orders of magnitude.
W options for the first move. For each of those, the next player can play any of the
W-1 remaining walls, etc.. That gives us a search-space of
SS = W * (W-1) * (W-2) * ... * 1, or
SS = W!. Factorials are huge, but that's only the beginning.
SS is the number of leaf nodes in the search space. More relevant to our analysis is the total number of decisions which had to be made (i.e. the number of branches
B in the tree). The first layer of branches has
W options. For each of those, the next level has
B = W + W*(W-1) + W*(W-1)*(W-2) + ... + W!
B = SUM W!/(W-k)!
Let's look at some small table sizes:
Board Size Walls Leaves (SS) Branches (B)
1x1 04 24 64
1x2 07 5040 13699
2x2 12 479001600 1302061344
2x3 17 355687428096000 966858672404689
These numbers are getting ridiculous. At least they explain why the brute-force code seems to hang forever on a 2x3 board. The search-space of a 2x3 board is 742560 times larger than 2x2. If 2x2 takes 20 seconds to complete, a conservative extrapolation predicts over 100 days of execution time for 2x3. Clearly we need to prune.
I started by adding very simple pruning using the alpha-beta algorithm. Basically, it stops searching if an ideal opponent would never give it its current opportunities. "Hey look - I win by a lot if my opponent lets me get every square!", thought no AI, ever.
edit I have also added pruning based on symmetrical boards.
I don't use a memoization approach, just in case someday I add memoization and want to keep that analysis separate. Instead, it works like this: most lines have a "symmetric pair" somewhere else on the grid. There are up to 7 symmetries (horizontal, vertical, 180 rotation, 90 rotation, 270 rotation, diagonal, and the other diagonal). All 7 apply to square boards, but the last 4 don't apply to non-square boards. Each wall has a pointer to it's "pair" for each of these symmetries. If, going into a turn, the board is horizontally symmetric, then only one of each horizontal pair needs to be played.
edit edit Memoization! Each wall gets a unique id, which I conveniently set to be an indicator bit; the nth wall has the id
1 << n. The hash of a board, then, is just the OR of all walls played. This is updated at each branch in O(1) time. The size of the hashtable is set in a
#define. All tests were run with size 2^12, because why not? When there are more walls than bits indexing the hashtable (12 bits in this case), the least significant 12 are masked and used as the index. Collisions are handled with a linked list at each hashtable index. The following chart is my quick-and-dirty analysis of how hashtable size affects performance. On a computer with infinite RAM, we would always set the table's size to the number of walls. A 3x4 board would have a hashtable 2^31 long. Alas we don't have that luxury.
Ok, back to pruning.. By stopping the search high in the tree, we can save a lot of time by not going down to leaves. The 'Pruning Factor' is the fraction of all-possible-branches which we had to visit. Brute-force has a pruning factor of 1. The smaller it is, the better.