Re: computer-go: 5x5 Go is solved

[Erik van der Werf <E.vanderWerf@xxxxxxxxxxxxx>]

Close, but not exactly what I implemented in this version.

We do indeed use zorbrist, but not with 8 (or 16) keys computed all the
time. Instead just one key is calculated all the time without using any
symmetries. When checking for symmetries the keys for symmetrical
positions are (re)calculated only when needed. Naturally this takes
somewhat more computation time per symmetry lookup, but in many
positions we do not need to do it. In fact, since most of the
symmetrical positions occur more near the starting position (where also
the largest node reductions can be obtained) the hashes for symmetrical
positions are computed (and used) a number of plies away from the leafs
only. As a consequence multiple symmetrical positions can be stored in
the table which can all be used to narrow bounds on the score. 

I'm not sure if this approach is the best way to do it, but it was
pretty easy to implement and it seems to work quite well.

Erik.


PS Peter, when you talked to Jos we were considering the approach you
described, but at that time it was not implemented and I never tested it
in practice. I believe it works but I'm not sure of it's worth the
computational overhead near the leafs. I guess it depends on the type of
positions...


Peter McKenzie wrote:
> 
> Hello All,
> 
> I'm a Go & computer Go newbie so I don't know many of you, but I know a few
> through computer chess.
> 
> I think I can answer the question about symmetry because I asked Jos
> Uiterwijk about it after hearing Erik's talk in Maastricht this year.
> 
> They use a normal zobrist function, but calculate a hash key for each
> different symmetrical transformation of the position.  This gives N+1 hash
> keys including the original, where N = number of transformations.  Then
> select one of the keys, in a consistent way, for example always select the
> biggest one.  This means you will always select the same key whenever you
> reach any of the symmetrical positions.
> 
> When using the 'always select the biggest one' method, it would be important
> to use the lower bits of the key for indexing into the hash table otherwise
> you wouldn't get a very even distribution over the table :-)
> 
> cheers,
> Peter McKenzie
> 
> >
> > > Symmetry lookups in the Transposition table means that I check if a
> > > mirrored or rotated version of a position has already been examined. If
> > > this is the case the result can be re-used to narrow bounds, or directly
> > > return the score.
> >
> >I would be interested to know how you check for mirror / rotation in the
> >transposition table. Do you use Huima's hash function (which is broken)?
> >Another similar function? Do you store whole board position in the TT?
> >Do you maintain many hash value for the same board position (one for
> >every possible mirroring/rotation)? Or something else?
> >
> >Regards,
> >
> >     Antoine
> 
> _________________________________________________________________
> Unlimited Internet access for only $21.95/month.  Try MSN!
> http://resourcecenter.msn.com/access/plans/2monthsfree.asp