Fuego sometimes seems to resign even when the game is won

[dtsudo]

Hello herzbube!

I've been using Little Go for ~2 years now, and I thought I'd submit this small issue which I think is a bug.

In some cases, I've observed that the Fuego AI will occasionally resign, even though the game has actually been won by the AI.

I've attached an sgf file consisting of such a game (Anonymous vs. Anonymous 2.txt). Since GitHub doesn't support the .sgf extension, I've renamed the file to just be a .txt extension. I created this file by simply creating a "human vs human" game -- the game is very artificial; it begins with 9 stones handicap, and consists of both players just carving out the board into two halves. Under the Little Go ruleset, White wins by 6.5 points.

However, if I load up this game and ask Fuego to play as White, Fuego generally makes a feeble attempt at invading Black's territory and then resigns soon afterwards (despite the fact that White wins by 6.5 points).

In general, I've observed that Fuego seems to sometimes resign won games when the margin of victory is very small. (Sometimes, this also leads to Fuego making bad moves in an attempt to "win" even though it's already winning.)

I believe (without proof) that this might occur because Fuego doesn't recognize that the 9-stone handicap alters the scoring. (Under area scoring rules, White receives an additional point of compensation for each Black handicap stone.)

I took a quick look at documentation and the help text, but didn't find anything other than a warning that area scoring should be used since Fuego sometimes plays inside its own territory.

[herzbube]

Thanks for taking the time to write up this issue (and for reading the manual ☺)! I see what you mean, with your .sgf file I can reproduce this also on my side.

You wrote:

I believe (without proof) that this might occur because Fuego doesn't recognize that the 9-stone handicap alters the scoring.

I am going to ask about this on the Fuego mailing list. I am not convinced that you are right, after all the people who wrote Fuego have spent a lot of time on the Go playing subject, so I can't imagine that they would have got something elementary as this wrong. But on the other hand I cannot provide a counter-proof because, frankly, I don't understand the algorithms that Fuego uses for its inner workings.

In the meantime, as a workaround, have you already tried changing Fuego's resign behaviour? If not, then go to "Settings > Players & Profiles" and select a profile. For the default "Fuego" player this would be the "Strong" profile. Then tap "Resign behaviour". On my side, if I set this to "Stubborn" instead of the default "Normal", Fuego still attempts to invade Black's territory for some time, but after about 25 moves it starts passing. It no longer resigns.

Note to self: Fuego resigns when it thinks the best move that it can calculate is a very poor move (best move quality percentage is below the resign threshold percentage), in which case it is better to resign than to continue to play. The default resign threshold is 8%, so the best move quality must be below 8%. Setting the "Resign behaviour" to "Stubborn" decreases the resign threshold from 8% to 4%, which means that the best move quality percentage must be somewhere between 4% and 8%. I tried giving Fuego additional time and RAM for its calculations (20 seconds and 1024 MB instead of the default 10 seconds and 32 MB), but with resign threshold 8% it still resigns.

[herzbube]

The problem can be reproduced using Fuego on Mac OS X, compiled from trunk (r2034).

These are the commands with which to initialize Fuego. They correspond to how Little Go configures Fuego when the "Strong" profile is in effect, with the modifications of 20 seconds per move and 1024 MB RAM. The move sequence corresponds to the .sgf file provided by @dtsudo, with 11 moves played by me up to the point where Fuego resigns.

