Project 1: Jackhammer

Jackhammer was a project from the 2007 version of Programming and Problem Solving. The project description from 2007 is presented below. We will revisit this project in 2008, with the reports and programs from last years' groups available to you in courseworks. Of course, you're welcome to start from scratch if you think you have a new way of approaching the problem. (An advantage of starting with a previous problem is that it is easier to learn the mechanics of working with the provided programming interface.)

Directly building on the code from last year is acceptable, but keep the following points in mind:

• Your solution will be evaluated based on the increment beyond the code you started with. Tweaking a few parameters to slightly improve performance is unlikely to lead to a distinctive solution.
• Last year's code may have limitations that prevent a full exploration of the design space without substantial rewriting. Also, there may be subtle bugs remaining in the code. (Several groups have observed these issues in the past, and have regretted the choice to extend existing code rather than to start from scratch.)

Jackhammer is a game played on a triangular mesh, similar to that used in Chinese checkers. There are three players, who each start in one corner of the mesh. The size of the mesh is 17 units on a side, meaning that there are $17*18/2=153$ positions on the board.

On a turn, a player may move to an adjacent cell in any of the (up to) 6 valid directions for movement. Alternatively, a player may stay put and use a jackhammer to ``knock out'' an adjacent cell. Once a cell is hammered in this way, it is no longer available for movement by any of the players. A player may also choose to stay put without hammering a cell.

All players specify their moves simultaneously, and moves are resolved simultaneously. Multiple players can occupy the same cell.

Minor rules:

• You cannot hammer a cell with an opposing player on it.
• Movement turns are resolved before hammer turns, so that a hammer move that looks possible might become impossible (and vice versa). If an attempt to hammer becomes impossible, the player attempting to hammer does nothing.
• The simulator will prevent a player from making illegal moves (e.g., off the board, or onto a previously hammered cell). These will also become no-ops.
• Hammering a previously-hammered cell is a no-op.

A game finishes after 1000 turns. (In class we can discuss whether this is a reasonable number. We can always change it if a larger number turns out to be more interesting.)

The idea of the game is to claim territory. At the end of the game, a player's score will be the number of unhammered cells reachable (in zero or more legal moves) from the player's final position. However, if some other player is also reachable from the player's final position, then the score for both players is zero. It is possible for all three players to score zero!

Your job is to write a computer player to score well in this game. Your program will be run against the programs of other groups, and the winner will be the player with the highest average score over all rounds played.

Your player will not know the identity of the opposing players. (Nevertheless, a smart program might be able to guess identities based on player behavior: we'll discuss whether this is considered ethical in class.) The complete board state and history is available to all players.

Some things to think about:

• Is it possible to trap another player?
• Should a player try to assemble a region that includes the player's starting corner? Why or why not?
• What defensive strategies are available if an opponent (or both opponents) start to box you in?
• Do you think the time limit will come into play, or do you think that regions will be settled long before the limit is reached?
• It is possible for two players to gang up on a third. If you were trying to gang up with an opponent against the other opponent, how would you coordinate it?