Content-Transfer-Encoding: 8Bit


help bot wrote:

I'm not sure why it is that so many people are having
difficulties in reading and understanding these articles;
to me, the use of "solved" to mean only partly solved
was not a big problem, though I think it was a very poor
choice of words.

I don't believe that they arrived at a partial solution.
I believe that they solved checkers.

These guys seem to have figured out the equivalent
of our very own endgame tablebases, for positions
with ten or fewer checkers on the board. Not a big
deal when you consider that each game starts with
over twice that many on.

To solve a game, you do NOT have to extend your
tablebase to the starting position. You can extend
the tablebase back and the opening book forward
until they meet.

Here are the facts:

Checkers (English draughts / American checkers rules) was
weakly solved (see definitions below) 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 are 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"


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/