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 <[EMAIL PROTECTED]> 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@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
