124. Chew (3k) vs Fuego (Bot)

perceval · Post by **perceval** » Fri Jul 01, 2011 2:02 am

topazg wrote:
If we're talking about sufficient data points to improve play beyond chance, then I suspect 1 move won't tell us much

What i meant was, for next move, try to run fuego twice, one with min playout 23 , the other 2500 min playout, and see if the chosen move ,and the rate between explored moves, changes.
i propose to do it only for next move because maybe esmeralddemon as a life and no time to run all those experiments for our enjoyment :scratch:

.

Unfortunatly i don t have much time at home those days and compiling/running fuego at work might be a liiittle too much

or i ll try it myself.
Very interesting thread anyway :tmbup:

I really wish i had some time to burn on that.

My previous job was on automated software translation base on statistical algos, it was really a blast, so if i have been able to work on translation without being a linguist, i hope i could work on a MC go engine without knowing how to play.
Unfortunatly i am not sure that go engine dev really pays up the bills ...

Website · Post by **Chew Terr** » Fri Jul 01, 2011 8:10 am

Click Here To Show Diagram Code: [go]$$Bcm31 $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . O . . . . . . . . . | $$ | . . . O . O . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . X . . . . . . . . . . . . . O . . | $$ | . . . . O . . . . . . . . . . X O . . | $$ | . . X . . . . . . . . . . . X O X . . | $$ | . . . . . . . . . . . . . 0 O O X . . | $$ | . . . X . . . . . , . . . X . X . . . | $$ | . . . . . . . . . . . . . . . . X . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . O . . . | $$ | . . . . X X . X . . . . . . X O . . . | $$ | . . X , X O . . . O . . X . . X O . . | $$ | . . . . . O . O . . . . X O X . O . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

Ah, an easy decision. Keep strong, separate. Hope to capture the stones above, but only naturally and as part of a growing framework. Any running battle here seems to benefit me more than it does Fuego. Black can try to hane, but it would leave cutting points for later.

emeraldemon · Post by **emeraldemon** » Fri Jul 01, 2011 9:40 am

I asked the Fuego development mailing list about this, and this is the reply I recieved:

Martin Mueller wrote:Thank you for sharing your experiment. I agree that intuitively, this focus on one move is excessive. There are also some theoretical arguments against it. Still, we do not have anything that works better at the moment. This is definitely worth studying.

One problem with doing this in the whole search tree is that because of the child selection formula, exploring bad moves by doing more exploration costs you performance because of the averaging process. I.e. assume the following situation:
you play Black and have two choices:
move a is very aggressive, but it works and it will win the game immediately by some complex tactics.
move b is solid, and will lead to a quiet, balanced situation, say a .50 score.

To simplify, let's also assume that the opponent's reply to a, White a2, is forced. So let's look at the position when it is Black's turn to play after Black a, White a2. Since the position is very tactical, there is probably only one way for Black to win from here. With low exploration and deep search, the program may discover this win, and most simulations use this move, so the weighted average looks good and move a is selected. But with higher exploration, the program will explore many more of the losing continuations in this subtree, and the average value of a will drop.

I think it is hard (but of course very interesting) to try to fix this problem in general. A simpler approach would be to force more exploration at the root node only. I agree it must be wrong to have say 100 million simulations and spend more than 99 million on the same move.
Here, the tradeoff is between exploring the top move deeper, and exploring alternative moves deeper. I believe that at some stage MoGo was using a different bandit formula for the root node, and they may still do that. But I do not know what they do, or if the details are published. I will meet Olivier next week so I will ask him.

As far as I know no one ever tried different root bandits in Fuego.

Martin

I can certainly still try it if people are curious.

emeraldemon · Post by **emeraldemon** » Fri Jul 01, 2011 10:26 am

