Re: [computer-go] Bitmap Go revisited and mockup implementation
Hi René, David, 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, Antoine ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing with easy transformation comparison
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. Antoine ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing with easy transformation comparison
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. Erik 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. Antoine. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GTK client OSX and Windows
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 computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to improve Orego
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. Antoine 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 |= 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@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/