Intellectual Introduction

“Games of No Chance” are 2-player perfect-information games.

A SUM of such games is naturally defined as the game in which each player at his turn, may choose to make any of his legal moves on any single summand.

The study of such sums is a subject called “combinatorial game theory“. The first part of Winning Ways [2nd edition, 2001-2004] provides a good introduction to this subject. Many research papers on this subject were presented at conferences held in 1994 and 2000 in Berkeley, CA, at the Mathematical Sciences Research Institute (MSRI) and at the Banf Research Center in Canada in 2005 and 2008. Proceedings of those conferences were later published by Cambridge University Press under the titles Games of No Chance (GONC), More Games of No Chance (MGONC), and Games of No Chance 3 (GONC3). Aaron Siegel's Combinatorial Game Theory became the most definitive work on the subject when it appeared in 2013.

The solution of the game of NIM in 1902 by Bouton at Harvard is now viewed as the birth of combinatorial game theory. In the 1930s, Sprague and Grundy extended this theory to cover all impartial games. In the 1970s, the theory was extended to partisan games, a large collection which includes the ancient Hawaiian game called Konane, many variations of Hackenbush, cutcakes, ski-jumps, Domineering, Toads-and-Frogs, etc. One reviewer remarked that although there were over a hundred such games in Winning Ways, most of them had been invented by the authors. John Conway axiomatized this important branch of the subject. His axioms included two restrictive assumptions:

1. The game tree is LOOPFREE, so draws by repetitious play are impossible.
2. The NORMAL TERMINATION RULE states that the game ends when one player is unable to move, and his opponent then wins.

Checkers satisfies the normal termination rule, but it is loopy. For example, if each player has only one king remaining, and each gets into a double corner, then neither player can bring the game to a victorious termination.

Dots-and-Boxes is loopfree, but it violates the normal termination rule because victory is attained by acquiring the higher score rather than by getting the last move. Go also fails to satisfy the normal termination rule, because the game ends when both players choose to pass, and then the winner is determined by counting score. Japanese Go also fails to be loopfree; there are rare positions (such as triple Ko) in which the play can hang in a loop cycling again and again through the same positions. When played according to western rules, Go is loopfree, but only because of a somewhat artificial extra superko rule which forbids moving into any position which occurred earlier in the same game. Japanese Go contains only the more restrictive Ko rule which bans immediate moves through 2-cycle loops in the game tree. Chinese rules of Go ban some superko loops but allow others.

Conway showed that “numbers” occur as a special case of games satisfying his axioms. He then opined that this point of view superseded the classical works of Dedekind, Cantor, and many others. Don Knuth and Martin Kruskal became especially interested in numbers corresponding to infinite games, and the subject of “surreal analysis” was born. Other researchers found partisan games to be a “wonderland” or happy hunting grounds in their quest for examples of mathematical problems having various degrees of classifiable and/or provable difficulty. Indeed, almost all examples of mathematical problems considered harder than NP are combinatorial games. Some consider this intimate connection with complexity theory to be the primary mathematical justification for studying the subject. Aviezri Fraenkel has expounded this view persuasively.

Others, including Berlekamp, have been more fascinated by structural theorems and decomposition properties of partisan games, and with extensions of the axiomatic theory which provide powerful insights into real-world combinatorial games. The key to successful mathematical analysis of a combinatorial game has turned out to be the question of whether or not the positions in the game tend to decompose into sums of simpler positions. This issue creates a great chasm between games whose positions tend to decompose and those which do not. Games on one side of the chasm are fruitful targets for paper-and-pencil mathematical analysis, based on an ever-growing base of general theorems. Games on the other side resist this approach, even in their late-stage endgames. However, some of these games have succumbed to sophisticated computer attacks, which construct large databases of relevant positions.

Although chess definitely lies on the less theoretically tractable side, Noam Elkies showed that it is nearer to the edge of the chasm than checkers. He has composed some very clever “mathematical chess” problems which fit the abstract theory of partisan games. He has also won the annual award of the international chess federation for the best chess problem composition. However, most chess masters see problems of this genre as only very peripherally related to real chess endgames.

