Life In 19x19 :: Bots with pro level endgame

Life In 19x19 http://www.lifein19x19.com/

Bots with pro level endgame http://www.lifein19x19.com/viewtopic.php?f=18&t=13818	Page 1 of 1

Author:	LovelyLull [ Thu Nov 24, 2016 7:24 pm ]
Post subject:	Bots with pro level endgame
A few years ago, when top bots were 5D or so, many people on KGS were claiming that some bots had pro level endgames. It seems to me that Zen lost to Cho Chikun in games 1 and 3, in large part because of endgame mistakes. So I'm just curious whether people were talking nonsense or if bots already had pro level endgame.

Author:	DrStraw [ Thu Nov 24, 2016 7:41 pm ]
Post subject:	Re: Bots with pro level endgame
I have no answer to your question but it seems to me that it should be the one area where computers would be expected to be superior. Once the game is down to the last few moves it should be possible to read out every possibility and never go wrong.

Author:	Go_Japan [ Thu Nov 24, 2016 8:09 pm ]
Post subject:	Re: Bots with pro level endgame
LovelyLull wrote: A few years ago, when top bots were 5D or so, many people on KGS were claiming that some bots had pro level endgames. It seems to me that Zen lost to Cho Chikun in games 1 and 3, in large part because of endgame mistakes. So I'm just curious whether people were talking nonsense or if bots already had pro level endgame. I actually think Zen started playing endgame moves when in fact, there were still some areas that were not completely settled. To me, it seems that zen both won and lost in the middle game. I agree with DrStraw that computers should be really good at the endgame, but I don't think any of these games actually got to the endgame stage. In my experience playing bots, computers are punishing in the endgame stage. If you make a mistake on value or give up sente in error, they will just punish you.

Author:	pookpooi [ Thu Nov 24, 2016 8:56 pm ]
Post subject:	Re: Bots with pro level endgame
Is it because Zen play in Japanese rule? Zen may miss count some territories. If in Chinese rule everything is clear, at least to the human eyes.

Author:	yoyoma [ Thu Nov 24, 2016 9:46 pm ]
Post subject:	Re: Bots with pro level endgame
I don't agree with the idea that since it's the endgame there are very few variations to play. Even when in the 1 point stage, there are many 0 point dames, weaknesses in your own territory that may or may not need defending, invasions in enemy territory that may or may not work. There will probably be well over 100 legal moves for the computer to consider even on the very last endgame move of the game before passing. It's impossible for the computer to brute force this. The computer has to prune the tree to have any hope. A human will easily prune the tree to the relevant endgame moves but a computer may make mistakes in the pruning.

Author:	RobertJasiek [ Thu Nov 24, 2016 10:48 pm ]
Post subject:	Re: Bots with pro level endgame
LovelyLull wrote: A few years ago, when top bots were 5D or so "or so" - ok. 5d we cannot know because access to those bots was too restricted and so ratings too uncertain.

Author:	Bill Spight [ Fri Nov 25, 2016 12:11 am ]
Post subject:	Re: Bots with pro level endgame
I am skeptical about the level of endgame play by strong bots. Michael Redmond pointed out that they often make local mistakes (from the point of view of humans). There is an example where Zen loses two extra points in a semeai (White 144 in game 1 vs. Cho Chihoon. Correct local play is to descend to the edge, not to hane.). Giving away two points in the middle game does not increase the probability of winning the game, no matter what Monte Carlo Tree Search may suggest. In the endgame where the game breaks up into independent or quasi-independent regions, correct global play is almost always one of the correct local plays. Strong programs often make silly endgame plays (to human eyes). Sometimes such plays are defended by claiming that they actually increase the probability of winning the game, and humans are misjudging those plays because we do not think like the programs do. I remain unconvinced. On two counts. First, humans do think about the probability of winning the game. Second, the main way that humans evaluate endgame plays is in terms of fuzziness, not probability, and that may be a superior approach. Also, in the endgame the depth of Monte Carlo playouts can still be a couple of hundred moves, with plenty of possibilities for error.

Author:	pookpooi [ Fri Nov 25, 2016 1:05 am ]
Post subject:	Re: Bots with pro level endgame
RobertJasiek wrote: "or so" - ok. 5d we cannot know because access to those bots was too restricted and so ratings too uncertain. Nice article that tackle this problem (not that precise, but at least he try) for people who think KGS rank is not a good indicator http://www.computer-go.info/h-c/graph.html But for people who think KGS rank still hold some merits, last year Zen19S achieve 5D with 20min maintime and 30s byoyomi time setting.

Author:	hyperpape [ Fri Nov 25, 2016 8:58 am ]
Post subject:	Re: Bots with pro level endgame
Even if it is true that Monte Carlo shenanigans raise the winning probability (according to Monte Carlo evaluation, not objectively!) that would give us no reason to call the results pro-level, correct or even good endgame. It's simply bad endgame that the bots know won't hurt their chance of winning.

Author: Bill Spight [ Fri Nov 25, 2016 9:28 am ]

Post subject: Re: Bots with pro level endgame

Here is the local sequence of play in game 1 starting with White 144.

