transposition table

["Serge Boisse STNA 7P (33) 562 14 5731" <boisse@xxxxxxxxxxxx>]

I'm currently working on a transposition table for a minmax local search of best
moves.
I found this greatly improves speed, but there are some tricky problems with Ko
: I need help to solve that !

Basically, a transposition table is a record of triples (board hash, best moves,
score).
Thus, wen the search engine found a position whose hash is already in the table,
it simply return the best Moves and scores found in the table without further
search.
I use Zorbrist hash algorithm with 64-bits hash values, this is extremely
efficient (almost no collision).

I tried to improve my transposition table by allowing it to detect board
symetries.
As you surely know, there are eight possible board symetries.
The idea is : I have a fonction that computes hash values for each of the eight
symetrics of the current Board position.
Then if one of these eight hashes matches an entry in the transposition table,
just return the record with "transposed" best moves (change coordinates of the
stone played according to symetry).

This works fine as long as  (super) Ko is not relevant for the position, (I
notice a great speed improvement), but  when Ko or super Ko is relevant, there
are several positions which are the same (thus same hash), but whose best moves
are not the same.
So I tried to use a couple (hash, move Number) as the Key for the hashtable I
use as transposition table.
It appears that it solves only a part of the problem :

Suppose we have the following game tree :
          A
          |
          B
        /   \
       C     D
       |     |
       F     G

where F and G are symetric position (let's say G is F rotated by 90 degrees) and
F is super Ko with B (same board position), while G is not.

Then F and G have same move number, are symetrics, but have not same score :
using a transposition table here would fail.
The problem is : suppose you use a depth-first search that encounters F before G
: you can still "mark" F in transposition table as using (super) Ko, so that
when you come to G, you'll know that you cannot use F record because the symetry
of G is not identity.
But if the search encounters G before F, G will not be marked, so when the
search comes to F, the algo thinks it can use record of G in transposition table
while this is wrong...

Furthermore, there are even more problems : transposition table can fail even if
there is no symetry stuff :
              A
            /   \
          B       H
        /   \     |
       C     D    I
       |     |    |
       F     G    J

Suppose you add a new branch that leads to a J node that is a identical to F,
but there is no super Ko because B is replaced by H in the past history of J :
then there F and J are same position at same move number, but their score and
best moves list  could differ !

How could a transpositon table handle such a tricky situation ?

Help !!


--
         ______________________
        / Let java be with me !\           \\\|///
        \______________________/ O       \\  ^ ^  //
                                   o o    (  @ @  )
 +--------------------------------------oOOo-(_)-oOOo----+
 |  Serge Boisse                                         |
 |  SERVICE TECHNIQUE DE LA NAVIGATION AERIENNE (STNA)   |
 |  PHIDIAS project, http://www.stna.dgac.fr/phidias     |
 |  tel: (33)562 14 5731                                 |
 |  mailto:boisse@xxxxxxxxxxxxxxxxx                           |
 |  homepage:  http://www.mygale.org/~boisse             |
 +-----------------------------------------------Oooo----+
                                         oooO   (   )
                                         (   )   ) /
                                          \ (   (_/
                                           \_)