# New Technology

Trending Technology Machine Learning, Artificial Intelligent, Block Chain, IoT, DevOps, Data Science

## Wednesday, 10 April 2019

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

• 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.)