# 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.

• Do we have to use minimax?
– qwr
Jun 6, 2014 at 21:43
• @qwr Can you let me know what other option you had in mind?
– user9206
Jun 7, 2014 at 7:26
• Wait, there's a predictable winner in this game based solely on grid size? Jun 17, 2014 at 15:52
• @Charles Yes if both players play optimally.
– user9206
Jun 17, 2014 at 16:07
• @PeterTaylor I think you get two points but only one extra turn.
– user9206
Jun 18, 2014 at 7:46

## 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.

## 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. "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.

• input is formatted as specified by the question. two space-separated integers rows columns specifying the size of the board Jun 18, 2014 at 14:20
• @Lembik I don't think there is anything left to do. I'm done with this crazy project! Jun 26, 2014 at 16:20
• I think your answer deserves a special place. I looked it up and 3 by 3 is the largest problem size that has ever been solved before and your code is almost instant for it. If you can solve 3 by 4 or 4 by 4 you could add the result to the wiki page and be famous :)
– user9206
Jun 26, 2014 at 19:17
• @wrongu The first thing I want to say is that I am picking up the proverbial torch and reading through your code was a fantastic learning experience and way to start. I took away a lot of great ideas from you. I think an edit should be made to the post indicating that it may not be correct. solver_ab_sym_memo outputs a score of 0 on a 2x2 for instance, when it should be a score of 2, so who knows if there are some critical bugs Jun 28, 2020 at 7:42
• @jeremye thanks for looking into this. I might have time to fix things myself in a few weeks (might be fun to port to python too). Jun 28, 2020 at 14:34

# Python - 2x2 in 29s

Cross-posting from puzzles. Not especially optimized, but may make a useful starting point for other entrants.

from collections import defaultdict

VERTICAL, HORIZONTAL = 0, 1

#represents a single line segment that can be drawn on the board.
class Line(object):
def __init__(self, x, y, orientation):
self.x = x
self.y = y
self.orientation = orientation
def __hash__(self):
return hash((self.x, self.y, self.orientation))
def __eq__(self, other):
if not isinstance(other, Line): return False
return self.x == other.x and self.y == other.y and self.orientation == other.orientation
def __repr__(self):
return "Line({}, {}, {})".format(self.x, self.y, "HORIZONTAL" if self.orientation == HORIZONTAL else "VERTICAL")

class State(object):
def __init__(self, width, height):
self.width = width
self.height = height
self.whose_turn = 0
self.scores = {0:0, 1:0}
self.lines = set()
def copy(self):
ret = State(self.width, self.height)
ret.whose_turn = self.whose_turn
ret.scores = self.scores.copy()
ret.lines = self.lines.copy()
return ret
#iterate through all lines that can be placed on a blank board.
def iter_all_lines(self):
#horizontal lines
for x in range(self.width):
for y in range(self.height+1):
yield Line(x, y, HORIZONTAL)
#vertical lines
for x in range(self.width+1):
for y in range(self.height):
yield Line(x, y, VERTICAL)
#iterate through all lines that can be placed on this board,
def iter_available_lines(self):
for line in self.iter_all_lines():
if line not in self.lines:
yield line

#returns the number of points that would be earned by a player placing the line.
def value(self, line):
assert line not in self.lines
all_placed = lambda seq: all(l in self.lines for l in seq)
if line.orientation == HORIZONTAL:
#lines composing the box above the line
lines_above = [
Line(line.x,   line.y+1, HORIZONTAL), #top
Line(line.x,   line.y,   VERTICAL),   #left
Line(line.x+1, line.y,   VERTICAL),   #right
]
#lines composing the box below the line
lines_below = [
Line(line.x,   line.y-1, HORIZONTAL), #bottom
Line(line.x,   line.y-1, VERTICAL),   #left
Line(line.x+1, line.y-1, VERTICAL),   #right
]
return all_placed(lines_above) + all_placed(lines_below)
else:
#lines composing the box to the left of the line
lines_left = [
Line(line.x-1, line.y+1, HORIZONTAL), #top
Line(line.x-1, line.y,   HORIZONTAL), #bottom
Line(line.x-1, line.y,   VERTICAL),   #left
]
#lines composing the box to the right of the line
lines_right = [
Line(line.x,   line.y+1, HORIZONTAL), #top
Line(line.x,   line.y,   HORIZONTAL), #bottom
Line(line.x+1, line.y,   VERTICAL),   #right
]
return all_placed(lines_left) + all_placed(lines_right)

def is_game_over(self):
#the game is over when no more moves can be made.
return len(list(self.iter_available_lines())) == 0

#iterates through all possible moves the current player could make.
#Because scoring a point lets a player go again, a move can consist of a collection of multiple lines.
def possible_moves(self):
for line in self.iter_available_lines():
if self.value(line) > 0:
#this line would give us an extra turn.
#so we create a hypothetical future state with this line already placed, and see what other moves can be made.
future = self.copy()
if future.is_game_over():
yield [line]
else:
for future_move in future.possible_moves():
yield [line] + future_move
else:
yield [line]

