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:

• 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 provided later.