[computer-go] Mega transposition table

[Nick Apperson]

I don't think Don was clear about whether he was using stack, heap or static
allocation of that structure.  I am just saying that it could be done in
such a way that any code anywhere can know where that object is without
having to pass around a pointer to the structure which is a really nice
feature in C/C++.  To do something like that in Java you have to contruct a
singleton or equivalent hack which is obviously slower and hacked design.
Of course the downside to having a global variable like that is that you can
only have one of those structures at a time, but for us that is likely to be
the case so it is worth making it static in my opinion.  It was really just
a side comment and the advantages of making it static aren't that big.

- Nick

On 1/19/07, Jim O'Flaherty, Jr. <jim_oflaherty_jr at yahoo.com> wrote:
>
>  Nick,
>
> I am not sure I follow.  Are you implying the following
> "...&(big_array[1300])" an strong indication that big_array is stack based,
> as opposed to heap based?  It is possible to do such a thing as stack based
> in Java, although quite uncustomary and require special start-up parameters
> to force a larger stack to accommodate something so large.
>
> However, my interpretation of Don's description and code had me assuming
> he was preallocating tons of heap space.  If my assumption is accurate, then
> I do the same thing in Java.  As for then interpreting the bits - I would do
> the identical mechanics as are done in C without any "new" operator using
> several different techniques depending upon whether this was a CPU or memory
> bottleneck.
>
>
> Don,
>
> So could you elaborate on where you are allocating space for big_array in
> your code snippet below?
>
>
> Jim
>
>
> Nick Apperson wrote:
>
> 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/
> >
>
> ------------------------------
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.orghttp://www.computer-go.org/mailman/listinfo/computer-go/
>
>
> _______________________________________________
> 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/5d6ceb25/attachment.htm