require Game::Stones; $take = Game::Stones::Take($my_stones, $his_stones, $pile, $maxTake);
Game::Stones
plays the game of Stones.
Whenever it is the module's turn,
call Game::Stones::Take
.
The parameters are:
$my_stones
$his_stones
$pile
$maxTake
Game::Stones::Take
returns the number of stones that the
module takes on that turn.
maxTake - the maximum number of stones that may be taken in one turnThe state, or position, of a game of Stones is described by a 4-tuple:
(Pile, Turn, A, B)Where:
Pile is the number of stones remaining in the pile Turn indicates which player has the next turn A is the number of stones in player A's pile B is the number of stones in player B's pileFor example, the position at the start of a game with 7 stones, where A goes first, would be written
(7, A, 0, 0).
We can further simplify by recalling that there are always an odd number stones in the game. Therefore, the parity of B's pile is determined by Pile and the parity of A's pile. This means that we can represent any position as a 3-tuple:
(Pile, Turn, pA)where Pile and Turn are as before, and pA is the parity of A's pile.
/* Pile Turn pA */ int Winner[10002][ 2 ][ 2]Each time we encounter a position in the move tree, we check the table. If there is an entry, we prune the search tree at that node and use the saved result; otherwise, we evaluate the position and record the result in the table.
Regardless of the potential of a recursive algorithm to explode exponentially, the number of positions in the table is linear in Pile. Since we never evaluate any position more than once, we can now search the move tree in linear time.
This technique of reducing an exponential algorithm to a polynomial one by keeping a table of previously solved sub-problems goes by the general name "dynamic programming".
# Pile Turn pA Winner[ 0]{ A}[ 0] = "B"; Winner[ 0]{ A}[ 1] = "A"; Winner[ 0]{ B}[ 0] = "B"; Winner[ 0]{ B}[ 1] = "A";For positions in higher rows, we define the winner as the player who has a winning strategy from that position.
maxTake = 3 Pile Turn pA Current position ( 5, A, 1) Accessible positions ( 4, B, 0) ( 3, B, 1) ( 2, B, 0) Current position ( 5, B, 1) Accessible positions ( 4, A, 1) ( 3, A, 1) ( 2, A, 1)There are two significant facts about accessible positions:
Each row of the table is specified by 4 bits: the winner for the 4 positions in that row. maxTake rows are specified by 4*maxTake bits. Therefore, the table must repeat within 2^(4*maxTake) rows.
For maxTake==3, the maximum cycle length is 2^(4*3) or 4096, which is less than 10001, but not by enough to bother with. For any higher value of maxTake, the maximum cycle length is greater than 10001.
However, this is only an upper bound. The cycle length might be less. For maxTake from 3 to 9, the cycle length turns out to be far less - no more than 20.
Rather than evaluate the table all the way up to 10001, we can stop once we detect a cycle. When presented with a position in a row that we have not evaluated, we reduce Pile modulo the cycle length and obtain the result from a row that we have evaluated.
$take = Game::Stones::Take($my_stones, $his_stones, $pile, $maxTake)
$Game[$maxTake] = { position => $position, lower => $lower, period => $upper - $lower };$position is the table of game positions. $lower is the first row in the table cycle and $upper is the last. period is the period of the cycle. We compute the period and discard $upper.
The position table is indexed like this:
$position->[$pile]{me}[$pA]{winner} = 'him'; $position->[$pile]{me}[$pA]{take } = $take;The players are represented by the strings 'me' and 'him'. Since we actually want to play this game, we need to record not just the winner for each position, but also the number of stones to take from that position in order to win. Thus, there is one final hash after the three indices into the table:
{ winner => $winner, take => $take }
for my $pile (1..10001) { for my $player (qw(me him)) { for my $parity (0..1) { Play($maxTake, $position, $pile, $player, $parity);Play() iterates over the accessible positions
for (my $take=1; $take<=$maxTake && $take<=$pile; $take++) {and sets winner and take for the current position. $position1 is a reference to an accessible position; Play() gets to it by computing its indices in $position->[]{}[] from the current position and $take:
my $pile1 = $pile-$take; my $player1 = $Other{$player}; my $parity1 = $player eq 'me' ? $parity ^ ($take & 1) : $parity; my $position1 = $position->[$pile1]{$player1}[$parity1];The expression for $parity1 is slightly squirrelly; review the pA column in the examples of accessible positions shown above to see why this is.
If there are several winning values for take, Play() chooses the largest, on the consideration that we might as well get it over with. If there are no winning values for take, it takes 1 stone, so as to give the other player more opportunities to make a mistake.
After filling in each row, GenerateGame() calls Cycle() to see if there is a cycle in the table. For our purposes, a cycle must contain at least maxTake rows. We can't detect a cycle until the table is twice the cycle length. Cycle() checks for all possible cycle lengths between these two bounds.
Cycle() calls CompareBlocks() to compare blocks of rows for equality. CompareBlocks() calls CompareRows() to compare rows. Rows compare equal if they have the same winners, because winner and take depend only on the winners in lower rows, not the take values.
When Cycle() detects a cycle, it returns its bounds as ($lower, $upper) to GenerateGame(). GenerateGame() breaks out of its loops, records $lower and computes period, and returns.
GetRow($pile, $maxTake) calls GenerateGame() to compute the tables for $Game[$maxTake], if it hasn't already done so. Then it uses $lower and $period to reduce $pile to a row of the table that has been evaluated:
my $row = $pile < $lower ? $pile : $lower + ($pile-$lower) % $period;Finally, it indexes into $Game[$maxTake]{position} with $row and returns a row from the table.
Take() calls GetRow() to get a row from the table, and then indexes into the row with 'me' (because it's my turn) and $mine&1 (the parity of my pile). This gives it a single position from the table; it returns the take value for that position.
-w
. Sorry.
"The Stones Contest: Results", The Perl Journal, #9 (Spring 1998), p64.