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

Recent Post

Codecademy Code Foundations

Search This Blog

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 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)
    if N is a leaf then
         return the estimated score of this leaf
       Let N1, N2, ...,  Nm  be the successors of N;
       if N is a Min node then
            return min{MINIMAX(N1), ..., MINIMAX(Nm)}
           return max{MINIMAX(N1),...,  MINIMAX(Nm)

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

Popular Articles