Zebra

Being a computer freak, I decided to start working seriously on an Othello playing program in June 1997. I decided to give the program the name "Zebra". I already had created such a program two years earlier, but its weak play made it necessary to discard almost all the old code. The program has since then improved a lot, and the only hopes I have of winning against it now is that I will discover some obscure search bug in the code... so when I do win against it, I know that there is some debugging to be done. Except for terribly buggy versions, I have never beaten Zebra. The closest I have come is a drawn position with 21 empty... which I (of course) failed to convert and lost 29-35 instead... bummer. Zebra is now strong enough that it is extremely unlikely that I get this close again; not that this is an overly strong statement - I get crushed by all strong human players as well...

A Windows version of Zebra can be downloaded from the download page. This is a joint project with Lars Ivansson who has created the GUI.

There is an Android version of Zebra written by Alex Kompel.

The Zebra source code is released under the GPL: Download (last updated on October 2, 2006)

Short facts

Opening book based on games between top players and self-play games, currently more than 500'000 positions. Learns from each game it plays.
Uses the search algorithms NegaScout and Multi Prob-Cut. A hash table of 2'000'000 entries (or more) is used during tournaments. Hash table information, move statistics and shallow searches are used for move ordering.
Evaluates positions using a pattern-based evaluation scheme. Each configuration of every
- row
- column
- diagonal of length 4-8
- edge + adjacent X-squares
- 3x3-corner
- 5x2-corner
has a value associated with it for each of 12 game stages. Linear interpolation is used between game stages. The pattern values are added together with a parity measure and estimates the final disk difference. To tune the values for the patterns (about 1'000'000 different when taking symmetries into account), a large over-determined linear system of equations was solved approximately using Fletcher-Reeves' conjugate gradient method.
Searches 18-27 moves in the midgame and 24-31 moves in the endgame in a normal game (2x15 minutes).
Usually runs on a Thunderbird / 1.33GHz / 1024MB under Windows 2000. On this hardware, Zebra typically searches 1'300'000-1'500'000 positions/second in the midgame and 4'000'000-7'000'000 positions/second in the endgame.
Consists of about 50'000 lines of C code and 1'000 lines of x86 assembly code (which can be replaced by equivalent C code on other platforms). Usually compiled with MinGW GCC .

History

June 3rd 1997: Created
IOS rating of 1500 after three weeks.
August 1997: Crude evaluation function and search algorithm working.
IOS rating: 1700
September 1997: All major program components working (opening book, hash table, endgame solver).
IOS rating: 1900
January 1998: New pattern-based evaluation function.
IOS rating: 2300
February 1998: Multi Prob-Cut and an improved opening book working.
IOS rating: 2400
March 1998: Selective endgame solver working; general speedup.
May 1998: Beat Hannibal, the strongest active program in the world, for the first time.
IOS rating: 2600
June 1998: Available as freeware for Windows 95.
IOS rating: 2650
October 1998: Finished 3rd in the "Princeton II" tournament.
Spring 1999: Search speed up, especially in the endgame.
Summer 1999: More knowledge added.
Fall 1999: Endgame speedup.
Spring 2001: Midgame speedup.

Performance

Zebra has played in some tournaments for computer programs. Here is how it has performed.

GGS open (April 2003) 3rd/12

GGS rand open (March 2003) 5th/16

GGS open (January 2003) 3rd/16

GGS rand open (December 2002) 3rd/19

GGS open (May 2002) 5th/10

GGS Tamenori theme (March 2002) 3rd-6th/13

GGS rand open (January 2002) 4th/15

IOS rand open (August 1999) 2nd-3rd/5

IOS open (May 1999) 3rd/8

Princeton II (October 1998) 3rd/13

IOS open (April 1998) 3rd/15

IOS open (February 1998) 2nd/15

Princeton I (October 1997) 13th/15

Things to work on

Rare board configurations in some cases are not evaluated correctly due to lack of example positions in the game database which was used for creating Zebra's knowledge. This problem can in part be solved by developing an interpolation scheme to fill the knowledge gaps, Mark Brockington solved this problem in his program Keyano by using a neural net.

Credits

Michael Buro: For raising computer Othello to swindling heights.

Jan C. de Graaf: For giving me lots of computer time and inspiration.

Igor Durdanovic: For writing the Internet Othello Server.

Lars Ivansson: For much feedback and many interesting games.

Yves Lafon: For providing a rival program to keep up with when I started working on Zebra.

Fabien Letouzey: For many exciting games between Zebra and Turtle.

David John Summers: For letting me incorporate his stability code (which improved performance in lopsided endgames) and many weird ideas.

Ieuan Willisfor sharing many of his ideas.

Not to forget the numerous people who have played Zebra and its kid brothers and/or given comments and suggestions (OO1, zardoz, reveil, kenta and several others).

Last modified July 18, 2011 by Gunnar Andersson

gunnar@radagast.se

GGS open (April 2003)	3rd/12
GGS rand open (March 2003)	5th/16
GGS open (January 2003)	3rd/16
GGS rand open (December 2002)	3rd/19
GGS open (May 2002)	5th/10
GGS Tamenori theme (March 2002)	3rd-6th/13
GGS rand open (January 2002)	4th/15
IOS rand open (August 1999)	2nd-3rd/5
IOS open (May 1999)	3rd/8
Princeton II (October 1998)	3rd/13
IOS open (April 1998)	3rd/15
IOS open (February 1998)	2nd/15
Princeton I (October 1997)	13th/15