**Game Playing**

**Two Players**

The players alternate

Focus on game of perfect information

Zero sum game

**Game Playing as Search**

Initial state is the initial position

Successor function - defines the set of legal moves from any position

terminal test determines when the game is over

Utility function gives a numerical outcome for the game

**Basic Strategy**

- Grow a search tree
- Only one player can move at each turn
- Assume we can assign a payoff to each final position - called a utility.
- We can propagate values backwards from final positions
- Assume the opponent always makes moves worst for us
- Pick best moves on own turn

**2 player games**

- 2 players
- zero sum
- perfect information

The two players are called respectively MAX and MIN. We assume that the MAX player makes the first move

The leaves represent terminal positions

**Game tree**

- Successive nodes represent positions where different players must move. We call the nodes MAX and MIN nodes depending of who is the player that must move at that node.
- A game tree could be infinite.
- The ply of a node is the number of moves needed to reach that node (i.e. arcs from the root of the tree). The ply of a tree is the maximum of the plies of its nodes.

**Brute-Force Search**

We begin considering a purely brute-force approach to game playing.

This will only be feasible for small games , but provides a basis for further discussions.

Example - 5-stone Nim

- played with 2 players and pile of stones.
- Each player removes a stone from the pile.
- player who removes the last stone wins the game.

**Minimax**

- Minimax theorem - Every two-person zero-sum game is a forced win for one player, or a forced draw for either player, in principle these optimal minimax strategies can be computed.
- Performing this algorithm on tic-tac-toe results in the root being labeled a draw.

**Minimax Search**

- The MAX (MIN) player selects the move that leads to the successor node with the highest (lowest) score.
- The scores are computed starting from the leaves of the tree and backing up their scores to their predecessor in accordance with the Minimax strategy.
- it explores each node in the tree.

function MINIMAX(N)

begin

if N is a leaf then

return the estimated score of this leaf

else

Let N1, N2, ..., Nm be the successors of N;

if N is a Min node then

return min{MINIMAX(N1), ..., MINIMAX(Nm)}

else

return max{MINIMAX(N1),..., MINIMAX(Nm)

end

**Game tree for chess**

- Chess has an average branching factor of about 35.
- Games are often about 50 moves for each player
- Size of game tree is about 35100 ~ 10154 nodes.
- (Search graph actually has about 1040 distinct nodes.)

## No comments:

## Post a Comment