next up previous
Next: Project 2: Cookie Cutter Up: W4444 Programming and Problem Previous: Group Membership for Projects

Project 1: Rectangles Revisited

In the 2002 class, we played the game of rectangle, described below. The game generated sufficient interest that I thought I would use the problem again. This time, you are not approaching the problem from scratch, but can (if you choose) take advantage of the work done by students in last year's class. The first discussion class (September 4) will survey the various approaches used last year.

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, if robots from (at least) two different players occupy a single cell, then the cell reverts to an ``unpainted'' state.

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. Remember that multiple robots can share a cell.

The game ends when some large number of moves have been played without any cells having been claimed. The precise number of moves for termination will be discussed in class. 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 outlined in class on September 4. We will also provide the player code for last year's players.

Feel free to enhance an existing player, to mix strategies from existing players, or to create a new player from scratch. The discussion and interface specs from last year can be found here. Code for last year's players is here.


next up previous
Next: Project 2: Cookie Cutter Up: W4444 Programming and Problem Previous: Group Membership for Projects
Ken Ross 2003-09-11