icon

Darwersi (a Darwinian Reversi)

Copyright © ; 1996-1999. All rights reserved.

Do you prefer to play Black or White?


Classic theme
screen shot

Other screen shot
of interface


Screenshot of Wood theme for Darwersi



Download it

At last, NEW 2.1(beta) release available. Download Darwersi.
It fixes the bug for windows version (see history) and improves the GUI.



Darwersi

Why this name?

Darwersi's AI (Artificial Intelligence) is the result of a darwinian evolution that has selected better and better brains (not mine smiley). Thus it is a DARWinian revERSI. See below for more details.

Version

This version (2.1) is an update of the 2.0 version (that fixes a nasty windows bug). If you like this new release... let us know! Next release is under development but we need to ear from you ! (mail us at I'll forward all messages to other contributors)

Why a new reversi?

This new reversi game implementation is not intended to challenge with world class ones (like Logistello). We are trying to make a new kind of reversi program that will become a valuable opponent (teacher?) for human players. We are planning to add features to help human to improve their reversi skills, like end game puzzles, openings study, move analysis with textual comments, various playing styles, adaptative strength, etc... But the prerequisite for this is a strong playing reversi program with all the basic features (well, and also some bugs).

Why this new version?

Previous release has been proven to be buggy smiley This version is a far much tough opponent (it climbed up to a 2300+ (8th) IOS score and will probably reach higher rank during next months).
Stephane Lavirotte (see links below) has made the new interface. It's coded in Tcl/TK and runs on unices and windows systems. MacOS version is planed but we need some help here...
Stephane made a really nice work isn't it? Especially if we consider he had to use Tcl and ... Windows smiley.
Between code and debug phases I made the new graphics with POV and hope they are easier to read than those of previous version. Some more themes are available (like a more classic B&W board).

Search method

Darwersi uses a refined alpha-beta search with dynamic search ordering and iterative deepening. Yves Lafon is the author of the variant used in this release. He made a nice work that improved in a significant way the think speed (ie: the strength) of Darwersi.

Darwersi uses a new exact end game solver. This means that end of game may be solved in a perfect way sooner in game (start it at 20 empty squares is ok, tournament versions are able to solve game perfectly at -24 or WLD at -26).

Darwersi is also able to think during opponents turn. This speed up answers (refutations). Thus you may play more and wait less.

Evaluation function

Evaluation function is based on these components:
  • number of stones (aka disc count)
  • number of playable squares (aka mobility)
  • potential mobility (aka frontier. That is the number of empty squares aside opponent stones)
  • parity (Who will put the last stone if no pass occurs)
  • edge pattern (pre-computed evaluation for each 10 squares edge+2X configuration in 8 phases of game)
  • corner pattern (10 squares on a triangle pined at corner plus one more diagonal square)
  • other patterns have been tried. Next version should use more and/or bigger ones.
  • the end search evaluation/ordering function uses a lot of small edge/parity corelated patterns.

All these components are incrementally updated to achieve a good depth of search (that needs a high grid per second ratio).

Mixing these values to obtain a single evaluation is done by a so called brain. A Darwersi brain is mainly a set of n*60 floats that weights these n strategic values during each 60 plies.
Manually tuning these amount of parameters is too tricky for an average player like me. Thus I used the oldest trick in the world: evolution! The default brain is the result of more than 1 000 000 generations of evolution (~3 000 000 000 games). At each generation a bunch of new born brains is generated by mutations of old ones and struggle for life runs until only a small set of brains survive. Then, a new generation starts over. This high cpu consuming algorithm runs (parallelized) on a virtual cluster of Dec, Sun and Linux boxes. The evolution master process sucked all the idle CPU on these computers by the mean of distributed slaves. This bunch of GFlops has been generoulsy donated to Darw by INRIA. This scheme seemed very promising to me when I thought of it, but tuning mutation factors, selection predicates and population figures is a tricky part.
Now you may understand this strange name Darwersi (darwinian reversi).

Implementation

First version of Darwersi had been coded in a hurry (54 hours if I trust XTimex), this one is a far much long run... my XTimeX says 400+ hours, but I must admit I spend a lot more time in brainstorms with other coders or in my bathtub thinking of new improvements smiley...
Its playing core (designed as a library) is 40 000 lines of C and has proven to be widely portable. It compiles on a variety of unices and windows.

Future developments

Darwersi is far from perfection. But now we are three to work on it!. Stephane is the GUI master and Yves is the alpha/beta guru. Thus we may expect to add new features at a higher rate.

At this time there is no more opening book. A new one is in progress and is based on a learning scheme. Thus in a near future Darwersi will nether make twice the same mistake smiley!
You may have noticed that Darwersi is not using selective search... MultiProbCut is one of our next goals, but current evaluation function does not fit well in this scheme... some more nights are obviously needed smiley!

Stephane is working on an IOS extension for interface that will allow you to play with other humans or programs on Internet Othello Server. This server is managed by Igor Šurdanovic and Michael Buro (respectivly authors of Kitty and Logistello programs). Logistello is probably the strongest othello player on earth and has just defeated the human World Champion: Takeshi Murakami. Thus, if you dare, IOS is offering you a nice collection of world class players.
BTW, Yves just made a neat hack to plug darwersi on IOS as a standalone robot.

In the next step we are thinking to add features to turn darwersi into a more "human like" opponent. Our goal is to provide the othello communauty with a good opponent that is also able to give sensible advices. I mean, not only choosing a move for you, but also explaining why a move seems to be the good one! Some other features like end game puzzles or classic openings study are planed too.

Well, I guess the list may be enlarged at will. But this is enough to show that coding a good reversi program is not an easy task.

I hope you'll enjoy playing with us.

Thanks

Thx to Stephane who made this new interface to the darwersi library.
Thx to Yves for the very cool brainstorming sessions on evolution tuning or search algorithms (take a look at his web-fortress). Thx to him also for the various works on alpha-beta (middle and lightning fast end-game).
Thx to Pierre and Patrick for the previous interface. They were working too hard to deal with this version but they put the first stones for current look and feel.
Thx to many other reversi coders... (including: Michael Buro, Igor Šurdanovitch, Olivier Casile, Ieuan Willis, Gunnar Andersson, and many more).
Thx to Wihem for her day to day help, some tricky bug fixes, and AIX, IRIX, HPUX ports.
Thx to all beta testers (including in no particular order: my father, philippe, wihem, colas, nicolas, yannis, stephane, yves and probably you smiley).

Friends links:

Name Email Adress Web Adress
Olivier Arsac Email Home page
Stéphane Lavirotte Email Home page
Yves Lafon Email Home page
Wihem Kherrati Email CV
Pierre Valentin Email Dreamtel home page
Patrick Ribault Email Dreamtel home page
Philippe Kaplan Email Home page
Colas Nahaboo Email Home page

More links:

A very complete othello guide from IIOA main page, a very good start point.

A text version of the IIOA FAQ is included (iiofaq.txt). It answers to a lot of good questions like:
What are the rules of the game?
Where did the game of Othello come from?
...

FFO, french page.

Others links with famous contributors to othello programming:
Michael Buro (Logistello).
Igor Šurdanovic (Kitty).
Martin Piotte and Louis Geoffroy (Brutus, Hannibal).
Gunnar Andersson (Zebra).
Mark G. Brockington (Keyano).



icon

Back to link page.

Back to my home page.