TPJ readers submitted subroutines to play Stones, and I wrote a judging program that pit them against one another and recorded the results. Every subroutine played four games against every other subroutine; since going first is a big advantage, each subroutine got a chance to go first twice.
Two distinct strategies emerged, which I call end zoners and control freaks. The end zoners assumed that until the number of stones decreased below some threshold, the progress of the game was completely irrelevant. Once below the threshold, the subroutine could then seize control of the game and force the opponent into a loss.
The control freaks knew that for any number of stones in the pile, and any N, the outcome could be determined and forced from the very first move. They beat the end zoners. The control freaks could be further subdivided into two categories, Brutes and Calculators.
Brutes attempted to win the game using sheer computing power. They built and parsed large sections of the game tree - a data structure that represents your possible moves, your opponents' responses, your counterresponses, and so on - in order to determine the best move. This can be an extremely resource intensive task, especially when rebuilding the game tree on each successive call to the routine.
One brute was take_random_arenson(), which builds a game tree for every number of remaining stones, and then iterates each position to determine if it is a winning or losing position. For less than a hundred stones, this is reasonable. However, when it took several hours to complete its first game, I disqualified it.
Another brute was hash_cohoon(), which constructs an enormous hash. The values of the hash are either undefined (for a loss), or the number of stones to take for a forced win. This method is extremely memory hungry and finally had to be run on a machine with three gigabytes of RAM. The README promised that it would produce a single move in at most 15 seconds. A game of 5000 stones and an N of 6 could result in a game of 800 moves, which would have taken over three hours to complete. So I disqualified it too.
Calculators assumed that the number of stones taken to force a win is a pattern that repeats, based on a function of N. Once a routine found a pattern and followed it, it should win. take_stones_powell() and take_dinger() were calculators that performed very well.
take_cheat_abercrombie() shamelessly tried to add more stones to the pile. My first judging program was naive enough to allow his subroutine to cheat and get away with it. A quick modification resulted in his subroutine finishing with a dishonorable 121 forfeits.
no_mercy_rosella() was a huge 1.4Mb, containing 13,000 lines. This subroutine created 14 arrays, each containing 10,002 elements to perform lookups on any position to determine his next move. Unfortunately the running time of this routine was too high and his entry was disqualified too.
Competition Statistics. Fifty entrants submitted 79 subroutines; 73 made it into the final game, which took thirteen hours. Each subroutine played every other subroutine four times, for a total of 10512 games.
The smallest entry was from Tomas Rokicki, who managed to place fourth with only 87 meaningful characters:
my($m,$d,$r,$a)=@_;$r+=$a++;$m+=$a|$r/$a;
return((($r+=$d=$a&1)%=$a+$d)+=1&$m+$r)%$a||1;
The winner was a Calculator with a twist. It's really ten entries: two Masters and eight Slaves, all of whom conspire to let the Masters win. Given that the only communication between routines is the number of stones taken each turn, how does one subroutine make its presence known to the other? If the master routine seems to be losing and the number of remaining stones is less than 100, it emits an identifiable sequence of stones. By the time twenty stones are left, if the slave still believes it's playing a master, it takes a dive and lets the master win. Congratulations and $100 to Nick Solomon for TweedleDee and TweedleDum, who finished in that order.
_ _END_ _
The top entries:
| Name | Wins | Losses |
| TweedleDee | 209 | 79 |
| TweedleDum | 208 | 80 |
| master_branicky | 195 | 93 |
| stones_solovay | 194 | 94 |
| rokicki | 194 | 94 |
| Take_mcdougall | 194 | 94 |
| take_dinger | 194 | 94 |
| recorded_move_random_madsen | 193 | 95 |
| Dominus | 193 | 95 |