Re: [computer-go] Re: Core i7 performance in computer-go
2009/6/6 Hideki Kato hideki_ka...@ybb.ne.jp: Hi Lukasz, I have five core2 and one i7 computers running at home. I prefer i7, though don't have exact measure. The most important difference is the memory interface, ie, core2 uses a obsolete common bus (FSB) while i7 uses p2p connection with an internal (on chip) memory controller. Also, core2 uses DDR2 (obsolete) and i7 uses DDR3 memory modules. I know the technical differences. I just wonder do they matter in practice of computer-go On overclocking, i7 performs better. i7 920 (cheapest model) runs at 3.6 GHz (C0 stepping; recent D0 is said at 4 GHz) while core2 Q9550 (middle range model) runs at 3.2 GHz, with a rather silent air cooling. thanks. If you have a benchmark program please send me. Ubuntu Linux or WIndows XP is fine. http://www.mimuw.edu.pl/~lew/engine.gz please run with: ./engine --seed 123 -b FYI it tests only the processor, not the memory and is optimized for core2. Ah, I don't prefer two sockets SMP computers since we will have hexa and octa core chips soon (next year? I don't remember). I agree. Hideki Łukasz Lew: c55009e70906060527i424cd3d9h525e8f87ec165...@mail.gmail.com: Hi I have few days to buy a computer for Monte-carlo Go program. There is not enough money for a multi processor, so I have to decide between - core i7 2.66 GHz - some core2 quad both subjected to over-clocking. Have you observed that Monte-Carlo Go program is faster on core i7 than on core2 ? Lukasz PS Or have you found some cheap solutions for shared memory dual processor? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- g...@nue.ci.i.u-tokyo.ac.jp (Kato) ___ 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] Tweak to MCTS selection criterion
This is kind of interesting. Is anybody measuring their playout performance in real-time at the moment and performing this sort of computation, to check if overtaking the leading move is mathematically impossible? It's interesting with UCT because of the interplay between the time management algorithm and the exploration parameter. Suppose you are early in the game, and your time management algorithm says you should be spending 10 seconds on a move. After six seconds, because your parameter is skewed towards exploitation, you already have 90% more trials on the leading move than anything else, calculate that it cannot be overtaken and abort. Some things come to mind: - If this behaviour is happening consistently, i.e. you end up spending too little time on all your moves, is your exploitation parameter correct? There is a reason you use a time management algorithm to allocate a lot of time in the beginning. You may be doing pointless searches. - Would you rather exploit less in that case, thus spending your allotted time to do more exploration, or would you instead keep searching instead of aborting and reuse the tree for pondering and/or your follow-up move? Given that people spend a lot of time experimenting on good exploitation/exploration parameters, I suspect that the last option (obey the time management, continue searching, reuse the tree) is the better? Christian Don Dailey wrote: 2009/6/6 dhillism...@netscape.net mailto:dhillism...@netscape.net I think this is one of those design decisions that nobody takes on faith. We all wind up testing it both ways and in various combinations. An additional advantage of using the number of visits is that branches at the root become mathematically eliminated and can be pruned away. It often also allows the search to be stopped early. It can save a lot of time for forced moves. Let me see if I understand what you are saying here. If you have set a goal time for thinking of 10 seconds, and let's say 6 seconds have progressed, then it might be possible to stop the search early if you do the math and see that it's not possible for any other move to have more visits given an additional 4 seconds? So when there is a position that has only a single clearly best move, perhaps a capture that cannot wait or a necessary atari defense, then you can probably save as much (or close to) as half the thinking time on that move.Is this correct? So if this understanding is correct, then it still makes sense to do the pebbles test at this point and check to see if another move has a higher score before stopping the search.If the move really is forced and necessary, then the answer will be no and you can stop early. If there is a move that currently appears better but with a too small sample, then it seems foolish to stop early.If the move is a result of just a few lucky playouts, then it will quickly be revealed and you can still stop early. - Don - Dave Hillis -Original Message- From: Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com To: computer-go computer-go@computer-go.org mailto:computer-go@computer-go.org Sent: Sat, 6 Jun 2009 5:07 pm Subject: Re: [computer-go] Tweak to MCTS selection criterion Another strategy to be considered is to not allow the thinking to cease until the maximum win rate and the maximum visit count agree on the same move. Obviously this requires some extra code to make sure you don't lose on time, etc. Brian Sheppard wrote: When a UCT search is completed, the usual selection criterion is choose the move that has the most trials. This is more stable than choosing the move that has the highest percentage of wins, since it is possible to have an unreliably high percentage if the number of trials is small. I have a small tweak to that criterion. Pebbles uses choose the move that has the most wins. This rule selects the same move as the conventional criterion in almost every case. The reason why Pebbles' rule is superior is revealed in the case where the moves differ. When Pebbles chooses a different move than the conventional criterion, it is because Pebbles move has more wins in fewer trials. When that happens, Pebbles move would inevitably become the move with the most trials if searching were to continue. So there is actually no downside. Of course, the upside is minor, too. For validation, Pebbles has been using both strategies on CGOS games. At present, the conventional selection strategy has won 341/498 = 68.47%. Pebbles strategy has won 415/583 = 71.18%. This isn't statistically conclusive or anything (0.7 standard deviations; we would need 4 to 8 times as many trials for strong
Re: [computer-go] Tweak to MCTS selection criterion
I think all principles I use in the time management for Valkyria came up in this thread more or less. 1) Valkyria selects move that has been searched the most. 2) It is given a base time for example 20 seconds early on on 9x9 CGOS 3) The base time is adjusted down if the program is winning big. 4) If the best winrate move and the most searched move is the same (moves that have been searched less than N times are ignored) the following can happen: 4a) If only one move has been searched more than N times it is played if it has been searched M times. 4b) If the best move have been searched 20% more than the second best then it plays the best move as soon as remaining time does not allow the second best move to catch up 5) If the move with the best winrate and the most searched move disagree the search will not until 3 times the basetime has elapsed. That on CGOS it will think for up to 1 minute on a single move. I do not prune moves because they cannot catch up. Mainly because the code is so complicated as it is. Also perhaps it is not necessary. If a move suddnly jumps in winrate the program will give it 3 times more time to finish it. In losing positions it always spend the maximum time, since the winrate drops for most searched move most of the time. I intentionally set the time managment to think a lot for the opening moves, because I noticed that Valkyria often lost games in the opening and not due to limitations in the playouts. It played on inferior hardware in the latest KGS tournament, and at least showed it can beat any program. On my todo list is some opening book system so it can save time on the opening moves. Quoting Christian Nentwich christ...@modeltwozero.com: This is kind of interesting. Is anybody measuring their playout performance in real-time at the moment and performing this sort of computation, to check if overtaking the leading move is mathematically impossible? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Tweak to MCTS selection criterion
2009/6/6 dhillism...@netscape.net I had the early stop rule and didn't know if anyone else had thought of it. But I never considered the pebbles rule, which somewhat conflicts with the early stop rule. But as I layed out above I think you could do both. This is probably one of those things that adds a little bit but is difficult to measure. - Don Hmm. Well, the way I remember it, I first heard the pebbles rule idea from you, Don. I checked my code to see if I could pinpoint a date, but no luck. This was a while ago. I could be wrong. I think you are remember this wrong. I don't remember ever telling anyone about the pebbles rule, but when I just heard about it seemed new to me. I usually remember ideas that I already had when expressed by someone else. I vaguely remember telling you about the rule to stop searching when I can calculate that it's impossible for any other move to overtake the winning move. But I'm not even sure of that. It probably makes sense to even do this speculatively if you don't push it too hard.Another thing that would have to be studied! - Don - Dave Hillis -- Wanna slim down for summer? Go to America Takes it Offhttp://www.aolhealth.com/diet/weight-loss-program/?ncid=emlcntusheal0001to learn how. ___ 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] bots and handicaps (Re: New CGOS)
The handicap system is imperfect anyway, it's almost a coincidence that it works as well as it does. okay, this sounds like chess bias. the handicap system *defines* the difference in skill levels in go. it's a coincidence that something like ELO can match fairly well to stones. not the other way around. the fact that chess doesn't have a fine-grained way to handicap a game, in fact, the fact that most games don't, doesn't mean that it's hard to deal with. my guess is that any go playing program that doesn't depend upon an opening book for a lot of its strength is going to adapt just fine. experiments between players of different CGOS-measured strengths could find this out for sure -- time for another set of experiments? i'll donate some cpu time. if it helps to encourage the authors, just keep in mind that winning with handicap is extremely convincing evidence to regular go players that one player is much stronger than another. plus, it takes exponentially fewer games to determine that difference. with a logarithmic (in range of handicap, say, +/-6 stones) number of games you could get a very accurate view of the strength difference between two players. say, take best of 2 out of 3 at each test level and do binary search. some go clubs just keep track of the relative difference in stone strength between pairs of players, requiring, say, a 3-win streak by one player to adjust the handicap by a single stone. alternatively, you can (somewhat cheesily) map ELO to handicap and vice-versa for a limited range of ELO and handicap. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Core i7 performance in computer-go
Łukasz, is the program multi-threaded? Corei7 920 runs about 7% slower than core2 at the same clock. Possibly due to the optimized code for core2? Experimental results follow. On a 3 GHz (333 x 9) core2 Q6600: 20 playouts in 1.49209 seconds 134.04 kpps 44.6798 kpps/GHz (clock independent) 105316/94359 (black wins / white wins), Average of the middle 10 of 12 runs is 44.79506 kpps/GHz. Raw data: 44.6798, 44.7951, 44.8276, 44.8207, 44.8398, 44.6887, 44.8317, 44.8491, 44.782, 44.7216, 44.7983, 44.8451 On a 3.6 GHz (180 x 20) corei7 920: 20 playouts in 1.34808 seconds 148.359 kpps 41.2643 kpps/GHz (clock independent) 105316/94359 (black wins / white wins), Average of the middle 10 of 12 runs is 41.57643 kpps/GHz. Raw data: 41.2643, 41.9025, 41.3732, 41.5582, 41.1666, 41.4887, 41.7724, 41.9751, 41.6362, 41.787, 41.269, 41.7128 On a 3 GHz (150 x 20) corei7 920: 20 playouts in 1.6001 seconds 124.992 kpps 40.1661 kpps/GHz (clock independent) 105316/94359 (black wins / white wins), Average of the middle 10 of 12 runs is 41.79165 kpps/GHz. Raw data: 40.1661, 41.8626, 41.8366, 41.687, 41.7099, 41.9556, 41.3053, 41.9335, 41.8255, 41.8838, 42.077, 41.9167 With hyper threading on (3 GHz 920): 20 playouts in 1.5881 seconds 125.937 kpps 41.9898 kpps/GHz (clock independent) 105316/94359 (black wins / white wins), Average of the middle 10 of 12 runs is 41.82533 kpps/GHz. Raw data: 41.9898, 42.0318, 42.0503, 41.947, 40.6079, 41.7033, 42.0283, 41.8386, 41.5187, 41.8013, 41.9114, 41.4831 Hideki Łukasz Lew: c55009e70906070309q4d6224e1s509c2d858ff7e...@mail.gmail.com: 2009/6/6 Hideki Kato hideki_ka...@ybb.ne.jp: Hi Lukasz, I have five core2 and one i7 computers running at home. I prefer i7, though don't have exact measure. The most important difference is the memory interface, ie, core2 uses a obsolete common bus (FSB) while i7 uses p2p connection with an internal (on chip) memory controller. Also, core2 uses DDR2 (obsolete) and i7 uses DDR3 memory modules. I know the technical differences. I just wonder do they matter in practice of computer-go On overclocking, i7 performs better. i7 920 (cheapest model) runs at 3.6 GHz (C0 stepping; recent D0 is said at 4 GHz) while core2 Q9550 (middle range model) runs at 3.2 GHz, with a rather silent air cooling. thanks. If you have a benchmark program please send me. Ubuntu Linux or WIndows XP is fine. http://www.mimuw.edu.pl/~lew/engine.gz please run with: ./engine --seed 123 -b FYI it tests only the processor, not the memory and is optimized for core2. Ah, I don't prefer two sockets SMP computers since we will have hexa and octa core chips soon (next year? I don't remember). I agree. Hideki Łukasz Lew: c55009e70906060527i424cd3d9h525e8f87ec165...@mail.gmail.com: Hi I have few days to buy a computer for Monte-carlo Go program. There is not enough money for a multi processor, so I have to decide between - core i7 2.66 GHz - some core2 quad both subjected to over-clocking. Have you observed that Monte-Carlo Go program is faster on core i7 than on core2 ? Lukasz PS Or have you found some cheap solutions for shared memory dual processor? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- g...@nue.ci.i.u-tokyo.ac.jp (Kato) ___ 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/ -- g...@nue.ci.i.u-tokyo.ac.jp (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] bots and handicaps (Re: New CGOS)
On Sun, Jun 7, 2009 at 11:02 AM, steve uurtamo uurt...@gmail.com wrote: The handicap system is imperfect anyway, it's almost a coincidence that it works as well as it does. okay, this sounds like chess bias. the handicap system *defines* the difference in skill levels in go. it's a coincidence that something like ELO can match fairly well to stones. not the other way around. Both systems are badly broken because they both make simplfying assumptions that are just not true. It's just that the ELO systme is less broken. Here is why the handicap system is broken. We can talk about how the ELO system is broken in another discussion but it is too. At 1 or 2 stones difference, the handicap system works well.At greater handicaps it's skewed. The coincidence that I'm talking about is that it works to a reasonable degree at larger handicaps. The handicap system is based on the idea that no matter what your level of play, you can give 7 stones to a player 7 stones weaker.Everyone knows this is not true. It is very accurate at low handicaps, and progressively less accurate at high handicaps (as well as high levels) so for instance a professional player with a relatively low professional ranking does not need as many stones as indicated by his opponents ranking to beat another professional WHO IS SEVERAL RANKS HIGHER. Is this not correct? When I say it's imperfect, that is what I am talking about. There is nothing wrong with defining 1 stone handicap as a rank and I don't view that definition as imperfect and that is a reasonable basis for defining the ranking system in GO. What's imperfect is the assumption that 9 stones makes it a perfectly even match if you are 9 ranks apart no matter where along the scale you are. If you wanted to know what handicap is needed to win a match at various handicaps from beginner to world chamption, you would need a 2 dimentonal table lookup because it's not as simple as just taking the difference in their rankings.With the table lookup and a huge amout of data to back it up, you would have a predictor as good as ELO. Does that clarify what I meant when I said the handicap system is imperfect?As we discussed many times on this forum and in private email, a one stone handicap has a different meaning at different levels - it's just an awkward system to deal with mathmatically on a go server for computers where wild mismatches will be common. the fact that chess doesn't have a fine-grained way to handicap a game, in fact, the fact that most games don't, doesn't mean that it's hard to deal with. There are simple ways to deal with it. One could simply increase or decrease your rank as soon as you start winning or losing you games at your current handicap level.We don't need ELO for that and it's simple to do. What I see on most servers and in this modern day and age is a move away from the centuries old system, not an embrace of it as being superior.Of course I understand there is a sentimental attachment to it.It was like this in chess many years ago when the old fashion descriptive chess notation was replace in the USA with algebraic notation in order to stay with the modern world and to many people it was just not chess anymore. my guess is that any go playing program that doesn't depend upon an opening book for a lot of its strength is going to adapt just fine. experiments between players of different CGOS-measured strengths could find this out for sure -- time for another set of experiments? i'll donate some cpu time. It took a lot of work and energy to do these studies - I'll have to think about this one. Of course they would adapt if that was the system. Even if this idea was not good for current MCTS programs they would adjust is that was what was required to do well in competition. if it helps to encourage the authors, just keep in mind that winning with handicap is extremely convincing evidence to regular go players that one player is much stronger than another. plus, it takes exponentially fewer games to determine that difference. with a logarithmic (in range of handicap, say, +/-6 stones) number of games you could get a very accurate view of the strength difference between two players. say, take best of 2 out of 3 at each test level and do binary search. some go clubs just keep track of the relative difference in stone strength between pairs of players, requiring, say, a 3-win streak by one player to adjust the handicap by a single stone. alternatively, you can (somewhat cheesily) map ELO to handicap and vice-versa for a limited range of ELO and handicap. Like I say, a table will do it, and I believe some kind of formula could be fitted to the data. - Don s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Core i7 performance in computer-go
2009/6/7 Hideki Kato hideki_ka...@ybb.ne.jp: Łukasz, is the program multi-threaded? Is is single threaded and 32-bit. Corei7 920 runs about 7% slower than core2 at the same clock. Possibly due to the optimized code for core2? That is my belief. I will reconsider buying i7. Thank you for your benchmarks. Lukasz Experimental results follow. On a 3 GHz (333 x 9) core2 Q6600: 20 playouts in 1.49209 seconds 134.04 kpps 44.6798 kpps/GHz (clock independent) 105316/94359 (black wins / white wins), Average of the middle 10 of 12 runs is 44.79506 kpps/GHz. Raw data: 44.6798, 44.7951, 44.8276, 44.8207, 44.8398, 44.6887, 44.8317, 44.8491, 44.782, 44.7216, 44.7983, 44.8451 On a 3.6 GHz (180 x 20) corei7 920: 20 playouts in 1.34808 seconds 148.359 kpps 41.2643 kpps/GHz (clock independent) 105316/94359 (black wins / white wins), Average of the middle 10 of 12 runs is 41.57643 kpps/GHz. Raw data: 41.2643, 41.9025, 41.3732, 41.5582, 41.1666, 41.4887, 41.7724, 41.9751, 41.6362, 41.787, 41.269, 41.7128 On a 3 GHz (150 x 20) corei7 920: 20 playouts in 1.6001 seconds 124.992 kpps 40.1661 kpps/GHz (clock independent) 105316/94359 (black wins / white wins), Average of the middle 10 of 12 runs is 41.79165 kpps/GHz. Raw data: 40.1661, 41.8626, 41.8366, 41.687, 41.7099, 41.9556, 41.3053, 41.9335, 41.8255, 41.8838, 42.077, 41.9167 With hyper threading on (3 GHz 920): 20 playouts in 1.5881 seconds 125.937 kpps 41.9898 kpps/GHz (clock independent) 105316/94359 (black wins / white wins), Average of the middle 10 of 12 runs is 41.82533 kpps/GHz. Raw data: 41.9898, 42.0318, 42.0503, 41.947, 40.6079, 41.7033, 42.0283, 41.8386, 41.5187, 41.8013, 41.9114, 41.4831 Hideki Łukasz Lew: c55009e70906070309q4d6224e1s509c2d858ff7e...@mail.gmail.com: 2009/6/6 Hideki Kato hideki_ka...@ybb.ne.jp: Hi Lukasz, I have five core2 and one i7 computers running at home. I prefer i7, though don't have exact measure. The most important difference is the memory interface, ie, core2 uses a obsolete common bus (FSB) while i7 uses p2p connection with an internal (on chip) memory controller. Also, core2 uses DDR2 (obsolete) and i7 uses DDR3 memory modules. I know the technical differences. I just wonder do they matter in practice of computer-go On overclocking, i7 performs better. i7 920 (cheapest model) runs at 3.6 GHz (C0 stepping; recent D0 is said at 4 GHz) while core2 Q9550 (middle range model) runs at 3.2 GHz, with a rather silent air cooling. thanks. If you have a benchmark program please send me. Ubuntu Linux or WIndows XP is fine. http://www.mimuw.edu.pl/~lew/engine.gz please run with: ./engine --seed 123 -b FYI it tests only the processor, not the memory and is optimized for core2. Ah, I don't prefer two sockets SMP computers since we will have hexa and octa core chips soon (next year? I don't remember). I agree. Hideki Łukasz Lew: c55009e70906060527i424cd3d9h525e8f87ec165...@mail.gmail.com: Hi I have few days to buy a computer for Monte-carlo Go program. There is not enough money for a multi processor, so I have to decide between - core i7 2.66 GHz - some core2 quad both subjected to over-clocking. Have you observed that Monte-Carlo Go program is faster on core i7 than on core2 ? Lukasz PS Or have you found some cheap solutions for shared memory dual processor? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- g...@nue.ci.i.u-tokyo.ac.jp (Kato) ___ 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/ -- g...@nue.ci.i.u-tokyo.ac.jp (Kato) ___ 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] bots and handicaps (Re: New CGOS)
Pro ranks are assumed to be about 1/3 of a stone; the one stone per rank formula applies to amateur ranks. I have watched a pro 8p regularly give three stones to a 6 dan amateur. A weaker pro might give the same player 2 stones. Some ( including myself in the past ) have argued that they can easily beat a person who is nine ranks higher with a nine stone handicap. I have done this often enough that I believed it. However, after losing a fair number of such 9-stone games, I conclude that many people slack off, assuming that their opponent is really inept; if the weaker player can keep most of his groups alive, and pressure white, he will win. When white aggressively exploits weak groups, the weaker player's positions collapse. A dan-level player has an understanding of life and death which seems almost magical to a weaker player. When that superior knowledge is exploited, the weaker player crumbles. Last week, I played a series of 9-stone games. After losing three in a row, my opponent thanked me for giving him a serious challenge. I think many players do not rise to that challenge; they don't apply their full strength against kyu-level players. Until computer programs rise to the level of even play against pros, human-computer matches will be handicap games. It makes sense to develop the ability to play handicap games well. It would be sad if a program with a seven stone handicap frittered away its advantage instead of hoarding it jealously. Terry McIntyre terrymcint...@yahoo.com Any system of entrusting the government to judge and correct its own abuses is the same as appointing the accused criminal as his own judge and jury: don't expect many convictions. -- Allen Thornton, Laws of the Jungle ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] bots and handicaps (Re: New CGOS)
I can't really agree with this statement. My customers tell me they would much rather play a challenging even game against an opponent of their level, than a challenging handicap game against a much stronger or much weaker opponent. This is why version 12 of Many Faces has levels that are calibrated to be about 3 stones apart, so there is always a level that does not require a handicap, unless you are weaker than 20 kyu or stronger than 1 dan. Until computer programs rise to the level of even play against pros, human-computer matches will be handicap games. It makes sense to develop the ability to play handicap games well. It would be sad if a program with a seven stone handicap frittered away its advantage instead of hoarding it jealously. Terry McIntyre terrymcint...@yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] bots and handicaps (Re: New CGOS)
At 1 or 2 stones difference, the handicap system works well.At greater handicaps it's skewed. The coincidence that I'm talking about is that it works to a reasonable degree at larger handicaps. The handicap system is based on the idea that no matter what your level of play, you can give 7 stones to a player 7 stones weaker.Everyone knows this is not true. It is very accurate at low handicaps, and progressively less accurate at high handicaps (as well as high levels) so for instance a professional player with a relatively low professional ranking does not need as many stones as indicated by his opponents ranking to beat another professional WHO IS SEVERAL RANKS HIGHER. Is handicap accurate at all with professional ranks? I've heard before that they are 1/4 stone apart. I am 3k on KGS and I'd say that I win nearly every game that I give handicap and lose over half the games that I receive handicap. That would seem to imply that more handicap should be given near my rank. Is this not correct? When I say it's imperfect, that is what I am talking about. There is nothing wrong with defining 1 stone handicap as a rank and I don't view that definition as imperfect and that is a reasonable basis for defining the ranking system in GO. What's imperfect is the assumption that 9 stones makes it a perfectly even match if you are 9 ranks apart no matter where along the scale you are. If you wanted to know what handicap is needed to win a match at various handicaps from beginner to world chamption, you would need a 2 dimentonal table lookup because it's not as simple as just taking the difference in their rankings.With the table lookup and a huge amout of data to back it up, you would have a predictor as good as ELO. Does that clarify what I meant when I said the handicap system is imperfect?As we discussed many times on this forum and in private email, a one stone handicap has a different meaning at different levels - it's just an awkward system to deal with mathmatically on a go server for computers where wild mismatches will be common. the fact that chess doesn't have a fine-grained way to handicap a game, in fact, the fact that most games don't, doesn't mean that it's hard to deal with. There are simple ways to deal with it. One could simply increase or decrease your rank as soon as you start winning or losing you games at your current handicap level.We don't need ELO for that and it's simple to do. What I see on most servers and in this modern day and age is a move away from the centuries old system, not an embrace of it as being superior.Of course I understand there is a sentimental attachment to it.It was like this in chess many years ago when the old fashion descriptive chess notation was replace in the USA with algebraic notation in order to stay with the modern world and to many people it was just not chess anymore. my guess is that any go playing program that doesn't depend upon an opening book for a lot of its strength is going to adapt just fine. experiments between players of different CGOS-measured strengths could find this out for sure -- time for another set of experiments? i'll donate some cpu time. It took a lot of work and energy to do these studies - I'll have to think about this one. Of course they would adapt if that was the system. Even if this idea was not good for current MCTS programs they would adjust is that was what was required to do well in competition. if it helps to encourage the authors, just keep in mind that winning with handicap is extremely convincing evidence to regular go players that one player is much stronger than another. plus, it takes exponentially fewer games to determine that difference. with a logarithmic (in range of handicap, say, +/-6 stones) number of games you could get a very accurate view of the strength difference between two players. say, take best of 2 out of 3 at each test level and do binary search. some go clubs just keep track of the relative difference in stone strength between pairs of players, requiring, say, a 3-win streak by one player to adjust the handicap by a single stone. alternatively, you can (somewhat cheesily) map ELO to handicap and vice-versa for a limited range of ELO and handicap. Like I say, a table will do it, and I believe some kind of formula could be fitted to the data. - Don s. ___ 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 mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Tweak to MCTS selection criterion
Many Faces does this. This is kind of interesting. Is anybody measuring their playout performance in real-time at the moment and performing this sort of computation, to check if overtaking the leading move is mathematically impossible? Christian Don Dailey wrote: 2009/6/6 dhillism...@netscape.net mailto:dhillism...@netscape.net I think this is one of those design decisions that nobody takes on faith. We all wind up testing it both ways and in various combinations. An additional advantage of using the number of visits is that branches at the root become mathematically eliminated and can be pruned away. It often also allows the search to be stopped early. It can save a lot of time for forced moves. Let me see if I understand what you are saying here. If you have set a goal time for thinking of 10 seconds, and let's say 6 seconds have progressed, then it might be possible to stop the search early if you do the math and see that it's not possible for any other move to have more visits given an additional 4 seconds? So when there is a position that has only a single clearly best move, perhaps a capture that cannot wait or a necessary atari defense, then you can probably save as much (or close to) as half the thinking time on that move.Is this correct? So if this understanding is correct, then it still makes sense to do the pebbles test at this point and check to see if another move has a higher score before stopping the search.If the move really is forced and necessary, then the answer will be no and you can stop early. If there is a move that currently appears better but with a too small sample, then it seems foolish to stop early.If the move is a result of just a few lucky playouts, then it will quickly be revealed and you can still stop early. - Don - Dave Hillis -Original Message- From: Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com To: computer-go computer-go@computer-go.org mailto:computer-go@computer-go.org Sent: Sat, 6 Jun 2009 5:07 pm Subject: Re: [computer-go] Tweak to MCTS selection criterion Another strategy to be considered is to not allow the thinking to cease until the maximum win rate and the maximum visit count agree on the same move. Obviously this requires some extra code to make sure you don't lose on time, etc. Brian Sheppard wrote: When a UCT search is completed, the usual selection criterion is choose the move that has the most trials. This is more stable than choosing the move that has the highest percentage of wins, since it is possible to have an unreliably high percentage if the number of trials is small. I have a small tweak to that criterion. Pebbles uses choose the move that has the most wins. This rule selects the same move as the conventional criterion in almost every case. The reason why Pebbles' rule is superior is revealed in the case where the moves differ. When Pebbles chooses a different move than the conventional criterion, it is because Pebbles move has more wins in fewer trials. When that happens, Pebbles move would inevitably become the move with the most trials if searching were to continue. So there is actually no downside. Of course, the upside is minor, too. For validation, Pebbles has been using both strategies on CGOS games. At present, the conventional selection strategy has won 341/498 = 68.47%. Pebbles strategy has won 415/583 = 71.18%. This isn't statistically conclusive or anything (0.7 standard deviations; we would need 4 to 8 times as many trials for strong statistical evidence). But Pebbles' strategy should be better by a small amount, and it has been, so I present it to you with confidence. Best, Brian ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Wanna slim down for summer? Go to America Takes it Off http://www.aolhealth.com/diet/weight-loss- program/?ncid=emlcntusheal0001 to learn how. ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org
Re: [computer-go] bots and handicaps (Re: New CGOS)
I was referring to matches against pro players. It's going to be a while before a computer can win even games against pros, therefore we must assume that any such matches will involve the program taking a handicap. My personal preference is the strongest possible opponent. When reviewing games that I have won against computer programs, I find that tweaking just one computer move would often destroy my position; hence, I was getting false feedback, believing my position to be superior when in fact it was terribly weak. Play against devastatingly strong opponents (from my point of view) has motivated me to discover (and hopefully repair) weaknesses in my reading skills. Playing against opponents of my level only encourages me to be a little trickier - to push problems beyond the horizon of my opponent's skills (and often my own). Terry McIntyre terrymcint...@yahoo.com Any system of entrusting the government to judge and correct its own abuses is the same as appointing the accused criminal as his own judge and jury: don't expect many convictions. -- Allen Thornton, Laws of the Jungle From: David Fotland fotl...@smart-games.com To: computer-go computer-go@computer-go.org Sent: Sunday, June 7, 2009 11:06:37 AM Subject: RE: [computer-go] bots and handicaps (Re: New CGOS) I can’t really agree with this statement. My customers tell me they would much rather play a challenging even game against an opponent of their level, than a challenging handicap game against a much stronger or much weaker opponent. This is why version 12 of Many Faces has levels that are calibrated to be about 3 stones apart, so there is always a level that does not require a handicap, unless you are weaker than 20 kyu or stronger than 1 dan. Until computer programs rise to the level of even play against pros, human-computer matches will be handicap games. It makes sense to develop the ability to play handicap games well. It would be sad if a program with a seven stone handicap frittered away its advantage instead of hoarding it jealously. Terry McIntyre terrymcint...@yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] bots and handicaps (Re: New CGOS)
Don Daily wrote: so for instance a professional player with a relatively low professional ranking does not need as many stones as indicated by his opponents ranking to beat another professional WHO IS SEVERAL RANKS HIGHER. For centuries pro ranks were defined by the handicap required against other pro's. But the difference between pro dans is smaller than a stone per rank. rank difference = handicap 0p = alternating black and white 1p = black in two out of three games 2p = black in all games 3p = two stones in one out of three games, black in two out of three games 4p = two stones in two out of three games, black in one out of three games 5p = two stones in all games ... 8p = three stones in all games These were the handicaps defining pro ranks in Japan up until 2003 (in 2003 they dropped the handicap system but it was not changed into a rating system either http://senseis.xmp.net/?NihonKiInNewPromotionSystem http://senseis.xmp.net/?NihonKiInNewPromotionSystem . In fact I think the new system seems quite arbitrary and unpredictible): Dave de Vos Van: computer-go-boun...@computer-go.org namens Don Dailey Verzonden: zo 7-6-2009 18:10 Aan: computer-go Onderwerp: Re: [computer-go] bots and handicaps (Re: New CGOS) Here is why the handicap system is broken. We can talk about how the ELO system is broken in another discussion but it is too. At 1 or 2 stones difference, the handicap system works well.At greater handicaps it's skewed. The coincidence that I'm talking about is that it works to a reasonable degree at larger handicaps. The handicap system is based on the idea that no matter what your level of play, you can give 7 stones to a player 7 stones weaker.Everyone knows this is not true. It is very accurate at low handicaps, and progressively less accurate at high handicaps (as well as high levels) so for instance a professional player with a relatively low professional ranking does not need as many stones as indicated by his opponents ranking to beat another professional WHO IS SEVERAL RANKS HIGHER. Is this not correct? When I say it's imperfect, that is what I am talking about. There is nothing wrong with defining 1 stone handicap as a rank and I don't view that definition as imperfect and that is a reasonable basis for defining the ranking system in GO. What's imperfect is the assumption that 9 stones makes it a perfectly even match if you are 9 ranks apart no matter where along the scale you are. If you wanted to know what handicap is needed to win a match at various handicaps from beginner to world chamption, you would need a 2 dimentonal table lookup because it's not as simple as just taking the difference in their rankings.With the table lookup and a huge amout of data to back it up, you would have a predictor as good as ELO. Does that clarify what I meant when I said the handicap system is imperfect? As we discussed many times on this forum and in private email, a one stone handicap has a different meaning at different levels - it's just an awkward system to deal with mathmatically on a go server for computers where wild mismatches will be common. the fact that chess doesn't have a fine-grained way to handicap a game, in fact, the fact that most games don't, doesn't mean that it's hard to deal with. There are simple ways to deal with it. One could simply increase or decrease your rank as soon as you start winning or losing you games at your current handicap level.We don't need ELO for that and it's simple to do. What I see on most servers and in this modern day and age is a move away from the centuries old system, not an embrace of it as being superior.Of course I understand there is a sentimental attachment to it.It was like this in chess many years ago when the old fashion descriptive chess notation was replace in the USA with algebraic notation in order to stay with the modern world and to many people it was just not chess anymore. my guess is that any go playing program that doesn't depend upon an opening book for a lot of its strength is going to adapt just fine. experiments between players of different CGOS-measured strengths could find this out for sure -- time for another set of experiments? i'll donate some cpu time. It took a lot of work and energy to do these studies - I'll have to think about this one. Of course they would adapt if that was the system. Even if this idea was not good for current MCTS programs they would adjust is that was what was required to do well in competition. if it helps to encourage the authors, just keep in mind that winning with handicap is extremely convincing evidence to regular go players that one player is much stronger than another. plus, it takes exponentially fewer
RE: [computer-go] bots and handicaps (Re: New CGOS)
I am 3k on KGS and I'd say that I win nearly every game that I give handicap and lose over half the games that I receive handicap. That would seem to imply that more handicap should be given near my rank. That is because the KGS rating system is not based on handicap. It is based on winning rates in even games like an Elo system (but it is probably weighted like the EGF system so that it stays more or less aligned to the traditional go rank system. None of these rating systems seems to have found a satisfactory set of weights to achieve a good alignment, but I think EGF does it better than KGS) Dave de Vos ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Tweak to MCTS selection criterion
check if overtaking the leading move is mathematically impossible? Yes. Pebbles does this. Please note that the discussion has veered into time control policy, which is not the subject of the original post. The original post discusses move selection policy: when your program stops, for whatever reason, which move should it select? Pebbles' policy is to select the move that has the most wins, rather than the most trials. Pebbles policy is a risk-free improvement over the standard policy of selecting the move that has the most trials. Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
