Re: transposition table

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

>

I'll reply to Dave ans jermy in a single mail.

Dave Dyer wrote :

> Perhaps I"m missing something, but I don't see how symmetric
> positions can be of much interest unless the positions are
> full board, and therefore can only be of interest when starting
> from an initially symmetric full board position.
>
> In almost all other circumstances, the the initial setup lacks symmetry,
> so the leaf nodes have no useful symmetries either.

Symetric positions are of great interrest in a  fuseki library, and also in
joseki because
you can interchange the four corners.
They are also interesting when you want to make a full minmax search of a whole
game (yes, this is possible only on very small boards, up to 4x4 I think :(  I
first encountered that a year ago, when testing my own program "Spirit Of Go"
... on a 2x2 Board.
Actually the 2x2 Board/goBan is incredibly complex to solve and can be solved
only when super Ko rule applies. The maximum depth for search is 80 ! By the
way  the result (black wins by 1) you can find in Mori's Go pages is correct

Jeremy Thorpe Wrote :

> there can never be a perfect solution to this problem if you want to
> account for super-ko, short of recording and hashing the entire game
> history.  here's why:
>
> there are plenty of reversible moves (even ones other than ko), so you can
> construct a game that goes any number of moves before (potentially)
> repeating, let's just say 10.  now, it's not only on the tenth move (when
> your move is restricted) that you have to start considering the
> implications of super-ko, you may want to have considered super-ko on,
> say, move 5.
>
I do agree with your reasonning but not with your conclusion.
Remember the key for my transposition table (TT) s not Board hash, but the pair
(board hash, move Number). So if position at move#10 is same as at move#5, and
super Ko applies at move#10, the transposition table would work because the key
for the two positions is not the same (they differ by move number).

It appears that using such a pair as keys instead of simply board hash does only
slightly increase the search time, because most transposed positions are at same
move number (for instance from a position P1 at move #5, play move black a1,
white c3,  black b2, white g6 giving position  P2 at move #9, or play black b2,
white c3, black a1, white g6, giving P3 at move #9, and P2=P3 if there are no
captures)

But as I pointed in my first post, having such a pair as a key for TT is not
enough because for instance in the tree from position P at move #5, you can have
one position P4 at move #9 being Ko with its parent at move #7, while another
position P5 at move #9 (in the same tree starting from P) can be identical to P4
but NOT being Ko with ist own parent at move #7. (I hope I'm clear).

So I think the solution is to add a Ko term to the records in TT, as P.J Leonard
suggested in his last post...

Any comment ?

--
         ______________________
        / 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   (   )
                                         (   )   ) /
                                          \ (   (_/
                                           \_)