## Ernst and the King: myths and facts about chess and game theory

Institute of Cybernetics

Wednesday, 8 April 2009, 14:00 (note the unusual weekday)

Cybernetica Bldg (Akadeemia tee 21), room B101

Slides from the talk [pdf]

**Abstract**: There is an urban legend circulating among chess
amateurs. The claim goes that, if White plays perfectly, then he/she
will win the game whatever the counter-game of Black may be---and that
such a fact can be proven mathematically. (Of course, no chess amateur
can give the purported proof.)

What is actually true, is that German mathematician Ernst Zermelo
stated in 1913 the first theorem of game theory. Rather than a "White
wins" statement, his paper gives necessary and sufficient conditions
for a position of the pieces on the checkboard to allow a win or a
draw for White, together with an upper bound on the maximum number of
moves a win may require. Zermelo's exquisitely non-constructive
argument applies to any two-player, zero-sum, perfect information
game; and, though the original proof was based on a controversial
argument, the main result has been reproved and improved by König
and Kalmar.

This talk, based on the 2001 article by Schwalbe and Walker, is
aimed at debunking the myth that "White always wins a perfect
game". This shall be accomplished by going through Zermelo's theorem,
and also by considering the counter-evidence arising from the computer
solution of the game of checkers in 2007.

Tarmo Uustalu

Last update 6.4.2009