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

Silvio Capobianco

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