Ticket #107 (new task)

Opened 2 years ago

Last modified 3 weeks ago

eyes.db improvements

Reported by: gunnar Assigned to: gunnar
Priority: normal Milestone: 3.7.13
Component: source Version:
Severity: normal Keywords:
Cc: patch: 1

Description

The encoding of eye values in GNU Go includes a number of different stable eyes, where one or both players can threaten to decrease or increase the number of eyes (eye values 0001 0002 0111 0112 1112 0222 1222). These are used in eyes.db but certainly not everywhere they occur and more importantly the points where threats can be made are not marked. See #101 for an example where it would be useful to have threat points marked, in that case the eye pattern 

(.(

:0001

The key to doing this with reasonable efficiency is the GTP function analyze_eyegraph (functionality implemented at the end of source:engine/optics.c) and automating calling it for different configurations of margins and opponent stones for a given eyeshape.

Attachments

gunnar_7_9.14.diff (22.6 kB) - added by gunnar on 02/27/06 00:23:06.
analyze_eyegraph improvements
check_eye_patterns.pike (41.6 kB) - added by gunnar on 03/02/06 23:14:24.
automated testing of eyes.db
gunnar_7_9.15.gz (24.2 kB) - added by gunnar on 03/03/06 22:41:56.
significant extension of eyes.db
gunnar_7_9.14b.diff (29.7 kB) - added by gunnar on 04/13/06 15:34:37.
further analyze_eyegraph improvements
gunnar_7_13.3.diff (5.3 kB) - added by gunnar on 04/23/08 21:57:15.
Incremental patch on top of gunnar_7_9.15 to work around some of the problems.
gunnar_7_13.5.diff (0.7 kB) - added by gunnar on 04/24/08 22:33:31.
Owl tuning intended to fix strategy5:290.

Change History

02/27/06 00:23:06 changed by gunnar

  • attachment gunnar_7_9.14.diff added.

analyze_eyegraph improvements

02/27/06 00:23:32 changed by gunnar

  • patch set to 1.

03/02/06 23:14:24 changed by gunnar

  • attachment check_eye_patterns.pike added.

automated testing of eyes.db

03/02/06 23:22:39 changed by gunnar

The attached file check_eye_patterns.pike is a script which parses eyes.db and tests whether various eyeshapes are correctly evaluated (using analyze_eyegraph to find the supposedly correct answer). It does not have many comments and is not intended for inclusion into the GNU Go sources unless people insist.

It also contains code to actually play out eyeshapes accordíng to the local game model which the optics code is based on. In practice that is not as useful as analyze_eyegraph, however, because it doesn't understand captures of defending stones inside the eyespace.

03/03/06 22:41:56 changed by gunnar

  • attachment gunnar_7_9.15.gz added.

significant extension of eyes.db

(follow-up: ↓ 5 ) 03/03/06 23:48:41 changed by gunnar

The patch gunnar_7_9.15 provides a much bigger and more complete eyes.db. Now attack and defense points are also marked for eyeshapes with ko threat values. Another difference is that analyze_eyegraph is used as baseline for the eye values. In particular this makes some changes for ko and/or outer liberty dependent eyes.

The regression results are somewhat scary: 

owl:2           FAIL 1 F8 [1 E9]
ld_owl:43       FAIL critical S1 S2 [critical (R1|S2|T7) S2]
ld_owl:49       FAIL alive [critical B18 (A18|B18)]
ld_owl:179      FAIL 0 [3 T17]
ld_owl:182      FAIL 1 R2 [2 S1]
ld_owl:189      FAIL alive [critical S1 (S4|S1|T2)]
ld_owl:190      FAIL critical B3 B3 [critical (B3|D2|B5|A5|A4) A2]
ld_owl:198      FAIL alive [dead]
ld_owl:305      FAIL alive [critical E2 (E2|E1)]
ld_owl:319      FAIL 1 B1 [3 D2]
optics:1705     FAIL 2 2 [1 2 A18 A18]
golife:1        PASS C7 [C7]
strategy2:73    PASS R17 [F7|R17|P15]
nicklas1:1902   FAIL D5 [B7]
trevor:261      FAIL A2 [F9]
nngs:240        FAIL T6 [R4|S4|Q2]
trevorc:240     FAIL K3 [K2]
vie:33          FAIL 0 [1 B2]
owl1:322        FAIL 1 D1 [0]
owl1:356        PASS 1 L3 [1 L3]
ninestones:150  FAIL G14 [C5|D5]
nando:12        PASS 0 [0]
seki:601        FAIL C9 [B1]
seki:602        FAIL C9 [C1|B1]
trevorb:140     pass
9x9:197         fail
owl1:388        pass
6 PASS (4 PASS, 2 pass)
21 FAIL (20 FAIL, 1 fail)
Total nodes: 1684103523 3334649 12612955 (+0.17% +0.58% +0.065%)

Many of the failures are related to eyespaces which are two certain eyes with sufficient outer liberties but less with a shortage of liberties, like the 2x3 rectangle in the corner,





The new eyes.db assumes there are sufficient outer liberties, so these shapes need a complementary entry in owl_vital_apats.db when there aren't.

(follow-up: ↓ 6 ) 04/13/06 14:04:32 changed by gunnar

Many of the failures are related to eyespaces which are two certain eyes with sufficient outer liberties but less with a shortage of liberties, like the 2x3 rectangle in the corner, The new eyes.db assumes there are sufficient outer liberties, so these shapes need a complementary entry in owl_vital_apats.db when there aren't.

After a second thought I think it's better to do this (more) properly. Since dependence on outer liberties and ko results are relatively uncommon it should not be too expensive to include that information in the eye database.

I'm considering a model where the number of outer liberties and the ko threat situation are specified. The latter is encoded as an integer which tells how many ko threats one of the players is allowed to ignore. Positive values mean that the defender is allowed to ignore ko threats and negative that the attacker is. (Thus positive values of outer liberties and ko threats are both to the advantage of the defender.)

For example the 2x3 rectangle in the corner would give the following analyze_eyegraph results for different number of outer liberties (horizontally) and ko threat numbers (vertically). 

    0     1     2
   
   |<*.  |.>.  |<<<
-2 |.*.  |.*.  |<<<
   +---  +---  +---
   1122  1122  1222
                   
   |.*.  |.>.  |<<<
-1 |.*.  |.*.  |<<<
   +---  +---  +---
   1122  1122  1222
                   
   |.*.  |.>.  |<<<
 0 |.*.  |.*.  |<<<
   +---  +---  +---
   1122  1122  1222
                   
   |.*.  |<<<  |<<<
 1 |.>.  |<<<  |<<<
   +---  +---  +---
   1122  1222  1222
                   
   |.*.  |<<<  |<<<
 2 |.>.  |<<<  |<<<
   +---  +---  +---
   1122  1222  1222

This could be condensed (ignoring unimportant attack and defense points) to something like 

Pattern X

|.*.
|...
+---

:1122,max_outer_liberties(0)


Pattern X+1

|...
|.*.
+---

:1122,max_outer_liberties(1),max_ko_threats(0)


Pattern X+2

|.<.
|.<.
+---

:1222

where as usual it's assumed that pattern matching returns after the first hit.

There are of course a few weaknesses of this scheme. For example it will not be quite straightforward for the optics code to pick up the fact that with one outer liberty there's a ko-dependent number of eyes.

04/13/06 15:34:37 changed by gunnar

  • attachment gunnar_7_9.14b.diff added.

further analyze_eyegraph improvements

(in reply to: ↑ 3 ) 11/06/07 21:42:07 changed by gunnar

Replying to gunnar: 

owl:2           FAIL 1 F8 [1 E9]
ld_owl:43       FAIL critical S1 S2 [critical (R1|S2|T7) S2]

The proposed moves are also valid solutions in these test cases. 

owl1:322        FAIL 1 D1 [0]

GNU Go isn't really supposed to pass this - classic cutting point in eyespace problem. Was lucky before. 

seki:601        FAIL C9 [B1]
seki:602        FAIL C9 [C1|B1]

The owl reading is improved which makes a specific seki pattern necessary instead.

(in reply to: ↑ 4 ) 11/06/07 21:50:05 changed by gunnar

Replying to gunnar:

After a second thought I think it's better to do this (more) properly. Since dependence on outer liberties and ko results are relatively uncommon it should not be too expensive to include that information in the eye database.

I still think that would be a proper solution but for now a quicker workaround to solve the main problems seems more appropriate so this eye database revision can finally get in.

The quickest fix is most likely to revise the outer liberty dependent eye patterns to return the result under the assumption of a shortage of liberties just like it's done today. It will make the eye database less consistent with respect to the verification tools, but it's an acceptable price to pay until better solutions are implemented.

04/23/08 21:57:15 changed by gunnar

  • attachment gunnar_7_13.3.diff added.

Incremental patch on top of gunnar_7_9.15 to work around some of the problems.

04/23/08 22:00:14 changed by gunnar

  • milestone changed from 3.8 to 3.7.13.

The patch gunnar_7_13.3 is an incremental patch (due to size concerns) on top of gunnar_7_9.15, working around many of the problems discussed above and adding fixes for some of the regression failures.

04/24/08 21:28:33 changed by gunnar

Much better results now after adding the incremental patch. The workarounds do their job and the new eye patterns make wonders on the STS-RV_e semeai tests. 

golife:1        PASS C7 [C7]
strategy2:73    PASS R17 [F7|R17|P15]
trevor:261      FAIL A2 [F9]
nngs:240        FAIL T6 [R4|S4|Q2]
trevorc:240     FAIL K3 [K2]
semeai:107      PASS D6 [D6|C7]
STS-RV_1:77     FAIL 1 0 G3 [1 1 (.*)]
STS-RV_1:175    PASS 1 1 H2 [1 1 H2]
STS-RV_1:179    PASS 1 0 Q17 [1 0 Q17]
STS-RV_1:187    PASS 1 1 R4 [1 1 R4]
STS-RV_1:188    PASS 1 0 R4 [1 0 R4]
STS-RV_e:13     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:14     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:25     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:26     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:55     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:56     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:61     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:62     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:83     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:84     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:87     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:88     PASS 1 0 PASS [1 0 PASS]
STS-RV_e:157    PASS 1 0 PASS [1 0 PASS]
STS-RV_e:158    PASS 1 0 PASS [1 0 PASS]
STS-RV_e:225    PASS 1 0 B9 [1 0 B9]
STS-RV_e:229    PASS 1 0 T14 [1 0 T14]
STS-RV_e:230    PASS 1 1 T14 [1 1 T14]
STS-RV_e:231    PASS 1 0 H18 [1 0 H18]
STS-RV_e:232    PASS 1 1 H18 [1 1 H18]
STS-RV_Misc:7   FAIL 1 0 T7 [1 1 N7]
STS-RV_Misc:8   PASS 1 1 T7 [1 1 T7]
STS-RV_Misc:46  FAIL 1 1 C17 [1 1 D19]
trevord:680     PASS S16 [S16]
owl1:322        FAIL 1 D1 [0]
owl1:354        FAIL 1 S13 [0]
owl1:356        PASS 1 L3 [1 L3]
owl1:372        FAIL 0 [1 D18]
owl1:388        PASS 1 A2 [1 A2]
strategy5:290   FAIL E2 [S16|S17|T16]
nando:12        PASS 0 [0]
9x9:197         FAIL D8 [E8|H5]
31 PASS
11 FAIL
Total nodes: 1702185916 3353717 12405332 (+0.043% +0.3% +0.0087%)

04/24/08 21:58:00 changed by gunnar

Nothing too dramatic about the failures except strategy5:290 which is really bad. Since the overall results are so good I will apply the two current patches first and then fix strategy5:290.

04/24/08 22:33:31 changed by gunnar

  • attachment gunnar_7_13.5.diff added.

Owl tuning intended to fix strategy5:290.