Click Here To Show Diagram Code: [go]$$Bcm41 $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . O . . . . . . . . . | $$ | . . . O . O . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . X . . . . . . . . . . . . . O . . | $$ | . . . . O . . . . . . . . . . X O . . | $$ | . . X . . . . . . . . . . . X O X . . | $$ | . . . . . . . . . . . . 1 O O O X . . | $$ | . . . X . . . . . , . . . X . X . . . | $$ | . . . . . . . . . . . . . . . . X . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . O . . . | $$ | . . . . X X . X . . . . . . X O . . . | $$ | . . X , X O . . . O . . X . . X O . . | $$ | . . . . . O . O . . . . X O X . O . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

Compared to last move, this one was an easy decision for fuego. Only took 15 minutes, and 99% of playouts were at that move. Value = 49.9%

Sequence:

Click Here To Show Diagram Code: [go]$$Bcm41 $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . O . . . . . . . . . | $$ | . . . O . O . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . X . . . . . . . . . . . . . O . . | $$ | . . . . O . . . . . . . . . 4 X O . . | $$ | . . X . . . . . . . . 5 . 2 X O X . . | $$ | . . . . . . . . . . . . 1 O O O X . . | $$ | . . . X . . . . . , . . 8 X 3 X . . . | $$ | . . . . . . . . . . . . 0 . . . X . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . 7 . 6 . . . . | $$ | . . . . . . . . . . . . . . . O . 9 . | $$ | . . . . X X . X . . . . . . X O . . . | $$ | . . X , X O . . . O . . X . . X O . . | $$ | . . . . . O . O . . . . X O X . O . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

seems pretty much forced, and :b43:

is solid, if a little slow. But I doubt white should play :w44:

. It seems a bit too slow for the situation. Also I've noticed black often considers the slide at :b49:

, it seems to be a large point to take.

Website · Post by **Chew Terr** » Fri Jul 01, 2011 11:40 am

Click Here To Show Diagram Code: [go]$$Bcm41 $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . O . . . . . . . . . | $$ | . . . O . O . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . X . . . . . . . . . . . . . O . . | $$ | . . . . O . . . . . . . 4 . . X O . . | $$ | . . X . . . . . . . . . 3 2 X O X . . | $$ | . . . . . . . . . . . . X O O O X . . | $$ | . . . X . . . . . , . . . X . X . . . | $$ | . . . . . . . . . . . . . . . . X . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . O . . . | $$ | . . . . X X . X . . . . . . X O . . . | $$ | . . X , X O . . . O . . X . . X O . . | $$ | . . . . . O . O . . . . X O X . O . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

Yeah, black gets a couple of good forcing moves here to harm my framework, but at least it will have to go back and fix the cutting point after. I know computer triggers don't work per se, but if black takes 43, I call dibs on 44.

flOvermind · Post by **flOvermind** » Fri Jul 01, 2011 1:07 pm

emeraldemon wrote:
Well, Fuego isn't capable of wishful thinking in the way humans are: it uses the exact same algorithm do choose both white and black moves, so it can't hope for the opponent to play poorly, the way a human can. That said, it can certainly miss tesuji and play poorly in the tree and in the playouts. The hope is that it will make mistakes in roughly equal amount for both sides, so that the board evaluation is correct.

emeraldemon · Post by **emeraldemon** » Fri Jul 01, 2011 2:37 pm

Fuego doesn't accept your trigger!

Click Here To Show Diagram Code: [go]$$Bcm41 $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . O . . . . . . . . . | $$ | . . . O . O . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . X . . . . . . . . . . . . . O . . | $$ | . . . . O . . . . . . . . . . X O . . | $$ | . . X . . . . . . . . . . O X O X . . | $$ | . . . . . . . . . . . . X O O O X . . | $$ | . . . X . . . . . , . . . X 3 X . . . | $$ | . . . . . . . . . . . . . . . . X . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . O . . . | $$ | . . . . X X . X . . . . . . X O . . . | $$ | . . X , X O . . . O . . X . . X O . . | $$ | . . . . . O . O . . . . X O X . O . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

Value = 50.6%

Thought for 15:33, another relatively quick decision. 93% of playouts were spent on the chosen move. Here's the sequence it's thinking of:

