[computer-go] Mega transposition table

[Nick Apperson]

This is a very good design in my opinion.  I was about to ask why you used
an index instead of a pointer until I saw that you were using a pointer
actually.  Using global data like this highlights one of the ways that C++
can blow away Java's requirement that everything must be allocated on the
heap.

On 1/19/07, Don Dailey <drd at mit.edu> wrote:
>
> On Fri, 2007-01-19 at 16:51 +0000, Eduardo Sabbatella wrote:
> > Sorry, I didn't understand the big table but It sounds
> > promissing. I don't understand how do you access to
> > different variations ... it seems like a merge-sort
> > array but not sure.
>
> It forms a tree in memory, but it's just a huge array of nodes.
>
> Each node has this:
>
>     move           - the move played from parent to get us here
>     visits         - number of times this node visited
>     score          - number of wins from this node
>     first_child    - index of node of first child
>     child_count    - number of legal moves from this position.
>
> (the move and child_count are 16 bits, everything else 32 bits,
> total structure size = 32 + 32 + 32 + 16 + 16 bits. = 128 bits. )
>
> if child_count == 0 the node has not yet been expanded.
>
> If first child is stored at index 1300, for example and there
> are 10 children, then
>
>      1300 - first child
>      1301 - second child
>      1302 - third child
>      ....    etc.
>
> first_child is actually a pointer in my implementation, but to
> make this explanation clearer you can think of it as an index
> into the global array.   In the example the pointer addresses
> array location 1300 .. in c ->  (node_t *) child = &(big_array[1300]);
>
> - Don
>
>
>
>
>
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070119/33b3bb39/attachment.htm