The Stones Contest - The Perl Journal, Fall 1997

Russell Caton

Some time ago, I was shown a game simply called stones. It’s a simple game that can be played with stones, pebbles, matches, or coins. In the wee hours one morning, it dawned on me that stones could be played with a computer as well. The game is easy to learn, easy to play, and with a small number of stones, easy to win.

Two players sit opposite an odd number of stones. Each player takes one, two, or three stones in turn until no stones are left. The person with an odd number of stones wins. Here’s a sample game with fifteen stones:

Player One  Player Two  Remaining   Comment 
     -           -         15    The game begins
     2           -         13    Player one takes 2
     2           3         10    Player two takes 3
     3           3          9    Player one takes 1
     3           5          7    Player two takes 2
     6           5          4    Player one takes 3
     6           7          2    Player two takes 2
     7           7          1    Player one takes 1
     7           8          0    No stones left

Player one has seven stones, so he wins!

Your mission, should you choose to accept it, is to create a Perl subroutine that plays stones, using any strategy that you see fit, as long as your subroutine plays fairly.

Any subroutine which is deemed to be playing unfairly (e.g. peeking at opponent subroutines) will be disqualified.
Your subroutine will play every other subroutine twice, using a random number of odd stones. Your subroutine will be player one in one of the games, and player two in the other.
Points will be awarded as follows: three points for a win, one point for a loss. (This is to overcome the Norway effect.(A Eurovision Song Contest phenomenon. Two years running, Norway failed to get a single point. Awarding points for a loss means no one gets a zero.))
The subroutine with the most points will be declared the winner, and its creator(s) will receive $100. In the event of a tie, the prize will be split among all winners.

Obviously, there must be some ideal strategy. Here’s one that guarantees a win for player one with fifteen stones: Take two on your first move. On subsequent moves, if you have an odd number of stones, act so that 1, 8, or 9 stones are left. Otherwise, act so that 4, 5, or 12 stones are left.

Having just shown the solution, I’ll change the rules a little. For our contest, the maximum number of stones that you can take in any one turn will change from one game to another. In any turn, your subroutine can take between 1 and n, where n is a random integer between 3 and 9 chosen prior to the game. To increase the complexity further, the number of stones will be randomized between 1001 and 10001, inclusive.

Your subroutine will be passed four arguments at each invocation:

The number of stones you have
The number of stones your opponent has
The number of stones left in the pile
The maximum number of stones you may take at a time.

Your subroutine should return the number of stones that you wish to take. Subroutine that attempt to take more stones than allowed will be disqualified.

Here’s a sample subroutine that chooses a random number of stones between 1 and the maximum:

sub take_random_caton { 
    my $my_stones        = $_[0] ; 
    my $opponents_stones = $_[1] ; 
    my $remaining_stones = $_[2] ; 
    my $maximum_at_once  = $_[3] ; 

    # Take a random number of stones between 1 and
    # $maximum_at_once 
    # 
    if ( $remaining_stones == 1 ) { 
        return 1 ; 
    } 

    # Make sure we don’t take too many or we could
    # be in trouble 
    # 
    if ( $remaining_stones < $maximum_at_once ) {
        $maximum_at_once = $remaining_stones ; 
    } 

    return (int rand($maximum_at_once)) ; 
}

Entries should be supplied as a tar or zip file with two files. One file should contain your subroutine, and the second file should be called README and have your name, postal address, email address, and a description of how the subroutine works.

Please append your surname to the subroutine name (e.g. take_random_caton() above) to ensure that all subroutine names are unique, and don’t forget to my() any variables you create in your subroutine. Amusing variable names will not affect the competition results, but may make me more gentle in the analysis.

Entries should be sent via FTP to tpj.com and deposited in pub/orwant/stones before December 15, 1997. Please submit early and often! Winners, losers and strategies will be dissected in TPJ #9.

_ _END_ _

TABLE OF CONTENTS