Re: [computer-go] symmetry optimizations vs statistics?
Perhaps this is also among the well-known material (or something
There have been discussions about handling symmetry in the past.
See for instance Heikki Levanto's group theoretic hashing paper.
For 'classic' (non MC) programs, board-symmetries were not important,
except for handling joseki/ fuseki collections: in a 'normal' game, the board
has no simmetries after a few moves, and there will
after that point *never* be a position that has one of its 15
mirror images present in the same gametree. So there is no need to check for
them,
because there is no possible gain.
MC is different, because it needs to re-evaluate the same
position many times, the even boardsize in Don's example
will make it even more pathological.
can be reached in multiple ways (a generalization of miai?), so counting
The miai-case is the topological variant of a symmetry.
Recognising these would need a whole different coding
('topological hashing' ?), and probably save a lot of
(wasted) effort in tsumego/semeai/endgame playing.
IMHO (I am not a statistician) not being aware of the symmetries
in MC (as in Don's case) just leads to wasted effort (and under-estimation of
the samples quality), but not to wrong results.
HTH,
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] symmetry optimizations vs statistics?
On Tue, Sep 30, 2008 at 04:29:12PM +0200, A van Kessel wrote: There have been discussions about handling symmetry in the past. See for instance Heikki Levanto's group theoretic hashing paper. I'm afraid you must have misattributed that - I don't know much about hashing, less about group theory, and not being in the academia, I am not publishing papers. I am just a programmer who likes to dabble with programming Go, when other interests don't claim all of my spare time. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] symmetry optimizations vs statistics?
Oops I confused you with Antti Huima. No offense... I meant: http://fragrieu.free.fr/zobrist.pdf Sorry, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] symmetry optimizations vs statistics?
Since statistics play such a vital role in modern Go engines, is there a danger that good old-fashioned low-level optimizations interfere with those statistics? Things like not re-evaluating symmetric positions (boar mirroring/rotation, move transposition, etc.) multiple times interacting with statistics based on number of evaluations. It seems that the keyword transpositions gives more useful search results in the list archives than just symmetries. There seem to be several issues, including: - if one uses hashing into a transposition table, one will simply be able to find and reuse results from earlier visits to similar positions via different paths; that might interfere with results that only exist as sums (eg, ownership maps/territory heuristic) stored higher up in the tree (boards resulting from playouts are added into a single higher-up array, then thrown away); the solution here is probably to keep more local data, but that could be expensive.. - if one uses transpositions to find all paths into the current position, one will be able to sample multiple simulations in one go; that might interfere with biases and confidence (giving more samples to positions that can be reached in multiple ways); the solution here is probably to be careful about the statistics, whatever that may mean;-) What I was wondering about was to what extent and with what results such interactions between statistical sampling and optimizing transpositions have been investigated. Is that any clearer? Claus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
