General Game Playing
General
Artificial
Intelligence

Assignment 4

The main focus of this week's assignment to the implementation of players that can select moves without searching the entire game tree. In the first part of the assignment, your job is to implement some evaluation functions for states encountered during tree search, Your job in the second part of the assignment is to implement various players that can use these functions to select moves without searching the entire game tree. There is nothing to submit for parts 1 - 3. After each match in parts 4 - 6 is complete, take a snapshot of the screen and submit on Gradescope.

  1. Implement a pessimistic evaluation function, i.e. one that returns the actual reward on terminal states and returns 0 for all other states. (Very easy.)

  2. Implement a mobility function. For states, when your player is in control, the function should return a high score for states in which your player has many moves and a low score for states in which it has few moves. For states in which you player is not in control, it should return a high score for states in which the player in control has few moves and a low score for states in which it has few moves. (Easy.)

  3. Implement an intermediate reward function, i.e. one that returns the actual reward associated with that state, whether or not it is terminal. (Very easy.)

  4. Implement a bounded-depth minimax player, i.e. one that explores the game tree to a fixed depth and uses estimated rewards for states at the fringe of the tree. Once your player is ready to go, choose one of the evaluation functions implemented above and click on the links below to test your player.

  5. Hamilton
    Hunter
    Alquerque
    Connect Four
    Skirmish

  6. Implement an iterative deepening minimax player, i.e. a bounded-depth minimax player that searches the game tree to depth 1, then searches again to depth 2, then depth 3, and so forth until a fixed number of node is expanded or until time runs out. Once your player is ready to go, choose one of the evaluation functions implemented above and click on the links below to test your player.

  7. Hamilton
    Hunter
    Alquerque
    Connect Four
    Skirmish

  8. Implement a greedy minimax player, i.e. a minimax player that expands the tree one node at a time, at each point selecting the node that optimizes your preferred combination of exploitation and exploration scores, continuing until a predetermined number of expansions is reached of until time runs out. Once your player is ready to go, choose one of the evaluation functions implemented above and click on the links below to test your player. (Hint: use your intermediate reward function.)

  9. Hamilton
    Hunter
    Alquerque
    Connect Four
    Skirmish

Bring your computer to class and be prepared to demonstrate your preferred player in a short competition. Games will be similar to the ones above but will not be announced until the start of the class. So be sure not to build in any details about the specific games above.