The Hotness
Scythe: Digital Edition
Super Mario Galaxy 2
Portal 2
Borderlands 2
Dragon's Crown
Surviving Mars
Mystic Vale
Age of Fear 3: The Legend
Surviving Mars: Green Planet
Master of Orion
Star Wars: Knights of the Old Republic
Super Mario Kart
Lunar: The Silver Star Story Complete
Fallout (1997)
GoldenEye 007
Call of Duty: Finest Hour
City of Heroes
Harvest Moon: A Wonderful Life
Their Finest Hour: The Battle of Britain
Metroid Fusion
Out Run
The Operational Art of War III
Anno 1404
Achtung Spitfire
Strider (NES)
Velvet Assassin
The Shivah
Journey (2012)
Age of Fear: The Undead King
Dragon Age: Inquisition
Twilight Struggle
Hearthstone: Heroes of Warcraft
One Finger Death Punch
Shovel Knight
Mirror's Edge: Catalyst
The Talos Principle
Cities: Skylines
Dark Souls III
Horizon Zero Dawn
NieR: Automata
The Legend of Heroes: Trails of Cold Steel II
The Binding of Isaac: Afterbirth
Enter the Gungeon
Call of Cthulhu: The Official Video Game
Evolution (2019)
The Operational Art of War IV
Search: Titles Only:
Article Edit | History | Editors

Game tree

In game theory, a game tree is a graph whose nodes are positions in a game and whose edges are moves.

Digraph game tree

Pragmatically this representation is a directed graph (digraph). Each turn directs the game from one node in the game tree to another. So the flow between the nodes is directed. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that obtained from the extensive-form game representation.

The first two plies of the game tree for tic-tac-toe.

The diagram shows the first two levels, or plies, in the game tree for tic-tac-toe. The rotations and reflections of positions are equivalent, so the first player has three choices of move: in the center, at the edge, or in the corner. The second player has two choices for the reply if the first player played in the center, otherwise five choices. And so on.

The number of leaf nodes in the complete game tree is the number of possible different ways the game can be played. For example, the game tree for tic-tac-toe has 255,168 leaf nodes.

Game trees are important in artificial intelligence because one way to pick the best move in a game is to search the game tree using the minimax algorithm or its variants. The game tree for tic-tac-toe is easily searchable, but the complete game trees for larger games like chess are much too large to search. Instead, a chess-playing program searches a partial game tree: typically as many plies from the current position as it can search in the time available. Except for the case of "pathological" game trees [1] (which seem to be quite rare in practice), increasing the search depth (i.e., the number of plies searched) generally improves the chance of picking the best move.

Two-person games can also be represented as and-or trees. For the first player to win a game, there must exist a winning move for all moves of the second player. This is represented in the and-or tree by using disjunction to represent the first player's alternative moves and using conjunction to represent all of the second player's moves.

Acyclic Digraph game trees

Cyclic Digraph game trees

Finite vs Infinite Games

A finite game has both some maximum number of moves, and a finite number of nodes in the tree. Thus a finite game must have some finite acyclic game digraph.

An infinite game has one of the following conditions:

  • an infinite number of nodes
  • an infinite number of moves due to a cycle in the graph
  • an infinite number of nodes and an infinite number of moves due to a cycle in the graph

An acyclic game may or may be of finite length. Going back to Tic-Tac-Toe, there are a maximum of nine moves between the players. So the graph would have to be finite.

But let's consider the "game" Name the biggest Number. Thus this simple "game" has no cycles, but if all the players play rationally, then the game should never end. It has an infinite number of nodes.

Name the biggest Number
The youngest player starts and names a number. Each next player names a bigger
number. A player who is not able to name a larger number is eliminated.

A cyclic game can continue forever because the players cycle through a series of moves. Thus games with a cyclic digraph always have always an infinite game tree.

Pragmatically almost all games have stopping rules to prevent such runaway games. The few that don't, like Achi, are implicitly counting on the fact that sooner or later one player will make a mistake.

Sequential vs. Simultaneous moves

The discussion till now has implicitly been about games with sequential moves. ...

[What Links Here]
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.