Re: computer-go: Most simple Go rules

[Nick Wedd <nick@xxxxxxxxxxxxx>]

In message <20010625092030.B16165@rootless>, William Harold Newman
<william.newman@xxxxxxxxxxxxxxxxx> writes
>On Mon, Jun 25, 2001 at 09:58:58AM +0100, Nick Wedd wrote:
>> __ Standard ko rule, i.e. 2-cycles forbidden.
>>     Implementing superko is difficult.  Some of the programs at Dublin
>> will not be world leaders, they will be newcomers to CG.  I do not want
>> to make things difficult for them.
>
>In my experience, minimal support for superko is not very difficult to
>implement. Make some sort of reasonably wide hash (e.g. 64 bit Zobrist
>hash) of each board position. Maintain a collection of hashes of
>positions which have occurred so far in the game. Disallow moves which
>collide with previous hashes.

Do you need anything as clever as Zobrist hashing?  Can't you just hash
on the number of stones on the board, and then check for collisions?

>In a language with library support for sparse collections with
>efficient collision detection (e.g. C++, Java, Perl, Common Lisp..)
>this could be about two dozen lines of code. Maybe it's a little more
>if the language makes 64-bit arithmetic unwieldy (Java or Perl, maybe?
>I dunno).
>
>This is only a probabilistic algorithm, but at 64 bits of hash, I
>expect false collisions to be less likely than tripping over the power
>cord; and if that isn't safe enough for your tastes, you can make the
>error probability exponentially smaller by using a wider hash.
>
>How do you plan to deal with situations like triple ko without a
>superko rule? Do you have an alternative rule which is easier to
>implement than superko? Or do you just figure that triple ko is
>sufficiently uncommon that you don't need to worry about it in your
>tournament?

I plan to deal with triple-ko in the same way as it is dealt with in
human Go events in these islands.  Count it as half a win to each
player, and make the most of the opportunity for publicity!

Though your suggestion also has a publicity opportunity - "Why didn't
black play there, even a beginner would find that obvious?"  "Because it
thought it was illegal, its Zobrist hash collided."

Nick
-- 
Nick Wedd