Artificial Intelligence (BSc CSIT, CSC261): the questions likely to come

Adversarial Search

Adversarial search deals with problems in which two or more agents have conflicting goals — the gain of one is the loss of another (zero-sum games such as Chess, Tic-Tac-Toe, Checkers). The agent must plan against an opponent who also plays optimally. The search space is modelled as a game tree where levels alternate between the player (MAX) and the opponent (MIN).

Minimax Algorithm

Minimax computes the optimal move assuming both players play optimally:

• MAX nodes choose the child with the maximum value.
• MIN nodes choose the child with the minimum value.
• Terminal/leaf nodes are scored by a utility/evaluation function.

function MINIMAX(node, isMax):
    if node is terminal: return utility(node)
    if isMax:
        best = -infinity
        for child in node: best = max(best, MINIMAX(child, false))
        return best
    else:
        best = +infinity
        for child in node: best = min(best, MINIMAX(child, true))
        return best

It is a depth-first exploration with time complexity $O(b^m)$ and space $O(bm)$, where $b$ = branching factor, $m$ = depth.

Alpha-Beta Pruning

Alpha-Beta pruning improves Minimax by eliminating branches that cannot affect the final decision, without changing the result.

• $\alpha$ = best (highest) value MAX can guarantee so far.
• $\beta$ = best (lowest) value MIN can guarantee so far.
• Prune (stop exploring) a node whenever $\alpha \ge \beta$.

With optimal move ordering it reduces complexity to $O(b^{m/2})$, effectively doubling the searchable depth.

Example Game Tree

                MAX
              /     \
           MIN       MIN
          /  \       /  \
         3    5     6    9
        (A)  (B)   (C)  (D)

• Left MIN node = min(3,5) = 3.
• For the right MIN node, after seeing 6 we know it will be ≤ 6. Since MAX already has 3 ($\alpha=3$) and 6 > 3, MAX may still prefer this branch, so we examine 9 → min(6,9) = 6.
• Root MAX = max(3, 6) = 6.

If instead the right subtree began with a value ≤ 3 (say 1), then once that leaf is seen $\beta=1 \le \alpha=3$, the remaining siblings of that node are pruned, because MAX would never choose this branch.