Pierre Dehornoy

Combinatorial game theory (after Berlekamp, Conway & Guy)

Pierre Dehornoy проведет 4 занятия

The goal of this course is to introduce some -- very interesting -- basic examples and notions of combinatorial game theory, following the book "How to win your mathematical games", by Berlekamp, Conway and Guy.

Combinatorial game theory deals with games with full information, and no luck. So, for every game there is a winning strategy, and to find one one can use the well-known idea of winning/losing positions. Though, it turns out that for some games often there is a very interesting and fine theory, with a lot of interesting ideas -- including those on which are nowadays based the best "Go"-playing programs.

1. Introduction to partizan games, ie games in which both players are allowed different moves. This first course is devoted to the game of Hackenbush, which is one of the simplest non-trivial game (presented here: http://mathworld.wolfram.com/Hackenbush.html). We will see how one can iteratively associate a number to a position, representing the advantage of a given player, and how this can be use to determine a winning strategy.
2. Nim-like games: in these games, both players have the same possible moves. We will see how one can (again!) associate numbers to positions and how one this helps to determine the winning strategy. We will also see how this induces very surprising rules of arithmetics!
3. Back to partizan games: we will encounter positions which have infinitely small values. These considerations lead to a natural extension of the rational numbers into the "surreal" numbers. This implies new unexpected rules of arithmetics.
4. Temperature theory. We will see the limits of the association of numbers and games: some positions can not be associated to a single real number! In order to evaluate these complicated "hot" positions, we will introduce temperature theory, and if time allows, how it helps in solving "kos" in the go game.

Organization Committee e-mail:
dubna@mccme.ru