Project 3: Push

The game of Push is played between 6 players on a hexagonal grid. The grid is itself hexagonal, resembling the inner part of a Chinese Checkers board, with five slots on each side. There are thus 61 slots altogether. Each player is positioned at one of the six corners of the grid. This corner slot is called the player's home slot. The board starts with a coin in every slot, 61 coins in total. On each turn, all six players submit moves that are resolved simultaneously as described below. A game consists of a fixed number m of turns, known in advance to all players.

A move consists of pushing a pile of coins from one slot to an adjacent slot. A player can only ``push'' coins, meaning that they end up further from the player's home slot than before: Of the six potential directions for a move, only three are available to each player. The result of a move is that the adjacent slot now contains all of the coins from the original slot, together with any coins that were on the adjacent slot (and were not themselves moved by another player on that turn). Players can only push the entire pile on a slot; partial stacks of coins cannot be moved.

Players must make a valid move, from a slot containing at least one coin in a direction where a valid slot exists (i.e., not off the edge of the board); players cannot pass. Players that attempt invalid moves will receive a final score of zero. In the unlikely event that a player has no valid moves (when could that happen?) the simulator will notice, and will accept (but not execute) an invalid move without penalty.

The only possible move conflict in the game is when two or more players try to move the same pile in different directions. When that happens, the simulator will choose randomly among the conflicting players, and execute one of the players' moves.

At the end of the game, each coin that is closer to player X's home slot than to all other players' home slots contributes to the score of player X. The score of a coin is multiplied by a bonus factor that depends on the slot S the coin occupies. If the distance from the player's home slot to S is d, and the distance from S to the closest other player is e with e>d, then the bonus factor is e-d. So, the bonus for coins on the home slot itself is 4, since that slot is distance 0 to the home slot (trivially) and distance 4 to the nearest opponent's home slot. The bonus for a slot one step away from the home slot along the edge of the board is 2.

All attempted moves are published at the end of each move, so that all players have access to the entire history of the game. However, players do not know the identity of the other players. (If we didn't hide player identities, it might be possible for two players, or two instances of the same player, to pre-arrange a cooperative agreement.)

You will implement a player to play this game. Your players will be expected to choose a move within an interactive timeframe, say 1 second. At the end of the project we'll run a tournament to see which players achieve the best average score over many games.

Some initial things to think about:

• This is not a zero sum game. (Why not?) How does that affect strategy?
• A player's moves never increase his score, and can sometimes reduce it. A player therefore has to hope that other players move in a way that increases his score. How might a player encourage other players to help him?
• Do the positions of the opposing players strongly influence how a player should interact with them?