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 .
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 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 ...
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.
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Fri Jul 01, 2011 9:40 am
by emeraldemon
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.
seems pretty much forced, and is solid, if a little slow. But I doubt white should play . It seems a bit too slow for the situation. Also I've noticed black often considers the slide at , it seems to be a large point to take.
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.
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Fri Jul 01, 2011 1:07 pm
by flOvermind
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.
Of course, I'm aware of that Fuego uses the same algorithm for the answers than it uses for its own moves, so it should theoretically assume the same moves it would play itself. But in practice that doesn't need to be the case: For each move deeper in the tree, there is less computation time for the individual moves. And with the massive branching factor of go, that might make a big difference.
Of course that doesn't necessarily mean that the first move is bad, since the mistakes for both sides should cancel out. That's the basic assumption of the MC playout strategy. But it does tell us something about the usefulness of MC engines for analysis
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...
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Fri Jul 01, 2011 2:52 pm
by Chew Terr
$$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]$$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.
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Fri Jul 01, 2011 4:43 pm
by Numsgil
I really don't like black's last few moves. And I have very specific reasons
1. They build thickness but the influence isn't all that helpful since white has a pretty solid bottom right corner. 2. It sort of builds a center moyo for black, but black's construction has holes in it. 3. It helps white build his own moyo, and white's construction doesn't really have leaks like black's does. 4. It makes invasions of white's moyo harder for black. Before these last few exchanges, the top right region was open for invasion (since it has 21+ open points and no roof), but after this exchange the roof is starting to close.
The whole thing strikes me as playing without a plan Which I guess makes sense given the MC nature of play. I wonder if any strong players like the last several exchanges for black.
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Sat Jul 02, 2011 7:48 am
by emeraldemon
$$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]$$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 , 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.
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Mon Jul 04, 2011 3:17 am
by perceval
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 ?
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Mon Jul 04, 2011 8:05 am
by flOvermind
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.
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Mon Jul 04, 2011 10:01 am
by emeraldemon
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.
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Mon Jul 04, 2011 1:37 pm
by perceval
o ok i though there was something special about the first node because of those 23 playouts for all nodes.
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Mon Jul 04, 2011 5:29 pm
by Mike Novack
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.
.
or i ll try it myself.
seems pretty much forced, and 
is solid, if a little slow. But I doubt white should play 
. It seems a bit too slow for the situation. Also I've noticed black often considers the slide at 
, it seems to be a large point to take.
, 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.