Dots And Boxes

How To Play

This is a computerised version of the old classic which lets you play the game online. The aim is complete more boxes than your opponent.
You and your opponent take it in turns to join up two adjacent dots with a line.
If any player fills a box they must make another move.
You can play 1 or 2 player. But watch out, the computer strategy is driven by a reasonably intelligent algorithm!

Spread the word / Feedback

I wrote this website for fun. If you have anything to say, you can leave a message on my personal website. Or tweet me at @dotsandboxes. You might also like my other html5 project crosswordex
where you can compile your own crossword in under a minute and challenge your friends.

Expert Play

One simple strategy you should be aware of is the double crossing move.
Take all the boxes in a long chain except the last two.
Let the opponent take these and she must give you more boxes with her extra move.
But the theory behind the game is actually quite complex and is all about trying to get control of the board.
To get into the details read the resources at the bottom of this page.

How my engine works

Graphics

I am using SVG with pure JavaScript. New elements are drawn by manually appending elements to the svg placeholder. Elements are given animinate
sub-elements if animations are supported by the browser. There is some minor housekeeping to make sure that the animations happen in sync and are queued correctly.

In order to keep the browser responsive, the main cpu intensive tree-searching (see below) is done in a separate web-worker thread which reports back to the main
JavaScript thread every time it completes a further level of depth. When the time is up (or the user forces a move) the best move so far is chosen.

Gameplay

The game of dots and boxes has been shown (in sketch-proof at least) to be np-hard which means the algorithm
to solve an n × n board is exponential in n.
However the game has a rich structure and you can massively outperform the naïve solving algorithm
by taking advantage of symmetries and mathematical analysis of the game.

I use a modification of the half-edge data structure to represent the board. Each edge of each box is called a half-edge
allowing double counting; thus an edge between two neighbouring boxes will be represented by two half-edges – one for each box that it is part of.
So the total number of half-edges is N = Width × Height × 4 and each half-edge is assigned an index ranging from
0 to N − 1.

First, I maintain two arrays of size N:

Other half-edge

Defines the index of the other side of the half-edge. Or − 1 if there is no other half (ie. this edge is on the boundary so is a border for only one box)

Next half-edge

The index of the next half-edge for the box that is this half-edge is associated with.
By “next” we could just give the one that is anticlockwise. In fact the ordering doesn’t matter, so long as the sequence of next half-edges goes in a loop
and cover all 4 edges of this box

When considering which move to take I initially look to see if there are any of the following free moves I
can take. If there are, I take one and do not bother searching the rest of the game tree.

• If there is a broken chain of length not equal to 3 I will eat a square from it
• If there is a broken loop of length greater than 4 I will eat a square from it
• If there is a broken chain and a broken loop then I will eat a square from the broken loop
• If there are 2 or more broken loops then I will eat a square from one of them
• If there are 2 or more broken chains then I will eat a square from one of them

After doing this the game will be in one of three states

1. There are no boxes with only 1 edge left
2. There is one box with only 1 edge left which is part of a chain of length 3
3. There is one box with only 1 edge left which is part of a loop with 4 boxes remaining

Once this is done I simplify the game structure somewhat. In the half-edge data structure I only include boxes that have 3 or more edges left.
Any boxes of valence 2 will be collapsed. Any any boxes of valence 1 will be represented by a flag indicating which of the three
states above the game is in.
So the final data structure consists of

Other half-edge

As above

Next half-edge

As above

Chain lengths

Array of size N representing the number of boxes of valence 2 that have been collapsed between this half-edge and its
other half-edge

Independents

Array of independent chains and loops. The value in the array indicates the size

Independents Are Loops

Boolean flag indicating if the Independents are loops or chains

Looney Value

Value of 0, 2 or 4 indicating the which of the 3 states above the game is in

Who To Play Next

Boolean indicating who will be playing next

Score so far

Number of boxes the player to play next already has − number of boxes the other player has

I then perform a depth-first mega-max search of the game tree with alpha-beta pruning.
The end evaluate function consists of counting the number of boxes by which one person leads.
If the previous move was looney (ie. Looney Value above is 2 or 4) then it is known that
the next player to move can capture at least half the remaining squares. So I simply assign 3/4 to that player.

Future Improvements

• Usng a simple hash-table to cache game values and avoid recomputing is the lowest hanging fruit in terms of performance
• When using the hash-table above I should take care to identify games that are equivalent but have different representations in my structure (eg. a permutation of half-edges).
  Determining if two planar graphs are isomorphic is a linear time problem in theory (though I know of no such actual algorithm actually written) so it should be tractable to do so.
  I have seen a n2 algorithm in the references here.
• In the evaluate and megamax, I should also keep track of known maximum and minimum scores (ie. after looney moves) as well as the average score which is what it currently returns
• Nimstring analysis
• Improve move ordering (eg. search sacrifice moves last)
• Search tree with several webworkers in parallel
• etc. etc.

Other dots and boxes games

Let me know if you have developed a version and I’ll include it here

PRBoxes

Very Strong opponent. Uses full nimstring analysis etc. This is the best computer program for the game I have found

Knox

Very strong algorithm that goes even further than nimstring analysis applying some techniques in the middle game. I haven’t been able to get it
to run and test it out yet though…

Dabble

Strong open source written in C with a nice GUI runnable in windows

Ossie’s Dots and Boxes

A version of the game I wrote in Visual Basic a while ago. Does not do anything particularly smart

Web Dots and Boxes

Pretty weak but online version of the game

Resources