superko violation examples

[alain]

Two games played by twinbot on CGOS, lost due to superko.
The comment included in the game at the last move explain the fault.
This happened in 1722 games played.

Last move changed by the twin compared to 3.7.9 for game 879 (was the first draft ;)

Move 44 (white): GNU Go plays J2 (49.46) - Game move H1
This is not linked to the superko

game 30527: Interesting. The twin move is not directly responsible for the superko violation, which is replayed by gg3.7.9, but it shows one problem with superko.

Move 71 (black): GNU Go plays C6 (1.00) - Game move E1

This move provoke a ko, and the threat fire back with superko violation later. Under superko rules playing like this gives an eye to the opponent.

---

GNU Go 3.7.4 games on CGOS (7 superko violation in 10500 games):

• 13435.sgf opponent lives if superko rules applied
• 25811.sgf interesting: it is seki, but W tries to kill and that would lead to infinite loop. Here superko rules are nice ;-)

---

GNU Go 3.7.4 games on CGOS: wrong killing logic.

• 14198.sgf interesting failure. Tries to kill from the wrong side and don't know "Take the ko last"
• 26449.sgf Idem. Something wrong in the killing logic

---

GNU Go 3.7.4 games on CGOS: Probably --capture-all-dead in action

• 31446.sgf superko can be avoid with better order in the killer moves
• 37169.sgf idem. opponent tries to survive with triple ko. Better order kills all.
• 994.sgf idem.

[alain]

On CGOS there is time constraint 600s SD.
Some "chaotic" opponents makes GNU Go use lot of time, and level sometimes fall to 0.

[gunnar]

Testcases

[gunnar]

The patch gunnar_7_10.11 adds testcases for some of the mistakes leading up to the superko violations.

[gunnar]

Fixes for some of the testcases added in gunnar_7_10.11.

[gunnar]

The patch gunnar_7_10.12 solves some of the new testcases. Regression results, including the new testcases, are

nicklas1:1509   FAIL H1 [T14]
semeai:132      PASS H9 [H9|J4]
kgs:360         PASS B18 [B18]
thrash:20       pass
thrash:21       pass
thrash:22       pass
thrash:27       pass
thrash:28       pass
thrash:29       pass
thrash:30       pass
9 PASS (2 PASS, 7 pass)
1 FAIL
Total nodes: 1691664620 3342344 12622136 (+0.094% +0.3% +0.047%)

The patch contains a number of small fixes.

• Call identify_thrashing_dragons() earlier in make_dragons() so that the information is available before it is used to determine whether to compute owl threats. This is a slightly serious bug since old thrashing dragon data from a previous move or a previous testcase were used instead. The increase in owl nodes is most likely because this fix causes owl threats to be computed more often. The passes of semeai:132 and kgs:360 are due to this fix, as well as the fail of nicklas1:1509. The latter is bogus, however, since it now finds a move to suppress a thrashing dragon according to policy.
• Avoid generating self atari moves at an early stage in aftermath_genmove(). Such moves can be generated later in the function if needed, with better checking against mistakes. This solves thrash:21.
• In do_owl_attack(), don't consider a defender move playing into send-two-return-one. Instead backfill first just as for suicide moves. This solves thrash:20.
• In move_connects_strings(), reduce string connection bonus for ko captures. This solves thrash:29.
• Don't consider send-two-return-one moves in find_more_attack_and_defense_moves(). This solves thrash:22. (Notice that this is about finding more tactical moves. find_more_owl_attack_and_defense_moves() has had this restriction a long time.)
• Reduce the maximum bonus from secondary move values by a soft_cap to 0.4 points. This solves thrash:27,28,29.
• When looking for more tactical attack and defense moves in find_worm_attacks_and_defenses() (called from make_worms()), don't consider send-two-return-one moves. This also solves thrash:22 and together with the aftermath fix, thrash:30.

[gunnar]

Implementation of superko and suicide options.

[gunnar]

The patch gunnar_7_10.13 implements superko options. Using --position-superko fixes all illegal moves reported in this ticket. It also correctly implements suicide options, solving #134.

[gunnar]

After the patch there are four different ko rule options

• --simple-ko, only forbid immediate recapture of a normal ko (default).
• --no-ko, allow any kind of board repetition.
• --positional-superko, forbid repetition of a previous position.
• --situational-superko, forbid repetition of a previous position with the same player to move.

and three different suicide options

• --forbid-suicide, all suicide moves forbidden (default).
• --allow-suicide, allow suicide but not of single stones.
• --allow-all-suicide, allow all suicide moves.

GNU Go itself still won't generate suicide moves, neither will it recapture a simple ko with --no-ko. It may play superko repetitions when such rules are not used, however.

Summary of changes:

• new static functions really_do_trymove() and is_superko_violation() in board.c
• store board hashes in the move history
• is_legal() does no longer depend on allow_suicide
• new function is_allowed_move() to determine legality with respect to current suicide and ko rules
• new global variables suicide_rule and ko_rule
• replace illegal moves with passes near the end of do_genmove()
• reevaluate_ko_threats() revised
• look for ko threats also if best move is a superko violation, assuming superko rules are used
• new suicide options --forbid-suicide (default) and --allow-all-suicide, in addition to the earlier --allow-suicide
• new ko rule options --simple-ko (default), --no-ko, --positional-superko, and --situational-superko
• use is_allowed_move() instead of is_legal() in play_gtp.c, play_ascii.c, and play_solo.c

[arend]

Phew, finally we understand superko! :)

Minor comments:

• A comment somewhere clarifying move_history_hash[] stores the board hash *without* ko state seems appropriate.
• In is_allowed_move(), case 4., maybe has_neighbor() is more intuitive than the EAST/WEST check.
• To me your naming of suicide rules is a little unintuitive. Maybe s.th. like FORBIDDEN, ALLOWED_EXCEPT_SINGLE_STONE, ALLOWED is more clear? (Which version is more frequently used, btw?)

[gunnar]

To me your naming of suicide rules is a little unintuitive. Maybe s.th. like FORBIDDEN, ALLOWED_EXCEPT_SINGLE_STONE, ALLOWED is more clear? (Which version is more frequently used, btw?)

Allowing single stone suicide is unheard of, except for the New Zealandish rules proposed, but then withdrawn, for the 2006 Computer Olympiad. That's the reason for the odd naming. One can also note that with positional superko, single stone suicide is automatically forbidden due to board repetition and that in general it would only be a different way to pass, but possibly not invoking game-end conditions, which is rather contra-productive.

[gunnar]

Same as gunnar_7_10.13 but with improved documentation

[gunnar]

The patch gunnar_7_10.13b improves the code comments, adds texinfo documentation of the new options, and removes the superko TODO entry.