126 competition/games/othello.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
126 competition/games/othello.p
How good are computers at Othello?
competition/games/othello.s
("Othello" is a registered trademark of the Anjar Company Inc.)
As of 1992, the best Othello programs may have reached or surpassed the
best human players [2][3]. As early as 1980 Jonathon Cerf, then World
Othello Champion, remarked:
"In my opinion the top programs [...] are now equal (if not superior)
to the best human players." [1]
However, Othello's game theoretic value, unlike checkers, will likely
remain unknown for quite some time. Barring some unforeseen shortcut or
bankroll, a perfect Othello playing program would need to search in the
neighborhood of 50 plies. Today, even a general 30 ply search to end the
game, i.e. 30 remaining empty squares, is beyond reach.
Furthermore, the game of Othello does not lend itself to endgame database
techniques that have proven so effective in checkers, and in certain chess
endgames.
Progress of the best Othello computer programs:
1980
"Iago" (by Rosenbloom) [2]
1990
"Bill 3.0" (by Lee and Mahajan) [3] uses:
1. sophisticated searching and timing algorithms, e.g. iterative
deepening, hash/killer tables, zero-window search.
2. lookup tables to encode positional evaluation knowledge.
3. Bayesian learning for the evaluation function.
The average middle game search depth is 8 plies.
Exhaustive endgame search within tournament-play time constraints, is
usually possible with 13 to 15 empty squares remaining.
"Bill 3.0" defeated Brian Rose, the highest rated American Othello
player, by a score of 56-8.
1992
At the 4th AST Computer Olympiad [4][5], the top three programs were:
Othel du Nord (France)
Aida (The Netherlands)
Jacp'Oth (France)
References
----------
[1] Othello Quarterly 3(1) (1981) 12-16
[2] P.S. Rosenbloom, A World Championship-Level Othello Program,
"Artificial Intelligence" 19 (1982) 279-320
[3] Kai-Fu Lee and Sanjoy Mahajan, The Development of a World Class
Othello Program, "Artificial Intelligence" 43 (1990) 21-36
[4] D.M. Breuker and J. Gnodde, The AST 4th Computer Olympiad,
"International Computer Chess Association Journal 15-3 (1992) 152-153
[5] Jos Uiterwijk, The AST 4th Conference on Computer Games,
"International Computer Chess Association Journal 15-3 (1992) 158-161
Myron P. Souris
EDS/Unigraphics
St. Louis, Missouri
souris@ug.eds.com
Continue to:
My Books
