Context Navigation

Ticket #29 (new task)

Opened 6 years ago

Last modified 3 years ago

--large-scale

Reported by:	arend	Owned by:	gnugo
Priority:	normal	Milestone:	Future
Component:	source	Version:
Severity:	normal	Keywords:
Cc:	cassio@…	patch:	yes

Description (last modified by arend) (diff)

The --large-scale option is potentially very useful and needs to be evaluated more closely.

The breakage after applying arend_7_7.3* (on CVS 05-10-05):

nngs1:42        PASS O9 [O9]
neurogo:16      FAIL H14 [H17|K17|H15|L16]
arion:2         FAIL S15 [Q18|S16]
strategy2:89    FAIL H11 [(D16|B7|G13)]
nicklas1:1107   PASS N2 [N2]
trevor:163      FAIL C7 [B9]
nngs:700        FAIL K16 [K17]
trevorc:1540    FAIL M11 [M10]
global:22       FAIL H2 [F2]
13x13:61        PASS K8 [K8]
strategy4:187   PASS E4 [C4|E4]
strategy4:202   PASS B6 [B6]
handtalk:10     FAIL G8 [E9|F8]
nngs2:110       FAIL M16 [B14|B13]
nngs2:140       PASS P5 [P5]
nngs3:330       FAIL Q12 [P12|Q11]
nngs3:470       PASS G15 [!J17]
nngs3:490       FAIL T13 [P15]
nngs3:950       PASS F15 [F15]
nngs4:580       FAIL H5 [E5]
gunnar:51       FAIL T5 [S7]
gifu03:702      PASS N6 [N6]
9x9:320         PASS F4 [E5|F4|D4|E4]
9x9:330         PASS F3 [D3|F3]
9x9:410         PASS B5 [B5]
cgf2004:80      PASS O15 [Q12|O15]
kgs:330         PASS H1 [H1]
kgs:710         PASS B7 [B7]
olympiad2004:11 PASS S14 [S19|R19|O14|O13|S14]
Total nodes: 1822137518 3685493 13786827
16 PASS
13 FAIL

P.S.: To go through the list with view.pike, one can do

./view.pike nngs1:42 neurogo:16 arion:2 strategy2:89 nicklas1:1107 trevor:163 nngs:700 trevorc:1540 global:22 13x13:61 strategy4:187 strategy4:202 handtalk:10 nngs2:110 nngs2:140 nngs3:330 nngs3:470 nngs3:490 nngs3:950 nngs4:580 gunnar:51 gifu03:702 9x9:320 9x9:330 9x9:410 cgf2004:80 kgs:330 kgs:710 olympiad2004:11

Attachments

arend_7_7.2-large_scale_reorganization.diff (11.0 KB) - added by arend 6 years ago.: Reorganizes the large scale code, breaking it up into 3 smaller functions
arend_7_7.3b-no_large_scale_in_seki.diff (831 bytes) - added by arend 6 years ago.: Trying for an owl attack only makes sense against dragons who are both owl critical AND overall critical (i.e., not alive in seki)
arend_7_7.3c-ineffective_owl_attack_revision.diff (688 bytes) - added by arend 6 years ago.: minor ineffective owl attack logic revision
arend_7_7.3a-avoid_large_scale_side_effect.diff (1.3 KB) - added by arend 6 years ago.: avoid side effects between large scale and find_more_owl... by reordering them
arend_7_8.5a-large_scale_node_limit.diff (2.5 KB) - added by arend 6 years ago.: Don't hardwire owl node limit for large scale attacks.
large_scale_statistics.diff (6.2 KB) - added by arend 6 years ago.: For reference: patch to collect statistics on large scale attack success depending on original number of owl attack reading notes
arend_7_8.10-owl_attack_node_count.diff (3.7 KB) - added by arend 6 years ago.: Don't try large scale owl attack if original owl attack reading was expensive already.

Regression Results

