[pbmserv-dev] proposed ko algorithm for pbmserv go

[Scott Huddleston <scotth@ichips.intel.com>]

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?

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.


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?