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):

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