othello exact endgame solution

[sam krasnik]

many of the top othello AIs solve endgames exactly when there is a
given number of moves left. (like 20). i try to do the same thing, and
to speed up the evaluation function, i don't use any fancy variables
like mobility and frontier, but only win or loss (which is all i
really care about when solving an endgame), but i can't seem to search
deeper than 14 or so in the endgame, compared to others' 20 or 26.

what am i doing wrong? are there other optimizations i can use for
exact endgame solutions? do i for example need to use some form of the
principal variation search (will that help?) basically, any knowledge
or links to explanation and hints at exact endgame solution for
othello would be VERY appreciated!

--sam

[Linares]

You are not probably doing anything wrong. Ok, almost for sure your code
can be optimized so it can run faster. However, the point is, what algorithm
have you implemented man? If you have implemented a classical alpha-beta
then you are even lucky!! :) :) :) (many other programmers would have not
achieved such a depth of 14 or so).

Usually, during end games, programmers use to make use of a boolean version
of the alpha-beta algorithm which goes pretty fast. In this case you are NOT
interested in knowing how much pieces you will get at the end but on winning
so instead of searching game-trees with different integer (discrete) values
that have to be minimaxed when backed-up, you can consider you are exploring
a win-loss search tree where you only have true for winning and lose for losing
(the value of a draw depends upon you, man!). You do this consideration at depth
20 so you assure you will win the game. Then, at depth 14 you can maximize your
difference of stones on the board exploring the real game tree search.

Even if you try the classical alpha-beta with such a simplification, you will see
it goes faster (because more prunes will happen).

Finally, in order to get a depth equal to 20 or so, you have to implement
a specialized version of alpha-beta known as Scout (which is the boolean version
of the search algorithm known as PAlpha-beta); then, of course, you will have to
optimize your code as much as possible.

Though the pages have been written in spanish, you can find pseudocodes in english
in:

http://delicias.dia.fi.upm.es/proyectos/en-curso/monyca/codepab.html (PAlpha-beta)
http://delicias.dia.fi.upm.es/proyectos/en-curso/monyca/codes.html (Scout)

Play with these pseudocodes on a paper, before trying them in the computer so you
can finally get the general idea.

Hope all of this helps you, Sam!
 
 
 

-- 
Carlos Linares Lopez
Ground Systems Engineering Division
Payload Data Segment
ESRIN - European Space Agency
00044 Frascati
Italy

+39 06 94 180 527

 

[sam krasnik]

you seem to be very jovial...

yes, i have implemented an alpha-beta algorithm, and working on adding
transposition tables in conjunction with the MTD algorithm as an
improvement over negascout which seems to be used in most games these
days. i think part of my problem is that i DONT yet have full
transposition table support and a wide window alpha-beta.

--sam

[sam krasnik]

you seem to be very jovial...

[Richard Delorme]

sam krasnik wrote:

I have published a simple (but already fast) endgame solver for othello.
The code, in C language can be found here :

http://perso.club-internet.fr/abulmo/radoth/solver.htm

Here is a brief description of what is in :
* 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 & stablest 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.

I have found a few (but not important) bugs, or C language
inconstitencies in this code, so I am going to upload a new version
within a few weeks.

Another source (slower than mine) may be found here
ftp://ftp.nj.nec.com/pub/igord/IOS/src/Gunnar_improved_endgame.mail

The fastest endgame solver I am aware of is the one written by Gunnar
Anderson and can be downloaded here:

http://www.nada.kth.se/~gunnar/download2.html

Richard.