Game Theory and Chess

Game theory is a study of strategic decision making. More formally, it is "the study of mathematical models of conflict and cooperation between intelligent rational decision-makers". An alternative term suggested "as a more descriptive name for the discipline" is interactive decision theory. Game theory is mainly used in economics, political science, and psychology, as well as logic and biology. The subject first addressed zero sum games, such that one person's gains exactly equal net losses of the other participant(s). Today, however, game theory applies to a wide range of behavioral relations, and has developed into an umbrella term for the logical side of decision science, to include both human and non-humans, like computers.

Modern game theory began with the idea regarding the existence of mixed-strategy equilibria in two-person zero-sum games and its proof by John von Neumann. Von Neumann's original proof used Brouwer’s fixed-point theorum on continuous mappings into compact convex sets, which became a standard method in game theory and mathematical economics. His paper was followed by his 1944 book Theory of Games and Economic Behavior, with Oskar Morgenstern, which considered cooperative games of several players. The second edition of this book provided an axiomatic theory of expected utility, which allowed mathematical statisticians and economists to treat decision-making under uncertainty.

This theory was developed extensively in the 1950s by many scholars. Game theory was later explicitly applied to biology in the 1970s, although similar developments go back at least as far as the 1930s. Game theory has been widely recognized as an important tool in many fields. Eight game-theorists have won the Nobel Memorial Prize in Economic Sciences, and John Maynard Smith was awarded the Crafoord Prize for his application of game theory to biology.
  http://en.wikipedia.org/wiki/Game_theory

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

In game theory, Zermelo’s theorem, named after Ernst Zermelo, says that in any finite two-person game of perfect information in which the players move alternatingly and in which chance does not affect the decision making process, if the game cannot end in a draw, then one of the two players must have a winning strategy.

More formally, every finite extensive-form game exhibiting full information has a Nash erquilibrium that is discoverable by backward induction.. If every payoff is unique, for every player, this backward induction solution is unique.

Zermelo's paper, published in 1913, was originally published only in German. Ulrich Schwalbe and Paul Walker faithfully translated Zermelo's paper into English in 1997 and published the translation in the appendix to Zermelo and the Early History of Game Theory. Zermelo considers the class of two-person games without chance, where players have strictly opposing interests and where only a finite number of positions are possible. When applied to chess, Zermelo's Theorem states "either white can force a win, or black can force a win, or both sides can force at least a draw".
  http://en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theory)

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

What this means for chess –

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

November 27, 2013

The Formula that Would Destroy Chess Forever

By Georg Mathisen Editor's Note: This article was provided by our partner, ScienceNordic..
While Norway’s Magnus Carlsen and India’s Viswanathan Anand slug it out in the World Chess Championship, mathematicians are playing with a theory that would spoil the game and make these kinds of matches superfluous.

An ultimate recipe for victory exists. But nobody has discovered it yet.

Insufficient Computing Power
"Everyone agrees that if a computer were given X number of years, it would be able to calculate the ultimate way to win at chess. Or at least the ultimate way of averting a loss," says Kjetil Haugen. Hagen is vice-rector of Molde University College, a professor of logistics and sports management and an avid game theory enthusiast.

The claim is not new – in fact it is 100 years old in this year of the World Chess Championship. In 1913 the German mathematician Ernst Zermelo published what would come to be known as Zermelo’s theorem.
Briefly, the theorem says that in any finite two-person game involving alternating moves – where both players can follow every move and chance does not influence the decision-making process – a winning strategy exists.
The theorem has been interpreted in various ways through the decades.
"The main problem hindering the discovery of that formula involves the limits of computer power," says Haugen.

He explains that a chess game involves an unfathomable number of possible moves. With the world’s current hardware capacity, no such winning formula is likely to be found in the near future.
And do we really want to find a recipe for victory?
Tic-Tac-Toe to the Nth Degree
He compares chess to tic-tac-toe, also called noughts and crosses. It’s a simple game with nine squares in which whoever starts can be guaranteed at least a draw.

"This is why they don’t organise a world championship in tic-tac-toe. Chess is an overgrown version of it.
As a game it is structurally very similar, with two players taking alternating moves within a finite strategic space. But in reality they are far apart. The possible moves in chess are also finite, but the difference between them is an enormous order of magnitude."

Haugen is placing no bets on any math or computer genius at the Molde University College solving the chess formula once and for all.

The Rules a Neck Ahead
"I hope that doesn’t happen. For the sake of chess, and for all those who love chess," he says.

If the secret formula for determining the outcome of any game of chess were to be found, the game rules would have to be changed to keep ahead of the computational powers of machines. The ancient game would be altered to stay at least the neck of a knight ahead of technology.

Professor Kjetil Haugen admits that he doesn’t play chess. He prefers to watch soccer.

"That, too, is a thrilling game involving plenty of mathematics. Quite a lot about soccer has much in common with my work," he says with a smile.

Translated by Glenn Ostling.
http://www.realclearscience.com/articles/2013/11/27/the_formula_that_would_destroy_chess_forever_108379.html