ECE 461 – Software Engineering
February 1 & 3 Sessions
Basic Game Theory and AI Search
“Game theory is to games of strategy what probability theory is to games of chance.”
– Two-Person Game Theory
, Anatol Rapoport, 1966
Formal Definition of a Game
A game has at least two players.
Example: Solitaire is not considered a game by game theory.
An instance of a game begins with a player choosing from a set of specified (by the game rules) alternatives. This
choice is called a move.
After the first move is made, the new situation determines which player is to make the next move and the
alternatives available to that player.
Example: In many two-player board games, the player making the next move is simply the other player.
Example: In many multi-player card games, the player making the next move depends on who dealt, who
took the last trick, won the last hand, etc.
The moves made by a player may or may not become known to the other players. Games in which all the moves
of all players are known to everyone are called games of perfect information.
Example: Most board games are games of perfect information.
Example: Most card games are not games of perfect information.
Every instance of the game must end.
When an instance of a game ends, each player receives a payoff. A payoff is a value associated with each player's
final situation. A zero-sum game is one in which the elements of the payoff matrix sum to zero.
Example: In chess, win = 1 point, draw = ½ point, loss = 0 points.
Example: In a typical zero-sum game, win = 1 point, draw = 0 points, loss = -1 points.
Introduction to Evaluation Functions
Nine Men's Morris is a game of perfect information, but a player does not know, in general, what move their
opponent will make in response to their move; there are few situations where only one move is possible. Thus, a
player must consider several possible futures. An AI player uses a tree data structure to examine the future. The
vertices of the tree represent board positions, with