next up previous
Next: Project 4: Avoid the Up: W4444 Programming and Problem Previous: Project 2: They do

Project 3: Rectangle

Rectangle is played on a square grid of size $n$ by $n$. There are $p$ players, and each player has $b$ robots under his/her control. $n$, $p$, and $b$ are parameters. A player gives instructions to each robot to move north, south, east or west, or to stay put. (A move off the edge of the grid is not allowed, and the robot stays put.) As a robot moves, it leaves a trail. Imagine each robot painting its player's color on a cell of the grid as it arrives onto that cell. A previously painted cell is ``painted over'' when a new robot reaches that cell. Two robots can be present on a cell simultenously. However, in that case the cell reverts to an ``unpainted'' state. (This behavior happens even if the two robots belong to the same player.)

The aim for player $i$ is to create unbroken painted rectangles on the grid, where the boundary of the rectangle has $i$'s color. The interior of the rectangle does not need to be colored. When an unbroken rectangle is formed, player $i$ achieves a score equal to the number of ``paintable'' cells properly enclosed within the rectangle. What's more, the interior cells become ``unpaintable,'' and all paint is removed from them. When a robot visits an unpaintable cell, no paint is placed on that cell. When a large rectangle encloses a rectangle previously claimed (by any player), only the unclaimed cells count for the score of the enclosing player.

Note that the enclosing rectangle itself remains painted. Sides of this rectangle can be re-used for future rectangles.

Each player sees the entire board on each turn, and has complete information about all players' previous moves. The player controls the robots at each turn, telling them where to move. It is your job to write a computer player to play this game, and hopefully play it well.

To start the game, each player privately selects positions for all $b$ of its robots. These positions are revealed simultaneously, and robots for each player are placed as requested, and the cells are colored according to the rules above. Note that multiple robots can share a cell.

The game ends when some large number of moves (say $n^2$) have been played without any cells having been claimed. The precise number of moves for termination will be discussed in class, once we have some experience playing the game. The players are ranked according to their total score.

Special rules:

Some initial strategic considerations to think about:

We'll provide software than manages the state of the grid, and exports data structures that you can use. This software will interact with your program, asking for moves for each of your robots on each turn. The precise specifications will be provided later.

next up previous
Next: Project 4: Avoid the Up: W4444 Programming and Problem Previous: Project 2: They do
Ken Ross 2002-09-11