Robotics Reference
In-Depth Information
for the program to achieve is Schaeffer's goal, solving the game. As of
January 2005 the Edmonton group had completed the compilation of
all databases up to nine pieces: roughly 4.5 trillion positions. Of the ten-
piece database, five pieces against five pieces and six pieces versus four had
been completed (22.8 trillion positions). The total size of the databases
at that time was 30 trillion positions and counting, as a result of which
Chinook had already proved that one of the most popular openings in
Checkers, known as the White Doctor, is a draw with perfect play. 23
Using Databases to Solve Other Games
Once the power of endgame databases was demonstrated in Chess and
Checkers it was not long before programmers in other game domains
jumped on the bandwagon. Some classic strategy games have already
been solved using this approach. As computers become faster and ac-
quire more memory, so it will become easier for programmers to develop
databases for games that are currently beyond solution. Within the next
two decades I would certainly expect Xiang-Qi (Chinese Chess, with
10 45 possible positions) and Dames (Checkers on a 10 x 10 board, with
10 35 positions) to be solved, amongst others. The games that have already
succumbed to databases include Connect-4 TM , Nine Men's Morris and
Awari.
Connect-4 TM , which is also known as four-in-a-row, is marketed
by Milton Bradley. The game is played on a vertical array with seven
columns and six rows. The players take turns to drop coloured discs into
whichever of the columns they choose, provided that it is not already
full. A disc once dropped then occupies the lowest vacant square in that
column. The game is won by the player who first completes an unbro-
ken line, vertical, horizontal or diagonal, of four of his own coloured
discs. If neither player can achieve this goal then the game is a draw.
The number of possible positions in Connect-4 is approximately 10 14 ,
one five-millionth of the number for Checkers. The game was solved, at
about the same time but working independently, by Victor Allis in the
Netherlands and James Allen in the U.S.A. With correct play the game
is a win for the first player, who should start by dropping a disc in the
central column. Against all other opening moves the second player can
draw with correct play.
23 At that time two more openings were almost solved, with 173 still to be addressed.
Search WWH ::




Custom Search