go_param_rules ko_rule simple
go_param_rules japanese_scoring 0
boardsize 19
komi 0.5
uct_max_memory 1024000000
uct_param_search number_threads 1
uct_param_player reuse_subtree 1
uct_param_player ponder 1
uct_param_player max_ponder_time 300
go_param timelimit 20
uct_param_player max_games 18446744073709551615
uct_param_player resign_min_games 5000
uct_param_player resign_threshold 0.080000
clear_board
set_free_handicap D4 Q16 D16 Q4 D10 Q10 K4 K16 K10
gogui-play_sequence W J4 B K3 W J3 B K2 W J2 B K1 W J1 B K5 W J5 B K6 W J6 B K7 W J7 B K8 W J8 B K9 W J9 B L10 W J10 B L11 W K11 B L12 W K12 B L13 W K13 B L14 W K14 B L15 W K15 B L16 W J16 B L17 W K17 B L18 W K18 B L19 W K19 B M16 W J17 B O16 W J15 B N16 W E16 B P16 W D17 B R16 W D15 B S16 W C16 B T16 W E10 B R10 W D11 B S10 W D9 B T10 W C10 B P10 W E4 B O10 W D5 B N10 W C4 B M10 W D3 B P4 W D2 B O4 W D1 B N4 W D4 B M4 W B4 B L4 W A4 B R4 W F4 B S4 W G4 B T4 W H4 B P5 W D6 B P6 W D7 B P7 W D8 B P8 W D10 B P9 W F10 B P11 W G10 B P12 W H10 B P13 W D12 B P14 W D13 B P15 W D14 B P17 W D16 B P18 W D18 B P19 W D19 B P3 W B16 B P2 W A16 B P1 W B10 B M13 W A10 B N13 W F16 B O13 W G16 B N11 W H16 B N12 W J12 B N9 W H12 B N8 W G12 B N7 W F12 B N5 W E12 B N6 W G18 B M7 W G17 B L7 W G19 B O7 W B17 B M8 W B18 B L9 W B19 B M5 W C13 B L6 W B13 B M6 W A13 B L5 W C7 B O5 W B7 B O6 W A7 B O8 W C2 B M9 W B2 B L8 W A2 B O9 W G2 B O3 W G3 B O2 W G1 B O1 W H7 B N3 W G7 B N2 W F7 B N1 W E7 B M3 W G13 B M2 W G14 B M1 W G15 B  PASS W R2 B T2 W T1 B S1 W R18 B T18 W T19 B S19 W R1 B T3
uct_param_globalsearch territory_statistics 0
uct_param_policy knowledge_type greenpeep

Copy & paste the commands above into a file cmds.txt, then run this on the command line:

./fuego --config ./cmds.txt

Let Fuego perform its calculations for 5 minutes in the background (= pondering), then enter this command:

genmove W

The result: Fuego resigns. Here is the output on stdout:

