[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Testing move generation and tree traversal
Hi Peter,
Ok, it turns out that I do test for KO inside the move make routine
and that would explain the discrepency.
My version is very slow because I'm doing state copies (see the code I
sent), which is very expensive in the case that the data
representation is simple. This version of my program was designed for
Palm handheld devices and uses super trivial representation of things.
The state copy hurts a great deal in this case. For instance, I copy
the whole board and then place the stone, you probably just update one
array element. (We both do some testing for capture/suicide which is
more expensive that simply placing the stone.)
I also expect you will take a big hit when you start updating a
zobrist key. This is a simple and fast operation if done
incrementally, but may still be expensive compared to what
little work is involved in placing a stone on the board in a program
with a very simple data representation and no evaluation.
Otherwise, we have proved that java really is at least 5X faster than
C and Vincent was even more wrong than we thought :-)
It's probably not worth the trouble, but one could get much deeper
searches if we allowed alpha/beta pruning. Here is how it could be
done deterministically:
1. Specify some cannonical move ordering
2. Specify exactly the evaluation function.
3. Specify the alpha/beta variant.
For instance:
1. Always sort moves in "ascii notation" order (A1 before B1, etc.)
2. Evaluation function always returns 0. (or some deterministice simple one.)
3. Use pure alpha/beta, no special aspiration techniques.
I once considered doing this for chess many years ago in order to
"freeze" a reference chess program in time. The idea was that it
would always be possible to exactly recreate a playing algorithm from
a precise specification. If that program could be benchmarked today
against humans, then in 50 years you could resurrect it and see how
much humans have improved. I had in mind specifying this to the
extent that any 2 implementations should match node counts and
evaluation at any depth. I would have kept the implementation very
simple (and thus much weaker than what would be possible) in order to
make it relatively simple to implement. Such a project would be a good
jumping off point for a better chess program since it would be easy to
verify correctness.
I eventually decided this would be more trouble than it would be
worth, but it was an interesting idea I thought at the time!
- Don
X-Sender: peter_mckenzie@xxxxxxxxxxxxxxxxx
From: "Peter McKenzie" <peter_mckenzie@xxxxxxxxxxxxxxxxx>
Date: Sat, 15 Jan 2005 03:07:56 +0000
>From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
<snip>
>You didn't report your boardsize==5 numbers except for the 7 ply case.
>
>Here is my 5 ply data:
>
>(Data for boarsize 5, 2.4 Pentium. Time given in seconds.)
>
> 1. No KO test.
> 2. No pass moves
> 3. Suicide illegal
>
>
>DEPTH TIME END NODES
>----- ------ ------------
> 1 0 25
> 2 0 600
> 3 0 13,800
> 4 0 303,424
> 5 4 6,368,416
> 6 94 127,124,176
Thanks Don, I get the same results.
I'm a bit confused by your 6 ply result though as you say 'no KO test' where
as I have implemented the ko rule in my program and get the same result as
you. Without the ko rule my result is 127,124,208. My other rules are the
same as yours namely no suicide and no passing. I don't have any superko
rule implemented either.
Here are my results for 5x5, run on a 1Ghz PIII (program written in Java).
Depth; Nodes at Depth; Total Nodes; Time
1; 25; 25; < 1s
2; 600; 625; < 1s
3; 13,800; 14,425; < 1s
4; 303,424; 317,849; < 1s
5; 6,368,416; 6,686,265; 3.4s
6; 127,124,176; 133,810,441; 63.3s
7; 2,411,088,112; 2,544,898,553; 1233s
8; 43,219,574,768; 45,764,473,321; 23821s
Note the need for a 64 bit counter :-)
Of course the time column is not so interesting as its not a speed test.
The purpose of the test is to verify correctness. Still, I'm happy enough
that my thing isn't too slow although it is very bare bones at the moment
(not even updating a hash key yet).
Is anyone able to verify the 7 and 8 ply numbers? In my experience (from
computer chess) you never regret building this type of test into your
program. It allows one to fearlessly optimise and refactor your program
safe in the knowledge that if you do introduce a bug it will be picked up
very quickly.
cheers,
Peter
>
>- Don
>
>
>
> Date: Thu, 13 Jan 2005 08:29:33 -0500
> From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
> CC: computer-go@xxxxxxxxxxxxxxxxx
> Reply-to: drd@xxxxxxxxxxxxxxxxx
> X-Spam-Score: -4.9
> X-Spam-Flag: NO
> X-Scanned-By: MIMEDefang 2.42
>
>
> Hi Peter,
>
> I did the test and came up with slightly different numbers. I thought
> I would report this before I check to see what I did wrong.
>
> As far as I can tell I'm not eliminating KO moves (which are not a
>factor
> anyway in this case) but not pass moves.
>
> depth: 1 count: 81
> depth: 2 count: 6,561
> depth: 3 count: 518,481
> depth: 4 count: 40,447,617
>
> You get:
> 81 ways of playing a 1ply game,
> 6,480 ways of playing a 2ply game,
> 511,920 ways of playing a 3ply game,
> 39,929,136 ways of playing a 4ply game,
> 3,074,496,080 ways of playing a 5 ply game.
>
>
> - Don
>
>
>
> int count_search( position *p, int depth )
> {
> int i;
> int mv;
> position tmp;
> int count = 0;
>
> if (depth == 0) return(0);
>
> for (i=0; i<valid_point_count; i++)
> {
> int x;
> int mv = valid_points[i];
>
> tmp = *p;
>
> x = make(&tmp, mv);
> if ( x >= 0 )
> {
> count++;
> count += xsearch( &tmp, depth -1 );
> }
> }
>
> return(count);
> }
>
>
>
> Hi All,
>
> In computer chess there is a thing called perft
> (http://homepages.caverock.net.nz/~peter/perft.htm) for testing the
>move
> generation and tree traversal functionality of a chess program.
>
> Has anyone done this in Go?
>
> I've been working on a Go program and would like to verify that my
>core code
> is working OK. It does incremental updating of chains etc so there
>is a
> fair chance of bugs :-)
>
> According to my program, for 9x9 Go, there are:
>
> 81 ways of playing a 1ply game,
> 6,480 ways of playing a 2ply game,
> 511,920 ways of playing a 3ply game,
> 39,929,136 ways of playing a 4ply game,
> 3,074,496,080 ways of playing a 5 ply game.
>
> Oh, that is excluding passing at all nodes. Maybe its a bad idea to
>exclude
> pass moves? But I thought it would make things simpler and it meant
>I
> didn't have to think about what to do after 2 consecutive passes.
>
> Similarly for 5x5 Go there are 2,411,088,112 ways of playing a 7ply
>game.
>
> Is anyone able to verify those numbers?
>
> cheers,
> Peter McKenzie
>
_________________________________________________________________
Listen to music online with the Xtra Broadband Channel
http://xtra.co.nz/broadband
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/