Combinatorial game theory

Combinatorial game theory is a special area of mathematics and theoretical computer science. It studies sequential games where two players take turns making moves. These games have clear rules and a known goal. Both players always know what moves are possible. Unlike games with luck or hidden information, combinatorial game theory looks at games where everything is open.

Popular games like chess, checkers, and Go are part of this theory. Simpler games like tic-tac-toe are also studied to see how games can be solved completely. Solving a game means finding the best moves for both players so the result is always the same. For example, tic-tac-toe always ends in a draw if both players play their best.

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

Difference with traditional game theory

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

Combinatorial game theory has 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 looks at practical ways to play, combinatorial game theory is more about understanding the ideas behind the games.

History

Combinatorial game theory began with the study of simple games like Nim, where both players have the same moves. In the 1930s, the Sprague–Grundy theorem showed that these games work like piles in Nim.

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

Examples

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

• Blue–Red Hackenbush - a game where players can build different values.
• Toads and Frogs - a game that can be written with short strings of letters.
• Domineering - a game where moving can be good or bad, 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 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 a player's extra moves or advantage. Positive numbers help the first player (called Left), and 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 at every step. For example, Nim is impartial because any objects one player can remove, the other player can remove too. However, games like domineering or Checkers are not impartial, since the players follow different rules.

For any ordinal number, we can create a game like 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 ∗.