RE: computer-go: Super-Ko

["Mark Boon" <tesuji@xxxxxxxxx>]

> -----Original Message-----
> From: owner-computer-go@xxxxxxxxxxxxxxxxx
> [mailto:owner-computer-go@xxxxxxxxxxxxxxxxx]On Behalf Of John Tromp
> Sent: Friday, July 13, 2001 4:39 PM
> To: computer-go@xxxxxxxxxxxxxxxxx
> Subject: Re: computer-go: Super-Ko
>
>
> > About Super-Ko
> >
> > How much speed will it take out of a program,
> > if for every move the total numbers of stones actual on the
> board is counted and stores in an array,
> > and the Super-Ko is only checked with the prevous board
> position where the count of stones is equal to the present position ?
>
> That's still neither as simple nor as fast as looking up the
> current boardhash
> in a hashtable. E.g. in java you can just define a
>
>   HashSet oldboards = new HashSet();
>
> and a new move will violate superko if
>
>   oldboards.add(board.zobristHash()) == false
>
> (add() returns true if its argument is not already present)
> this will take constant time.
>

This is not strictly correct. Storing hashed values (and looking them up)
only takes constant time if no two hash-keys ever get mapped to the same
index in the hashtable. And for storing about 400 numbers and be reasonably
sure this will never happen, you'll need to pass an initial size to the
constructor of a million or so.

In complexity theory, looking something up in a hashtable is not considered
to be O(c), but O(sqrt(n)) where c is a constant and n is the number of keys
stored. In practise one can often exchange speed for storage space as is the
case here. But I wouldn't take a hashtable with less than several thousands
of entries in this case.

At a technical level, I wouldn't advise to use the implementation suggested
above anyway because it allocates a new object for each item added. Object
allocation is expensive and definitively not constant in time.