A recent XKCD comic charted the difficulty of various games for computers, from
Tic Tac Toe and
Nim being solved for all positions, to computers mastering the physical game of
Beirut and mental game of
chess (
the 2006 Deep Fritz vs Vladimir Kramnikin games, previously). There are other games that are basic on the face, but whose potentials for move combinations is so vast as to be beyond the scope of computers.
Marion Tinsley was the last great human checkers player, matching off against
Chinook in the last 6 games of his life, each ending in a draw (
previously).
Checkers was finally solved in 2007 (Google quickview;
original PDF), and is largest game that has been solved to date, at 8x8.
Solving Othello might be possible, if the decision tree were truncated, as
the 10x10 board game tree complexity is very huge.
The 19x19 Go board is is often noted as one of the primary reasons why a strong program is hard to create, though
some programs are
getting better at
optimizing move evaluations. More:
computerized gaming solutions previously, and
the Wikipedia page for solved games.
posted by filthy light thief
on Jan 11, 2012 -
57 comments
"It was my luck (perhaps my bad luck) to be the world chess champion during the critical years in which computers challenged, then surpassed, human chess players. [...] What if instead of human versus machine we played as partners? My brainchild saw the light of day in a match in 1998 in León, Spain, and we called it "Advanced Chess." Each player had a PC at hand running the chess software of his choice during the game. The idea was to create the highest level of chess ever played, a synthesis of the best of man and machine."
The Chess Master and the Computer: A article/book review on computer chess and the state of the top-level chess world by Garry Kasparov.
[more inside]
posted by painquale
on Jan 26, 2010 -
43 comments
For nearly two decades, fifty computers have been running day and night on an extremely complex problem. Today, scientists from the University of Alberta announced the result of all that work - they have
solved the game of checkers. Chinook, the computer program they developed, can never be beaten -
try for yourself. While checkers is the most complicated game to be solved so far, it is
not the only one. You can play a
perfect game of tic-tac-toe, of course, but also
connect four, and a 6x6 board of the game
othello. Chess players are already
thinking ahead to when their game is solved, with
Advanced Chess being Gary Kasparov's answer. The hardest game to completely solve might be Go, which
may not be solved until 2100.
posted by blahblahblah
on Jul 19, 2007 -
76 comments
Who was the most dominant athlete of all time? If athletes include
draughts players then
Marion Tinsley makes a good candidate, losing but 7 games plus 2 more to a computer over the course of a 45 year career. [more inside]
posted by Chuckly
on Dec 19, 2006 -
42 comments
