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:

• It is possible that an enclosing rectangle and an enclosed rectangle are completed at exactly the same time. In that case, the completions are resolved from smallest to largest, so that each player involved in such a tie gets some score.
• It is also possible for a player to complete a structure that simultaneously achieves multiple rectangles. In that case, enclosing rectangles take precedence over enclosed rectangles. The player gets a score from each cell enclosed by some rectangle.

Some initial strategic considerations to think about:

• The score is proportional to the area of the rectangle, which is quadratic in the perimeter. Thus, there is an incentive to build a small number of large rectangles rather than a large number of small rectangles. What other considerations might suggest that extremely large rectangles would not be a good idea? Are long-skinny rectangles better or worse than squarish ones?
• Should a player have multiple robots working on a single rectangle, or operate the robots on independent rectangles? What are the trade-offs?
• What is the role of defense in this game? What kinds of defensive strategies are possible?
• How would strategy change as the parameters $n$, $p$, and $b$ are varied?
• Would you use a different strategy if you're winning than you would if you're losing?

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.