Fastest player for Dots and Boxes The challenge is to write a solver for the classic pencil and paper game Dots and Boxes .  Your code should take two integers m and n as input which specifies the size of the board.  


  Starting with an empty grid of dots, players take turns, adding a
  single horizontal or vertical line between two unjoined adjacent dots.
  A player who completes the fourth side of a 1×1 box earns one point
  and takes another turn. (The points are typically recorded by placing
  in the box an identifying mark of the player, such as an initial). The
  game ends when no more lines can be placed. The winner of the game is
  the player with the most points.




You can assume that either n = m or n = m - 1 and m is at least 2.

The challenge is to solve the largest possible Dots and Boxes game in under a minute. The size of a game is simply n*m.   The output of your code should be win , draw or lose which should be the result for the first player assuming both players play optimally.

Your code must be compilable/runnable on ubuntu using easily installable and free tools.  Please report your score as the largest area you can solve on your computer in 1 minute together with the time.  I will then test the code on my computer and make a rank ordered table of entries.

In the case of a tie-break, the winner will be the fastest code on the largest size board it can solve in under a minute.



It would be better if the code outputted not just win or lose but the actual score as well. This makes for a sanity check of correctness.
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!
Primary features:

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

Potential improvements:

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.

Code
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.
Results

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 squares, 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.
There are 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 W-1, etc.
B = W + W*(W-1) + W*(W-1)*(W-2) + ... + W!

B = SUM W!/(W-k)!
  k=0..W-1

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.
Pruning Analysis
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. &quot;Hey look - I win by a lot if my opponent lets me get every square!&quot;, 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 &quot;symmetric pair&quot; 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 &quot;pair&quot; 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 &lt;&lt; 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.