Attachment	Rev.	PASS	FAIL	Nodes	Status
arend_7_7.2-large_scale_reorganization.diff	2381				patch does not apply	details
arend_7_7.3a-avoid_large_scale_side_effect.diff	2381				patch does not apply	details
arend_7_7.3b-no_large_scale_in_seki.diff	2381				patch does not apply	details
arend_7_7.3c-ineffective_owl_attack_revision.diff	2381				patch does not apply	details
arend_7_8.10-owl_attack_node_count.diff	2381				patch does not apply	details
arend_7_8.5a-large_scale_node_limit.diff	2381				patch does not apply	details
large_scale_statistics.diff	2381				patch does not apply	details

Change History

comment:1 Changed 6 years ago by arend

Description modified (diff)

Changed 6 years ago by arend

attachment arend_7_7.2-large_scale_reorganization.diff added

Reorganizes the large scale code, breaking it up into 3 smaller functions

comment:2 Changed 6 years ago by arend

Cc arend.bayer@… added

comment:3 Changed 6 years ago by arend

patch set

comment:4 Changed 6 years ago by arend

Type changed from defect to task

comment:5 Changed 6 years ago by arend

Cc arend.bayer@… removed

Changed 6 years ago by arend

attachment arend_7_7.3b-no_large_scale_in_seki.diff added

Trying for an owl attack only makes sense against dragons who are both owl critical AND overall critical (i.e., not alive in seki)

comment:6 Changed 6 years ago by stephane

Cc cassio@… added

Changed 6 years ago by arend

attachment arend_7_7.3c-ineffective_owl_attack_revision.diff added

minor ineffective owl attack logic revision

comment:7 Changed 6 years ago by arend

Description modified (diff)

Changed 6 years ago by arend

attachment arend_7_7.3a-avoid_large_scale_side_effect.diff added

avoid side effects between large scale and find_more_owl... by reordering them

comment:8 Changed 6 years ago by arend

Description modified (diff)

Commented brekage:

ngs1:42        PASS O9 [O9]                    Huge gain.
neurogo:16      FAIL H14 [H17|K17|H15|L16]      This is fully ok.
arion:2         FAIL S15 [Q18|S16]              More aji but still ok.
strategy2:89    FAIL H11 [(D16|B7|G13)]         Bad.
nicklas1:1107   PASS N2 [N2]                    Hardly relevant.
trevor:163      FAIL C7 [B9]                    Loses 2 points.
nngs:700        FAIL K16 [K17]                  Leaves too much aji.
trevorc:1540    FAIL M11 [M10]                  Bad (at least unclear to me)
global:22       FAIL H2 [F2]                    Ok.
13x13:61        PASS K8 [K8]                    L13 was also ok.
strategy4:187   PASS E4 [C4|E4]                 Huge gain.
strategy4:202   PASS B6 [B6]                    Huge gain.
handtalk:10     FAIL G8 [E9|F8]                 Still ok.
nngs2:110       FAIL M16 [B14|B13]              Ok.
nngs2:140       PASS P5 [P5]                    Big gain.
nngs3:330       FAIL Q12 [P12|Q11]              Still ok.
nngs3:470       PASS G15 [!J17]                 No difference.
nngs3:490       FAIL T13 [P15]                  Bad.
nngs3:950       PASS F15 [F15]                  CVS move was ok.
nngs4:580       FAIL H5 [E5]                    Bad (owl misread)
gunnar:51       FAIL T5 [S7]                    Bit weird but T5 seems to work
gifu03:702      PASS N6 [N6]                    Good.
9x9:320         PASS F4 [E5|F4|D4|E4]           Good.
9x9:330         PASS F3 [D3|F3]                 Improved a bit.
9x9:410         PASS B5 [B5]                    Very good.
cgf2004:80      PASS O15 [Q12|O15]              Lucky.
kgs:330         PASS H1 [H1]                    Good.
kgs:710         PASS B7 [B7]                    Good (small gain).
olympiad2004:11 PASS S14 [S19|R19|O14|O13|S14]  Ok (I think the test is nitpicking)
Total nodes: 1822137518 3685493 13786827
+7%, +14%, +3.7%
16 PASS
13 FAIL

comment:9 Changed 6 years ago by gunnar

