|
|
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
 ).
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
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 .
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 ...
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  !
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
!
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 ).
Friends links:-
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).
|
|
