Games as Search Problems

Last updated Nov 8, 2022 Edit Source

Perfect information also means fully observable unlike in Poker where you cannot see the opponent’s hand.

Maximize own utility and minimize opponent’s

1. Generate game tree to terminal state or a certain depth
2. Calculate the utility from the bottom-up (MAX turn will maximize own utility, MIN turn will minimize MAX utility)
3. Select the best move (we can assume that we start as MAX)

Tic-Tac-Toe Tree Example:

Reflective and rotational symmetries: