Re: [pbmserv-dev] proposed ko algorithm for pbmserv go

[Richard Rognlie <rrognlie@gamerz.net>]

On Fri, Sep 05, 2003 at 06:18:36PM -0700, Scott Huddleston wrote:
> Well, after my shock at realizing pmbserv go has no ko detection I'll
> try to do something about it.
> 
> First:  confirming the general ko rule.  Is it that no exact position
> should ever be repeated?

The "simple" Ko rule is that no move is made to recreate a prior board
position (as of 2 moves ago).

This prevents the simple

    . o x .       . o x .       . o x . 
    o . o x  ==>  o X . x  ==>  o . O x 
    . o x .       . o x .       . o x . 


However, there is a more general "super" Ko rule which states that no 
move can be made such as to recreate a prior board state.

And it's important that "state" is not only the positions
of the stones on the board.  But also who's turn it is.

While I'm hard pressed to come up with an example, it is conceivable
(through some string of moves) that I make a move that recreates the
positions of the stones on the board... but in the prior instance,
it was my move next... and this this instance, it is my opponent's
turn.   And if that's the case, it's a legal move.


> Second:  here's a proposed algorithm I think is pretty simple in concept:
> 
> Maintain a "ko position list" for go games which are board positions
> that might potentially be repeated in a ko situation.  Usually the
> list will be empty.  Maintain the ko position list as follows
> (C pseudo-code):
> 
> -----------------------------------------------------------------------
> 
> if (submitted move would duplicate a board in the ko position list) {
>    forbid the move as a ko violation;
>    wrapup and terminate rejected move processing;
> }
> 
> 
> if ( (move captures 0 or 2+ stones)
>    OR (move before capture has any liberties or friendly stones as
>        neighbors)
>    )
> {
>    clear the ko position list;
> } else {
>    add the position before the move to the ko position list;
> };
> 
> 
> make the move;
> 
> -----------------------------------------------------------------------
> 
> Comments on this algorithm?  I believe it handles nearly all ko
> positions that normally arise in go, including immediate ko and
> triple and multiple ko.
> 
> The concept seems simple, and the resource requirements are pretty
> low.  Every time a ko threat is made the ko position list is cleared,
> so it is rare that the ko position list will ever contain more than
> one board.  Snapbacks clear the ko position list.
> 
> I think the concept of storing a short history of boards is new in
> pbmserv.  I don't know how difficult adding this concept will be.

A right royal pain in the butt...

I've looked at this problem in the past, and the resources have been
limited.

I think the easiest way to do it is to create a "HASH" value for each 
player after each move.   And *that* is could be maintained as a N-tuple
for each move.

When a move is made, apply the move, and calculate the new HASH values.
and then run through every Nth set in the history list.

If you don't find it in the list, it's a non-Ko board state.

If you DO find it in the list, it's a POSSIBLE Ko board state.  And you
need to recreate the old board (from the move history) and do a complete
board comparison.

Creating/maintaining the HASH is fairly easy.   f(stones,position)



> Third:  if the algorithm seems sound, I'd like to get it implemented.
> I wouldn't mind if someone else were willing to step up to the plate
> and do it.  If no one does, I'll try to make the time to do it myself.
> 
> Please comment (or volunteer :-).
> 
> Thanks,
> - Scott
> 
> 
> P.S. - Does pbmserv go prevent suicide?

Only in Gonnect, I think.   Suicide is just a "pass".

-- 
 /  \__  | Richard Rognlie / Oracle Prophet / Gamerz.NET Lackey
 \__/  \ | http://www.gamerz.net/rrognlie/    <rrognlie@gamerz.net>
 /  \__/ | I can only please 1 person per day.  Today is not your day.
 \__/    | Tomorrow doesn't look good either.