6.1 Games

• A type of search that can be use to playing a game!!
  • Computer play a game with human, we want a computer to win a game
• Games or adversarial search problems focus on handling a multi-agent competitive environment.
• ต่างจาก Search อื่นยังไงก็คือมันเป็น Multi-agent — Human + Computer ไงงง
• Limit to the type of games with following characteristics:
  • Fully observable, and Deterministic (no random) environment
  • Turn-taking: each player selects an action, after which the turn passes to the other player.
  • Two-player: human vs. computer
  • Zero-sum: Win = +1 and Lose = -1
    • Sum the utility of which player receive is zero; called Zero-sum นั่นเอง
• Examples of games with the above properties include Tic-Tac-Toe, Chess, Go, etc.
• Searching to win the game is different from the general search because of the unpredictable opponent, and time constraints.
  • Search แบบนี้มี Unpredictable เพราะมีคนไงล่ะ…

6.2 Game as a Search Problem

• $S_0$: Initial state
• Player(s): define which player has the move in a state
• Actions(s): legal moves available in state s
• Result(s, a): the resulting state after applying action a in state s
• Terminal-Test(s): returns true when the game is over, and false otherwise
• Utility(s, p): final numeric value for a game ending in state s for player p

Game Tree

คล้าย ๆ Search Tree ตรงที่ Nodes = states; edges = actions แต่ต่างกันตรงที่เรามี Max (maximize score) vs. Min (minimize score)

• Purpose: Represents all possible move sequences in a multi-agent, adversarial game
• Structure:
  • Nodes = game states
  • Edges = legal actions
    • Players: $Max$ (maximize score) vs. $Min$ (minimize score) alternate turns
    • Components:
      • Root = initial state
      • Terminal nodes = game over with utility values (win/lose/draw) = leaf nodes
• Usage: Used in Minimax and Alpha-Beta Pruning to find optimal strategies
• Challenge: Size grows exponentially with depth → use heuristics and depth limits

Example 6.1 - Tic-Tac-Toe Game Tree

• Initial node จะเป็นของ Max player เสมอ

6.3 Optimal Decisions in Games

Optimal Decisions = the move that maximize the utility value!

• Goal: Choose the best move assuming both players act rationally
• MAX player: Tries to maximize the utility value
• MIN player: Tries to minimize the utility value
• Algorithm logic:
  • Base case: If s is terminal → return Utility(s)
  • Recursive case:
    • If Player(s) = MAX → choose action with maximum value
    • If Player(s) = MIN → choose action with minimum value
• Advantage: Explores the entire game tree to guarantee optimality
• Drawback: Exponential time complexity in tree depth

6.3.1 Minimax Function

The minimax function is a recursive function that computes the minimax value of a game state. It evaluates the utility of terminal states and propagates these values back up the tree to determine the best move for the current player.

• Search method: Depth-first search is used to explore the game tree and compute the minimax values
• Decision: The best move is the one that maximizes the utility value for the current player

Example 6.2

• เข้าใจ Notation ก่อน
  
• Green arrow → The best move!
  

The Minimax Algorithm

• Process: Before making a decision, the minimax algorithm is applied to compute the minimax value from the current state
• Implementation: The algorithm recursively computes the minimax values of each successor state
• Similarity: This is similar to conducting a depth-first or depth-limited search

Example 6.3 - Two-Player Number Game

N = 0 นะ อันที่สอง อาจารย์เขียนผิดเลยล่ะ

Practical Considerations

• Problem: In previous examples, the search goes deep until a terminal state is found. This is not practical
• Real-world challenge: A game tree in real-world games like Chess contains a huge number of branches and is very deep. It would take too long to reach all the terminal states
• Solution: In practice, the search is limited to a particular depth, and a heuristic function is applied to estimate the utility values of nodes at that depth

6.4 Alpha-Beta Pruning

• Purpose: Minimax search has a drawback that the number of states it has to examine is huge, and exponential in the depth of the game tree
• Goal: A technique called "alpha-beta pruning" aims to correctly explore the game tree without looking at every node

Algorithm Parameters

The algorithm maintains two values, $\alpha$ and $\beta$ at each node:

• $\alpha$ (alpha):
  • The best value that the maximizer currently can guarantee at that level or above
  • It is the lower bound of the minimax value of a node
  • Initial value of $\alpha$ of the root node is $-\infty$
  • Initial value of $\alpha$ of other nodes is inherited from its parent node
• $\beta$ (beta):
  • The best value that the minimizer currently can guarantee at that level or above
  • It is the upper bound of the minimax value of a node
  • Initial value of $\beta$ of the root node is $+\infty$
  • Initial value of $\beta$ of other nodes is inherited from its parent node

Pruning Condition

• Rule: Whenever $\alpha\ge\beta$, the player does not need to explore the remaining descendants of the current node
  • Lower bound is higher than upper bound!!!

6.5 Deep Blue

• Overview: Deep Blue is a chess-playing computer developed by IBM
• Historical achievement: It was the first computer system to defeat a reigning world chess champion, Garry Kasparov, in a match under standard chess tournament time controls in 1997
• Algorithm: It implements the minimax algorithm with alpha-beta pruning to efficiently search the game tree
• Hardware: It uses custom hardware and parallel processing to evaluate 200 million positions per second
• Evaluation: It uses an evaluation function to assess the desirability of a position based on various factors, such as:
  • Material balance
  • Piece activity
  • King safety