Re: [computer-go] Testing move generation and tree traversal

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Thu, Jan 13, 2005 at 10:11:43AM +0000, Peter McKenzie wrote:
> 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 :-)

I agree that it would be valuable to have such a thing for Go, but
note that the natural ways of making mistakes are probably distributed
differently in Go than in Chess.

Legal move generators and board updaters for Go seem pretty simple
compared to Chess. (I've written legal move generators for Go several
times, never for Chess, but Chess sure does look messier, not only
because of sheer number of behaviors but because of messy issues like
castling through check.) In Chess, I'd expect it to be relatively easy
to mess up the programming in some corner case even when you
understood the rules. In Go, I'd expect it to be more likely that an
error would reflect a simple misunderstanding of the rules, with
differences between rulesets (Chinese, Japanese, New Zealand...) being
the most likely cause of misunderstanding.

To support this theory, I have a story from my first computer Go
tournament. The computer tournament at the AGA Congress in Santa Fe
was run under Ing rules, which allow suicide. My program understood
that. Furthermore, its evaluation function had a bug which made it
think a suicide would be a good idea (in a reasonably ordinary
position, not one of the few weird positions where suicide really is a
good idea). So, my program made a suicide move, and by so doing blew
its opponent out of the water, since the opposing program was wired to
support a ruleset where suicide is illegal, and could not process the
suicide move or continue the game.

For me the funny part is that my program was by most reasonable
standards clearly the second weakest in a 5-program field. (I played
another game afterwards against the program which my program had
beaten by suicidal deviousness, and in that suicide-free game my
program was clearly stronger, especially at the end of the game;
conversely, I am under no illusions that my program was anywhere near
as strong as the other three programs.) The result of the tournament
(my program coming in 4th) turned out to reflect this, but it was only
by sheerest accident. My program's sneaky antibrilliancy happened to
come during its game against the one program it could beat fairly.
However, it turned out that many of its other opponents (all of them,
IIRC) would've been overpowered by the suicide trick. So if the bug
had shown up in any of the other three games instead, justice might
not have prevailed and I might've gone home with third place.:-|

So whether or not you get serious about testing in the perft style, be
careful with your ruleset(s). (And best of luck if you decide to get
serious with ko in the Ing ruleset.:-)

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
"Be liberal in what you accept, and conservative in what you send."
  -- Jon Postel, RFC 1122
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/