[computer-go] a few more questions

[Álvaro Begué]

On Tue, May 13, 2008 at 8:10 PM, Weston Markham
<weston.markham at gmail.com> wrote:
> On Tue, May 13, 2008 at 7:08 PM, Gunnar Farnebäck <gunnar at lysator.liu.se> wrote:
>  >  And I agree, don't even think of doing this with floating point
>  >  numbers.
>
>  This is a bit tangential to computer go.  But you have piqued my curiosity....
>
>  Offhand, that sounds rather extreme to me.  Perhaps I haven't really
>  thought this through completely, but it seems as if there is a simple
>  modification to the stated algorithm, that would ensure that it works
>  fine with floating point numbers.  Or at least well enough for any
>  conceivable purpose:
>
>  Make sure that you select each random number from a slightly larger
>  range than prescribed by the exact totals.  (For example, always round
>  up while calculating the totals.  If you do not have control over the
>  rounding mode, just add on some small fraction of the largest weight.)
>   Then, in the event that subtracting the weights of the
>  points/rows/buckets never reduced the selected number to a
>  non-positive value, just select a new random number and start over.
>
>  Would this work fine, or is there some flaw in my thinking that Álvaro
>  and Gunnar have already considered?

John Tromp and I spent quite a bit of time patching the floating-point
implementation and hunting down the subsequent bugs. I am not saying
that making it robust is impossible, but I ended up so frustrated that
I don't think I will ever try again. Integers are much better behaved
and are sufficient for everything we wanted to do.

As to the optimal branching factor for the tree (assuming there are
many many leaves), I believe it's n=3, if all you care about is
picking random points fast.

Outline of the proof:
  On a particular level of the tree you will make about n/2
comparisons before you pick your branch and descend. The number of
leaves is l = pow(n,k), so the number of levels is k = log(l)/log(n).
The total number of comparisons will be something like
(log(l)/2)*(n/log(n)). The first part is fixed, so we need to minimize
n/log(n). That function reaches its minimum at n=e, but unfortunately
n has to be an integer value. Among the integers, n=3 is the best,
with n=2 and n=4 tied at as close seconds.

Of course, in practice you will also need to do updates to the weights
(actually more often than picking random points), so the number of
levels in the tree becomes more relevant, which favors larger values
of n. My original implementation had n=2 and the tree was beautifully
implemented as an array, in the same style as the usual implementation
of a heap. However, Rémi pointer out that cheaper updates were
important. I think the two-level solution using rows is easy to
implement and probably close to optimal.


Álvaro.