5

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.)

4
  • What evidence do you have that there is or can be a simpler, yet correct, definition? The Rules for Go already are quite simple, and have had hundreds of years of use and refinement. Dec 18, 2017 at 19:10
  • Perhaps you could clarify what incorrect decisions you are happy with. I would have thought one would prefer a programme that prevents all illegal and some legal moves to one that allows all legal and some illegal moves, but it sounds to me as though you are aiming at the latter.
    – PJTraill
    Dec 18, 2017 at 21:14
  • @ForgetIwaseverhere It was just an idea that came up and I could not think of an immediate reason why it would be wrong, that's why I asked :D
    – mafu
    Dec 19, 2017 at 17:18
  • @PJTraill It should allow only legal moves and all legal moves. This Q is particularly about the ko rule.
    – mafu
    Dec 19, 2017 at 17:19

2 Answers 2

8

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 . .
$$ . . . . . . .
1
  • 1
    As an interesting side note, the "ko rules" in Tibetan go are such that you are not allowed to play in intersections from which a stone was just captured. This does mean that to be able to play snapbacks, and many other tactical tricks, you need to have at least one ko threat.
    – jussius
    Jan 29, 2018 at 15:23
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.

1
  • Yes, I was not aiming for superko, only simple ko. I forgot to say that. Thanks for the hint in the PS!
    – mafu
    Dec 19, 2017 at 17:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .