Sprouts is a paper-and-pencil game with significant mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in the early 1960s; the game is played starting with a few spots drawn on a sheet of paper. Players take turns, where each turn consists of drawing a line between two spots and adding a new spot somewhere along the line; the players are constrained by the following rules. The line must not touch or cross itself or any other line; the new spot cannot be placed on top of one of the endpoints of the new line. Thus the new spot splits the line into two shorter lines. No spot may have more than three lines attached to it. For the purposes of this rule, a line from the spot to itself counts as two attached lines and new spots are counted as having two lines attached to them. In so-called normal play, the player who makes the last move wins. In misère play, the player who makes the last move loses. Misère Sprouts is the only misère combinatorial game, played competitively in an organized forum.
The diagram on the right shows a 2-spot game of normal-play Sprouts. After the fourth move, most of the spots are dead–they have three lines attached to them, so they cannot be used as endpoints for a new line. There are two spots. However, it is impossible to make another move, because a line from a live spot to itself would make four attachments, a line from one live spot to the other would cross lines. Therefore, no fifth move is possible, the first player loses. Live spots at the end of the game are called survivors and play a key role in the analysis of Sprouts, it is not evident from the rules of Sprouts that the game always terminates, since the number of spots increase at each move. The correct approach is to consider the number of lives instead of the number of spots. We can show that if the game starts with n spots, it will end in no more than 3n−1 moves and no fewer than 2n moves. In the following proofs, we suppose that a game starts with n spots and lasts for m moves; each spot starts with three lives and each move reduces the total number of lives in the game by one.
So at the end of the game there are 3n−m remaining lives. Each surviving spot has only one life, so there are 3n−m survivors. There must be at least one survivor, namely the spot added in the final move. So 3n−m ≥ 1; this upper bound is the maximum, it can be attained in many ways by ensuring that there is only one survivor at the end of the game. For instance, the game on the right has 3n − 1 moves. At the end of the game each survivor has two dead neighbors, in a technical sense of "neighbor", different from the ordinary graph notion of adjacency. No dead spot can be the neighbor of two different survivors, for otherwise there would be a move joining the survivors. All other dead spots are called pharisees. Suppose there are p pharisees. N + m = 3 n − m + 2 + p since initial spots + moves = total spots at end of game = survivors + neighbors + pharisees. Rearranging gives: m = 2 n + p / 4 So a game lasts for at least 2n moves, the number of pharisees is divisible by 4; this lower bound on the length of a game is the minimum.
The diagram on the right shows a completed game of 2n moves. It has 2n neighbors and 0 pharisees. Real games seem to turn into a battle over whether the number of moves will be k or k+1 with other possibilities being quite unlikely. One player tries to create enclosed regions containing survivors and the other tries to create pharisees. Since Sprouts is a finite game where no draw is possible, a perfect strategy exists either for the first or the second player, depending on the number of initial spots; the main question about a given starting position is to determine which player can force a win if he or she plays perfectly. When the winning strategy is for the first player, it is said that the outcome of the position is a "win", when the winning strategy is for the second player, it is said that the outcome of the position is a "loss"; the outcome is determined by developing the game tree of the starting position. This can be done by hand only for a small number of spots, all the new results since 1990 have been obtained by extensive search with computers.
Winning Ways for your Mathematical Plays reports that the 6-spot normal game was proved to be a win for the second player by Denis Mollison, with a hand-made analysis of 47 pages. It stood as the record for a long time, until the first computer analysis, done at Carnegie Mellon University, in 1990, by David Applegate, Guy Jacobson, Daniel Sleator, they reached up to 11 spots with some of the best hardware available at the time. Applegate and Sleator observed a pattern in their results, conjectured that the first playe
Combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that studies sequential games with perfect information. Study has been confined to two-player games that have a position in which the players take turns changing in defined ways or moves to achieve a defined winning condition. CGT 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, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are changing. Scholars will define what they mean by a "game" at the beginning of a paper, these definitions 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, Go, which are regarded as non-trivial, tic-tac-toe, considered as trivial in the sense of being "easy to solve".
Some combinatorial games may have an unbounded playing area, such as infinite chess. In CGT, the moves in these and other games are represented as a game tree. Combinatorial games include one-player combinatorial puzzles such as Sudoku, no-player automata, such as Conway's Game of Life, Game theory in general includes games of chance, games of imperfect knowledge, games in which players can move and they tend to represent real-life decision making situations. CGT has a different emphasis than "traditional" or "economic" game theory, developed to study games with simple combinatorial structure, but with elements of chance. CGT 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 CGT is of interest in artificial intelligence for automated planning and scheduling. In CGT there has been less emphasis on refining practical search algorithms, but more emphasis on descriptive theoretical results.
An important notion in CGT 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 leads to a draw—but this result was a computer-assisted proof. Other real world games are too complicated to allow complete analysis today, although the theory has had some recent successes in analyzing Go endgames. Applying CGT to a position attempts to determine the optimum sequence of moves for both players until the game ends, by doing so discover the optimum move in any position. In practice, this process is torturously difficult unless the game is simple, it can be helpful to distinguish between combinatorial "mathgames" of interest to mathematicians and scientists to ponder and solve, 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 the foundation of CGT, one of the first computerized games. Tic-tac-toe is still used to teach basic principles of game AI design to computer science students. CGT 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. Nim is an impartial game for two players, 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 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 known as ONAG, which introduced the concept of surreal numbers and the generalization to games. On Numbers and Games was a fruit of the collaboration between Berlekamp and Guy. Combinatorial games are 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 the sum of two games, a game where each player may choose to move either in one game or the other at any point in the game, a player wins when his opponent has no move in either game; this way of combining games leads to a powerful mathematical structure. John Conway states in ONAG that the inspira
John Horton Conway
John Horton Conway is an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He has contributed to many branches of recreational mathematics, notably the invention of the cellular automaton called the Game of Life. Conway spent the first half of his long career at the University of Cambridge, in England, the second half at Princeton University in New Jersey, where he now holds the title Professor Emeritus. Conway was born in the son of Cyril Horton Conway and Agnes Boyce, he became interested in mathematics at a early age. By the age of eleven his ambition was to become a mathematician. After leaving sixth form, Conway entered Caius College, Cambridge to study mathematics. Conway, a "terribly introverted adolescent" in school, interpreted his admission to Cambridge as an opportunity to transform himself into a new person: an "extrovert", he was awarded his Bachelor of Arts degree in 1959 and began to undertake research in number theory supervised by Harold Davenport.
Having solved the open problem posed by Davenport on writing numbers as the sums of fifth powers, Conway began to become interested in infinite ordinals. It appears that his interest in games began during his years studying the Cambridge Mathematical Tripos, where he became an avid backgammon player, spending hours playing the game in the common room, he was awarded his doctorate in 1964 and was appointed as College Fellow and Lecturer in Mathematics at the University of Cambridge. After leaving Cambridge in 1986, he took up the appointment to the John von Neumann Chair of Mathematics at Princeton University. Conway is known for the invention of the Game of Life, one of the early examples of a cellular automaton, his initial experiments in that field were done with pen and paper, long before personal computers existed. Since the game was introduced by Martin Gardner in Scientific American in 1970, it has spawned hundreds of computer programs, web sites, articles, it is a staple of recreational mathematics.
There is an extensive wiki devoted to cataloging the various aspects of the game. From the earliest days it has been a favorite in computer labs, both for its theoretical interest and as a practical exercise in programming and data display. At times Conway has said he hates the Game of Life–largely because it has come to overshadow some of the other deeper and more important things he has done; the game did help launch a new branch of mathematics, the field of cellular automata. The Game of Life is now known to be Turing complete. Conway's career is intertwined with mathematics popularizer and Scientific American columnist Martin Gardner; when Gardner featured Conway's Game of Life in his Mathematical Games column in October 1970, it became the most read of all his columns and made Conway an instant celebrity. Gardner and Conway had first corresponded in the late 1950s, over the years Gardner had written about recreational aspects of Conway's work. For instance, he discussed Conway's game of Sprouts and his angel and devil problem.
In the September 1976 column he reviewed Conway's book On Numbers and Games and introduced the public to Conway's surreal numbers. Conferences called Gathering 4 Gardner are held every two years to celebrate the legacy of Martin Gardner, Conway himself has been a featured speaker at these events, discussing various aspects of recreational mathematics. Conway is known for his contributions to combinatorial game theory, a theory of partisan games; this he developed with Elwyn Berlekamp and Richard Guy, with them co-authored the book Winning Ways for your Mathematical Plays. He wrote the book On Numbers and Games which lays out the mathematical foundations of CGT, he is one of the inventors of sprouts, as well as philosopher's football. He developed detailed analyses of many other games and puzzles, such as the Soma cube, peg solitaire, Conway's soldiers, he came up with the angel problem, solved in 2006. He invented a new system of numbers, the surreal numbers, which are related to certain games and have been the subject of a mathematical novel by Donald Knuth.
He invented a nomenclature for exceedingly large numbers, the Conway chained arrow notation. Much of this is discussed in the 0th part of ONAG. In the mid-1960s with Michael Guy, son of Richard Guy, Conway established that there are sixty-four convex uniform polychora excluding two infinite sets of prismatic forms, they discovered the grand antiprism in the only non-Wythoffian uniform polychoron. Conway has suggested a system of notation dedicated to describing polyhedra called Conway polyhedron notation. In the theory of tessellations, he devised the Conway criterion which describes rules for deciding if a prototile will tile the plane, he investigated lattices in higher dimensions, was the first to determine the symmetry group of the Leech lattice. In knot theory, Conway formulated a new variation of the Alexander polynomial and produced a new invariant now called the Conway polynomial. After lying dormant for more than a decade, this concept became central to work in the 1980s on the novel knot polynomials.
Conway further developed tangle theory and invented a system of notation for tabulating knots, nowadays known as Conway notation, while correcting a number of errors in the 19th century knot tables and extending them to include all but four of the non-alternating primes with 11 crossings. See Topology Proceedings 7 118, he was the primary author of the ATLAS of Finite Groups giving prope
On Numbers and Games
On Numbers and Games is a mathematics book by John Horton Conway first published in 1976. The book is written by a pre-eminent mathematician, is directed at other mathematicians; the material is, developed in a playful and unpretentious manner and many chapters are accessible to non-mathematicians. Martin Gardner discussed the book at length Conway's construction of Surreal numbers, in his Mathematical Games column in Scientific American in September 1976; the book is divided into two sections: the first half, on numbers, the second half, on games. In the first section, Conway provides an axiomatic construction of numbers and ordinal arithmetic, the integers, the countable infinity, entire towers of infinite ordinals, using a notation, an trite variation of the Dedekind cut; as such, the construction is rooted in axiomatic set theory, is related to the Zermelo–Fraenkel axioms. The section covers what Conway termed the "surreal numbers". Conway notes that, in this notation, the numbers in fact belong to a larger class, the class of all two-player games.
The axioms for greater than and less than are seen to be a natural ordering on games, corresponding to which of the two players may win. The remainder of the book is devoted to exploring a number of different two-player games, such as nim and the map-coloring games col and snort; the development includes their scoring, a review of Sprague–Grundy theorem, the inter-relationships to numbers, including their relationship to infinitesimals. The book was first published by Academic Press Inc in 1976, ISBN 0-12-186350-6, re-released by AK Peters in 2000. A game in the sense of Conway is a position in a contest between two players and Right; each player has a set of games called options to choose from in turn. Games are written where L is the set of Left's options and R is the set of Right's options. At the start there are no games at all, so the empty set is the only set of options we can provide to the players; this defines the game, called 0. We consider a player who has no options to have lost the game.
Given this game 0 there are now two possible sets of options, the empty set and the set whose only element is zero. The game is called 1, the game is called -1; the game is called *, is the first game we find, not a number. All numbers are positive, negative, or zero, we say that a game is positive if Left will win, negative if Right will win, or zero if the second player will win. Games that are not numbers have a fourth possibility: they may be fuzzy, meaning that the first player will win. * is a fuzzy game. Winning Ways for your Mathematical Plays