Two Players Games in AI

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 take turn and try respectively to maximize and minimize a utility function.

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