celebdil:bin patrick$ ./fuego --config ./cmds.txt 
Fuego 1.1.SVN
Copyright (C) 2009-2015 by the authors of the Fuego project.
This program comes with ABSOLUTELY NO WARRANTY. This is
free software and you are welcome to redistribute it under
certain conditions. Type `fuego-license' for details.

SgRandom::SetSeed: 23595565
SgUctSearch: system memory 17179869184, using 1000000000 (6250000 nodes)
GoUctFeatureKnowledgeFactory Read weights for 2200 features with k = 10, minID = 0, maxID = 2153
GoUctGlobalSearch: setting default number of threads to 4
Loading opening book from '/Users/patrick/fuego-resign-test/fuego-trunk/book/book.dat'... ok
go_param_rules ko_rule simple
= 

go_param_rules japanese_scoring 0
= 

boardsize 19
= 

komi 0.5
= 

uct_max_memory 1024000000
= 

uct_param_search number_threads 1
= 

uct_param_player reuse_subtree 1
= 

uct_param_player ponder 1
= 

uct_param_player max_ponder_time 300
= 

go_param timelimit 20
= 

uct_param_player max_games 18446744073709551615
= 

uct_param_player resign_min_games 5000
= 

uct_param_player resign_threshold 0.080000
= 

clear_board
= 

set_free_handicap D4 Q16 D16 Q4 D10 Q10 K4 K16 K10
GoUctPlayer: Setting default parameters for size 19
= 

gogui-play_sequence W J4 B K3 W J3 B K2 W J2 B K1 W J1 B K5 W J5 B K6 W J6 B K7 W J7 B K8 W J8 B K9 W J9 B L10 W J10 B L11 W K11 B L12 W K12 B L13 W K13 B L14 W K14 B L15 W K15 B L16 W J16 B L17 W K17 B L18 W K18 B L19 W K19 B M16 W J17 B O16 W J15 B N16 W E16 B P16 W D17 B R16 W D15 B S16 W C16 B T16 W E10 B R10 W D11 B S10 W D9 B T10 W C10 B P10 W E4 B O10 W D5 B N10 W C4 B M10 W D3 B P4 W D2 B O4 W D1 B N4 W D4 B M4 W B4 B L4 W A4 B R4 W F4 B S4 W G4 B T4 W H4 B P5 W D6 B P6 W D7 B P7 W D8 B P8 W D10 B P9 W F10 B P11 W G10 B P12 W H10 B P13 W D12 B P14 W D13 B P15 W D14 B P17 W D16 B P18 W D18 B P19 W D19 B P3 W B16 B P2 W A16 B P1 W B10 B M13 W A10 B N13 W F16 B O13 W G16 B N11 W H16 B N12 W J12 B N9 W H12 B N8 W G12 B N7 W F12 B N5 W E12 B N6 W G18 B M7 W G17 B L7 W G19 B O7 W B17 B M8 W B18 B L9 W B19 B M5 W C13 B L6 W B13 B M6 W A13 B L5 W C7 B O5 W B7 B O6 W A7 B O8 W C2 B M9 W B2 B L8 W A2 B O9 W G2 B O3 W G3 B O2 W G1 B O1 W H7 B N3 W G7 B N2 W F7 B N1 W E7 B M3 W G13 B M2 W G14 B M1 W G15 B  PASS W R2 B T2 W T1 B S1 W R18 B T18 W T19 B S19 W R1 B T3
= 

uct_param_globalsearch territory_statistics 0
= 

uct_param_policy knowledge_type greenpeep
= 

GoUctPlayer::Ponder: start
GoUctPlayer: No tree to reuse found
 0:05 | 0.075 | 4312 | 7.8 | R7 R13 L3 L2 M12 M11 T17 S17 S18 T1
 0:10 | 0.075 | 8644 | 8.6 | R7 S8 S7 R8 T8 T9 T7 R13 R12 S12 S13 S14 R14 T13 H15
 0:15 | 0.075 | 13036 | 9.1 | R7 S8 S7 R8 T8 T9 T7 R13 T17 S17 S18 R19 Q18 Q19 Q17
 0:20 | 0.075 | 17223 | 9.4 | R7 S8 S7 R8 T8 T9 T7 R13 T17 S17 S18 R19 Q18 Q19 Q17
 0:25 | 0.075 | 21407 | 9.5 | R7 S8 S7 R8 T8 T9 T7 R13 T17 S17 S18 R19 Q18 Q19 Q17
 0:30 | 0.075 | 25555 | 9.7 | R7 S8 S7 R8 T8 T9 T7 R13 T17 S17 S18 R19 Q18 Q19 Q17
 0:35 | 0.075 | 29765 | 9.9 | R7 S8 R8 S7 S6 R6 R5 S5 Q6 T6 R6 R13 T17 S17 S18 *
 0:40 | 0.075 | 33664 | 10.2 | R13 R19 Q18 Q19 R7 R8 S8 S9 S7 Q7 Q8 Q9 L3 L2 Q17
 0:45 | 0.075 | 37488 | 10.1 | R13 R19 Q18 Q19 R7 R8 S8 S9 S7 Q7 Q8 Q9 L3 L2 Q17
SgUctSearch: maximum tree size 6400000 reached
SgUctSearch: pruning nodes with count < 16 (at time 49.1)
SgUctSearch: pruned size: 1347751 (21%) time: 0.1
 0:50 | 0.075 | 41412 | 10.3 | R13 R19 Q18 Q19 R7 R8 S8 S9 S7 Q7 Q8 Q9 L3 L2 Q17
 0:55 | 0.075 | 45529 | 10.3 | R13 R19 Q18 Q19 R7 R8 S8 S9 S7 Q7 Q8 Q9 L3 L2 Q17
 1:00 | 0.075 | 49360 | 10.5 | R13 R19 Q18 Q19 R7 R8 S8 S9 S7 Q7 Q8 Q9 L3 L2 Q17
 1:05 | 0.075 | 53294 | 10.5 | R13 R19 Q18 Q19 R7 R8 S8 S9 S7 Q7 Q8 Q9 L3 L2 Q17
 1:10 | 0.075 | 57562 | 10.4 | R13 R19 Q18 Q19 R7 R8 S8 S9 S7 Q7 Q8 Q9 L3 L2 Q17
 1:15 | 0.075 | 61683 | 10.4 | R13 R19 Q18 Q19 R7 R8 S8 S9 S7 Q7 Q8 Q9 L3 L2 Q17
 1:20 | 0.075 | 65855 | 10.5 | R13 R19 Q18 Q19 R7 R8 S8 S9 S7 Q7 Q8 Q9 L3 L2 Q17
 1:25 | 0.075 | 70162 | 10.6 | R7 S8 R8 S7 S6 R6 R5 Q5 Q6 T6 T17 S17 S18 R13 R12 *
SgUctSearch: maximum tree size 6400000 reached
SgUctSearch: pruning nodes with count < 16.0 (at time 88.4)
SgUctSearch: pruned size: 2319505 (36%) time: 0.1
 1:30 | 0.075 | 74432 | 10.7 | R7 S8 R8 S7 S6 R6 R5 Q5 Q6 T6 T17 S17 S18 R13 R12 *
 1:35 | 0.075 | 78555 | 10.7 | R7 S8 R8 S7 S6 R6 R5 Q5 Q6 T6 T17 S17 S18 R13 R12 *
 1:40 | 0.075 | 82880 | 10.8 | R7 S8 R8 S7 S6 R6 R5 Q5 Q6 T6 T17 S17 S18 R13 R12 *
 1:45 | 0.074 | 87251 | 10.8 | R7 S8 R8 S7 S6 R6 R5 Q5 Q6 T6 T17 S17 S18 R13 R12 *
 1:50 | 0.074 | 91625 | 10.8 | R7 S8 R8 S7 S6 R6 R5 Q5 Q6 T6 T17 S17 S18 R13 R12 *
 1:55 | 0.074 | 96048 | 10.8 | R7 S8 R8 S7 S6 R6 R5 Q5 Q6 T6 T17 S17 S18 R13 R12 *
SgUctSearch: maximum tree size 6400000 reached
SgUctSearch: pruning nodes with count < 16.0 (at time 118.7)
SgUctSearch: pruned size: 3074330 (48%) time: 0.1
 2:00 | 0.074 | 100395 | 10.9 | R7 S8 R8 S7 S6 R6 R5 Q5 Q6 T6 T17 S17 S18 R13 R12 *
 2:05 | 0.074 | 104775 | 10.9 | R7 S8 R8 S7 S6 R6 R5 Q5 Q6 T6 T17 S17 S18 R13 R12 *
 2:10 | 0.074 | 109125 | 10.9 | R7 S8 R8 S7 S6 R6 R5 Q6 T17 S17 S18 R13 T5 S5 T7 *
 2:15 | 0.074 | 113433 | 11.0 | R7 S8 R8 S7 S6 R6 R5 Q6 T17 S17 S18 R13 T5 S5 T7 *
 2:20 | 0.074 | 117231 | 11.0 | R7 S8 R8 S7 S6 R6 R5 Q6 T17 S17 S18 R13 T5 S5 T7 *
SgUctSearch: maximum tree size 6400000 reached
SgUctSearch: pruning nodes with count < 16.0 (at time 144.4)
SgUctSearch: pruned size: 3647348 (56%) time: 0.1
 2:25 | 0.074 | 121063 | 11.0 | R7 S8 R8 S7 S6 R6 R5 Q6 T17 S17 S18 R13 T5 S5 T7 *
 2:30 | 0.074 | 125254 | 11.0 | R7 S8 R8 S7 S6 R6 R5 Q6 T17 S17 S18 R13 T5 S5 T7 *
 2:35 | 0.074 | 129252 | 11.1 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T6 T7 T6 S6 T17 *
 2:40 | 0.074 | 133146 | 11.1 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T6 T7 T6 S6 T17 *
 2:45 | 0.074 | 137294 | 11.1 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T6 T7 T6 S6 T17 *
SgUctSearch: maximum tree size 6400000 reached
SgUctSearch: pruning nodes with count < 32.0 (at time 166.2)
SgUctSearch: pruned size: 1080921 (16%) time: 0.0
 2:50 | 0.074 | 141186 | 11.1 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T6 T7 T6 S6 T17
 2:55 | 0.074 | 145273 | 11.1 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 3:00 | 0.074 | 149471 | 11.1 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 3:05 | 0.074 | 153594 | 11.1 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 3:10 | 0.074 | 157720 | 11.2 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 3:15 | 0.074 | 161805 | 11.2 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 3:20 | 0.074 | 165895 | 11.2 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 3:25 | 0.074 | 169927 | 11.2 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
SgUctSearch: maximum tree size 6400000 reached
SgUctSearch: pruning nodes with count < 16.0 (at time 208.3)
SgUctSearch: pruned size: 2607287 (40%) time: 0.1
 3:30 | 0.074 | 173480 | 11.2 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 3:35 | 0.074 | 177525 | 11.2 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 3:40 | 0.074 | 181687 | 11.2 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 3:45 | 0.074 | 185938 | 11.3 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 3:50 | 0.074 | 190267 | 11.3 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 3:55 | 0.074 | 194262 | 11.3 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
SgUctSearch: maximum tree size 6400000 reached
SgUctSearch: pruning nodes with count < 16.0 (at time 238.1)
SgUctSearch: pruned size: 3340552 (52%) time: 0.1
 4:00 | 0.074 | 198465 | 11.3 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 4:05 | 0.074 | 202465 | 11.4 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 4:10 | 0.074 | 205582 | 11.4 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T17 S17 S18 R13 R12 *
 4:15 | 0.074 | 209566 | 11.4 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T6 T7 T17 S17 S18 *
 4:20 | 0.074 | 213459 | 11.4 | R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T6 T7 T17 S17 S18 *
SgUctSearch: move cannot change anymore
Count          213672
GamesPlayed    213672
Nodes          5954577
Time           2.6e+02
GameLen        186.0 dev=10.0 min=8.0 max=237.0
InTree         11.4 dev=3.6 min=0.0 max=28.0
Aborted        0%
Games/s        820.9
Value          0.07
Sequence       R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T6 T7 T17 S17 S18 R13 H15 
TimeInitTree   0.00
TimeRootFilter 0.00
GoUctPlayer::Ponder: end
genmove W
SgDefaultTimeControl: timeLeft=20.0/1 remaining=1.0 timeMove=20.0
GoUctPlayer: Reusing 3794605 nodes (63%)
SgUctSearch: move cannot change anymore
Count          214555
GamesPlayed    883
Nodes          3933247
Time           1
GameLen        187.6 dev=9.5 min=161.0 max=222.0
InTree         11.8 dev=3.2 min=4.0 max=21.0
Aborted        0%
Games/s        870.6
Value          0.07
Sequence       R7 S8 R8 S7 S6 R6 R5 Q6 T5 S5 T6 T7 T17 S17 S18 R13 H15 
TimeInitTree   0.09
TimeRootFilter 0.00
= resign

[herzbube]

Changing the resign threshold has no effect whatsoever on Mac OS X. Fuego resigns even if the resign threshold is set to 0:

uct_param_player resign_threshold 0.000000

This happens both for the "Fuego trunk" build, and for the "Fuego on iOS" build. Very strange.

[dtsudo]

Thanks for the reply! It seems like based on your comments, perhaps this is an issue within Fuego itself (rather than Little Go's usage of Fuego).

I wanted to elaborate more on my hypothesis that this is related to handicap stones.

When an even game is being played, it doesn't appear that Fuego ever resigns a won game. Attached (EvenGame_WhiteWinBy0.5.txt) is a no-handicap game where White wins by only 0.5 points. When Fuego is given control of White, Fuego simply passes since it knows it has won.

In contrast, when an even game is lost (EvenGame_WhiteLosesBy1.5.txt), Fuego plays a few futile moves and then resigns.

In summary, for an even game, Fuego behaves as expected (at least for the two attached games here).

Then, I tried a 3-stone handicap game. Here, when Fuego is winning by 4.5 points (3Handicap_WhiteWinsBy4.5.txt), Fuego happily passes its turn. However, when Fuego is winning by only 2.5 points (3Handicap_WhiteWinsBy2.5.txt), Fuego will resign (despite being ahead by 2.5 points).

Moving on to a 6-handicap game, when Fuego is winning by 7.5 points (6Handicap_WhiteWinsBy7.5.txt), it's happy to pass its turn. But when it's winning by only 5.5 points (6Handicap_WhiteWinsBy5.5.txt), Fuego will resign.

Finally, at 9-stone handicap, Fuego requires a winning margin of 10.5 points before it will stop resigning. (9Handicap_WhiteWinsBy10.5.txt; 9Handicap_WhiteWinsBy8.5.txt)

Based on these observations, it seems like the threshold for which Fuego stops resigning depends on how many handicap stones it has. Admittedly, the hypothesis has some flaws though; for instance, in a 9-stone handicap game, White gets 8 points of compensation; but even if this weren't so (i.e. White got 0 points of compensation), it should still be clear that the 8.5-point win is still a win (albeit now it's only a 0.5 point win).

[herzbube]

@dtsudo Forget everything I said above - you were totally right, and I was wrong. There is indeed a configuration option which tells Fuego to include or exclude handicap compensation in its score calculations, and as you suspected the option by default is set to exclude compensation.

The bug therefore is Little Go's, because the app never sets the option to its correct value when area scoring is in force.

go_param_rules extra_handicap_komi 1

Obviously this will be fixed in the upcoming release (which I hope will hit the App Store in the next two weeks or so).

[dtsudo]

Cool; thanks so much for resolving the issue! Little Go is definitely the best iOS Go app out there, and I'm looking forward to the upcoming release :)

[herzbube]

It's interesting to see that if a ruleset is chosen that uses the territory scoring system, then Fuego again starts resigning. This is a clear indicator that Fuego is not able to properly count with territory scoring, as mentioned in the manual in the "Scoring" section under "Why area scoring is the default".

[herzbube]

@dtsudo Unless you object I'm going to add you to the in-game credits list. If you would like to appear under your real name rather than "dtsudo" let me know via private message (herzbube at herzbube dot ch).

[dtsudo]

Cool; thanks @herzbube !