Click Here To Show Diagram Code: [go]$$Bcm43 $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . O . . . . . . . . . | $$ | . . . O . O . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . 7 8 . . | $$ | . . X . . . . . . . . . . 6 . . O . . | $$ | . . . . O . . . . . . . . . . X O . . | $$ | . . X . . . . . . . 9 . 2 O X O X . . | $$ | . . . . . . . . . . . 3 X O O O X . . | $$ | . . . X . . . . . , . . . X 1 X . . . | $$ | . . . . . . . . . . . . . . . . X . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . O . . . | $$ | . . . . X X . X . . . . . . X O . . . | $$ | . . X , X O . . . O . . X 5 . X O . . | $$ | . . . . . O . O . . . . X O X . O . . | $$ | . . . . . . . . . . . . . 4 . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

The move Chew triggered recieved 23,618 playouts, which is about 0.6% of the total. I think Chew's move was better, but I'm not certain. I'm also not sure who's winning. As black I would be very tempted to try a move like Q17, or maybe R17. But that may be an overplay...

Website · Post by **Chew Terr** » Fri Jul 01, 2011 2:52 pm

Click Here To Show Diagram Code: [go]$$Bcm41 $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . O . . . . . . . . . | $$ | . . . O . O . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . X . . . . . . . . . . . . . O . . | $$ | . . . . O . . . . . . . . . . X O . . | $$ | . . X . . . . . . . . . 4 O X O X . . | $$ | . . . . . . . . . . . . X O O O X . . | $$ | . . . X . . . . . , . . . X X X . . . | $$ | . . . . . . . . . . . . . . . . X . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . O . . . | $$ | . . . . X X . X . . . . . . X O . . . | $$ | . . X , X O . . . O . . X . . X O . . | $$ | . . . . . O . O . . . . X O X . O . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

Huh, interesting. I suppose I may as well grow the top. I still have the interesting aji below, but this move is pretty large, as my opponent can take it in sente at will if I don't right now... Jumping up from below and jumping down from above are getting big, as is the slide in the bottom left.

Numsgil · Post by **Numsgil** » Fri Jul 01, 2011 4:43 pm

emeraldemon · Post by **emeraldemon** » Sat Jul 02, 2011 7:48 am

Click Here To Show Diagram Code: [go]$$Bcm41 $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . O . . . . . . . . . | $$ | . . . O . O . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . X . . . . . . . . . . . . . O . . | $$ | . . . . O . . . . . . . . . . X O . . | $$ | . . X . . . . . . . . . O O X O X . . | $$ | . . . . . . . . . . . 5 X O O O X . . | $$ | . . . X . . . . . , . . . X X X . . . | $$ | . . . . . . . . . . . . . . . . X . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . O . . . | $$ | . . . . X X . X . . . . . . X O . . . | $$ | . . X , X O . . . O . . X . . X O . . | $$ | . . . . . O . O . . . . X O X . O . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

value = 51.2%

Click Here To Show Diagram Code: [go]$$Bcm45 $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . O . . . . . . . . . | $$ | . . . O . O . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . X . . . . . . . . . . . . . O . . | $$ | . . . . O . . . . . . . . . 4 X O . . | $$ | . . X . . . . . . . . . O O X O X . . | $$ | . . . . . . . . . 0 . 1 X O O O X . . | $$ | . . . X . . . . . , . . . X X X . . . | $$ | . . . . . . . . . . . . . . . . X . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . 8 O . . . | $$ | . . . . X X . X . . . . . . X O . . . | $$ | . . X , X O . . . O . . X 3 . X O . . | $$ | . . . . . O . O . . 6 . X O X . O . . | $$ | . . . . . . . . . 5 7 . 9 2 . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

I agree with Numsgil, I prefer white here. I think judging from the sequences Fuego is predicting, we can get some hints as to why it overestimates its own chances. For example, it shows white capturing the stone at :w48:

