Mini Project: Adversarial Search or Playing Games with Python
Game name: Tic Tac Toe (Using: The Minimax Algorithm)
Adversarial Search
- Examine the problems that arise when we try to plan ahead in a world where other agents are planning against us.
- A good example is in board games.
- Adversarial games, while much studied in AI, are a small part of game theory in economics.
Typical AI assumptions
- Two agents whose actions alternate
- Utility values for each agent are the opposite of the
other - creates the adversarial situation
- Fully observable environments
- In game theory terms: Zero-sum games of perfect
information. - We’ll relax these assumptions later.
Search versus Games
- Search – no adversary
- Solution is (heuristic) method for finding goal
- Heuristic techniques can find optimal solution
- Evaluation function: estimate of cost from start to goal through given node
- Examples: path planning, scheduling activities
- Games – adversary
- Solution is strategy (strategy specifies move for every possible opponent
reply). - Optimality depends on opponent. Why?
- Time limits force an approximate solution
- Evaluation function: evaluate “goodness” of game position
- Examples: chess, checkers, Othello, backgammon
Types of Games
Game Setup
1. Two players: MAX and MIN
2. MAX moves first and they take turns until the game is over
- Winner gets award, loser gets penalty.
3. Games as search:
- Initial state: e.g. board configuration of chess
- Successor function: list of (move, state) pairs specifying legal moves.
- Terminal test: Is the game finished?
- Utility function: Gives numerical value of terminal states. E.g. win (+1), lose
(-1) and draw (0) in tic-tac-toe or chess
4. MAX uses search tree to determine next move.
Size of search trees
- b = branching factor
- d = number of moves by both players
- Search tree is O(bd)
Chess
- b ~ 35
- D ~100
- – search tree is ~ 10 154 (!!)
- – completely impractical to search this
Game-playing emphasizes being able to make optimal decisions in a finite amount of time
- Somewhat realistic as a model of a real-world agent
- Even if games themselves are artificial
Partial Game Tree for Tic-Tac-Toe