In any field of science, we like to clearly define concepts in a formal way. In the field of artificial intelligence, when one talks about game theory, one begins with the definition of a game tree. A Game-tree is a rooted tree whose vertices are valid board positions and whose edges are valid moves. The root of a game-tree is the empty or initial board position and is the board position which always begins a game. The leaf vertices of a game-tree are terminal board positions and are the board positions where one of the players is the winner or the game has ended in a draw.
An edge in any graph is a relation (x,y) where x and y are elements of the vertices. In a game tree the vertices is the set of all valid board positions. An edge in a game-tree is called a move because the second member of a move is the board position that follows the first member after a player makes a valid move. Figure 3 gives an overview of the game-tree for the popular children's game of Tic-Tac-Toe.
Fig 3. The first three levels of the game tree for Tic-Tac-Toe. Each level shows the player who has a turn to move.
A game-tree is a graph and graphs involve concepts that need proper definitions. Firstly, two vertices are adjacent if there exists an edges between them and two edges are adjacent if they have a vertex in common. a walk is a sequence of vertices and edges such that the vertices and edges are adjacent. A path is a walk where the vertices are distinct and a closed path is called a circuit. Given a vertex v, every other vertex adjacent to v is a child of v and vertices in a set of child vertices are called children. Any two vertices in a set of child vertices have a sibling relationship. In a game-tree, a Game is a single non-circuit path from the initial board position to a terminal board position.
The field of artificial intelligence often involves the study of search algorithms. Search algorithms perform traversals of graphs and they fall into two main types. The first type of search algorithm is called a depth-first search. A depth-first search visits vertices in a child relationship first but may visit vertices in a sibling relationship when children are exhausted. The second type of search algorithm is called a breadth-first search. A breadth-first search visits vertices in a sibling relationship first but may visit vertices in a child relationship when siblings are exhausted.
The most famous game-tree search is called a min-max search. In a min-max search the players are categorized as player Min and player Max, respectively. A min-max search involves a value function f(x) where x is a terminal board position. The value function f(x) is a measure of the winner. For example, If Min is the winner at terminal board position x then f(x) = 1 and if Max is the winner then f(x) = -1 (in the case of a draw f(x) can return zero ). A min-max search is a depth first search of a game-tree. When the min-max search reaches any terminal board position x, it returns the value given by function f(x). At any non-terminal board position v where player Min has a turn, the min-max search returns the minimum of values found at the children of v. At any non-terminal board position v where player Max has a turn, the min-max search returns the maximum of values found at the child positions of v. A game theoretic of a board position is the value a min-max search returns for that board position.
(Under construction and more to come )
Last Modified: 20/01/2008