I think we need to reduce the cost of this patch. The obvious weakness in my opinion is the search area for large scale moves. Contrary to the code comments it's not a Manhattan distance from the dragon but the max-norm distance from the axis-parallel bounding box of the dragon, which frankly doesn't make much sense.

First, if we are going to use a simple geometric distance from the dragon it should at least relate to the actual dragon, not to a bounding box.

Second, it should be possible to use some more problem-specific distance. The distance used in atari_atari (see update_aa_goal()) might serve as inspiration, although it's hardly applicable in this context as is.

Third, although not really tempting it might be effective to use the opponent's last move as guide for where to search.

Changed 6 years ago by arend

attachment arend_7_8.5a-large_scale_node_limit.diff added

Don't hardwire owl node limit for large scale attacks.

Changed 6 years ago by arend

attachment large_scale_statistics.diff added

For reference: patch to collect statistics on large scale attack success depending on original number of owl attack reading notes

comment:10 Changed 6 years ago by arend

Here is an example of the kind of statistics collected by the attached patch:

Statistics for close attacks (node limit = 350):
node count:<=   0 <= 100 <= 200 <= 300 <= 400 <= 500 <= 600 <= 700 <= 800 <= 900 <=1000
Successes:    346     13     13      5      3      5      1      2      1      3      0
Cumulated:    346    359    372    377    380    385    386    388    389    392    392
Nodes:       6057   1492   4264   1361   1034    861    345    986     73    269      0
Cumulated:   6057   7549  11813  13174  14208  15069  15414  16400  16473  16742  16742
Failures:    1511    120     74     55     38     22     19     17     14      2      0
Cumulated:   1511   1631   1705   1760   1798   1820   1839   1856   1870   1872   1872
Nodes:      50034  17166  14648   8168   6502   7161   4572   8003   4814    700      0
Cumulated:  50034  67200  81848  90016  96518 103679 108251 116254 121068 121768 121768

Statistics for wide attacks (node limit = 150):
node count:<=   0 <= 100 <= 200 <= 300 <= 400 <= 500 <= 600 <= 700 <= 800 <= 900 <=1000
Successes:    478     12     12      5      7      2      0      0      0      0      0
Cumulated:    478    490    502    507    514    516    516    516    516    516    516
Nodes:      12837    524    939    323    368    221      0      0      0      0      0
Cumulated:  12837  13361  14300  14623  14991  15212  15212  15212  15212  15212  15212
Failures:    6209    232    189    131     62     44     39     18     14     10      0
Cumulated:   6209   6441   6630   6761   6823   6867   6906   6924   6938   6948   6948
Nodes:     111319  14676  24048  11780   3677   5962   2631   3185   2206   1200      0
Cumulated: 111319 125995 150043 161823 165500 171462 174093 177278 179484 180684 180684

It suggests that we can about 90% of the effect of --large-scale at 60% of the cost if we only try attacks on dragons where the original owl attack analysis too less than ~300 resp. ~100 nodes (for close and wide attacks, respectively).

Changed 6 years ago by arend

attachment arend_7_8.10-owl_attack_node_count.diff added

Don't try large scale owl attack if original owl attack reading was expensive already.

comment:11 Changed 6 years ago by arend

Here is the breakage after applying arend_7_8.10:

nngs1:42        PASS O9 [O9]
neurogo:16      FAIL H14 [H17|K17|H15|L16]
arion:2         FAIL S15 [Q18|S16]
strategy2:89    FAIL H11 [(D16|B7|G13)]
nicklas1:1107   PASS N2 [N2]
trevor:163      FAIL C7 [B9]
nngs:700        FAIL K16 [K17]
trevorc:1540    FAIL M11 [M10]
global:22       FAIL H2 [F2]
13x13:61        PASS K8 [K8]

strategy4:187   PASS E4 [C4|E4]
strategy4:202   PASS B6 [B6]
handtalk:10     FAIL G8 [E9|F8]
nngs2:140       PASS P5 [P5]
nngs3:470       PASS G15 [!J17]
nngs3:490       FAIL T13 [P15]
nngs3:950       PASS F15 [F15]
nngs4:580       FAIL H5 [E5]
gifu03:702      PASS N6 [N6]
9x9:330         PASS F3 [D3|F3]
9x9:410         PASS B5 [B5]
cgf2004:80      PASS O15 [Q12|O15]
kgs:330         PASS H1 [H1]
kgs:710         PASS B7 [B7]
olympiad2004:11 PASS S14 [S19|R19|O14|O13|S14]
Total nodes: 1734027834 3535609 12202282
15 PASS
10 FAIL