, probably because in playouts those stones have enough aji to be useful. But in practice, I don't think Chew needs to make that capture, and it's hard to see what black can do to crack that moyo. Also, as mentioned before, Fuego still thinks white will descend with :W46: , but Chew said he would push up, which leaves more cutting points.

This is the tricky part about using MC to evaluate: any time those black stones on top survive, or maybe the white group on the bottom dies, black will win that playout, even if with proper play it can't happen.

perceval · Post by **perceval** » Mon Jul 04, 2011 3:17 am

Here is what i understand of Fuego process, which might be really wrong:
-it uses the UTC algo ie generate random playouts, with a preferences to explore moves that seems to be better.
ez4u asked why in the number of playout the min seemed to be 23.
my guess is that a minimum value to get a rough estimate of the winning % of each node.

However 23 playouts gives a huge error bar on winning ratio (10%).

Increasing to, say 2500 would take little time (300*2500*=750000 playout, much less than the total number played) and decrease the error bar to 1%

i would like to know if changing this value would change the exploration rates and the final move ?
it should not of course but i wonder how the search tree would be modified.

Esmeralddemon, if you know how to change this value, would you have time to run the 2 search with 23 and 2500 as min playout for next move to see if there is a difference ?

it might be a part of the horizon "effect" ie the fact that increasing the thinking time does not linearly increase the playing strength because a good move might be discarded early because of lack of luck in early explorations. (or more complicated effects such as: its a good move but only following a very narrow tactical path that a few random playouts are unlikely to find).
Woudl you find this experiment interesting ?

flOvermind · Post by **flOvermind** » Mon Jul 04, 2011 8:05 am

The problem with increasing the minimum playouts of each move is that this involves an exponential decrease in the statistical coverage of the followup moves.

Making 1500 playouts once is not that much, but 1500 playouts for each move at each expanded node is quite a lot. With normal tree traversal that would translate to an exponential increase in time, but the nature of the UCT algorithm's playouts means effectively that the total amount of playouts choosing "good" nodes decreases, while the time remains constant. That means the child nodes will get expanded later (on average), and the maximum tree depth decreases.

Effectively, you're making the search tree more balanced. That makes the horizon effect worse instead of better

Of course it would be interesting to find a good balance between discarding bad nodes early, and increasing the accuracy when deciding what nodes are bad. But 1500 feels a lot too high.

emeraldemon · Post by **emeraldemon** » Mon Jul 04, 2011 10:01 am

perceval wrote:
Increasing to, say 2500 would take little time (300*2500*=750000 playout, much less than the total number played) and decrease the error bar to 1%

The trouble is that the UCT algorithm doesn't treat the root node differently from any other node in the search tree. So it wouldn't be +750000 playouts, it would be +750000 playouts per move (which is why fl0vermind said the increase is exponential). The response from Martin Mueller suggested the possibility of changing the algorithm to treat the root node differently, but it would be a nontrivial change to the source code.

That said, there is a specific exploration/exploitation tradeoff parameter I can tweak and play with. I will try some different values for the next move, see what it does.
However, as topazg pointed out. It's easy to see if the program plays differently, but not so easy to tell if it plays better.

perceval · Post by **perceval** » Mon Jul 04, 2011 1:37 pm

o ok i though there was something special about the first node because of those 23 playouts for all nodes.

Mike Novack · Post by **Mike Novack** » Mon Jul 04, 2011 5:29 pm

perceval wrote:ez4u asked why in the number of playout the min seemed to be 23.
my guess is that a minimum value to get a rough estimate of the winning % of each node.

However 23 playouts gives a huge error bar on winning ratio (10%).

Ah, but does an error bar of that size hurt anything? At this point all that is being done is pruning the worst nodes from the tree. Not yet selecting the best. All that is needed is that the right node (the move ultimately decided upon) not get pruned early.

For example, if that first pruning process didn't remove anything with a score over half of the highest score then that possible 10% error wouldn't much.

Life In 19x19

124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)