Misplaced Pages

#209790

44-541: The first volume introduces combinatorial game theory and its foundation in the surreal numbers ; partizan and impartial games ; Sprague–Grundy theory and misère games . The second volume applies the theorems of the first volume to many games, including nim , sprouts , dots and boxes , Sylver coinage , philosopher's phutball , fox and geese . A final section on puzzles analyzes the Soma cube , Rubik's Cube , peg solitaire , and Conway's Game of Life . A republication of

88-430: A minimax search to determine the value of the initial position. It is hard even to estimate the game-tree complexity, but for some games an approximation can be given by raising the game's average branching factor b to the power of the number of plies d in an average game, or: G T C ≥ b d {\displaystyle GTC\geq b^{d}} . The computational complexity of

132-434: A position that the players take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance,

176-449: A choice of sides and then defeat them either way. Another game studied in the context of combinatorial game theory is chess . In 1953 Alan Turing wrote of the game, "If one can explain quite unambiguously in English, with the aid of mathematical symbols if required, how a calculation is to be done, then it is always possible to programme any digital computer to do that calculation, provided

220-448: A draw—but this result was a computer-assisted proof . Other real world games are mostly too complicated to allow complete analysis today, although the theory has had some recent successes in analyzing Go endgames. Applying combinatorial game theory to a position attempts to determine the optimum sequence of moves for both players until the game ends, and by doing so discover the optimum move in any position. In practice, this process

264-457: A fixed size of board is a finite problem that can be solved in O(1), for example by a look-up table from positions to the best move in each position.) The asymptotic complexity is defined by the most efficient (in terms of whatever computational resource one is considering) algorithm for solving the game; the most common complexity measure ( computation time ) is always lower-bounded by the logarithm of

308-405: A game describes the asymptotic difficulty of a game as it grows arbitrarily large, expressed in big O notation or as membership in a complexity class . This concept doesn't apply to particular games, but rather to games that have been generalized so they can be made arbitrarily large, typically by playing them on an n -by- n board. (From the point of view of computational complexity a game on

352-413: A game is the number of legal game positions reachable from the initial position of the game. When this is too hard to calculate, an upper bound can often be computed by also counting (some) illegal positions, meaning positions that can never arise in the course of a game. The game tree size is the total number of possible games that can be played: the number of leaf nodes in the game tree rooted at

396-485: A simple upper bound for the size of the state space is 3 = 19,683. (There are three states for each cell and nine cells.) This count includes many illegal positions, such as a position with five crosses and no noughts, or a position in which both players have a row of three. A more careful count, removing these illegal positions, gives 5,478. And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions. To bound

440-455: A small number of pieces are being studied). A game, in its simplest terms, is a list of possible "moves" that two players, called left and right , can make. The game position resulting from any move can be considered to be another game. This idea of viewing games in terms of their possible moves to other games leads to a recursive mathematical definition of games that is standard in combinatorial game theory. In this definition, each game has

484-493: Is generalized . A natural generalization is to m , n , k -games : played on an m by n board with winner being the first player to get k in a row. It is immediately clear that this game can be solved in DSPACE ( mn ) by searching the entire game tree. This places it in the important complexity class PSPACE . With some more work it can be shown to be PSPACE-complete . Due to the large size of game complexities, this table gives

SECTION 10

#1732906211210

528-497: Is a loopy game, in which a valid move of either left or right is a game that can then lead back to the first game. Checkers , for example, becomes loopy when one of the pieces promotes, as then it can cycle endlessly between two or more squares. A game that does not possess such moves is called loopfree . There are also transfinite games, which have infinitely many positions—that is, left and right have lists of moves that are infinite rather than finite. Numbers represent

572-497: Is a position in combinatorial game theory. In standard notation, ↑ = {0|∗}. Up is strictly positive (↑ > 0), but is infinitesimal . Up is defined in Winning Ways for your Mathematical Plays . Down , written as ↓, is a position in combinatorial game theory. In standard notation, ↓ = {∗|0}. Down is strictly negative (↓ < 0), but is infinitesimal . Down is defined in Winning Ways for your Mathematical Plays . Consider

