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,
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 =
Yes, it's clear how you do it. I suspect this is better than what I
do. My list of intersections include ALL the intersections not just the
empty ones and use a fixed or static array. But this is all easy to
change.
I will give this a try at some point and let you know if it's faster.
-
If this randint routine is critical, you can save some calls to rand()
when you know that n is always below some value (see my previous post
about bitmap go).
For instance if n 128 (probably true for 9x9 go), you could try:
while (true) {
r = rand();
if ((r v) n) return (r v);
r = 7;
I'm pretty sure the time of this function is dominated by the call to
rand(), but it never occurred to do a table lookup for the mask,
interesting idea.
- Don
On Thu, 2006-12-07 at 22:36 +0100, Antoine de Maricourt wrote:
If this randint routine is critical, you can save some calls to rand()
By the way,
I'm amazed that the code for playing random games is fast enough that
getting random numbers is actually a bottleneck and it's worthy of a
discussion on optimization.
One of the fastest chess programs a few years ago in terms of nodes per
second was Fritz. It heavily used a common
So it's
quite possible that
this sequence dominates the call to rand().
on another note, if the only reason that you
need random numbers is to choose a number from
a list (82, or 362), and the depth is being
constrained to something reasonable, then what
you need is not a super-duper random
In the Orego paper the problem of selecting a move when the board is filled
with stones is mentioned. Orego uses a sort of double-hashing scheme.
But isn't it trivial to keep a list of empty intersections?
Before the MC-run is started, one builds up this list. If a stone is placed
now on the
It's not clear whether this is faster. Determining that a move is
illegal because the point is occupied is very fast; determining that
a move IS legal (i.e., not a suicide or ko violation) is the slow
part, and I avoid that by taking the first legal move I find. (Of
course, once all moves