• Unit 8: Game-Playing Models

    Games have become an important component of AI and are a global industry. This unit shows you how to analyze the game state and represent it in a way that fosters interesting algorithms. We will look at a range of algorithms and give an overview of how games can be modeled in AI applications.

    Completing this unit should take you approximately 4 hours.

    • Upon successful completion of this unit, you will be able to:

      • describe how to model a two-person adversarial game;
      • detail the workings of the minimax algorithm to determine player moves;
      • detail how to improve the performance of the minimax algorithm using alpha-beta pruning; and
      • describe the basics of multi-person game models.

    • 8.1: Game Trees and the Minimax Algorithm

      The simplest game model is that two adversaries are matched against each other. The state of the game can be represented as a game tree that describes all the possible moves of both players in turn. The minimax algorithm is a simple way to illustrate how two players (min and max) take turns to play the game based on expected outcomes. The minimax algorithm computes a player's next rational move, assuming perfect play by the opponent.

    • 8.2: Game-Playing Strategies

      Now, we will look at optimizing the minimax algorithm using alpha-beta pruning. Because the game model only allows perfectly rational play by both players, players will only take the paths that can improve their score. Alpha-beta pruning is applied at every stage to avoid exploring parts of the tree that are irrelevant to making the best move. We will also see models for multiple-person games, including elements of game theory and other concepts. Multi-party games are far more complex to model.