Re: [computer-go] Re: Dynamic Komi's basics
Quoting Ingo Althöfer 3-hirn-ver...@gmx.de: Darren Cook wrote: I'm surprised people are using a simple linear decreasing rule, but very interested to hear there is a tangible improvement. I was surprised, too. Perhaps being adaptive isn't needed? The simplest solution is the best solution (old proverb). I have implemented *adaptive* dynamic komi in Valkyria now and are testing it on KGS. It adjusts the komi after each move, and uses the same komi for each generated move. Wild stuff do happen when groups dies and both colors makes blunders under time pressure. With adaptive dynamic komi the search becomes very unpredictable. So for many moves it will search with a too high or a too low komi. In the opening it is not much of a trouble. So I can perfectly see why a linearly decreasing komi will give a boost for sure to the playing strength without risking loosing games because of the chaotic nature of adaptive dynamic komi. Valkyria now uses dynamic komi in all games and also for lost position up to being behind 20 points. It sets the dynamic part to zero when there are two dames left, which leads to the tricky behavior that it tries wild things just before resigning, after trying to catch up by playing a proper endgame. Tonight it move from 6 kyu to 5 kyu, but the 6 kyu rating was not certain so it is hard to tell whether the change affects the strength. I think it is now more fun to play against it and would appreciate any comments about the new playing style from strong as well from weak players. Best Magnus -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to Fuego!
If the winning chance are lower than a lower threshold it should resign not pass. The only alternative to resigning in a lost position is to play on unless there are no legal moves. Best Magnus Quoting Lars Schäfers to.larsi...@web.de: Hi Nick, just two little comments to the report: - In your comment to round 12 you stated that gomorra doesn't support cleanup. It does. But if the winning chance is lower than a certain threshold it also passes in the cleanup phase when there are still dead stones. - Since the last tournament there is a little typo in the Processor numbers, power, etc section, where gomorra got an additional m :) Thank you all for the tournament and thank you Nick for the report too!! Lars ___ Preisknaller: WEB.DE DSL Flatrate für nur 16,99 Euro/mtl.! http://produkte.web.de/go/02/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to Fuego!
I struggled a lot with pass, because it somehow have to be legal when it is necessary to pass. But in order to handle seki (that is play strong in general when a seki is present or a possible outcome) I found that the only way to do it is to let the playouts handle it correctly. Since Valkyria has extremely heavy playouts it is not costly. Basically one only has to check suicidal moves if they could be part of a seki and then forbid such moves. But there are a lot of special cases and one has to be careful to only forbid such moves that really could be part of a seki. There is no single algorithm but just a lot of special cases for different situations. -Magnus Quoting Lars Schäfers to.larsi...@web.de: So far, gomorra doesn't support the pass move in the search. So it is its only possibility to get through a seki position at the end of the game. Therefore gomorra passes 3 times before it resigns. Of course, its not optimal :) I wonder if there are others who haven't implemented the pass move but found a nice way of handling seki situations during the search? - Lars -Ursprüngliche Nachricht- Von: Magnus Persson magnus.pers...@phmp.se Gesendet: 12.01.10 11:49:28 An: computer-go@computer-go.org Betreff: Re: [computer-go] Congratulations to Fuego! If the winning chance are lower than a lower threshold it should resign not pass. The only alternative to resigning in a lost position is to play on unless there are no legal moves. Best Magnus Quoting Lars Schäfers to.larsi...@web.de: Hi Nick, just two little comments to the report: - In your comment to round 12 you stated that gomorra doesn't support cleanup. It does. But if the winning chance is lower than a certain threshold it also passes in the cleanup phase when there are still dead stones. - Since the last tournament there is a little typo in the Processor numbers, power, etc section, where gomorra got an additional m :) Thank you all for the tournament and thank you Nick for the report too!! Lars ___ Preisknaller: WEB.DE DSL Flatrate für nur 16,99 Euro/mtl.! http://produkte.web.de/go/02/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ Preisknaller: WEB.DE DSL Flatrate für nur 16,99 Euro/mtl.! http://produkte.web.de/go/02/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Joseki Book
Quoting terry mcintyre terrymcint...@yahoo.com: I don't knwo how to build such a book, but Kogo's Joseki dictionnary is a huge .sgf file containging joseki + trick moves and punishment. Maybe it can be parsed to extract only joskis. The problem with josekis are that most of the moves in them are not commented at all, and there are many seemingly reasonable alternatives moves that has to be punished. And just storing one counter move is not enough. And of course the whole board position is most important when a joseki breaks down because of a mistake. What I am trying to say that in order to help a weak program playing well whatever the opponent plays the joseki dictionary has to be enormous. The whole idea behind a joseki is that super strong players have been thinking about what may be playable or not and the the sequence we find in book is just the tip of the iceberg. I think it may make more sense to break down the joseki into common local patterns and let for example MCTS search among those local patterns, sometime reproducing josekis sometimes not. I think someone here wrote long ago that larger patterns do not improve at all on small pattern of some size. A joseki dictionary can be seen as using very large patterns. -Magnus -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Rating variability on CGOS
When I get more time to work on Valkyria again maybe I should look closely at the games against Pachi... -Magnus Quoting Brian Sheppard sheppar...@aol.com: About two weeks ago I took Pebbles offline for an extensive overhaul of its board representation. At that time Valkyria 3.3.4 had a 9x9 CGOS rating of roughly 2475. When I looked today, I saw Valkyria 3.3.4 rated at roughly 2334, so I wondered what was going on. I found a contributing factor: Valkyria has massively different results against Pachi than against Pebbles. It happens that Pachi started playing a day or two after Pebbles went offline. Pebbles and Pachi are both rated around 2200, but Valkyria shreds Pebbles a lot more often than Pachi: Pachi: 185 / 273 = 67.8% Pebbles: 429 / 503 = 85.3% There are a lot of lessons here... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Progressive widening vs unpruning
I was not at all surprised by this result. My thinking goes like this. On 9x9 the global situation is everything that matters and precomputed information is not as important as searching effectly is. Good 9x9 games are often very sharp fights where then next move often violates good shapes known from 19x19 games. On 19x19 deep global search is impossible and good local shape is more often more important (or perhaps more often local shape is good enough to indicate the correct move) than the global situation so heuristic precomputed knowledge is essential to make search efficient. In Valkyria I also learned that things I do to improve 19x19 has no effect on 9x9 or sometimes makes it weaker. -Magnus Quoting David Fotland fotl...@smart-games.com: So far on 9x9 go, Many Faces doesn't seem to make a huge difference. On 19x19 it makes a huge difference. I ran test games overnight against Gnugo. With Many Faces turned on, my engine wins 85%. With many Faces turned off, my engine wins 7%. Both results are unexpected. Since most of my tuning is on 19x19, the combination of Many Faces and UCT is probably badly mistuned for 9x9. David ___ 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
? :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Christian Nentwich Director, Model Two Zero Ltd. +44-(0)7747-061302 http://www.modeltwozero.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ 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
Quoting Petr Baudis pa...@ucw.cz: On Thu, Sep 10, 2009 at 01:54:49PM +0200, Magnus Persson wrote: This is very interesting. Here is a crazy idea, maybe it the same as Marks but I want to take it to its extreme. Since AMAF values are so helpful, perhaps one can let go of the idea of sequential play following the rules of go, and basically play moves in parallel on all empty intersection. Compute new state (do captures) and repeat a fixed number of times and evaluate. Since I do not understand GPU programming at all I cannot judge whether this would make things easier to implement. Also a lot of weird thing will happens when you do things in parallel. What happens when two adjacent blocks are captured at the same time. Are both removed? Are there tricks to remove the one that was most likely to captured to begin with. Well, after one iteration, _all_ blocks should be captured since there will be no empty intersections, right? (Even if you don't play in eye-like spaces, you will have this situation until some of these actually form.) The easiest heuristic would seem to be to capture the smallest group, but I have hard time imagining this working well, _and_ how to choose the smallest group efficiently (other than that, modifying my source to do this should be fairly easy). -- Petr Pasky Baudis A lot of people have my books on their bookshelves. That's the problem, they need to read them. -- Don Knuth ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ 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
Sorry for my empty reply to Petr, I misclicked When a block is identified you could also sum up what the original strength of the original stones covered by the block and use that as a heuristic for what should be captured first. Also to avoid filling all liberties. One can avoid that with pattern matching when the original position is copied to the GPU. For example if black has an empty triangle, black will rather pass than play that point. Thus either white plays there or it remains empty. Basically it mean we can impose heavy pruning on the original position. And then copy many copies of that position and evaluate them massively in parallel. -Magnus Quoting Petr Baudis pa...@ucw.cz: On Thu, Sep 10, 2009 at 01:54:49PM +0200, Magnus Persson wrote: This is very interesting. Here is a crazy idea, maybe it the same as Marks but I want to take it to its extreme. Since AMAF values are so helpful, perhaps one can let go of the idea of sequential play following the rules of go, and basically play moves in parallel on all empty intersection. Compute new state (do captures) and repeat a fixed number of times and evaluate. Since I do not understand GPU programming at all I cannot judge whether this would make things easier to implement. Also a lot of weird thing will happens when you do things in parallel. What happens when two adjacent blocks are captured at the same time. Are both removed? Are there tricks to remove the one that was most likely to captured to begin with. Well, after one iteration, _all_ blocks should be captured since there will be no empty intersections, right? (Even if you don't play in eye-like spaces, you will have this situation until some of these actually form.) The easiest heuristic would seem to be to capture the smallest group, but I have hard time imagining this working well, _and_ how to choose the smallest group efficiently (other than that, modifying my source to do this should be fairly easy). -- Petr Pasky Baudis A lot of people have my books on their bookshelves. That's the problem, they need to read them. -- Don Knuth ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ 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
Quoting steve uurtamo uurt...@gmail.com: Since AMAF values are so helpful, perhaps one can let go of the idea of sequential play following the rules of go, and basically play moves in parallel on all empty intersection. Compute new state (do captures) and repeat a fixed number of times and evaluate. two thoughts: i) how do you determine color to play for each thread? Random. Only one random bit necessary for each decision. ii) if i) becomes unsynchronized with the rules of go, you're basically exploring random boards instead of boards that are related to the game that you're interested in. the board should rapidly converge to something that retains no information about the initial state of the board (assuming that the initial board has stones on it). Usual lightweight random games are also random creating situation that never happen in normal play. But violation of rules will probably make it more biased than a usual light playout. Hard to tell before trying. My feeling is that it might work surprisingly well but it might get extremely biased in some situations, which perhaps can be fixed by prefiltering of the move that can be played. Magnus -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo policy: capture stones anywhere?
I never tried pseudoliberties in Valkyria. It actually stores arrays of the liberties in addition to the count. This make programming complex algorithms simple, but perhaps not the most efficient way. -Magnus Quoting Peter Drake dr...@lclark.edu: On Sep 1, 2009, at 8:11 AM, David Fotland wrote: I don?t think any of the strong programs use pseudoliberties. Interesting! Can those involved with other strong programs verify this? My board code is descended from my Java re-implementation of libEGO. I tried writing one using real liberties earlier, and it was considerably slower in random playouts. Perhaps it's worth the speed hit as playouts get heavier. Incidentally, preliminary experiments indicate that the capture-the- largest-chain heuristic (after escaping and matching patterns) does improve strength, despite the speed cost. I'll run a larger experiment tonight... Peter Drake http://www.lclark.edu/~drake/ -- Magnus Persson Berlin, Germany ___ 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
Don, what you write is certainly true for even games, but I think the problem is a real one in high handicap games with the computer as white. I use a hack to make Valkyria continue playing the opening in handicap games as white. It is forbidden to resign in the opening and early middle game because it would if it could. To rephrase your argument for even games, the problem situation should never occur because the losing player *should out of courtesy* resign long before the evalutaion become so skewed. But this does not apply to h9 games on 19x19 for example. And if I am not mistaken strong heavy playouts evaluates such positions very pessimistically, and thus we have a problem to solve, which grows with increasing playing strength. Still stronger programs will discriminate between bad and good moves even with extreme scores, so I think the dimensions of this problem is exaggerated. -Magnus Quoting Don Dailey dailey@gmail.com: One must decide if the goal is to improve the program or to improve it's playing behavior when it's in a dead won or dead lost positions. It's my belief that you can probably cannot improve the playing strength soley with komi manipulation, but at a slight decrease in playing strength you can probably improve the behavior, as measured by a willingness to fight for space that is technically not relevant to the goal of winning the game.And only then if this is done carefully. However I believe there are better ways, such a pre-ordering the moves. Even if this can prove to be a gain, you are really working very hard to find something that only kicks in when the game is already decided - how to play when the game is already won or already lost.But only the case when the game is lost is this very interesting from the standpoint of making the program stronger. And even this case is not THAT interesting, because if you are losing, on average you are losing to stronger players. So you are working hard on an algorithm to beat stronger players when you are in a dead lost game? How much sense does that make? So the only realistic pay-off here is how to salvage lost games against players that are relatively close in strength since you can expect not to be in this situation very often agaist really weak players.So you are hoping to bamboozle players who are not not weaker than you - in situations where you have been bamboozled (since you are losing, you are the one being outplayed.) That is why I believe that at best you are looking at only a very minor improvement.If I were working on this problem I would be focused only on the playing style, not the playing strength. If you want more than the most minor playing strength improvement out of this algorithm, you have to start using it BEFORE the loss is clear, but then you are no longer playing for the win when you lower your goals, you are playing for the loss. - Don 2009/8/19 Stefan Kaitschick stefan.kaitsch...@hamburg.de One last rumination on dynamic komi: The main objection against introducing dynamic komi is that it ignores the true goal of winning by half a point. The power of the win/loss step function as scoring function underscores the validity of this critique. And yet, the current behaviour of mc bots, when either leading or trailing by a large margin, resembles random play. The simple reason for this is that either every move is a win or every move is a loss. So from the perspective of securing a win, every move is as good as any other move. Humans know how to handle these situations. They try to catch up from behind, or try to play safely while defending enough of a winning margin. For a bot, there are some numerical clues when it is missbehaving. When the calculated win rate is either very high or low and many move candidates have almost identical win rates, the bot is in coin toss country. A simple rule would be this: define a minimum value that has to separate the win rate of the 2 best move candidates. Do a normal search without komi. If the minimum difference is not reached, do a new a new search with some komi, but only allow the moves within the minimum value range from the best candidate. Repeat this with progressively higher komi until the two best candidates are sufficiently separated.(Or until the win rate is in a defined middle region) There can be some traps here, a group of moves can all accomplish the same critical goal. But I'm sure this can be handled. The main idea is to look for a less ambitious gloal when the true goal cannot be reached. (Or a more ambitious goal when it is allready satisfied). By only allowing moves that are in a statistical tie in the 0 komi search, it can be assured that short term gain doesn't compromise the long term goal. Stefan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson
RE: [computer-go] Interesting endgame case
Valkyria plays J3 or capture the ko, with capturing the ko as the most common choice. But it always thinks for some thousands of playouts before it sees a clear win. Magnus Quoting David Fotland fotl...@smart-games.com: I checked this position again, and Many Faces finds j3 after a few thousand playouts, but even at a million playouts (28 seconds) it's only 61%. From: computer-go-boun...@computer-go.org [mailto:computer-go-boun...@computer-go.org] On Behalf Of Brian Sheppard Sent: Saturday, August 15, 2009 8:13 AM To: computer-go@computer-go.org Subject: [computer-go] Interesting endgame case assuming komi 7.5 and Chinese rule, playing at J3 white will win. After J3, white has 35. It only needs to win the ko or takes two dames. If black fills the dame, it loses the ko. If it fills the ko, white can take two dames. Yes, Chinese and 7.5. I basically figured that J3 was just another in a long series of stupid moves by Pebbles, but when it insisted that J3 was winning no matter how long it searched then I decided to look into it. J3 looks stupid because it fills territory that O already owns. J3 wins because it is reverse sente (I think this is the right terminology) because H4 is no longer sente for X. It also gains a move in the semeai against X's dead stones on the left, so O gains *two* ko threats. Just curious: how did you find J3? 1 2 3 4 5 6 7 8 9 A - - O - - - - - - B X X X O X - - - - C O O X O X X - - - D O - O X X - X X - E - O O O X X O X X F - X O - X O O O X G - X O - X O O - O H O X O - X X O O - J - - - O X - X O - O to play -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Heavier playouts
I think this is the normal way of improving playouts. You start out with captures and escaping broken ladders, then one continues with 2 liberty cases where you for example can fix fundamental problems like sekis. In Valkyria I have some rules for 3 liberties as well, but then it starts to get really complicated with semeais of many kinds. Magnus Quoting David Fotland fotl...@smart-games.com: Yes, something like that. Before my local playout rules just looked for one liberty groups, like - if group including stone just played has one liberty, capture it, or if group adjacent to last move played has one liberty, save it. Now I added some rules where the number of liberties is two. -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Robert Jasiek Sent: Thursday, August 13, 2009 11:32 PM To: computer-go Subject: Re: [computer-go] Heavier playouts Just a guess of me what a 2-liberty local rule might look like: If a string has at most / exactly 2 liberties, then first consider as next move a play on an intersection adjacent to the string or adjacent to one of its adjacent strings that have at most 2 liberties themselves. If two strings, of which neither is a basic nakade string shape, share the same 2 liberties and do not have any other, then first do not consider a play on either. Is this roughly something you might be using? (You do not need to reveal your secrets. I just would like to understand roughly what you mean by the concept 2-liberty local rule.) -- robert jasiek ___ 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/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Dynamic komi in commercial programs
I also tried dynamic komi with Valkyria a long time ago. It failed. I did not waste much time on it. Anyway here are my opinions and intuitions about it. As usual I am open to been proved being wrong with some empirical evidence along with a nice algorithm that I can steal and add to Valkyria. :-) As already mentioned, one needs to set the dynamic komi to some kind of magic value, which IMO requires so much insight about the position, it means that the program should *know* the best way of playing anyway without the help of the dynamic komi. Personally I am absolutely happy with how Valkyria plays in handicap games. It gives large handicaps against weaker players on KGS and wins. The only problem is to avoid it resigning early because the situation is hopeless. With handicap on small boards it is so strong that the problem just do not seem to exist anymore. Sure it plays ugly moves in handicap games, but this is not different from even games where it often plays a little bit too creative to my taste. The problem with MCTS is that they are weak in evaluation. I am pretty sure that this fixation on dynamic Komi is confounded with the fact that most programs has quite light playouts, and programs with heavy playouts still has big holes in the knowledge that leads to delusional evaluations. I guess the reason that people think dynamic komi is important is that these bad evaluations can always in principle be repaired in *hindsight*. But repairing something in hindsight is useless. If I fiddle with komi until the program plays a move I like it is not the program that selects the move anymore. As the programmer I cannot add a human expert to the code. This is most certainly true for 19x19. The correct solution to bad plays is to make the program *stronger*. I am open to opponent modeling such as make the playouts of black in handicap games weaker. But in this case I think real gain if any would come from making the statistics more sensitive to the qualitative difference in available moves, rather than actually modeling the opponent, by bringing the win rates closer to 50%. Although I think it would be really hard to degrade the black moves in the playouts in a realistic way. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Another odd seki
Valkyria correctly behaves as if this is seki. It actually does not now it is seki explicitely, but it prunes all moves that would break the seki. The principle to do this as simple as possible is thus not actually to identify seki in general but to find simple rules that prunes bad moves. This means one has to have many rules, but each rule becomes simple. Pruning J3 for X is a very neat example which is easy to do with the rich boardrepresentation of Valkyria. First the program at som point identifies J3 as a false eye. Some false eyes must be played and some most not be played. In this case XJ2 and XH3 both have two liberties, then V. looks at the corners of J3 and finds OH2 which also has two liberties. Now the liberties of XJ2 and XH3 that are not the false eye are matched to the liberties of OH2. Also these liberties are at the moment suicidal for both players. This is enough to safely conclude that filling in the false eye cannot be a good move becuase it just connect two liberties that cannot be played anyway. But! There are always exceptions. In this case one exceptions is when the false eye is on the 1-1 point and only two stones are connect and that the resulting shape is a precursor to bent four in the corner. In that case filling in the false eye is essential. I cannot exclude that are no more exceptions to this rule, but so far it works nicely. Oh, by the way I find on the sight of it hareder to prune O J1. I know Valkyria prunes this but I do not remember exactly how it is done, but I guess the code that handle sacrfices has to check for false eyes becoming real eyes because of the sacrfice or something like that. -Magnus Quoting Brian Sheppard sheppar...@aol.com: There is a seki in the lower left of the position below: 1 2 3 4 5 6 7 8 9 A - O X X - X - - - B X O X X X X X - X C - O O X X - X X - D O O O O X X X X X E X X O - O X - X O F - X X O O O X X O G O X X X O X X O - H O O X X O X O - O J - X - X O O O O - It is obvious that X cannot play F1. O cannot play F1 because that would sacrifice a straight four. Pebbles has followed Magnus's advice and added a rule that prevents the two-for-one trade that would occur when X plays J1, so that is also not a problem. And for O, playing J1 is ruled out because X has another eye on J3. What isn't obvious is that X cannot play J3. If X plays J3 then O follows with J1 atari, and X loses because of the nakade shape of O's stones. The bottom line is that Pebbles rates this position as hugely favorable for O, because X stumbles into J3 in the playouts. How does your program handle this situation? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Really basic question
Quoting Oliver Lewis ojfle...@gmail.com: Others on this list have reported in the past that the randomness is actually very important. Playouts that are very heavy, no matter how clever they are, actually reduce the performance because they narrow the number of games too much. I would like to disagree with this statement. I think it is difficult to make a good heavy playouts, but it is not impossible. Failing to make a playout stronger through heaviness does not prove anything. It just mean one has failed. If I could make a heavy playout of 1 Dan strength and then run in MC tree search. I am sure it would be stronger than the playout itself. The problem I think is to find a good tradeoff between heavyness and speed. In my test with Valkyria vs Fuego, Valkyria is superior when the number of playouts are the same. But Fuego can play 5 times more playouts per second on the hardware that results in Fuego being slightly stronger than Valkyria at the moment. It just cannot be that having strong playout leads to worse play in general. It is just a matter of not slowing down the code too much and add just those heavy elements that do increase playing strength. -Magnus -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Experimentation
Quoting Darren Cook dar...@dcook.org: * The scaling behavior might be different. E.g. if Fuego and Valkyria are both run with 10 times more playouts the win rate might change. Just to dismiss an algorithm that loses at time limits that happen to suit rapid testing on today's hardware could mean we miss out on the ideal algorithm for tomorrow's hardware. (*) I just happened to have experimental data on exactly this topic. This is Valkyria vs Fuego where I scale the number of playouts (Sims) x4 in each row. SimsWinrate Err N WR EloDiff 2 99.20.4 500 0.992 837 8 98.20.6 500 0.982 696 32 94.21 500 0.942 484 128 88.81.4 500 0.888 360 512 82 1.7 500 0.82263 204883.21.7 499 0.832 278 819281.31.7 497 0.813 255 32768 75.53.6 139 0.755 196 The data shows clearly that the 0.3.2 version of Fuego I use, probably plays really bad moves with a high frequency in the playouts. With more playouts a lot of these blunders can be avoided I guess and the win rate goes down from 99% towards 80%. The question here if it goes asymptotically towards 80% or perhaps 50% with more simulations. Unfortunately I cannot continue this plot because I run out of memory and it takes ages to finish the games. So the question is then: are there a fixed gain of the heavy playouts with more than 512 simulations or does the effect of the heavy playout get less and less important with larger tree size. Note also that this also not only a matter of having heavy playouts or not. There is also a difference in tree search since Valkyria and Fuego probably search their trees differently, and it could be that Valkyria search deep trees inefficiently. Maybe I should run a similar test against a light version of Valkyria to control for the search algorithm. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Experimentation
I have not used time exactly to match up Valkyria and Fuego. But also with fixed numbers of simulations one can match them up closely in processor time. And then I do that Valkyria wins something like 41-45% of the time. I never intentionally designed Valkyria to work well small number of simulation as in these tests, but in principle you have to do that no matter how many simulations you run per move, because you will always have few simulations in the leaves of the tree. And if the leaves are evaluated strongly then the nodes nearer to the root also will benefit. Magnus Quoting Christian Nentwich christ...@modeltwozero.com: Magnus, along the lines of the argument I am trying to make: did you try your experiments with time limits from 30 seconds per game to five minutes per game (say), rather than playouts? Using gogui-twogtp this is relatively easy to achieve. I am obviously not associated with Fuego, but I guess it is reasonable to assume that Fuego's architecture was not designed to operate at limits like 2, 8 or 32 simulations in the same way Valkyria was. It is an interesting study in its own right for scalability purposes; but to go on to infer strength from it would seem like comparing apples and oranges. Christian Magnus Persson wrote: Quoting Darren Cook dar...@dcook.org: * The scaling behavior might be different. E.g. if Fuego and Valkyria are both run with 10 times more playouts the win rate might change. Just to dismiss an algorithm that loses at time limits that happen to suit rapid testing on today's hardware could mean we miss out on the ideal algorithm for tomorrow's hardware. (*) I just happened to have experimental data on exactly this topic. This is Valkyria vs Fuego where I scale the number of playouts (Sims) x4 in each row. SimsWinrateErrNWREloDiff 299.20.45000.992837 898.20.65000.982696 3294.215000.942484 12888.81.45000.888360 512821.75000.82263 204883.21.74990.832278 819281.31.74970.813255 3276875.53.61390.755196 The data shows clearly that the 0.3.2 version of Fuego I use, probably plays really bad moves with a high frequency in the playouts. With more playouts a lot of these blunders can be avoided I guess and the win rate goes down from 99% towards 80%. The question here if it goes asymptotically towards 80% or perhaps 50% with more simulations. Unfortunately I cannot continue this plot because I run out of memory and it takes ages to finish the games. So the question is then: are there a fixed gain of the heavy playouts with more than 512 simulations or does the effect of the heavy playout get less and less important with larger tree size. Note also that this also not only a matter of having heavy playouts or not. There is also a difference in tree search since Valkyria and Fuego probably search their trees differently, and it could be that Valkyria search deep trees inefficiently. Maybe I should run a similar test against a light version of Valkyria to control for the search algorithm. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Christian Nentwich Director, Model Two Zero Ltd. +44-(0)7747-061302 http://www.modeltwozero.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Complicated seki with Ko
This case is of course not pruned by Valkyria, simply because the the pattern here is completely different from what we discussed. :) This sacrifice prevents an eye to be made. -Magnus Quoting Christian Nentwich christ...@modeltwozero.com: |- - - - - - - |. * * o . . . |* . * o * . * |o . o o * . . |o * o . * . . |o o o * . . . |. * * * . . . |. . . . . . . |. * . . . . . Black to play and kill :) Christian On 01/07/2009 17:41, Magnus Persson wrote: In this case one needs to check that after the two stones are captured the capturing single stone can be recaptured bringing us back to where we started. If it is a big eye there is no recapture. -Magnus Quoting Brian Sheppard sheppar...@aol.com: For black I think I prune this kind of two stone suicide always no matter what the situation is (exception is ko). These prunings are probably wrong in some extremely rare cases. How can you tell the difference between this kind of two-stone self-atari, and a self-atari of two stones within an opponent's big eye, which could be necessary for lifedeath? ___ 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/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Complicated seki with Ko
Valkyria behaves the same as Many Faces in this position. It sees maximum 1% winrate for Black. The seki is not really detected by Valkyria, J6 is simply pruned for both players. For white it is just stupid suicide with too many stones. For black I think I prune this kind of two stone suicide always no matter what the situation is (exception is ko). These prunings are probably wrong in some extremely rare cases. Valkyria handles most simple cases of seki, including bent 4 in the corner, and recently seki where false eyes are true eyes because of seki. In general one does not need to make sure it is seki to prune stupid suicidal move or prune filling in false eyes that are could become real eyes in seki. One just has to prunes moves that looks stupid at the moment, and sort of postpone things. If the situation never change then it is a seki. X cannot fill J6 so in my way of seeing H5 is a real eye. A nice but computationally complex feature of the board representation of Valkyria is that all points that are suicidal or illegal are known at all times for sure. This makes it much easier to analyze these kind of situations. Best Magnus Quoting Brian Sheppard sheppar...@aol.com: With X to move, Many Faces immediately gives about a 1% win rate, and after a few seconds, resigns, showing 23742 playouts with 0.5% win rate. 10 ply principal variation, staring with A7. I don't have any special code to detect superko or give-2, get-1 in playouts, but the playouts don't generate self- atari moves in a seki, so I think it never tries J6 for either side. How does MF recognize that it is a seki without analyzing what happens in the ko? The eye on H5 is false if X can fill J6, so it is premature to use the both sides have an eye with only shared liberties rule. 1 2 3 4 5 6 7 8 9 A - O - O X - - X - B - X O - O X - O O C - O O - O - X O - D X X X O O O O O O E - O X X X O X O O F - - O X O X X X X G - - X X O O X X - H - O X O - O O X X J - O X O O - X - X X to play. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Complicated seki with Ko
In this case one needs to check that after the two stones are captured the capturing single stone can be recaptured bringing us back to where we started. If it is a big eye there is no recapture. -Magnus Quoting Brian Sheppard sheppar...@aol.com: For black I think I prune this kind of two stone suicide always no matter what the situation is (exception is ko). These prunings are probably wrong in some extremely rare cases. How can you tell the difference between this kind of two-stone self-atari, and a self-atari of two stones within an opponent's big eye, which could be necessary for lifedeath? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: fuego strength
much, but it appears to be over 200 ELO weaker at this level. Since fuego is using only about half the CPU resources of gnugo, I can increase the level.I've only played 30 games at 19x19, so this conclusion is subject to signficant error, but it's enough to conclude that it's almost certainly weaker at this level but perhaps not when run at the same CPU intensity as gnugo. Of course at higher levels yet, fuego would be far stronger than gnugo-3.7.10 as seen in the 19x19 cgos tables. But I'm hoping not to push the anchors too hard - hopefully they can be run on someones older spare computer or set unobtrusively in the background on someones desktop machine. - Don inline file ___ 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/ -- ___ computer-go mailing listcomputer...@computer-go.orghttp://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/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to Zen!
Quoting Nick Wedd n...@maproom.co.uk: In message 20090622202905.utvbb8wkgk8cw...@webmail.phmp.se, Magnus Persson magnus.pers...@phmp.se writes I looked at the report and would like to give my opinion on why the programs played as they did in the commented game between Zen and Aya. In the game white 106 threatens to capture the left side and most importantly avoid the dangers of a huge semeai. If black does not play 111 the game is over without a fight. After white 112 at least black has a chance that white blunders and get a seki or wins a semeai in the center. Saving the white group with 112 is only big if the black group dies. But it must die - unless the white central group dies. And the white central group can get out with n13, can't it? It can get out, but it is not that easy to read out. And this uncertainty is what strong players (and MC programs) try to avoid. Anyway, assuming you are right, may I quote you in my report? Sure. Maybe that maight provoke some even stronger player to give an even better analysis. Later on in the game white takes the ko at J11 for move 134 and after a ko threat black captures the right side group but white get the big left side for sure and a large endgame move at the bottom, for a clear won position, which illustrates the one sided nature of this game after move 105. By the way the main meaning of 105 is to threaten the center white group since if black tries to surround the white group white can connect and live with all white stones with 105. So in my opinion both programs played well moves 106-112. White simply played forcing moves that defended a won position and black tried to keep the game complex enough in order to have a possibility of winning. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Position Rich in Lessons
Quoting Brian Sheppard sheppar...@aol.com: What komi did you use? It is nice to have the sgf in addition to the position. It is 7.5, and I do not have the SGF. I will try to create SGF for future posts, to make reproduction easier for all. Could it be that Pebbles have trouble seeing that the semeai is won after white C9. Yes, exactly. Pebbles has no code (in either search or playouts) for winning semeais of more than one move. No pattern that identifies C9 as a good move for O. There is code that finds C9 for X: it is a winning snapback. There is no code that tries to play the opponent's move, so the knowledge does not transfer from one color to the other. What rule proposes C9 in Many Faces or Valkyria? C9 is not treated in a special way. I guess in this case it is AMAF that finds it and play at te root level. I use the same code to bias the tree part as I use for the playouts. In the playouts a lot of tactical code for pruning bad suicidal moves and playing forced moves (when the number of liberties in the semeai is 2 or less) are used. I can also be that Valkyria finds C9 for X quickly if O does not play it. 1 2 3 4 5 6 7 8 9 A - - - - - - - - - B - O O O O X X X O C - X X X O O X O - D - O - X O X O O - E O - O O X X O X X F - O X X X X X O - G - X X - - O X O - H X O O O - - X X O J - - - - - - - O - On the face of it, C9 doesn't put O ahead in any semeai. After C9, O is behind X's B8 string by 3 liberties to 2, and O is behind X's E8 string by 2 liberties to 2 with X to move. Anyway I entered the position manually with komi 7.5, and Valkyria plays C9 right away winning the semeai in the upper right corner and after that white wins 0.5 even if black gets everything else. C9 is winning, but it isn't so obvious as Magnus suggests. There are several complexities to see through. Your analysis is correct. And to me it just appears quite obvious. And as David point out it is not physical liberties that are counted but the move necessary to play. 1) O wins the semeai on top only if O moves first. After X's A8, O must find A6, A5, and A7. Those moves must be played in that order, because if X plays A8 and A6 then X wins the semeai because O cannot play A9, which is self-atari. 2) If O tenukis at any time, then X wins by playing F9 or G9, followed by capturing O's F8/G8 string, and atari with D9. 3) In a random-play game, the fact that X has 2 sequences versus 1 (i.e., F9 or G9 for X versus only A6 for O) makes up for the fact that O gets to move first. So it is vitally important to have code in the playouts that handle the semeai more accurately for O than purely random. 4) Magnus says wins by 0.5 even if Black gets everything else but that's not right. O must also win the semeai at left. In a random-play game, O would lose that battle fairly often. The principal way to lose is X C1, O tenuki, X D3 (atari), O E2, X F1 (atari), O G1 and a Ko fight for life. The O must win the semeai is also obvious. What I meant is that O can let X start ko fights and win them as long O just captures the large X block. 5) The Ko fight there is a picnic for X, since X was counting on losing anyway. It follows that X will gain a move in the battle of his choice, so O will only win if his tenuki was played in the semeai at upper right. I think that to play this situation completely right you must have playout policies that specifically drive success in semeais and/or ko. Valkyria does nothing intelligent when it comes to ko and wins always in this position. But this is because white can let black win all small ko fight as long as all important semeais is won. So in this position only semeai knowledge is necessary. But you might try to decrease the komi, because then white will have to win with a larger margin! That could make the position much harder to read out correctrly. Those successful policies do not have to be right for the right reason. For example, if you play C9 because you believe that it is the only move that has a chance of winning the semeai against E8/E9, then you are right for the wrong reason, because there is no way to win against E8/E9; C9 just happens to win against another string. Without heuristics that specifically drive success, the combination of multiple battles make matters combinatorially worse. For example, the dynamic in Pebbles is for the moves that win the semeais to be the second, third, fourth or higher move generated. This is not so bad if there is only one battle. But when multiple battles are joined, X can play a forcing move for a turn in another battles, and then return to the other side. It is a dynamic version of the horizon effect, where bad effects are first pushed out, and then delayed by bad move ordering. I think that working on this position will yield several advances in move ordering. I have already found the snapbacks, and I think there will be others. Are you talking about move ordering in the
Re: [computer-go] Zero exploration?
Yes, bad luck can be a problem. Solutions: 1) RAVE/AMAF do bias good moves such that exploration take place anyway 2) Biased priors that initially forces many playouts for good candidates, so that bad luck becomes less likely for moves that are rated high using patterns or other means. 3) One can try to bias all moves to be searched initially if one has no patterns Valkyria uses 1 and 2. I used to have 3 but at some pointed I tested it and it was really bad on large boards. Searching all moves at least once (or more) on 19x19 wastes way too much for no gain. But if the 1) and 2) does not work well because the program is weak otherwise maybe 3 can be an option at least on small boards. The hard part here is probable to have all these things working simultaneously, and when it started to do so in Valkyria it was really awesome! :-) Nethertheless I some times observe some good moves not being searched at all just because of random factors. I think there is a trade off here. In order to get a really efficient search all of the time one has to live with a small probability that some moves are overlooked now and then. Also highly selective search will correct itself given enough time, because if the current best move is not good enough to win the winrate will drop towards 0 which allows other move to be searched as well. Magnus Quoting Peter Drake dr...@lclark.edu: There has been some talk here of using a zero exploration coefficient. Does this literally mean using the win ratio (with one dummy win per node) to decide paths through the MC tree? It seems that the best move could easily be eliminated by a couple of bad runs. Does this only work when using RAVE/AMAF? -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Position Rich in Lessons
Quoting Brian Sheppard sheppar...@aol.com: Further analysis convinced me that O is actually winning this game. My current engine likes A8 for O until iteration 7000, and then F9 for O, and switches to the winning move only on iteration 143,000. But it doesn't really see the win, because the evaluation remains around 50.3% no matter how long Pebbles searches. What komi did you use? It is nice to have the sgf in addition to the position. Anyway I entered the position manually with komi 7.5, and Valkyria plays C9 right away winning the semeai in the upper right corner and after that white wins 0.5 even if black gets everything else. Could it be that Pebbles have trouble seeing that the semeai is won after white C9. Valkyria expects black A8 after C9 which delays the capture of the white stones. Sometimes Valkyria has (or used to) problems evaluating such semeais. -Magnus -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to Zen!
I looked at the report and would like to give my opinion on why the programs played as they did in the commented game between Zen and Aya. In the game white 106 threatens to capture the left side and most importantly avoid the dangers of a huge semeai. If black does not play 111 the game is over without a fight. After white 112 at least black has a chance that white blunders and get a seki or wins a semeai in the center. Saving the white group with 112 is only big if the black group dies. Later on in the game white takes the ko at J11 for move 134 and after a ko threat black captures the right side group but white get the big left side for sure and a large endgame move at the bottom, for a clear won position, which illustrates the one sided nature of this game after move 105. By the way the main meaning of 105 is to threaten the center white group since if black tries to surround the white group white can connect and live with all white stones with 105. So in my opinion both programs played well moves 106-112. White simply played forcing moves that defended a won position and black tried to keep the game complex enough in order to have a possibility of winning. Best Magnus Quoting Nick Wedd n...@maproom.co.uk: Congratulations to Zen, winner of yesterday's KGS bot tournament with 8 wins from 9 games. My (very short) report is now at http://www.weddslist.com/kgs/past/48/index.html Nick -- Nick Weddn...@maproom.co.uk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 1x1 patterns?!
Probably 1x1 patterns implies that different priorities are assigned to the absolute position of empty moves. AMAF can be seen this way. AMAF learns statistics of 1x1 patterns if the move is played in the playout but ignores all information surrounding the move at the time it is played. Another example would be to have lower priorities for the moves at the first and second line. -Magnus Quoting Peter Drake dr...@lclark.edu: I've seen reference in some papers to 1x1 patterns. What does that even mean? A point is either black, white, or vacant, and it's illegal to play there unless it's vacant. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MCTS, 19x19, hitting a wall?
Would this be a simple way of using many cores effectively? Otherwise I cannot see how recursive UCT would be anything else than an ineffective implementation of UCT. Unless it provides some information that could be used more effectively than with normal search. In order to do so the playouts need to communicate what moves are good perhaps something like the historyheuristic used in chess. Magnus Quoting Gian-Carlo Pascutto g...@sjeng.org: On Wednesday 10 June 2009 18:48:55 Martin Mueller wrote: Currently, we try to sidestep this fundamental problem by replacing local search with local knowledge, such as patterns. But that does not fully use the power of search. So, has anyone tried recursive UCT (using UCT again in the playouts), and what were the results? I saw some results for uninteresting games, but nothing about Go. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ 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
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] Negative result on using MC as a predictor
this, please let me know how it works out. Or if you have other ideas about how to extract more information from trials. Best, Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Future KGS bot tournaments
Actually, MCTS-programmers should be happy with any timeconstraints that does not make the program run out of memory, since a proper MCTS-program should scale nicely no matter the time constraint. Maybe an ultrafast tournament with a tenth of a second would favor Valkyria on small boards but we do not want to play that fast... I think all programmers should participate whatever strength their programs have. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
Valkyria simply do not expand the tree when it runs out of unused nodes. That would be the most simple thing to prevent crashing. Then one could consider pruning the tree in order to be able to expand the tree even deeper. -Magnus Quoting Isaac Deutsch i...@gmx.ch: 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/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Reflections on a disaster
Hi, as usual Valkyria seems to handle this position well at the price of being a super slow program in general. This is just one example of how it reacts. After 100 simulations it treats F1 as the best almost always, having searched 30 to 100 times. Perahps 50-70 times is the most common result. Valkyria handles this position well for two reasons. As soon as X plays F1, the semeai is defended properly, so the Winrate for O is just 5% and then drops down to 0%. The few wins for O comes from X randomly removing one of its own liberties in a dumb way at J5. Removing the liberty at G5 that makes an empty triangle is safely pruned since it is dominated by G6 which removes a liberty from the same block of O but gain a liberty. So one of the two gamelosing mistakes are pruned. The hard part for Valkyria is to search F1 at all, and there is a special mechanism (or hack really...) to ensure that. Valkyria computes AMAF win rates for all moves including those that are pruned or illegal in the position. What I noticed is that in cases of critical semeais the AMAF values of moves that are for example illegal can get very high since they only get legal when you win the semeai and thus win the game Therefore Valkyria takes the AMAF values of moves that cannot be played yet, and try to find approach moves that will enable playing them and replaces the AMAF values of the approach move with the AMAF value of the illegal move if it is higher. This is a costly computation so it is only done if the position has been visited several times. Without this AMAF-hack Valkyria sometimes has a problem finding F1. It also seems to take a longer time to find F1 in all cases where does find it. I have not yet tested the effect on the playing strength from this. Best Magnus Quoting Brian Sheppard sheppar...@aol.com: The simplest problems give me new appreciation for the difficulties we face in programming this maddening game. Here is an example, with X to play: 1 2 3 4 5 6 7 8 9 A - X - - - - X - - B - - - - X X - X X C X - - - X - X O O D X X X O X X O O O E O O O X X X X O O F - X X O O O O - O G - X O O - - - O O H O O X X X X O - - J - O O X - O O - - heuristics often produce the *wrong* move ordering, too. In that case there is a loss of efficiency. Yes this is the hard part. Note for example how Valkyria in this position will prune X at G5 becuase G6 must always be a better move. However, X J5 is not pruned because at the moment I have no simple way of proving that removing a liberty from the opponent is not a good move. The easiest way to prune that move would be to read the ladder it creates, still it might be confused with a nakade that sacrifices stones to kill and capture the surrounding stones so one need to make sure this is not the case so I will not do that in Valkyria right now it is just too complicated. Best Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Justification for c==0
Quoting Brian Sheppard sheppar...@aol.com: OK, so you don't have to worry if you set c==0. It might even be best. Just a note: in very preliminary experiments, c==0 is not best for Pebbles. If longer experiments confirm that, I presume it is because Pebbles runs on a very slow computer and searches only small trees. So your mileage may vary. But if c==0 tests well, then there is no reason not to use it. I think it has to do with two things. Valkyria uses c==0 but I started doing that when I combined AMAF values with win rates. Even if only one move is searched AMAF values for nonsearched moves can go up and thus force the search to switch, even if the win rate for the most searched move does not go down. Also with higher quality playouts you get a wider range of win rates for bad and good moves which lowers the need to search all moves as used to be the case before. Other than that I agree that sticking to winning moves unless proved otherwise seems to work well. It just does not work fast enough if the search otherwise is ineffective. Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Roadmap 2020 - using analysis mode to improve programs
a bit with a commercially available program. An almost-ladder which has an extra liberty will apparently be evaluated the same as a true ladder, and the program can be tricked into trying to capture my ladder-like position. This sort of predictable flaw might provide a clue to improve the next version. Terry McIntyre terrymcint...@yahoo.com Government is an association of men who do violence to the rest of us. - Leo Tolstoy ___ 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/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can't get on CGOS
/main.tcl -c CONFIG_FILE -k KILL_FILE -p PLAYER_FIRST -s -c specified name of config file - this is MANDATORY -k sepcifies a file to create which will stop client after current game -p specifies which player plays first game -s display a sample configuration file to stdout and exit Third: I dug through archives and found what I thought might be a valid configuration file. Its contents are shown below: # config file for testing various version of Pebbles # %section server server cgos.boardspace.net port 6867 %section player name Pebbles password mypwd invoke../Release/Pebbles.exe priority 1 Now I really am not sure what the specified name and password mean. Is this the name of the program on CGOS? Or is this the login name of the account that is registered on CGOS? Fourth: I looked for instructions about how to get an account on CGOS, but I did not find any. Am I supposed to create an account on boardspace.net, and use that account? Fifth: I tried to use the supplied config file, and I got a peculiar error message: (Pebbles) 6 % cgosGtp.exe -c cgos-config.txt -k kill.txt -p Pebbles child process exited abnormally Also, a dialog box titled Error in TclKit popped up with the following message: this isn't a Tk applicationbad window path name cgos-config.txt I probably should have asked just one question: how do I get my program on CGOS? But then someone would have pointed me to http://cgos.boardspace.net/. :-) Background info: I am using GoGui as front end, and I have implemented enough GTP to play go using GoGui. Is that enough for CGOS also? Help would be appreciated. Thanks, Brian ___ 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/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can't get on CGOS
Hi Don, you can of course use my example! I did test with the viewer and it did not work. Yesterday I tried to connect Valkyria but had to switch to 19x19. Could it be that only you can start connect when no one else is connected? Best Magnus Quoting Don Dailey dailey@gmail.com: Hi Magnus, Can I use your examples and such and put a section in the web page? As far as I know, CGOS has not been down. Unless it was somehow preventing logins or something.The way to test is to bring up the viewer, it will not come up at all if CGOS is down. I put 3 weak programs on the 9x9 server just so that people would have something to play against and Brain might be able to get things tested. I'm also updating the archives, since December though Feb is missing. - Don -Original Message- From: Magnus Persson magnus.pers...@phmp.se Reply-To: computer-go computer-go@computer-go.org To: computer-go@computer-go.org Subject: Re: [computer-go] Can't get on CGOS Date: Sat, 28 Mar 2009 16:14:48 +0100 Ok, here is what I do to connect to CGOS using Windows XP. This citation is from the a box on the CGOS page: A note for Windows users: If you choose the Multi-platform starkit route, please note that there are 2 types of tclkit's for your platform. One is built with TK support (for GUI application) and is probably not the one you want, although it can be made to work if you know what you are doing. The one you want will have a name like tclkitsh instead of tclkit or some variation of this. So one want to use the file tclkitsh for windows and nothing else. I have a single line .bat file that look like this, which enable me to stop the client by creating the file Quit.txt (with a second file Quit.bat that copies itself to Quit.txt) and all activity is logged to log.txt: tclkitsh cgosGtp.kit -c config9.txt -k Quit.txt log.txt The file config9.txt look like this: %section server server cgos.boardspace.net port 6867 %section player name Valkyria3.2.7 password invoke..\\..\\ValhallGTP.exe time threadengine ponder priority 7 You need to use '\\' instead of '/' in the path to your program I think. Note that as far as I know the 9x9 server has not been running for over a week, so this is of course also a reason for not beeing able to connect to it... I find it useful to use the viewer for testing if CGOS is running, and the log file is also immediately helpful. I hope this will help. Also, since the 9x9 server is down, some programs are actually playing 13x13 right now so it would be fun if more programs did that, since it is so rare that any programs at all play 13x13. Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ 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?
Quoting Sylvain Gelly sylvain.ge...@m4x.org: On Wed, Jan 28, 2009 at 10:01 PM, Isaac Deutsch i...@gmx.ch wrote: 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? Yes the formula looks very similar (David proposed that formula to me in the beginning of 2007). However my implementation did not contain the (q_ur*(1-q_ur) factor, that I approximated by a constant, taking q=0.5 so the factor=0.25. I did not try the other formula, maybe it works better in practice, while I would expect it is similar in practice. Valkyria uses an even more complicated version of what David Silver proposed (I really did not understand it so I came up with something that looked plausible to me that actually estimated the bias for each candidate move rather than assuming it constant). When Sylvain proposed this simple version I tested that version against my own interpretation. On 9x9 my complicated version might have a win rate 3% better than the simple version for 3 data points (700 games each) near the maximum. The standard error according to twogtp is 1.9. On 19x19 I got results where there no difference at all but with much higher uncertainty because there was not many games played. But the term is important for sure, the constant BIAS used should be larger than 0 but you should be careful to not set it too high. For Valkyria the 0.015 value Sylvain posted here worked fine. But if it is higher for example 0.15 leads to bad performance on 9x9 and catastrophic performance on 19x19. Initially I thought this parameter should be something like 1 and that was completely wrong. I was just lucky to get it right, just by visual inspection of the search behavior when I played around with the parameter. The reason is that the bias term of the denominator should be close to zero initially is to allow AMAF to have strong impact on the search but at some point (which is delayed by having a small BIAS constant) there is a quick shift towards using the real win rate instead. -Magnus ___ 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?
Quoting Sylvain Gelly sylvain.ge...@m4x.org: On Fri, Jan 30, 2009 at 9:29 AM, Magnus Persson magnus.pers...@phmp.sewrote: Did you try to tune the bias constant at all or just took the one I posted? I wrote it from memory and I believe it is in the range of possibly good values, but it is certainly not optimal, I can be off by a significant factor in both directions. Yes I always tries to test at least 5 values. Three values centered around what I currently believe is the best value and two or more values to the extremes to get the big picture and make sure that I am at least the maximum. ConstantWinrate Against Gnugo 0.00015 43.9 0.0015 50 0.015 50 0.1543.1 1 7.1 10 6.7 The bias can't possibly be 1 because by definition it is the difference between the expected value of the normal tree search and the expected value of AMAF. As those two values are in [0,1] anyway, the bias is certainly not 1, and in most cases very small. I think I was confused about exactly what in the term that was the bias. I do not really remember what and why I thought these things. Anyway your explanation is very clear. On a side note I think Valkyria for some moves have very large biases because the playouts are very heavy. I am thinking of an experiment to test this. One way is to simply play uniform playouts from a single position N times for all moves and thus get accurate win rates for all those moves as well as AMAF values. Then taking the difference in values for AMAF and real win rates should reveal the size of bias in general and if there are systematic difference for certain patterns or situations. Alternatively one could play N playouts for a single move and see what AMAF values one get. Now can see to what extent the biases are stable when moves are played on the board. The real values will change for all moves and the AMAF as well, but will the bias be constant? Or will it be random as a function of the position. There is no tree search in these two cases. Selective search is often similar to the second situation, and my question is whether this can cause larger systematic biases for some moves, that thus is missed. And if one understands the nature of such biases maybe they can be neutralized somehow. It could be that using patterns to start with strong biases in the prior AMAF values is doing exactly this. Has anyone has done anything like this or have any interesting opinions I would be thankful. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] hard position for MCTS
Quoting Darren Cook dar...@dcook.org: Interesting position attached, white to play. Both Many Faces and Mogo utterly miss the correct move (white H2). And they don't even get it after black fills F4 - they both still believe they are winning (though Many Faces' static score gets it right at that point, as does gogui scoring). Valkyria selects this move before it searches... and then spends 90% of search on H2. The reason for is simple. Valkyria recognize this type of seki in the playouts and can therefor accurately evaluate the situation. Programs who do not do that are doomed because in such playouts black will probaly fill in and break the seki in playout. This having nothing to do with search algorithm, seki is something that has to be reconized in the playouts in order to be handled properly. Valkyria handles some common seki shapes but not all of them, and would also fail miserably in such positions. Best Magnus -- Magnus Persson Berlin, Germany ___ 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?
Quoting Thomas Lavergne thomas.laver...@reveurs.org: - the best play is a good only if played immediatly and very bad if played later in the game : - the first playout for this play resulted in a lost. score and RAVE score will be very low and this play will never be considered again until a very long time. You raise an interesting concern. The simple solution to your question is to add an exploration term using UCT for example. Then it becomes an empirical question what parameter for exploration gives the strongest play. My experience is that the best parameter is so small it can be set to zero. I think the conditions you defined are very rarely completely fulfilled. What can be true often however is that a single bad move makes the best move very bad if played later in the game. If the bad move happen to be the second best move, it will be searched a lot lowering the AMAF score (rw/rc) for the best move. This is likely to happen when there are several local moves that more or less solves the same problem. That is when one move is played the effect of the other move played later will overlap with the first. -Magnus ___ 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 think I found a bug in ChooseMove Quoting Sylvain Gelly sylvain.ge...@m4x.org: coefficient = 1 - rc * (rc + c + rc * c * b) I think this has to be coefficient = 1 - rc / (rc + c + rc * c * b) thus when c is 0 (initially) the coefficient is 0 when c goes towards infinity the coefficent goes 1 which is how this function should behave. Magnus -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT RefBot
I could find anything problematic with your specification so I just make some comments. Quoting Mark Boon [EMAIL PROTECTED]: - When it reaches N simulations, the child of the root-node with the best wins-visits ratio is played. I've also seen that simply the child with the highest number of visits is selected. Is there a difference? The following can happen if you chose the move with the best wins-visits ratio: If the search is very selective (for example using progressive widening or AMAF (RAVE)) a move can be searched a small number of times and get a really good ration and selected. In Valkyria which uses both methods of selectivity there is always moves that have higher win-visits ratios than the most searched move (19x19). If you do plain MC and UCT I think win-visits may be just as good as highest number of visits, because the search will be quite wide. Using the highest number of visits is sort of robust. Even if you know the move is not as good as it initially seemed, you sort of know that one has to search deep to see this and maybe the opponent cannot see the refuting move. Also the reason for the low win-visits ratio may be that problems in the position will give a low ratio for all moves if they are searched deep enough. This is by definition true in any lost position. If you can prove that all moves are losing the move that required the largest tree for the proof is the candidate for provoking a mistake. Valkyria plays fast whenever win-visits and highest number of visits agree and slow otherwise, in an attempt to eliminate uncertainty. I'd also like to hear opinions on what would be a good N for a reference bot. If I set N to 2,000, just like the reference-bots on CGOS, it plays rather poorly. Much worse than the ref-bot. I haven't tested it a lot yet, but I think the break-even point against the MC-AMAF ref bot would be somewhere around N=10,000. What about doing a MC-AMAF-UCT version. Or perhaps just simply try a MC-AMAF-TS in a best win-visits ratio first manner? Best Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT RefBot
Quoting Mark Boon [EMAIL PROTECTED]: Thanks for the comments Magnus. On 20-nov-08, at 13:00, Magnus Persson wrote: The way I understood the article, after a playout it updates all the nodes at the current level of all the moves played during the playout (if it's a win for the player) with a RAVE value that is used in a similar fashion to the UCT value of a node. Only of the current node does it update the win-visit ratio. Is that correct? This implies creating a lot more nodes than I'm currently doing. I have seen remarks that others postpone expanding a node until a certain number of simulations have been done. I never quite understood the need for that, but maybe this has to do with the fact that AMAF requires a much larger number of node-creations? I think you understand the basic principle of RAVE correctly. The hard part is how to weight together the AMAF value (which I call *virtual win-visit* ratio) with the actual win-visit ratio. And I have to admit that my implementation of RAVE in Valkyria might be a quite unique interpretation of the somewhat hard to understand information that has been posted here. I just implemented something that seemed to work and tested the parameters thoroughly. But I think I need to do new tests since there has been so many changes. Especially I should do test on large boards. Valkyria postpones expansion of new nodes about 10 times, and an expansion includes all children of a position. This is necessary in order to update virtual win-visit scores for all moves played of the color for the current simulation even if there is only one. Thus a node in the tree is a list of children for a given position. This simplifies code that bias the tree search, since all necessary algorithms are executed simultaneously for all children during expansion. This is perhaps not efficient, but is perhaps less prone to bugs. The effect of RAVE with a complete expansion is that after a few simulations (let us say 40) we have a rather good sample of virtual win-visit scores for all moves. Also if patterns biases exploration all real win-visit scores has been collected for those moves (often a single move) that are most likely to be the best. Thus the win rate for this position is already close to that of the best move. This is different from pure MC-UCT where all candidate moves are searched once and the win-rate initially is the average of all moves, bad as well as good ones. It takes a lot of time until MC-UCT will converge on to the winrate of the best move in each position. Simply put combining virtual and real win-visit values for searching the tree lets us safely ignore the worst moves in all positions and the search basically only searches moves that our pattern heuristics predicted to be good or moves that were discovered thanks to AMAF. The search is very selective when it works. And of course it often misses the best move. But it kind of works because a) often the second best move wins as well b) the selective search searches so deep effectively so it corrects itself quickly. Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT RefBot
About allowing early passes. I think my problem is that RAVE/AMAF really say nothing about the value of pass moves, which makes it problematic when selective search do not search bad moves such as pass. So how are we supposed to know when to search pass and not? Thus, everytime I had some kind of design flaw or a bug in Valkyria it seemed to play early passes because of some weird interaction in my code. So allowing passes early seemed to be a good bug catcher... on the other hand it also seemed to cause bugs for me. I do not even remember anymore how Valkyria handles pass because I changed it so many times and had to add a lot of kludges to avoid problems with older kludges and so on... -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] FW: computer-go] Monte carlo play?
I use a method inititally from the Mogo team that sorts of randomizes the position before running the heavy playout. One simply plays uniformly random *non contact* moves. The effect of this is that it preserves the shapes of stones on the board, but it prevents the heavy playouts from playing long sequences deterministically. I have not tested this, but I felt that the evaluation on large boards got less noisy and/or biased doing this. Magnus Quoting Michael Williams [EMAIL PROTECTED]: It seems move selection in the playouts should be very random at first and more deterministic toward the end of the playout. Has anyone tried that? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] FW: computer-go] Monte carlo play?
I have to add that it is possible that a large part of the advantage from using heavy playouts in valkyria comes from using the same code to bias the the exploration part of MCTS. I could probably test it by simply relying completely on AMAF with the proximity heuristic as the only bias. A second experiment would be to rewrite the playouts and make them superfast. -Magnus Quoting Mark Boon [EMAIL PROTECTED]: On 17-nov-08, at 02:42, George Dahl wrote: So you say that: ...I'm observing that most of the increase in level comes from the selection during exploration and only in small part from the selection during simulation., could you elaborate at all? This is very interesting. That almost suggests it might be fruitful to use the patterns in the tree, but keep lighter playouts. That's exactly what it's suggesting. But as I said, I need to do some more testing to make a hard case for that. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] FW: computer-go] Monte carlo play?
Quoting Hideki Kato [EMAIL PROTECTED]: Heikki Levanto: [EMAIL PROTECTED]: The way I understand it, modern Monte Carlo programs do not even try to emulate a human player with a random player - obviously that would not work. I believe CrazyStone's use of patterns does so and it seems successful. With Valkyria I try to follow two principles in heavy playouts. 1) In contact fights there are a lot of shapes that are played most of the time. Thus Valkyria checks each move played if there is an obvious local response to it. If so it plays it deterministcally. In many situations there are two or more such candidates and then it plays one of those moves. 2) In many positions the last move played does not trigger any obvious response, and then a random move is chosen uniformly 3) There are moves that are inferior 100% of the time both locally and globally. These moves are pruned if they are selected and a new random move is chosen as long as there are moves left to try. I got hundreds of handcoded patterns for both 1 and 3. It would be too time consuming to test these patterns, so I use my knowledge and intuition (European 2 Dan) to simply decide what patterns to include. So Valkyria has a lot of go knowledge, but mostly such knowledge that all go players have up to some strength such as perhaps 8-10 kyu. It has no knowledge about global matters. The beauty of MC-evaluation is that globally strong moves are most of the time evaluated better than globally weak moves. Heavy playouts removes noise from MC-evaluation and makes it more sensitive to the true value of moves. Still there are biases with all heavy playouts, but they are overcome with MC Tree Search (MCTS) that corrects mistakes in the evaluation recursively. Here are my latest scaling experiment on 9x9 for Valkyria. Valkyria plays 1150 random games per second on my 4 year old laptop. This test is against gnugo 3.7.10 assumed to be Elo 1800. Most datapoints are based on 500 games. N sims means Valkyria playes N heavy playouts per move played. Winrates are in %. N sims WinRate Elo (rel Gnu) 47 7.4 1361 94 22 1580 188 37 1708 375 53 1821 750 69.91946 150081.22054 300088 2146 600092.62239 12000 94 2278 24000 97.22416 48000 97.42429 the heavy playouts of Valkyria needs just 375 random games per move to match gnugo using only 0.3 seconds per move. And even using only 47 simulations per move it can still win. So obviously the heavy playout code of Valkyria is much weaker ( Elo 1361) than Gnugo and most human opponents, but compared to CGOS a lot of programs witho no knowledge are about the same level, although they uses 2000 simulations or more. Searching efficiently using MCTS with AMAF it apparently can be made arbitrarily strong. Hope this explains how both the nature of playouts and the MCTS contributes to the playing strength of a program. Should one go heavy or light? I do not know, I feel that Valkyria is a little bit too slow on equivalent hardware against most top programs. On the other hand I think it could be tweaked and improved upon. Perhaps it can even be made faster by removing code that does not improve playing strength. And there is probably still room for adding code that improves strength without a noticable slowdown. I just know that is a lot of hard work doing it the way I did it. Best Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] FW: computer-go] Monte carlo play?
Yes, Valkyria does a lot of ladder reading as well. Actually pattern matching in the case of Valkyria is a little unclear, it is a decision trees where the leaves are often procedure calls that looks at a larger portion of the board. The ladder code is called for various reasons in the tree. Is 3.7.10 level 10 weaker than the default settings? I will run a test using 5000 playouts and 375 playouts to see if it makes a difference. Also have you tried this version on CGOS9x9? This version http://cgos.boardspace.net/9x9/cross/Valkyria3.2.6_C2.html used a machine similar to yours and reached 3000 playouts per second using two threads. Your code is then 8 times faster and should be much stronger. -Magnus Quoting David Fotland [EMAIL PROTECTED]: I thought Valkyria does local search (ladders) during the playouts. Many Faces is lighter on the playouts. I have 17 local 3x3 patterns, then go to uniform random without filling eyes. Against Gnugo 3.7.10 level 10 on 9x9, with 5000 playouts, I win 92%, so our performance is similar. I'm doing 23K playouts per second on my 2.2 GHz Core 2 Duo, so my performance might be a little better, depending on the specs of your old machine. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: AMAF
Quoting Darren Cook [EMAIL PROTECTED]: But that is just an impression I'd picked up from day to day reading of this list; and at CG2008 people were still talking about AMAF in their papers (*). Can someone with a strong bot confirm or deny that AMAF is still useful? Valkyria probably has the (?) heaviest and slowest playouts of all stronger programs. Thanks to AMAF Valkyria searches extremely selective. I have not tried to turn of AMAF. I am currently comparing Valkyria with the results from 13x13 scaling study. http://cgos.boardspace.net/study/13/index.html Here is just one datapoint for level 4 the programs uses 1024 simulations per move. LeelaLight 824 Elo Leela 1410 Elo Mogo 1599 Elo Valkyria 1860 after 100 games in general it as least 200 Elo stronger than Mogo using the same number of simulations. But currently I think Mogo is fast enough to be slightly stronger on equivalent hardware using normal time controls. If I turned off AMAF for Valkyria I would probably have to retune all parameters to make a fair comparison, but I am quite sure that crudely turning it off would be very bad. Magnus -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] (early) termination of random playouts?
Valkyria does, because is superheavy anyway! A lot of weird stuff can happen near the end of the game against programs that play randomly. I think I implemented it because I had to to make it play correctly in some positions. But it was a long time so I do not remember the details. -Magnus Quoting Michael Williams [EMAIL PROTECTED]: While this may be true, I don't think anyone uses the superko rule in the playouts. It would slow them down too much and there would probably not be much benefit beyond the theoretical. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] (early) termination of random playouts?
No, if there was a serious problem it would perhaps only happen for 1 in 1000 games. So it would be pointless trying to measure it. And some of these problems only happens against extremely weak programs. At least in my experience. -Magnus Quoting Michael Williams [EMAIL PROTECTED]: I stand corrected. Do you know if you were able to measure a strength increase? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Leela experiment with 6x6
I checked these variation myself and with valkyria and it seems to be sensible. -Magnus Quoting Don Dailey [EMAIL PROTECTED]: I took all the games played by Leela in my 6x6 experiment and applied mini-max to them, taking the statistics at various depths into the games. Don't know if there are bugs here or not but this is what I get: Depth Score Principal Variation - --- -- 1 0.2372 C3 2 0.2372 C3 D4 3 0.2372 C3 D4 C4 4 0.2372 C3 D4 C4 D3 5 0.2500 C3 D4 C4 D3 C5 6 0.2500 C3 D4 C4 D3 C5 C2 7 0.2500 C3 D4 C4 D3 C5 C2 B2 8 0.2500 C3 D4 C4 D3 C5 C2 B2 D2 9 0.2500 C3 D4 C4 D3 C5 C2 B2 D2 E5 10 0.2500 C3 D4 C4 D3 C5 C2 B2 D2 E5 D5 11 0.2500 C3 D4 C4 D3 C5 C2 B2 D2 E5 D5 D6 12 0.2182 C3 D4 C4 D3 D5 E5 D2 E2 E3 E4 E1 F3 13 0.4286 C3 D4 C4 D3 D5 E5 D2 E2 E3 E4 E1 C5 B5 14 0.4286 C3 D4 C4 D3 D5 E5 D2 E2 E3 E4 E1 C5 B5 F3 15 0.6579 C3 D4 C4 D3 D5 E5 D2 E2 E4 E3 E6 F4 C5 C2 B2 16 0.6579 C3 D4 C4 D3 D5 E5 D2 E2 E4 E3 E6 F4 C5 C2 B2 D1 17 0.6579 C3 D4 C4 D3 D5 E5 D2 E2 E4 E3 E6 F4 C5 C2 B2 D1 B1 18 0.6579 C3 D4 C4 D3 D5 E5 D2 E2 E4 E3 E6 F4 C5 C2 B2 D1 B1 F6 19 0.7000 C3 D4 C4 D3 D2 E2 D5 E5 E3 E4 E1 C5 B5 F3 C2 D6 B6 F1 F2 20 0.7000 C3 D4 C4 D3 D2 E2 D5 E5 E3 E4 E1 C5 B5 F3 C2 D6 B6 F1 F2 C6 21 1. C3 D4 C4 D3 D2 C5 D5 E5 E2 B5 B4 F3 F2 A4 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Correct Komi for 6x6 is 2.0
I fear we are not talking about the same game. In case I made a mistake in my email you get the sgf here: (;FF[4]CA[UTF-8]AP[GoGui:1.1]SZ[6] KM[2.5]DT[2008-09-30]RE[B+Resign] ;B[cc];W[dd];B[cd];W[dc];B[db];W[eb];B[de];W[ee];B[ed];W[ec] ;B[ef];W[fd];B[ce];W[cb];B[bb];W[da];B[ba];W[ff];B[fe];W[ca] ;B[bc];W[ff];B[ea];W[fa];B[fe];W[ed];B[df];W[ff];B[fb];W[fc] ;B[fe];W[];B[ff]) There is only one black group and it cannot be killed because there are no cutting poits and the eyspace is too large. -Magnus Quoting Ingo Althöfer [EMAIL PROTECTED]: F1 by Black would be a huge blunder, because then White plays B1 and kills the black group in the lower right corner. So, Black has to react on the quasi-Ko-thread c2, giving White time to occupy F1. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Correct Komi for 6x6 is 2.0
Great! Mystery solved. Magnus Quoting Ingo Althöfer [EMAIL PROTECTED]: Hello Magnus, there was indeed a notation error in your original posting. There you give 13.C1 (see last line below) and not 13.C2 as in the sgf. Ingo. I have been trying to see what Valkyria does. But it is a little unstable when it reads deep at 6x6. It should not be a problem for Valkyria but I have not had any time to search for the bug. Anyway the 2.5 komi black should lose if Don is right. So I have the following very cute complete game sequence: bC4 wD3 bC3 wD4 bD5 wE5 bD2 wE2 ... The beginning is very natural, and although I did not check carefully all what Don reported but I think there is agreement that this is a strong seqence for both colors. ... bE3 wE4 bE1 wF3!!!... Normally wF2 is played in the corner. But with wF3 white has the option to play aggresively with wF1 which usually is a bad idea because the ko fight risk to much. But on a small board things are not normal... ... bC1 wC5 bB5 wD6 bB6 wF1!... -- 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/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Correct Komi for 6x6 is 2.0
Quoting [EMAIL PROTECTED]: See comments below... ... bE3 wE4 bE1 wF3!!!... Normally wF2 is played in the corner. But with wF3 white has the option to play aggresively with wF1 which usually is a bad idea because the ko fight risk to much. But on a small board things are not normal... Can I ask which ruleset this is played with? All the computer go engines here based on MCTS methods assumes area scoring rules. So unless stated otherwise you can see area scoring as default. For example, in Japanese or similar rulesets where dame are not worth anything, white cannot gain any benefit by starting the F1 ko. So I will assume it's some sort of area counting until told otherwise... Maybe F1 simply speaking is a trick move. Right now (on a new computer in office) I have to visualize the game in my head... so take any answers to your question with a grain of salt. ... bC1 wC5 bB5 wD6 bB6 wF1!... white starts a ko. If white first plays wC6 bF1 wins the game right away. To clarify, that would be B+1.5 (with your 2.5 komi) right? This wF1 can be a skillful play to try to steal the last dame, but doesn't your sequence below show it to be a failure (B+3.5)? I agree that bB4 (filling in your own territory) is optimal - nice move :) Initially Valkyria (my program) and myself thought starting the ko was correct. But cutting as a first ko threat also creates a lot of kothreats. So of course it is a failure, but I am sure you could beat strong opponents with it. It is a good trick to try. But technically all moves for white are losing moves anyways since the komi is only 2.5. In other words it is a difficult move for both humans and at least one computer program. After looking at the various games posted here and a number of variations of my own, I'm inclined to think the correct komi is 4 (for area counting.) Here is an interesting variation that noone has mentioned, maybe someone can find a flaw: bC3 wD4 bC4 wD3 bC2 wC5 bB5 wD5 bE2 wD2 bD1 wB6 bE3 wB4 bB3 wA5 bE4 wE5 bF5 wA3 bA2 wA4 bF4 wE6 bF6 (B+4) I played it out with paper and pencil and it looks reasonable to me. But I need to check it later with Valkyria and Gogui. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Correct Komi for 6x6 is 2.0
I have been trying to see what Valkyria does. But it is a little unstable when it reads deep at 6x6. It should not be a problem for Valkyria but I have not had any time to search for the bug. Anyway the 2.5 komi black should lose if Don is right. So I have the following very cute complete game sequence: bC4 wD3 bC3 wD4 bD5 wE5 bD2 wE2 ... The beginning is very natural, and although I did not check carefully all what Don reported but I think there is agreement that this is a strong seqence for both colors. ... bE3 wE4 bE1 wF3!!!... Normally wF2 is played in the corner. But with wF3 white has the option to play aggresively with wF1 which usually is a bad idea because the ko fight risk to much. But on a small board things are not normal... ... bC1 wC5 bB5 wD6 bB6 wF1!... white starts a ko. If white first plays wC6 bF1 wins the game right away. ...bF2 wC6 bB4! if I understand this move it is a truly cool move. If black plays the larg ko at E3 as most people would instinctively do including myself white cuts at B4 and get a lot of kothreats and wins the game. With bB4 white has no ko threats. ...wF1 bE6 wF6 bF2 wE3 bD1 wF1 bF5 wF4 bF2 wPass bF1 B+3.5 So komi should be larger unless there are a mistakes by white in this sequence. Valkyria should have the credit for all strong moves here but they are not always found, so this analysis is also shaky. At short time controls I do not think any existing MC programs will get these things right. Even if it is wrong I found some of the moves really fascinating. The search behavior of Valkyria jumps up and down between 25-75% all the time as these moves are found. If it had been more stable maybe I could just let it run for a long time and find out stuff more or less for sure. But I hope this sequence adds some understanding at least. -Magnus Quoting Don Dailey [EMAIL PROTECTED]: I would be very interested in various opinions on this. Is the correct komi for 6x6 (under CGOS type rules) 2.0? Especially would I like to see some strong players review my (actually Leela's) analysis and weight in on this. Do you think we can say with relatively high confidence that 2.0 is the correct komi for 6x6 go? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Correct Komi for 6x6 is 2.0
Quoting Ingo Althöfer [EMAIL PROTECTED]: Hello Magnus, interesting and strange. I went through your constructed game (it is repeated here without the in-between text) bC4 wD3 bC3 wD4 bD5 wE5 bD2 wE2 ... ... bE3 wE4 bE1 wF3!!!... ... bC1 wC5 bB5 wD6 bB6 wF1!... ...bF2 wC6 bB4! ...wF1 bE6 wF6 bF2 wE3 bD1 wF1 bF5 wF4 bF2 wPass bF1 B+3.5 Here I do not understand your counting: Black has control over 21 sqaures, White over 15. So, the final score of your game would be B+6. I am assuming a komi of 2.5 that is 6-2.5=3.5. But ... when White instead of passing continues wC2, the game should go on with bB2 wF1 bPass wF2, and now the score is B+2. Black ignores w C2 and plays F1. I added the pass only because it gives us the shortest game with the correct score for this variation. Or did I miss something? By the way, in my experimental runs with Leela it was really strange to see the evaluation switching between rather extremes - on this little board. I think it is completely normal and expected. MCTS is so strong on small boards that most of the time it searches variations with a certain outcome. But when the search discovers overlooked moves the score quickly change. Much more so than on larger boards. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Correct Komi for 6x6 is 2.0
I stubbornly always use x.5 komi because I do not like Jigo. in this case it was 2.5. I do that simply because Valkyria is coded like that, it cannot play with integer komi. Quoting Christoph Birk [EMAIL PROTECTED]: On Tue, 30 Sep 2008, Magnus Persson wrote: ...wF1 bE6 wF6 bF2 wE3 bD1 wF1 bF5 wF4 bF2 wPass bF1 B+3.5 I guess you mean B+4. Couln't black win by just refusing to play the ko? I could B+4 in that case too. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo v.s. Kim rematch
Quoting Mark Boon [EMAIL PROTECTED]: Playing out that fake ladder in the first game meant an instant loss. Surprising. And embarassing. Any information on the number of processors used? The interesting question is if there is a silly bug or something more sophisticated. I have struggled with ladders in Valkyria and it is often really hard to tell what causes these problems. In Leksand most games on 19x19 where lost in a ways similar to the recent mogo game. I could not find an obvious problem with the playouts at least not in terms of an easily fixable bug. Note that Valkyria reads out 99% of all ladders correctly both in the tree and in the playouts. What I realized was that AMAF in combination with heavy playouts causes some serious biases, for some kinds of very bad moves such that AMAF completely misevaluate them. In the case of the ladders the heavy playouts of Valkyria correctly prunes playing out ladders for the loser. But sometimes in the playouts the ladder is broken and after that there is a chance that the stones escape anyway. This means that almost always when the escaping move is played it is a good move! Thus AMAF will assign a very good score to this move My solutions to this was simply to turn off AMAF-eval for all shapes commonly misevaluated for ladders. But I think this problem is true for many shapes in general. What makes ladders special is that the problem repeats it self and the effect get stronger and thus even more likely the larger the ladder gets. I think a better solution would be to modify AMAF in some way to avoid these problems, or perhaps change the playouts in a way to balance the problem. Does anyone know something to do about it or have any ideas? -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Disputes under Japanese rules
I would also like to add the following: The real answer to this question about how to end a game with japanese rules is that it over a longer course of time it is solved through social interaction. If someone refuses to score games correctly you simply never play a game with that person again. Also if someone would do this in a club setting everyone would soon know about it and the offender would have to adapt or never play a game again. On the internet however it is much easier to abuse social conventions and get away with it. This applies not only to go but basically all activities, and therfore one often see extra control systems such has ratings on Ebay, moderators in discussion groups, etc. Japanese rules work perfectly fine in real life, but one have to realize it is because it is a social game not a mathematical abstraction. -Magnus Quoting Dave Dyer [EMAIL PROTECTED]: Japanese: bad. I don't think this is the case at all. The Japanese rules are just a human optimization, to avoid having to make the last 100 meaningless moves, and still arrive at the correct score with a minimum of extraneous manipulation. The tortured details, while not elegant, rarely matter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Bobby Fischer
I know a 4-Dan player who told a story that goes something like this: He and his friends who were all very strong chess players at the time, discovered the rules of go and played a bunch of games against each other until they thought they mastered it. Later they met a player who gave them a 9-stone handicap and beat them easily. They were shocked and told him he must be a master player but he just replied: No I am just a beginner. -Magnus Quoting Mark Boon [EMAIL PROTECTED]: On Thu, Sep 11, 2008 at 8:53 AM, Adrian Grajdeanu [EMAIL PROTECTED] wrote: I read that story in a book, just after Bobby Fisher's death. Don't remember all details, save that he was astonished he got beaten. Adrian Hehe. After I learned the game (from a book, playing with my father who brought a set from Japan for my birthday) I was also astonished to be beaten by the first other person I met that knew the game. And he gave me 9 stones handicap! But rather than putting me off it made me even more intrigued by the game. Now I know this person was probably not even 15 kyu. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] 9x9 to 19x19 scaling strangeness
Quoting David Fotland [EMAIL PROTECTED]: Can you put crazystone back on 19x19 so I can see if it is just a fluke against fuego? I added locality to the light playouts - play near last or second to last move, and some code to handle long ladders in playouts. I dont think this is anything unusual. Both should help 19x19, but I dont know why 9x9 would be damaged. I have the same experience with Valkyria. For 9x9 all biases in the search is turned off. Apparently search on 9x9 is so efficient that introducing biases often cause inefficiencies. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] cgos 13x13 seems down
I will also run Valkyria on CGOS 13x13 over the weekend, (or long as things are stable). -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Bug in the Reivax
The program reivax on 9x9 CGOS seems to be strong but suffer from a bug leading it to pass too early, and thus it often loses games against weaker programs that do not resign. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] yet a mogo vs human game
Some months ago someone published a set of LD problems made for MCTS programs. Going through this I found a lot of serious bugs in Valkyria where overly aggressive pruning removed tesujis (tesuji = move that normally should be pruned). After that Valkyria improved perhaps 50-100 Elo. But I agree that finetuning on difficult problems may make the program weaker. It is like letting evolution run on Zoo animals for generations and then let them free in their natural environment. Not likely to be an improvement. So, I think test suits can be very helpful for finding serious bugs but thats it. Studying LD is good for human players but IMHO the strength gain do not come from solving LD situation better, it is because LD problems helps improving the ability to read in general. Or in other words studying LD improves the human search algorithm in general. -Magnus Quoting David Fotland [EMAIL PROTECTED]: The scary strong Rybka program claims to be weak tactically. The developers say that problem solving skill does not correlate strongly with playing strength and they don't tune or care about that. I've found the same thing for go. I have a large tactical problem set, and I use it for regressions, but I've found that spending much time tuning to solve problems can make the program weaker. There is not a strong correlation between problem solving and general go strength. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Counting the final score with seki
Quoting Jacques Basaldúa [EMAIL PROTECTED]: When you detect self atari in the playouts (something I haven't tried yet, but from recent posts in this group I am convinced that it is an important issue) a new problem arises: How can you score the board _fast_ at the end? Valkyria makes a simple loop that goes through each position on the board. Remaining stones are always counted as points. Stones in seki are alive and should be counted as usual so that is not different. The dames created by sekis have to be detected and differentiated from eyes. It is enough to just count the black and white stones in the 4 adjacent positions to see if it is an eye or a dame. There should be no dame that does not have *both* a black and white adjacent stone. Best Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rz-74 on CGOS ?
I looked at the last games played by rz-74, and it looks like a MC-program given how how it plays in the opening (odd moves in the center). I also doubt there are any traditional programs who can get 90% against gnugo on 19x19. Are there? But it seems to overplay badly in the opening in the last games against CS although I did not look carefully at it. One guess is that it is a MCTS version of gnugo, that may explain why its beats gnugo easily. -MP Quoting Don Dailey [EMAIL PROTECTED]: I was curious about that too, who is rz-74? The name is perhaps a clue. Is it at version 74?I haven't been watching the games, but are you saying it behaves like a Monte Carlo program? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: What's happening at the European Go Congress?
Here is my take on joseki and fuseki in computer programs. My older program Viking, had a quite nice patternmatching feature which matched the entire board or smaller parts of it towards a database of 50k games or so. It makes it play nice but as far as I could tell it had no impact on the strength of the program. With 9x9 I have used many systems learned or handmade, but it all boils down to that as been said earlier. It only works for a program that does not change, since it overfits its own strengths and weaknesses. -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Re: mogo beats pro!
Quoting Don Dailey [EMAIL PROTECTED]: Yes, UCT is easier to use with multiple CPU's because with additional processors alpha-beta programs do wasted work, unless you are talking about theoretical programs with perfect move ordering, which you aren't. Nice that all is clear about alpha-beta programs. But... does not UCT with additional processors waste a lot of simulations because what would be the optimal path through the search tree depends on the threads that have not finished yet? Some people reported that more processors helps a lot on large boards, whereas on smaller one there is not much gain. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
Quoting Hideki Kato [EMAIL PROTECTED]: Yes, UCT does. From my recent experiments with a delay line (a fixed size FIFO queue) between a UCTsearcher and an MC simulator with RAVE against GNU Go 3.7.11 level 0 on 9x9 (single thread): delay #po winsgames winning rateELO 1 sigma of wr 0 1,000 721 2,000 36.05% -99.6 1.07% 1 1,000 721 2,000 36.05% -99.6 1.07% 2 1,000 690 2,000 34.50% -111.4 1.06% 3 1,000 663 2,000 33.15% -121.8 1.05% 5 1,000 642 2,000 32.10% -130.1 1.04% 10 1,000 522 2,000 26.10% -180.8 0.98% 20 1,000 412 2,000 20.60% -234.4 0.90% 50 1,000 82 2,000 4.10% -547.6 0.44% If I understand this correctly this simulation for delay 50 computes 50 playouts and then updates the tree. In Valkyria I do the following. Every simulation from the root with their own thread updates all nodes as visited down the tree before entering the heavy playout. This means that all moves made in the tree are temporarily updated as losses. When a playout has finished, half of the moves were winners and updated accordingly. The idea behind this is that this hopefully avoids searching the same path over and over again. Have tried anything like this? Also your results shows clearly that there is inefficency. But do you also have results where for example delay 50 also computes 50x1000 simulations so that we can see if what it means in practise? Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: What's happening at the European Go Congress?
I think most programs developed by people who did not write old scool programs has serious problems with seki. Valkyria detects some basic seki shapes, but has problems with nakade/seki. -Magnus Quoting Erik van der Werf [EMAIL PROTECTED]: You're right, my reply was sloppy (it seems I'm too much used to Japanese rules). Also I should have read GCP's email more carefully; I did not realize that his program, even with a large tree, would not be able to recognize the seki. I knew of course that the original Mogo playouts had this problem, but I thought all strong programs had solved it by now... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Use tclkitsh-win32.upx.exe for Windows
I think I found the reason for my confusion. If I just run tclkit.exe cgosGtp.kit nothing happens but if I redirect stderr with tclkit.exe cgosGtp.kit 2log.txt I get the expected text in the logfile. But if I now do tclkit.exe cgosGtp.kit -s 2log.txt the parameter -s is ignored and I get the same result as the previous line had. But I found the solution. There are two different versions of tclkit for windows, and I needed to use the commandline version of course. Otherwise the handlings of stdin, stdout and stderr does not work properly. So use the file with sh in the name: tclkitsh-win32.upx.exe found at http://www.equi4.com/tclkit/download.html -Magnus Quoting Don Dailey [EMAIL PROTECTED]: Hi Magnus. I think I have a properly up to date client now. Below is a sample configuration file I am using for gnugo. You can run it with the appropriate cgosGtp.something for your platform. I use cgosGtp.kit and use the tcl runtime for my platform but you can use one of the binaries. Or you can use the pure tcl script if you have tcl installed. You can run cgosGtp -c config_file to make it happen. You can run it without any arguments to get usage instructions. You can make it give you a sample configuration file by doing cgosGtp.tcl -s You can have multiple sections and play different versions or different programs, it will take turns using the specified priorities. If you want 8 out of 10 games to be played with programA you would set priorities 8 and 2 for program A and program B respectively. Or you could set 80 and 20, etc.You can do 8 2 0 if you have 3 programs and you do not want to play one of them. # config file for playing gnugo # - %section server server cgos.boardspace.net port 6813 %section player name Gnugo-3.7.10-a1 password somePassword invokegnugo --mode gtp --score aftermath --capture-all-dead --chinese-rules --min-level 10 --max-level 10 --positional-superko priority 7 On Sun, 2008-08-03 at 00:26 +0200, Magnus Persson wrote: This reminds of that I have always used an ancient client to connect to the 9x9 go servers. The link for connecting to the 19x19 on http://cgos.boardspace.net/ is for an older clinet I think. So I would like to know how to connect using cgosgtp.tcl in windows with a configuraton file. I have .bat containing the single line tclkit cgosGtp.tcl -c config13.txt -k Quit.txt which leads to tcl popping up the error msg: This isn't a TK applicatinBad window path name config13.txt (The missing space and missing s in windows is as it is shown) Any hints are wellcome! Quoting Don Dailey [EMAIL PROTECTED]: Ok, the 13x13 server is up and running. Here are some temporary instructions that will probably be understandable for those with bots already running: Everything remains basically the same except the port and the location of the web pages. SIZE PORT - - 9x9 6867 13x136813 19x196819 (not up yet) The web pages are not linked yet from the main page. However the URL differs only in the initial directory path, it will be 9x9, 13x13 or 19x19 (when it's ready) and here is the main standings page for the 13x13 server as an example: http://cgos.boardspace.net/13x13/standings.html It would be nice to get a few bots on 13x13 to get it started off. The instructions for the viewers are on the main web page, but to refresh your memory here is how to view the 13x13 games: /home/drd/bin/cgosview.kit -server cgos.boardspace.net -port 6813 - Don ___ 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/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 13x13 server up and running
This reminds of that I have always used an ancient client to connect to the 9x9 go servers. The link for connecting to the 19x19 on http://cgos.boardspace.net/ is for an older clinet I think. So I would like to know how to connect using cgosgtp.tcl in windows with a configuraton file. I have .bat containing the single line tclkit cgosGtp.tcl -c config13.txt -k Quit.txt which leads to tcl popping up the error msg: This isn't a TK applicatinBad window path name config13.txt (The missing space and missing s in windows is as it is shown) Any hints are wellcome! Quoting Don Dailey [EMAIL PROTECTED]: Ok, the 13x13 server is up and running. Here are some temporary instructions that will probably be understandable for those with bots already running: Everything remains basically the same except the port and the location of the web pages. SIZE PORT - - 9x9 6867 13x136813 19x196819 (not up yet) The web pages are not linked yet from the main page. However the URL differs only in the initial directory path, it will be 9x9, 13x13 or 19x19 (when it's ready) and here is the main standings page for the 13x13 server as an example: http://cgos.boardspace.net/13x13/standings.html It would be nice to get a few bots on 13x13 to get it started off. The instructions for the viewers are on the main web page, but to refresh your memory here is how to view the 13x13 games: /home/drd/bin/cgosview.kit -server cgos.boardspace.net -port 6813 - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] What Do You Need Most?
I played on that temporary 7x7 server and I think the better programs came close at being almost unbeatable on 7x7 white and 9.5 komi especially if one uses the known opening library. So it might quickly get boring for most better programs. Although losses with white might reveal some serious bugs if one knows the program should win for sure. -Magnus Quoting Jason House [EMAIL PROTECTED]: On Jul 31, 2008, at 12:45 PM, Don Dailey [EMAIL PROTECTED] wrote: We put up a 7x7 site a while back and I thought it would get heavy traffic, but instead almost no interest. I don't remember ever hearing about it. I'd use it for faster testing. On Thu, 2008-07-31 at 12:39 -0400, Jason House wrote: On Jul 31, 2008, at 12:20 PM, Don Dailey [EMAIL PROTECTED] wrote: I am working on a plan to possibly be able to run 2 boardsizes on Dave Dyers boardspace site. If this plan works out, obviously 9x9 is very popular and we will keep it. The only questions is what should the other board size be. It is starting to appear than 19x19 is the second most popular for computer go. 7x7 is interesting to me for a few reasons: • It was solved by some dans a while back. This gives a perfect fuseki database and measurably correct and incorrect evaluations • 7x7 64, so bitboards could be extremely effective. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Operator needed
I also see myself listed in the EGC tournament(I made a half promise some time ago). I cannot go myself but fortunately Valkyria run in Windows, and I can setup an easy to use Zip file for any volunteer. On this topic: I would also want to ask if there is any volunteer with good hardware who would like to run Valkyria on CGOS. Unless I buy a new computer myself I currently have no access to fast machines. Preferable with 4 cores so that the scaling and stability of my thread implementation can be tested. I am running on a 4-year old 1.4 Ghz Pentium M, so it would be interesting to see the difference. Best Magnus -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CGOS 9x9 is down
Actually it is only the updating of the webpage that does not work. The programs play as usual. Quoting Urban Hafner [EMAIL PROTECTED]: Seems like it's down since the 29th. -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some beginner's questions concerning go bots
Quoting Carter Cheng [EMAIL PROTECTED]: 1) How typically do UCT bots score simulations quickly? I am not too familiar with Chinese scoring rules. In the end of a random games. There are only Black stones and Black Eyes, as well as White stones and eyes. If your playouts are smart enough there may also be points in seki. In that case at least one black and a white stone is adjascent to the point in seki which is simply not counted. If the playouts is even smarter it might avoid capturing some dead stones, but then you have to deal with that in counting. Although counting may be slower your random playouts become shorter so there may be a gain in efficency. Also some people stop the random playout prematurely after very large captures that makes it clear that one side has won the game. 2) How do machines define eyes analytically (mathematically) and are there approximations which are faster to calculate for more traditional or UCT designs (is this information even used for UCT bots?). Mathmatically speaking there are eyes that are not detected by 3x3 patterns. For example a living group can be made having the corners (1,1) and (19, 19) empty. If then all stones on the first line of the board has the same color then this is a live group. This violates 3x3 patterns because it does not matter if the (2,2) and (18,18) point belong to the opponent. But these types of eyes are so rare in real games that it can be ignored, and simply looking at 3x3 patterns are good enough to make a strong program. 3) What sort of algorithm is used to match patterns once you have mined them from some data source? If there is a general approach you probably want to take your pattern (whatever shape it has) and make a hash score of it and put it in a hash table. In the table you will store only those patterns that appear most frequently in games if you use large patterns. The best approach imho that is also well documented is that for Crazystone so go and check the papers at http://remi.coulom.free.fr/CrazyStone/ My program Valkyria rely completly on handwritten pattern recognition, basically using a decision tree which sometimes calls quick algorithms for tricky cases. This is a very time consuming approach for the programmer. 4) And lastly how does UCT cope with ladders? Valkyria reads ladders in the playouts. The ladder code is special because it can only read ladders and do not implement proper go rules. It also gives up if the ladders gets complicated. So it actually returns a) A stone can be captured for sure b) It does not know if it can be captured. This way the ladder code will be as fast as possible and still return a lot of helpful information. The ladder implementation uses a stack to record all changes to the board and then restores the board to the original state. This is because my board representation is too complex to use with the ladder code which must be super fast. The ladder information can be used to play better moves in the playouts, and bias the search in the UCT tree. Thanks in advance, Good luck! Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] The effect of the UCT-constant on Valkyria
I have already posted the following results. The results shows the winrates of Valkyria 3.2.0 against gnugo at default strength. 512 Simulations per move UCT_K Winrate SERR 0 58.82.1 (Winrate only) 0.0156.82.2 0.1 60.92.2 0.5 54.22.2 1 50.62.2 With 512 simulations there is not much work done in the tree. So I extend the test to 2048 simulations and also added the parameter value 2 to see what happens when search get really wide. 2048 Simulations per move UCT_K Winrate SERR 0 80.72.3 (Winrate only) 0.0183.32.2 0.1 83.72.1 0.5 77.32.4 1 71.33 2 62 4.9 The number of games are 300 for parameters 0 to 0.5 and a little less for parameter values 1 and 2 The results confirm that Valkyria still benefits from using confidence bounds with UCT, although the effect is really small. Also the effect of the constant might be a little greater with 2048 simulations rather than for 512. Still the curves look more or less the same. Does anyone have experience doing a test with different amounts of simulations where the best parameter value depend on the number of simulations? I prefer to use a low amount of simulations since it is simply faster, and also if the winrate of Valkyria gets to close to 100% it becomes harder to measure the effect of different parameter settings. Maybe I should quit testing against gnugo, and try something stronger. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] The effect of the UCT-constant on Valkyria
Quoting David Fotland [EMAIL PROTECTED]: So I'm curious then. With simple UCT (no rave, no priors, no progressive widening), many people said the best constant was about 0.45. What are the new concepts that let you avoid the constant? Is it RAVE, because the information gathered during the search lets you focus the search accurately without the UCT term? Many people have said that RAVE has no benefit for them. Yes, it is RAVE, and mor specifil as it was last presented here recently in the mailing list by the Mogo team, and not how it is was originally presented in the mogo paper. Also there may be several minor details that are peculiar to my implementation. Actually I did not understand some aspects of the Mogo method mailed here and just guessed some details. It suddenly worked and I could feel that the search was unusually strong and selective, and since then I just adjusted some parameters. I used to do progressive widening but that is now turned off. RAVE is free to pick any move that is not pruned right away. Currently I believe that RAVE is only effective if one gets other parameters right. For me it meant changing the uct parameter from 0.8 into 0.1. I also know of many pathological situations where Valkyria currently will not find the best move, but rather the second best. It is possible that other programs suffers even more than Valkyria from similar problems and that this to some extent has to do with that the nature of the playouts may interfere with AMAF. For example V either plays forced moves or uniformly random among moves that are not pruned. Other programs may rely on patterns to pick all moves in the playouts and this might be bad for AMAF (this is a wild speculation). Do most of the strongest programs use RAVE? I think from Crazystone's papers, that it does not use RAVE. Gnugomc does not use rave. You might not need it if you have strong pattern matching priors for the tree part similar to Crazystone. RAVE makes it possible to ignore most bad moves in a given positions. The weakness is that often some good (with a chance of being the best possible move) are also ignored completely. Is it the prior values from go knowledge, like opening books, reading tactics before the search etc? Do all of the top programs have opening books now? I know mogo does. Valkyria has just 4 moves in a hardcoded openingbook. Previous versions used a book with several 1000's of positions that was both self learned and modified by hand, but as long as the program changes the book tend become inaccurate, so right now I do not use it and is planning to write something more efficient than the old one which kept each position as file on the harddrive. Do most of the top programs read tactics before the search? I know Aya does. Valkyria only does some simple tactics in the playouts. It is stronger than anything I ever programmed (on 9x9 at least) so currently I cannot see how to integrate precomputed tactical results in the later search. I think Aya is special because it was very strong doing search before it went MC. Does it matter how prior values are used to guide the search? I think mogo uses prior knowledge to initialize the RAVE values. Do other programs include it some other way, by initializing the FPU value, or by initializing the UCT visits and confidence, or some extra, prior term in the equation? Right know Valkyria sets priors for AMAF so that moves that are a good local response to the last move have a prior 100% winrate with 20-100 visits depending on the priority of the triggered pattern. I think Mogo has a fixed number of visits for the priorities but modifies the winrate, but I never saw this described in a way that made it clear. Previously I biased the UCT values after everyting else was computed but found that this led to some bad behavior. By biasing the AMAF values these biases will get less influential as the true winrate has more weight than the AMAF-scores. Are there other techniques (not RAVE) that people are using to get information from the search to guide the move ordering? I think crazystone estimates ownership of each point and uses it to set prior values in some way. I used to do that long time ago in Viking (the precursor to Valkyria) that used alphabeta + MC-eval. As I remember it then it had a great impact on move ordering that was quite bad (or even nonexistent) for Viking. I have tried it in Valkyria but was never able to see an improvement. But I did not try hard enough to tell for sure. Both ownership and AMAF use the same information (playouts), so trying to use it twice is perhaps partially a waste of effort. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Test position set for MC programs
Quoting Michael Williams [EMAIL PROTECTED]: I'm curious what the winrate of the bug-fixed version is over the original version. The last version with bugs was Valkyria3.2.0 with 2216 Elo on CGOS, whereas the new version Valkyria3.2.1 currently has 2255. It is doing really well against MonteGnu and mogo-1core. But has problems against test-81725. A side note. Is it only me who are a little annoyed when strong programs play with names that are impossible(for examlple test-81725) to understand? Do not forget to add an entry on sensei at http://senseis.xmp.net/?ComputerGoServer whenever you play with a new program on CGOS, it is much more fun to know who is behind the programs and a short description of makes the program tick. I might run a test against gnugo soon as well but that may take sometime to finish. I do not expect these bugfixes to make a big increase in playing strength, since the kind of tactics involved mostly happens very late in very specifik positions on 9x9 and most games are won or lost earlier. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Greedy search vs UCT
I have checked if there is a difference for Valkyria in using confidence bounds or just greedily search the move with the highest winrate. This is Valkyria 3.2.0 using 512 simulations per move against GnuGo 3.7.10. UCT_K Winrate SERR 0 58.82.2 (greedy) 0.0156.82.2 0.1 60.92.2 0.5 54.22.2 1 50.62.2 As you can see up to uct_k = 0.1, the winrate aginst gnugo is more or less constant (500 games was played for each value of uct_k) and then it declines. So although 0.1 was best I cannot claim that it is better than a plain greedy search. I will repeat this using 4 times as many simulations per move. The search sensitivity to uct_k may depend on how deep the tree is searched. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Greedy search vs UCT
I run it with gnugo3.7.10.exe --mode gtp --chinese-rules --score aftermath --capture-all-dead --positional-superko Which is the default level which I do not know what it is. -Magnus Quoting David Fotland [EMAIL PROTECTED]: What level for gnugo 3.7.10? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Test position set for MC programs
I went through the problems with Valkyria. Right now it can do 32 out 50 where it had to think more than 10 seconds on perhaps 2 of those problems it solved. But I do recommend to go through these problems by hand. At least one position had the first move right but it seemed very week on the followup moves. And I found some bugs deeper in the tree. I guess 10 or so of these positions were not solved because of bug in the move generation. Valkyria prunes moves aggressively, and not surprisingly, tactical tesujis are pruned because normally those kinds of moves are not useful. So this problems set was very helpful to find several patterns that were wrong. I hope to fix these bugs and then I come back and report what it cannot solve and why it is hard to fix it. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Paper for AAAI
Quoting Olivier Teytaud [EMAIL PROTECTED]: Also, I've met people claiming that - they need a constant 0 for exploration; I use 0.1*Sqrt( ln(totvisits)/(5*Visits)); The 5 in the equations is there for historical reasons. But I think the advantage I get from a constant 0 is so small it is hard to measure. But it was some time I tested this and could not find the data. What was clear however is that performance goes down a lot when constant goes up to the levels valkyria used when I started workking on it. I think I should do I new test of this. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A problem with selectivity and AMAF bias
Quoting steve uurtamo [EMAIL PROTECTED]: magnus, I hate to ask the obvious, but how much time does each simulation take? If 100 simulations would be enough information to get it out of its rut, why not just check every legal move for (say) 100 simulations before doing anything else? My program is doing perhaps 2000 simulations per second in the endgame. Your suggestion would kill performance completely, since it would apply to all nodes in the tree. If there are 16 candidates moves in a node it would spend 1600 simulations just to search the root and one would get only 2-3 ply with normal thinking times, this simply almost reverts into simple MC eval without tree search. This is how my first MC program worked before UCT, it did alpha-beta search evaluating each move with a constant number of moves unless a cut was enabled early. Here is an example of how wonderfully selective the search is right now: After 500 simulations it has switched to the correct move 2 which is searched 292 times wheras as move 1 was searched 184 times. With my first fix the switch would take at least 2 seconds. The program was allowed to search for 15 seconds but stopped after 2.8 seconds because of superiority of the best move. Here is how the search tree looks like. Root: Move 1 is searched 6163 times WR=67%, move 2 575 times WR=48%, all 16 moves that were not pruned at move generations they were searched 2-14 times each. 1 ply 3568/1149/785/272/181/156/... and then 1-7 times 2 ply 2432/641/297/59/48/39/16/... and then 1-3 times 3 ply 1016/799/501/98/... and then 1-2 times 4 ply 766/166/25/16/... and then 1-5 times for each ply I listed the number of simulations spent on all candidate moves that got any attention. The principal variation is longer than this but my programs only prints those positions that have been searched above some threshold. Also the move ordering of this principal variations is very strong. As you can see the tree which is something like 16x15x14x13x12x... has been reduced to something like 2x3x3x2 which is higly selective. And the quality of moves are still excellent. This is of course only possible in the endgame, in the opening the width of the search is reduced from about 20-25 candidate moves to 3-7 moves. I probably still have some strong biases in AMAF in my program, and I guess there will be more positions whith bad behavior but from now on this will do it for me because as long as it does not locks into searching only one move the bias is probably mixed up and cannot become that extreme. But any ideas on how to remove bad bias from AMAF is wellcome. The only thing I do right now is that I only use the first 70% of the moves played in the simulations for AMAF, following the idea that moves at the end of each simulations probably is only noise anyway. -Magnus -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] A problem with selectivity and AMAF bias
Yesterday I noticed an odd phenomena in Valkyria wich was caused by high selectivity and AMAF. In this position (;GM[1]FF[4]SZ[9]AP[SmartGo:1.4] KM[7.5] ;B[ee];W[de];B[ed];W[df];B[ef];W[dd];B[dg];W[ge];B[dc];W[cc];B[cd];W[bd] ;B[cb];W[ce];B[bc];W[bb];B[cd];W[cg];B[cc];W[bf];B[gd];W[hd];B[hf];W[gc] ;B[gf];W[fd];B[fb];W[gb];B[fc];W[he];B[fe];W[ib];B[dh];W[ch];B[ad];W[be] ;B[di];W[ci];B[ha];W[ga];B[ie];W[id];B[if];W[fa];B[gd];W[hb];B[eg];W[eb] ;B[ec];W[da];B[ca];W[ae];B[ic]) there are only two possible moves 1) capturing the last black stone played or 2) capture the ko. Only capturing the ko wins. In this position valkyria will first search 1) because capturing the last stone is urgent. But the search locks into to that move only because there are a strong bias against move 2) in the AMAF evaluation for Valkyria. I guess what happens with AMAF is that alternative local moves (local relative to the first move in a repeated sequence) will always be biased downwards. This is so because playing the alternative local moves after the first one is played is often inefficient because of a duplication of effort. Then since there is nothing in the AMAF scores that indicate that move 2 is any good it is never searched, since the search is so selective that the bounds will not grow large to compensate for the bias in a reasonable time. I do not expect your programs to have the same problem in this particular position. But the problem could be general and I am curious if you have solutions for it if you do. I did implement a crude solution that works in this position and did not make Valkyria lose rating overnight. I added IF (#TotVisits 500) AND (#Visits 0.9*#TotVisits) THEN uctQ := 0.5*uctQ; before computing Q := beta*virQ + (1-beta)*uctQ; the effect of this is simply that as soon as a move has been played more than 90% of the time after at least 500 moves has been played in the position then other moves has to be played. This has to the drawback that the search gets slightly inefficient when it finds forced moves. One reason I have this problem may be that I bias the Q value towards local shapes after it has been computed. I should perhaps put weight on high priority patterns by adjusting the prior value of the AMAF instead. I realized this when I read the latest easy-to-read paper from the MOGO team and I will test that as well. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Paper for AAAI (David Silver) PDF problem
No, I can read it without problems on windows. Quoting Jacques Basaldúa [EMAIL PROTECTED]: and I still cannot read any mathematical expressions. I guess this applies to all Windows users. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Some ideas how to make strong heavy playouts
A recurrent concept popping up in discussions on how to improve playouts is balance. So I would like to try to share my philosophy behind the playouts of Valkyria and how I define balance and how it relates to the evaluation of go positions. *Background In an old school program the evaluation function would try to see which stones are safely connected to other stones of the same colours. Connected stones are called groups, and the program would probably also try to evaluate the safety of the groups looking at the eyespace at hand, weak neighbouring groups and so on. This quickly gets very commplicated. My old program Viking had several 1000's of handmade patterns for evaluating connectivity alone. This worked as a dream as long as the position consisted of patterns in the database... but in each an every game there were new situations and new patterns had to be added. A more robust method would be to use tactical search in the program to evaluate connectivity. The problem there is to ensure accuracy efficiently. Any tactical search tends to either become too time consuming, or resort to guessing. *MC-evaluation Programs using uniformly random MC-eval favors very solid but inefficient shape, often building blocks of adjascent stones in the center of the board. The reason is that if stones are played more loosely the stones often get cut off and get killed in the simulations. What we rather want is a program that can play efficent moves where stones are safely connected but occupy as much territory/eyespace as possible. The tree search (UCT) cannot alone solve this problem. Shapes created in a 19x19 game may exist untouched to the late endgame and it is not possible to read out all shapes on the board. It is much better if secure shapes stay stable in the simulation. They way I implemented that in Valkyria is that the playout part is basically reactive to random moves that attacks shapes on the board. It does not in any sense attempt to play the best move on the board. If it does not need to defend a shape it plays uniformly random somewhere. [Note that Valkyria also prunes really ugly moves, thus it plays uniformly the first move that is not pruned] This is also how the pattern system works in Mogo as I understand it. If I remember correctly I would say that all Mogo patterns are very basic and common sense defenses against attacks on otherwise stable shapes. But there also have to be balance. Valkyria also punishes bad shape. That is if a weak shape already is on the board, or a random move attacked two shapes simulatanously in the simulation, then the program may attack the weakness (or in a way it also reacts to the situation defending against the weak shape becoming stronger). Often the same move that would have been the proper defence is played. *Eliminating noise rather than predicting the best move Nothing I wrote above is original or new to the readers of this list. But I want to make a distinction between systems that tries to predict the best move and a system that only tries to eliminate noise from the otherwise very random simulations. Noise is eliminated when strong stones live and weak stones die almost always in the simulations. This way the random evaluations will mostly react to moves that matter in urgent fighting with shapes that are not yet stable. A MC-program that does this should stop defending and attacking strong shapes and would require much less simulations to discriminate between good and bad moves. Valkyria2 and Valkyria3 has slightly different tree search algorithms but uses the same playouts. Both versions needs only 512 playouts per move to win 50% against Gnugo 3.7.10. Still I think predicting the best moves is very important in the tree part, but this may be much less important in the playouts, and perhaps even detrimental as some people have experienced. *19x19 The best programs on 19x19 seems to focus the uct search on local fighting. This temporarilly overcomes the biases of the simulations locally. But the information gained locally about good shape in the tree is forgotten when the fighting moves elswhere. But this knowledge can then be rediscovered later if the fighting comes back. Could a future improvement to 19x19 go be to use locally narrow searches that seeds the playouts with strong patterns for the current shapes on the board? Maybe someone is already doing this? A really strong approach would be to eliminate the need of hard coded patterns or offline pattern harvesting and let the program learn during the game. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some ideas how to make strong heavy playouts
Quoting Don Dailey [EMAIL PROTECTED]: I have a response to this comment: Still I think predicting the best moves is very important in the tree part, but this may be much less important in the playouts, and perhaps even detrimental as some people have experienced. A class of bad moves is moves on the edge of the board when nothing else is nearby. In other words, the candidate edge placement doesn't touch any other stones of either color. In my experiments I found that it strengthens the program significantly to avoid trying these moves in the tree search (I call them veto patterns even though they are not necessarily veto'd permanently.) Sofar I have not tried removing those moves in the tree only. I need to try that. But I also discovered that there seems to be no benefit whatsoever in removing them from the play-outs.I have no real explanation for this. But it does tell me that the play-outs are very different in nature from the tree - you cannot just use the same algorithms for selection and prioritizing moves. My experience is that sometimes I get really bad interactions between special patterns in my playouts and plays on the first and second line. For example, if ladders are implemented then a move on the first line will be able to capture a contact move to the side of it. Thus I had situations where I think removing those moves made a positve difference, because the program liked those bad moves too much. But an alternative solution is also to prune bad moves, for example playing next to a stone of the first line allowing a ladder is perhaps even worse than the first move. So my program solves these kind of problems in a very adhoc multiple ways so it is hard to tell if my eperineces and your experiences here are universal or just specific to certain programs as a whole. Still I recently had the idea that perhaps AMAF works best if in all moves are played because then each move played in the playouts are tested under a larger variety of situations. But I do not remember now if I tested it properly. What I did do recently was to stop pruning moves in the trees and allowed all legal moves. This dropped the winrate of 1500 playouts vs gnugo with 10%, it seemed to have a lot of temporary hallucinations early in search where a lot of really bad moves were searched perhaps 50-200 times before finding more decent moves to search. I planned to make a version that make some soft pruning allowing them to be searched later so that tree will have full width near the root and be strongly pruned below. I would be happy if I could do that and keep the playing strength becuase then my program would at least in principle be able to play perfectly. Right now the pruning is to aggressive for that to be true. I think I like your theory that eliminating noise is a good thing and probably the primary thing. Your last comment is what I am interested in the most, and what I have spent quite some time looking at. I call it learning on the fly. The use of patterns is acceptable in this setting if those patterns are learned during the game. The basic important observation is that most of the things learned during the game is relearned over and over and over and over All-moves-as-first is a form of this learning, but very brittle of course. And I don't have a problem with imposing knowledge from the outside if it's used only as a kick start - a way to overcome the initial learning inertia, but not imposed in any absolute way. I agree also here but I have no really good practical ideas, just loose feeling on what it should be like. But every time I try to think in more concrete terms I never get anywhere... -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimal explore rates for plain UCT
Quoting Petr Baudis [EMAIL PROTECTED]: Please note that pachi1 had a rather embarassing bug of starting the random playouts with wrong color (so if the last tree node was black, the playout would start with black as well). pachi2 has this bug fixed; the ELO rating is still not settled, but so far it seems that the impact of this has been about 20-30 ELO in the 110k playouts area, which seems surprisingly little to me. It just shows that MC evaluation is robust, and this is because it is relative between moves and not an absolute evaluation. As long as the same bug applies to all moves it should not be that important. If the playouts are light i guess it matters even less. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] solving the nakade problem
Quoting Ivan Dubois [EMAIL PROTECTED]: Hello, I think there is a very easy and straigthforward solution to the nakade/seki problem, here it is : For moves that are self-atari on a group that contains MORE than 5 stones : Both in the tree and the playouts, strictly forbid them (exactly like you forbid filling an eye). (This is to handle seki and have efficient playouts). For moves that are self-atari on a group that contains LESS than 5 stones : Allow them both in the tree and the playouts. In the playouts, they should be played with a low probability. But they should be played when there is no other move left. (This is to ensure groups with are dead with nakade are eventualy captured in some playouts). What do you think about this solution ? I will probably implement it in Zoe to see if it efficient, unless someone finds a flaw in the logic. Valkyria has a lot of logic about what self-ataris should be allowed or not, and the size of group is part of that. I see two possible flaws in playing the remaining moves self ataris with low probability. a) In some cases the group under attack will appear as alive because the nakade is always always captured in a way that creates a second eye. Just playing all moves with low probability does not mean that the right move is played. Also correct nakade handling means that some moves has to be played immediately as response to a liberty filling move from the other player. b) You also have the problem of seki. Many nakade problems includes seki as a possibility in the search tree. And there are some common seki patterns involving just a few stones, so in some cases the probability of playing a move should be zero even with few stones. I think the program need to either: 1) Implement proper logic for picking the correct moves 2) Learn from its mistakes, maybe hash every suicidal situation in the playouts played and store statistics. But of course there are always room for any quick and dirty heuristics which actually improves the playing strength. It does not have to be perfect to work well. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimal explore rates for plain UCT
Quoting Don Dailey [EMAIL PROTECTED]: When the child nodes are allocated, they are done all at once with this code - where cc is the number of fully legal child nodes: In valkyria3 I have supernodes that contains an array of moveinfo for all possible moves. In the moveinfo I also store win/visits and end position ownership statistics so my data structures are memory intensive. As a consequence I expand each move individually, and my threshold seems to be best at 7-10 visits in test against Gnugo. 40 visits could be possible but at 100 there is a major loss in playing strength. Valkyria3 is also superselective using my implementation of mixing AMAF with UCT as the mogo team recently described. The UCT constant is 0.01 (outside of the square root). When it comes to parameters please remember that they may not have independent effects on the playing strength. If one parameter is changed a lot then the best value for other parameters may also change. And what makes things worse is probably that best parameters change as a function of the playouts. I believe that ideally the better the MC-eval is the more selective one can expand the tree for example. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimal explore rates for plain UCT
Quoting Jonas Kahn [EMAIL PROTECTED]: On Tue, Mar 11, 2008 at 09:05:01AM +0100, Magnus Persson wrote: Quoting Don Dailey [EMAIL PROTECTED]: When the child nodes are allocated, they are done all at once with this code - where cc is the number of fully legal child nodes: In valkyria3 I have supernodes that contains an array of moveinfo for all possible moves. In the moveinfo I also store win/visits and end position ownership statistics so my data structures are memory intensive. As a consequence I expand each move individually, and my threshold seems to be best at 7-10 visits in test against Gnugo. 40 visits could be possible but at 100 there is a major loss in playing strength. Valkyria3 is also superselective using my implementation of mixing AMAF with UCT as the mogo team recently described. The UCT constant is 0.01 (outside of the square root). When it comes to parameters please remember that they may not have independent effects on the playing strength. If one parameter is changed a lot then the best value for other parameters may also change. And what makes things worse is probably that best parameters change as a function of the playouts. I believe that ideally the better the MC-eval is the more selective one can expand the tree for example. Typically, how many parameters do you have to tune ? Real or two-level ? I guess I have 10 real valued and 10 binary ones. There are probably a lot of stuff that are ahrd coded and could be parameterized. Here I am also completely ignoring playouts that have hundreds of handtuned parameters. If you consider a yet reasonable subset of parameters, an efficient way to estimate them is to use fractional factorial design for the linear part, and central composite design for quadratic part (once you know you are already in the right area). You are much more precise than with change-one-at-a-time strategies if there is no interaction between parameters, and you can detect interactions. I once met this guy: http://meche.mit.edu/people/faculty/index.html?id=27 his research is a mix of testing formal methods and how well they work in practice and also studying how engineers (who often do not use these methods) actually do in practice. He seemed to argue that doing parameter optimization intuitively by hand is not as bad as one might think compared to fractional factorial design. So I use that as an excuse for just doing it as I always did. For me it is important to keep a careful record of what I do and plot the result with confidence intervals to avoid tricking myself. Alternatively, especially with a very high number of real parameters, derivatives of MC techniques can be efficient and easy to implement: particle filtering or swarm optimization in particular. That would be tempting (I once implemented a fitting method inspired by simulating annealing and it was very efficient) but it would require a completely different test setup than the one I use right now. It also a matter of time and patience. I want new results every day. If I would test all parameters at once using formal methods I would still have to wait for weeks. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
Attached is an sgf-game of a long kofight on 9x9 between Valkyria and Gnugo. Valkyria of course wins with 0.5 otherwise it would probably not have been such a nice example of a long kofight. -Magnus kofight318392.sgf Description: application/go-sgf ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Should 9x9 komi be 8.0 ?]
Quoting Mark Boon [EMAIL PROTECTED]: On 3-mrt-08, at 18:43, Don Dailey wrote: I base that logic on my observations that once the score goes below 10% for Lazarus, it is losing. It's extremely rare that it salvages a game once the score goes below even 20%. In which case I could argue that attempts at winning by playing 'silly' moves are not working either. It hardly seems like an argument supporting your position. It may in fact make things worse. This is a feeling I get when I see MC programs play, as soon as one falls behind the loss is made irreversible by some extremely silly moves. But this is more the case early in the game, not by the end of the game. The behavior of Valkyria as I see it is that it actually plays patiently up to the point where it knows for sure it has lost. When this happens it actually plays moves that makes the game as long as possible. These moves may look completely crazy, sometime it is just odd forcing moves. Against weaker programs this works quite often, and against stronger programs of course rarely. Often when I investigate bad moves in the endgame, it is clear that normal moves would had simplified the game and end in a clear loss. In those situations Valkyria should have started playing crazy even earlier. Also my impression is that MC-programs always plays better moves to a human eye if it searches deeper even in lost positions. It might still be crazy moves but better crazy moves. For me it feels like a waste of time experimenting with playing style in the end of the game of lost positions. At least it comes really low on my priority list. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Should 9x9 komi be 8.0 ?]
Quoting Don Dailey [EMAIL PROTECTED]: Just to make it clear, the case we want to fix is the case where many bots are programmed to resign. Lazarus will resign when the score is below 1% (and has remained so for a couple of moves in a row which is probably just a superstition on my part to delay it.) Valkyria is an aggressive resigner and does so below 10% already, and I have no memory of it resigning in a position where it was meaningful to play on. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
Quoting steve uurtamo [EMAIL PROTECTED]: cool. do you have any examples from a 19x19 game? that's what i was referring to when i said that i've never seen an MC player play out a ko fight. Valkyria is unfortunately way to weak for 19x19. My argument is more that in principle MC programs plays ko fights perfectly but not in complex positions,and most 19x19 games are complex. Actually one of my happiest moments of go programming was then my first MC-program played several kothreats in a 13x13 game. This surprised me because nothing in my program would motivate it to do so and I thought the search necessary to read it out was way beyond its capability but it was not. Then I realized that I no longer had to come up with some smart programming for ko and just could focus on other things. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
