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.
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Tue Jul 05, 2011 7:39 am
by Chew Terr
$$Bcm41
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . O . . . . . . . . . |
$$ | . . . O . O . . . , . . . . . O . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . X . . . . . . . . . . . . . O . . |
$$ | . . . . O . . . . . 6 . . . . X O . . |
$$ | . . X . . . . . . . . . O O X O X . . |
$$ | . . . . . . . . . . . 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 . . . . . a . . . . X O . . |
$$ | . . X . . . . . . . . . O O X O X . . |
$$ | . . . . . . . . . . . 5 X O O O X . . |
$$ | . . . X . f . . . , . . . X X X . . . |
$$ | . . . . . . . . . . . . . . . . X . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . e . . . . . O . . . |
$$ | . . . . X X . X . . . . . . X O . . . |
$$ | . . X , X O . . . O . . X c . X O . . |
$$ | . . b . . O . O . . . . X O X . O . . |
$$ | . . . d . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ ---------------------------------------[/go]
I wanted all of these points. 'b' is iffy because it hurts my bottom group a bit, but the rest look pretty good. 'c' is slightly less big, now that there's at least some black stones above for these to run to if I steal their base. Essentially though, it seemed TOO good for black to let it turn the curner here in the middle, so I jumped ahead to prevent it. I'll have to think about the biggest next move again in a bit, but I want this now. I like the looks of 'f' actually, not for any threatened followup, but for the safe reduction.
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Wed Jul 06, 2011 7:47 pm
by emeraldemon
$$Bcm41
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . O . . . . . . . . . |
$$ | . . . O . O . . . , . . . . . O . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . X . . . . . . . . . . . . . O . . |
$$ | . . . . O . . . . . O . . . . X O . . |
$$ | . . X . . . . . . . . . O O X O X . . |
$$ | . . . . . . . . . . . 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 . . |
$$ | . . . . . . . . . 7 . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ ---------------------------------------
[go]$$Bcm47
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . O . . . . . . . . . |
$$ | . . . O . O . . . , . . . . . O . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . X . . . . . . . . . . . . 2 O . . |
$$ | . . . . O . . . . . O . . . . X O . . |
$$ | . . X . . . . . . 3 . . O O X O X . . |
$$ | . . . . . . . . . . . X X O O O X . . |
$$ | . . . X . . . . . , . . . X X X . . . |
$$ | . . . . . . . . . . . . . . . . X . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . O . . . |
$$ | . . . . X X . X . . . . . . X O . . . |
$$ | . . X , X O . . . O . . X 5 . X O . . |
$$ | . . . . . O . O . 6 9 . X O X . O . . |
$$ | . . . . . . . . 7 1 8 0 . 4 . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ ---------------------------------------[/go]
Still seems to greatly overestimate the aji of its 2 stones in the upper right. For the people who were curious, I ran again w/ a significantly higher search count:
revised.png (629.88 KiB) Viewed 11204 times
It came up with this sequence:
$$Bcm47
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . O . . . . . . . . . |
$$ | . . . O . O . . . , . . . . . O . . . |
$$ | . . . . . . . . . . . . . . 8 . . . . |
$$ | . . X . . . . . . . . . . 9 7 4 O . . |
$$ | . . . . O . . . . . O . . 6 5 X O . . |
$$ | . . X . . . . . . . . . O O X O X . . |
$$ | . . . . . . . . . . . X X O O O X . . |
$$ | . . . X . . . . . , . . . X X X . . . |
$$ | . . . . . . . . . . . . . . . . X . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . O . 1 . |
$$ | . . . . X X . X . . . . . . X O . . . |
$$ | . . X , X O . . . O . . X 3 . X O . . |
$$ | . . . . . O . O . . . . X O X . O . . |
$$ | . . . . . . . . . . . . . 2 . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ ---------------------------------------
[go]$$Bcm41
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . O . . . . . . . . . |
$$ | . . . O . O . . . , . . . . . O . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . X . . . . . . . . . . . . . O . . |
$$ | . . . . O . . . . . O . . . . X O . . |
$$ | . . X . . . . . . . . . O O X O X . . |
$$ | . . . . . . . . . . . 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 . 8 . . X O X . O . . |
$$ | . . . . . . . . 0 X 9 . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ ---------------------------------------[/go]
Yeah, I've been leaving this group hanging for a bit too long. Really wanted to slide into the corner more for eyespace instead, but didn't like how much white could threaten to sever connections, while undercutting my base.
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Thu Jul 07, 2011 11:46 am
by emeraldemon
Fuego doesn't like your suggestions...
$$Bcm41
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . O . . . . . . . . . |
$$ | . . . O . O . . . , . . . . . O . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . X . . . . . . . . . . . . . O . . |
$$ | . . . . O . . . . . O . . . . X O . . |
$$ | . . X . . . . . . . . . O O X O X . . |
$$ | . . . . . . . . . . . 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 . O . . X O X . O . . |
$$ | . . . . . . . . 9 X . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ ---------------------------------------
[go]$$Bcm49
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . O . . . . . . . . . |
$$ | . . . O . O . . . , . . . . . O . . . |
$$ | . . . . . . . . . . . . . . . 8 . . . |
$$ | . . X . . . . . . . . . . . . . O . . |
$$ | . . . . O . . . . . O . . . . X O . . |
$$ | . . X . . . . . . . . . O O X O X . . |
$$ | . . . . . . . . . . . X X O O O X . . |
$$ | . . . X . . . . . , . . . X X X . . . |
$$ | . . . . . . . . . . . . . . . . X . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . 6 . . . . . . . . . |
$$ | . . . . . . . . . 9 0 . . . 7 O . . . |
$$ | . . . . X X . X . . . . . . X O . . . |
$$ | . . X , X O . . . O . . X . . X O . . |
$$ | . . . . . O . O . O 4 . X O X . O . . |
$$ | . . . . . . . . 1 X 2 3 . . . . . . . |
$$ | . . . . . . . . . . 5 . . . . . . . . |
$$ ---------------------------------------[/go]
I like the undercutting that fuego is trying, but with the corner open I don't think black can really do much here. All white has to do is slide (which is pretty big). Overall I still prefer white here, but the game's not over yet (I can't help but root for Fuego).
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Thu Jul 07, 2011 12:18 pm
by Chew Terr
$$Bcm41
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . O . . . . . . . . . |
$$ | . . . O . O . . . , . . . . . O . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . X . . . . . . . . . . . . . O . . |
$$ | . . . . O . . . . . O . . . . X O . . |
$$ | . . X . . . . . . . . . O O X O X . . |
$$ | . . . . . . . . . . . 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 . O . . X O X . O . . |
$$ | . . . . . . . 0 X X . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ ---------------------------------------
[go]$$Bcm53
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . 5 . . . . . O . . . . . . . . . |
$$ | . . 3 O . O . . . , . . . . . O . . . |
$$ | . . . . . . . . . . . . . . . 6 . . . |
$$ | . . X . . . . . . . . . . . . . O . . |
$$ | . . . . O . . . . . O . . . . X O . . |
$$ | . . X . . . . . . . . . O O X O X . . |
$$ | . . . . . . . . . . . X X O O O X . . |
$$ | . . . X . . . . . , . . . X X X . . . |
$$ | . . . . . . . . . . . . . . . . X . . |
$$ | . . . . . . . . . . . . . . . . . 9 . |
$$ | . . . . . . . . . . . . . . . . 8 0 . |
$$ | . . . . . . . . . . . . . . . O . 7 . |
$$ | . . . . X X . X 1 . . . . . X O . . . |
$$ | . . X , X O . O . O . . X . . X O . . |
$$ | . . . . . O . O . O . . X O X . O . . |
$$ | . . 2 . 4 . . O X X X . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ ---------------------------------------[/go]
What's the deal with and ? I know I said Fuego evaluates both sides the same way, but somehow white seems to take all the pointless gote moves in this sequence...
Re: 124. Chew (3k) vs Fuego (Bot)
Posted: Sat Jul 09, 2011 2:10 am
by Loons
Wait, I'm confused about how Fuego thinks, again.
So the numbers on the board are the quantity of MC game-play-outs it started there, and every victorious play-out adds weight to that play-out's starting move, and high placing moves (2nd, 3rd place etc) are tried earlier in later play-outs (as they become established)?
Could you give us some samples of the finished MC play-outs Fuego reaches ? I am curious how crazy they look. (Sorry if I just overlooked them earlier). Would it be useful to post a white's-move-values board for the first move after Fuego's chosen move, or can we just infer that from Fuego's predicted sequences?
PS: The board doesn't look *so* terrible for black, though I guess I keep imagining in some kind of life on top. Where would other people play their next few moves as black, after Chew slides for life? (To contrast Fuego's tenuki sequences).
and 
? I know I said Fuego evaluates both sides the same way, but somehow white seems to take all the pointless gote moves in this sequence...