[computer-go] How to improve Orego

[Łukasz Lew]

I really do randomize a whole vector of empty intersections before the playout.
When I get new empty intersection I just pick random place in vector,
move it to the end,
and use the place for new intersection.

Here is the code:

  void add_rnd (v::t v) {
    int ii;

    empty_v_cnt++;

    ii = pm::rand () % empty_v_cnt;         // TODO improve speed "%"
    tab[empty_v_cnt-1] = tab[ii];
    tab[ii] = v;
    assertc (mc_legal_ac, empty_v_cnt <= max_size*max_size);
  }

I play the playout until there are no more legal moves. I allow ko
recapture and large suicides. I have problem with signle stone
suicides.
So when one happens (I can only detect it by actually playing the
stone), I just take next empty intersection.

"Circular" reduces frequency of such wasteful events.
It means that I check next empty intersection in the vector starting
from the place I finished last time.

I hope this is clear now. If not, just ask :)

Lukasz Lew

On 12/6/06, Don Dailey <drd at mit.edu> wrote:
> On Mon, 2006-12-04 at 18:32 +0100, Łukasz Lew wrote:
> > I deal with eyes by randomizing list of empty intersections before the
> > playout, and while searching non-eye I go through them in circular
> > manner.
>
> What do you mean by circular and what does this have to do with eyes?
> I'm looking to speed my random player up a little bit more.   Here is
> what I've been doing for the last year or two:
>
> I collect all the empty intersections into an array and I randomize them
> as I go.   When a capture happens, it screws up your list - you must
> either add those intersections back to the pool of empty intersections
> or just reinitialize the list.   Right now I'm just reinitializing the
> list from scratch again - probably not the fastest way.
>
> I could of course randomize the list of empty intersections with a
> Fisher-Yates shuffle FIRST and then traverse the list in order till
> there is a capture but I think this is more work on the average because
> if you scramble a big list and the next move is a capture,  you have to
> rework the list anyway and randomize again.    I guess you might call
> what I do a "lazy" shuffle - you don't do the work unless you need to.
> (However, if I knew I would always need the whole list, it probably
> produces a little bit faster code to scramble them all at once in a
> tight little shuffle loop.)
>
> The actually procedure for "incremental randomization" is that I pick
> randomly from the empty list and then "fix the list back up" by swapping
> this out of the way with the first element in the list (which gets moved
> out of the picture because I bump up the "list start" pointer.)
>
> - Don
>
>
>
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>