Click Here To Show Diagram Code: [go]$$Wcm44 Zen loses 2 points locally $$ --------------------------------------- $$ | . . O X b . 5 W . 2 1 3 6 . . . . . . | $$ | . O . O X . W X X X X O X . . X X . . | $$ | . . O . X . W W X . O O 4 X . O . O . | $$ | . O . , X . . W X X O X . X O , O . . | $$ | . X O O X . . a O O X X . X . O X . . | $$ | . X X X O . . . O X O . . . . O X . . | $$ | . . . . . . . . . . . O . O O O X . . | $$ | . . . . . . . . . . . . O X . X X . . | $$ | . . . . X . . . O . . . O X . X . . . | $$ | . . . , O X X . O X . O X X O X O . . | $$ | . . X X X O X . . . . O X . . O . . . | $$ | . . O . O O O X X X . X X O . . . . . | $$ | . . X O . X X O O X . . X . . O O . . | $$ | . . X . . . O . . O O . O O O X X X . | $$ | . . X O . . . . . . . . . . X X . O O | $$ | . . X O . . . . . , . . . . X O O O X | $$ | . . O . . O . . . . . O . . X O . X X | $$ | . . . . . . . . . . . . . . X O O X . | $$ | . . . . . . . . . . . . . . . . . X . | $$ ---------------------------------------[/go]

OC, White loses the semeai. But he also unnecessarily loses the :w44:

stone.

at 46 also allows White to take his kikashi in sente, but loses only 5 stones instead of 6.

White has a cutting point at "a", and :w48:

protects the :wc:

stones by the possibility of connecting them with a play at "b".

Why would a Monte Carlo based bot pick :w44:

over

. I don't know, it may have been a random error, but here is a hypothesis.

Click Here To Show Diagram Code: [go]$$Wc Fill the outside liberty $$ --------------------------------------- $$ | . . O X . . . O 3 . 4 1 . . . . . . . | $$ | . O . O X . O X X X X O X . . X X . . | $$ | . . O . X . O O X . O O 2 X . O . O . | $$ | . O . , X . . O X X O X . X O , O . . | $$ | . X O O X . . . O O X X . X . O X . . | $$ | . X X X O . . . O X O . . . . O X . . | $$ | . . . . . . . . . . . O . O O O X . . | $$ | . . . . . . . . . . . . O X . X X . . | $$ | . . . . X . . . O . . . O X . X . . . | $$ | . . . , O X X . O X . O X X O X O . . | $$ | . . X X X O X . . . . O X . . O . . . | $$ | . . O . O O O X X X . X X O . . . . . | $$ | . . X O . X X O O X . . X . . O O . . | $$ | . . X . . . O . . O O . O O O X X X . | $$ | . . X O . . . . . . . . . . X X . O O | $$ | . . X O . . . . . , . . . . X O O O X | $$ | . . O . . O . . . . . O . . X O . X X | $$ | . . . . . . . . . . . . . . X O O X . | $$ | . . . . . . . . . . . . . . . . . X . | $$ ---------------------------------------[/go]

After the descent, :w1:

is normal play, winning the semeai.

Click Here To Show Diagram Code: [go]$$Wc Do not fill the outside liberty $$ --------------------------------------- $$ | . . O X . . . O 3 . 1 . . . . . . . . | $$ | . O . O X . O X X X X O X . . X X . . | $$ | . . O . X . O O X . O O 2 X . O . O . | $$ | . O . , X . . O X X O X . X O , O . . | $$ | . X O O X . . . O O X X . X . O X . . | $$ | . X X X O . . . O X O . . . . O X . . | $$ | . . . . . . . . . . . O . O O O X . . | $$ | . . . . . . . . . . . . O X . X X . . | $$ | . . . . X . . . O . . . O X . X . . . | $$ | . . . , O X X . O X . O X X O X O . . | $$ | . . X X X O X . . . . O X . . O . . . | $$ | . . O . O O O X X X . X X O . . . . . | $$ | . . X O . X X O O X . . X . . O O . . | $$ | . . X . . . O . . O O . O O O X X X . | $$ | . . X O . . . . . . . . . . X X . O O | $$ | . . X O . . . . . , . . . . X O O O X | $$ | . . O . . O . . . . . O . . X O . X X | $$ | . . . . . . . . . . . . . . X O O X . | $$ | . . . . . . . . . . . . . . . . . X . | $$ ---------------------------------------[/go]

However, after the hane, filling the outside liberty is a mistake, allowing White to win the semeai. I suspect that in Monte Carlo randomized playouts, Black will lose the semeai more often after the hane than after the descent and thus the program will assign the hane a higher probability of winning the game. I do not think that this error would occur if the tree search were confined locally, but it is global. Claims that Monte Carlo bots correctly assess the probability of winning the game must be taken with a grain of salt.

Author:	Bill Spight [ Fri Nov 25, 2016 9:59 am ]
Post subject:	Re: Bots with pro level endgame
One reason why a fuzzy approach may be better than a probabilistic approach in the endgame. Consider the following partial board position, in which the Black stones are alive. Click Here To Show Diagram Code `[go]$$Wc Miai $$ \| . . . . . . . . . \| $$ \| . X X X X X X X . \| $$ \| X X O O O O O X X \| $$ \| W . O . O . O . W \| $$ -------------------[/go]` Human go players consider the two corner positions to be miai. No matter who plays first, Black can capture one of the stones and White can save the other one, resulting in 2 points for Black. OC, in some ko sequences one player may get in both plays. But consider the result with randomized global playouts. Then we may expect that 25% of the time Black will capture both stones, for 4 points, 25% of the time White will save both stones, for 0 points, and 50% of the time Black will capture one stone and White will save the other, for 2 points. The average result is the same, but the variance is larger, and that could affect the calculated probability of winning a close game and introduce error. By fuzzy logic we may consider the value of each corner as a fuzzy 1 point for Black, ranging from 0 to 2 points. Treating the corners as miai may be considered as a defuzzification resulting in a crisp value of 2 points for the combination of the two positions. Absent a ko fight that destroys the miai, treating the two corners as miai simplifies the tree search and yields a more accurate final result than not doing so.

Page 1 of 1	All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/