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!

I wrote this website for fun. If you like it, do me a favour and help spread the word about it with the buttons to the left. I'm always looking for feedback so 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.

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.

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.

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-edge*s - 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

- There are no boxes with only 1 edge left
- There is one box with only 1 edge left which is part of a chain of length 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.

- 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
`n`algorithm in the references here.^{2} - 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.

- 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

- Wikipedia article - my favourite beginning resource on any subject
- Martin Fierz - Excellent introduction to strategy game programming
- David Wilson - Compendium of dots and boxes links
- Winning Ways book on Amazon - the seminal but readable book on mathematical games. Volume 3 has a chapter on Dots & Boxes
- Sophisticated Child's Play on Amazon - book on dots and boxes in particular Not much new material from Winning Ways but has a large set of problems and answers
- Demaine & Hern's overview of current knowledge of computational complexity of a set of games including Dots and Boxes
- Kukluk, Holder & Cook Experimentation of planar graph isomorphism algorithms

games played. Average human score is (% won)

No. | Score | Name | Time | Result | Duration (secs) | BoardSize | Comment |
---|

Loading Please Wait...

Final scores:

Enter your name and comment for the high score table:

Submit

If you enjoyed playing, please spread the word and share the site with your friends: