Re: [computer-go] Re: Should 9x9 komi be 8.0 ?]
Hideki Kato wrote: delta_komi = 10^(K * (number_of_empty_points / 400 - 1)), where K is 1 if winnig and is 2 if loosing. Also, if expected winning rate is around 50%, Komi is unmodified. I don't think the formula you posted is correct. In the opening it gives delta_komi = 0.8 and in the endgame it gives delta_komi = 0.1. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Should 9x9 komi be 8.0 ?]
Hideki Kato wrote: Gian-Carlo Pascutto: [EMAIL PROTECTED]: Hideki Kato wrote: delta_komi = 10^(K * (number_of_empty_points / 400 - 1)), where K is 1 if winnig and is 2 if loosing. Also, if expected winning rate is around 50%, Komi is unmodified. I don't think the formula you posted is correct. It's just an experimental formla with no theoritical basis. I don't think we can discuss its correctness. Even if it's a heuristic the outcome should be sensible. For what you posted it doesn't seem to be at all. So I think that what you posted is not what is in the program. That is what I mean by correct. In the opening it gives delta_komi = 0.8 and in the endgame it gives delta_komi = 0.1. I'm sorry but I don't understand what do you want to say. Too small? Yes. I don't understand how it can do anything if it adds _at most_ 0.8 points difference. Should it have been 10* instead of 10^ or something? -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)
I also implemented RAVE in Mango. There was a few points of improvements (around 60 Elo points with gnugo as reference), but as much as in the paper of Gelly and Silver :( (around 250 Elo points if I remember well) It might be that the effect of RAVE depends a lot on the simulation strategy. Indeed, sometimes my RAVE was playing very good moves but also very bad ones. I don't think the simulation strategy is the key. I suspect the improvement is largest when you don't do progressive widening. Nevertheless it would be quite interesting to see the implementation details of ggmc's RAVE. RAVE performance is quite dependent on exact implementation and parameters. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)
Hideki Kato wrote: 4) Before back-propagating the value of each playout, I setup a color table for all intersections of the board for speed-up, in fact (initialized with EMPTY). That is, fill the board (table[move] = color) by tracing the moves and the colors returned by the playout forward (from leaf node to end of the game). Then, by tracing the path from root to the leaf node, clear the table[move] (table[move] = EMPTY), in order to avoid duplicate counting with UCB1. I don't understand this. What and how would you be double counting? -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More UCT / Monte-Carlo questions
Olivier Teytaud wrote: Basically, the formula in MoGo combines the success ratio and the RAVE-success ratio, with more focus on the success ratio when the number of simulations is large. You have no bias which favors exploration at all? -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Selecting tree child objects, was Hydra theory (was Hybrid theory)
Harri Salakoski wrote: Hi such question that do you typically traverse all child objects or is there faster way to select explored node child object. I have concluded that it is not at least easy as multiple nodes uct values change each simulation so trying to keep biggest uct value in first in list is maybe too expensive best practical way is go trough all child moves. I made a similar reasoning as you some time ago and concluded the same. With progressive widening there are very few moves to consider anyway. And as you add more knowledge to playouts, the speed of the UCT part gets unimportant. But there is a good trick: the 1 + epison rule described on Lukas Lew's homepage. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] CGOS Deflation or Self-Play delusion?
I'm not sure what to think about the following: Leela 0.3.0 vs Leela 0.3.7, 455 game match 177 vs 278 = +78 ELO points for Leela 0.3.7 CGOS rating Leela_0.3.0_1CPU 2335 Leela_0.3.7_2CPU 2333 Hmm..but also Zen-0.9 2386 Zen-1.0 2385 or more: Uct-200801122348 Uct-200801132334 Uct-200801162326 Uct-20080117-t 2302 With greenpeep also similar things happened. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hybrid theory
Michael Williams wrote: So do I. I just stated a simpler version here because I previously suggested a more integrated approach and got zero replies. I'll state it again: Start with a UCT+MC engine. When a tree node reaches X number of playouts (1000?, 1?), do a tactical analysis. When that analysis exists for a given node, let it in some way bias the move selection at that node. I think it's a good idea :) -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go rating math information
Don Dailey wrote: I don't know how David figures 1000 ELO, but I would expect the difference to be much larger than that for 19x19 go. I don't believe they are yet very close to 1 Dan. http://www.gokgs.com/graphPage.jsp?user=CrazyStone You're right. They're closer to 2 Dan. :) -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go knowledge and UCT
David Fotland wrote: So, can the strong 19x19 programs please tell us your playout rates? I expect the higher the rank, the fewer playouts per second. I'm not interested in 9x9 data, since I think much less go knowledge is needed to play 9x9. With your playout rate, please include the machine, number of CPUs, and how you measured it (from an empty board, or averaged over a whole game, or ...). On an 1.7Ghz Pentium M, Leela 0.3.7 does 1350 playouts per second in the openings position. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go rating math information
Andy wrote: CrazyStone hasn't played since the initial spike to 1k in December. The movement of the chart afterwards is rating drift. Ok. For me this is actually GOOD news :) -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Study - prior in bayeselo, and KGS study
Don Dailey wrote: If a nakade fixed version of mogo (that is truly scalable) was in the study, how much higher would it be in your estimation? You do realize that you are asking how much perfect life and death knowledge is worth? -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Study - prior in bayeselo, and KGS study
Don Dailey wrote: I must not understand the problem. My program has no trouble with nakade unless you are talking about some special case position.My program immediately places the stone on the magic square to protect it's 2 eyes. Can your program identify sekis? Nice examples in attachement. I can't believe mogo doesn't do this, it would be very weak if it didn't. That's just an assumption shaped by a non-objective human bias. -- GCP llSeki.sgf Description: x-go-sgf seki.sgf Description: x-go-sgf ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Study - prior in bayeselo, and KGS study
Don Dailey wrote: So I think this is nakade. Yes. Leela 0.2.x would get it wrong [1]. [1] Not eternally, but it would still take unreasonably long. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Study - prior in bayeselo, and KGS study
Don Dailey wrote: Yes, the tree generates pass moves and with 2 passes the game is scored without play-outs. How do you detect dead groups after 2 passes? Static analysis? All is alive/CGOS? I can't believe mogo doesn't do this, it would be very weak if it didn't. That's just an assumption shaped by a non-objective human bias. So are you saying that if mogo had this position: | # # # # # # | O O O O O # | + + + + O # a b c d e That mogo would not know to move to nakade point c1 with either color? I was referring to your it would be very weak, not to what MoGo does or does not do. I don't know exactly what MoGo does. I do know you can not know the above and not be very weak. You can also not know about ladders and not be very weak. Many people seem to think this is completely unfathomable, and I was surprised you made the same mistake. I think it has something to do with both things being the first things a human player learns. Because he thinks it's basic, he concludes anybody not knowing it is weak. But strength just doesn't work that way. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Study - prior in bayeselo, and KGS study
Don Dailey wrote: I am concerned that the current study is, as Jacques has so ably described, a study of a restricted game where nakade and certain other moves are considered to be illegal; this restricted game approaches the game of Go, but the programs have certain blind spots which humans can and do take advantage of. These aren't computer-specific blind spots; humans train on life-and-death problems in order to gain an advantage over other humans also. This is good news and nothing to worry about.You are basically saying mogo has a bug, and if this bug is fixed then we can expect even better scalability. So any success here can be viewed as a lower bound on it's actual rating. If a nakade fixed version of mogo (that is truly scalable) was in the study, how much higher would it be in your estimation? I wanted to come back here because in the heat of the discussion it's easy to forget what you are actually discussing about. I think you wanted to make the point that it's possible to fix MoGo that it considers all moves in the UCT tree, and this scales to perfect play. This in turns means that the scaling results are to be considered a lower bound. One thing I want to point out to that is that fixing MoGo in the sense described could mean that its curve is a lot lower. The question is if the curve would have a different steepness. For sure it cannot actually flatten out at the same point! -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is MC-UCT really scalable against humans?
David Fotland wrote: This is an odd idea. When computers started beating people in chess, humans did not abandon the game and change to some other similar game. Why do you think go players would stop playing go when computers get strong? At some point human players playing computers started demanding that the computers did not use endgame databases or opening books, on the premise that these were an unfair advantage for the computers. Demands from the computer teams for a lobotomy in the memory lobe of the humans were not met, because that was considered a silly demand. I believe the last few matches were with pawn odds. I thought that in shogi, the reaction to strong computers was: you're not allowed to play them anymore, otherwhise someone might disgrace the human race. Humans *really* dislike losing. But so do game programmers :) -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some thoughts about Monte Carlo
So I wouldn't be surprised at all if at some point you'll see a marriage of the best ideas of traditional Go programs and Monte- Carlo / UCT. In fact, this is most likely already happening as these Monte-Carlo programs use algorithms / ideas from the traditional programs for tactics, pattern-matching and possibly others.. And I go out on a limb to predict that at some point heavy playouts will use information like territory, eye-space and group-strength to guide their playouts just like the traditional programs do. And that using fixed 3x3 patterns will be a passing fad. You don't even have to go out on a limb ;-) One detriment to this is still that increasing the strength of playouts does not make them necessarily better. This might cause a schism in the kind of information that is needed between classical approaches and Monte Carlo. So I do not think both approaches will totally converge. This comes to my first point. Optimizing early in a project is like listening to the devil. It eats up a lot of time, the visible progress is gratifying but in the grand scheme of things it's not all that important to do early. I implemented it using pseudo-liberties because... uh, well, because that's what everyone seemed to be doing to get high numbers of playouts per second. But I already start to doubt using pseudo-liberties are all that useful. Is anybody still using pure-random playouts for anything? As soon as you start to do anything more, pseudo-liberties are pretty useless. I agree here, and I made the same mistake. But the speed of the random playout becoms less and less important with heavy playouts. This I don't understand at all. The improvement curve for being faster isn't different with heavy than with light playouts. Next I was thinking about another subject that got some attention on this list, the mercy rule. It seems to save about 10% in the number of moves per game (on 19x19) and result in about 20% gain in performance. This discrepancy is most likely due to the fact that the administration, whether using pseudo-liberties or real, is much slower towards the end of the game because you have more moves that merge chains. And those 10% moves it saves are of course always at the end. So is it relevant? I don't know whether heavy playouts will be slower towards the end of the game or not. Possibly yes, as more moves made will have a small number of liberties that will need tactical analysis. I'd say that generally reducing the move-count is a good thing whichever method one uses. Possibly at a later stage more sophisticated methods can be developed to abort a game early. Possibly the mercy rule is a premature optimization just like psuedo- liberties :-) Next I allowed suicide only for White. You allowed single-stone suicide too, I guess? This is obviously bad since it will happen constinously near the end of an MC playout. It will be like one side is forced to pass 50% of the time and the other side not. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
John Fan wrote: If we are talking about real suicide, I do not see any point to allow the real suicide in the play out. What would be the gain if we allow the real suicide in the play out. The answer to this question has been given at least 3 times: Speed. It can take time to disallow a certain kind of move. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some thoughts about Monte Carlo
Mark Boon wrote: On 18-jan-08, at 12:01, Gian-Carlo Pascutto wrote: But the speed of the random playout becoms less and less important with heavy playouts. This I don't understand at all. The improvement curve for being faster isn't different with heavy than with light playouts. I see I didn't word this very clearly. I mean the speed of updating the administration during playout, like liberties or pseudo-liberties becomes less important. I agree. No, I did not allow single-stone suicide for either side as I see no reason to allow it and it would lead to lots of potential problems (like many board repetitions). Just allowing multiple-suicide for White is enough to push up Black's winning percentage that much. Thanks for the info. I guess I need to retest to see if the tradeoff I made still makes sense. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
Gian-Carlo Pascutto wrote: Multi-stone suicide is allowed, single stone not. I hadn't even considered suicide.(It would be a major change for me, as neither my Gui nor my board system allow such moves.) The question is Why do you do it? a. Just in case you wanted the entire program to support suicide go or b. Because that has some advantage as a random playout. If it was b, can anyone explain why suicide is a better evaluation for a normal (non suicide) game. None of the above! There are no advantages to allowing suicide, it is simply expensive for me in terms of speed to forbid it in playouts. If this is not the case for your board structure then you will probably want to forbid suicide. Leela does not allow suicide in the GUI and the engine itself will also never suicide in games. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
terry mcintyre wrote: That key play might even have been discouraged by some pattern. MoGo probably does not allow self-ataris. If you do not allow self-atari you cannot see such a shape is dead. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
No wonder it plays so well at 9x9, because the max length of playout is only 81, it can 'see' what the board look like when the game ends. The *average* length of a 9x9 playout is roughly 100 moves. The max length is much larger. On a 2.2Ghz Athlon64, I get about 10 000 playouts/second, at an average of 100 moves per game this is 1 million updates/second. There are many programs that are much faster. On the same hardware libego would be about 6 million updates/second. 19 x 19 is a bit slower, because strings are bigger on average. This also explains that when I read the games MoGo against GNUGo, toward the end of the game, GNUGo would play PASS, but MoGo would continue to play at some very uncommon positions that a normal player would never consider. Pass behaviour has little to do with the playouts themselves. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
Playing randomly like that shouldn't work, but when you play Mogo et al, you see that intelligent behaviour emerges. Although interesting, I would hardly call that 'intelligence' :-) Ah, the traditional flamewar topic: the definition of intelligence shifts whenever a computer achieves what was formerly considered intelligence. And I suspect how far it can achieve on 19x19 board (compare to human players of course). Perfect play, no need to suspect anything. The real question is how far humans are away from that :-) -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
Harri Salakoski wrote: The *average* length of a 9x9 playout is roughly 100 moves. The max length is much larger. The *average* length of a 9x9 playout is roughly 100 moves. The max length is much larger. Hmm, sorry if this is old subject but does it effect much for playout quality if I cut playouts for example max 110 moves in 9*9 board? Is that studied subject for almost random playouts. Another thing, do you include random moves for playouts, after some number of playouts or when there is K number empty points or using some other way. I play until there are only moves that put stones into a real eye, and then pass 2 times. I described my exact playout policy a few posts ago. Multi-stone suicide is allowed, single stone not. Light playouts (i.e. just random moves) were about as long, if I remember correctly the average playout length was 104 moves or so. It's good practise to measure this regularly over say 1 million games. Sometimes you will find that the average shifts at a moment you didn't expect it = Oops, introduced a bug :) -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
Rémi Coulom wrote: Gian-Carlo Pascutto wrote: Multi-stone suicide is allowed, single stone not. Strange. The reverse would make more sense to me. I do not track liberties, so the speed penalty for doing it that way is too much. I wrote my program to track psuedoliberties because this is very fast and I thought I could take a lot of shortcuts and early exits when I had to know the real amount of liberties. Unfortunately the interesting cases seem to be the ones that don't allow for the shortcuts. I am now convinced designing the program with psuedoliberties was a mistake. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
[EMAIL PROTECTED] wrote: Um, by easier I mean faster. Also, I think single point suicide is more likely to lead to infinite loops, depending on your eye-filling rule. - Dave Hillis Yes. Particularly near the end of the game there are zillions of bad single stone suicides, but not often multi-stone suicides. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
Christoph Birk wrote: On Jan 15, 2008, at 10:00 AM, [EMAIL PROTECTED] wrote: Um, by easier I mean faster. Also, I think single point suicide is more likely to lead to infinite loops, depending on your eye-filling rule. - Dave Hillis I don't understand why anyone would allow suicide in playouts. No commonly used (in particular CGOS) ruleset allows it. Passing is not allowed in chess. Yet nullmove is quite popular. There is no reason to follow the rules during playouts. If playing 10 moves at once made my program stronger, I would do just that. ...and yes, I did try that. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] handicap for mogo against pro ?
Don Dailey wrote: But with the type of scoring that MC does (where we optimize for winning percentage over score) it's more difficult to construct go problems. You have to construct them so that you LOSE the game if you don't play the right move, but if you do play it you win the game. Life death problems of large groups are a good start. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] handicap for mogo against pro ?
Hideki Kato wrote: No. Remember UCT is a sequential algorithm. Parallelizing UCT make playouts ineffective. Increasing the number of threads and/or communicating delay decreases the effectiveness of the playouts. With my experiments on a symmetrical threads implementation on a four core SMP system, winning rate against GNU Go decreases from 50.4+-1.1% to 46.7+-1.1%, which corresponds to -25 ELO, where 1.1% are the standard deviations [1]. This just shows that this SMP implementation has no *effective* speedup, but probably a effective slowdown. And so a loss of ELO is expected. I clearly stated what I meant by effective: How much faster you find the correct move. Not interesting is: how many positions you search per second or how many playouts you do per second. The fact that parallel UCT is not the same as serial UCT does not change anything at all with the above definition. Either it finds good moves faster, and hence is stronger, or it does not. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] handicap for mogo against pro ?
Hideki Kato wrote: What is correct move? It has sense only for some artificial problems or very limited positions, and so, it cannot evaluate total performance of a program. This is true, but we are interested in search performance. So, it makes sense to evaluate on those positions where the search makes the difference, no? -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] handicap for mogo against pro ?
Don Dailey wrote: It's not very clear to me how strong Mogo is at 19x19. I have no idea. Can't we estimate from KGS games? You'd need to know exactly how fast the hardware is, of course. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] handicap for mogo against pro ?
Olivier Teytaud wrote: Also, there are probably other people interested in combining UCT and mpi; I don't know if some people have a more precise idea of the level of the MPI+UCT combination than us. Someone ? MPI is just a parallel programming model/library, right? So the only thing to know is the effective[1] speedup of the MPI version, and how well UCT scales with increasing timecontrols/speed. I believe Don has data on the latter and you should have data on the former. [1] How much faster you find the correct move. Not interesting is: how many positions you search per second or how many playouts you do per second. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] handicap for mogo against pro ?
Michael Williams wrote: Gian-Carlo Pascutto wrote: Olivier Teytaud wrote: Also, there are probably other people interested in combining UCT and mpi; I don't know if some people have a more precise idea of the level of the MPI+UCT combination than us. Someone ? MPI is just a parallel programming model/library, right? So the only thing to know is the effective[1] speedup of the MPI version, and how well UCT scales with increasing timecontrols/speed. I believe Don has data on the latter and you should have data on the former. [1] How much faster you find the correct move. Not interesting is: how many positions you search per second or how many playouts you do per second. Not exactly, because the algorithm is probably not going to be exactly the same -- that would require too much communication between nodes. So what? That is not relevant, as long as the algorithm is still UCT-like even when parallelized, so that Don's scaling research holds. How they parallelize is completely irrelevant as long as they measure effective speedup, i.e. time to find the best move. There is absolutely no requirement for the parallel algorithm to give the same results. Only the (average) speed of the end result matters. If you know how much faster you are, and you know how much stronger you get by being faster, you have the answer. Both data is available. Also good is: score versus a set opponent, or even better, set of opponents. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to design the stronger playout policy?
Yamato wrote: I guess the current top programs have much better playout policy than the classical MoGo-style one. The original policy of MoGo was, (1) If the last move is an Atari, plays one saving move randomly. (2) If there are interesting moves in the 8 positions around the last move, plays one randomly. (3) If there are the moves capturing stones, plays one randomly. (4) Plays one random move on the board. I (and maybe many others) use it with some improvements, however it will be not enough to catch up the top programs. What improvements did you try? The obvious one I know are prioritizing saving and capturing moves by the size of the string. Zen appears quite strong on CGOS. Leela using the above system was certainly weaker. Then I have tested a lot of change of probability distributions, but it was very hard to improve the strength. Any comments? I had the same problem, i.e. it seems almost impossible to improve the MoGo system by having a different pattern set for interesting moves, or even by varying the probability of interesting moves by pattern score. I tried 2 things: a) I exctracted about 5000 positions with a known winner (determined by UCT) from CGOS games, and measured the Mean Square Error of the result fof my playouts against the known result (also described in one of the MoGo papers). Then I applied a genetic algorithm to optimize the playout patterns. This worked, in the sense that the MSE measured over the 5000 positions dropped. However, it did not produce a stronger program! I found that somewhat shocking. It makes me doubt the value of the MSE measure. 2) I made a simple genetic algorithm that makes a random pool of a few hundred playout policites, picks 2 random parents and crossovers/mutates to 2 children, plays a 10 game match between the 2 children with simulations = 100, and then keeps the winner. This did not produce anything interesting either. My best guess is that the match results are simply too random. So I did not found any way to automatically optimize the patterns. I finally improved my playouts by using Remi's ELO system to learn a set of interesting patterns, and just randomly fiddling with the probabilities (compressing/expanding) until something improved my program in self-play with about +25%. Not a very satisfying method or an exceptional result. There could be some other magic combination that is even better, or maybe not. I now got some improvement by merging the (1) (2) (3) in the MoGo system and using probabilities on that. It makes sense because the playouts wont try hopeless saving moves, for example. What is so frustrating is that the playouts are essentially black magic. I know of no way to automatically determine what is good and not besides playing about 500 games between 2 strategies. The results are very often completely counterintuitive. There is no systematic way to improve. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to design the stronger playout policy?
Yamato wrote: I finally improved my playouts by using Remi's ELO system to learn a set of interesting patterns, and just randomly fiddling with the probabilities (compressing/expanding) until something improved my program in self-play with about +25%. Not a very satisfying method or an exceptional result. There could be some other magic combination that is even better, or maybe not. I also have implemented Remi's Minorization-Maximization algorithm. But I could not find how to use the result of it to improve the strength. Would you explain the details of the playout policy? (1) Captures of groups that could not save themselves last move. (2) Save groups in atari due to last move by capturing or extending. (3) Patterns next to last move. (4) Global moves. I quantize the MM pattern scores to 0..255 by multipying them with a large constant and clipping. This causes the very good patterns to have close scores. I then use a threshold so I do not play the very bad patterns at all. The remaining moves are played with the probabilities indicated by the quantized values. I also throw away very bad moves in phase (4) unless there are no alternatives. This gives a small but measurable improvement. But now I believe all the above is actually flawed. With this system I will play bad saving moves even if there are great pattern moves. It might be that your ladder detection avoids these problems somewhat. Considering the probabilities of all moves as Crazy Stone does avoids this problem. I am now trying to get a similar effect without incrementally updating all urgencies. Do you use only 3x3 patterns? Yes. I have not tried bigger ones. For size = 4 the tables would become 2 x 16M. Might be worth a try. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CGOS 19 is stuck
Chris Fant wrote: CGOS 19 is has been stuck for a while now. At the bottom of the page, it says Many Faces is in a game, but does not show it as currently playing at the top of the page. Perhaps the problem is related to a bot leaving near the time a round is ending/beginning. I guess Oliver isn't running the watchdog script that Don created? Any progress on CGOS 19x19? It appears to have been stuck for 2 weeks now? -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] low-hanging fruit - yose
Rémi Coulom wrote: In Crazy Stone (maybe that is the case of MoGo, too), nakade is such a big problem because the program avoids playing self-atari in playouts. Crazy Stone will play the self-ataris anyway, but with a low probability, so they are played at the end of the playout only. In case there is a semeai around the nakade, this behaviour generates awful evaluation errors. Don't you miscount all sekis as well? At the end of the game the self-atari is the last move left, you play it, and you lose. The self-atari/seki/nakade isssue is for me one of the biggest pains with playouts. If you do not allow self-atari, sekis are OK, but you do not understand life death in many simple situations. If you allow self-atari, you misjudge sekis. Misjudiging sekis seems to be preferable in terms of playing strength. I think one is alternately miscounting the seki for both sides in the playouts, so the effect is not so bad. The biggest problem is with scoring games. Humans have problems if you cannot understand simple LD situations or claim their stones in seki are dead. The solutions I could come up with so far are: a) Don't allow self-ataris until the game is passed out and you are lost. This can handle seki and nakade. The problem is that you are still miscounting, even though it shouldn't change the winner. Unfortunately, it seems to make the program weaker. b) Do not play self-ataris for big groups. Maybe big should be determined experimentally. I would guess at 4. I think I remember Remi saying that Aya does this and it caused a loss at UEC Cup? Haven't tried it myself. I would appreciate feedback from anyone who has struggled with the same problem. Particularly if you solved it :) -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Please have your bot resign, for your own good
steve uurtamo wrote: It was my understanding that the netlag to the Philippines was about 380 ms; accounting for an additiaonal 15% packet loss and we end up at about 440 ms. i think that it works out to roughly double that because of the protocol, right? Yes, the server sends out the move and starts your clock immediately. You need 1 ping time to see the move and start calculating. After you move, there's an additional ping time to get the move to CGOS. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Jason House wrote: MoGo uses TD to predict win rates. Really? Where did you get that information? -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Jason House wrote: The paper introduces RAVE and near the end talks about using heuristics for initial parameter estimation. The heuristic they used was based TD. Ah, you're talking about RLGO. RLGO was trained with TD, but MoGo itself doesn't use TD (directly). There are posts from Sylvain and David here that the latest MoGo's use a simpler and faster heuristic which works just as well. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New engine? From a Chess programmer perspective.
Mogo is around 2500 on CGOS: http://cgos.boardspace.net/9x9/cross/MoGo_psg7.html This implies you believe the ratings didn't shift over time. http://computer-go.org/pipermail/computer-go/2007-October/011405.html http://cgos.boardspace.net/9x9/cross/MoGo_monothreadC.html http://cgos.boardspace.net/9x9/cross/goala1.html The MoGo team has worked for 5 months and gained...-200 ELO. http://cgos.boardspace.net/9x9/cross/greenpeep0.3.4.html http://cgos.boardspace.net/9x9/cross/greenpeep0.4.2.html Same phenomenon. In Amsterdam, ajahuang (kgs 6d) played a few games against MoGo on 9x9, and won them all. This can be seen in his history on KGS. That's a good data point which would drop the estimate a few ranks. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] FPGA to Hardware
Joshua Shriver wrote: FPGA boards are expensive How many gates do you need? It's not because the eval boards you find everywhere are expensive that FPGA's are. Low-cost ones go from 10 to 70 USD depending on the gate count. A bargain compared to an ASIC solution as long as the quantities are below tens or hundreds of thousands. What does your VHDL do and what frequency would it synthesize at on a common FPGA? Or was this all a hypothetical question? -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KGS: Sending game comments
Petr Baudis wrote: Hi, is there any way to send game comments through kgsGtp on your own (without the opponent triggering you)? I think some possibility to send messages would be great. I could swear I saw MogoBot do this, but I couldn't find anything in the KGSGtp documentation. The message I would want to print out most is This bot will resign by itself if it's lost. If it does not resign in a losing position, the status of some groups is not clear, and should be played out, or there are still some winning chances. It will pass when it thinks it has won. What I've seen several times is that the game gets passed out in the middlegame with a large fight almost resolved (in disfavor of the bot, except that it doesn't understand that sometimes). My bot will only pass out when this wins in the count, so this usually ends up in scoring dispute and an annoyed human. I guess people are aking to interpret pass as resign when they are winning, but the program's intention is directly the opposite in this case. Also, it could be interesting if the experimental bots could print the winning probability for each move they play in free games. Most bots are unranked and hence most games are free, so I'm not sure this is a good idea. Knowning the winning percentage gives you an advantage and can also be very annoying. Being able to broadcast a message to all spectators minus the opponent would be better. This is whispering on the chess servers. No idea if KGS has something similar. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
