Homework

Write a program that plays Marienbad.
Assigned 31 May 2002

How to play Marienbad

Start with the following configuration of sticks:


   |  |  |  |  |

   |  |  |

   |


There are two players. Each turn, a player can take one or more
sticks from a single row. The player cannot take sticks from
different row during the same turn. The player taking the last
stick wins. (Traditionally, the player taking the last stick
loses, but in this case, the winning strategy is harder to describe.)


First player takes 3 sticks from the top row:


   |  | 

   |  |  |

   |


Second player takes 3 sticks from middle row:


   |  | 


 
   |


First player takes 1 stick form last row:


   |  | 


Second player takes all the remaining sticks and wins.

How to write the program

Proceed in three phases:

Phase I:
   Write a program that accepts input and keeps track of the game board.
   The input will be of the form r, n where r is the row number
   and n is the number of sticks to take from that row.
   In this phase, the computer does not play at all, it only prints
   out the board, wait for a move, updates the board, prints it out
   again, and waits for more input.
Phase II:
   To Phase I add to ability for the computer to play. It doesn't have
   to play well, but it does have to make legal moves and recognize
   when the game is over.
Phase III:
   To Phase II add a winning strategy.

Phase I

(3)  | | | | |
(2)  | | |
(1)  |

move? 3 2

(3)  | | 
(2)  | | |
(1)  |

move?

class Board
{

    private final static int BOARD_SIZE = 3 ; // BOARD_SIZE is 3 or 4.
    int [] board = new int [BOARD_SIZE] ; 

    Board( ) {
       // initialize the array board.
    }

    void printBoard() { 

    }

    boolean move( int row, int number ) { 
        // returns true on legal move and updates board
        // returns false of illegal and leaves board unchanged

    }

    boolean isDone() { 
        // returns true if there are no more sticks

    }

}

Phase II

Add the method

   void playSimpleStrategy()

to the class.

Phase III

Write the method

   void playWinningStrategy()

which implements a winning strategy.

One such strategy was given in class. For this strategy, the
methods needed are:

method int -> int[]  e.g. 5 -> {1,0,1}
method int [] -> int, eg. {1,0,1} -> 5
method int [], int [] -> int []  e.g. {1,1,0}, {1,0,1} -> {0,1,1}
method int [] -> boolean , return true only when {0,0,0}, else false

- method evalute which returns boolean, using all these things, if you
are  "on" strategy

- method to enumerate all possible moves starting from the current game

- method using both to find a winning move; if fails, use previous 
arbitrary move method.