On Mon, Oct 26, 2015 at 04:51:39PM +0000, Gonçalo Mendes Ferreira wrote:
> >I must admit that I don’t quite follow how you’ve implemented things, but
> >then you seem to be further along than me as I haven’t even started with
> >transposition tables.
> >
> >Urban
> >
> Well I took the liberty to steal and very crudely modify a MCTS diagram from
> wikipedia:
>
> http://pwp.net.ipl.pt/alunos.isel/35393/mcts.png
>
> Maybe with images it is clearer. You seem to be using an acyclic graph with
> pointers for the arcs.
Ah. In Pachi, at one point I wanted to rewrite things this way to get
awesome cache locality, but it was such a dull work that I gave up. :-)
So I wanted to do it when I was writing this again in Michi, but this
approach breaks encapsulation (you can't just pass around a node object
reference, but need a (parent, coord) tuple) which makes the code a bit
dense and clumsy, so I decided it's not very pedagogical to do it this
way...
> When you need to find transpositions, and free
> malloc'd nodes because you're out of memory, I find my solution much more
> practical because all the information for selecting what play to make is in
> the current node. But Pachi is no small program so I'm sure I'm wrong
> somewhere.
To clarify, Pachi and Michi do not use transposition tables but
a simple tree structure. Transpositions (and meaningfully explored
transpositions at that) are relatively rare in Go, plus there are
pitfalls when propagating updates, aren't there? OTOH having
a fixed-size list of followups carries some overhead when the board is
getting filled up. So I never bothered to do this; but I know that some
other strong programs do use transposition tables.
--
Petr Baudis
If you have good ideas, good data and fast computers,
you can do almost anything. -- Geoffrey Hinton
_______________________________________________
Computer-go mailing list
[email protected]
http://computer-go.org/mailman/listinfo/computer-go
