[computer-go] How to improve Orego

[Łukasz Lew]

Hi, here is an explanation along with the code:

First, my eyechecking is very fast:

  bool is_eyelike (color::t color, v::t v) {
    int diag_color_cnt[color::cnt];

    assertc (board_ac, is_ready ());

    if (((nbr_player_cnt[v] >> (color * 4)) & 0xf) != 4) {
      assertc (board_ac && slow_ac, slow_eyetest(color, v) != 4);
      return false;
    }
    assertc (board_ac && slow_ac, slow_eyetest(color, v) == 4);

    rep (c, color::cnt) diag_color_cnt[c] = 0;
    diag_color_cnt[color_at[v::NW (v)]]++;
    diag_color_cnt[color_at[v::NE (v)]]++;
    diag_color_cnt[color_at[v::SW (v)]]++;
    diag_color_cnt[color_at[v::SE (v)]]++;

    if (diag_color_cnt[color::edge] > 0)
diag_color_cnt[color::opponent(color)]++;
    if (diag_color_cnt[color::opponent(color)] >= 2) return false;
    return true;
  }

Basicly it's all about this condition
((nbr_player_cnt[v] >> (color * 4)) & 0xf) != 4

color is 0 (black) or 1(white) .
nbr_player_cnt[v] is two 4bit  counters in one int.
Updating it is fast, as I add 0x01 or 0x10 depending on new neighbour.
nbr_player_cnt[v] += (1 << (new_nbr_color * 4));

----

So I do not allow for self eye filling. What I did is I was generating
pass when I made full loop on my circular list (array), without
finding legal move.

What I do now (from yesterday), I move all rejected moves (for any of
the players) to "rejected" array. When the main list gets empty, I
just memcpy rejected onto main and try again. I generate pass if after
memcpy, no legal move is found. This improved 30.1 -> 33.3pps.

If I allow for only one memcpy, then sometimes
one-eye-only-no-other-liberties dead stones
remain after the playout, but there is no to much thrashing on the end
of the playout and I get 37 pps

Hope this helps.

Lukasz.

On 12/9/06, Don Dailey <drd at mit.edu> wrote:
> Lukasz,
>
> I have an implementation of your circular list in place, but I'm having
> a difficult time dealing with the single point eyes which my program
> does not allow as well as suicide which I don't allow either.
>
> I built a little circular list and I put captured points back into the
> circular
> list in random locations.   That part is fine.
>
> My implementation does not allow suicide or moves to certain kinds of 1
> point eyes.   When I reach those points in the list of empty
> intersections,  I cannot play them, but I cannot dismiss them either.
> They may be legal for the opponent and they may be legal later for the
> computer.
>
> Just for timing purposes I wanted to see what would happen if I just
> pushed those to the end of the list and continued until I tried all
> moves.   This is clearly not random but it does work.
>
> Unfortunately,  near the end of games I'm thrashing around in the list a
> lot and it's actually a slowdown.   There are too many unplayable moves
> that I have to skip over but I cannot dismiss them.   These moves
> dominate the list near the end of the game.
>
> The problem is more with the eyes than with suicide.   You solved the
> suicide problem by making it legal,  but I don't know how you solved the
> eye problem.
>
> I'm not sure what you are doing, but it sounds like you basically allow
> ANY move to an empty intersection except a single stone suicide, in
> which case you dismiss this intersection from the empty list forever.
> This would probably cause your loop to terminate before going to far
> even without an eye rule.
>
> But is this understanding correct?   Can you clarify?
>
> - Don
>
>
>
> On Thu, 2006-12-07 at 16:05 +0100, Łukasz Lew wrote:
> > 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/
> > >
>
>