| |
KF5JRV > TECH 09.07.16 15:05l 26 Lines 1359 Bytes #999 (0) @ WW
BID : 5773_KF5JRV
Read: GUEST
Subj: Checker Solved
Path: IW8PGT<IZ3LSV<IQ2LB<IR2UFV<IR0UGN<CT2KCK<F1OYP<KQ0I<W9ABA<N9LYA<
N0KFQ<KF5JRV
Sent: 160709/1148Z 5773@KF5JRV.#NWAR.AR.USA.NA BPQK1.4.65
Checkers is "Solved"
Jonathan Schaeffer and his team at the University of Alberta announced on
April 29, 2007 that the game of checkers was "solved". Perfect play led to a
draw.
"The crucial part of Schaeffer's computer proof involved playing out every
possible endgame involving fewer than 10 pieces. The result is an endgame
database of 39 trillion positions. By contrast, there are only 19 different
opening moves in draughts. Schaeffer's proof shows that each of these leads to
a draw in the endgame database, providing neither player makes a mistake.
"Schaeffer was able to get his result by searching only a subset of board
positions rather than all of them, since some of them can be considered
equivalent. He carried out a mere 1014 calculations to complete the proof in
under two decades. 'This pushes the envelope as far as artificial intelligence
is concerned,' he says.
"At its peak, Schaeffer had 200 desktop computers working on the problem full
time, although in later years he reduced this to 50 or so. 'The problem is
such that if I made a mistake 10 years ago, all the work from then on would be
wrong,' says Schaeffer. 'So I've been fanatical about checking for errors.' "
Based on this proof, Schaeffer's checkers-playing program Chinook, could no
longer be beaten. The best an opponent could hope for is a draw.
Read previous mail | Read next mail
| |
