You are here

Combinatorial Games: Tic-Tac-Toe Theory

Jósef Beck
Cambridge University Press
Publication Date: 
Number of Pages: 
Encyclopedia of Mathematics and Its Applications 114
[Reviewed by
Kyle Burke
, on

Beck's analyses of weak-win versions of Tic-Tac-Toe-like games both provide interesting results for large game sizes and illustrate the strength of analytical tools. Most notable is the development and use of the "fake probabilistic method." This tool, used to bypass the fruitless brute-force battle with exponential game-tree sizes, mimics the combinatorial probabilistic method but yields exact results for games on large spaces.

Due to the weak-win style of the games presented here, any real coverage of traditional game theory is only offered in the appendix, and should not be missed by the reader. Instead, with these very non-symmetrical games, Beck focuses on exhaustively covering the results of his enlightening fake probabilistic method. The conclusion is far from fake: entire infinite classes of games are shown to be solved.

Beck's text is accessible to game theorists outside of pure mathematics. Indeed, an entire appendix on Ramsey Numbers is given, providing much of the necessary knowledge to follow the main proofs. However, many definitions and explanations are awkwardly "math heavy"; undefined terms from advanced mathematics abound in small examples, where simpler descriptions would suffice.

Despite these minor problems, the text is enjoyable to read. Utilizing the non-symmetrical aspect of the games, Beck poses many examples as one-player puzzles, arming the reader with intuition before presenting some of the larger-scale results. Additionally, Beck is kind enough to include numerous open problems — enough to warrant their own appendix. (Seven of these are pulled aside as the most humiliating.)

Beck describes this work as "a long journey" as he covers as much as seemingly possible with the basic potential analysis as well as the fake probabilistic method. The result is an entertaining and exclusive look at this method and its application to Tic-Tac-Toe-like games.

Kyle Burke is a Ph.D. student in Computer Science at Boston University, working on both developing and solving combinatoric games under his advisor Shang-Hua Teng. He is primarily interested in working with impartial two-player games.

Preface: A summary of the book in a nutshell

Part A. Weak Win and Strong Draw
1. Win vs. weak win
2. The main result: exact solutions for infinite classes of games

Part B. Basic Potential Technique - Game-Theoretic First and Second Moments
3. Simple applications
4. Games and randomness

Part C. Advanced Weak Win - Game-theoretic Higher Moment
5. Self-improving potentials
6. What is the biased meta-conjecture, and why is it so difficult?

Part D. Advanced Strong Draw - Game-theoretic Independence
7. BigGame-SmallGame decomposition
8. Advanced decomposition
9. Game-theoretic lattice-numbers
10. Conclusion

Complete list of open problems

What kind of games? A dictionary

Dictionary of the phrases and concepts

Appendix A. Ramsey numbers
Appendix B. Hales-Jewett theorem: Shelah’s proof
Appendix C. A formal treatment of positional games
Appendix D. An informal introduction to game theory