Re: [computer-go] Bitmap Go revisited and mockup implementation

2009-08-25 Thread Antoine de Maricourt

Hi René,


Confession: I have not tested 19x19. As you have noted, and others 
before you over the years, a 19x19 board does not fit in one but three 
128-bit registers and there would be a rather big penalty as a result, 
perhaps (likely?) wiping out all of the benefits of bitmaps. Antoine 
voiced his disappointment about the speed advantage even on 9x9 in the 
e-mail to the list that served as my basis. My hope, as Hideko Kato 
points out, is in longer registers or perhaps being able to port this 
to a GPU. A 64-bit OS with twice the number registers would also 
surely help out. Nevertheless, I was surprised that I was able to get 
to almost the same level of speed as Libego provides.

As far as I remember, I was not disappointed by the speed itself on 9x9 
boards, but mainly with the following 2 points:

a) my feeling is that, as you say, it does not scale very well on 19x19 
(on current hardware).
I don't think other classical implementations suffer such a big 
penalty when scaling from 9x9 to 19x19.

b) I also felt that this kind of implementation was not very flexible.
For instance, I had another classical implementation, running at 
equivalent speed, but in which local 3x3 pattern matching was almost for 
free, as well as other more elaborated information.
When I started to think about introducing 3x3 local patterns in the 
bitmap only implementation, it was clear it would not be for free.

At that time, my conclusion was that if one only needs pure random play 
with no intelligence at all during playouts, then bitmap implementation 
could compete (at least on 9x9).
If one needs more elaborated knowledge (such as small patterns matching, 
or even knowledge about blocks of stones), then pure bitmap 
implementation is probably not so competitive.

I thus gave up with the idea and jumped to more promising ones.

Anyway, I'm glad my post has been usefull to you. And I encourage you to 
improve your implementation and let us know, especially if you have fun. 
Starting with something and playing with it is a good way to have new 
ideas, even if this makes your initial ones look less interesting a 
while after.

Best regards,


computer-go mailing list

Re: [computer-go] Zobrist hashing with easy transformation comparison

2007-02-11 Thread Antoine de Maricourt

Please do.
I will put it on a web page. But I need some time. My job keeps me very 
busy right now.

But I'm not sure I
will post the statistical analysis (it was almost ten hand writen pages,
and I'm not sure I still have them).

Have You performed an empirical test for collisions?
No, analysis was analytic. I've used the scheme in different ways, and 
since I knew were was the defect I put extra code to protect from the 
defect. This proved to be usefull... I was able to catch collisions at 
low rate in practice, but this rate would have been unacceptable if I 
had not been able to detect them.

The defect is as follow: if you have 2 different board configurations, 
the probability that they have the same hash key can be as low as 1/256 
(for a 64-bit key) if the difference between the 2 configurations has 
self symmetries. Anti Huima's scheme had the same defect, except the 
probability was 1. That's why I've been able to isolate it: I always had 
collisions between the same positions, and it didn't depend on the way 
random bits were generated.

computer-go mailing list

Re: [computer-go] Zobrist hashing with easy transformation comparison

2007-02-11 Thread Antoine de Maricourt

On 2/10/07, Łukasz Lew [EMAIL PROTECTED] wrote:

On 2/10/07, Antoine de Maricourt [EMAIL PROTECTED] wrote:
 If there is strong interest, I can post the scheme.
Please do.

Since Antoine claims there is only on solution I might as well post 
mine ;-)

mirroring: [abcdefgh] - [hgfedcba]
rotation: [abcdefgh] - [cdefghab]

This scheme follows trivially from dividing the square in 8 triangular
regions, and assigning each a letter. If you want to include color
symmetry you need to change the operators (xor doesn't work any more)
or increase the number of segments.


This is one out of the 3 possibilities that were left once we eliminated 
obvious defects (the ones the original proposal by Anti Huima suffered). 
However, if my analysis was right, this scheme was the one that 
introduces the biggest weakness in the key. That's why I didn't keep it.


computer-go mailing list

Re: [computer-go] Zobrist hashing with easy transformation comparison

2007-02-09 Thread Antoine de Maricourt


did you read Anti Huima's paper? The idea looks similar, but 
unfortunately it does not work. I provided a proof of the defect on this 
list (end of 2002 if I remember well). It's not that easy to get a 
working scheme. In fact there is only one combination with 8 chunks of 
data. In 2002 I exchanged a lot of email with Nici Schraudolph, and we 
found the right scheme. We wanted to write a paper, but we did not (it 
takes time, and I had not that much time - mathematic and computer go is 
just a hobby for me).

After having the right scheme, the tricky part is to perform a 
statistical analysis: unfortunately introducing constraints to deal with 
symetries weakens the hash key. The probability of collision becomes non 
uniform and depends on the board configuration. In short: if you take 
two different random board configurations, then the probability that 
they have the same key becomes higher if one of the configuration has 
self symetries.

If there is strong interest, I can post the scheme. But I'm not sure I 
will post the statistical analysis (it was almost ten hand writen pages, 
and I'm not sure I still have them).


computer-go mailing list

Re: [computer-go] GTK client OSX and Windows

2007-01-27 Thread Antoine de Maricourt

If you didn't start writing your client, and if you use C++, you might 
consider using wxwidgets.

It uses GTK under X11, and native UI system under Mac or Windows.

My understand is that there is a Mac port that doesn't need X11.

I'm hoping to do a viewing client in GTK and I would just need
someone to compile code I would write on these other platforms
and perhaps help me understand what changes to make if it doesn't
work 100 percent.

- Don

computer-go mailing list

Re: [computer-go] How to improve Orego

2006-12-07 Thread Antoine de Maricourt
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;
 if ((r  v)  n) return (r  v);
 r = 7;
 ... // 2 more times

Also it could be better to read the mask (v) from a table (provided the 
upper limit of n is small enough). At least on a P4, it will avoid a 
long data dependency chain and might give a (probably small) improvment. 
It might even be benefical on other processors.


On Thu, 2006-12-07 at 16:05 +0100, Łukasz Lew wrote:

ii = pm::rand () % empty_v_cnt; // TODO improve speed %

Try this,  I think it could be faster, not sure,  but has the advantage
that it's slightly more correct.

// returns an integer between 0 and n-1 inclusive
unsigned long randint(unsigned long n) 

  unsigned long   v =  n;
  unsigned long   r;

  v |= v  1;
  v |= v  2;
  v |= v  4;
  v |= v  8;
  v |= v  16;

  do  { r = rand(); } while ( (r  v) = n );

  return( r  v );

- Don

computer-go mailing list

computer-go mailing list