DIMACS Discrete Mathematics Seminar


Tic-Tac-Toe-like games and randomness II


Joszef Beck
Rutgers University


Room 431, CoRE Building,
Busch Campus, Rutgers University.


4:30 PM
Tuesday, February 7, 1995


(Note: This seminar is a continuation of a talk given on January 24, which was an introduction and overview of the subject. The upcoming talk will be self-contained, and will provide details of one or more of the main results surveyed previously.)

Tic-Tac-Toe-like games is a large class of finite 2-player games with complete information and no chance moves. Randomness plays an auxiliary but crucial role in the theory. This is quite surprising since both the games and the optimal strategies are deterministic. How can randomness then enter the story? Well, this is what we call the ``random game principle", and it says in a nutshell that in many ``complex" games, the outcome between two perfect players is the same as the ``majority outcome" between two ``random generators". Warning: this doesn't mean at all that a random counter-play is effective against a clever opponent. We also mention two other principles: the ``neighborhood principle" and the ``fractional mirror image".

Document last modified on February 1, 1995