[computer-go] Mogo MCTS is not UCT ?
I think it's now well known that Mogo doesn't use UCT. I realize that i have no idea at all what Mogo do use for it's MCTS. There are only two things i dislike about UCT : - It's slow to compute. - It's deterministic I really wonder if there was an article describing the new MCTS of mogo somewhere that i missed. How is it better than UCT ? _ Email envoyé avec Windows Live Hotmail. Dites adieux aux spam et virus, passez à Hotmail ! C'est gratuit ! http://www.windowslive.fr/hotmail/default.asp___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] RAVE formula of David Silver (reposted)
On Dec 1, 2008, at 12:23 AM, Mark Boon [EMAIL PROTECTED] wrote: On 30-nov-08, at 16:51, Jason House wrote: You've claimed to be non-statistical, so I'm hoping the following is useful... You can compute the likelihood that you made an improvement as: erf(# of standard deviations) Where # of standard deviations = (win rate - 0.5)/sqrt(#games) Erf is ill-defined, and in practice, people use lookup tables to translate between standard deviations and confidence levels. In practice, people set a goal confidence and directly translate it to a number of standard deviations (3.0 for 99.85%). This situation requires the one-tailed p test. After about 20 or 30 games, this approximation is accurate and can be used for early termination of your test. Lately I use twogtp for my test runs. It computes the winning percentage and puts a ± value after it in parenthesis. Is that the v alue of one standard deviation? (I had always assumed so.) Even afte r a 1,000 games it stays in the 1.5% neighbourhood. Sounds like it. Maybe 20-30 games is usually an accurate approximation. But if you perform tests often, you'll occasionally bump into that unlikely event where what you thought was a big improvement turned out to be no improvement at all. Or the other way around. Only when I see 20+ games with a zero winning percentage do I stop it, assuming I made a mistake. The 20 or 30 game caveat would really only apply for extreme winning or losing streaks. Up until that point, confidence levels are not as high as one might expect from the approximation. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo MCTS is not UCT ?
On Dec 1, 2008, at 3:38 AM, Denis fidaali [EMAIL PROTECTED] wrote: I think it's now well known that Mogo doesn't use UCT. I realize that i have no idea at all what Mogo do use for it's MCTS. There are only two things i dislike about UCT : - It's slow to compute. - It's deterministic I really wonder if there was an article describing the new MCTS of mogo somewhere that i missed. How is it better than UCT ? My understanding is that MoGo dropped the upper confidence bound portion. That makes it a bit faster, but still deterministic for a given set of playout results. Heuristics and RAVE give a sufficiently good move ordering that less exploration is needed. IIRC, Valkyra still uses UCT, but has a very low coefficent on the upper confidence bound term. Qui vous permet d'enregistrer la TV sur votre PC et lire vos emails sur votre mobile ? la réponse en vidéo la réponse en vidéo ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] log base e vs. log base 10
Just now I realized that I'm using the standard Java Math.log() function in places where it computes the log(visits). In Java, this log() function is actually the logarithm of base e, which I suppose is normally actually written as ln(). When I read articles about UCT and it says log(), does that actually mean log base e, or log base 10? I figured it probably won't make an awful lot of difference. But there should be some difference. Just to make sure I replaced Math.log () by Math.log10(). Now I'm seeing a slight degradation of play, so I suppose that should answer the question. That doesn't surprise my an awful lot, somehow intuitively it seems to make more sense to use log base e. But maybe adjusting the exploration-factor a little would bring them closer still. I just wanted to make sure... Another thing I tried was replacing log(virtual-parent-visits) by log (parent-visits) in the RAVE calculation. I see no effect on the level of play, so apparently it's a wash. But using the latter saves a little memory and / or (depending on your implementation) a little performance since the log() function is expensive. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] log base e vs. log base 10
When unspecified always assume the natural logarithm. For UCT this does not really matter; only a different tuning constant. log10(x) == ln(x) / ln(10) Erik On Mon, Dec 1, 2008 at 3:22 PM, Mark Boon [EMAIL PROTECTED] wrote: Just now I realized that I'm using the standard Java Math.log() function in places where it computes the log(visits). In Java, this log() function is actually the logarithm of base e, which I suppose is normally actually written as ln(). When I read articles about UCT and it says log(), does that actually mean log base e, or log base 10? I figured it probably won't make an awful lot of difference. But there should be some difference. Just to make sure I replaced Math.log() by Math.log10(). Now I'm seeing a slight degradation of play, so I suppose that should answer the question. That doesn't surprise my an awful lot, somehow intuitively it seems to make more sense to use log base e. But maybe adjusting the exploration-factor a little would bring them closer still. I just wanted to make sure... Another thing I tried was replacing log(virtual-parent-visits) by log(parent-visits) in the RAVE calculation. I see no effect on the level of play, so apparently it's a wash. But using the latter saves a little memory and / or (depending on your implementation) a little performance since the log() function is expensive. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Mogo MCTS is not UCT ?
Let's assume that the UCT formula is UCTValue(parent, n) = winrate + sqrt((ln(parent.visits))/(5*n.nodevisits)) (taken from sensei library) What is the Upper confidence bound term ? That would'nt be sqrt((ln(parent.visits))/(5*n.nodevisits)) ?? I doubt that exploring only the move with the best winrate would lead to a fast enough convergence even on 9x9. Is that what you meant by dropping the upper confidence bound term ? Otherwise, what does the formula without the upper confidence bound term do looks like ? My understanding is that MoGo dropped the upper confidence bound portion. That makes it a bit faster, but still deterministic for a given set of playout results. Heuristics and RAVE give a sufficiently good move ordering that less exploration is needed. IIRC, Valkyra still uses UCT, but has a very low coefficent on the upper confidence bound term. _ Email envoyé avec Windows Live Hotmail. Dites adieux aux spam et virus, passez à Hotmail ! C'est gratuit ! http://www.windowslive.fr/hotmail/default.asp___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] December KGS Computer Go tournament: small boards, fast
The December 2008 KGS computer Go tournament will be this Sunday, December 12t7 in the Asian evening, European morning and American night, starting at 08:00 UTC (GMT) and ending soon after 12:00 UTC (GMT). The Formal division will be a 12-round Swiss with 9x9 boards and 8 minutes main time. The Open division will be an 8-round Swiss with 13x13 boards and 13 minutes each main time. Both will use Chinese rules with 7.5 points komi, and a very fast Canadian Overtime, of 25 moves in 20 minutes. There are details at http://www.gokgs.com/tournInfo.jsp?id=435 for the Formal division, and at http://www.gokgs.com/tournInfo.jsp?id=436 for the Open. Registration is now open. To enter, please read and follow, as usual, the instructions at http://www.weddslist.com/kgs/how/index.html. The rules are given at http://www.weddslist.com/kgs/rules.html. Please send your registration email (with the words KGS Tournament Registration in the title) to me at maproom at gmail dot com (converted to a valid address in the obvious way). Last month, the Formal division began with five registered players. One of these did not show up; and because there was an odd number, a bye was assigned, unfortunately to a different player. So only one game was actually played in the first round, while two other players got a bye and a walkover. To avoid this kind of thing, I have changed the settings to allow Requested Byes and to Drop latecomers. I confess that I am not fully confident of what these do, but I have received advice. The good effect of the change should be that programs that do not show up will receive any necessary byes, rather than byes being allocated randomly. An unfortunate side-effect is that all players that do not show up will automatically receive byes, and receive a half-point for each, so long as they manage to play at least one game. Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo MCTS is not UCT ?
I think it's now well known that Mogo doesn't use UCT. I realize that i have no idea at all what Mogo do use for it's MCTS. A complicated formula mixing (i) patterns (ii) rules (iii) rave values (iv) online statistics Also we have a little learning (i.e. late parts of simulations are evolved based on online statistics and not only the early parts). I really wonder if there was an article describing the new MCTS of mogo somewhere that i missed. How is it better than UCT ? http://www.lri.fr/~teytaud/eg.pdf contains most of the information (many other things have been tried and kept as they provided small improvements, but essentially the ideas are in this version) Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo MCTS is not UCT ?
On 1-dec-08, at 18:55, Olivier Teytaud wrote: I think it's now well known that Mogo doesn't use UCT. I realize that i have no idea at all what Mogo do use for it's MCTS. A complicated formula mixing (i) patterns (ii) rules (iii) rave values (iv) online statistics Isn't that technically still UCT? I mean, you use different input and probably a different formula, but most likely what you do is still establish an upper bound to which extent you trust the win-ratio (and possibly other data) to determine which node to extend next. When that upper-bound is passed you decide to extend a less promising node to make sure you don't overlook an unlikely but possibly very good candidate. It's just that people here have come to associate UCT with a particular formula, but that formula is not the only way you can establish an upper confidence bound. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] regression testing
Someone recently asked about regression testing, and methods of expressing the expected results. Unfortunately, I can't find the post in question. The GnuGo regression suite appears to encode expected results in the .sgf file; here is an example: $ cat Goemate990902-1.sgf (;N[Goemate990902-1.gob]ID[Goemate990902-1.gob]BS[0]WS[0]GM[1]FF[3]SZ[19] AB[eb][gb][lb][qb][cc][dc][hc][ic][kc][mc][qc][ad][dd][nd][od][pd][rd][be][de][k e][af][cf][ef][ff][gf][hf][mf][bg][cg][gg][mg][hh][ih][lh][nh][gi][hi][ji][ki][m i][qi][hj][ij][kj][mj][qj][bk][dk][ek][ik][jk][nk][qk][fl][gl][hl][nl][ql][cm][p m][kn][mn][nn][pn][sn][bo][jo][lo][po][dp][fp][jp][mp][pp][qp][rp][cq][eq][er][h r][ir][jr][gs] AW[mb][nb][rb][ec][oc][pc][rc][bd][cd][ed][gd][hd][id][jd][qd][ce][ee][pe][qe][r e][df][if][jf][dg][hg][ig][lg][og][qg][bh][ch][dh][fh][gh][jh][oh][ei][ni][oi][e j][fj][nj][pj][gk][hk][kk][lk][mk][pk][il][jl][ll][pl][rl][hm][km][lm][qm][rm][d n][gn][in][qn][eo][fo][qo][ep][hp][lp][np][op][fq][gq][lq][mq][pq][qq][rq][fr][k r][fs][js] ;C[move(rk,black):best ]) Terry McIntyre [EMAIL PROTECTED] -- Libertarians Do It With Consent! ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
