Content-Transfer-Encoding: 8Bit


help bot wrote:

"Solved", to me, means that every legal position has a
known result, and that every legal move leads to another
position which has a known result, and every capture
yields a simpler position, with a known result.

That is just one definition of "solved."

NOT just having a computer which can't be beaten (like say,
Rybka).

Nobody that I know of has called anything like that "solved."

First, some definitions:

"Ultra-strongly solved" or means that there is an algorithm
which leads to a win for one player or a draw or a game that
goes on forever, against any possible moves by the opponent,
starting from any position, even ones that cannot be reached
from the initial position.

"Strongly solved" or "completely solved" means that there
is an algorithm which leads to a win for one player or a
draw or a game that goes on forever, against any possible
moves by the opponent, starting from any position that can
be reached from the initial position, even if one or both
players has already made one or more mistakes.

"Weakly solved" means that there is an algorithm which leads
to a win for one player or a draw or a game that goes on
forever, against any possible moves by the opponent, starting
from the initial position only.

"Ultra-weakly solved" means that it has been proven whether
the first player will win, lose, draw or play on forever,
against any possible moves by the opponent, starting from
the initial position only, but there is no algorithm telling
us how to do it. Typical proofs of this class are strategy
stealing arguments -- proving that if player two has a winning
strategy player one can always steal it. For example, change
chess to allow white to "pass" (make no move) or to swap
colors as his first move and chess is ultra-weakly solved:
If there is a forced or win for white, the first player
plays it. If there is a forced win for black, the first player
passes or swaps colors. Thus we know that the first player
can always draw or win, but we don't know how.

When the word "solved" is used without a qualifier, the
default assumption is "weakly solved"

Checkers (English draughts / American checkers rules was
weakly solved on April 29, 2007. The solution will be
published in an upcoming edition of _Science_ magazine.

Checkers solved:
http://www.cs.ualberta.ca/~chinook/
http://chinook.cs.ualberta.ca/users/chinook/index.html
http://www.cs.ualberta.ca/~chinook/p..._checkers.html
http://www.nature.com/news/2007/0707...070716-13.html
http://games.slashdot.org/article.pl.../07/19/1952211

Here is a link to GAMESMAN, a system developed for solving,
playing and analyzing two-person, abstract strategy games
such as Tic-Tac-Toe and Chess. Given the description of a
game as input, and sufficient resources/time, it claims to
generate a graphical application that will solve it (in the
strong sense), and then play it perfectly. (No promises
that "sufficient resources/time" is smaller than the number
of atoms in the universe or shorter than the age of the
universe, though!)
http://gamescrafters.berkeley.edu/

Here is a list of solved games, including Awari, Chess on 3x3
board, Chess with 6 or fewer men, Checkers, Chomp, Connect
Four, Dakon, Fanorona, Free Gomoku Hex, Go for board sizes
up to 5×5. Kalah, L Game, Magic Fingers, Maharajah and the
Sepoys, mnk-games, Nine Men's Morris, Pentominoes, Quarto,
Qubic, Reversi/Othello for board sizes up to 6×6, Free Renju,
Teeko, Three Men's Morris, and Tic-tac-toe.
http://en.wikipedia.org/wiki/Solved_game

--
Guy Macon
http://www.guymacon.com/

Interesting post Guy.

I liked this quote from the Nature article:
"People continued to run for sport after the invention of the automobile."
Ed Trice, games expert.

My gut feeling is that if the solution could be reduced to a book format
(small enough to not crush you when opening it), that would hurt the
popularity of the game a lot (like looking up a Rubik cube solution). There
is no functional difference in following the algorithm through a book or
watching it on screen in a silicon implementation, but I think there is a
still a mystery, a sense of an automata or a spirit in the box inside a
computer, but a book doesn't hold that.

Regards
RichardV