Combinatorial games : tic-tac-toe theory / József Beck.

Format:

Book

Author/Creator:

Beck, József, author.

Series:

Encyclopedia of mathematics and its applications ; v. 114.

Encyclopedia of mathematics and its applications ; volume 114

Language:

English

Subjects (All):

Game theory.

Combinatorial analysis.

Physical Description:

1 online resource (xiv, 732 pages) : digital, PDF file(s).

Edition:

1st ed.

Place of Publication:

Cambridge : Cambridge University Press, 2008.

Language Note:

English

Summary:

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. 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.

Contents:

pt. A. Weak win and strong draw

ch. I. Win vs. weak win

Illustration : every finite point set in the plane is a weak winner

Analyzing the proof of theorem 1.1

Examples : tic-tac-toe games

More examples : tic-tac-toe like games

Games on hypergraphs, and the combinatorial chaos

ch. II. The main result : exact solutions for infinite classes of games

Ramsey theory and clique games

Arithmetic progressions

Two-dimensional arithmetic progressions

Explaining the exact solutions : a meta-conjecture

Potentials and the Erdős-Selfridge theorem

Local vs. global

Ramsey theory and hypercube tic-tac-toe

pt. B. Basic potential technique : game-theoretic first and second moments

ch. III. Simple applications

Easy building via theorem 1.2

Games beyond Ramsey theory

A generalization of Kaplansky's game

ch. IV. Games and randomness

Discrepancy games and the variance

Biased discrepancy games : when the extension from fair to biased works!

A simple illustration of "randomness" (I)

A simple illustration of "randomness" (II)

Another illustration of "randomness" in games.

pt. C. Advanced weak win : game-theoretic higher moment

ch. V. Self-improving potentials

Motivating the probabilistic approach

Game-theoretic second moment : application to the picker-choose game

Weak win in the lattice games

Game-theoretic higher moments

Exact solution of the clique game (I)

More applications

Who-scores-more games

ch. VI. What is the biased meta-conjecture, and why is it so difficult?

Discrepancy games (I)

Discrepancy games (II)

Biased games (I) : biased meta-conjecture

Biased games (II) : sacrificing the probabilistic intuition to force negativity

Biased games (III) : sporadic results

Biased games (IV) : more sporadic results

pt. D. Advanced strong draw : game-theoretic independence

ch. VII. BigGame-SmallGame decomposition

The Hales-Jewett conjecture

Reinforcing the Erdős-Selfridge technique (I)

Reinforcing the Erdős-Selfridge technique (II)

Almost disjoint hypergraphs

Exact solution of the clique game (II).

ch. VIII. Advanced decomposition

Proof of the second ugly theorem

Breaking the "square-root barrier" (I)

Breaking the "square-root barrier" (II)

Van der Waerden game and the RELARIN technique

ch. IX. Game-theoretic lattice-numbers

Winning planes : exact solution

Winning lattices : exact solution

I-can-you-can't games

second player's moral victory

ch. X. Conclusion

More exact solutions and more partial results

Miscellany (I)

Miscellany (II)

Concluding remarks

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.

Notes:

Title from publisher's bibliographic system (viewed on 05 Oct 2015).

Includes bibliographical references (p. [730]-732).

ISBN:

1-139-88202-3

1-107-38378-1

0-511-96086-7

0-511-88924-0

0-521-18475-4

1-107-39864-9

0-511-73520-0

1-107-39022-2

1-107-39501-1

OCLC:

776951260