/ 
Games-Chomp-0.02
/ Games::Chomp

NAME

Games::Chomp - Playing Chomp and calculating winning positions

SYNOPSIS

use Games::Chomp;
my $chomp = new Games::Chomp;
$chomp->run;

DESCRIPTION

Chomp is the name of a mathematical table game with 
finate number of positions. Though it is easily proven 
that the one who moves first has a winning strategy
there is no mathematical function that will calculate
the next winning move from any given position.

This module provides an algorithm to programatically 
calculate the winning moves for any given position.

The current implementation has some O(n**4) (?) complexity
so it is not a good one but this is the first version after
all.

THE RULES

There is a chocolate of n*m cubes.
The upper left cube is poisoned. Two people are eating the
chocolate (at least one cube at a time) and whoever eats the 
poisoned chocolate looses.

Eating the chocolate is done by pointing at one of the existing 
cubes eating it and everything to the right and below it.

Examples:
In the following case 
z - is the poisoned cube.
o - is a regular cube
x - is where the player points

Beginning: a chocolate with 4 rows and 6 cubes in every row.
zooooo
oooooo
oooooo
oooooo

player 1 points at row 2 cube 4

zooooo
oooxoo
oooooo
oooooo

result:

zooooo
ooo
ooo
ooo


player 2 points at row 3 cube 2

zooooo
ooo
oxo
ooo

result:

zooooo
ooo
o
o

player 1 points at row 1 cube 2

zxoooo
ooo
o
o

z
o
o
o

player 2 points at row 2 cube 1

z
x
o
o

result:

z

player 1 has to eat the poisoned cube so s/he looses.

METHODS

use Games::Chomp;
my $chomp = new Games::Chomp;

$chomp->run;
   ask for position in row-length representation
   computes all the positions up to that position and
   saves them in a file called chomp.txt in the local
   directory.
   Using run later will use the already calculated
   positions that were saved in that file.

$chomp->reset;
   Empties the list of winning positions kept in memory.
   The only case you want to use this is if you want to
   benchmark the module and start from an empty environment.

$chomp->resolve(POSITION);
   POSITION is array reference, it is a reference to a row-length 
   representation.
   
   resolve returns 1 if the above position is a winning position
   and returns 0 if it is a loosing position. As a side effect
   it *might* compute the 'winningness' of all the positions
   which are smaller than this one.

$chomp->show_all_winning_pos
   prints all the winning positions calculated so far
   (except the already obvious onces.) in row-length representation.

$chomp->transpose(POSITION)
   returns a reference to an array which is a POSITION where
   the rows and the columns are transposed.
   given [5,4,3]  it returns [3,3,3,2,1]
   not implemented yet

REPRESENTATIONS

A certain state of the game can be represented in different ways.

ROW-LENGTH
One of the ways I call row-length representation. I use this
representation in my implementation. In this representation we
give a list of numbers that represent the number of chocolates 
in the given row. [5,4,3] is the same as
    ooooo
    oooo
    ooo

AUTHOR

Gabor Szabo <lt>gabor@tracert.com<gt>

COPYRIGHT

The Games::Chomp module is Copyright (c) 2002 Gabor Szabo.
All rights reserved.

You may distribute under the terms of either the GNU General Public
License or the Artistic License, as specified in the Perl README file.

SEE ALSO

Games::NIM