def make_move(self, move):
for line in move:
self.scores[self.whose_turn] += self.value(line)
self.whose_turn = 1 - self.whose_turn

def tuple(self):
return (tuple(self.lines), tuple(self.scores.items()), self.whose_turn)
def __hash__(self):
return hash(self.tuple())
def __eq__(self, other):
if not isinstance(other, State): return False
return self.tuple() == other.tuple()

#function decorator which memorizes previously calculated values.
def memoized(fn):
def mem_fn(*args):
return mem_fn

#finds the best possible move for the current player.
#returns a (move, value) tuple.
@memoized
def get_best_move(state):
cur_player = state.whose_turn
next_player = 1 - state.whose_turn
if state.is_game_over():
return (None, state.scores[cur_player] - state.scores[next_player])
best_move = None
best_score = float("inf")
#choose the move that gives our opponent the lowest score
for move in state.possible_moves():
future = state.copy()
future.make_move(move)
_, score = get_best_move(future)
if score < best_score:
best_move = move
best_score = score
return [best_move, -best_score]

n = 2
m = 2
s = State(n,m)
best_move, relative_value = get_best_move(s)
if relative_value > 0:
print("win")
elif relative_value == 0:
print("draw")
else:
print("lose")

• Can be sped up to 18 seconds using pypy.
– user9206
Jun 18, 2014 at 15:56

# Javascript - 1x2 board in 20ms

Online demo available here (warning - very slow if larger than 1x2 with full search depth): https://dl.dropboxusercontent.com/u/141246873/minimax/index.html

Was developed for the original win criteria (code golf) and not for speed.

Tested in google chrome v35 on windows 7.

//first row is a horizontal edges and second is vertical
var gameEdges = [
[false, false],
[false, false, false],
[false, false]
]

//track all possible moves and score outcome
var moves = []

function minimax(edges, isPlayersTurn, prevScore, depth) {

if (depth <= 0) {
return [prevScore, 0, 0];
}
else {

var pointValue = 1;
if (!isPlayersTurn)
pointValue = -1;

var moves = [];

//get all possible moves and scores
for (var i in edges) {
for (var j in edges[i]) {
//if edge is available then its a possible move
if (!edges[i][j]) {

//if it would result in game over, add it to the scores array, otherwise, try the next move
//clone the array
var newEdges = [];
for (var k in edges)
newEdges.push(edges[k].slice(0));
//update state
newEdges[i][j] = true;
//if closing this edge would result in a complete square, get another move and get a point
//square could be formed above, below, right or left and could get two squares at the same time

var currentScore = prevScore;
//vertical edge
if (i % 2 !== 0) {//i === 1
if (newEdges[i] && newEdges[i][j - 1] && newEdges[i - 1] && newEdges[i - 1][j - 1] && newEdges[parseInt(i) + 1] && newEdges[parseInt(i) + 1][j - 1])
currentScore += pointValue;
if (newEdges[i] && newEdges[i][parseInt(j) + 1] && newEdges[i - 1] && newEdges[i - 1][j] && newEdges[parseInt(i) + 1] && newEdges[parseInt(i) + 1][j])
currentScore += pointValue;
} else {//horizontal
if (newEdges[i - 2] && newEdges[i - 2][j] && newEdges[i - 1][j] && newEdges[i - 1][parseInt(j) + 1])
currentScore += pointValue;
if (newEdges[parseInt(i) + 2] && newEdges[parseInt(i) + 2][j] && newEdges[parseInt(i) + 1][j] && newEdges[parseInt(i) + 1][parseInt(j) + 1])
currentScore += pointValue;
}

//leaf case - if all edges are taken then there are no more moves to evaluate
if (newEdges.every(function (arr) { return arr.every(Boolean) })) {
moves.push([currentScore, i, j]);
console.log("reached end case with possible score of " + currentScore);
}
else {
if ((isPlayersTurn && currentScore > prevScore) || (!isPlayersTurn && currentScore < prevScore)) {
//gained a point so get another turn
var newMove = minimax(newEdges, isPlayersTurn, currentScore, depth - 1);

moves.push([newMove[0], i, j]);
} else {
//didnt gain a point - opponents turn
var newMove = minimax(newEdges, !isPlayersTurn, currentScore, depth - 1);

moves.push([newMove[0], i, j]);
}
}

}

}

}//end for each move

var bestMove = moves[0];
if (isPlayersTurn) {
for (var i in moves) {
if (moves[i][0] > bestMove[0])
bestMove = moves[i];
}
}
else {
for (var i in moves) {
if (moves[i][0] < bestMove[0])
bestMove = moves[i];
}
}
return bestMove;
}
}

