## Combinatorial Games: Tic-Tac-Toe TheoryTraditional 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. The main challenge of combinatorial game theory is to handle 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-theoretic adaptation of the probabilistic method in combinatorics. Using this, the author is able to determine the exact results about infinite classes of many games, leading to the discovery of some striking new duality principles. Available for the first time in paperback, it includes a new appendix to address the results that have appeared since the book's original publication. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

PART A WEAK WIN AND STRONG DRAW | 15 |

Analyzing the proof of Theorem1 1 | 41 |

TicTacToe like games | 59 |

Games on hypergraphs and the combinatorial chaos | 72 |

exact solutions for infinite classes | 91 |

Potentials and the ErdosSelfridge Theorem | 146 |

Local vs Global | 163 |

Ramsey Theory and Hypercube TicTacToe | 172 |

Sacrificing the probabilistic intuition to force | 418 |

Sporadic results | 430 |

More sporadic results | 439 |

ADVANCED STRONG DRAW GAMETHEORETIC | 459 |

Reinforcing the ErdosSelfridge technique I | 470 |

Reinforcing the ErdosSelfridge technique II | 479 |

Almost Disjoint hypergraphs | 485 |

Exact solution of the Clique Game II | 492 |

PART B BASIC POTENTIAL TECHNIQUE GAME | 193 |

Games beyond Ramsey Theory | 204 |

A generalization of Kaplanskys game | 216 |

Games and randomness | 230 |

when the extension from fair | 245 |

A simple illustration of randomness I | 260 |

A simple illustration of randomness II | 270 |

Another illustration of randomness in games | 286 |

ADVANCED WEAK WIN GAMETHEORETIC | 305 |

application to | 320 |

Weak Win in the Lattice Games | 329 |

Gametheoretic higher moments | 340 |

Exact solution of the Clique Game I | 352 |

More applications | 362 |

Whoscoresmore games | 372 |

What is the Biased MetaConjecture and why is | 380 |

Discrepancy games II | 392 |

Biased MetaConjecture | 400 |

Advanced decomposition | 504 |

Breaking the squareroot barrier I | 525 |

Breaking the squareroot barrier II | 536 |

Van der Waerden Game and the RELARIN technique | 545 |

Gametheoretic latticenumbers | 552 |

exact solution | 575 |

Conclusion | 610 |

Miscellany I | 620 |

Miscellany II | 634 |

Concluding remarks | 644 |

Appendix A Ramsey Numbers | 658 |

Shelahs proof | 669 |

A formal treatment of Positional Games | 677 |

An informal introduction to game theory | 705 |

Complete list of the Open Problems | 716 |

What kinds of games? A dictionary | 724 |

730 | |

### Common terms and phrases

2-Coloring Achievement Number Aligned Square Lattice analogue arbitrary arithmetic progression assume Avoidance Number biased Big Board Big Game Big Sets block Breaker Chooser Chooser–Picker chooses Clique Game color complete graph completes the proof defined denote Disjoint hypergraph drawing strategy edges emergency set Erd˝os–Selfridge Theorem exponential finite hypergraph game-theoretic goal Hamiltonian cycle hazardous set hypercube hyperedge hypergraph inequality integer intersection Lattice Games least Lemma log2 log2N logn lower bound Maker Maker–Breaker monochromatic Move Number occupy a whole Open Problem parallelogram lattice Picker Picker–Chooser pigeonhole principle plane play player can force player win Positional Game probabilistic proof of Theorem prove Ramsey Theory Random Graph second player secondary set Section small board small game small sets Strategy Stealing Strong Draw subset super-sets Theorem 1.2 Tic-Tac-Toe torus torus game total number trivial unoccupied upper bound vertices whole winning set winning lines winning strategy xi+1 yi+1

### References to this book

Building Bridges: Between Mathematics and Computer Science Martin Grötschel,Gyula O.H. Katona Limited preview - 2008 |