Re: [computer-go] Dynamic Komi at 9x9 ?
Fuego_9x9_1h (or a variation of this name) played on OGS a couple of handicap 9x9 games. It used dynamic komi. I think it was manually adjusted after every move, and worked well. -ibd Am 17.02.2010 um 22:51 schrieb Ingo Althöfer: Hello, I informed the German go scene that there is (some) progress at KGS bots with dynamic komi. Based on this, a friend told me that they would have an open afternoon for go beginners in the middle of March - and they expect many newbies with strengths between 17k and 30k. His question is if a bot with dynamic komi might be a suitable opponent for such beginners on 9x9 (with high handicap). Does someone here have already experience with non-static komi for handicap games on 9x9? Or would someone be willing to test something with his bot? Ingo. -- NEU: Mit GMX DSL über 1000,- ¿ sparen! http://portal.gmx.net/de/go/dsl02 ___ 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] kgsGtp has changed
It looks like zengg19 on KGS has to be restarted with the new version, it keeps crashing, or so it seems. Am 27.12.2009 um 13:09 schrieb Hiroshi Yamashita: It seems KGS client has changed. Old kgsGtp does not work. Latest version (kgsGtp-3.3.27) is ok. kgsGtp-3.3.27.zip http://www.gokgs.com/download.jsp Regards, Hiroshi Yamashita ___ 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] pure 3x3 pattern playouts weaker than light playouts?
I now have playouts based on 3x3 pattern weights. When I tested it on CGOS it seemed to be weaker than my old engine which used light playouts only. I used a comparable setup, and the elo difference is about 100 after more than 150 games. I can also seem some weird RAVE value patterns (not 1-1 points are the worst, but the 2-1/2-2 points), but they are symmetrical so I doubt it's a bug. Is this a known phenomenon and are 3x3 patterns only strong in combination with more knowledge, or should I start debugging? Or is it possibly an effect caused by the rating of the cgos bots not being the same as when I first tested? regards, ibd ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] pure 3x3 pattern playouts weaker than light playouts?
50k playouts. they apply globally. Am 13.09.2009 um 01:22 schrieb Jason House: Same number of playouts? What are your pattern weights? Do they apply around the last move played or for all board areas? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] pure 3x3 pattern playouts weaker than light playouts?
Did you learn weight for every possible pattern using the crazystone algorithm, or are you just using the basic mogo patterns? No, all 1000 and something weights are learned using the algorithm. Are you using global patterns as UCT priors, or to choose moves during playouts? During playout it’s important to favor local responses. David No, there are no priors yet, only RAVE. I only use it during playouts. Currently, the playouts only follow the patterns, no other weights. Thanks, ibd___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CUDA implementation of the per-intersection GPGPU approach
maybe some divide conquer algorithm? Am 10.09.2009 um 14:43 schrieb Petr Baudis: On Thu, Sep 10, 2009 at 08:29:31AM -0400, Jason House wrote: I've thought of something similar in the past, but with a twist: pre-compute a subset of moves that could be safely played in parallel. Even if you can only play 285 moves in parallel on an empty 19x19, it could still be a huge speed boost. Hmm, do you have some ideas how this pre-computation could be done in less than O(N)? I'm gonna think about this now during some travelling... ;-) Petr Pasky Baudis ___ 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] CGOS Engine does NOT use time control commands
I always see this message when booting up CGOS. However, my program supports time_left and I also state this in list_commands. Time control would be much better if I got feedback from the server. How can I use it? Is there a special command I'm missing? Thanks, Isaac ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CGOS Engine does NOT use time control commands
thanks, it works! Am 10.09.2009 um 18:49 schrieb Go Fast: I think it needs time_settings On Thu, Sep 10, 2009 at 12:37 PM, Isaac Deutsch i...@gmx.ch wrote: I always see this message when booting up CGOS. However, my program supports time_left and I also state this in list_commands. Time control would be much better if I got feedback from the server. How can I use it? Is there a special command I'm missing? Thanks, Isaac ___ 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] any mac programmers out there?
Yes, I'm one. Haven't upgraded to SL yet, though. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IGS?
I watched a game of your bot, and it still fills its own eyes, killing alive groups. I suggest you strictly forbid eye-filling moves until the bot is much stronger (I think it is needed in very few cases to kill groups). Also it plays many, many bad self-atari moves into the tiger mouth shape. If you evaluate positions and give them a score, these moves should receive a worse score. Do you have an account on KGS? (Human, not bot :) That said, I think you have enough testing opportunities on KGS and CGOS. It's probably not worth the hassle if IGS doesn't support normal GTP for bots. :p -ibd Am 05.09.2009 um 18:07 schrieb Folkert van Heusden: Hi, Does anyone know how to interface your go program to IGS? It is already on KGS and CGOS but would like to have it play on IGS as well. Folkert van Heusden -- MultiTail ist eine flexible Applikation um Logfiles und Kommando Eingaben zu überprüfen. Inkl. Filter, Farben, Zusammenführen, Ansichten etc. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ 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] Monte-Carlo Simulation Balancing
I admit I had trouble understanding the details of the paper. What I think is the biggest problem for applying this to bigger (up to 19x19) games is that you somehow need access to the true value of a move, i.e. it's a win or a loss. On the 5x5 board they used, this might be approximated pretty well, but there's no chance on 19x19 to do so. Am 13.08.2009 um 05:14 schrieb Michael Williams: After about the 5th reading, I'm concluding that this is an excellent paper. Is anyone (besides the authors) doing research based on this? There is a lot to do. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
With crazystone-like playouts, you can just put noise over the possibilites. the more noise, the more random the playout is, which is weaker. The best move in the tree is then the one that requires the least amount of noise for the other player to reach 50% win chance if behind, or the one that requires the most amount of noise for me if ahead. Would that work? Am 13.08.2009 um 16:02 schrieb Don Dailey: This idea makes much more sense to me than adjusting komi does. At least it's an attempt at opponent modeling, which is the actual problem that should be addressed. Whether it will actually work is something that could be tested. Another similar idea is not to pass but to play some percentage of random moves - which probably would work in programs with strong playout strategies. Of course this would be meaningless for bots that have weak (and already random) playout strategies. - Don On Thu, Aug 13, 2009 at 6:17 AM, Tapani Raiko pra...@cis.hut.fi wrote: I don't think the komi should be adjusted. Instead: Wouldn't random passing by black during the playouts model black making mistakes much more accurately? The number of random passes should be adjusted such that the playouts are close to 50/50. Adjusting the komi would make black play greedily, while random passing during playouts would make black play safe (rich men don't pick fights). Tapani Raiko Christoph Birk wrote: I think you got it the wrong way round. Without dynamic komi (in high ha ndicap games) even trillions of simulations with _not_ find a move that creates a winning line, because the is none, if the opponet has the same strength as you. WHITE has to assume that BLACK will make mistakes, otherwise there would be no handicap. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Tapani Raiko, tapani.ra...@tkk.fi, +358 50 5225750 http://www.iki.fi/raiko/ ___ 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] new kid on the block
Congrats for breaking the 1000 elo mark on cgos. ;) Some things I noticed when watching 2 games: -stop plays on the first line/corner in the beginning. maybe this helps: http://computer-go.org/pipermail/computer-go/2008-December/017340.html or this: http://computer-go.org/pipermail/computer-go/2008-December/017457.html -stop fills its own eyes, killing alive groups. you should prevent moves that fill own eyes. look here: http://computer-go.org/pipermail/computer-go/2008-May/014929.html regards, ibd ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] O-Meien vs Zen
Congrats for a good 19x19 game and a won 9x9 game. -ibd ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] O-Meien vs Zen
Did you think the bot would not benefit much from additional time usage? Am 10.08.2009 um 15:46 schrieb Yamato: Thank you all for watching the games against O Meien 9p. He was very strong. I am sorry that Zen did not play very good. Ingo Althöfer wrote: Why did Zen play so quickly in the 19x19 game? Only very seldomly it used more than 2 seconds to reply. I don't think it was so quick. The setting was 15 seconds per move. -- Yamato ___ 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] Crazystone-like playouts
Hi, I have some questions regarding the crazystone-like playouts I'm trying to implement. 1. What data type should I use for the weights? So far I tried integers, floats and doubles. Integers are good because they have no precision issues, but I think I might have problems with overflowing later on, when adding more weights. If I have weights between 0-1, that might be the case, especially for the row/total sums. Floats don't have the problem, but I got some precision issues that are not so easy to fix. Doubles have neither problem (or not as pronounced), but I think they're a bit slower, and they also take twice the space. 2. When a position becomes illegal, should I stop updating its weight and recalculate it when it becomes legal again? The other way is to update the weight anyway. This question only concerns certain features such as patterns, but maybe also distance to last move. On one hand, updating anyway might be a bit faster per update but slower over all. On the other hand, recalculating when a position becomes legal again should be faster, but it requires the handling of more special cases like ko, and certain dead group shapes. Do you have any tips for making the playouts faster? My goal is 20k/s, so far I've only reached about 15k/s (using the method of always updating described at 2.) with a bit of optimizing. I have a mercy rule. I also read about using patterns as much as possible, but I only use the 3x3 patterns for eye knowledge. Thanks and regards, Isaac Deutsch ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
I planned to enter the august tournament but development progressed slower than expected. I plan to enter the september tournament. You'll have 1 weak bot more ;) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] new kid on the block
Welcome. :) Consider implementing GTP so that your program can be used with nice GUIs such as GoGui. Regards, Isaac Am 29.07.2009 um 13:49 schrieb Folkert van Heusden: I started yesterday to create a new Go program. It is called 'Stop' and is written in Java. The .jar-file can be found on my website: http://www.vanheusden.com/stop/ It is console-only (i.e. text-only) and can be invoked like this: java -jar stop-0.2.jar It is still very much in the beginning of development so some bugs may still exist. All feedback is welcome! Folkert van Heusden -- MultiTail cok yonlu kullanimli bir program, loglari okumak, verilen kommandolari yerine getirebilen. Filter, renk verme, merge, 'diff- view', vs. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ 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] Global RAVE
Similar to normal RAVE: Initially it was weighted 1:0 with UCT, eventually 0:1 with UCT. I think it reached zero weight after about 5000 games. Am 25.07.2009 um 00:59 schrieb Peter Drake: Did you weigh these data as heavily as the raw Monte Carlo data, or discount them somehow? On Jul 24, 2009, at 3:50 PM, Isaac Deutsch wrote: My program performed worse with this (about 50 elo), but I didn't combine it with RAVE (just pure UCT with this). Am 25.07.2009 um 00:38 schrieb Peter Drake: Is anyone also using a global table of moves made after ALL nodes in the search, a sort of global RAVE table? It would be noisier still, but it would fill with useful data very quickly, no? Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Peter Drake http://www.lclark.edu/~drake/ ___ 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] Computating ELO ratings, again.
Hello, I have a question regarding the paper by Rémi Coulom. There is a link to it here: http://computer-go.org/pipermail/computer-go/2007-December/012557.html My first question also relates to that mailing list post. Rémi says: My suggestion would be to test your code with very small amounts of artificial data. For instance, start by two players A and B, and, say A beats B twice and B beats A once. Gammas should converge to gamma_A = 2 * gamma_B. I tried this test and it converges to the right solution when I have no prior. When I have a prior (which means 2 competitions where each feature wins and loses once versus a dummy feature), it does not converge to the right solution. Instead, gamma_A approx. = 1.66 * gamma_B. Is this normal? Also, are there other artificial tests I could try? Secondly, I used the technique explained in the paper to calculate ELO data for various features, including 3x3 patterns. I get good convergence for all features except the 3x3 patterns. I have made a chart showing this: http://files.getdropbox.com/u/1298345/elo.png It is most notable for the connection pattern (an example 3x3 pattern that connects 2 groups), but it also applies to the hane and empty triangle pattern. It seems like the gamma value isn't totally wrong, but it doesn't converge to a stable value but to zero instead. Any ideas how I can fix this, or where I should start debugging? I used about 4000 pro games and every 4th move in these games for training data, so about 100k trained positions. I do merge symmetrical patterns. Regards, Isaac___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Computating ELO ratings, again.
Am 24.07.2009 um 16:25 schrieb Jason House: Adding a prior through a 3rd player should alter your results. There's minimal data on how A compares to B, so since the data for dummy says they're equal, you should expect results closer to one. You could do priors that simply set the initial guesses. That won't alter the results. You also could increase the number of games between A and B. That'll push the results back to theoretical. Are you sure the connect pattern is still valuable once the other patterns are taken into account? It may be that without other knowledge, it works well, but that a full pattern set can better differentiate when a connection is good or not? Sent from my iPhone Hi Jason, OK I see that this alters the result. The full pattern set is just all 3x3 patterns, so there isn't a lot of additional knowledge. Nevertheless, there is a downwards tendency for all patterns. You can find the exact patterns (triangle, connect and hane) and the average rating of all patterns here: http://pastie.org/557743 Thanks, Isaac___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Computating ELO ratings, again.
An overall drift in the numbers might be nothing. Some pattern (sub)sets can be multiplied by a constant value without affecting overall prediction accuracy. Fixing one or more gamma values may fix your drift issue. I think Remí's paper forced the average gamma to be 1 after each iteration. If I fixed the average gamma, wouldn't that make the other features drift *upwards*? I know it isn't a problem in general, but if the number range is too big I might get precision issues. Do you suggest I fix the value of a single 3x3 pattern? Would that stabilize the 3x3 pattern values or would it also affect the other values (extend, kill, etc.)?___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Computating ELO ratings, again.
To answer exactly, I need to know more about how you set up your patterns. If every point gets one, and exactly one 3x3 pattern, then fixing one 3x3 pattern is required. If some points have no 3x3 pattern, then you're implicitly fixing an other pattern to a value of 1 and then no fixing of a 3x3 pattern is needed. Just like 3x3 patterns, any orthogonal subset should have one value fixed... Does that help? When teaching a position, all legal positions get a pattern. This means positions that would be suicidal, ko, or aren't empty get no pattern. All legal positions get exactly one 3x3 pattern assigned. What do you mean with orthogonal subset? Please tell me if you need more information. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Computating ELO ratings, again.
It sounds to me like your 3x3 patterns are an orthogonal set relative to everything else. Because of that, you must pin on 3x3 gamma. You may need to pin a few more... Note that any set of features where you don't pick one for every legal move doesn't require pinning because you implicitly have an anything else that is pinned to a value of 1. I hope that helps! Thanks a lot Jason, I understand clearly now! It's exactly the way you described. I hope I'll get my bot to run until the next tournament. ;) -ibd ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Global RAVE
My program performed worse with this (about 50 elo), but I didn't combine it with RAVE (just pure UCT with this). Am 25.07.2009 um 00:38 schrieb Peter Drake: Is anyone also using a global table of moves made after ALL nodes in the search, a sort of global RAVE table? It would be noisier still, but it would fill with useful data very quickly, no? Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
I'm about to implement this. Since I have multiple features (patterns, is in atari, is adjacent to last play, etc.), the weight is the product of the weight of all matching features. I'm thinking about having a table of weights, storing the sum of each row and the total (like Rémi suggested). I want to do this incrementally, so if I find a new feature match in a position, I can multiply its weight by the feature's weight. If I remove a feature, I can divide. My question/problem: How do I deal with features that have a weight of zero? I'm sure there are certain 3x3 patterns that have the weight zero, such as ### #*. #.. with * to be played. It's clear that when this pattern matches, the total weight is set to zero. How do I find the resulting weight when removing this pattern, though? Since I can't divide by zero, I would have to reconstruct the weight by checking all features, which would be relatively slow. Is there a way this can be avoided, such as setting all weights to a very low value instead of zero? Regards, Isaac___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
In my example, #=border/edge of the board, not black. I was just trying to come up with an example feature that might have weight zero to illustrate my problem. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
Thanks to both for the elaborate feedback! I was wondering about pattern symmetry, too, and I also had a lookup table in mind since there are only about 65000 combinations (and only a fraction of them legal). I had another idea for the zero weight problem: Keep a counter of how many times this weight was multiplied by zero. This counter can be stored in 1 byte or less, depending on the number of features. If the counter is 0, the weight is the floating point value. Else, the weight is zero. When adding a zero-weight-feature, increase the counter by one, else decrease it by one. This way, the weight doesn't have to be recomputed, although it uses slightly more memory than nicely packing the features in an int like in GNU Go. It seems like the rounding errors that are accumulated this way are insignificant, according to my tests. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] gtp which version to implement?
For KGS, there is kgsgtp.jar, CGOS provides scripts that connect your engine to the server, too. Am 15.07.2009 um 15:41 schrieb Carter Cheng: Where can I find information on these bridging protocols or are libraries provided for this (to the 9x9 19x19 servers)? --- On Wed, 7/15/09, Hellwig Geisse hellwig.gei...@mni.fh- giessen.de wrote: ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Basic question concerning the edges of the board
Am 13.07.2009 um 17:36 schrieb Carter Cheng: Hi, I have again been considering trying my hand at implementing a simple go program. The question I have pertains to checking for the edge of the board in capture situations and so on. For a modern CPU (given what limited information I have on this) the extra branches might result in pipeline stalls if I am constantly checking if values are in range. Is it best to extend the size of the board to say 21x21 to somehow avoid these sorts of checks? Or are the relative cost of these branches negligible in the scheme of things? Thanks in advance, Carter. If you have a 1d array, a 20*21+1 array is enough. the right edge is the left edge. There was an ascii image that illustrates it, but I can't find it right now... You can also precalculate the neighbour coordinates for each position, and reserve a special coordinate for the border. Just make sure to recalculate these when resizing the board. I don't know how fast it is to check each value if it is in range, but I think making the board a bit bigger is faster. Isaac ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Keep lists of stones in a group?
Hello, I'm thinking about wether it's better to keep a list of stones for each group in the board state or not. I'm keeping a linked list of liberties like Lukasz suggested and it is useful in many cases, but the only case that access to all stones in a group is handy is when removing it. I'm already keeping track of group membership for each stone with union-find. This is needed for the liberty management. There are 3 options I can think of: 1. Keep a doubly linked list for each group. Takes about 1.5 KB ram for 19x19. Stone insertion is O(1), merging is O(1). 2. Keep a simple linked list. Takes about 700B ram. Stone insertion is O(1), but merging is O(min(n,m)) where n,m are the sizes of the groups being merged. 3. Don't keep lists at all. No merging or insertion, takes no ram. In all 3 cases, removing a group takes O(n), n being the size of the group. Option 3 might be a bit slower there because a stack has to be used to perform DFS on the group, also option 3 takes additional memory for the stack. Over all, which do you think is the fastest? All options seem to take about the same amount of effort to maintain. Regards, Isaac p.s. Sorry if this is a double post, I couldn't verify that the message was sent to the mailing list the first time. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Keep lists of stones in a group?
Isn't 4. similar to doubly linked lists? You have to keep almost as many pointers as there are points on the board at most. How do you effectively store the pointers to only use as few as possible? I don't see how 5) is good for removing groups. Are there other uses for the bitmaps? Am 11.07.2009 um 18:27 schrieb Moi de Quoi: On Sat, 2009-07-11 at 08:57 -0700, David Fotland wrote: 4. Keep a singly linked list of stones for each group and keep an additional pointer for each group to the last element of the list. This is what I do in Many Faces. 5) Use a bitmap. This costs a bit more memory (if one bitmap is allocated per stone), but may have a better locality of reference. Also, there are fewer corner cases wrt cyclic/ empty linked lists, etc. AvK ___ 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] Hash tables
Okay, I've almost got it. I'm also looking into implementing a transposition table. Some things are still unclear to me. If you're hashing by chaining, you presumably go to the appropriate slot in the table, then traverse the (short) linked list of nodes hanging from that slot. If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. How do you find such a node without a lengthy search? Peter Drake http://www.lclark.edu/~drake/ Firstly, I don't understand the problem you describe: If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. Are you referring to a node that was inserted, then overwritten, and now you need it again? Secondly, to find a node that has to be overwritten, do you have a criteria that always finds the node the least probable to be used again, or can it also return that there aren't any nodes in this chain that should be overwritten? The first one would always limit the search to a single chain, without looking at other chains in the hash table, wouldn't it? Isaac ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Monte-Carlo Simulation Balancing
Has anyone tried this algorithm improvement on bigger boards and can give us a result? Link to original message: http://computer-go.org/pipermail/computer-go/2009-April/018159.html Thanks, ibd So maybe I could get 600 more Elo points with your method. And even more on 19x19. I noticed that, in general, changes in the playout policy have a much bigger impact on larger boards than on smaller boards. As to whether we can extrapolate, I hope so :-) I share the same feeling that improving the simulation policy will be more impactful on bigger boards with longer simulations. On the other hand I've been surprised by many things in MC Go, so nothing is certain until we try it! -Dave -- GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT! Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New CGOS - need your thoughts.
I'm voting for 2 time settings: One normal and one fast (so maybe 5 min and 1 min on 9x9). -- GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT! Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] building a combinatorial game theory bot
Sounds interesting. Have you considered learning these temperatures from pro games? -- GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT! Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] multithread performance
Hi, I did some tests with my program about how well it does using 2 threads instead of using only 1 thread. I played 200 games of 9x9 with 5 min SD using gogui's twogtp. Here's the results: rango (my program), 1 thread vs. gnugo: 46.7 +-3.5% wins rango, 2 threads vs. gnugo: 54.5 +-3.5% wins rango, 2 threads vs. rango, 1 thread: 54.8 +-3.5% wins Do you have any comparable data, also how it scales with more than 2 cores (which I don't have...)? It seems the difference of an additional core vs. gnugo is much bigger than versus the program itself. Regards, -ibd -- GMX FreeDSL mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.! http://dslspecial.gmx.de/freedsl-aktionspreis/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to Steenvreter!
Congrats to stv. But I would prefer more, and would like to know what I might do to attract more entrants. Nick What about a Rengo tournament? :) I don't know how feasible that would be, but it could be fun to have programs cope with someone else on their team. -- GMX FreeDSL mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.! http://dslspecial.gmx.de/freedsl-aktionspreis/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] UCT tree pruning
Hi. I've been thinking about pondering, and the way the tree has to be built to support pondering. Because with pondering, the thinking time for a move can be very big theoretically, I would like to handle automatic pruning of the tree to avoid running out of memory. Right now I have a fixed size pool of nodes, and I simply stop the tree from growing when I see that all nodes are used. However I'm afraid this could hurt the performance when thinking times are very long. This brings me to my question: When I see that I'm running out of memory, which leaves/subtrees of the UCT tree should be pruned? -Prune moves with a low winrate and a low variance. This would favor nodes near the root, and often lots of memory would be freed this way. However, one has to be careful not to prune potentially good moves. -Prune leaf nodes with little visits that are old. This would have a small impact on the UCT search but the memory freed is very little, meaning I would have to do a lot of pruning. Another approach would be of course to just let the tree grow indefinitely and hope that it will not use too much memory, but I'm not sure it would work well in all situations. What do you do in your programs? Have you tested other approaches? Do you think hard pruning is bad in general? Regards, -ibd -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
In dimwit we simply increase the number of visits to a node before it is added to the UCT tree, to slow down its growth. I wasn't too happy about how selective the tree got with a long time to think, but it's unclear if this particular hack had anything to do with that. Álvaro. I already do this - a node is expanded if it has 4 visits. Still, I worry about not being able to prune the tree. Are you suggesting that it is unlikely that I will run into memory problems? Isaac -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
No. We use a threshold that is a function of how large the tree already is. It starts at 5 and then we increase it as the tree grows larger. I think the exact formula scaled with something like the log(tree_size)^2, but I would have to check when I get home. Álvaro. Ah, now I understand. I'm not sure if I like the idea because the tree is very much shaped based on the initial estimated values. Do you think it is not a problem that the tree might struggle to converge to the best move once it has explored a long line that doesn't work? Greetings, Isaac -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to Fuego, the new champion!
Wow, you're fast to congratulate. ;) Congratulations from me, too. Isaac -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Choosing moves in playouts.
Hello, I'm about to work on heavy playouts, and I'm not sure how to choose a move during the playout. I intend to have weights for various features. I thought about 3 versions: 1. In a position, calculate all the weights and the total weight. Then, play one move i with the probability weight_i/total_weight. 2. Select a move randomly. Calculate the weight of it, then squash that weight in the [0,1] range. Play that move with that probability. 3. Same as 2., but play that move if the probability is higher than a certain treshold. Which one do you think works best? I'm looking forward to other ideas, too. :) -Isaac -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Infinite loop between CGOS and cgosGtp.kit
Does my session on CGOS eventually time out? Yes, you'll have to wait until it times out before you can log in again. This is a bit annoying because you can't immediately reconnect after a disconnect. -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
Hi Lukasz, I think I understand the way it is done for storing the stones; I do it exactly the same way. For the liberties: Does the index of the direction (NWSE) state where the chain is in respect to the liberty? So if you place a single stone on the board at position, you add 4 liberties and link them: - left of position, E - right of position, W - below of position, N - above of position, S Is that correct? I have another question. How do you efficiently track visited positions to avoid superko? I use zobrist hashing, but the memory it uses is quite big, and I think copying it from board to board takes a lot of time. Of course I don't do superko checks in the playouts, but in the UCT tree I have to check for it. Isaac Now the liberties. One liberty can be in many groups. But in only as many as 4. Let's call links between neighboring vertices pseudoliberties. Now we can create a structure similar to chain_next_v that track all pseudo-liberties of a group. It would be again map implemented as an array indexed by vertex and direction (N,W,S,E). Now when you merge you just go over this list and throw away duplicates. This can be done in linear time using another map-array vertex - bool. That will have info whether particular liberty (vertex without direction) was already in visited. Hope this helps :) Lukasz -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Zobrist hashing
Yep. I'm thinking about implementing it in libego with heavy playouts for demonstration. Maybe It will get libego some attention. :) Thanks for your answers. I'm impressed with the speed of your library. I use zobrist hashing as well. But the random base is separated from board and shared so I don't copy it. I copy just a xor hash which is no more than 8 bytes per board. I have an array that stores for each position and color combination a random ushort (2 bytes). It is global. Also every board has its own hash which is derived from all the positions/colors that have been played xored into it. So I think it is similar to yours in these aspects. What I don't understand is: How do you know from just a single xor hash if you have played a certain position/color before? Don't you somehow have to store for each possible hash (which is 2 bytes in my example) if it has been used before? The amount of possible hashes even for 2 bytes is quite large. -ibd -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing
Like any hash function, multiple board positions can hash to the same value. The idea is that the probability of encountering two board positions in the same game that have the same hash value is so low, that if you get a duplicate hash value you are practically guaranteed that it's a superko. Colin Yes, that is clear, but Lukasz didn't mention how he stores the past hash values. Sorry if my statement was not clear. Isaac -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
I made some artificial tests where I do x inserts, 1 delete, 10 counts and 1 merge. For x=4 inserts, linear arrays are about 4 times faster. For x=8 inserts, linear arrays are about 3 times faster. From your data I calculated an average liberty count of 2.8 (which seems low to me). This means that for the used board sizes, the constant time merge does not pay off vs. the constant time count. So I can confirm that the linear arrays do seem to be faster, however I haven't tested how they compare to pseudo libs. For heavier playouts, I reckon that true liberties might be a bit faster and more useful. Isaac Original-Nachricht Datum: Fri, 3 Apr 2009 10:22:37 MDT Von: w...@swcp.com An: computer-go computer-go@computer-go.org Betreff: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties? Isaac, Most groups have only say 4 to 8 liberties. This is why simple arrays of liberty locations work so well. The new Intel CPUs have instructions that can search strings 16 bytes at a time, so it could run even faster. Bit vectors also work, but if you want a true liberty count, then you have to avoid counting (1 or 1) as 2, which is the pseudo liberty problem, and which takes more code to write and more time to compute. When I started, I wanted to find a better implementation than gnugo, and I was unable to do so. Of course one can refine or simplify the gnugo code in many different ways, but gnugo has all of the good ideas. Michael Wing PS: Here is the data for how many times the program tried to insert a stone into a chain that has x liberties or x adjacencies. It was taken from a run that combined monte carlo simulations and ladder reading exercises. Note that there are only 2% as many liberties/adjacencies of size 8 as there are of size 0. Chains with liberties/adjacency lists of size 16 are so few as to be irrelevant. data here. On Thu, Apr 2, 2009 at 5:14 AM, w...@swcp.com wrote: Isaac, I implemented about 6 way to track liberties, a couple years ago, and measured the running performance, and by far the best is also the simplest: keep an array of liberties for each chain, and do a simple linear search. This may seem slow, but it has a couple real advantages. First, it works with the cache to maximize locality. Second it is very simple. This *does* seem slow, even when caching the number of liberties. You mentioned that you did this a couple years ago, do you think it still holds true? Thank you for the information. This is what I do too. I never bothered with bit-arrays but possibly that's simply because I fail to see how you can merge two chains and count liberties in O(1). Merging would be a simple OR operation. Counting can be done, for example, with some kind of binary search. Counting the bits set has been well researched and many different algorithms exist. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
I actually found a bug in my test, and corrected it. The gap is far less large now. I found that for 10 inserts (and 1 delete, so 9 total libs), The arrays are faster by a small amount. For 11 inserts (10 libs), bit arrays are faster. This leads us to the question if groups in average have =10 or 10 liberties... :) Space is also very significant when choosing a representation. Michael Wing Can you explain? Isaac -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
On Thu, Apr 2, 2009 at 5:14 AM, w...@swcp.com wrote: Isaac, I implemented about 6 way to track liberties, a couple years ago, and measured the running performance, and by far the best is also the simplest: keep an array of liberties for each chain, and do a simple linear search. This may seem slow, but it has a couple real advantages. First, it works with the cache to maximize locality. Second it is very simple. This *does* seem slow, even when caching the number of liberties. You mentioned that you did this a couple years ago, do you think it still holds true? Thank you for the information. This is what I do too. I never bothered with bit-arrays but possibly that's simply because I fail to see how you can merge two chains and count liberties in O(1). Merging would be a simple OR operation. Counting can be done, for example, with some kind of binary search. Counting the bits set has been well researched and many different algorithms exist. -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
Many Faces also counts real liberties, and is quite fast enough. I can confirm, with a bit of optimization, counting real liberties is only marginally slower than counting pseudo-liberties. So there's really no benefit that I can see from using pseudo liberties. Mark When John Tromp and I were thinking about these things in 2007 we decided to switch to counting real liberties instead of pseudo-liberties. Someone (Rémi?) told us that in the end the performance difference wasn't very large, and we verified this. Álvaro. Thanks. What is a fast way to track liberties? I thought about bit arrays. Merging to groups would take O(1), counting takes O(1)-ish, and memory required would be small. Of course I could also use STL's set structure, but I found it to be quite slow - it implements a set using a RB-tree. This was actually the reason I switched to pseudo libs. -ibd. -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The Zen Program
Probably the most original part of Zen is in the playout. I don't think MC simulations must be always fast, so it has a lot of hard-coded Go knowledge. Yamato Hello Are your playouts simple enough so you could publish the exact algorithm in (pseudo) source code? I'm sure many will be interested if you are willing to share it. Regards, Isaac -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
No hurry, I will be away for a week next week. :-) Isaac, I haven't looked at this stuff for a while. I'm not at home so I can't look at it now. From the error I understand that tesuji/games/general/MoveIterator is missing. It is there in the Subversion source-tree however. So I don't know what could be wrong. Maybe it's somehow missing in the GoEngineGTP.jar If you can wait until Wednesday I'll fix it for you then. Mark -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Hi, Can you explain what minimumNrNodes and nrSimulations do? In my program I play 50k games regardless of the number of nodes, so I would like to adjust this accordingly. Otherwise, it works now. :) -ibd Original-Nachricht Datum: Sun, 8 Feb 2009 14:47:55 -0200 Von: Mark Boon tesujisoftw...@gmail.com An: computer-go computer-go@computer-go.org Betreff: Re: [computer-go] How to properly implement RAVE? I had a little spare time to look at it. It seems indeed I forgot to update the GoEngineGTP.jar file last time I made some changes. This was easy to fix even from here and I think it should work now. Just as a note, if you want to change the number of playouts to 50K, you need to change the minimumNrNodes from 4,000 to 50,000 in the ReferenceMonteCarloTreeSearch definition in the TesujiRefBot.xml. But you may also want to increase the 'nrSimulationsBeforeExpansion' value to something higher like 8 or even 32. It depends on how much memory you have available. You may want to set it to the same value you use for your own program to get a good comparison anyway. Use the MCTSRefBot to play, which means you'll be passing the following command to two-gtp: java -xmx512M -jar GoEngineGTP.jar MCTSRefBot Adjust the -xmx???M to whatever you think is suitable on your computer. I think if you set nrSimulationsBeforeExpansion=8 then 512M should be enough but you may have to experiment a little to find the optimal settings. Mark On Feb 8, 2009, at 7:06 AM, Isaac Deutsch wrote: No hurry, I will be away for a week next week. :-) Isaac, I haven't looked at this stuff for a while. I'm not at home so I can't look at it now. From the error I understand that tesuji/games/general/ MoveIterator is missing. It is there in the Subversion source-tree however. So I don't know what could be wrong. Maybe it's somehow missing in the GoEngineGTP.jar If you can wait until Wednesday I'll fix it for you then. Mark -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
I'm currently tied up but you can get my MCTS implementation, which includes RAVE, and set it up to play 50K playouts. It's only a matter of setting the right number in the configuration file. You can also use it to play through two-gtp, that way you can test an awful lot faster. Mark Hi Mark, This would be awesome. Can you send the source code to this eMail address? Thanks, ibd -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
I put all files in a folder like so: http://img21.imageshack.us/img21/5272/bild4ya1.png But I get various errors when I try to run, for example, GoEngineGTP.jar with java -jar ..., also I'm not able to select the RefBot as player. I'm not sure what the others do, but one seems to connect to the 19x19 CGOS server. I don't have any experience with java. Any ideas? Isaac The beginning of the error: org.springframework.beans.factory.BeanCreationException: Error creating bean with name 'TesujiRefBot' defined in file [/Users/ibd/Desktop/computer go/Rango/CGOS/TesujiRefBot.xml]: Cannot resolve reference to bean 'referenceLibertyAdministration' while setting bean property 'monteCarloAdministration'; nested exception is org.springframework.beans.factory.BeanCreationException: Error creating bean with name 'referenceLibertyAdministration' defined in file [/Users/ibd/Desktop/computer go/Rango/CGOS/TesujiRefBot.xml]: Instantiation of bean failed; nested exception is java.lang.NoClassDefFoundError: tesuji/games/general/MoveIterator Original-Nachricht Datum: Sat, 7 Feb 2009 09:30:53 -0200 Von: Mark Boon tesujisoftw...@gmail.com An: computer-go computer-go@computer-go.org Betreff: Re: [computer-go] How to properly implement RAVE? You can get everything here: http://plug-and-go.dev.java.net The MCTS program description is under 'Derived Projects'. You don't really need the source-code. You can just get the 'binaries scripts' and then copy the files 'TesujiRefBot.jar' and 'TesujiRefBot.xml' to the directory where you put the binaries and everything works automagically. It's all plug and go. You may want to change the number of nodes to read in the XML file to 50K (it's called minimumNrNodes). Of course if you prefer to get the source you are free to do so. I do remember making a significant fix a little while ago that I don't think I submitted yet. But I won't be able to commit that for a few more days as I'm not at home. But if you implemented RAVE correctly your bot should do at least as well as this one. Hopefully it's any help. Mark On Sat, Feb 7, 2009 at 7:18 AM, Isaac Deutsch i...@gmx.ch wrote: I'm currently tied up but you can get my MCTS implementation, which includes RAVE, and set it up to play 50K playouts. It's only a matter of setting the right number in the configuration file. You can also use it to play through two-gtp, that way you can test an awful lot faster. Mark Hi Mark, This would be awesome. Can you send the source code to this eMail address? Thanks, ibd -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ 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/ -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
The rating of the bot still seems to be drifting upwards, but I think I can conclude my UCT implementation is OK afterall. Many thanks to the bots provided. Does someone have a bot that does 50k light playouts + RAVE? I would be most grateful if you could put them online for a few days of testing. :-) By the way, I've seen 2 games when checking my bot's status where one of the myCtest bots lost because of an illegal ko move. Maybe there's a bug in handling superko? Regards, Isaac -- Jetzt 1 Monat kostenlos! GMX FreeDSL - Telefonanschluss + DSL für nur 17,95 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Thanks Christoph. I've changed my bot to play 50k games. I know the results aren't very statistically meaningful yet, but the 2 bots look close to each other already. ;-) I will let it run for some more days if I can. http://img145.imageshack.us/img145/3586/bild3bk3.png -ibd I have started the following versions of 'myCtest': myCtest-50k-UCT (Bayes-ELO= 1618+-14) myCtest-10k-AMAF (Bayes-ELO= 1481+-14) myCtest-10k-UCT (Bayes-ELO= 1334+-12) Christoph -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
I actually tried leaf parallelization first, but after reading the mentioned paper I switched to an implementation of root parallelization (as described). I'm not sure if I implemented it correctly (like in my description), but after testing a 2-core-version against a single- core-version with a few games, I can say the dual core version wins at least 75% of the games, which I think would be an ELO difference of about 200. I have yet to switch colors but the results should be similar. -ibd There were a couple of papers [2] at CG2008 on this subject. The consensus seemed to be that root parallelization [1] was best. In fact Guillaume Chaslot's version got a strength speedup of 3.0 using 2 threads, and 6.5 using 4 threads (dropping to 14.9 with 16 threads). This is of course impossible, and implies the parallel version is somehow doing MCTS better than the single thread algorithm! Darren [1]: Build multiple MCTS trees in parallel, one per thread. No communication. At end add the trees together and use grand total to select move. [2]: http://www.cs.unimaas.nl/g.chaslot/papers/parallelMCTS.pdf and A Parallel Monte-Carlo Tree Search Algorithm by Tristan Cazenave (I couldn't seem to find a PDF link.) -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Hi Jason, Thanks for your numbers. I might try to limit my bot to 50k playouts and 1 core, but I usually simulate as long as time permits. Do you suspect my pure UCT version has bugs, too, judging from its rating? I find it hard to find good tests for the correctness of a program depending on randomness, and even harder to find bugs. Maybe we can set up our bots to play under similar circumstances on CGOS. Regards, Isaac My bot is about 1/4-1/2 of the speed of yours, but here are my strength numbers (median of reported bayeselo numbers below): HouseBot Rango_004 RAVE - 1778 ELO 1721 ELO UCT- 1587 ELO 1642 ELO Given the tremendous speed difference between our bots, I suspect you may have some debugging to do :( I'll try to put my bot up on CGOS again in the next few days. Maybe some head to head games will best answer how our implementations compare to each other. -- Jetzt 1 Monat kostenlos! GMX FreeDSL - Telefonanschluss + DSL für nur 17,95 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Wow, thanks for all the answers! You're being really helpful. Do you use UCT with a too large exploration term? That's a good idea. I actually use a rather big value for c=0.5. I might try lowering it. Thanks! (Precisely, the formula is c*sqrt(log(p)/c).) My first (braindead) multi-threaded UCT played weaker with two cores than one core. How do you combine search trees/results? How do you pick a move to play? I have the threads write to a global array (of course one after another that stores the values and the numbers of games played (each thread adds to these values) of the first ply. I then pick the move with the most games played through that node. The value of this best move (sum/numplayed) determines if the bot should resign. Yes, and you should go by the bayeselo page which is a better picture of what is going on. The ELOs posted here refer to these values. I don't think many people realize that you have to play hundreds of games just to be within 40 or 50 ELO with much certainty. If you play less than 100 games you could easily be off by over 100 ELO. Maybe I'm a bit (a lot :) impatient, but I try to make a rough guess after about 150-200 games, which is about 1-2 days of letting the program run on the server. I think it's possible to say after 150 games that RAVE did not give me a 300 ELO boost. Thanks again, Greetings, Isaac -- Jetzt 1 Monat kostenlos! GMX FreeDSL - Telefonanschluss + DSL für nur 17,95 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
I have about 200-300k games/move, so maybe the effect is even less. But, maybe I still have a grave bug somewhere. I will check again. Cheers, ibd On Feb 2, 2009, at 9:57 AM, Isaac Deutsch wrote: They are not pattern based playouts, but as I said uniformly random. I reckon the effect of RAVE is less with these? My MCTS implementation sees a gain of 200-400 ELO from RAVE using uniformly random moves. 400 gain (90% win-rate) for 2K playouts, becoming slowly less for larger numbers of playouts. Mark -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Hi Issac, You should be more in the range of +200-300 ELO, at least with pattern based playouts. Sylvain Isaac. They are not pattern based playouts, but as I said uniformly random. I reckon the effect of RAVE is less with these? How many playouts per second do you get with each version? Actually, to make comparable tests with both versions, the version without RAVE just sets the coefficient of RAVE in the UCT-RAVE value calculation to zero. I get about 41k games/s on 9x9 (using 2 cores, about 20k/s/core). The playouts are fairly optimized but the tree search isn't at all yet, so there is still some potential. -- Jetzt 1 Monat kostenlos! GMX FreeDSL - Telefonanschluss + DSL für nur 17,95 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] JFFoS + Criticality Heuristic + Parameter Optimization
Hi, The criticality stuff looks really interesting. Do you apply it with the offline knowledge, or as a RAVE prior value, or otherwise? It looks like you precalculate (before the MTCS) the ownership + criticality map, maybe it can be extracted from playouts in the MTCS as well? ibd Original-Nachricht Datum: Sun, 01 Feb 2009 11:01:12 +0100 Von: Rémi Coulom remi.cou...@univ-lille3.fr An: computer-go computer-go@computer-go.org Betreff: [computer-go] JFFoS + Criticality Heuristic + Parameter Optimization Hi, I have just come back from a trip to Japan. I was invited to give presentation at the JFFoS Symposium and the UEC. You can now find slides of my presentations on my web page: The Monte-Carlo Revolution in Go http://remi.coulom.free.fr/JFFoS/JFFoS.pdf (Nothing new here. A simple presentation for a general audience) Criticality: a Monte-Carlo Heuristic for Go Programs http://remi.coulom.free.fr/Criticality/ Local Quadratic Logistic Regression for Stochastic Optimization of Parameters http://remi.coulom.free.fr/QLR/ (This is work in progress. I will very soon update that page with a more detailed paper that I will submit to ACG 12) I thank all the persons at JFFoS and UEC who invited me. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
By the way, I got about 75 ELO points (1650-1720) with light playouts out of RAVE. Do you think this is in the expected range? It's not really similar to the 20%-60% win rate rise vs. GnuGo described in some papers... At the moment I'm also tuning the bias in the range 0.001-0.1. Given uniformly random (light) playouts, is the bias expected to be bigger than with heavy playouts, meaning the constant has to be bigger aswell? Cheers, ibd -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
At the moment I'm also tuning this constant in the range 0.001-0.1. Given uniformly random (light) playouts, is the bias expected to be bigger than with heavy playouts, meaning the constant has to be bigger aswell? -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Hi again ;)
I found some time to actually implement this stuff. And, this has raised
some small questions. In this part of the code:
for (j = index; j moves_played_in_tree.size(); j += 2) {
//stuff
}
for (j = 0; j moves_played_out_tree.size(); ++j) {
//more stuff
// If it is either not the right color or the intersection is
// already played we ignore that move for that node
if (move 0 || already_played.AlreadyPlayed(move)) continue
already_played.Play(move)
//stuff
}
1. Shouldn't the first loop start at j=index+1? Starting at j=index would
mean that the RAVE value of the node is updated with the move of the node
itself, wouldn't it? It makes more sense to me to actually start at the
first child of the node that is being back-upped. Correct me if I'm wrong.
2. Shouldn't the order in the second loop be:
-if (already played): continue;
-update already played;
-if (wrong color): continue;
Otherwise, moves that are the wrong color don't get counted as already
played (because they never get updated). I'm not sure if it makes a
difference in this case because you check in the playouts, too, but maybe
it does.
And a final question: You calculate the (beta) coefficient as
c = rc / (rc+c+rc*c*BIAS);
which looks similar to the formula proposed by David Silver (If I recall
his name correctly). However, in his formula, the last term looks like
rc*c*BIAS/(q_ur*(1-q_ur))
Is it correct that we could get q_ur from the current UCT-RAVE mean value,
and that it is used like that?
Regards,
Isaac Deutsch
--
Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen:
http://www.gmx.net/de/go/multimessenger
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] bad/good moves? How to prune? Heavy playouts.
Hello, There is lots of information about heavy (heavier) playouts on this mailing list. It looks like the main purpose of them is to make the evaluation better by killing dead groups with a high probability, connecting groups that are connected with high probability, etc. However, it looks like some randomness is desired, and mainly, noise should be reduced by pruning bad moves. Which moves do you prune in the playouts? I saw some ideas including: -self atari -first line plays with no stones near -second/third line / near-center plays with no stones near -bad patterns (this seems vague to me) -ladders/escape sequences that don't work On the other hand, there are moves that should be played more often: -escape atari -kill groups -good patterns (vague again) -play in unsettled regions (for example determined by previous playouts) Are there others you would add? Also, it seems like a lot of experimentation is involved - people just try to find a good speed/strength balance. Also, how do you find bad/good patterns? Learn from pro games? Go knowledge? Secondly, how do you prune/favour these moves? I thought about 2 ideas: 1. Prune moves for the first x games. The higher x, the more certain we are that this move is worse than a random move. This way we might get better information initially but explore all moves eventually. 2. Prune moves with the probability p (0=p=1). This would lead to better playouts over all too, but the monte carlo tree is better balanced. Same goes for good moves, but instead of pruned, they are played deterministically. Additionally, I thought about checking the good moves in a different order every playout to add more randomness. This would be by creating permutations of the list of features (kill group, escape, etc.), then checking in that order. I would like to hear your opinions/ideas. ;) Cheers, ibd -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] RAVE and memory allocation considerations
Thanks again for your pseudo-implementation, Sylvain. At the moment I have a program that uses plain MCTS. With every genmove, it creates a certain number of threads (2), gives them some starting data, and lets them think for a while, then rejoins them, extracting the best move. During the thinking, the threads build a normal UCT tree. At the beginning, they allocate a certain number of nodes (100'000 as of now) and delete the nodes when thinking has finished. To add RAVE to this, each node would need up to size*size additional values for RAVE. I thought about allocating this memory when children are added (which seems logical to me), and deleting it also at the end of the thinking time. However, this seems (I don't have any data) *slow* to me , to allocate up to ˜50 MB of RAM every time, then destroying it again afterwards. Do you think the spent allocating could be critical? What do you think would be a good way to deal with this? I think to avoid the continuous allocation/deallocation, it's necessary to keep the threads running instead of creating/joining them for each genmove. This would allow them to only have to alloc/dealloc when the board size is changed. Regards, Isaac -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] RAVE and memory allocation considerations
I made some tests: -Creationjoining of threads is almost free; on my system it takes about 0.003s to createjoin 8 threads. -when allocating, writing to and deallocating 100'000 nodes without RAVE values (about 25 byte each), it takes about 0.025s (almost free considering this is about 1/40-1/400 of the total thinking time). -when doing the same with nodes with rave values (I considered 1600 byte average each), it takes about 0.3s. So indeed, it might be useful to keep a pool of the big nodes, but I wouldn't bother with smaller arrays. How do you think this pool should be made? I don't want the threads to step on each other's toes. :) Regards, Isaac Original-Nachricht Datum: Tue, 20 Jan 2009 19:17:06 +0100 Von: Sylvain Gelly sylvain.ge...@m4x.org An: computer-go computer-go@computer-go.org Betreff: Re: [computer-go] RAVE and memory allocation considerations Hi, You should really look into never deallocate memory (by calling delete/free) but keeping it in some memory pool. I did that for the main objects that you deal with: nodes and small vectors (the one you create on the fly to keep the moves that have been played in the playout). It really speeds up things a lot. Apart from that, I did the same as you, creating the thread after the genmove and joining them at the end of the thinking time. Sylvain 2009/1/20 Isaac Deutsch i...@gmx.ch Thanks again for your pseudo-implementation, Sylvain. At the moment I have a program that uses plain MCTS. With every genmove, it creates a certain number of threads (2), gives them some starting data, and lets them think for a while, then rejoins them, extracting the best move. During the thinking, the threads build a normal UCT tree. At the beginning, they allocate a certain number of nodes (100'000 as of now) and delete the nodes when thinking has finished. To add RAVE to this, each node would need up to size*size additional values for RAVE. I thought about allocating this memory when children are added (which seems logical to me), and deleting it also at the end of the thinking time. However, this seems (I don't have any data) *slow* to me , to allocate up to ˜50 MB of RAM every time, then destroying it again afterwards. Do you think the spent allocating could be critical? What do you think would be a good way to deal with this? I think to avoid the continuous allocation/deallocation, it's necessary to keep the threads running instead of creating/joining them for each genmove. This would allow them to only have to alloc/dealloc when the board size is changed. Regards, Isaac -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Sensationsangebot verlängert: GMX FreeDSL - Telefonanschluss + DSL für nur 16,37 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K1308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Hi, Sorry for the slow reply. Hi I'd prefer quality over speed anytime. ;) Your pseudo code is excellent and helped me to understand some of the trickier things. Thanks again! I think I will now be able to implement my own version. :) Regards, Isaac -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Hi, I'm also interested at the same thing. Glad I'm not alone. ;) It sounds good but it seems to lack the check of whether a given move is first played in a given intersection. When you add that, it because a little more tricky to update in the tree. I see, I missed that. I actually prune second (third, fourth...) moves at the same intersection in the playouts. However, this means that I can't just count every 2nd move as a move for the given node color, so I'd have to change the update loop. You also update the value of each move independently of the color, i.e. a position in which it is black turn will be update with white moves. You should restrict the update. This I don't really understand. Are you talking about the issue raised by basically doing j+=2 in the loop instead of checking whether the move color is the same as the node color? If yes, I understand. I have a question about the the part were the stats are updated. (l.15-25). having an array of amaf-values in every node seems very memory intensive and I don't get how you would access these values. Something like searching for all nodes below the visited node with the same pos+color as the ones visited and updating amaf-stats directly in these nodes would make more sense to me. (but also costs more cpu time) I have been thinking *exactly* the same thing. When you keep the values in the node, it's easiest to keep boardsize*boardsize values to be able to access AMAF values directly by the childrens' positions. This wastes a bit of memory, but not too much. Keeping the value in the children is more cpu expensive but saves memory. For me, the first way seems easier to implement. How would you exactly do searching for all nodes below the visited node with the same pos+color as the ones visited? I think by the visited node you mean the first move played after root, is that correct? On a side note, I found that using plain AMAF for MCTS (so a single AMAF table for all nodes in the tree) actually made my program play about 100 elo *worse*! Clearly, it's necessary to implement proper RAVE to get a benefit. Thanks again, Isaac -- Sensationsangebot verlängert: GMX FreeDSL - Telefonanschluss + DSL für nur 16,37 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K1308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Hi Sylvain, I think it's starting to make sense now. :-) Sorry to be unclear. I wish we have a white board where we could discuss and that would sorted out in a few minutes :). Several results turn up in a google search ;p http://www.google.com/search?q=online+white+board What I tried to mean is that when you do the backup for a given node, you look at the part of the playout that happen after that node (including that node), and you do a normal AMAF backup for that part of the playout. Does it make sense? I hope we make progress and I am not making things more confusing :). I should write a pseudo code I guess, but for today I am too lazy :). Sylvain I tried putting this into pseudo code, but it already looks like C. ;p http://pastie.org/357231 If you could look at it, I would be most grateful. -Isaac -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] How to properly implement RAVE?
I'm a bit confused about the difference between AMAF and RAVE (if there's one). As far as I understand, with AMAF, you sample in each playout (after it leaves the tree) the moves played (by both players), but only the first move at any position, then you reward all moves played either by a win or loss, depending on their colors. I tried comparing this to RAVE, as described in many papers. There might be multiple definitions of RAVE, but the one that seems the most clear to me is this one (picture used because of math stuff): http://img352.imageshack.us/img352/443/bild1pb3.png Is it correct that with RAVE, after a playout (after the tree), only the siblings of the last node in the tree are updated accordingly? The main difference to AMAF would be that instead of a single array with values of AMAFsumReward and AMAFnumPlayed, each node keeps for each of its children separate variables that hold these values. When a playout is finished, only the values of these children are updated instead of the single array. I hope you're able to make any sense out of this, sometimes a text can be confusing when the writer is confused. ;p Cheers, ibd -- Sensationsangebot verlängert: GMX FreeDSL - Telefonanschluss + DSL für nur 16,37 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K1308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Hi Sylvain, Thanks for your quick answer. in a nutshell RAVE is basically AMAF adapted for Monte Carlo Tree Search. The original paper describing it is http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf and a paper for broader audience can be found here: http://www.lri.fr/~gelly/paper/MoGoNectar.pdf (the picture you posted comes from that paper). Yes, I took a screenshot. Another paper I looked at was http://www.lri.fr/~teytaud/eg.pdf There are two important parts in the algorithms: the backup and the use of the RAVE value. The second is the hardest to tune and to make it right. The proposed way of using the values in the original paper is not optimal (while already very useful). A much better way (especially in 19x19) has been described on that list by David Silver. Do you mean the calculation of the factor beta that the RAVE value is multiplied with? For the backup (as it is your original question), for each node traversed by the simulation, back up the values exactly as it would be done in AMAF *if* the playout began at that node. Note that I call playout the whole simulation starting from the root and going to the end of the game. I see what you mean with the playout going from the root to the end of the game. How do you mean back up the values ... if the playout began at that node? Since every playout starts at the root (in my program, the root is the (previous) move of the opponent player), wouldn't that mean only updating the RAVE statistics for the root? I'm sorry if this question sounds stupid. - Count only moves that happen after the node. How do you measure if a move is after another move? The amount of moves taken from the root (i.e. the depth of the node in the tree/the playout)? Or do you mean that the node is effectively a (grand-grand-...) father of the move, so the playout has visited that node? I hope it will help you write a correct implementation. Don't hesitate to ask for precisions. I really appreciate your help. -ibd -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Black/White winning rates with random playout?
I ran some tests with 500k games each and came to this result: with komi 0.5, white has 47.5 winn. perc. with komi 1.5, white has 50.7 winn. perc. with komi 2.5, white has 50.9 winn. perc. with komi 3.5, white has 54.0 winn. perc. with komi 4.5, white has 53.8 winn. perc. -- ? with komi 5.5, white has 57.3 winn. perc. with komi 6.5, white has 57.1 winn. perc. - ? with komi 7.5, white has 60.3 winn. perc. with komi 8.5, white has 60.3 winn. perc. with komi 9.5, white has 63.1 winn. perc. with komi 10.5, white has 63.1 winn. perc. with komi 11.5, white has 65.9 winn. perc. The percentage is mostly according to komi, with 2 exceptions. -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
