Back to Study Material Artificial Intelligence

Game playing in AI

Game playing in AI presents a special challenge because the environment includes an adversary who is actively trying to defeat the agent. Unlike standard s...

Game playing in AI

Adversarial Search

Game playing in AI presents a special challenge because the environment includes an adversary who is actively trying to defeat the agent. Unlike standard search problems where the agent controls all actions, a two-player zero-sum game, one where one player's gain is exactly the other's loss, requires the agent to plan not just its own moves but also to anticipate and counter every possible response from the opponent.

The game tree is the primary data structure for adversarial search. The root node represents the current game state. Its children represent all states reachable after each legal move by the first player, called MAX because they want to maximise the outcome. Their children represent states reachable after each response by the second player, called MIN because they want to minimise the outcome. The tree alternates between MAX and MIN levels until terminal states, where the game ends, are reached. Terminal states are assigned utility values: positive for MAX wins, negative for MIN wins, zero for draws in a symmetric game.

AI has achieved superhuman game-playing performance across multiple domains. IBM's Deep Blue defeated world chess champion Garry Kasparov in 1997. DeepMind's AlphaGo defeated world Go champion Lee Sedol in 2016 using deep neural networks to evaluate positions and Monte Carlo tree search to navigate the enormous branching factor of Go. AlphaZero subsequently mastered chess, shogi, and Go from scratch using only self-play reinforcement learning.

Evaluation Functions

Because game trees are too large to search to terminal states in practice, agents apply evaluation functions to non-terminal nodes to estimate the value of positions. A chess evaluation function might consider material balance, king safety, pawn structure, and piece mobility, weighting each factor based on experience and analysis.

Interview Tip

Interviews on game playing almost always cover the minimax algorithm and alpha-beta pruning together. Be prepared to explain why alpha-beta pruning does not change the outcome of minimax but reduces the effective branching factor from b to approximately the square root of b under ideal move ordering, which roughly doubles the search depth achievable in the same time.