Semeai code and sekis

[arend]

The current semeai code misanalyzes some very simple seki situations. The reason is the following: Pass instead of playing a move is only tried when no move has been found. This assumes that none of the semeai move generates would generate a suicidal self-atari in a seki situation, which is unfortunately not true (vital owl patterns are a major offender).

The attached patch thus tracks whether an "undangerous" move has been generated, which is so far simply a move that is not a liberty of our goal dragon (and not a ko move for technical reasons). A pass is tried whenever no such undangerous move has been found.

Since this makes GNU Go pass more often, it does increase semeai nodes overall. To migitate this somewhat, we no longer require "!pass" when doing a cache lookup. The reason is that pass == 1 doesn't really change the semantics of do_owl_analyze_semeai() (like a non-empty komaster would), it is just additional information that can shortcut the search.

See semeai:77, 79, 80 for simple situations where passing is needed.

Breakage:

blunder:33      PASS O19 [!H6|J1]
trevora:530     FAIL F2 [H4]
nicklas2:904    FAIL G8 [B1|E1]
nngs:510        PASS G14 [G14]
nngs:820        FAIL D14 [J13|L9]
semeai:77       PASS 1 0 PASS [1 0 PASS]
semeai:79       PASS 1 0 PASS [1 0 PASS]
semeai:80       PASS 1 0 E9 [1 0 (PASS|E9|E8|J9|H5)]
semeai:124      FAIL 1 1 T15 [1 1 P19]
strategy4:155   FAIL M16 [D18]
nngs3:400       FAIL D11 [N13]
ninestones:570  PASS J15 [A9|B10|D11|F11|J15|A16]
ninestones:660  FAIL Q2 [P1]
9x9:120         PASS F1 [F1]
Total nodes: 1701981663 3345191 13185083

Running just the above list of tests with "--semeai-node-limit=1000" leaves semeai:124 as only FAIL, while 5 PASSes remain (all except nngs:510 and ninestones:570).

And the full breakage of running 3.7.7 + this patch + 1000 as semeai node limit:

blunder:33      PASS O19 [!H6|J1]
strategy:50     PASS Q9 [Q9]
semeai:77       PASS 1 0 PASS [1 0 PASS]
semeai:79       PASS 1 0 PASS [1 0 PASS]
semeai:80       PASS 1 0 E9 [1 0 (PASS|E9|E8|J9|H5)]
semeai:124      FAIL 1 1 T15 [1 1 P19]
9x9:120         PASS F1 [F1]
Total nodes: 1770685319 3837347 13692829
(+4.0%, +14.7%, +3.9%)

Here is for comparison the breakage without the patch, but with --semeai-node-limit=1000:

strategy:50     PASS Q9 [Q9]
nngs:304        PASS M7 [B14|M7]
global:44       PASS D5 [D5]
semeai:32       PASS 1 0 B6 [1 0 B6]
nngs2:460       FAIL N15 [J4|K2|K3|K4|K5|L2]
nngs4:1120      PASS N7 [N7]
Total nodes: 1768941889 3606253 13852259
(+3.8%, +11.5%, +4.2%)
5 PASS
1 FAIL

(See comment below for description and breakage of revised version.)

[arend]

Semeai code passes more often

[gunnar]

Alternative, but not successful, approach

[gunnar]

I once tried a modification with the same aim but it wasn't successful; 3 FAIL and 0 PASS when I last ran regressions. I have attached it as potential_blunder.diff for reference.

[arend]

The increase in owl nodes for the regression run with semeai_node_limit == 1000 shows that the explosion of the branching factor caused by this patch is unacceptable. The only reason this didn't cause a bigger increase in owl nodes originally is that most of the semeai reading this the 500 threshhold anyway. I am reworking the patch to cause a pass less often.

[arend]

New version: stricter definition of dangerous moves

[arend]

The new version arend_7_8.2b-semeai_fix.diff deems a move as risky if it decreases the liberty count of any string in the goal dragon. We pass only if no move has worked, no riskless move had been generated found, and the opponent doesn't look alive yet.

The node increases are a lot more acceptable now:

blunder:33      PASS O19 [!H6|J1]
nicklas2:904    FAIL H7 [B1|E1]
semeai:77       PASS 1 0 PASS [1 0 PASS]
semeai:79       PASS 1 0 PASS [1 0 PASS]
semeai:80       PASS 1 0 E9 [1 0 (PASS|E9|E8|J9|H5)]
semeai:124      FAIL 1 1 T15 [1 1 P19]
ninestones:570  PASS J15 [A9|B10|D11|F11|J15|A16]
9x9:120         PASS F1 [F1]
Total nodes: 1702617311 3276226 13263462

And with --semeai-node-limit=1000:

blunder:33      PASS O19 [!H6|J1]
strategy:50     PASS Q9 [Q9]
nngs:304        PASS M7 [B14|M7]
semeai:77       PASS 1 0 PASS [1 0 PASS]
semeai:79       PASS 1 0 PASS [1 0 PASS]
semeai:80       PASS 1 0 E9 [1 0 (PASS|E9|E8|J9|H5)]
semeai:124      FAIL 1 1 T15 [1 1 P19]
nngs4:1120      PASS N7 [N7]
Total nodes: 1767953273 3641406 13819848