Computer solvability of games
Scott Donaldson
several games. Chess, go, and (to a lesser extent) checkers are not solvable.
But surely othello (reversi) has been solved by now ?
Any information ?
If this is the case, it would be interesting to hear if the othello
championships still take place: or has human interest just faded away.
The point of if-deep-thought-becomes-too-strong-will-human-interest-in-
chess-disappear has already been discussed in this group, but if
othello *is* solvable, and interest *has* faded away, the extention indicates
that there could be a practical answer to the DT question above.
**********************************************************
sdon...@cs.strath.ac.uk "Free the mind
------------------------ and you can achieve
Computer Science dream control"
University of Strathclyde
"I'm a computer scientist but I'm okay"
**********************************************************
Benjamin Sloss
>As a comparison part of my project I'm discussing the sovability of
>several games. Chess, go, and (to a lesser extent) checkers are not solvable.
The game turns out to be a draw. Further, the strongest checkers program
is close to being able to play a perfect game at normal time controls.
Anyone have any info to the contrary?
--
Ben Sloss Email: b...@osc.versant.com Work: (415) 329-7500 x172
Quote: "It's all fun and games until someone gets paid."
Transportation: '83 CB650SC (straight roads) '93 CBR 900RR (twisty roads)
'91 XR 250L (dirty roads) '87 Mustang 5.0 (wet roads)
Robert Hyatt
>As a comparison part of my project I'm discussing the sovability of
>several games. Chess, go, and (to a lesser extent) checkers are not solvable.
>But surely othello (reversi) has been solved by now ?
>Any information ?
>
>If this is the case, it would be interesting to hear if the othello
>championships still take place: or has human interest just faded away.
>
>The point of if-deep-thought-becomes-too-strong-will-human-interest-in-
>chess-disappear has already been discussed in this group, but if
>othello *is* solvable, and interest *has* faded away, the extention indicates
>that there could be a practical answer to the DT question above.
>
>
It hasn't either. There are 60*59*...*1 empty squares at each stage
of the game.... there are not that many legal moves since you can't
move to "any" empty square, but must reverse at least one of your
opponent's stones as well.
However, this number is sufficiently large that it hasn't been done
yet. We ran such a game on a Cray years ago (Cray Blitz modified
to play othello) and found that we could solve the game from
somewhere around move 21 (I forget exactly since we didn't think it
was that important). That still left the first 20 moves (ten by each
side) to play before we could figure out who would win. I believe
we were using 1 min for the time limit. As you can see, from the
root position, it is still a *big* search problem....
--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !
Robert Hyatt
>sdon...@cs.strath.ac.uk (Scott Donaldson) writes:
>>As a comparison part of my project I'm discussing the sovability of
>>several games. Chess, go, and (to a lesser extent) checkers are not solvable.
> On the contrary, I recall that someone 'solved' checkers over a year ago.
>The game turns out to be a draw. Further, the strongest checkers program
>is close to being able to play a perfect game at normal time controls.
>Anyone have any info to the contrary?
>
>>sdon...@cs.strath.ac.uk
>
Yes, and you are wrong. This seems to come up about once a year or
so. The last time Jonathan schaeffer responded and I am copying his
response below this.... maybe this will put to rest such rumors.
Chess, checkers, othello, go, etc. HAVE NOT BEEN SOLVED YET.... with
emphasis on the YET....
Subject: Re: checkers
Message-ID: <jonathan.726257357@maligne-lk>
Sender: ne...@cs.UAlberta.CA (News Administrator)
dcr...@uoft02.utoledo.edu writes:
>>>It is finished. They don't even work on the programs anymore as the maximum
>>>number of permitations is EASILY crunched by your average home PC.
Sorry, but I am reminded of a DMC quote from a previous article:
If you open your mouth, and make assertions you don't feel
you can back up, why do you make them in the first place?
>Please, a cite so I can do more research.
Some publications that might be available in your libraray on Chinook
include:
1. Jonathan Schaeffer, Joseph Culberson, Norman Treloar,
Brent Knight, Paul Lu and Duane Szafron, "A World
Championship Caliber Checkers Program", Artificial
Intelligence, Vol. 53, No. 2-3, 1992, pp. 273-290.
2. Jonathan Schaeffer, "Checkers: A Preview of What Will
Happen in Chess?", Journal of the International
Computer Chess Association, Vol. 14, No. 2, 1991, pp.
71-78.
3. Jonathan Schaeffer, Joseph Culberson, Norman Treloar,
Brent Knight, Paul Lu and Duane Szafron, Reviving the
Game of Checkers, in Heuristic Programming in
Artificial Intelligence; The Second Computer Olympiad,
D.N.L. Levy and D.F. Beal (ed.), Ellis Horwood, London,
1991, pp. 119-136.
4. Jonathan Schaeffer, Joseph Culberson, Norman Treloar,
Brent Knight, Paul Lu and Duane Szafron, "Checkers
Program to Challenge for World Championship", SIGART
Bulletin, Vol. 2, No. 2, 1991, pp. 3-5.
As well, there is a technical report describing the Chinook-Tinsley
match available by ftp from menaik.cs.ualberta.ca in the file
/usr/menaik/ftp/pub/TechReports/TR92-19/TR92-19.ps
Joel F Feinstein
>several games. Chess, go, and (to a lesser extent) checkers are not solvable.
>But surely othello (reversi) has been solved by now ?
>Any information ?
>If this is the case, it would be interesting to hear if the othello
>championships still take place: or has human interest just faded away.
Othello has by no means been solved! A game usually lasts 60 moves:
computers expect to play correctly with up to 20 moves remaining under
tournament conditions, and can analyze endgames with up to about
27 moves remaining overnight in simple cases. There is still a long
way to go!
Humans continue to play tournaments: every year there are National and
World Championships. But I would say that there are only about a hundred
serious players in Britain.
Joel Feinstein (British Othello Champion).
David Ebbo
>several games. Chess, go, and (to a lesser extent) checkers are not solvable.
>But surely othello (reversi) has been solved by now ?
>Any information ?
Othello is not as simplistic as you may think. It still hasn't been
solved and probably won't be for a very long time.
At the university of Waterloo, we have a yearly computer othello tournament,
and the interest is growing from year to year.
I believe the human player community is also a growing one. As far as I know
the level of play of the best programs is comparable to that of the best
human players (the current world champion is Japanese).
David Ebbo
Jonathan Schaeffer
>sdon...@cs.strath.ac.uk (Scott Donaldson) writes:
>>As a comparison part of my project I'm discussing the sovability of
>>several games. Chess, go, and (to a lesser extent) checkers are not solvable.
> On the contrary, I recall that someone 'solved' checkers over a year ago.
>The game turns out to be a draw. Further, the strongest checkers program
>is close to being able to play a perfect game at normal time controls.
>Anyone have any info to the contrary?
Checkers is solvable (5*10**20 positions) and NO, it has not been solved.
The best programs are capable of playing at the World-Championship level,
but the best player in the world is still human.
Paul Lu
>>As a comparison part of my project I'm discussing the sovability of
>>several games. Chess, go, and (to a lesser extent) checkers are not solvable.
>
> On the contrary, I recall that someone 'solved' checkers over a year ago.
>The game turns out to be a draw. Further, the strongest checkers program
>is close to being able to play a perfect game at normal time controls.
>Anyone have any info to the contrary?
Hi, I've been working as part of the Chinook (checkers) project. Our
long term goal is to solve the game of checkers, but it has NOT been
achieved yet. There is strong _empirical_ evidence that the game is
indeed a draw, but no proof as of yet (to my knowledge).
We won't make any serious attempts to solve the game until we have
completed the 8-piece endgame databases. We have done about 40% - 45%
of that to date.
And Chinook is far from perfect at normal (or otherwise) time
controls. Chinook plays a very strong game, arguably in the top 3 in
the world, but it makes its share of mistakes. Perfect play in
checkers is far more difficult than most people imagine.
Regards,
...Paul
Bryant Fujimoto
>As a comparison part of my project I'm discussing the sovability of
>several games. Chess, go, and (to a lesser extent) checkers are not solvable.
>But surely othello (reversi) has been solved by now ?
>Any information ?
I don't believe that othello has been solved. They are still holding
computer tournaments. Othello is discussed in rec.games.abstract so
you can ask for more info there.
Regards
Bryant Fujimoto
fuji...@denali.chem.washington.edu
Jeffrey C. Ely
|> In <11...@baird.cs.strath.ac.uk> sdon...@cs.strath.ac.uk (Scott Donaldson) writes:
|>
|> >As a comparison part of my project I'm discussing the sovability of
|> >several games. Chess, go, and (to a lesser extent) checkers are not solvable.
|> >But surely othello (reversi) has been solved by now ?
|>
|> What is meant by "solvable"? Decidable? I would have thought that
|> chess, having finite numbers of board positions and drawing rules
|> (50-move, 3-rep, insuff material) guarantees that you could,
|> theoretically, construct a tree of all possible games and "solve" it.
|> Granted, it is not "solved" and is unlikely to given the size of the
|> problem, but it is, in theory anyway, "solvable". Or am I
|> misunderstanding what is meant by solvable?
|> --
|> Rob Ryan
|> rr...@panix.com
uh oh.
+++++++++++++++++++++++++++++++++|+++++++++++++++++++++++++++++++++++++++++
Jeff Ely | "He said the Sun's not yellow...
Department of Economics | It's Chicken!"
UC Berkeley |
je...@econ.berkeley.edu |
Rob Ryan
>As a comparison part of my project I'm discussing the sovability of
>several games. Chess, go, and (to a lesser extent) checkers are not solvable.
>But surely othello (reversi) has been solved by now ?
Paul Hsieh
>As a comparison part of my project I'm discussing the sovability of
>several games. Chess, go, and (to a lesser extent) checkers are not solvable.
>But surely othello (reversi) has been solved by now ?
>Any information ?
It most certainly has not. Checkers is closer to being solved than Othello.
The checkers program Chinook can occasionally announce the outcome of the
game after only about 15 moves. The analogous thing in Othello has only
been done once (late last year the Othello program Aida solved a game for
a win after about 28 moves, but that position was so incredibly lopsided
that you could hardly expect such a solve to occur in real games with any
sort of regularity).
>If this is the case, it would be interesting to hear if the othello
>championships still take place: or has human interest just faded away.
Othello has never been more popular. Thousands of people play in Japan and
there is a world champioship tournament held the summer of every year. The
world championship is usually won by a Japanese, but last year Marc Tastet
from France won over David Shaman from the U.S. (though he was representing
England), with the Japanese champion not even making the semi-finals. For
more information I refrer you to the newsgroup rec.games.abstract where
there has been regular discussion about Othello and solvability of games.
>The point of if-deep-thought-becomes-too-strong-will-human-interest-in-
>chess-disappear has already been discussed in this group, but if
>othello *is* solvable, and interest *has* faded away, the extention indicates
>that there could be a practical answer to the DT question above.
The only semi-serious game that has ever been solved is Connect Four. The
game is a win for the first player after playing the center column. Even
though the game is obscure, I met a guy in Amsterdam a couple years ago who
still plays the game (and very well I might add). Some friends and I stayed
with him while touring the city and played some games with him. I informed
him the the game was solved but that did not seem to phase him as he put
forth the challenge the play Kasparov for the world championships in Connect
Four.
Not that that makes much of a point but I don't think that a computer world
champion in chess would stop people from playing. And I think this sentiment
is shared by many of the readers of rec.games.chess.
Paul (qed)
Benjamin Sloss
>92...@leland.Stanford.EDU (Benjamin Sloss) writes:
>>
>> [...] I recall that someone 'solved' checkers over a year ago.
>>The game turns out to be a draw.
>
>long term goal is to solve the game of checkers, but it has NOT been
>achieved yet. There is strong _empirical_ evidence that the game is
>indeed a draw, but no proof as of yet (to my knowledge).
>Regards,
> ...Paul
My apologies to all, I seem to have been mistaken. If the Chinook people
haven't heard of anyone searching the entire game, it seems a reasonable
assumption that it has not, in fact, been done.
I stand corrected.
Joseph Albert
>sdon...@cs.strath.ac.uk (Scott Donaldson) writes:
>
>>As a comparison part of my project I'm discussing the sovability of
>>several games. Chess, go, and (to a lesser extent) checkers are not solvable.
>>But surely othello (reversi) has been solved by now ?
>>Any information ?
well, for starters there is a big difference between a game being solvable
being solved. the former just means that there exists an algorithm
to generate the best move available from any position. the latter means
that you know what this algorithm is, or have one that approximates
it and runs in a reasonable amount of time.
so algorithms to solve, say, chess, might suffer from not know what the
algorithm is fully, while others might suffer from not running in a
reasonable amount if time. for example:
since there are a finite number of positions in these games, a trivial
algorithm to solve any of them is a table look up. you have a table of
every legal chess (or go, othello etc.) position, and the best move
from that position stored in the table. to generate a move, the algorithm
merely looks up the position in the table, and retrieves the move.
this algorithm, we don't know fully how to describe, since we don't
know what is the best move from every position.
similarly, there is a finite upper bound on the length of a chess game,
so if keeping a tree of every possible moves from a position, all possible
moves from the position obtained applying a moive to the original position
etc. will be a finite tree with leaves at points where the game ends.
the algorithm can use this strategy to generate the best move. however,
it will not run in reasonable time on today's hardware.
thus, chess, go, othello, reversi, checkers are all solvable.
Joseph Albert
alb...@hplabs.hp.com