Combinatorial Games. Tic-Tac-Toe Theory
This extensive book contains a close to ultimate review of the topic of combinatorial game theory. However, it is not just a simple review as most of the book contains the results of the author, who is currently one of the greatest pioneers of this branch of game theory. This seems to be the best and most useful treatment of the subject so far. Traditional game theory has been successful at developing strategy in games of incomplete information: when one player knows something that the other does not. But it has little to say about games of complete information, for example tic-tac-toe, solitaire and hex. This is the subject of combinatorial game theory. To analyse a position in such a game, one has to examine available options, then further options available after selecting any option and so on. This leads to "combinatorial chaos", where brute force study is impractical. In this comprehensive volume, József Beck shows readers how to escape from the combinatorial chaos via the "fake probabilistic method", a game-theory adaptation of the probabilistic method in combinatorics.
At the beginning, the book explains the basic concepts: Tic-Tac-Toe-like games, weak win and strong draw, the connection with Ramsey theory, the strategy stealing argument and plenty of game examples and techniques. Then we move on to full use of the powerful potential technique – games-theory first and second moments. The book continues developing these methods in many complex ways. Using them, the author is able to determine exact results about infinite classes of many games, leading to the discovery of some striking new duality principles and showing many new approaches to understanding combinatorial games. At the end, the volume contains an extremely helpful dictionary and a list of challenging open problems. The book is recommended for a broad mathematical audience. Almost all concepts from other parts of mathematics are explained so it is convenient both for the specialist seeking a detailed survey of the topic and for students hoping to learn something new about the subject. The book has a potential to become a milestone in the development of combinatorial game theory.