616-485: Is also of interest in artificial intelligence , particularly for automated planning and scheduling . In combinatorial game theory there has been less emphasis on refining practical search algorithms (such as the alpha–beta pruning heuristic included in most artificial intelligence textbooks), but more emphasis on descriptive theoretical results (such as measures of game complexity or proofs of optimal solution existence without necessarily specifying an algorithm, such as

660-589: Is an impartial game for two players, and subject to the normal play condition , which means that a player who cannot move loses. In the 1930s, the Sprague–Grundy theorem showed that all impartial games are equivalent to heaps in Nim, thus showing that major unifications are possible in games considered at a combinatorial level, in which detailed strategies matter, not just pay-offs. In the 1960s, Elwyn R. Berlekamp , John H. Conway and Richard K. Guy jointly introduced

704-410: Is considered trivial, in the sense of being "easy to solve". Some combinatorial games may also have an unbounded playing area, such as infinite chess . In combinatorial game theory, the moves in these and other games are represented as a game tree . Combinatorial games also include one-player combinatorial puzzles such as Sudoku , and no-player automata, such as Conway's Game of Life , (although in

748-403: Is the number of leaf nodes in the smallest decision tree that establishes the value of the initial position. The game-tree complexity of a game is the number of leaf nodes in the smallest full-width decision tree that establishes the value of the initial position. A full-width tree includes all nodes at each depth. This is an estimate of the number of positions one would have to evaluate in

792-420: Is torturously difficult unless the game is very simple. It can be helpful to distinguish between combinatorial "mathgames" of interest primarily to mathematicians and scientists to ponder and solve, and combinatorial "playgames" of interest to the general population as a form of entertainment and competition. However, a number of games fall into both categories. Nim , for instance, is a playgame instrumental in

836-470: The strategy-stealing argument ). An important notion in combinatorial game theory is that of the solved game . For example, tic-tac-toe is considered a solved game, as it can be proven that any game will result in a draw if both players play optimally. Deriving similar results for games with rich combinatorial structures is difficult. For instance, in 2007 it was announced that checkers has been weakly solved —optimal play by both sides also leads to

880-459: The sum of two games, which is a game where each player may choose to move either in one game or the other at any point in the game, and a player wins when his opponent has no move in either game. This way of combining games leads to a rich and powerful mathematical structure. Conway stated in On Numbers and Games that the inspiration for the theory of partisan games was based on his observation of

924-414: The asymptotic state-space complexity, since a solution algorithm must work for every possible state of the game. It will be upper-bounded by the complexity of any particular algorithm that works for the family of games. Similar remarks apply to the second-most commonly used complexity measure, the amount of space or computer memory used by the computation. It is not obvious that there is any lower bound on

SECTION 20

#1732906211210

968-438: The class of the surreal numbers . Star , written as ∗ or {0|0}, is a first-player win since either player must (if first to move in the game) move to a zero game, and therefore win. The game ∗ is neither positive nor negative; it and all other games in which the first player wins (regardless of which side the player is on) are said to be fuzzy with or confused with 0; symbolically, we write ∗ || 0. Up , written as ↑,

1012-415: The foundation of combinatorial game theory, and one of the first computerized games. Tic-tac-toe is still used to teach basic principles of game AI design to computer science students. Combinatorial game theory arose in relation to the theory of impartial games , in which any play available to one player must be available to the other as well. One such game is Nim , which can be solved completely. Nim

1056-602: The game in a way that only increases the size of the game tree (for example, by allowing illegal moves) until it becomes tractable. For games where the number of moves is not limited (for example by the size of the board, or by a rule about repetition of position) the game tree is generally infinite. The next two measures use the idea of a decision tree , which is a subtree of the game tree, with each position labelled with "player A wins", "player B wins" or "drawn", if that position can be proved to have that value (assuming best play by both sides) by examining only other positions in

1100-454: The game states. The above game describes a scenario in which there is only one move left for either player, and if either player makes that move, that player wins. (An irrelevant open square at C3 has been omitted from the diagram.) The {|} in each player's move list (corresponding to the single leftover square after the move) is called the zero game , and can actually be abbreviated 0. In the zero game, neither player has any valid moves; thus,

1144-416: The game tree, there are 9 possible initial moves, 8 possible responses, and so on, so that there are at most 9! or 362,880 total games. However, games may take less than 9 moves to resolve, and an exact enumeration gives 255,168 possible games. When rotations and reflections of positions are considered the same, there are only 26,830 possible games. The computational complexity of tic-tac-toe depends on how it

1188-431: The game {1|−1}. Both moves in this game are an advantage for the player who makes them; so the game is said to be "hot;" it is greater than any number less than −1, less than any number greater than 1, and fuzzy with any number in between. It is written as ±1. It can be added to numbers, or multiplied by positive ones, in the expected fashion; for example, 4 ± 1 = {5|3}. An impartial game is one where, at every position of

1232-443: The game's initial position. The game tree is typically vastly larger than the state space because the same positions can occur in many games by making moves in a different order (for example, in a tic-tac-toe game with two X and one O on the board, this position could have been reached in two different ways depending on where the first X was placed). An upper bound for the size of the game tree can sometimes be computed by simplifying

1276-507: The game, the same moves are available to both players. For instance, Nim is impartial, as any set of objects that can be removed by one player can be removed by the other. However, domineering is not impartial, because one player places horizontal dominoes and the other places vertical ones. Likewise Checkers is not impartial, since the players own different colored pieces. For any ordinal number , one can define an impartial game generalizing Nim in which, on each move, either player may replace