When Mathematical Go began in 1989, it initially received a somewhat similarly skeptical reaction from professional Go players. However, as the mathematics expanded and improved, some scholars are now approaching the ability to analyze some real professional games and provide analyses which are deeper and more accurate than those obtained by human experts. The reason for this optimism is that virtually all Go endgames pass through a stage in which the play naturally divides into disjoint battlefields. A typical late-stage Go endgame on a single small battlefield is of at most modest complexity. In the early 1990s, new operators were introduced which map many such positions into the simpler games of Winning Ways. These mappings preserve winning strategies, and formed the original core of Mathematical Go, a subject which has continued to progress at a substantial rate. Researchers in this field have also succeeded in establishing serious communication with certain leading professional Go players, including the women's world champion, Naiwei Rui, 9 dan, and her husband, Jujo Jiang, 9 dan. Under Berlekamp's sponsorship, they have played all-day demonstration games, both at the American Ing Goe Center in Menlo Park in 1998 and at MSRI in 2000, using novel modified rules designed to bridge some of the gap between conventional Go and the more promising mathematical models of it. Bill Spight's paper in MGONC gives an extensive analysis of the last 66 moves of their 1998 game, including four subtle but fatal mistakes. In November 2007, several of the foremost professional Go players in Korea competed against each other in a Professional Coupon Go Endgame Tournament. In November 2010, a similar tournament at the Mind Sports Center in Beijing attracted the best professional Go players in China.

The theory of mathematical Go has advanced to the point that there now appear to be very promising prospects for combining it with some of the best tree-searching algorithms developed in the AI community. An initial goal would be a set of software tools which can analyze most championship-level Go endgames more accurately than any human. This could also have a big intellectual impact throughout east Asia, where the conventional wisdom still holds to the premise that Go demonstrates the superiority of “holistic” Asian thinking over the more “reductionist” approaches favored in the west.

Other interesting operators are known to map other classes of harder games into easier ones. The harder games which have succumbed to attacks of this kind include “Blockbusting”, “2 x n Domineering”, “3 x n Domineering”, and “Entrepreneurial Chess”.

Pencil-and-paper mathematics has met with considerable success in analyzing endgames of virtually every combinatorial game whose positions tend to decompose. Dots-and-Boxes is another such a game. Most people who play it are children, and the number of expert human players is few. Yet the triumph of mathematics over heuristics in Dots-and-Boxes is remarkably decisive. ALL purportedly expert Dots-and-Boxes players have discovered some of the relevant mathematical theorems. Each of them follows a strategy based on his theorems, extended by verbally described heuristic techniques. There are at least four significantly different levels of play. Yet there has never been any player at any level whose skill and heuristics were sufficient to give him any serious chance against even the weakest of the players in the next higher level. Promotion from each level to the next is entirely an issue of mastering another theorem, although interesting heuristic-based contests do occur between any two players at the same level.

The known collection of results in combinatorial game theory includes many theorems which focus on specific classes of games as well as a few general results relevant to all partisan games. One of these rather general portions of the subject is the asymptotic theory, which studies the sum of n copies of an arbitrary finite game, G, for large integers n. The main result is a MEAN VALUE THEOREM (cf. Winning Ways). Earlier versions of this important theorem had been discovered and proved by Hanner and Milnor even before partisan games were axiomatized by Conway. The Mean Value Theorem of combinatorial game theory plays a role analogous to the central limit theorem of probability theory. In games, as in statistics, there is an important sense in which the sum of many objects is typically more well-behaved than its individual summands. Extensions of the Mean Value Theorem to certain kinds of loopy games have uncovered some surprises, including some Ko positions in Go whose mean values are intrinsically ambiguous in the sense that one can get substantially different answers depending on subtle differences in how one phrases the questions. Although there is a sense in which mean values of loopy games can be defined and used, the mean value of a sum of loopy games need not be the sum of the mean values of the summands.

An arbitrary finite loop-free partisan game may be written as the sum of a number and another game which has mean value zero. This is not quite the same as the conventional decomposition of an Abelian group into torsion and torsion-free components, because the group of games with mean value zero includes infinitesimals of many orders, many of which are “torsion-free“. Although one might pursue the decomposition of zero-mean games along those lines, a different decomposition has, so far, attracted more attention. It is

Games such as Domineering or Go include many positions which a good player quickly recognizes as splitting into two or more weakly interacting components, corresponding to different regions of the board. In many such instances, the value of the position is precisely equal to the sum of the values of the components, and so a mathematical decomposition occurs even though the two regions are connected and the correctness of the decomposition is quite nontrivial. In other similar positions, the decomposition yields incorrect results. Similar questions occur in many branches of mathematics (e.g., when is a group the wreath product of two of its subgroups?). Decomposition issues also lie at the heart of the design problem of computer systems, be they hardware or software or both. The crucial design decision is usually how to partition the overall system into tractable modules, and how much and what sorts of interactions to allow between the modules. I personally view combinatorial game theory, especially as it relates to such games as Domineering, Amazons, and Go, as a very fruitful domain in which to explore such issues of modularity.

