Project 2: Merge

The board images below confuse latex2html. You can get the real images here.  

Merge is a game played on a chessboard between 4 players. Each player starts with four pieces, one on each of that player's ``special squares''. The special squares are located as shown by letters in the upper left corners in the diagram below. [true]

Player 1 controls the pieces on squares A to D, player 2 controls E to H, player 3 controls I to L, and player 4 controls M to P. Each piece is labeled with the letter of the special square that it starts on.

Pieces can move one square orthogonally (not diagonally) on any given move. They may also stay put. More than one piece may occupy a single square as long as all pieces on the square are controlled by the same player.

All players submit orders for all of their pieces. All four players' moves are revealed simultaneously and are resolved according to the rules given below.

1.

Each piece moves as ordered. At this point, some squares may have pieces controlled by different players. For each such square s, we determine the player p_s with the most pieces on square s. If there is no unique p_s, then all pieces on s are removed (they will be placed back on the board in step 4). If there is a unique p_s, then all pieces other than those controlled by p_s are removed from s.

2.

At this point, all squares have pieces from a single player on them, or are empty. If a special square s (one with a label on it) is occupied by a piece belonging to a player p other than the player controlling s, then s becomes controlled by p.

3.

As a result of step 2, pieces with labels corresponding to squares s that have changed hands now become controlled by the new player occupying s. All such pieces are removed from the board.

4.

All pieces that are off the board are replaced on the board in their original locations. (Why won't this step ever violate the constraint that no square has pieces from more than one player on it?)

The crucial part of the game is the capture of opposing special squares. When such a square is captured, the captor gains a piece, and the player who formerly controlled the square loses a piece.

The aim of the game is to control as many pieces as possible. The game ends either (a) when one player controls all pieces, or (b) after some large number N of moves. The score of each player at the end of the game is the number of pieces controlled.

Here is a sample move. The original position below shows pieces using the player number with a superscript containing the label(s) of the piece(s) on that square. More than one label means there's more than one piece on the square. [true]

Each player controls their original four squares in the position above. Here are the moves:

Player 1	Player 2	Player 3	Player 4
A S	E W	I H	M W
B E	F S	J E	N H
C S	G W	K N	O W
D E	H S	L E	P W

Each player moves each of his/her pieces north (N), south (S), east (E), west (W), or hold (H). The outcome of this move is the position below. [true]

The squares that have changed hands are D, E, G, I, K, and O. Player 1 now controls 6 pieces (ABCEGI), Player 2 controls 3 pieces (DFH), Player 3 controls 3 pieces (JLO), and Player 4 controls 4 pieces (KMNP).

Make sure you understand how these moves happened. In particular, understand how:

• Players 1 and 2 swapped control of D and G.
• Player 3 succeeded in moving to e3 even though there's just one piece there in the end.
• The two pieces on h4 did different things.

Think also about the following:

• What would have been the outcome had Player 4 ordered piece N north instead of holding?
• Would the outcome have been the same if Player 3 had ordered piece I to move?
• Would the outcome have been the same if Player 3 had ordered piece K to go east?
• What is the minimum number of moves needed to achieve the initial position above from the starting position?
• What does it take to capture a labeled square that is occupied by the corresponding piece when that piece is continually ordered to hold?
• When would you consider a mutual removal (and replacement on the original squares) a good outcome? When would it be a bad outcome?
• When is having many pieces on one square a good idea? When is it a bad idea?
• If you have a choice of two squares to capture, how might the current location of the corresponding pieces affect your choice?
• Are ``alliances'' with other players a good idea? When? What kind of coordination is possible?

You will write a program that plays this game. The interface specifications will be given later. Your program will be run against other groups' programs in a tournament.