How good are computers at Othello?
competition/games/othello Added material
Problem
How good are computers at Othello?
Show solution
("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
Additional material
In article <3acdgl$9pl@usenet.INS.CWRU.Edu> axb52@po.cwru.edu writes:
>Are there any mathematical algorithms that can be used to win at
>Othello? What are some strategic laws that would ensure victory?
>I'm trying to write a program for the computer to play someone
>at Othello and actually win in a reasonable amount of time.
I notice that other people have already responded to this post with
some very good ideas...I think the best of them dealt with X, A, B, and
C squares around the edge of the board. This person didn't cite a
source, but this notion of edge stability is used, along with other
factors, in a couple of championship-playing Othello programs. Two of
the most commonly referenced programs are Iago (Rosenbloom, 1982) and
Bill (Lee and Mahajan, 1990). Bill beat the best American player in
1989 by a small margin...56-8.
The concept of edge stability is related to someone else's comment that
you need an algorithm which changes based on the board position.
Actually, you don't need a changing algorithm...you need an algorithm
which accounts for the fact that the strength of a certain square
depends on the state of the squares around it; this is what both Bill
and Iago did. The X, A, B, and C-type squares are taken directly from
Iago's and Bill's edge stability algorithm. If you want to know the
details, don't ask me...I could give you the algorithm without
explanation, or you could look it up in a reference.
The other major feature which both Iago and Bill used was the concept
of mobility, which other people had already mentioned. However,
someone indicated that the program should try to be *less* mobile at
the beginning and then let an exhaustive search take over at the end;
this is *not* what Iago and Bill did. They both aimed at always
increasing mobility (increasing the number of potential moves), even if
some of those moves weren't so hot.
Besides mobility and edge stability, you could always look for ways to
improve your searching mechanism. For example, you *could* use
exhaustive search near the end of the game. There are variations of
minimax search, however, which might help a little bit before then.
-- Michael Wolfe <wolfe@ils.nwu.edu>
Almost all the comments posted so far have been beginner level stuff.
That's the level I'm at also, but there's at least one book I've seen
that goes into Othello strategy at a much deeper level:
Othello: Brief & Basic, by Ted Landau
This is the official handbook of the US Othello Association.
-- Jeff Kenton <jkenton@world.std.com>
I can second that. Everybody interested in Othello should check out
the Internet Othello Server (IOS) at:
telnet faust.uni-paderborn.de 5000
There are lots of stuff and very strong programs.
-- Thomas K. Bischoff <bit@ten.ch>
[ Editor: postings of November 1994. ]