Register and play online chess>>>

Friday, December 22, 2006

Chess Mathematics and computers

Chess is interesting from the mathematical point of view; the number of legal positions in chess is estimated to be between 1043 and 1050, with a game-tree complexity of approximately 10123. The game-tree complexity of chess was first calculated by Claude Shannon as 10120, a number known as the "Shannon number". Typically an average position has thirty to forty possible moves, but there may be as few as zero (in the case of checkmate or stalemate) or as many as 218.

The most important mathematical challenge of chess is the development of algorithms which can play chess. The idea of creating a chess playing machine dates to the eighteenth century; around 1769, the chess playing automaton called The Turk became famous before being exposed as a hoax. Serious trials based on automatons, such as El Ajedrecista, were too complex and limited to be useful.

Since the advent of the digital computer in the 1950s, chess enthusiasts and computer engineers have built, with increasing degrees of seriousness and success, chess-playing machines and computer programs. The groundbreaking paper on computer chess, "Programming a Computer for Playing Chess", was published in 1950 by Shannon. About the future possibilities of newly-born computers, Shannon wrote:

The chess machine is an ideal one to start with, since: (1) the problem is sharply defined both in allowed operations (the moves) and in the ultimate goal (checkmate); (2) it is neither so simple as to be trivial nor too difficult for satisfactory solution; (3) chess is generally considered to require "thinking" for skilful play; a solution of this problem will force us either to admit the possibility of a mechanized thinking or to further restrict our concept of "thinking"; (4) the discrete structure of chess fits well into the digital nature of
modern computers.Shannon, Claude E. XXII. Programming a Computer for Playing Chess. Philosophical Magazine, Ser.7, Vol. 41, No. 314 - March 1950. Available online at (PDF).

The Association for Computing Machinery (ACM) held the first major chess tournament for computers, the North American Computer Chess Championship, in September 1970. Chess (Northwestern University)CHESS 3.0, a chess program from Northwestern University, won the championship. At first considered only a curiosity, the best chess enginechess playing programs, for example Rybka or Hydra (chess)Hydra, have become extremely strong. Nevertheless, from the point of view of artificial intelligence, chess-playing programs are relatively simple: they essentially explore huge numbers of potential future moves by both players and apply an evaluation function to the resulting positions.

Garry Kasparov, then ranked number one in the world, played a six-game match against International Business MachinesIBM's chess computer Deep Blue in February 1996. Deep Blue won the Deep Blue - Kasparov, 1996, Game 1first game, but Kasparov convincingly won the match by winning three games and drawing two. The six-game rematch in May 1997 was won by the machine (informally dubbed "Deeper Blue"), which was subsequently retired by IBM.

With huge databases of past games and high analytical ability, computers also help players to learn chess and prepare for matches. Additionally, Internet sites such as Free Internet Chess Server and Kurnik allow people to find and play opponents all over the world. It is estimated that more than 285 million people play chess via the internet today. The presence of computers and modern communication tools have also raised concerns regarding cheating during games, most notably the "FIDE World Chess Championship 2006#Bathroom controversybathroom controversy" during the 2006 World Championship.
Source wikipedia



Anonymous Anonymous said...

Chess played a special role in history of mathematics. Unlike games of chance, which attracted the attention of mathematicians from the 17th century onwards and led to the creation of probability theory, deterministic games like chess were ignored by mathematicians for two or three more centuries. The first theorem of game theory -- remarkably, about chess -- belongs to the famous set theorist Ernst Zermelo and was published in 1913 in his paper An application of set theory to the theory of chess. I state the result in its modern formulation; will the reader be surprised?

In the game of chess, at least one of the players has a strategy which assures that he either wins or, at least, never loses the game.

Of course, nowadays it is self-evident; but it was not so in the beginning of the 20th century, when, in the mass culture, chess
was assumed to be a psychological game, something like poker -- although Steinitz has already initiated a scientific approach to the game, building on earlier work by Philidor. Interestingly, Lasker, a prominent mathematician and one of the leading chess players of the beginning of 20th century, was much criticised for his "psychological" style of play.

If you are interested, you can find more on that in my book Mathematics under the Microscope

12/23/2006 2:46 AM  
Blogger Say No to Crack said...

I find it pretty interesting that chess is one of the few complex strategy games where computer algorithms have been developed to a point to be superior to the best humans. Look at Go as a comparison, a beginner at Go (like myself) can beat the world's best Go computers with very little difficulty.

12/24/2006 7:52 PM  
Blogger Allan Hanson said...

For a scholarly article I am writing, I am wondering about the amount of freedom of choice in the most complex chess-playing programs. If there is a given configuration of pieces on the board, will such a program invariably make the same move? Or might it make different moves, as a human player might, depending on matters such as tendencies toward falling into traps or other characteristics of the opponent that have been observed in prior moves?

Allan Hanson
Professor of Anthropology
University of Kansas

4/13/2007 6:49 PM  
Blogger johnhealy said...

In response to Prof. Hanson, I understand current commercial chess programmes to be deterministic for a given set of conditions (position, opening libraries, computer hardware, time...).

6/20/2007 8:49 AM  

Post a Comment

<< Home



Top 5 Chess Players
1. Ladydulac botslayercourage100courage70courage80courage90honourmerit20swisstournament16tournament4
2. Vlastous courage100courage70courage80courage90merit100merit20merit50swisstournament16tournament4
3. luca67 courage100courage70courage80courage90honourmerit100merit50tournament16tournament4
4. aksri65 courage100courage70courage80courage90honourswisstournament16tournament4
5. SergeyBabich merit20merit50tournament4merit100courage100courage90courage80courage70tournament16
Online Chess Links

Enter your email address:

Delivered by FeedBurner

Play Online Chess

If you have a website or a homepage, feel free to link to ChessManiac using these links: Play online chess

Online Chess Widget

RSS Reader
This widget is the staple of our platform. Read all your feeds right here with this one widget - Supported feeds are OPML, RSS, RDF, ATOM. Watch your favorite Podcast in the embedded Video Player on the Desktop or publish your own video playlist to your site for others to view!
Get this widget!

Daily Online Chess Puzzle