Looking at each possible sequence of moves produces an n! time for analysis. My program looks at each possible position instead, which produces a 2n time for analysis. Although 2n gets large quickly, it's nowhere near as large as n!.
For each position the program stores the best score for the player on the move for future boxes. Boxes already surrounded are ignored. Thus, each position is uniquely identified by the lines present. No data about scoring up to that move is kept.
The analysis works backward from the position with all lines filled. That position is assigned the value given in the first line of the data file (normally zero). Then the program processes the positions with one less line filled in. When those are done, it processes the positions with another line less. Eventually it gets back to the original position.
For each such position the program considers all possible moves and keeps the score with the best result for the player on the move.
For each possible move the program first checks to see if zero, one or two new boxes were formed. If no new boxes were formed, the score for the move is the negative of the score for the resulting position since the position has the best score for the other player recorded. If one or two new boxes were formed, the score for the move is the score for the resulting position plus the number of new boxes since the player remains on the move.
A position is represented by a binary number with one bit (binary digit) place assigned to each line. The bit is 0 if the line is present and 1 if the line is absent. (I reversed the usual convention to make it easier to check for new boxes.)
I divide the lines into groups. Each group of lines is represented by consecutive bits in the position's binary number. These bits can be copied and placed in a separate number representing the state of the lines within the group. For example, for the 3x3 game there are 24 lines total. The program uses two groups of lines with 12 lines each. For each possible line count for a group (0 to 12), the program constructs a list of numbers representing a group with that number of lines present. Then to find the positions with n lines set, I combine all the first group state with i lines set with the second group state with n-i lines set where i varies over all possible values that don't result in an impossible number of lines for either group. For example, to find all positions with 15 lines in the 3x3 game, the program combines all first group states with 3 lines with all second group states with 12 lines (there's only one of those), then all first group states with 4 lines with all second group states with 11 lines, ... , and finally all first group states with 12 lines (again, only one possible) with all second group states with 3 lines.
Each line is given an index number that corresponds to its bit in the position's binary number. The program has two sets of box test values which are referenced using the index number of a new line. One set checks for a new box above or to the left of a new line. The other checks for a box below or to the right of a new line. These values are used to check if the other 3 lines are already present. The bits corresponding to those 3 lines are set to 1; all other bits are set to 0. The test is done using a logical "and" operation between the position's binary number and the test value. The "and" operation, for each bit position, produces 1 if the corresponding bits in both values are set; 0 otherwise. Since the position's binary number has bits set to 0 if a line is present, the "and" of this and the test value produces a zero result if and only if the three lines are already present.
If a box does not exist because a line is on the edge, the test value has all bits set, thereby testing for all lines being present. Since the test is performed before the new line is placed into the position's binary number, there is at least one line not set and the test with this value will say there's no new box.
After the Icelandic analysis ran in just a half an hour, I realized that computing time would not be a problem for the 3x5 game analysis. The Icelandic game has 30 open lines while the 3x5 game has 38 open lines making it 256 (28) times more difficult. 256 times half an hour is 128 hours or about 5 days. Since I could set up the program to start where it left off following an abort or reboot, the 5 days could easily be done over nights and weekends. So the problem became figuring out how to make it fit on my machine with 256 MB RAM and 16 GB free disk space.
At first, it didn't look possible. Storing the analysis would take 238 bytes or 256 GB of disk space. The space needed in RAM while calculating the value for positions with 19 lines set while referring to the results for positions with 20 lines set would be 56 GB, rather more than my one quarter GB of RAM.
Assuming that the lines were divided into two groups of 19 lines each, I could have in RAM just the values corresponding a given number of lines for each of the two groups. For example, while doing positions with 19 lines, I could be evaluating the positions with 9 lines in the first group and 10 lines in the second group. I'll call these the 9/19 10/19 positions. To calculate these values I'd have to refer to two sets of positions with 20 lines: 10/19 10/19 and 9/19 11/19. I did not need both those 20 line sets in memory at once; they could be used one at a time by saving the best scores considering just new lines in the first group for all the 9/19 10/19 positions and then seeing if any improvement could be made in the scores with a new line in the second group. The two buffers would take just 16 GB.
Then I realized I could break up the lines into more than two groups. By using 6 groups, I could cut the RAM needed to just 426 MB. A further cut using symmetry (see below) made it fit. Of course, to find, for example, the scores for the 4/8 3/6 3/6 3/6 3/6 3/6 positions, the program had to read in six different set of scores with 20 lines--each having one more line in one of the six groups.
The 3x5 game is symmetric vertically and horizontally, so by taking advantage of the symmetry, I could divide the space requirements by 4 (actually, by 3 in my final implementation). Paul Stevens reported a bug in the test for symmetry over a diagonal on a square board.
To calculate the score for a position, the program looks at the previously calculated scores for the positions that result from adding one more line. However, adding a line can result in a position that needs to be symmetrically transformed before its score can be found. To make sure that score for the position that results from the symmetric transformation is immediately available, it is necessary that the transformation map any lines into the same group. That way, the number of lines in each group remains the same after transformation.
Before the program assigns lines to groups, it first looks for lines that are associated with one another by symmetric transformation. In the 3x5 game, there are seven sets of 4 lines and fives sets of 2 lines that are associated. The program then assigns the sets of lines to the groups. For the 3x5 game using 256 MB RAM, six groups result (each with two sets of lines) of sizes 8 6 6 6 6 6.
To determine if a position should be symmetrically transformed, the program looks at the lines in the first group only. During the setup phase, the program scans through all possible line configurations in the first group of lines. To each configuration, it applies the vertical reflection, horizontal reflection and reflection through the origin transformations. If one of these transformation results in a number for the state of the lines in the group that is numerically smaller than the number for the state of the original lines, then (1) the configuration is NOT included in the linked list of configurations with a given number of lines set and (2) information is saved as to which symmetric transformation needs to be used to get a position whose score has been calculated--that is, to how to get to the corresponding configuration with the lowest numeric value for the state of its lines.
Even though only the first group is used to see if a transformation should be done, when the transformation is done it affects the lines in all the groups.
The scores for positions with a given number of lines in each group
are stored in a single disk file. For example, the scores for
the 4/8 3/6 4/6 2/6 3/6 3/6 positions are stored in file:
The backslashes separate nested folder names. 3x5 is the name of the game being analyzed. 19 is the total number of lines in the position. The rest of the folder names and the file name come from to number of lines in the groups. The number of lines in the last group is not used since it is fixed by the other numbers. The .bin means this is a binary file--its contents cannot be directly viewed. Nested folders are used because Windows processes folders with a large number of files very slowly.
Symmetric transformations cut the disk space required from 256 GB to 85 GB. However, it is not necessary to retain the entire analysis results. As soon as the program was done with positions with 19 lines, the results for positions with 20 lines could be deleted. With just 16 GB free disk space available, the program keeps the results for positions with 15 or fewer lines. This results in an "opening book" for the 3x5 game.
However, storing just the results for 20 line positions and 19 line positions still takes 22 GB. This is solved by deleting portions of the 20 lines position files as they are no longer needed for further calculation of scores for 19 lines positions. When the program goes through all possible combinations of lines counts for the groups that add up to 19 lines, the count for the first group of lines never decreases. Thus, once the count for the first group of lines moves from 0 to 1, for example, all the files starting with \Boxes\3x5\20\0\ can be deleted. With this change, the analysis fit in the 16 GB available.
At this point, the program was still inadequate for solving the 5x5 problems in chapter 12 of The Dots-and-Boxes Game by Elwyn Berlekamp (A. K. Peters, 2000). If computers continue to double their capacity every 18 months, we should be able to analyze the entire 5x5 game in 2034 since it has 22 more lines than the 3x5 game, which was analyzed in 2001. The program now can deal with positions with up to 36 open lines where the position has no symmetry and 14 Gb of disk space is available. That meant that just the 5x5 positions with 24 or more lines (out of the 60) could be tackled. None of the chapter 12 problems had that many lines.
A chain is a string of one or more boxes with two sides filled in. I made the assumption that once one of the players took a line in a chain, at least one of the best play lines involves all the rest of the lines in the chain being filled in, by one player or the other, before any lines elsewhere are filled in. Each set of chain lines are represented by a single "pseudo line". The position representation in the program has just one bit saying whether or not the chain has been completely filled or is still complete empty. For example, here is the position for problem 12.18 (before the dashed line move):
+ + + . + + + | . | | . | | . | + + . + . + + + | . | . | . | .... | . | + + . +-----+-----+-----+ | . | | . | .......... | . | . + + . + . +-----+ . + | | . | .... | .... | . | + + + . + . +-----+ | . | .... | + + +-----+ + +The dots mark the chains that are each represented by a single pseudo line. Of the 60 lines, 15 are filled in, 30 are empty, and 15 are involved in 6 chains. The positions that can arise from this starting position are represented by 36 bits--30 for the empty lines and 6 for the 6 chains. Thus, this position is just barely within the current capabilities of the program.
In many of the positions resulting from a given starting position, initial chains will have become part of longer chains. The program does not change the position representation scheme in this situation. The pseudo lines continue to represent just the initial chains. This is because the position representation is used as an "address" to access the previously calculated scores.
While evaluating whether moving into an initial chain is a good idea for the player on the move, the program has available the net score with best play for future boxes for the player on the move after the entire initial chain is filled. The program then needs to check the boxes around the chain to see which player will have the first chance to take the boxes in the chain, to see if that player would profit from making a sacrifice to avoid bring on the move after the chain is filled, and to check if the chain has been extended or even made part of a loop.
If the initial chain has a 3-sided box on either side just beyond the chain, then the player on the move can move into the chain with a capture and has the option of taking the boxes in the chain. Otherwise, it's the other player who has the option in the chain. I'll call the person with the option of taking the boxes in the chain, the "chain player".
If the initial chain has been extended enough so that the chain player can make a sacrifice later, then the score after the chain is completely filled already reflects this option and the chain player takes all the boxes in the initial chain. Otherwise, the program checks to see if there's enough room for a sacrifice assuming the best move into the chain by the player originally on the move and looking at the initial chain and any extensions. If there's still not enough room for a sacrifice, the chain player takes all the boxes. Otherwise the program checks if a sacrifice is profitable and if so evaluates moving into chain for the player originally on the move assuming the chain player makes the sacrifice.
The program allows a penalty to be applied to the score of the player making the last move. If this penalty is large enough, the moves chosen as best will be the same as those chosen by nimstring analysis. For example, I have analyzed problem 11.16 with penalties of increasing magnitude. The program does not allow fractional penalties because they would supply no additional information:
The final version of the program includes loony move analysis. In the output, a score is suffixed by v if player A must make the next loony move or by ^ if player B must. If neither player must make a loony move, no suffix is used. During analysis, two bits of the byte used to hold the score are used to hold the loony state of the move. This leaves just 6 bits for the scores. Thus, only scores from -32 to +31 can be stored. This makes the loony move analysis version of the program unreliable on boards bigger than 5 by 6. Therefore, I keep a version available that does not do loony move analysis for use with larger boards.
To find loony moves in a reasonable amount of computer time, the program makes a loony bonus check whenever it is possible to capture a box. If the box on the other side of the line being considered has exactly two other sides already filled in, the program concludes that the opponent's previous move was loony.
William Fraser wrote: "Are you taking into account the fact that [ab] and [ba] refer to equivalent links? Thus (if you put the eight corner links into the final 8 line group) you can store only 3^4=81 entries instead of 2^8=256. This would be completely independent of rotation/reflection. It cuts disk usage by 75% and memory usage by an average of 75%."
I implemented this suggestion, which made it possible to analyze the 4x4 game.
Translation of this page: Swedish
David Wilson / firstname.lastname@example.org