Many Faces only has big nodes with all of the child statistics in one node, along with the totals for the position. Like the right hand of your diagram, but also with the 11/22 totals. There is no tree. All nodes are in a big transposition table and there are no child or parent pointers. I did this for performance (cache locality), and to avoid the complexity of having both a transposition table and a tree to maintain.
David > -----Original Message----- > From: Computer-go [mailto:[email protected]] On Behalf > Of Petr Baudis > Sent: Monday, October 26, 2015 10:56 AM > To: [email protected] > Subject: Re: [Computer-go] Understanding and implementing RAVE > > 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 _______________________________________________ Computer-go mailing list [email protected] http://computer-go.org/mailman/listinfo/computer-go