There is a long and successful tradition of “mathematizing” various branches of human knowledge. Engineering and astronomy both built up substantial bodies of empirical knowledge long before significant portions of those disciplines were mathematized. History shows many such examples in which the application of increasingly sophisticated mathematics to other areas of human knowledge has yielded not only significantly more understanding of the area of the application, but interesting new mathematics as well.

We believe that combinatorial game theory is now in this exciting phase of its historical development. Like many branches of science and engineering, humans already have a vast store of knowledge of games. Chess and Go both have extensive literature and a well-educated cadre of professional masters who have devoted their careers to studies of the game. Go originated in China at least 4000 years ago. The professional Go community in Japan has libraries and institutions dating back about 300 years. Indeed, if an accountant attempted to estimate the total number of human man-hours that have been spent on various human activities, he might plausibly conclude that the total human man-hours spent playing Go is well in excess of the total time spent studying calculus.

There are two other branches of game theory, which have significantly different emphases than combinatorial game theory.

One is called artificial intelligence, or AI. The AI approach to game-playing emphasizes very hard problems, including the play of openings and middle games which are so complicated that even the best human experts remain unsure whether any winning move exists or not. In the twentieth century, the favored AI methods were very limited search followed by heuristic evaluation and backtracking. In many games, the AI heuristics were sufficient to play competitively against most humans, but rarely good enough to compete with the human champions, who in turn might well all be playing at some level still well below perfection.

Many devotees of artificial intelligence have long hoped that there would be considerable commonality in the best programs for chess, checkers, Go, Othello, etc. On the other hand, skeptics saw little such commonality in the best programs written before 2000.

After the chess victory of Big Blue over Kasparov, much of the AI community's interest has shifted to Go, a game in which, up until 2016, thousands of humans could consistently beat the world's best current computer program.

All human Go players of professional rank can recognize a vast number of patterns. They quickly distinguish good shape from bad shape; thickness from heaviness. They can also “read out” long lines of hot play. Computers have long been superb at reading long lines of play, although until recently they were no match for humans at recognizing the patterns or the positions whose followers were worth exploring. Then in 2016, a small group at Google succeeded in training a deeper neural-net-simulating program on a vast number of human professional games, from which it “learned” how to distinguish good shape from bad shape, and thickness from heaviness. Their program which was based on this neural net then succeeded in a competitive match against one of the world champion professional human Go players!

The standards of artificial intelligence are necessarily empirical rather than logical. Performance of programs is evaluated subjectively, and by competitions against each other or against human experts. Since no one knows which of their moves are correct and which are not. Many people assume that the best humans are playing nearly perfectly, but I'm among the skeptics who think that perfection remains a distant goal.

As I use the term, “combinatorial game theory” differs from artificial intelligence in the same primary respect that mathematics differs from engineering: the emphasis is on conclusions which are provably correct rather than on conclusions which are plausible or good enough to be acceptable in some imprecise sense. The mathematicians' main goal is understanding; the engineer's main goal is a functioning system. Despite this important philosophical difference, there are many areas of overlap between combinatorial game theory and AI. Combinatorial game theorists are quite willing to use software tools and systems developed by AI practitioners. Many AI buffs are quite willing to use results of combinatorial game theory whenever relevant results exist. Some even view endgame analysis by database construction as AI; others see it as computer solutions of some very important yet very specific combinatorial game problems.

A third branch of game theory is the classical probabilistic theory of two-person games with chance and/or imperfect information. This is the sort of classical von Neumann game theory in which several people, including John Hicks, Kenneth Arrow, John Harsanyi, John Nash and Reinhard Selten have won Nobel prizes in economics. This subject differs even more from combinatorial game theory and AI than the latter two differ from each other. Even so, there are some significant overlaps. Linear programming lies near the core of the classical probabilistic game theory. Linear programming also plays a much smaller but still significant role in combinatorial game theory (e.g., in one proof of one of D. Wolfe's theorems).

Most of the initial theoretical results of combinatorial game theory were achieved by exploiting the power of recursions. Combinatorial game theory has that in common with many other mathematical topics, including fractals and chaos. Combinatorial game theory also has obvious and more detailed overlaps with many other branches of mathematics and computer science, including topics such as algorithms, complexity theory, finite automata, logic, surreal analysis, number theory, and probability.