This is +7.8% owl nodes, getting more acceptable, with little effect on the effective breakage.

comment:12 Changed 6 years ago by alain

it seems that the FAIL are mostly when there is ongoing semeai, so the chosen best move is urgent and should not be changed.

in other cases, it is good for cutting and capturing in a net, or saving our capturing stones.

Failures

"global:22"	"FAIL"	"H2"	"[F2]"			"Semeai/life"
"nngs:700"	"FAIL"	"K16"	"[K17]"			"Semeai"
"nngs2:110"	"FAIL"	"M16"	"[B14|B13]"		"semeai/must kill"
"nngs3:490"	"FAIL"	"T13"	"[P15]"			"semai/life"
"nngs4:580"	"FAIL"	"H5"	"[E5]"			"Urgent cut and kill"
"strategy2:89"	"FAIL"	"H11"	"[(D16|B7|G13)]"	"Difficult. Strategy. Rotten situation, 2 uncorrelated urgent moves."
"trevor:163"	"FAIL"	"C7"	"[B9]"			"Small yose"
"trevorc:1540"	"FAIL"	"M11"	"[M10]"			"Semeai"

lucky ?

"gunnar:51"	"FAIL"	"T5"	"[S7]"			"Bit weird but t5 seems ok"	"semai/life"
"arion:2"	"FAIL"	"S15"	"[Q18|S16]"		"More aji but still ok."	"Must kill"

ok, good also should not considered as a failure

"handtalk:10"	"FAIL"	"G8"	"[E9|F8]"		"Still ok"		"Boshi/gueta"
"nngs3:330"	"FAIL"	"Q12"	"[P12|Q11]"		"Still ok"		"Geta"
"neurogo:16"	"FAIL"	"H14"	"[H17|K17|H15|L16]"	"This i fully ok"	"Avoid semeai"

OK, PASS

"13x13:61"	"PASS"	"K8"	"[K8]"		"L13 was also ok"	"Good cut"
"9x9:320"	"PASS"	"F4"	"[E5|F4|D4|E4]"	"Good."			"Good cut"
"9x9:330"	"PASS"	"F3"	"[D3|F3]"	"Improved a bit"	"Good cut"
"9x9:410"	"PASS"	"B5"	"[B5]"		"Very good"		"Ok"
"cgf2004:80"	"PASS"	"O15"	"[Q12|O15]"	"Lucky."		"Ok"
"gifu03:702"	"PASS"	"N6"	"[N6]"		"Good."			"Good cut+geta"
"kgs:330"	"PASS"	"H1"	"[H1]"		"Good."			"Geta"
"kgs:710"	"PASS"	"B7"	"[B7]"		"Good small gain"	"Geta"
"Nngs1:42"	"PASS"	"O9"	"[O9]"		"Huge gain"		"N7 seems bigger, unclear test"
"nicklas1:1107"	"PASS"	"N2"	"[N2]"		"Hardly relevant"	"Minor"
"nngs2:140"	"PASS"	"P5"	"[P5]"		"Big gain"		"Direction pb in value moves"
"nngs3:470"	"PASS"	"G15"	"[!J17]"	"No diff"	
"nngs3:950"	"PASS"	"F15"	"[F15]"		"CVS move was ok"	"Frontier"
"strategy4:187"	"PASS"	"E4"	"[C4|E4]"	"Huge gain"		"Save cutting stones"
"strategy4:202"	"PASS"	"B6"	"[B6]"		"Huge gain"		"Cut"

comment:13 Changed 6 years ago by alain

semeai failures need the same kind of detection as #104 :

play urgent move (semeai) before big move

comment:14 Changed 3 years ago by gunnar

Milestone changed from 3.8 to Future

Note: See TracTickets for help on using tickets.

Download in other formats: