Search for games in AI

There are following Search for games in AI used

Game Problem Formulation

  • A game with 2 players (MAX and MIN, MAX moves first, turn-taking) can be defined as a search problem with:
    • initial state: board position
    • player: player to move
    • successor function: a list of legal (move, state) pairs
    • goal test: whether the game is over – terminal states
    • utility function: gives a numeric value for the terminal states (win, loss, draw)
  • Game tree = initial state + legal moves

Optimal Strategies

  • MAX must find a contingent strategy, specifying MAX’s move in:
    • the initial state
    • the states resulting from every possible response by MIN
  • E.g., 2-ply game (the tree is one move deep, consisting of two half moves, each of which is called a ply):
Optimal Strategies
Optimal Strategies

Minimax Value

  • Perfect play for deterministic game, assume both players play optimally
  • Idea: choose move to position with highest minimax value = best achievable payoff against best play

A Partial Game Tree for Tic-Tac-Toe

A Partial Game Tree for Tic-Tac-Toe
A Partial Game Tree for Tic-Tac-Toe

Leave a Comment