General Game Playing
Assignment 3
General
Artificial
Intelligence

Lessons Notes Videos Readings Resources Arena

This week, you should read Chapter 7 in the Notes. The main challenge of the week is to restructure your player so that it can select moves without searching the entire game tree. Once this is done, it will be easy to implement these basic techniques and the more interesting techniques to follow.

  1. Implement a depth-limited minimax player. For now, use an evaluation function that returns actual rewards on terminal states and returns 0 for all other states. Once your player is ready to go, click on the links below to test it out. Try running your player with different depth limits. Find the maximum depth that allows it to play each game without timing out.

  2. Hunter
    Kono

  3. Implement a node-limited minimax player. For now, use an evaluation function that returns actual rewards on terminal states and returns 0 for all other states. Once your player is ready to go, click on the links below to test it out. Try running your player with different node limits. Find the maximum number of nodes it can explore and still play each game without timing out.

  4. Hunter
    Kono

  5. Implement a time-limited minimax player. For now, use an evaluation function that returns actual rewards on terminal states and returns 0 for all other states. Once your player is ready to go, click on the links below to test it out. Make sure you leave enough of a pad that it never times out. For each of the games, record how many nodes it explores before terminating its search.

  6. Hunter
    Kono

  7. Implement a time-limited minimax player with a mobility heuristic. Given a game that is not able to search completely, your player should favor moves that leave it with the most options.) There are multiple ways this can be done, e.g. one step mobility, n-step mobility, number of reachable states, number of legal actions. You may pick whichever of these you like. Alternatively, implement a focus heuristic. (Given a game that is not able to search completely, your player should favor moves that leave it with the fewest options. Once your player is ready to go, click on the links below to test it out.

  8. Hunter
    Kono
    Connect Four

  9. Implement a time-limited minimax player with a reward heuristic. Your player should favor intermediate states that have higher rewards to those with lower rewards even if those states are not terminal. Once your player is ready to go, click on the links below to test it out.

  10. Hunter
    Kono
    Connect Four

  11. Implement a time-limited minimax player with a keep alive heuristic. As with the reward heuristic, your player should favor intermediate states that have higher rewards to those with lower rewards even if those states are not terminal. However, where rewards are the same and not 100, your player should favor non-terminal states to terminal states (so that it can keep on playing and possibly increase the minimal reward). Hint: Instead of computing a single value for each node in the game tree, compute an interval of minimum score and maximum score (under the assumption that the opponent is trying to minimize your score). Once your player is ready to go, click on the links below to test it out.

  12. Hunter
    Kono
    Connect Four

  13. Create instances of your time-limited minimax player with different heuristics and run them against each other. Is there one that is best for all games or do some work better on one game while others work better on another? If you had to choose just one, which would you choose? You can use the links below to start the games above plus a couple of additional games.

  14. Hunter
    Kono
    Connect Four
    Checkers on a Barrel No Kings
    Nine Board Tic Tac Toe


Comments and complaints to genesereth@stanford.edu.