var player1Turn = true;
var squares = [[0,0],[0,0]]//change to "A" or "B" if square won by any of the players
var lastMove = null;

function output(text) {
document.getElementById("content").innerHTML += text;
}

function clear() {
document.getElementById("content").innerHTML = "";
}

function render() {
var width = 3;
if (document.getElementById('txtWidth').value)
width = parseInt(document.getElementById('txtWidth').value);
if (width < 2)
width = 2;

clear();
//need to highlight the last move taken and show who has won each square
for (var i in gameEdges) {
for (var j in gameEdges[i]) {
if (i % 2 === 0) {
if(j === "0")
output("*");
if (gameEdges[i][j] && lastMove[1] == i && lastMove[2] == j)
output(" <b>-</b> ");
else if (gameEdges[i][j])
output(" - ");
else
output("&nbsp;&nbsp;&nbsp;");
output("*");
}
else {
if (gameEdges[i][j] && lastMove[1] == i && lastMove[2] == j)
output("<b>|</b>");
else if (gameEdges[i][j])
output("|");
else
output("&nbsp;");

if (j <= width - 2) {
if (squares[Math.floor(i / 2)][j] === 0)
output("&nbsp;&nbsp;&nbsp;&nbsp;");
else
output("&nbsp;" + squares[Math.floor(i / 2)][j] + "&nbsp;");
}
}
}
output("<br />");

}
}

function nextMove(playFullGame) {
var startTime = new Date().getTime();
if (!gameEdges.every(function (arr) { return arr.every(Boolean) })) {

var depth = 100;
if (document.getElementById('txtDepth').value)
depth = parseInt(document.getElementById('txtDepth').value);

if (depth < 1)
depth = 1;

var move = minimax(gameEdges, true, 0, depth);
gameEdges[move[1]][move[2]] = true;
lastMove = move;

//if a square was taken, need to update squares and whose turn it is

var i = move[1];
var j = move[2];
var wonSquare = false;
if (i % 2 !== 0) {//i === 1
if (gameEdges[i] && gameEdges[i][j - 1] && gameEdges[i - 1] && gameEdges[i - 1][j - 1] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j - 1]) {
squares[Math.floor(i / 2)][j - 1] = player1Turn ? "A" : "B";
wonSquare = true;
}
if (gameEdges[i] && gameEdges[i][parseInt(j) + 1] && gameEdges[i - 1] && gameEdges[i - 1][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j]) {
squares[Math.floor(i / 2)][j] = player1Turn ? "A" : "B";
wonSquare = true;
}
} else {//horizontal
if (gameEdges[i - 2] && gameEdges[i - 2][j] && gameEdges[i - 1] && gameEdges[i - 1][j] && gameEdges[i - 1] && gameEdges[i - 1][parseInt(j) + 1]) {
squares[Math.floor((i - 1) / 2)][j] = player1Turn ? "A" : "B";
wonSquare = true;
}
if (gameEdges[i + 2] && gameEdges[parseInt(i) + 2][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][parseInt(j) + 1]) {
squares[Math.floor(i / 2)][j] = player1Turn ? "A" : "B";
wonSquare = true;
}
}

//didnt win a square so its the next players turn
if (!wonSquare)
player1Turn = !player1Turn;

render();

if (playFullGame) {
nextMove(playFullGame);
}
}

var endTime = new Date().getTime();
var executionTime = endTime - startTime;
document.getElementById("executionTime").innerHTML = 'Execution time: ' + executionTime;
}

function initGame() {

var width = 3;
var height = 2;

if (document.getElementById('txtWidth').value)
width = document.getElementById('txtWidth').value;
if (document.getElementById('txtHeight').value)
height = document.getElementById('txtHeight').value;

if (width < 2)
width = 2;
if (height < 2)
height = 2;

var depth = 100;
if (document.getElementById('txtDepth').value)
depth = parseInt(document.getElementById('txtDepth').value);

if (depth < 1)
depth = 1;

if (width > 2 && height > 2 && !document.getElementById('txtDepth').value)
alert("Warning. Your system may become unresponsive. A smaller grid or search depth is highly recommended.");

gameEdges = [];
for (var i = 0; i < height; i++) {
if (i == 0) {
gameEdges.push([]);
for (var j = 0; j < (width - 1) ; j++) {
gameEdges[i].push(false);
}
}
else {
gameEdges.push([]);
for (var j = 0; j < width; j++) {
gameEdges[(i * 2) - 1].push(false);
}
gameEdges.push([]);
for (var j = 0; j < (width - 1) ; j++) {
gameEdges[i*2].push(false);
}
}
}

player1Turn = true;

squares = [];
for (var i = 0; i < (height - 1) ; i++) {
squares.push([]);
for (var j = 0; j < (width - 1); j++) {
squares[i].push(0);
}
}

lastMove = null;

render();
}