[computer-go] UCT and solving life and death
Michael Williams
michaelwilliams75 at gmail.com
Fri Feb 1 07:26:42 PST 2008
David Fotland wrote:
> Since you hijacked my thread, I'm changing the title and injecting some data
> :)
>
> I tried to be very clear that I didn't want that thread to become another
> scalability flame fest.
>
> Here is a high level mogo game, level 15 vs level 16, that hinges on a life
> and death problem that mogo gets wrong over and over again.
>
> I added some comments in the sgf file. White lets a big group die, tehn
> both side play like they think it's alive, then finally black gives the game
> away and loses.
>
> It's clear mogo has a long way to go when a life/death problem includes a
> big eye.
>
> David
Please read this email with a fixed-width font (paste into notepad or something).
I did some further analysis with MoGo on the move that David says lost the game. Here is the board:
A B C D E F G H J
+---------------------------+
9 | . . . . . . . . . |
8 | . O O O . . . . . |
7 | @ @ @ O . . . . . |
6 | . O @ O . . @ @ . |
5 | . O O @ @ . @ O @ |
4 | . O @ @ . @ O . . |
3 | . @ @ O O O O O . |
2 | . . . @ @ O @ @ O |
1 | . . . . . O . @ . |
+---------------------------+
White to move. MoGo moved at H4 in that game, but the correct move to save the lower-right white group and win the game is J4, followed by some ko threats
(according to David's in-game comments).
I used this command line:
java -jar gtpadapter.jar "./mogo --9 --nbThreads 2 --limitTreeSize 2000000 --collectorLimitTreeSize 1200000 --nbTotalSimulations $1" < test.gtp
I made the tree size as big as I could on my machine. When MoGo finishes it's move generation, it prints some info to stderr like this:
===========================================================================================
0.638770( 5%) || 65443/ 72935(90%)( 6%)(42%/0.37) || 875 |15 || A8 H4 J3 C1 E4 A4 A6 E6 F7 E7 ||SSP:A8 A6 H4 J4 J3 ||PSP:A8 A6 H4 J4 J3
72736 simulations(average length:0) done, time used: 3.46 seconds.(21022.0 games/sec)
A B C D E F G H J A B C D E F G H J
+---------------------------+ +---------------------------------------------------------------------------------+
9 | . . . . . . . . . | | 2.6155 2.6342 2.6240 2.6303 2.6358 2.6348 2.6316 2.6280 2.6214 |
8 | . O O O . . . . . | | 0.6388 2.0000 2.0000 2.0000 2.6339 0.0001 2.6344 2.6324 2.6256 |
7 | @ @ @ O . . . . . | | 2.0000 2.0000 2.0000 2.0000 2.6343 2.6352 2.6262 2.6209 2.6193 |
6 | . O @ O . . @ @ . | | 0.5564 2.0000 2.0000 2.0000 0.2500 0.0001 2.0000 2.0000 0.4623 |
5 | . O O @ @ . @ O @ | | 0.3929 2.0000 2.0000 2.0000 2.0000 2.6198 2.0000 2.0000 2.0000 | White to play
4 | . O @ @ . @ O . . | | 2.6308 2.0000 2.0000 2.0000 0.4953 2.0000 2.0000 0.5911 0.5477 | Black eaten stone(s): 0
3 | . @ @ O O O O O . | | 0.5882 2.0000 2.0000 2.0000 2.0000 2.0000 2.0000 2.0000 0.4614 | White eaten stone(s): 0
2 | . . . @ @ O @ @ O | | 2.6348 2.6367 0.4971 2.0000 2.0000 2.0000 2.0000 2.0000 2.0000 |
1 | . . . . . O . @ . | | 2.6162 0.0001 0.4263 0.4977 0.4444 2.0000 0.0001 2.0000 2.4965 |
+---------------------------+ +---------------------------------------------------------------------------------+
A B C D E F G H J A B C D E F G H J
+---------------------------+ +---------------------------+
9 | . . . . . . . . . | | 0 0 0 0 0 0 0 0 0 |
8 |(O) O O O . . . . . | | 9 9 9 9 0 0 0 0 0 |
7 | @ @ @ O . . . . . | | 10 10 10 9 0 0 0 0 0 |
6 | . O @ O . . @ @ . | | 0 11 10 9 0 0 4 4 0 | Move 40: A8
5 | . O O @ @ . @ O @ | | 0 11 11 7 7 0 4 5 18| Black to play
4 | . O @ @ . @ O . . | | 0 11 7 7 0 3 2 0 0 | Black eaten stone(s): 0
3 | . @ @ O O O O O . | | 0 7 7 2 2 2 2 2 0 | White eaten stone(s): 0
2 | . . . @ @ O @ @ O | | 0 0 0 17 17 2 15 15 16|
1 | . . . . . O . @ . | | 0 0 0 0 0 2 0 15 0 |
+---------------------------+ +---------------------------+
===========================================================================================
The upper-right grid represents the winrate for color-to-play for each move (values > 1 are invalid due to the move not being considered).
Row 4 is the interesting row because both the MoGo move and the correct move are on it. So here is that row slice from each test run while varying
nbTotalSimulations (which is shown in the first column):
A B C D E F G H J
000065536: | 2.6308 2.0000 2.0000 2.0000 0.4953 2.0000 2.0000 0.5911 0.5477 |
000131072: | 0.3043 2.0000 2.0000 2.0000 0.3854 2.0000 2.0000 0.5509 0.4671 |
000262144: | 0.3333 2.0000 2.0000 2.0000 0.4561 2.0000 2.0000 0.6428 0.5207 |
000524288: | 0.4400 2.0000 2.0000 2.0000 0.5035 2.0000 2.0000 0.6500 0.5293 |
001048576: | 0.4444 2.0000 2.0000 2.0000 0.4000 2.0000 2.0000 0.6543 0.5713 |
002097152: | 0.2500 2.0000 2.0000 2.0000 0.4074 2.0000 2.0000 0.6497 0.5492 |
004194304: | 0.4587 2.0000 2.0000 2.0000 0.5772 2.0000 2.0000 0.6356 0.5662 |
008388608: | 0.0001 2.0000 2.0000 2.0000 0.5716 2.0000 2.0000 0.6559 0.5710 |
016777216: | 0.0001 2.0000 2.0000 2.0000 0.5695 2.0000 2.0000 0.6655 0.5867 |
033554432: | 0.4902 2.0000 2.0000 2.0000 0.5746 2.0000 2.0000 0.6243 0.5818 |
067108864: | 0.5144 2.0000 2.0000 2.0000 0.5744 2.0000 2.0000 0.7509 0.5828 |
134217728: | 0.5141 2.0000 2.0000 2.0000 0.5802 2.0000 2.0000 0.8748 0.5812 |
268435456: | 0.4905 2.0000 2.0000 2.0000 0.5866 2.0000 2.0000 0.9378 0.5813 |
As you can see, MoGo favors the incorrect move even more strongly as nbTotalSimulations goes up. But the correct move is also seen more favorably.
MoGo also tells you the best move sequence for it's prefered move. For the longest test I ran (nbTotalSimulations==268435456), MoGo gives this sequence:
H4 J4 J3 C1 J6 J5 A8 G7 F7 G8
And here is the full grid of winrates for the longest test:
A B C D E F G H J A B C D E F G H J
+---------------------------+ +---------------------------------------------------------------------------------+
9 | . . . . . . . . . | | 0.3577 0.5383 0.4772 0.5310 0.5539 0.5132 0.5207 0.4801 0.4292 |
8 | . O O O . . . . . | | 0.6103 2.0000 2.0000 2.0000 0.4924 0.5478 0.5076 0.5155 0.4214 |
7 | @ @ @ O . . . . . | | 2.0000 2.0000 2.0000 2.0000 0.5398 0.5431 0.4999 0.4534 0.4115 |
6 | . O @ O . . @ @ . | | 0.5819 2.0000 2.0000 2.0000 0.5513 0.5695 2.0000 2.0000 0.5714 |
5 | . O O @ @ . @ O @ | | 0.3448 2.0000 2.0000 2.0000 2.0000 0.4569 2.0000 2.0000 2.0000 |
4 | . O @ @ . @ O . . | | 0.4905 2.0000 2.0000 2.0000 0.5866 2.0000 2.0000 0.9378 0.5813 |
3 | . @ @ O O O O O . | | 0.5070 2.0000 2.0000 2.0000 2.0000 2.0000 2.0000 2.0000 0.5936 |
2 | . . . @ @ O @ @ O | | 0.3750 0.4802 0.6080 2.0000 2.0000 2.0000 2.0000 2.0000 2.0000 |
1 | . . . . . O . @ . | | 0.3984 0.3774 0.5944 0.5316 0.5746 2.0000 0.4040 2.0000 0.1931 |
+---------------------------+ +---------------------------------------------------------------------------------+
I would like to repeat the test with a much larger tree on a machine with much more memory, but MoGo begins to act strange with huge trees.
More information about the computer-go
mailing list