[werewolf] And now for something completely different

["Adam Luter" <adam.luter@gmail.com>]

Ok, this is off topic and random, but I know at least one of you play go, and I know at least a few of you program.  So, I'm asking a question:

I am writing a go engine to a cellphone version of go, and I am trying to make the valid rules checks quick (say this five times fast).

Quick primer, in go you place pieces of alternating colors, and if any connected same-color group is totally surrounded (referred to as having no liberties) then it is captured and the stones are removed from the board.  Diagonals do not count for connecting or surrounding.  The edges of the board may be used for surrounding.

Besides this basic premise, there are only two other rules.  One, you may not place a piece such that it will be captured (ie because the placement is such that it would have no liberties) - unless such a move would also capture an enemy group, in which case thr enemy group gets captured and yours does not.  This often called 'no suicide'.

Two is known as 'ko' which means eternity.  The idea is that you may not place a piece that will bring the board back to a previous state.  Usually, this is not followed in the strictest sense (which is called super-ko) but rather that the board may not look like it did at the end of your previous turn.

Ok so my question relates to a quick ko check.  My original (and straightforward) check was to play out the move and compare the new board with the board from the previous turn.  This works but unless I want to do super-ko (by checking all previous boards in the same way) there should be a faster check.

? b w ?
b e e w
? b w ?

Ok so the above (? = don't care, b = black, w = white, e = empty) is a setup that is potential for ko.  (The black and white stones shown can be subsituted with the edge of the board.)

So ko can happen by white playing at the empty left square, if black responds (at any later time) at the right empty spot he will capture the white piece - additionally white may not -immediately- respond at the left spot becuase it would be ko.  White must play at some other place on the board (or pass).  Generally black then has an opportunity to play at the left most spot or play elsewhere.  If he does not play left only then may white play left, which would then make black's play right ko, etc.

So now that we have an example to look at, here is my proposed check logic:

If and only if, the current move captures a single stone and is itself a single stone (is not connected to any friendly units) and it is without any liberties itself (except the one provided by the capture) -then- the captured stone's location is marked as a ko move.

I'm pretty sure this is correct, but I wanted to bounce this off some fellow programmers and if they happen to know the rules of go, all the better.

Oh and I think you can extend a regular ko check to super-ko by keeping track of previous ko positions, but I'm not trying to solve that right now and this email is long enouigh.

Thanks,
  Gryn