Definitions

This section serves to clarify some of the terms related to game theory that are useful to understand. When appropriate, examples from the games Tic-Tac-Toe and "1,2,...,4" will be supplied to illustrate the terms. "1,2,...,4" is the same as "1,2,...,10" except the goal is to get the game to 4 instead of 10 first.

Position

Another word for this is a "board configuration" - it is a snapshot of the board with pieces on it and a turn designation. Every game has positions, regardless of whether or not it is played on a physical board. Figure 1 shows a sample position for Tic-Tac-Toe. Note that the outcome of the game would be quite different if it were O's turn. When we are encoding the position in scheme, we need to store the player whose turn it is also. In the diagram below, it is X's turn.

Figure 1: A Tic-Tac-Toe position

Slot

A slot is a coordinate on a board, which in the 2-D case would be an (X, Y) pair. A board, for some games, is a 2-D collection of slots. Keep in mind that abstract games such as "1,2,...4" do not have clear definitions of slots. In the game Tic-Tac-Toe, there are 9 slots, numbered in Figure 2.

Figure 2: The 9 Tic-Tac-Toe slots

Move

Moves are the action a player performs on his/her turn to change the board's configuration. In Tic-Tac-Toe, a move is the action of placing an X or O on an empty slot. Most games' rules dictate that the available moves are a function of position; in the game "1,2,...,10", however, there are exactly two possible moves for every position (except when the position's board = 9), 1 and 2. Most games dictate that the players alternate turns every other move.

Value or Outcome

Figure 3: A branch in a Tic-Tac-Toe game-tree

We have simplified the meaning of the value of a game from that usually discussed in combinatorial game theory circles. Every position has a value, which we will consider to be one of { Win, Lose or Tie } for the player whose turn it is to move. This can also be thought as the outcome of the game if played by perfect opponents. This means that if the game was played between perfect opponents, the player whose turn it was would always either win, lose or tie. Any move that leads to a winning position for the other player is a losing move, and consequently any move that leads to a losing position for the other player is a winning move. A tie move is one that leads to a tie position for the other player. If the first, or initial position in a game has value V, then the game is said to have value V. For example, if Tic-Tac-Toe began with position A in Figure 3 rather than a blank board, then Tic-Tac-Toe would be a winning game, since A is a winning position.

Figure 3 contains a very detailed Tic-Tac-Toe game tree to help us understand these terms. Note that under every position is a string that represents the position letter, whose turn it is and what the value of that position is. For example, the root position contains "A - X - Win", which means that it is position A, X's turn and a win for X. The arrows have a number and a letter beside them that represent which slot was chosen and what the value of that move was. For example, the upper-left-most arrow contains "7 - Win", which means that player X chose slot 7, and it was a winning move for player X.

Win

In some references this is called an "N" position, which means the Next player can win. This value is recursively defined by the following rule: A winning position is one in which there exists a losing child. This is best illustrated by position A in Figure 3, which has a winning (D), losing (B), and tieing (C) child, and is considered a winning position due to the existence of B. The move that leads to the losing child, slot 7, is the winning move. The following positions are all winning in the above game-tree: A, D and E.

Just because a player has a winning position doesn't necessarily mean the player will win, simply that the player can win. In position A above, a winning position, if X chooses the lone losing move to slot 9, X can lose. Sometimes a win is inevitable, since all the children are losing positions, and in these rare cases a winning position indicates that the player will win. Position E has one lone slot for X to choose which forces the win. X has no option but to choose slot 7 and win the game. It is important to remember that a winning position in general means that the potential for winning against a perfect opponent exists.

Lose

Similar to a winning position, a losing position is often called "P", which means the Previous player can win. Said another way, it means that the player whose turn it is will lose against a perfect opponent. This value is also recursively defined, but by a different rule: A losing position is one in which there does NOT exist a losing or tieing child. This means that the children of losing positions are either all winning or it is primitive (and has no children). The losing positions from Figure 3 (B, I and N) fulfill the latter case and are all primitive losing positions. We will describe primitive positions in a moment.

If a player has a losing position and is playing against a perfect opponent, the player has already lost the game and might as well concede. This is because a perfect opponent will continue to make winning moves until either it has reached a primitive winning position or the other player is left with a primitive losing position. However, if the opponent is imperfect, then a non-primitive losing position does not guarantee a loss, just the potential for losing.

Tie

A tie position is recursively defined as: A tying position is one in which there does not exist a losing child, but there does exist a tie child. Whether or not there are any winning children is irrelevant, as it does not affect the value. Position C in Figure 3 above is a perfect example of a tying position, since it has no losing child but doeshave a tie child, which is position F. A player with a tie position can either tie or lose against a perfect opponent. Against an imperfect opponent, it is possible to either tie, lose or win. Positions C, F, G and J are tie positions, yet only J is a primitive tie. As mentioned before, a tie move is one that leads to a tie position. If there are no tying terminating criteria (see below), there can never be a primitive tie position, and by induction, no non-primitive tie positions.

Draw

A draw position is defined as: A draw position is one in which there is no way to force a win or be forced to lose. This is often present for loopy games, or games in which it is possible to repeat a position we've been to before. It means that the best strategy is to keep the game going forever, because there's no clear strategy for winning and if we don't follow this advice, the opponent may just beat us. Tic-tac-toe is not a loopy game (it ends in at most 9 moves when all the slots are filled) and none of the games chosen this year are loopy. In general, you don't need to worry about these positions when writing your code; Gamesman internals will handle when a repeat position has been seen and do the right thing.

Primitive Positions and Terminating Criteria

Primitive positions are the leaves in the game tree and are the positions that fulfill the terminating criteria for the game. These criteria are what prevent the game from being infinite, as they force the game to end at some point. In Tic-Tac-Toe, there are two terminating criteria. The first is that the other player has just achieved three-in-a-row of his/her piece, which means that the position is a losing primitive position. The second is that a position has all 9 slots filled, in which case it is a tying primitive position. Note that for most games the order that these are checked is crucial, as position I fulfills both, and would be incorrectly labeled a tying position if the rules were reversed. Positions that are not primitive are either called non-primitive or recursively-defined, due to the definitions highlighted above. In Figure 3, the primitive positions are B, I, J and H.

Safe or Value Equivalent Moves

Safe moves are moves that lead to children of equal value as the original position. E.g., all winning moves from a winning position are safe. All tying moves from a tie position are safe. Lastly, all losing moves from a losing position are safe (and futile!). All five moves available to X (slots 2, 4, 5, 7 and 8 in Figure 4) are winning since all five lead to losing positions. These moves are safe and any may be chosen without risk to the outcome. This is true even though 2 leads to an immediate primitive losing position (for O) and 4, 5, 7 and 8 lead to non-primitive losing positions (for O).

Figure 4: A winning Tic-Tac-Toe position with three safe winning moves 2, 4, 5, 7 & 8

Perfect Opponents

Perfect opponents are opponents who always choose winning moves given winning positions and always choose tying moves given tying positions. It doesn't matter what perfect opponents choose given losing positions, since if they are primitive there are no moves available and the game is over (and if they are non-primitive all moves are value-equivalent "safe" losing ones). It is tempting to define perfect opponents as computers and imperfect opponents as humans, but that would incorrectly label bad programs and very knowledgeable humans. Gamesman, once it solves the game tree, plays perfectly. We may add a feature that would allow the user to change Gamesman so that it loses once in a while.

The Misère Game vs. The Standard Game

Every game has terminating criteria that constitute the rules of the game. These are called, for convenience, the standard rules, and must include winning or losing conditions. Every single game has a misère game, which is the game with the words "losing" and "winning" swapped into the terminating criteria for the standard game. For example, whereas the standard game in Tic-Tac-Toe can be explained as: "A player wins if he/she achieves three-in-a-row first", the misère game is explained as: "A player loses if he/she achieves three-in-a-row first".

Interestingly enough, sometimes perfect strategies for the standard game and the misère game differ by only the primitive positions and perhaps a few others. Conversely, some games have completely different strategies for the two games. Everyone must implement both standard and misère rules for the game they choose.

Gamesman ©2003 Dan Garcia. All rights reserved. Site design by Steven Chan. Site maintained by Hesam Samimi.