Combinatorial game theory

Combinatorial game theory is a special area of mathematics and theoretical computer science that studies sequential games where two players take turns making moves. These games have clear rules and a known goal, and both players always know what moves are possible. Unlike games that involve luck or hidden information, combinatorial game theory focuses on games where everything is out in the open.

Popular games like chess, checkers, and Go fall under this theory. Even simpler games like tic-tac-toe are studied to understand how games can be solved completely. Solving a game means figuring out the best moves for both players so the result is always the same, no matter what happens. For example, tic-tac-toe always ends in a draw if both players play their best.

Some games, such as Nim, are important for both mathematicians and everyday players. Nim helped shape the field and was one of the first games to be solved using computers. Studying these games helps scientists understand strategy and is also used to teach computers how to make smart moves in games.

Difference with traditional game theory

Combinatorial game theory is different from traditional or economic game theory. While economic game theory often uses probability and deals with incomplete information, combinatorial game theory focuses on two-player perfect-information games. This means both players always know all the moves available.

Combinatorial game theory has developed special ways to study games, like using surreal numbers. These games are important for artificial intelligence, especially in planning and scheduling. Unlike economic game theory, which often looks at practical ways to play, combinatorial game theory is more about understanding the theory behind the games.

History

Combinatorial game theory started with the study of impartial games like Nim, where the same moves are available to both players. In the 1930s, the Sprague–Grundy theorem showed that all such games are similar to piles in Nim.

Later, in the 1960s, researchers like Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy expanded the theory to include partisan games, where players might have different moves. Their important work was published in books such as Winning Ways for your Mathematical Plays and On Numbers and Games. This new theory was inspired by observing the game Go, especially its endgames.

Examples

Combinatorial game theory uses many fun games to help explain its ideas. Some important examples include:

• Blue–Red Hackenbush - a game where players can build different values, like simple fractions or even special numbers.
• Toads and Frogs - a game that can be easily written with short strings of letters.
• Domineering - a game where sometimes moving is good and sometimes it isn’t, helping us understand game temperatures.
• Nim - a simple game that helps create special numbers called nimbers.
• Go - an influential game that helped shape early combinatorial game theory.

Chess is also studied in this field. It has huge complexity, with estimates suggesting there are over 10¹²⁰ possible game paths, known as the Shannon number. While chess remains unsolved, researchers have used computers to understand smaller versions of the game.

Overview

A game is made up of moves two players, called left and right, can make. Each move leads to a new game position, and this idea helps us understand games in a mathematical way. In combinatorial game theory, each game is written as {L|R}, where L shows the moves left can make, and R shows the moves right can make.

For example, in a game called Domineering, players take turns placing dominoes on a board. The rules of the game can be shown using this notation. One simple game, called the star game, has just one move for each player, and the player who makes that move wins. Another simple game is the zero game, where no player can make a move, and the player whose turn it is loses.

Game abbreviations

Numbers in combinatorial game theory show how many extra moves a player has or their advantage. Positive numbers help the first player (called Left), while negative numbers help the second player (called Right). For example, the number 0 means no moves left, and the first player to move will lose. Numbers can be added together like regular integers; for instance, 3 plus −2 equals 1.

The symbol ★, called star, represents a game where the first player to move always wins. When two ★ games are combined, the result is zero, meaning the first player will lose. The star game is special because it is neither positive nor negative; it is considered equal to zero in a confusing way, written as ★ || 0. Another important game is up, written as ↑, which is always positive, while its opposite, called down, written as ↓, is always negative.

Nimbers

An impartial game is a game where both players have the same moves available to them at every point. For example, Nim is impartial because any objects one player can remove, the other player can also remove. However, games like domineering or Checkers are not impartial, since the players follow different rules or use different pieces.

For any ordinal number, we can create a game similar to Nim where players can reduce the number to any smaller ordinal. These special games are called nimbers. The Sprague–Grundy theorem tells us that every impartial game, following the normal play convention, is equivalent to one of these nimbers. The simplest nimbers are 0 and ∗.