I have been working on an Othello program for some time now. I used to be proud of a 5ply beta search using the no. of stones as a heuristic. I kept being proud through the first game against another Othello program, up until the last moves. My program was clearly winning (I had lots and lots of stones), until the predictable and unfortunate ending. It''s playing power went up tenfolds when I added the corners heuristics (corners are _very_ good, pieces next to the corner are bad). I started to be able to beat one other program (Daisy Reversi), but I still took serious beatings from Magic Reversi and from Deep Green Reversi. Then I added the edge heuristic (precalculate edge winner using the probabilistic expectimax algorithm). At this point the program won against both Magic and Deep Green, with only a 4ply search against their 7ply search. After I improved the search algorithm (turned the beta test into a real alpha-beta window test and improved the move ordering), I was able to do 7ply searches and thought I had a really strong program.

Enter stage Edge Reversi and the infamous Zebra. Thanks to it''s advanced search algorithms (transposition tables, multi-prob cut and who knows what else) Zebra can easily do 16ply searches, which is enough to bury my program into the ground. Turns out that thanks to a multipe pattern heuristic (among other things) , Zebra could beat my program (with all the glory of a 7ply search) without searching at all or using it''s opening book. It didn''t even care that it lost corners.

Edge Reversi is a lighter program, and made a good sparring partner for a while. It is a lot faster than my program at the same search depth, but I was able to tweak my evaluation function until the two programs are roughly equal at the same search depth (with an advantage for Edge Reversi).

After this I enjoyed a crushing victory against the Zebra program (stripped of it''s opening book and using a 1ply depth search - only heuristic) and a minor victory against a 2ply search Zebra.

The point is that while the search depth is important, the most significant advances were always knowledge based. In fact, the search itself depends heavily on the knowledge based heuristics, and deep searches need good heuristics to throw away bad choices early and focus on good choices.

Hey thanks Diodor - that was most informative (and also a good read - what other stuff have you done?).

One question : how does Zebra fare against humans using only its evaluation routine?

I've done a go-moku (connect five) program that was so bad I had to erase about 800 lines of heuristics and start all over (I'm working on it now)

For what it's worth (I'm not much of a player), my program used to beat me even before the edge pattern heuristics, so...

You can search Victor Allis's "Connect 4: a knowledge based approach" paper for another example of knowledge vs. search.

[EDIT] Link: ftp://ftp.cs.vu.nl/pub/victor/connect4.ps

[edited by - Diodor on October 21, 2002 9:09:42 AM]