On this page:
1 Implement a Game Tree
2 Use the game tree for the administrator
3 Use the game tree for the players
6.0.0.1

Project 10: 11/3

This project is due on 11/3 at midnight.

1 Implement a Game Tree

Design and implement a game tree module for Acquire. The module should come with two interfaces:

At a minimum, your game tree module must support one constructor:

generate : InternalState -> Tree

The given InternalState may describe the state after setting up the players with their initial tiles or an intermediate state after the game administrator has removed some unruly player. From the given state, generate creates a tree that describes all possible actions that the administrator and the players can take. A complete turn contains branches for all possible tiles a player can place, all possible hotels that could be involved, all possible combinations of shares to be bought, and finally all possible tiles that the administrator can hand over to the player. The result of these steps is a subtree, whose top-tier InternalState describes the result of these actions plus the rotation of the players.

The construction of an Acquire game tree is an algorithmic problem. An initial tree is a quite "bushy" tree. If three players participate, the first layer of share distribution has up to 3 out of 175 possibilities (which is 893,376), the second one 3 out of 174 (878,150), and so on. If you consider all possible cross-products, you get some 784,518,134,400 possibilities on the first two levels alone.

2 Use the game tree for the administrator

Change the game administrator so that it uses the game tree module to control the game. After setting up the players with tiles, the administrator generates a game tree. Once a player specifies the actions it wishes to perform for its turn, the administrator calls a function/method on the game tree to navigate to the appropriate subtree. In case navigation fails, the player cheated, and you should issue an appropriate error. The game ends if the internal state at the root of the tree is a final state.

3 Use the game tree for the players

Change your player and strategy implementations so that they make use of the game tree. When they go to select a move, the should select it out of the moves available in the game tree. For example, the random strategy will pick a random element of the first level of the tree.