Minimax is a game-search algorithm for choosing a move when two players compete. It builds a tree of possible future states, assumes the opponent will choose the most harmful response, and selects the move that gives the agent the strongest remaining outcome. section 3.7
A minimax search proceeds by:
- Generating child nodes for each valid move from the current game state. section 3.7
- Searching ahead to a chosen depth, because exploring the entire game tree may exceed memory and computation limits. section 3.7
- Scoring leaf states with a human-crafted heuristic rather than a learned model. section 3.7 section 1.18
- Alternating between maximizing the agent’s score and minimizing the opponent’s advantage while propagating scores upward. section 3.7
A Connect Four decision
A Connect Four position branches into possible moves. Minimax copies the position, plays each candidate move, recursively switches between maximizing and minimizing, and stops when it reaches a win, draw, full board, or depth limit. It then returns the move with the best score for the agent under the opponent’s strongest reply. section 3.7
Figure 3.12 The sequence of tree processing using Minimax search
Use the tree sequence to follow how leaf scores move upward while maximizing and minimizing alternate at successive turns. section 3.7
def minmax(connect, depth, min_or_max, move):
current_score = connect.get_score_for_ai()
current_is_board_full = connect.is_board_full()
if current_score != 0 or #A
current_is_board_full or depth == 0:
return Move(move, current_score)
best_score = INFINITY_NEGATIVE * min_or_max #B
best_max_move = -1
moves = random.sample(range(0, connect.board_size_y + 1),
➥connect.board_size_x) #C
for slot in moves:
neighbor = copy.deepcopy(connect) #D
move_outcome = neighbor.play_move(slot)
if move_outcome:
best = minmax(neighbor, depth - 1,
➥min_or_max * -1, slot) #E
if (min_or_max == MAX and best.value
➥> best_score) or (min_or_max == MIN
➥and best.value < best_score): #F
best_score = best.value
best_max_move = best.move
return Move(best_max_move, best_score) #G
The pseudocode connects the idea to implementation through terminal checks, recursive depth reduction, copied game states, and best-move selection. section 3.7
