Othello endgame search question
Daniel Lidström
I'm currently programming an endgame search module for othello. In othello,
as the number of discs increase, the number of moves decrease. This makes it
possible to compute the theoretical perfect result with ~20 discs left. To
do this one makes a call to the endgame search with alpha = -64 and beta =
64 (alphaBeta search). It is also possible to determine the winner only,
without the exact result. This is faster and is done with alpha = -1 and
beta = 1. It is good to first determine the WLD value and then proceed to
exact search. I am using hash table to store best moves. Now to my question:
how do I go from first searching WLD (win/loss/draw) to exact search? My
hash table will contain a lot of EXACT values that are exact only for WLD
and not the perfect search. I suspect it will be possible to change the
bounds in the hashtable to from lower and upper, depending on the score
perhaps.
Thanks!
--
Daniel Lidström
danli97(at)ite.mh.se
http://www.ite.mh.se/~danli97/
62 23' 25" N
17 15' 31" E
Steve Maughan
Surely after the WLD search the hash table should contain many bounds and
not exact scores (as you stated). The only exact scores should be for
positions that fall between Alpha and Beta i.e. draw. I guess you should
call WLD then adjust alpha and beta for most likely bound e.g. if white to
move and WLD gives fail high of +1 then research with Alpha=0 and Beta=+65
Steve
"Daniel Lidström" <dan...@NOSPAMite.mh.se> wrote in message
news:9vaf9q$q3e$1...@news.solace.mh.se...
Jean-Marc Alliot
You can have a look at Michael Buro's homepage
http://www.neci.nj.nec.com/homepages/mic/
His program (Logistello) is definitely the reference. I think it
currently solves endgames with ~24 discs left.
Your question looks related to the C* and the MTD(f) algorithm ;
There have also been publications on this subject by JC Weil (C*)
and Jonathan's Schaeffer's team (Aske Plaat among others if I remember
correctly).
Just pointers. My memory may be inaccurate.
--
| Jean-Marc Alliot |
| http://www.recherche.enac.fr/~alliot |
| all...@recherche.enac.fr |
Kenneth Sloan
> "Daniel Lidström" wrote:
>
> > Hi,
> >
> > I'm currently programming an endgame search module for othello. In othello,
> > as the number of discs increase, the number of moves decrease. This makes it
> > possible to compute the theoretical perfect result with ~20 discs left. To
> > do this one makes a call to the endgame search with alpha = -64 and beta =
> > 64 (alphaBeta search).
The values of alpha and beta have nothing to do with this. You search
to the end by...searching to the end. For example, my program sometimes
searches deeper and deeper until time runs out - and sometimes decides
to 'go for it"; to do that, you simply set the "search depth limit" to
some large value (easy to do in Othello).
> > It is also possible to determine the winner only,
> > without the exact result. This is faster and is done with alpha = -1 and
> > beta = 1.
Now *this* is seriously wrong. Again, alpha and beta have litte to do
with this. The common idea here is to use a DIFFERENT EVALUATION
FUNCTION. A typical Othello evaluation function will give more credit
for winning with a "plus 30" than winning with a "plus 1". If the
search cares about this, it can spend a lot of time finding the "biggest
win". If, instead, you evaluate all "wins" as identical, you will get
many more cutoffs, which means you can search more deeply at the same
cost.
> > It is good to first determine the WLD value and then proceed to
> > exact search. I am using hash table to store best moves. Now to my question:
> > how do I go from first searching WLD (win/loss/draw) to exact
search?
Change the evaulation function.
> > My
> > hash table will contain a lot of EXACT values that are exact only for WLD
> > and not the perfect search. I suspect it will be possible to change the
> > bounds in the hashtable to from lower and upper, depending on the score
> > perhaps.
> > Thanks!
You can try making the WLD values *close to* the exact values, and live
with some inaccuracy. You can purge the hash table when you switch
evaluation functions. You can add a bit to the hash table to indicate
whether the value is WLD or "exact" and evaulate the utility of
searching further when you are trying to find an "exact" value, but find
a WLD value instead.
The last strategy looks like it might allow for a smooth transition from
WLD to "exact". Except that (in my experience), if you have a WLD
result on one move it turns out to be easy to get an exact value on the
next move, without doing anything really special. The size of the tree
drops precipitously near the end of an Othello game.
--
Kenneth Sloan sl...@uab.edu
Computer and Information Sciences (205) 934-2213
University of Alabama at Birmingham FAX (205) 934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/info/faculty/sloan/
Daniel Lidström
> Jean-Marc Alliot <all...@recherche.enac.fr> writes:
>
> > "Daniel Lidström" wrote:
> >
> > > Hi,
> > >
> > > I'm currently programming an endgame search module for othello. In
othello,
> > > as the number of discs increase, the number of moves decrease. This
makes it
> > > possible to compute the theoretical perfect result with ~20 discs
left. To
> > > do this one makes a call to the endgame search with alpha = -64 and
beta =
> > > 64 (alphaBeta search).
>
> The values of alpha and beta have nothing to do with this. You search
> to the end by...searching to the end. For example, my program sometimes
> searches deeper and deeper until time runs out - and sometimes decides
> to 'go for it"; to do that, you simply set the "search depth limit" to
> some large value (easy to do in Othello).
Of course the endgame routine searches to the end, that is obvious, at least
to me.
> > > It is also possible to determine the winner only,
> > > without the exact result. This is faster and is done with alpha = -1
and
> > > beta = 1.
>
> Now *this* is seriously wrong. Again, alpha and beta have litte to do
> with this. The common idea here is to use a DIFFERENT EVALUATION
> FUNCTION. A typical Othello evaluation function will give more credit
> for winning with a "plus 30" than winning with a "plus 1". If the
> search cares about this, it can spend a lot of time finding the "biggest
> win". If, instead, you evaluate all "wins" as identical, you will get
> many more cutoffs, which means you can search more deeply at the same
> cost.
This is exactly what will happen if I call it with alpha and beta -1 and 1
respectively. And yes, the midgame evaluation function is not used to
evalutate terminal positions, only the disc count is used. How else do I
know the exact value? I am not seriously wrong, but right in every word!
Have you ever constructed a endgame search routine for Othello? If you have,
then you'll know what I'm talking about. Anyway, to qualify for any further
discussing, I suggest you browse through this sample endgame code:
ftp://ftp.nj.nec.com/pub/igord/IOS/src/endgame.c
I have done this:
when I search for WLD (alpha=-1, beta=+1) I don't set any entries to EXACT,
instead, when I find a value <= -1 I set the value to LOWER_BOUND and if it
is >= +1 I set it to UPPER_BOUND (using common transposition terminology).
The same routine is used to search for the exact value, and this seems to
work.
/Daniel
Fabien Letouzey
Sorry all for spamming a chess programming newsgroup with Othello stuff ;)
Daniel, you said:
> I'm currently programming an endgame search module for othello. In othello,
> as the number of discs increase, the number of moves decrease. This makes it
> possible to compute the theoretical perfect result with ~20 discs left. To
> do this one makes a call to the endgame search with alpha = -64 and beta =
> 64 (alphaBeta search). It is also possible to determine the winner only,
> without the exact result. This is faster and is done with alpha = -1 and
> beta = 1. It is good to first determine the WLD value and then proceed to
> exact search.
I totally agree with all this, this is used in all Othello programs I know,
including mine (Snail and Turtle, with source code available at
http://www.lifl.fr/~letouzey/).
Steve answered you:
> Surely after the WLD search the hash table should contain many bounds and
> not exact scores (as you stated). The only exact scores should be for
> positions that fall between Alpha and Beta i.e. draw. I guess you should
> call WLD then adjust alpha and beta for most likely bound e.g. if white to
> move and WLD gives fail high of +1 then research with Alpha=0 and Beta=+65
This is absolutely correct. There is no need to do anything special in
the transposition table between WLD and FULL search (you can even use many
intermediate searches). If you obtain incorrect results, that means you
are doing something wrong, probably while storing the values in the table.
Do you have actual problems or where you just wondering if you needed any
extra-computation?
Fabien Letouzey.
Daniel Lidström
I think I might have been doing something wrong when storing the EXACT
value. Of course it should only be stored when finding a draw (WLD). Thanks!
Now if that is working, perhaps you can tell me how to do WLD at 24 empties!
:)
/Daniel
Fabien Letouzey
Aha, this is not easy ;) There is little documentation (online or not) about
fast Othello endgame search, but there is source code ...
Gunnar Andersson is a specialist of that topic; you can have a look at
his WEB page: http://www.nada.kth.se/~gunnar/othello.html.
He is probably subscribed to this newsgroup anyway.
I suggest that you experiment with the fastest-first heuristic if you
don't know it already:
in a given position, try first moves that make the opponent mobility low
(nodes that have the fewest number of children).
Of course it's a bad idea to use this too deep in the tree.
Note that this heuristic is related to ideas in PN-search and some others.
There is also a simple heuristic I'm using in my Palm program PilOth:
try first moves that are "totally surrounded" by discs.
It is a very simplified view of parity, yet seems to help a lot ...
Good luck with your experiments,
Fabien Letouzey.
Richard Delorme
othello,
> as the number of discs increase, the number of moves decrease. This makes
it
> possible to compute the theoretical perfect result with ~20 discs left. To
> do this one makes a call to the endgame search with alpha = -64 and beta =
> 64 (alphaBeta search). It is also possible to determine the winner only,
> without the exact result. This is faster and is done with alpha = -1 and
> beta = 1. It is good to first determine the WLD value and then proceed to
> exact search. I am using hash table to store best moves. Now to my
question:
> how do I go from first searching WLD (win/loss/draw) to exact search? My
> hash table will contain a lot of EXACT values that are exact only for WLD
> and not the perfect search. I suspect it will be possible to change the
> bounds in the hashtable to from lower and upper, depending on the score
> perhaps.
> Thanks!
I just publish a source code for an endgame solver at
http://perso.club-internet.fr/abulmo/radoth/solver.htm
Some features:
- Fast (due to inlining and loop-unrolling) move generators.
- Principal Variation Search (an enhanced alphabeta).
- Move sorting according to the type of the squares.
- Move sorting to play fastest and most stable lines first.
- An hash table used to:
. anticipate cutoff of present level (if position is stored).
. anticipate cutoff of the next level (enhanced transposition
cutoff).
. replay known bestmove first.
Richard.
PS: Daniel, the source available here is more recent (and slightly better)
than the one I sent to you.