Game Playing

Artificial Intelligence - A Modern Approach (AIMA): Chapter 5.1-5.2

Overview

1. Aversarial Search
2. Minimax Algorithm.
3. Alpha-Beta Pruning
4. Evaluation Functions
5. Isolation Game Player
6. Multi-Player Probabilistic Games.

Challenge Question Introduction

Isolation

• http://www.cs.columbia.edu/~sal/notes/assign3-isolation-game.htm
• https://github.com/SashaZd/GaTech-AI-Isolation

Building a Game Tree

Which are valid moves for O

Building a Game Tree

How Do We Tell The Computer Not To Lose?

• Full Isolation Game Board

MIN and MAX Levels

• Top of MIN-MAX Tree is always going to be a Max Level.

Propagating Values Up The Tree

Computing MIN MAX Values

Choosing the Best Branch

• Computer Player has to choose any of the best branches and it will win.

Max Number Of Nodes Visited

Max Moves

The Branching Factor

Number of Nodes In a Game Tree

• Here ‘b’ is the average branching factor and ‘d’ is the depth of the game tree.

Depth-Limited Search

Evaluation Function Intro

• Maximize the number of the moves left.

Testing The Evaluation Function

Testing The Evaluation Function Part 2

• Isolation Game Tree - Level 3

Testing Evaluation Functions

• Isolation Game Tree - Level 2

Quiescent Search

Iterative Deeping

• University of British Columbia’s slides introducing the topic.
• 3.4.5 of Russel, Norvig
• Visually how Iterative Deepening is different from DFS

Understanding Exponential Time

Exponential B=3

Horizon Effect

Quiz: Good Evaluation Functions

Evaluating Evaluation Functions

Alpha-Beta Pruning

Minimax Quiz

Alpha Beta Pruning Quiz 1

Alpha-Beta Pruning Quiz 2

Searching Complex Games

• AIMA: Chapter 5.3-5.4

3-Player Games

3-Player Games Quiz

3-Player Alpha-Beta Pruning

Multi-player Alpha-Beta Pruning

• Korf 1991

In the above paper, you will get a chance to generalize minimax search techniques to games with more than three players. As you’ll see, alpha-beta pruning doesn’t work quite as effectively in this case as in the general case. Here are a few questions to keep in mind while reading through this paper:

• Why might alphabeta pruning only work well in the two player case?
• How does the size of the search tree change with more than two players?

Probabilistic Games

Probabilistic Alpha-Beta Pruning

Further Watching

• Game Playing
• Game Theory

Resources

• • https://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html