PREVIOUS  TABLE OF CONTENTS  NEXT 

The Stones Contest

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.

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:

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_ _


PREVIOUS  TABLE OF CONTENTS  NEXT