Difference between revisions of "Game theory"

Revision as of 20:32, 12 February 2010

Game theory is the formal study of mathematical games. The ultimate goal of game theory is usually to solve a game; that is, to determine the nature of an optimal strategy for each player, and the outcome of such a strategy. Often, solving a game entails lengthy calculations, necessitating the use of a computer. However, brute force computational power is usually insufficient and clever mathematical reasoning is needed to invent efficient algorithms. Thus, game theory lies at a crossroads between mathematics and computer science.

Basic concepts

The terms game, player, objective, and move denote axiomatic concepts in game theory and we will not attempt to define them here.

State

The state, position, or configuration of a game, loosely put, consists of exactly that information which determines the valid moves that can be made in the future and is itself modified when moves take place. In a deterministic game (see below), the state, taken together with the players' strategies, is sufficient and necessary to determine the game's outcome. In a nondeterministic game, the same combination is sufficient and necessary to determine the probabilities of the possible outcomes of the game.

Determinism

A deterministic game is one in which the decisions of the players, reflected in the moves they make, are sufficient to determine the game's outcome. The opposite is an indeterministic game. More simply, "games of chance" are nondeterministic, whereas pure strategy games with no element of chance are deterministic. Chess, for example, is a deterministic game, whereas backgammon is not. Deterministic games are of greater mathematical interest than nondeterministic games, but both can be studied with the aid of a computer.

Availability of information

When all players know the entire state of a game at any given time, the game is said to be perfect information. Perfect information games include chess, Go, and tic-tac-toe. Most games of interest in mathematics and computer science are perfect information games. Imperfect information games include most card games, as each player usually hides cards from opponents.

=Partiality

An impartial game is one which satisfies two conditions:

1. The valid moves from a given position depend only upon the position itself and not upon which player is to move next.
2. The outcome of the game is symmetric with respect to the players.

Most games fail the first condition. Chess, for example, fails the first, since we must know if the player moving next is player 1 or player 2 to determine whether that player is to move a white piece or a black piece. Games failing the second condition are much rarer in serious mathematical study. Nim is a archetype for the impartial game; pieces are shared between the two players and each has the same goal.