Fastest player for Dots and Boxes
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
-DDEBUGfor printouts
Potential improvements:
fix small memory leakfixed in first editalpha/beta pruningadded in 2nd editprune symmetriesadded in 3rd edit (note that symmetries are not handled by memoization, so that remains a separate optimization.)memoizationadded 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. "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.
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,
#that haven't already been placed.
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()
future.lines.add(line)
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.lines.add(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):
answers = {}
def mem_fn(*args):
if args not in answers:
answers[args] = fn(*args)
return answers[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")
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(" ");
output("*");
}
else {
if (gameEdges[i][j] && lastMove[1] == i && lastMove[2] == j)
output("<b>|</b>");
else if (gameEdges[i][j])
output("|");
else
output(" ");
if (j <= width - 2) {
if (squares[Math.floor(i / 2)][j] === 0)
output(" ");
else
output(" " + squares[Math.floor(i / 2)][j] + " ");
}
}
}
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();
}
document.addEventListener('DOMContentLoaded', initGame, false);