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
