Is this a correct formal heuristic for invalid moves due to Ko?

Question

In the game of Go, there is the ko rule, which basically states that immediately recapturing a single stone is not a valid move.

I am working on a Go computer program and am trying to implement the ko rule. For efficiency, I am satisfied with a more relaxed definition that aims at two goals:

1. It always prevents moves that would illegally recapture a ko
2. It never prevents moves that are legal

Currently, I go with:

If in the previous half-turn exactly one single stone was captured, then it is not allowed to play at the position of this stone in the immediately following half-turn (by the other player).

This is relaxed because it does not attempt to detect that a ko is actually present, it is only concerned with preventing an illegal move. For instance:

$$B
$$ -------
$$ | . . . . 
$$ | X X O O 
$$ | X O 1 O 
$$ | X X . . 

This situation is not a ko, because there is no way to recapture. However, playing at the location of the captured stone is still an invalid move, because it would be suicide. I believe that one or the other (illegal recapture or suicide) always applies.

My question is if my heuristic fulfills the two stated goals. (I think it does.)

Answer 1

No, this logic unfortunately doesn't work: It prevents moves that are in fact legal, because they include a snapback.

$$ white to play
$$ . . . . . . .
$$ . . X O X . .
$$ . X O X . X .
$$ . X O O O X .
$$ . . X X X . .
$$ . . . . . . .

White captures:

$$W
$$ . . . . . . .
$$ . . X O X . .
$$ . X O a 1 X .
$$ . X O O O X .
$$ . . X X X . .
$$ . . . . . . .

Now with your definition:

If in the previous half-turn exactly one single stone was captured

This is the case; white captured a single stone.

then it is not allowed to play at the position of this stone in the immediately following half-turn (by the other player).

That position is marked as a. However, it's perfectly legal for black to play there, as it captures the whole white group, and thus does not repeat the board position:

$$W
$$ . . . . . . .
$$ . . X O X . .
$$ . X . 2 . X .
$$ . X . . . X .
$$ . . X X X . .
$$ . . . . . . .

Answer 2

Your rule is adequate to detect simple kos but not all forbidden repetitions. EDIT: It incorrectly forbids snapbacks, as observed in balpha’s answer, and thus fails your condition (2). It is unclear to me from your question whether the “moves that would illegally recapture a ko” that you want it to prevent include only immediate recaptures or also later illegal recaptures; I cannot therefore tell if your condition (1) is satisfied.

The simple rule is inadequate when there is more than one ko on the board. The ko rule is therefore more complex than you suggest and exists in several variants. The most mathematically elegant forms rule out whole-board repetition, and these are probably also most convenient for programming. You could check out Sensei on Ko. Your rule fails to prevent illegal moves in situations like Triple Ko.

P.S. A handy speed up might be that a move cannot be an illegal repetition if there are more stones of either colour on the board than ever before in the game.