1320-399: The graph. (Terminal positions can be labelled directly; a position with player A to move can be labelled "player A wins" if any successor position is a win for A, or labelled "player B wins" if all successor positions are wins for B, or labelled "draw" if all successor positions are either drawn or wins for B. And correspondingly for positions with B to move.) Decision complexity of a game

1364-400: The notation {L|R} . L is the set of game positions that the left player can move to, and R is the set of game positions that the right player can move to; each position in L and R is defined as a game using the same notation. Using Domineering as an example, label each of the sixteen boxes of the four-by-four board by A1 for the upper leftmost square, C2 for the third box from the left on

Winning Ways for Your Mathematical Plays - Misplaced Pages Continue

1408-400: The number of free moves, or the move advantage of a particular player. By convention positive numbers represent an advantage for Left, while negative numbers represent an advantage for Right. They are defined recursively with 0 being the base case. The zero game is a loss for the first player. The sum of number games behaves like the integers, for example 3 + −2 = 1. Any game number is in

1452-593: The number with any smaller ordinal number; the games defined in this way are known as nimbers . The Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber. The "smallest" nimbers – the simplest and least under the usual ordering of the ordinals – are 0 and ∗. Game complexity Combinatorial game theory measures game complexity in several ways: These measures involve understanding game positions, possible outcomes, and computation required for various game scenarios. The state-space complexity of

1496-654: The play in Go endgames, which can often be decomposed into sums of simpler endgames isolated from each other in different parts of the board. The introductory text Winning Ways introduced a large number of games, but the following were used as motivating examples for the introductory theory: The classic game Go was influential on the early combinatorial game theory, and Berlekamp and Wolfe subsequently developed an endgame and temperature theory for it (see references). Armed with this they were able to construct plausible Go endgame positions from which they could give expert Go players

1540-458: The player whose turn it is when the zero game comes up automatically loses. The type of game in the diagram above also has a simple name; it is called the star game , which can also be abbreviated ∗. In the star game, the only valid move leads to the zero game, which means that whoever's turn comes up during the star game automatically wins. An additional type of game, not found in Domineering,

1584-431: The second row from the top, and so on. We use e.g. (D3, D4) to stand for the game position in which a vertical domino has been placed in the bottom right corner. Then, the initial position can be described in combinatorial game theory notation as In standard Cross-Cram play, the players alternate turns, but this alternation is handled implicitly by the definitions of combinatorial game theory rather than being encoded within

1628-405: The space complexity for a typical game, because the algorithm need not store game states; however many games of interest are known to be PSPACE-hard , and it follows that their space complexity will be lower-bounded by the logarithm of the asymptotic state-space complexity as well (technically the bound is only a polynomial in this quantity; but it is usually known to be linear). For tic-tac-toe ,

1672-607: The storage capacity is adequate." In a 1950 paper, Claude Shannon estimated the lower bound of the game-tree complexity of chess to be 10 , and today this is referred to as the Shannon number . Chess remains unsolved, although extensive study, including work involving the use of supercomputers has created chess endgame tablebases , which shows the result of perfect play for all end-games with seven pieces or less. Infinite chess has an even greater combinatorial complexity than chess (unless only limited end-games, or composed positions with

1716-440: The strictest definition, "games" can be said to require more than one participant, thus the designations of "puzzle" and "automata". ) Game theory in general includes games of chance, games of imperfect knowledge, and games in which players can move simultaneously, and they tend to represent real-life decision making situations. Combinatorial game theory has a different emphasis than "traditional" or "economic" game theory, which

1760-446: The theory of a partisan game , in which the requirement that a play available to one player be available to both is relaxed. Their results were published in their book Winning Ways for your Mathematical Plays in 1982. However, the first work published on the subject was Conway's 1976 book On Numbers and Games , also known as ONAG, which introduced the concept of surreal numbers and the generalization to games. On Numbers and Games

1804-493: The types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field. Combinatorial games include well-known games such as chess , checkers , and Go , which are regarded as non-trivial, and tic-tac-toe , which

Winning Ways for Your Mathematical Plays - Misplaced Pages Continue

1848-422: The work by A K Peters split the content into four volumes. This is a partial list of the games mentioned in the book. Note: Misère games not included Combinatorial game theory Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information . Study has been largely confined to two-player games that have

1892-409: Was also a fruit of the collaboration between Berlekamp, Conway, and Guy. Combinatorial games are generally, by convention, put into a form where one player wins when the other has no moves remaining. It is easy to convert any finite game with only two possible results into an equivalent one where this convention applies. One of the most important concepts in the theory of combinatorial games is that of

1936-429: Was initially developed to study games with simple combinatorial structure, but with elements of chance (although it also considers sequential moves, see extensive-form game ). Essentially, combinatorial game theory has contributed new methods for analyzing game trees, for example using surreal numbers , which are a subclass of all two-player perfect-information games. The type of games studied by combinatorial game theory

#209790