Re: [Computer-go] Alphago and solving Go
Except 361! (~10^768) couldn't plausibly be an estimate of the number of legal positions, since ignoring the rules in that case gives the trivial upper bound of 3^361 (~10^172). More likely it is a very, very bad attempt at estimating the number of games. Even with the extremely unsharp bound given in https://tromp.github.io/go/gostate.pdf 10^(10^48) < number of games < 10^(10^171) the 361! estimate comes nowhere close to that interval. /Gunnar On 08/07/2017 04:14 AM, David Doshay wrote: Yes, that zeroth order number (the one you get to without any thinking about how the game’s rules affect the calculation) is outdated since early last year when this result gave us the exact number of legal board positions: https://tromp.github.io/go/legal.html So, a complete game tree for 19x19 Go would contain about 2.08 * 10^170 unique nodes (see the paper for all 171 digits) but some number of duplicates of those nodes for the different paths to each legal position. In an unfortunate bit of timing, it seems that many people missed this result because of the Alpha Go news. Cheers, David G Doshay ddos...@mac.com <mailto:ddos...@mac.com> On 6, Aug 2017, at 3:17 PM, Gunnar Farnebäck <gun...@lysator.liu.se <mailto:gun...@lysator.liu.se>> wrote: On 08/06/2017 04:39 PM, Vincent Richard wrote: No, simply because there are way to many possibilities in the game, roughly (19x19)! Can we lay this particular number to rest? Not that "possibilities in the game" is very well defined (what does it even mean?) but the number of permutations of 19x19 points has no meaningful connection to the game of go at all, not even "roughly". /Gunnar ___ Computer-go mailing list Computer-go@computer-go.org <mailto:Computer-go@computer-go.org> http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Alphago and solving Go
On 08/06/2017 04:39 PM, Vincent Richard wrote: No, simply because there are way to many possibilities in the game, roughly (19x19)! Can we lay this particular number to rest? Not that "possibilities in the game" is very well defined (what does it even mean?) but the number of permutations of 19x19 points has no meaningful connection to the game of go at all, not even "roughly". /Gunnar ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [computer-go] Interesting endgame case
Petr Baudis wrote: 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 I don't see how J3 works, black still can win the ko, can't he? J3 - H4 - G4 - F4 - J6 Here's your mistake, don't exchange G4-F4. To begin with white can save G4 for use as a ko threat but in this case that is also wrong. By keeping G4 and F4 open white has enough outer liberties so that black only gets a single ko threat in the lower left (E1). now they play the ko: H9 - J9 - J5 black takes A4 - A5 - J6 white takes F1 - J2 - J5 black takes A2 - A1 - J6 white takes E1 - G1 - J5 black takes and white has no threats. I admit I didn't see F1 immediately and went at E1 right away, maybe that's the hard part for the bots? With two outer liberties F1 can be ignored. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Mirror Go against Zen
Ingo Althöfer wrote: Alain Baeckeroot wrote: gnugo --mirror will try to play mirror go :) How does it do this? In the simplest possible way. If there is a legal move obtaining mirror symmetry it will play it, otherwise revert to normal move generation. It does not worry about komi, nor about tactical disasters. As you may guess this was primarily implemented in order to test the anti-mirror-go strategies in GNU Go. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
Isaac Deutsch wrote: I'm about to implement this. Since I have multiple features (patterns, is in atari, is adjacent to last play, etc.), the weight is the product of the weight of all matching features. I'm thinking about having a table of weights, storing the sum of each row and the total (like Rémi suggested). I want to do this incrementally, so if I find a new feature match in a position, I can multiply its weight by the feature's weight. If I remove a feature, I can divide. My question/problem: How do I deal with features that have a weight of zero? I'm sure there are certain 3x3 patterns that have the weight zero, such as ### #*. #.. with * to be played. It's clear that when this pattern matches, the total weight is set to zero. How do I find the resulting weight when removing this pattern, though? Since I can't divide by zero, I would have to reconstruct the weight by checking all features, which would be relatively slow. Is there a way this can be avoided, such as setting all weights to a very low value instead of zero? Cache what features you have, then recomputing the weight will be fast. GNU Go incrementally keeps track of the following features: Black suicide (true/false) White suicide (true/false) Black self-atari (true/false) White self-atari (true/false) Number of stones captured by black move (0, 1, 2, 3+) Number of stones captured by white move (0, 1, 2, 3+) Color to the southeast (empty, white, black, off board) Color to the northeast (empty, white, black, off board) Color to the northwest (empty, white, black, off board) Color to the southwest (empty, white, black, off board) Color to the east (empty, white, black, off board) Color to the north (empty, white, black, off board) Color to the west (empty, white, black, off board) Color to the south (empty, white, black, off board) This information is stored in 24 bits of an integer. The 16 bits related to the local 3x3 pattern are mapped by table lookup to the 1107 rotation/mirroring invariant patterns. The remaining 8 bits are mapped to the following features: Opponent suicide (1 bit) Our self-atari (1 bit) Opponent self-atari (1 bit) Our captures (2 bits) Opponent captures (2 bits) by simple bit transposition depending on color to play. Additionally nearness to the previous move is added as a feature giving 1107*256 combinations, which are finally mapped to pattern weight by table lookup. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go + code + environment
Joshua Shriver wrote: Perhaps I'm mistaken in my reading, but isn't Mogo a clusterized and highly tuned version of gnugo? Things like that made me want to make this post. As I find the Go programming community more open to sharing ideas and code than my chess world counter part. You are mistaken. You may have mixed things up with SlugGo, which at least at some time could be loosely described as a clusterized GNU Go, although I don't believe highly tuned fits. I don't know what the current status of SlugGo is. MoGo is based on entirely other ideas than classical GNU Go and it's rather MoGo that has inspired the newer parts of the GNU Go algorithms than the other way round. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
Łukasz Lew wrote: ... For a reference you can take a look for a libego implementation: Ah, so you already use this idea in libego? libego uses this idea only for list of stones in chain. list of liberties are not implemented. but I guess I will implement it sometime soon. You can find this idea in the GNU Go montecarlo board implementation, although with doubly linked lists, see for example http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c starting at line 43. This code is doing quite a lot of book-keeping to support tunable pattern-based heavy playouts, however, so it may be easier to start with a previous iteration of the code at http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c?id=67cc097ed8c7e326d3b1659ca668326e23f65c3b /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
Łukasz Lew wrote: 2009/4/8 Gunnar Farnebäck gun...@lysator.liu.se: Łukasz Lew wrote: ... For a reference you can take a look for a libego implementation: Ah, so you already use this idea in libego? libego uses this idea only for list of stones in chain. list of liberties are not implemented. but I guess I will implement it sometime soon. You can find this idea in the GNU Go montecarlo board implementation, although with doubly linked lists, see for example http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c starting at line 43. This code is doing quite a lot of book-keeping to support tunable pattern-based heavy playouts, however, so it may be easier to start with a previous iteration of the code at http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c?id=67cc097ed8c7e326d3b1659ca668326e23f65c3b Indeed that's almost exactly what I meant. I can see that you are using doubly linked list to have a constant time liberty_edge removal. Is there any other reason? To be honest I don't really remember but that was probably the most important reason. Another possibility is that I became annoyed by the look of the code needed to traverse around a single linked cyclic list. :-) Have you considered amortized constant time (we remove it when we have an occasion) approach? No, not seriously at least. Actually this code hasn't been optimized at all, so there should be some gains left to be made. Lukasz PS This is nice code to read :) Thanks. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: static evaluators for tree search
Dave Dyer wrote: If you look at GnuGo or some other available program, I'm pretty sure you'll find a line of code where the evaluator is called, and you could replace it, but you'll find it's connected to a pile of spaghetti. That would have to be some other available program. GNU Go doesn't have a static position evaluator and consequently no line of code calling it. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GPGPU
Mark Boon wrote: I don't know if that's what you're already looking at, but recently Apple announced their new version of OS X called 'Snow Leopard' which supposedly focuses mostly on improvements in the use of multiple processing. And that includes the GPU. The module that binds it all together is called 'Grand Central'. I don't know much of the details, just picked up some buzz-words from articles like these: http://gizmodo.com/5017615/giz-explains-mac-os-106-snow-leopard-parallel-processing-and-gpu-computing If you google around a bit you may easily find more information about it. The most relevant part for GPU programming is OpenCL, which is expected to have about the same expressive power as nvidia's CUDA. But it won't change the processing and communication characteristics of the GPU. You still need to come up with some really clever vectorization tricks yourself, if you want to make good use of the GPU for go algorithms. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] regression testing
Mark Boon wrote: Yes, I asked that question. So GnuGo already uses a comment-node to store the information in the SGF tree. But twogtp uses information from the .tst file. So why the difference? No, GNU Go does not put the tests in the sgf files. We did so for a short while long ago, but it wasn't manageable. Instead we started to write tests as GTP commands (which was one of the reasons for introducing GTP in the first place) and soon also to include the correct answers as GTP comments in .tst files. This format has served us well. For those who need more context it can look like this, from endgame.tst: # E5 is two points gote, J3 one point sente, and J2 three points gote. # J2 wins the game by 0.5, all other moves lose. loadsgf games/endgame14.sgf 1000 reg_genmove black #? [J2] The first two lines are comments about the test, the third line loads the position, the fourth line specifies the test, and the fifth line is a specially formatted comment defining the correct answer. There may also be multiple correct answers like in this test: # See also 9x9:250. loadsgf games/nngs/evand-gnugo-3.5.2gf1-200312161910.sgf 52 207 attack A6 #? [3 (B4|C4|C1)]* This is a tactical reading test which is expected to give the result code 3 (win by ko where the attacker must make the first ko threat) for either of the moves B4, C4, and C1. There is also an asterisk at the end indicating that this test is expected to fail. Tests can also be more complex like this: # See also connection:119. loadsgf games/kgs/llk-GNU.sgf 150 trymove W N10 trymove B M10 trymove W M9 trymove B L10 trymove W M11 trymove B L14 219 defend K12 #? [1 M14]* popgo popgo popgo popgo popgo popgo This is derived from a failed connection test where it turns out that the problem is a tactical misreading starting six moves deep in the connection reading, which is set up with the six trymove commands and cleared up with the corresponding popgo commands. There are a number of reasons why it's useful to separate the test definitions from the sgf files. I'll list a few of them: 1. When working in a distributed group you need a succinct way of referring to specific tests, such as endgame:1000 for the first example above (the test numbered 1000 in the file endgame.tst). Talking about the fifth test at move number 150 in the file games/kgs/11k-GNU.sgf is way too inconvenient. Short names are also good in status reports like http://trac.gnugo.org/gnugo/wiki/RegressionResults or http://trac.gnugo.org/gnugo/ticket/199 (click one of the details links) 2. The marks for expected failures need to be updated periodically (e.g. at the time of a release) when the state changes and it's nicer to have your revision control showing repeated changes in a few tens of tst files than in thousands of sgf files. Yes, you really want to keep track of the expected status. For the record GNU Go 3.7.12 contains 86 tst files with a total of 5445 tests from 1760 sgf files. 3. It's practical to be able to say run the tests in semeai.tst for a quick sanity check of a change to the semeai reading. Btw, the sgf file with a test defined in a comment, that Terry dug up, was kindly contributed by Tristan Cazenave in a collection of test cases from his Golois program. That sgf comment has never been used by GNU Go. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Publishing source for (yet another) MC simulator
Don Dailey wrote: On Tue, 2008-11-04 at 07:43 +0100, Heikki Levanto wrote: My personal preference might be C, but at work I have to learn more Java... Anyway, I don't want to start a language war here, not again... Oh, you want a war :-) Seriously, Java has it's place but if you really get serious about developing the highest performance strong playing bot I think you pretty much are forced into a low level language. I see only a very few reasonable choices if you want to go that way: C or C++ Assembly D If you look for performance you can hardly discount Fortran. Actually there's a fair chance that the majority of the world's Monte Carlo programs are written in that language. Anecdote: My very first experience of games programming was in Fortran. As an intern I was given the assignment to update one of the last, and not exactly business critical, pieces of a large power distribution surveillance product (think lots of power plants and nationwide distribution networks) in a migration from one operating system to another. This was the operator's console distraction, an othello program written in a pre-Fortran77 version of Fortran, littered with arithmetic if statements. I had absolutely no clue (neither had anyone else) how the program worked until I had line by line translated it into C and unravelled the code structure into sensible (logical) if statements and while loops. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The Enemy's Key Point Is My Own
David Doshay wrote: One nasty form of The Enemy's Key Point Is My Own was the reverse monkey jump, where SlugGo would properly recognize that the opponent's best move against it was a monkey jump, and properly see that stopping that monkey jump was the best move, but it would then play the same exact point the opponent would have, thus playing way too far inside its own area. So, as I said in my earlier post, near is the right idea, not at the same point. There are other easy examples involving them extending towards our stones, where we should not take their extension as our move, but we should prevent their extension my moving into that area farther from our own stones than they would have approached. An extreme case is this life and death problem where playing the opponent's key point is the worst you can do locally. |O. |O. |.O.XOO |.XOX.O +-- /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] From zero to playing on CGOS in 10 minutes
Mark Boon wrote: I'm getting close to something I'd like to show people and get feedback. One thing to decide is how to make it public. Previously I used dev.java.net to host my project. But I stopped using it because I had a very slow internet connection and I was getting annoyed with the time it took to communicate with Subversion on the remote host. At the moment I have a bit more decent internet connection, but it's still not fast. Nor reliable. So ideally I'd like to keep the stuff in my local repository. Like a two-step process. I can store versions locally and when I want I can migrate or merge it with the one online. I know ClearCase is ideal for this kind of settup. But too expensive and I doubt there's an online service that supports it. Does anyone know if something like this is possible to setup with Subversion? anyone having experience with something like this? Subversion 1.4 can do repository replication (see heading svnsync at http://subversion.tigris.org/svn_1.4_releasenotes.html), which should work for a one-way mirroring. There's also svk, http://svk.bestpractical.com, which adds distributed version control on top of subversion. But I really agree with the people recommending git or mercurial. I haven't used mercurial myself yet but I have very positive experience with git. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GUI GTP Engine (not Controller)?
gogui-display does exactly what you want. /Gunnar Ross Werner wrote: Hi all, I'm looking for a very simple GUI GTP engine--not a controller. Programs like Jago or GoGUI are great GTP controllers--they can connect to a GTP engine like GnuGo and play against it just fine. What I'm looking for is a program that *cannot* directly attach to GnuGo, but instead requires a third controller program (like twogtp) to connect the two clients together. Does that make sense? Thanks in advance, ~ Ross p.s. preferably it would be Java or at least cross-platform. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go/Games with modified scores
Claus Reinke wrote: Just out of curiosity, what did you expect from the playouts? Nothing in particular, really; at this point I'm just trying to build up an intuition about what I can or cannot expect from them. At first, I thought light playouts would not fully explore, but at least randomly cover all possible games, so we wouldn't get good move sequences directly, but lots of useful statistics to work with; while heavy playouts would try to mimick more realistic games, so the statistics would be biased, but there'd be a better chance of getting good moves directly. That turned out to be somewhat naive on all counts, as the answers to my earlier messages showed!-) There is no chance of covering all possible games, That's a major understatement! The number of all possible games is really enormously huge. so uniformly random play (light playouts) definitely ignores some, and if realistic games are unlikely, and good move sequences even more so, then they get the least coverage. So, in the presence of limited resources, no bias is a bias on its own. Uniform simulations are badly biased but I wouldn't say it has anything to do with coverage. And the way eyes and other rules knowledge are encoded for efficiency reasons introduces other biases as well. Eye rules are not primarily there for efficiency reasons but to save information about the original position from dissipating completely. Heavy playouts never drop possible sequences, Heavy playouts may or may not drop some moves completely, depending on the design. they just try to focus the available resources away from sequences that appear less promising. That can have unpredictable effects, so the unpromising sequences are kept in the pool, at low priority, and the resulting focussed playouts need heavy testing to get some measure of confidence in any improvements. No, heavy playouts are not about finding promising sequences. The purpose is to get simulations that more often let living groups stay alive, let dead groups stay dead, let solid territory remain territory, and so on, so that the score of the final position correlates reasonably well with the value of the initial position. That's why uniform simulations are badly biased; solidly connected stones almost always win against more loosely connected but perfectly sound formations, causing the program to play very heavy and inefficiently. In sum, there doesn't seem to be a good basis for understanding playouts and their optimisation, other than by trial and error. [...] Some things are possible to understand, such as the often play close to the previous move idea resulting in fewer tenukis and therefore fewer opportunities for solidly living groups to die, or for hopelessly dead groups to spring alive. If this is not obvious I would recommend playing a number of games against a uniform random player with some 40-50 handicap stones on 9x9. But as far as fine tuning of playouts go I would say it's pretty much black magic. Actually that's true for everything but the most rudimentary principles. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go/Games with modified scores
Darren Cook wrote: What do your program's playouts think when presented with the board position in the article? This is a terminal position, both players have passed, a comfortable white win, yet pure random playouts think black will win more often. http://dcook.org/compgo/article_the_problem_with_random_playouts.html Any chance to get an sgf of the position? /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go/Games with modified scores
Claus Reinke wrote: Second, having now looked at some more random light playouts (just instrument your engine to output sgf before starting the next run), I feel that the name is highly misleading. These simulation runs have very little in common with actual play, eg, in a 19x19 run from an empty board, one might see an opening period, with 200 moves of randomly placed stones, followed by a middle period, with 100 or so moves occasionally making a firm connection or a true single-space eye, followed by an endgame with 100-200 moves exploring possible consequences of those little bits of random mess that cannot be ruined by random play. Just out of curiosity, what did you expect from the playouts? /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 7.5-komi for 9x9 in Beijing
Don Dailey wrote: On Wed, 2008-10-08 at 15:18 +0200, Erik van der Werf wrote: On Fri, Oct 3, 2008 at 2:33 PM, Don Dailey [EMAIL PROTECTED] wrote: I had heard somewhere that there are some who believe 8.0 is the right komi for 9x9 Chinese. I personally believed for a long time it was 7.0 based on statistical data of games.However that can be misleading. Do you understand why even numbers are very unlikely? Yes, I understand that. I compiled from CGOS statistics all possible results and their frequency. Here is a list of white results where the actual games end with a score. You will notice that even scores are much more common.There were just a few games that used 6.5 komi because when I first started CGOS I had set 6.5 by mistake but I think that was just for a few hours at most. The vast majority of these are 7.5 komi games: 391140.5 14881.5 209502.5 7013.5 ... I suspect that quite a few of the odd scores are not due to the presence of seki with an odd number of neutral points but are caused by uncaptured dead stones. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Another 6x6 analysis.
At http://trac.gnugo.org/6x6.sgf you can find an ongoing analysis of 6x6. This is a very big and quite raw sgf file where each node has a comment block looking like this: 0 -2.5: 0 4 black -0.5: 5 9 black 1.5: 9 10 black 3.5: 9 34 white 5.5: 38 20 white 7.5: 22 7 white 9.5: 6 0 white B3 4b47e72a68d23f011 + B4 4b47e72a68d23f011 + [...] F5 00f9e9a88c0120581 F6 01f9ba0f1b5c68e11 PASS 1 The first line is the id of the position in the form of a symmetry invariant 64-bit Zobrist board hash, written in hexadecimal, concatenated with the move number. Following are the results for different komi values. Listed on each line is komi value, number of observed white wins, number of observed black wins, and minimax winner. Last comes a list of moves and id of the obtained positions. If the id is followed by a plus sign it means that move has been played and can be found as a child node. If it is followed by a minus sign the move has been played but gives a transposition of a a position that has been expanded elsewhere in the tree. The example above is from the root node and means that correct komi currently is supposed to be between 1.5 and 3.5 (i.e. 2 or possibly, but unlikely, 3). This may very well have changed by the time you download the sgf. So far this analysis has only been done by GNU Go, with and without the --monte-carlo option. I would like other, stronger programs to join in. To do that, just point your regular cgos client to trac.gnugo.org, port 6867. This is of an experimental nature and hopefully works for more people than me. Don't worry about user names and passwords, those are not used for anything yet, just fill in something. Time controls are not used and the server will always report five minutes remaining time. Interrupted games are lost forever, but that's not really a problem. If you know how to play manually on cgos, feel free to do so here. Btw, programs are not playing against each other, but against the server following supposedly winning lines, falling back on GNU Go when it finds an unseen position. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Another 6x6 analysis.
A couple of hours. /Gunnar Michael Williams wrote: Very cool. How long has this been going on? Gunnar Farnebäck wrote: At http://trac.gnugo.org/6x6.sgf you can find an ongoing analysis of 6x6. This is a very big and quite raw sgf file where each node has a comment block looking like this: 0 -2.5: 0 4 black -0.5: 5 9 black 1.5: 9 10 black 3.5: 9 34 white 5.5: 38 20 white 7.5: 22 7 white 9.5: 6 0 white B3 4b47e72a68d23f011 + B4 4b47e72a68d23f011 + [...] F5 00f9e9a88c0120581 F6 01f9ba0f1b5c68e11 PASS 1 The first line is the id of the position in the form of a symmetry invariant 64-bit Zobrist board hash, written in hexadecimal, concatenated with the move number. Following are the results for different komi values. Listed on each line is komi value, number of observed white wins, number of observed black wins, and minimax winner. Last comes a list of moves and id of the obtained positions. If the id is followed by a plus sign it means that move has been played and can be found as a child node. If it is followed by a minus sign the move has been played but gives a transposition of a a position that has been expanded elsewhere in the tree. The example above is from the root node and means that correct komi currently is supposed to be between 1.5 and 3.5 (i.e. 2 or possibly, but unlikely, 3). This may very well have changed by the time you download the sgf. So far this analysis has only been done by GNU Go, with and without the --monte-carlo option. I would like other, stronger programs to join in. To do that, just point your regular cgos client to trac.gnugo.org, port 6867. This is of an experimental nature and hopefully works for more people than me. Don't worry about user names and passwords, those are not used for anything yet, just fill in something. Time controls are not used and the server will always report five minutes remaining time. Interrupted games are lost forever, but that's not really a problem. If you know how to play manually on cgos, feel free to do so here. Btw, programs are not playing against each other, but against the server following supposedly winning lines, falling back on GNU Go when it finds an unseen position. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Another 6x6 analysis.
Markus Enzenberger wrote: Gunnar Farnebäck wrote: To do that, just point your regular cgos client to trac.gnugo.org, port 6867. what rules does GNU Go use in the 6x6 analysis? Uh, whatever I happened to remember to set it to. :-) In this case that would be area scoring, no suicide, simple ko, three passes to end the game, scoring performed by GNU Go (unless there's a resignation). I connected Fuego configured with CGOS rules. After a while it terminated, because Fuego returned an error response to a play command with a move that violated the positional superko rule. (By default, Fuego does not accept illegal moves to avoid that configuration errors in experiments go by unnoticed.) Did you notice whether there was something interesting about that position? Anyway, I'll let it run like this for a while. I can restart it later with some superko rule in effect. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] semeai
terry mcintyre wrote: On Thu, 2008-09-04 at 18:07 +0200, Rémi Coulom wrote: When the playouts evaluate a critical semeai the wrong way, then no supercomputer can help, even at long time control. Semeais require a better algorithm, because no computing power can search them out with a tree, and playouts have to be extremely intelligent in order to evaluate them correctly. Has anyone tried implementing the ideas in Richard Hunter's Counting Liberties in a manner which can be used to guide the playouts? Static analysis is hopeless. Local search may work with some level of precision but you will have to read much further ahead than in Richard Hunter's model positions before you can even reliably recognize them. In particular I wouldn't advise trying to cancel outside liberties without playing out the moves in some order, otherwise detecting the need for approach moves is extremely difficult. GNU Go makes an attempt at reading semeais but has trouble already differentiating between outside liberties, inside liberties, and eyespace, not to speak about weird interactions with the tactical reading (which mostly doesn't understand semeai) in low liberty situations. If you think this should be simple, have a look at e.g. page 53, diagram 17, in Hunter's book or try to do a static evaluation of the semeai in upper left corner at http://trac.gnugo.org/regression/regress.plx?nngs2:150 Things to think about for the latter position: * How big eye does black have around F19? * What can white do around E9? * How to handle white sacrificing the C11 tail? * Is there a liberty to be gained by playing A14? * Does white need an approach move at M18? * Does black need an approach move at B10? * What is A16? Eyespace, some other kind of liberty, or neither? For some more semeai fun I can recommend http://trac.gnugo.org/regression/regress.plx?semeai:133 (which has an incorrect solution in GNU Go's test suite). /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] yesterday's KGS bot tournament
Nick Wedd wrote: My report is at http://www.weddslist.com/kgs/past/41/index.html In the round 10 game between AyaMC and CrazyStone, the marked H8 move has no effect on life and death; the white stones are already dead. The killing move was 27 at E9. As far as I can tell white couldn't afford to save the group with 26 at E9 either. The lower left would have lived but too small, ending in a 1.5 point loss or so. :-) /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] yesterday's KGS bot tournament
Nick Wedd wrote: My report is at http://www.weddslist.com/kgs/past/41/index.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] yesterday's KGS bot tournament
Nick Wedd wrote: My report is at http://www.weddslist.com/kgs/past/41/index.html [Please ignore the previous empty mail.] In round 9, MonteGNU appeared to misread a ladder in its game against CrazyStone. SGF. But maybe it knew it had no way to win. Yes, it was the usual Monte Carlo nonsense in hopeless positions. MonteGNU tries to cut some of that short by reverting to traditional GNU Go move generation, but not until the Monte Carlo search is sufficiently certain about the hopelessness. /Gunnar ___ 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 ?
Rémi Coulom wrote: Don Dailey wrote: 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? - Don After watching more games, I am less impressed by its strength. It is definitely a Monte-Carlo program (constant thinking time per move, weird moves in the opening, hopeless tricks when losing). Maybe Monte GNU, after all. I'm flattered by the guess that MonteGNU would be playing strongish at 19x19 but so far I'm happy if it manages to even place the stones on the intersections and not somewhere between. Oh well, maybe it can do a little better than that but compared to the strong programs it feels that much behind. /Gunnar ___ 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?
Erik van der Werf wrote: For the final position in the game record any strong human player will tell you that the game is clearly over. No points are left to be gained and the result is obvious. Actually there's one point left to gain in the seki, since the game is played with Chinese rules. ;-) /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] cgos 19x19 has no anchor
Don Dailey wrote: Hi Markus, Run gnugo 3.7.10 using these exact options: ./gnugo --mode gtp --score aftermath --capture-all-dead --chinese-rules --min-level 10 --max-level 10 --positional-superko This should work fine but you might as well remove --score aftermath. It has no effect at all in combination with --mode gtp. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Strange problem while connecting to CGOS
Thomas Lavergne wrote:
Hi,
I will have very few free time until end of this year to work on my go
program, so I have decided to cleanup the code and release it in free
software sooner that what I've wanted.
So after some work I'e obtained a version of goober with light
Monte-Carlo, hash-tree exploration with UCT for planing and some
optimisations like AMAF, benson-life and opening book.
There is still missing things like time handling instead of fixed
iteration and seki detection, but it works and before releasing it I've
wanted to retest it on CGOS 9x9 and 13x13.
So I've downloaded last client and made config files for the 2 version
and run them. All works ok and players go in the waiting queue. But when
the game start, the engine ask my program to play, wait for response,
and when it get it, it stop saying my program have crashed.
This is the output of the client :
[...]
14:54:10S-C username
14:54:10C-S Goober-0.6.0-25k-1
14:54:10S-C password
14:54:10C-S Hy13yn
15:02:07S-C setup 553666 9 7.5 30 Goober-0.6.0-25k-1(1200?)
AverageLib(545)
15:02:07C-E boardsize 9
15:02:07E-C =
15:02:07C-E clear_board
15:02:07E-C =
15:02:07C-E komi 7.5
15:02:07E-C =
15:02:10S-C play b H5 30
15:02:10C-E play b H5
15:02:10E-C =
15:02:10S-C genmove w 30
15:02:10C-E genmove w
15:02:10E-C =c5
15:02:10Apparently, engine crashed
But there is no sign of crash in my engine, all goes like if the cgos
client have interrupt my engine. If I restart the client, it replay this
start, send correctly the move made by my oponent but re-ask my engine
to think about the move already send, like if the client have discarded
the previous response.
I've checked my GTP code and all seems ok, when I use gogui to play
against it or gogui tools to make tests, all works ok.
I have no time for the moment to investigate this more but does anyone
of you have encoutered this type of strange things with cgos client ?
Thanks
Tom
PS: The code is not fully ready to be realeased but if some of you want
to take a look at it, you can download the current version at :
http://oniros.org/goober.c
It's only 2000 lines of code with 25% of comments.
Try the attached patch.
/Gunnar
--- goober.c.old 2008-08-06 15:54:39.0 +0200
+++ goober.c 2008-08-06 15:54:51.0 +0200
@@ -1645,9 +1645,10 @@
static void ge_send(const char *msg, ...) {
va_list args;
if (ge_status == false) {
+ putchar('=');
if (ge_id != -1)
printf(%d, ge_id);
- putchar('=');
+ putchar(' ');
ge_status = true;
}
va_start(args, msg);
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT again
Peter Drake wrote: On Aug 1, 2008, at 8:08 AM, Mark Boon wrote: The neighbours of the last move come in the picture because usually it's only the last stone played that can be escaping a ladder and it's the neighbours of the last move that could have been put into atari. Nothing to do with the additional complexities Don mentioned. Let me give a specific example. Suppose that, during a playout, the tree leads us to this position, with O to play: *.* *...OO* *..O##a...* *...Ob* *c* *.* *.* *.* *.* Having reached the frontier of the tree, we now finish the game using Monte Carlo with a ladder reader. The last stone played, to the left of a, is trapped in a ladder, but can escape if not chased. Our ladder reader therefore suggests O play at a. For the next move in the playout, if # only reads ladders from the last move played, it will see that the O stone at a is not in a ladder, so move is suggested. The playout now turns completely random, and it's a coin toss as to whether the group will escape. It's often a good idea to bias capturing moves in the playouts, regardless whether it's a ladder or not. This would result in those stones being captured in most simulations. If we also search stones next to the last stone played, things only get slightly better. # sees that its stones are in a ladder from which they cannot escape, so it doesn't suggest b. If we tell it to play a ladder breaker in such situations, it might play c, which is fine. However, on O's next turn, c is not in a ladder, nor is any stone next to c, so no move is suggested. Specifically, O does not make the vital capture at b. It seems too expensive to search every point on the board for ladders. What to do? Don't bother with ladder breakers in playouts. If the tree part of the search has started to run a ladder, the best thing the playout can do is to keep running it until the bitter end. This way the losing player in the ladder will be rightfully punished and discouraged from trying that line of play. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] question about a situation
Norbert Gábor Papp wrote: Thanks for your reply! I've tried to make the links workable... Hi! Here is a situation, from phase1-phase5 (I hope you'll se the pictures). Phase1 http://kepfeltoltes.hu/view/080529/phase1_www.kepfeltoltes.hu_.jpg Phase2 http://kepfeltoltes.hu/view/080529/phase2_www.kepfeltoltes.hu_.jpg Phase3 http://kepfeltoltes.hu/view/080529/phase3_www.kepfeltoltes.hu_.jpg Phase4 http://kepfeltoltes.hu/view/080529/phase4_www.kepfeltoltes.hu_.jpg Phase5 http://kepfeltoltes.hu/view/080529/phase5_www.kepfeltoltes.hu_.jpg I've used SmartGo, which engine is based on GNUGo, and tried to make some very beginner examples. No, SmartGo is not based on GNU Go. Also GNU Go has no difficulty getting the life and death status correct in those positions. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
I wrote:
Hideki Kato wrote:
Gunnar Farnebäck: [EMAIL PROTECTED]:
Hideki Kato wrote:
I didn't against you, Álvaro, rather I just made a caution for
programmers who will use your pseudo code as is. :)
First, I prefer SFMT (SIMD-oriented Fast Mersenne Twister) rather
than integer pseudo random number generators in practice where the
quality of play-out is important. Modern processors execute floating
operations as fast as interger ones and
picked = mt_rand() * (double) num_candidates;
is the simplest and safe.
Please note that for uniformity purists this method has exactly the
same problem as good_quality_int_rand() % num_candidates.
Mt_rand() has very good uniform distributions in [0..1)
while
good_quality_int_rand() % num_candidates
doesn't disribute uniformly when num_candidates is not a power of 2,
assuming good_quality_int_rand() ranges [0..2^32 or so) due to modulo
operations. They are not the same, aren't they?
Well, there's nothing magic about floating point numbers. Even a very
good uniform distribution in some interval is implemented by
distributing N discrete values over the interval as uniformly as
possible. When those N values by some mapping procedure are transformed
into a smaller range M, some of those will get at least one more hit
than some others, unless M divides N. It doesn't matter whether the
mapping procedure is an integer modulo operation or a floating point
multiplication + rounding.
It seems like this short explanation was too abstract. Let's try with
a more concrete one.
The function dsfmt_genrand_close1_open2 in the file dSFMT.h from
dSFMT-src-1.3, downloadable from
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html,
generates uniformly distributed double precision floating point
numbers in the interval 1 = x 2. This is done by taking uniformly
distributed 52 bit integers and placing those as the least significant
bits of a 64 bit IEEE 754 double precision floating point number with
the bit pattern
0 011 y,
where y denotes the 52 bits uniformly distributed integer. This is
interpreted as the floating point number with value
x = 1 + y / 2^52
The function dsfmt_genrand_close_open generates uniformly distributed
double precision floating point numbers in the interval 0 = x 1
simply by subtracting one from the numbers above. These are still
exactly representable by IEEE754 double precision floating point
numbers although their bit representations become somewhat more
involved due precisely to the point floating around.
Thus we now have the uniform integer distribution 0, ..., 2^52-1
mapped onto the floating point numbers 0, 1*2^(-52), 2*2^(-52), ...,
(2^52-1)*2^(-52).
Next we multiply this by num_candidates and round down to the nearest
integer. Let's say that num_candidates is 7. Then the 52 bit integers
are mapped onto the interval 0, 1, 2, 3, 4, 5, 6 so that
0 - 643371375338642 are mapped to 0
643371375338643 - 1286742750677284 are mapped to 1
1286742750677285 - 1930114126015926 are mapped to 2
1930114126015927 - 2573485501354569 are mapped to 3
2573485501354570 - 3216856876693211 are mapped to 4
3216856876693212 - 3860228252031853 are mapped to 5
3860228252031854 - 4503599627370495 are mapped to 6
This means that moves 0, 3 have a relative chance of 643371375338643
to be chosen whereas moves 1, 2, 4, 5, 6 have a relative chance of
only 643371375338642. Of course this is for almost any purpose
negligible but it is exactly the same bias you get by taking a
uniformly distributed 52-bit integer modulo 7, except that then it's
the moves 0 and 1 that are favored instead of 0 and 3.
Well, that's what naive theoretical computations give at least, but
it's usually dangerous to trust intuition too much when dealing with
floating point numbers. Actually trying this out with the attached
program gives the following result on my computer,
0 0.00 0
643371375338642 0.142857 0
643371375338643 0.142857 1
1286742750677284 0.285714 1
1286742750677285 0.285714 2
1930114126015926 0.428571 2
1930114126015927 0.428571 3
2573485501354568 0.571429 3
2573485501354569 0.571429 4
2573485501354570 0.571429 4
3216856876693211 0.714286 4
3216856876693212 0.714286 5
3860228252031853 0.857143 5
3860228252031854 0.857143 6
4503599627370495 1.00 6
showing that 2573485501354569 maps to 4 rather than 3, meaning that
it's moves 0 and 4 which are favored.
I could go on but I think this should be enough to demonstrate my
point.
/Gunnar
#include stdio.h
int main(int argc, char **argv)
{
unsigned long u;
double x;
int k;
unsigned long v[] = {
0ul,
643371375338642ul,
643371375338643ul,
1286742750677284ul,
1286742750677285ul,
1930114126015926ul,
1930114126015927ul,
2573485501354568ul,
2573485501354569ul,
2573485501354570ul,
3216856876693211ul,
3216856876693212ul,
3860228252031853ul,
3860228252031854ul,
4503599627370495ul};
for (k = 0; k (int) (sizeof
Re: [computer-go] 10k UCT bots
Hideki Kato wrote: I didn't against you, Álvaro, rather I just made a caution for programmers who will use your pseudo code as is. :) First, I prefer SFMT (SIMD-oriented Fast Mersenne Twister) rather than integer pseudo random number generators in practice where the quality of play-out is important. Modern processors execute floating operations as fast as interger ones and picked = mt_rand() * (double) num_candidates; is the simplest and safe. Please note that for uniformity purists this method has exactly the same problem as good_quality_int_rand() % num_candidates. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] a few more questions
Álvaro Begué wrote: On Tue, May 13, 2008 at 8:10 PM, Weston Markham [EMAIL PROTECTED] wrote: On Tue, May 13, 2008 at 7:08 PM, Gunnar Farnebäck [EMAIL PROTECTED] wrote: And I agree, don't even think of doing this with floating point numbers. This is a bit tangential to computer go. But you have piqued my curiosity Offhand, that sounds rather extreme to me. Perhaps I haven't really thought this through completely, but it seems as if there is a simple modification to the stated algorithm, that would ensure that it works fine with floating point numbers. Or at least well enough for any conceivable purpose: Make sure that you select each random number from a slightly larger range than prescribed by the exact totals. (For example, always round up while calculating the totals. If you do not have control over the rounding mode, just add on some small fraction of the largest weight.) Then, in the event that subtracting the weights of the points/rows/buckets never reduced the selected number to a non-positive value, just select a new random number and start over. Would this work fine, or is there some flaw in my thinking that Álvaro and Gunnar have already considered? John Tromp and I spent quite a bit of time patching the floating-point implementation and hunting down the subsequent bugs. I am not saying that making it robust is impossible, but I ended up so frustrated that I don't think I will ever try again. Integers are much better behaved and are sufficient for everything we wanted to do. I did the same, until I decided that it was utterly pointless. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] a few more questions
Álvaro Begué wrote: On Tue, May 13, 2008 at 4:22 PM, Carter Cheng [EMAIL PROTECTED] wrote: 2) When generating random variables for the case where the values of placing a stone on different points on the board are different. Are there good ways to throw and determine which point has been selected for the next move by the random player? I can answer this. The best way I know of getting a random point with different weights (proportional to probabilities) for each point is to keep a sum of weights per row and a total sum of weights for the entire board. These are easy to update dynamically when an individual weight changes. In order to pick a point, start with a random number between 0 and the total sum. Go down row by row subtracting the weight of each row, until you would get a negative number. Then walk the row subtracting the weight of each point until you would get a negative number. The place where you stop is the selected point. This method may not be very robust if you use floating-point numbers to represent weights (because you can't rely on associativity of addition), but it works fine if you use an integer type. If the description is not good enough, I can write some C++ code for you. Or you can read the source code of GNU Go 3.7.12, lines 1629-1658 of engine/montecarlo.c. The only difference is that GNU Go doesn't bother about actual rows but instead makes a two level structure where it uses the N lowest bits of the board coordinate to determine a partition number. N varies from 1 to 4 depending on the maximum board size GNU Go is compiled for (3 for 9x9, 4 for 19x19). And I agree, don't even think of doing this with floating point numbers. /Gunnar ___ 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
David Fotland wrote: 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? Whatever concepts are used it must indirectly be a question of improved move ordering. The better the move ordering, the smaller the need to do exploration. 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. 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. I've never had success with RAVE but I might make a new attempt for GNU Go some time. 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. The MonteGNU account on CGOS (9x9) has a self-learnt opening book with currently slightly more than 16000 moves. Over the last 1000 games it has played on average 4 moves (own moves that is, opponent moves not counted) from the book. The record is 22 moves from book. Do most of the top programs read tactics before the search? I know Aya does. GNU Go in Monte Carlo mode reads lots of tactics before the MC search. But it doesn't use the tactics for the MC search. :-/ 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? 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. GNU Go uses a global move ordering shared by all nodes in the tree and initialized from the results of the normal move generation. /Gunnar ___ 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
David Fotland wrote: Another alternate move. On problem 108 it seems that a2 works, although it looks inferior. A2, a3, g1, h1, a4, and if white cuts at b4, black captures and white has no ko threats. If white doesn’t answer at h1, black can live in the corner and white can’t live on the left. Gunnar, does this look correct? Yes, and I get the same score as with A3, so it's not even inferior, only more complicated. With the given komi it's also possible to play A2, A3, A4 directly without the G1, H1 exchange but this is inferior in points. /Gunnar ___ 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
David Fotland wrote: on problem 101, Many Faces likes A4, which I think also works, but I didn't have time to check it thoroughly. If A4 doesn't work, then Many Faces is back to 37. A4 doesn't work. White plays E1 and is safe. Black G1 is answered by J3. /Gunnar ___ 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
Yamato wrote: Thanks Gian-Carlo, Gunnar. Current list of results. GNU Go 3.7.12 level 0 : 24/50 GNU Go 3.7.12 level 10 : 34/50 GNU Go 3.7.12 level 15 : 37/50 GNU Go 3.7.12 mc, 1k : 30/50 GNU Go 3.7.12 mc, 10k : 31/50 GNU Go 3.7.12 mc, 100k : 38/50 GNU Go 3.7.12 mc, light, 1k: 33/50 GNU Go 3.7.12 mc, light, 10k : 30/50 GNU Go 3.7.12 mc, light, 100k : 25/50 GNU Go 3.7.12 mc, mogo, 1k : 34/50 GNU Go 3.7.12 mc, mogo, 10k: 33/50 GNU Go 3.7.12 mc, mogo, 100k : 35/50 Leela 0.3.14, 1k : 19/50 Leela 0.3.14, 10k : 28/50 Leela 0.3.14, 100k : 36/50 Zen 1.5, 1k: 19/50 Zen 1.5, 10k : 22/50 Zen 1.5, 100k : 24/50 Leela seems to have good scalability. 36/50 passes is fine. The results of GNU Go are a bit irregular because of its hybrid strategy. If GNU Go could run on the MC only mode, it might be more interesting, I guess. Ok, I patched out the contributions from normal move generation in the final move selection (but there's still some influence on UCT tree move ordering), giving this list: Only MC GNU Go 3.7.12 level 0 : 24/50- GNU Go 3.7.12 level 10 : 34/50- GNU Go 3.7.12 level 15 : 37/50- GNU Go 3.7.12 mc, 1k : 30/50 14/50 GNU Go 3.7.12 mc, 10k : 31/50 29/50 GNU Go 3.7.12 mc, 100k : 38/50 35/50 GNU Go 3.7.12 mc, light, 1k: 33/507/50 GNU Go 3.7.12 mc, light, 10k : 30/50 14/50 GNU Go 3.7.12 mc, light, 100k : 25/50 22/50 GNU Go 3.7.12 mc, mogo, 1k : 34/50 14/50 GNU Go 3.7.12 mc, mogo, 10k: 33/50 21/50 GNU Go 3.7.12 mc, mogo, 100k : 35/50 34/50 /Gunnar ___ 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
Yamato wrote: Gunnar Farnebäck wrote: 143: I don't see how A3 could win the semeai. A2 and C4 look more effective. Typo, it was A2. C4 cannot work. How does white defend against C4? I'm looking at B C4, W B4, B B5, W B6, B A2 without finding a way out for white. Did I miss something? Oh, I see... I quoted this problem from a book, but it did not mention C4. If C4 works, it is not a good test, then I modify it a little. I attached the fixed version to this email. Thanks for your help. One more correction. The fixed version added B1 as a correct move in 113, but that point is occupied. GNU Go 3.7.12 results for the fixed version: GNU Go 3.7.12 level 0 : 24/50 GNU Go 3.7.12 level 10 : 34/50 GNU Go 3.7.12 level 15 : 37/50 GNU Go 3.7.12 mc, 1k : 30/50 GNU Go 3.7.12 mc, 10k : 31/50 GNU Go 3.7.12 mc, 100k : 38/50 GNU Go 3.7.12 mc, light, 1k: 33/50 GNU Go 3.7.12 mc, light, 10k : 30/50 GNU Go 3.7.12 mc, light, 100k : 25/50 GNU Go 3.7.12 mc, mogo, 1k : 34/50 GNU Go 3.7.12 mc, mogo, 10k: 33/50 GNU Go 3.7.12 mc, mogo, 100k : 35/50 /Gunnar ___ 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
Don Dailey wrote: Go problems don't work for MC programs unless you can arrange them so that finding the right move wins, and anything else loses. I found you can modify some problems by manipulating the komi to make this true. You can manipulate komi to turn any unfinished position into a win/lose testcase. It might not have a unique solution but that's not required for a testcase to be useful. The difficulty is of course to find the proper komi so that the minimum number of moves are winning moves, and to find which those moves are. If you can do that you will in most cases get an interesting testcase. /Gunnar ___ 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
Yamato wrote: Hi all. I'd like to share my test set for MC programs. This is a gnugo-style regression test file. To use it, you need to implement 2 GTP commands, loadsgf and reg_genmove. Then, run your program like this: gnugo --mode gtp mctest.tst | awk -f regress.awk tst=mctest.tst This set contains 50 problems. They are relatively easy to human players and perhaps classic Go programs, but hard to MC programs. Here are my results. Zen-1.5 (1k playouts): 15/50 Zen-1.5 (10k playouts) : 20/50 Zen-1.5 (100k playouts) : 22/50 gnugo-3.7.10 (Level 0) : 22/50 gnugo-3.7.10 (Level 10) : 32/50 I want to know the results of other programs. Please post here. GNU Go 3.7.12 level 0 : 21/50 GNU Go 3.7.12 level 10: 32/50 GNU Go 3.7.12 mc, 1k (*1) : 28/50 GNU Go 3.7.12 mc, 10k (*2): 28/50 GNU Go 3.7.12 mc, 100k (*3) : 35/50 GNU Go 3.7.12 mc, light, 1k (*4) : 30/50 GNU Go 3.7.12 mc, light, 10k (*5) : 27/50 GNU Go 3.7.12 mc, light, 100k (*6): 22/50 GNU Go 3.7.12 mc, mogo, 1k (*7) : 32/50 GNU Go 3.7.12 mc, mogo, 10k (*8) : 28/50 GNU Go 3.7.12 mc, mogo, 100k (*9) : 30/50 (*1) gnugo --monte-carlo --mc-games-per-level 100 (*2) gnugo --monte-carlo --mc-games-per-level 1000 (*3) gnugo --monte-carlo --mc-games-per-level 1 (*4) gnugo --monte-carlo --mc-patterns uniform --mc-games-per-level 100 (*5) gnugo --monte-carlo --mc-patterns uniform --mc-games-per-level 1000 (*6) gnugo --monte-carlo --mc-patterns uniform --mc-games-per-level 1 (*7) gnugo --monte-carlo --mc-patterns mogo_classic --mc-games-per-level 100 (*8) gnugo --monte-carlo --mc-patterns mogo_classic --mc-games-per-level 1000 (*9) gnugo --monte-carlo --mc-patterns mogo_classic --mc-games-per-level 1 --mc-patterns uniform is uniform distribution except for filling eyes, i.e. so called light playouts. --mc-patterns mogo_classic is an approximation of the simulation policy from the report Modification of UCT with Patterns in Monte-Carlo Go by the MoGo team. The reason why light playouts do better with 1k simulations than 100k simulations is that the --monte-carlo move generation is a hybrid between UCT search and normal move generation and with few simulations, especially light playouts, the influence of normal move generation (in this case at default level 10) tends to be stronger. /Gunnar ___ 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
Yamato wrote: Don Dailey wrote: Go problems don't work for MC programs unless you can arrange them so that finding the right move wins, and anything else loses. I found you can modify some problems by manipulating the komi to make this true. I intend to have adjusted all of them like that (only 1 move = win). Do you mean you found some problems are wrong? 108: If I'm not mistaken A3 and G1 both give B+3.5 whereas A2 gives B+1.5 so komi could be 9.5 but there would still be two solutions. 113: Black can also start with E8 and still have sufficient ko threats. 125: B1 also kills. 128: D2 kills, not C2. 130: D2 becomes more complicated but looks good enough to win with komi 7.5. 131: It looks like B4 wins by 3.5 and D1 by 1.5 so komi should be 9.5 to give a unique winning move. 139: C2 and B1 also live. 143: I don't see how A3 could win the semeai. A2 and C4 look more effective. 148: D1 also wins? /Gunnar ___ 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
Yamato wrote: Gunnar Farnebäck wrote: 130: D2 becomes more complicated but looks good enough to win with komi 7.5. I don't see why D2 works. After E2, can black live? You're right. I was busy counting how much damage white could do on the right with various moves cutting the threatened connection and quickly forgot about the shortage of liberties that stopped the other 1-2 point from working in the first place... 139: C2 and B1 also live. Yes, but will not win with komi 7.5. Fair enough. 143: I don't see how A3 could win the semeai. A2 and C4 look more effective. Typo, it was A2. C4 cannot work. How does white defend against C4? I'm looking at B C4, W B4, B B5, W B6, B A2 without finding a way out for white. Did I miss something? /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching
Mark Boon wrote: Lately I have been putting some effort into pattern-matching. Although I have made progress, the result was not as good as what I had hoped for by about an order of magnitude. This makes me wonder what is currently actually the state of the art of pattern matching in Go. Of course it's a bit of a vague question, as there are many possible forms of pattern-matching. Fixed-size patterns are the easiest since a hash-code can be used. Nothing is going to beat that in terms of speed, but its use is limited to some special occasions. Joseki is one and apparently 3x3 patterns are used in Monte-Carlo programs. But I think the most generally useful form is one that can do pattern-matching for variable shapes. (Or which can have don't-care points if you like.) I thought I had a solution that would be pretty close to the theoretical best performance. Formally proving that would probably be a dissertation in itself, most important for me is in itself it works and with modest memory requirements. That is the good part. The bad part is, if I'm right this is the best it can get I'm a bit disappointed it isn't faster. I'd rather be proven wrong here. It's written in Java so making it in C would possibly give a two-fold speedup, but that's all I can think of. What I have now takes 10-15 microseconds on a 2Ghz Intel computer to find all the patterns on a board (on average for 9x9, for 19x19 it's more like 15-20 usec) and it also gives me the 'new' patterns i.e. patterns that match now but didn't match the previous move (I believe that's a useful feature, but it's a detail). The set of patterns is under a thousand patterns. Somehow smaller sets don't go much faster, but larger sets do slow down, every ten-fold increase in number of patterns seems to double the time. So I was wondering if others cared to share the performance of their pattern-matcher. I just want to find out if I'm chasing a unicorn or not by trying to make something faster. I tried this with GNU Go and got about 40-80 usec on 9x9 for a database of 500 patterns with in some cases lots of wildcards (black or empty, white or empty, black or white or empty (but not off board)). This was on a 2.2 GHz AMD64. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 9x9
Olivier Teytaud wrote: We have removed most of the openings, because they have been generated before we modify the behavior of mogo in front of Nakade, and the mogo with new nakade-behavior seemingly does not like the openings generated before the nakade-improvement. I guess a very strong improvement will come easily, just by restarting the complete (long and boring) process of generating opening books. Hey, are you going to stop playing games like http://cgos.boardspace.net/9x9/SGF/2008/03/25/364672.sgf ? MonteGNU had learned that sequence and played from book all the way up to move 31. How is MonteGNU now supposed to be able to win any games against MoGo? ;-) /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More statistics and conclusions from CGOS data
Christoph Birk wrote: On Thu, 14 Feb 2008, Gunnar Farnebäck wrote: Interesting. If I do the same with MonteGNU's fuseki database, which is based on online learning from own CGOS games, and cut off at 200 samples I get: E5 8101 | C3 2950 | | G5 1798 | | | G3 1145 (A) And the results (win/loss %) ? Due to the way the learning is done and because wins against weaker opponents are excluded, the win/loss statistics don't mean anything and are in fact close to 50% for most popular moves. Look at the numbers above as indications of how often the corresponding move historically has seemed like a good idea to play for the fuseki algorithm. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] gpugo
Florian Erhardt wrote: Hello ! My name is Florian Erhardt, I am a bachelor student of computer sciences and am in the process of optimizing libEGO for gpgpu. For now I implemented the SFMT (even I can do copy and paste) on the gpu and am now atomizing the MC to be done by the gpu. If everything works as I planned it, I'll have a releasable program in a few months (I still have to learn lots about parallelizing, gpu programming and programming in general [maybe leaning about genetic algorithms can't hurt either - The RAVE algorithm is more like a genetic algorithm - Right ?] - and I have to go to university :-) ). For now I'm using a MC-engine with UCT, trying out how much patterns and other things might make the results better. Now as I understand it, using patterns, groupstatus, ... during the MC-playout makes the results from the playout more meaningful (stronger - 30k instead of random), so if I would make the playout with a small engine (the easiest way to use the power of the gpu) the result should be more meaningful too. Has anyone done any test like that (like use gnugo level 0 instead of an MC-playout) ? Does anyone have a minimalistic non-MC go engine I could look at ? One more thing - has anyone tried using quasi-MC for go ? I don't want to discourage you but this doesn't match my experience of GPGPU from other applications, nor my experience of MC go. First, using GNU Go level 0 for playouts is pointless. It's too slow and deterministic for an MC approach and too slow and weak for a non-MC approach. Second, as other people have pointed out, the strength of individual playouts does not have a strong connection with the strength of an UCT program. I would go as far as to conjecture that it's entirely irrelevant. (Patterns are indeed useful but for other reasons than playout strength.) Third, if you want to get any kind of speed from the GPU you must go massively parallel. Think in terms of a big texture filled by lots of go boards side by side and try to operate on all of them simultaneously in a reasonably uniform manner. Forget everything about group status and other complicated concepts. If you can just implement an UCT engine with uniformly random playouts on the GPU and get significantly better performance than on CPU it's a major achievement in my book. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More statistics and conclusions from CGOS data
Don Dailey wrote: Here is the entire tree, where I drop nodes if they have less than 500 samples. These are games between 1700+ players who are within 100 ELO of each others rating. E5 49.1% 19630 | C4 49.6% 5894 | | C5 49.9% 1558 | | | B5 54.7% 788 | | | | C6 48.4% 566 | | C6 51.3% 1106 | | D4 53.5% 737 | | | C5 52.0% 765 | | E3 50.6% 678 | | D3 51.9% 620 | C5 56.0% 4131 | | D4 48.4% 1226 | | | C4 52.0% 765 | | C4 47.6% 710 | | D3 39.0% 605 | C3 54.2% 3702 | | C5 50.1% 1532 | | E7 50.3% 557 | D4 50.5% 3634 | | D5 52.3% 2730 | | | C5 37.3% 585 | | | E4 49.0% 582 | D5 39.3% 1688 | | D4 63.0% 1253 | | E4 58.4% 611 | | | D4 49.0% 582 D5 47.9% 8405 | F5 56.1% 2465 | | F4 47.2% 895 | | | G4 54.1% 512 | | E4 39.6% 528 | F4 52.9% 1516 | | F5 47.4% 529 | E5 50.8% 758 | | D4 45.9% 848 | | E4 50.4% 544 | G4 51.9% 698 | E4 49.1% 696 | | E5 58.4% 611 | | | D4 49.0% 582 | | E6 39.6% 528 | F3 49.5% 553 D4 47.4% 7963 | E6 51.4% 1466 | E5 55.2% 1355 | | D5 45.9% 848 | F6 53.1% 1019 | F7 51.3% 967 | D6 58.7% 652 | G7 58.5% 535 C4 44.6% 3206 C5 47.9% 2270 C3 40.3% 1438 Interesting. If I do the same with MonteGNU's fuseki database, which is based on online learning from own CGOS games, and cut off at 200 samples I get: E5 8101 | C3 2950 | | G5 1798 | | | G3 1145 (A) | | | | C5 403 | | | C7 310 | | E3 622 | | | C7 1145 (transposition of A) | C4 2249 | | C5 714 | | | B5 459 | | | | C6 403 | | D4 443 | | | C5 277 (B) | | C6 351 | | D6 286 | | E3 239 | C5 1708 | | D4 612 | | | C4 277 (transposition of B) | | C4 343 | | C3 297 | D4 864 | | E4 698 | | | D5 205 | D5 295 | | D4 216 D4 1608 | E5 681 | | E4 520 | | | D5 351 | | | | C5 212 | F6 279 | F5 250 D5 1521 | F5 508 | | F4 190 | F4 320 C4 585 C5 391 (C3 149) /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More UCT / Monte-Carlo questions
David Fotland wrote: Can you elaborate on what is in a node, and what you mean by expand? I assume you have simple node, where each node represents a position and the single move to get there. Then when you find a node with no children and expand it, you allocate up to 81 new nodes, but you only make one random playout. If uct picks a different leaf next time, you end up with most of the leaf nodes never visited. In this case you run out of memory quickly. If there are a few hundred K playouts to pick a move, and 90% of the leaves have no visits, then you need over a million nodes of memory. How do other programs handle this? I see that aya has an array of all children in each node. This still means allocating memory for all children when a new node is allocated. MonteGNU has a linked list of visited children and a bitboard marking moves which have not yet been visited. A new node is created without children and the bitboard marks all possible moves. It think many programs run several simulations through a node before allocating the children. I can see how this saves memory, but then how do you save the RAVE information from the early simulations? I have never managed to implement RAVE successfully. It made my program significantly slower but no stronger even at a fixed number of simulations. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to AyaMC, GNU, and MonteGNU!
terry mcintyre wrote: Does the KGS protocol permit one to propose a set of dead groups, then upon discovery of a conflict, to say Ok, your proposal still leads to my win, I'm perfectly happy to accept that result? No, at least not in any way that the engine can influence. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hydra theory (was Hybrid theory)
David Doshay wrote: I looked up borda voting on Wikipedia. I did not know this was called Borda voting, and it might be called a zeroth-order version of what I am thinking. Rather than just take rank order from each, I intended to try to include other metrics, for example, some measure of distance from top. One engine may evaluate that there is one really great move with all others considered very bad. That is different than many nearly equal good moves. [Commenting a somewhat arbitrary message in the thread.] MonteGNU (and gnugo --monte-carlo in the next development release) is doing a simple form of voting. Internally there are two engines; one UCT-MC engine and the ordinary GNU Go move generation. The UCT engine is allowed to nominate a number of moves and the ordinary move generation must choose one of those. More specifically the UCT engine nominates the following moves: 1. The highest scoring move in terms of win rate. Let N be the number of simulations for this move. 2. All moves with more than N/2 simulations 3. All moves with win rate win rate greater than 0.9 and more than N/10 simulations. 4. All moves if the highest scoring move has win rate less than 0.1. The move values from the ordinary move generation are then used to choose one of the nominated moves. If all nominated moves are thought useless the highest scoring UCT move is chosen. Pass is generated if and only if the ordinary move generation wants to pass. Usually this works fairly well. Most of the strength (on 9x9) comes from the UCT part and if it finds a clear winner the ordinary move generation only has a single move to choose from. When safely ahead many moves are nominated and the ordinary move generation gets to play for points, providing sensibly looking moves. Similarly when clearly losing and resignation is disabled, ordinary move generation gets to finish the game off in a tidy manner. A nice point is that with too few simulations the UCT engine will nominate lots of moves and the total result is that it more or less reverts to the ordinary move generation. Occasionally, however, it gives the worst of two worlds. The UCT engine may have a good move A first but a bad move B close behind and also nominated . The ordinary move generation maybe likes another good move C best and hates B but has completely missed A. Then B will be played, although both engines prefer better moves. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] gtp two way
Joshua Shriver wrote: In addition to my previous email is there a cli based app for doing two way gtp based head on head competitions between two engines? The GNU Go distribution provides multiple twogtp scripts in the interface/gtp_examples directory. These are written in Perl, Python, and Pike respectively with varying amounts of features. Additionally I also believe that GoGui includes a twogtp script (in Java). /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go board recap
Joshua Shriver wrote: For whatever reason my email grep'ing skills haven't spawns answers to a previously emailed question. In chess we have xboard/winboard. What clients do you recommend for linux for GTP playing? I recommend Quarry. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
Don Dailey wrote: Never mind, I found what I want: gnugo --mode gtp --score aftermath --capture-all-dead --chinese-rules --min-level 8 --max-level 8 --positional-superko Forget about --score aftermath. It does absolutely nothing when combined with --mode gtp. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
Don Dailey wrote: Thanks, will do that! Someone once told me that level 8 is faster and plays just as well. Is there any truth to that? I am planning to run this study at level 10. Level 8 is certainly faster and it ought to be weaker but I can't say anything about how much. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
Heikki Levanto wrote: On Wed, Jan 16, 2008 at 04:12:26PM -0500, Don Dailey wrote: There is no question that there are positions where suicide or eye filling are correct. I know suicide can be used as a ko-threat, but are there *any* other positions where it would be a correct move? Yes, but as far as I know only in obscure positions. http://www.goban.demon.co.uk/go/bestiary/rule_challenge.html is mandatory reading. If not, then it makes sense to forbid that in a random playout, since it is just a forcing move, and the (equally) random opponent is quite unlikely to answer the right way anyway. So the suicide move may look like a better move than it really is. I can not think of any situation where filling a one-point eye would be a correct move (provided that it is a real eye and not a false one). Can anyone come with concrete examples? This has been discussed before on this list. See e.g. http://computer-go.org/pipermail/computer-go/2006-August/006180.html http://computer-go.org/pipermail/computer-go/2006-August/006203.html /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
Erik van der Werf wrote: On Jan 16, 2008 10:42 PM, Heikki Levanto [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: I can not think of any situation where filling a one-point eye would be a correct move (provided that it is a real eye and not a false one). Can anyone come with concrete examples? Sure, for example with the following shape filling the eye makes a bulky five nakade in the corner _ |. # # |# # Under cgos rules you may in rare cases even have to fill eyes of pass-alive groups. This reminds me that one of the games in the January KGS tournament featured a case of moon-shine life because GNU Go by principle doesn't play inside unconditional territory unless it needs to remove all dead opponent stones, but even then only if there are dead stones in the same eye. The game record can be found at http://files.gokgs.com/games/2008/1/6/MonteGNU-break.sgf This is the final position, in cleanup mode after disagreement: A B C D E F G H J 9 . O . O O . . O . 9 8 . O O . O O . O O 8 7 O O + . O . + O O 7 6 O . O O O O . O O 6 5 . O O . + O . O . 5 4 O . O . . O O O O 4 3 O . + O . O X O X 3 2 O O . O O O X X . 2 1 . O O O X X X . X 1 A B C D E F G H J Black has just captured ko at J3, white passed since it refused to play inside any of its empty eyes, black of course passed too and the game was counted as it stood with the black stones considered alive. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: language efficiency
Forrest Curo wrote: So Scheme is one of the languages I've been considering, and in the process I stumbled upon a list of programs it was used to write. One of them: GIMP (Graphic Images Manipulation Program). Relevance?--Graphic images of any detail are enormous chunks of data; doing even a simple computation on one of these files has got to require a lot of bit-crunching, which used to be pretty time-consuming even when I was processing low-resolution grayscale photos for a monthly tabloid. I haven't run a direct comparison with GIMP's commercial rivals, but it's impressively fast by my standards... If something seems too good to be true, it is. All the heavy lifting in GIMP is done by C code, with scheme available as a scripting language on top. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] low-hanging fruit - yose
Heikki Levanto wrote: On Mon, Dec 10, 2007 at 04:08:48PM -0500, Don Dailey wrote: Would you rather be 95% confident of a win or 90% confident?There is only 1 correct answer to that question. Yes, if you can offer me reliable confidence numbers. We all (should) know that MC evaluations suffer from systematic problems that can not just be averaged away statistically. Compare these two positions: playout_benchmark 1 = Initial board: komi 7.5 A B C D E F G H J 9 . . . . . O O O O 9 8 O O O O O O O O O 8 7 O O O O O O O O O 7 6 O O O O O O O O O 6 5 # # # # # # # # # 5 4 O O O # # # # # # 4 3 O O O O . # # # # 3 2 . O O O . # # # . 2 1 # . O O . # # . # 1 A B C D E F G H J Performance: 1 playouts 0.032002 seconds 312.481 kpps Black wins = 1937 White wins = 8063 P(black win) = 0.1937 playout_benchmark 1 = Initial board: komi 7.5 A B C D E F G H J 9 . # . . . O O O O 9 8 O O O O O O O O O 8 7 O O O O O O O O O 7 6 O O O O O O # # # 6 5 # # # # # # # # # 5 4 O O O # # # # # # 4 3 O O O O . # # # # 3 2 . O O O . # # # . 2 1 . . O O . # # . # 1 A B C D E F G H J Performance: 1 playouts 0.084006 seconds 119.039 kpps Black wins = 7746 White wins = 2254 P(black win) = 0.7746 Which one is better, 77% or 19%? This reminds me of the first testcase I wrote when I started with MonteGNU. Black to play, no komi. A B C D E F G H J 9 . . O O X . X . X 9 8 . . . O X . X O X 8 7 O . O O X X O O X 7 6 O O O . X . X O O 6 5 X X X X X O O O . 5 4 . . X . O O . O . 4 3 X X O X O . + O . 3 2 X X O X O . . O . 2 1 . O O O O . . . . 1 A B C D E F G H J Naturally B has to play B8, or white plays there and wins big. This is trivial to find for a classic program and easy enough for a Monte Carlo program. What's interesting is that it takes some work to make black think that it has better than even winning chances after B8. The Monte Carlo code in GNU Go CVS version gets 0.079 with 10k, 0.387 with 100k, and 0.475 with 1M simulations. I suspect that stronger programs tend to be more optimistic about winning chances here. So please fill in this table if you have an MC program: 10k100k 1M GNU Go CVS 0.079 0.387 0.475 The sgf file is attached, load it before the first move. The positions before move 3 and 5 are also relevant tests. /Gunnar mc1.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] A thought about Bot-server communications
Nick Wedd wrote: Sorry, but I can't take this seriously. If your board update routine fails, just fix it. As long as you trust the controller to send legal moves, it's well defined how the board will look. The same board update logic can be used for all rulesets. If you don't agree about the legality, complain in a logfile. If you don't trust the controller to send legal moves, you have a problem that is hardly properly solved by asking it for a different board state description. I agree that the server knows better than me about the legality. I trust the server to make legal moves. I just might not know how to update the board state after a move I had not realised was possible. In 1998, running the Ing Cup, I tested all the entrants for their behaviour when someone played a suicide move at them. Many Faces put up a polite dialog box explaining that this was an illegal move. Go++ was more amusing: it allowed the move (which you would approve) but left the suicided stones on the board, where they became almost unkillable, it could not capture them by removing their last liberty as they didn't have one, the only way to lose them was to capture exactly one of their surrounding stones, in a perverted kind of snapback. I would have preferred these programs to have been able to respond wtf is going on, please tell me the current board state. Well, the thing is that fixing the board update logic should in most cases be a matter of adding a small number of lines, or in extreme cases even removing some lines. In terms of programming it's a much bigger operation to obtain information by external communication and then trying to recover the internal data structures. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A thought about Bot-server communications
Nick Wedd wrote: When I play Go on a Go server, I do not try to remember the board position. I can always find out what it is by looking at the client window on my screen. When a bot plays on a Go server, it does remember the position. This is something that programs are good at, so it seems reasonable to require them to do it. But there can be, very rarely, circumstances where a bot would like to ask the server what is the current board position?. Here are some examples. (1) My bot's opponent has just made a suicide move. My bot does not realise that, under the ruleset we are using, suicide is permitted. Therefore its board-update routine fails. It knows that its opponent has moved, and it knows that it does not know the current position. It would like to ask the server to send the current position. Sorry, but I can't take this seriously. If your board update routine fails, just fix it. As long as you trust the controller to send legal moves, it's well defined how the board will look. The same board update logic can be used for all rulesets. If you don't agree about the legality, complain in a logfile. If you don't trust the controller to send legal moves, you have a problem that is hardly properly solved by asking it for a different board state description. (2) As (1), but with a move that my bot thinks, wrongly, is forbidden by superko. Same as (1). (3) My bot, or the platform on which it is running, has had a serious accident. I have relaunched my bot and it wants to resume its game but has no knowledge of the position. It's standard practice for the controller to send play commands up to the point of resumption. If the engine has to be restarted the controller knows that it has lost state, there's no need for the engine to ask. KgsGtp knows how to do this, the CGOS client knows how to do this. If my understanding of the GTP spec at http://www.lysator.liu.se/~gunnar/gtp/gtp2-spec-draft2/gtp2-spec.html is correct, it is not possible for a bot to say please tell me the position. Should it be possible? No it shouldn't. GTP is designed to make it easy for engine authors to implement what the engine needs to play a game. For a go server protocol it can be useful to have methods to negotiate komi, negotiate opponents, ask the server all kinds of questions, and so on, but this is out of scope for GTP. A similar question applies to time. When I play in a tournament, I am allowed to look at my clock to find out how much time I have left. I am surprised to find that GTP provides no way for a bot to ask this. (Maybe I am misunderstanding the spec. I see that there are commands 'time_settings' and 'time-left' that the server can use to inform the bot of its remaining time, but I can find no indication of when, if ever, these commands will be issued.) For a game with time controls the controller is expected to send time_left commands once per move to keep the engine informed about the time situation. While thinking on a move the engine is expected to keep track of time by itself. By the way, if this has anything to do with KGS, the real problem there is that people who want to do advanced things with bots cannot modify kgsGtp, nor speak the server protocol themselves, since those are both proprietary. And just to be clear, the normal mode of communication between a bot and a server, if GTP is involved, is Server ---server protocol--- Client ---GTP--- Engine The server protocol and GTP have very different roles, capabilities, and complexities. In some cases the server protocol can be near GTP in complexity (CGOS), in some cases the server protocol is not available (KGS), and in some cases the server protocol can be hugely complex (IGS and NNGS clones). For the best result the client should have open code and be very configurable. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Where and How to Test the Strong Programs?
terry mcintyre wrote: Some of the MonteGNU code was just released on CVS. Check out Gnugo's development pages. Don't expect that code to do better than 2000 on CGOS though (mgtest2). The remaining code used by MonteGNU is still too messy. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CGOS down? Java client - basic GTP problem
Harri Salakoski wrote: command genmove w 30 reply=30 E3 cgos replys gameover 2007-11-27 B+Illegal do not understand syntax The cgos server does not speak GTP. A common solution is to let the cgos client cgosGtp.tcl translate the server protocol into GTP before connecting the engine. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] use for Monte Carlo on 19X19?
Stefan Mertin wrote: on 07.11.2007 07:35 Gunnar Farnebäck wrote: Stefan Mertin wrote: I am using GnuGo scoring in my tournaments. But GnuGo 3.7.10 mostly doesn´t score seki correctly, has this been revised for v3.7.11 ...?! What scoring mode are you using? /Gunnar SORRY - I was completely wrong here, I just realize that I was still using GnuGo 3.6 for scoring instead of 3.7.10! (for chinese : --score estimate --chinese-rules for japanese: --score estimate) In my actual computer Go tournament I just set up SmartGo2.7 to play GoIntellect10, and from 150 9x9games there are 7 with a seki in the final position. 5 of these were scored wrongly because I mistakingly had scored with GnuGo3.6 - I now have changed it to 3.7.11 and everything seams to be perfect! With GNU Go 3.6 you can try --score aftermath instead. It plays out the game until all stones except ones in seki are unconditionally settled, which usually gives a reliable seki detection. Also with current development versions --score aftermath is expected to be the most reliable scoring option, but the difference is much smaller nowadays. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] use for Monte Carlo on 19X19?
Don Dailey wrote: Lars, If I do anything to CGOS it would be handicap games. But I think your suggestion is sensible for Japanese scoring.GnuGo won't score perfectly every time, but I understand it is rarely incorrect. Does anyone have statistics on how well GnuGo scores professional 19x19 games? That depends on how difficult you make the problem. I have used Dave Dyer's test set of 623 scored professional 19x19 games, see http://www.andromeda.com/people/ddyer/go/scoring-games.html for information. As can be seen in the example on that page, those game records generally leave out all dame moves and even some moves required to finalize territories when it's clear how many points will be obtained there. Worse still, final endgame kos are frequently left out since it's assumed to be obvious who will win them. With this in mind, the results for GNU Go 3.7.11 are 534 (85.7%) correctly scored, 79 (12.7%) off by one point, 5 off by 2 points, 2 off by 3 points, and 1 each off by 12, 34, and 38 points. But mind you, GNU Go is trained on those games. It would certainly do worse on unseen games of a similar difficulty. On the other hand, if the game records are complete up to and including dame filling, I would expect the error rate to be less than 1%, possibly much better. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 CGOS
Don Dailey wrote: Who is running gnugo 10?You must using the right options. Here is how I run it: gnugo --mode gtp --score aftermath --capture-all-dead --chinese-rules --positional-superko You can skip --score aftermath, it has no effect when --mode gtp is used. (Without --mode gtp it would instead try to score the position but complain that no position was loaded with the -l option.) There is also a min-level and max-level setting - not sure what that does but I think this puts in some default level mode which is reasonbly strong. When playing without time controls you only have to specify --level n to play at level n, where level 10 is default. When playing with time controls GNU Go doesn't have infrastructure to spend a specific amount of time or abort the move generation based on time constraints. Instead it adjusts its playing level after each move, decreased level if it plays too slowly, increased level if it plays unnecessarily fast. This control is kind of crude and it's advisable to limit how high the level may become. Also a lower limit is sometimes useful as GNU Go tends to be rather erratic (more so than usual, that is) at really low level. Thus --min-level and --max-level sets these lower and higher limits that the time control is allowed to adjust the level between. By default min-level is 0 and max-level is 10 or the value set by --level, whichever is highest. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] XML alternatives to SGF
Jason House wrote: An XML alternative [1] to SGF has recently come to my attention. What do others think of this alternative? Personally, the effect of a tag affecting the previous tag seems kind of strange to me. For use in GNU Go it would need to have quite compelling benefits to become interesting. Let's look at numbers. GNU Go 3.7.10 roughly consists of 2.4 MB C code (83000 lines), 1.4 MB pattern data, 0.45 MB testcase files, 1.8 MB sgf game records (1500 sgf files), and 2 MB documentation. Of the C code 2600 lines come from the sgf library. If we want to use an available C library for XML, expat seems like a possible choice. The whole distribution is 2.5 MB but maybe it's possible to get away with the 400 kB (13000 lines) C code in the lib directory. Five times bigger than our sgf library but manageable. (That cannot be said of libxml2 though, with some 14 lines of code.) A potential problem with an XML library is the internal representation of the game tree. For debugging purposes it's not unusual to dump reading trees containing literally millions of moves, sometimes up to the limit of the available RAM. If an XML tree requires more bytes per move, the functionality would suffer. Does anybody know how big a node would become in expat for a move tag? Next problem is of course the file size of the game records. If they are 5 or 10 times as large we're talking 9 MB or 18 MB for the game records. Not a huge amount by itself but when considering the number of copies of GNU Go being distributed it sums up. So what are the benefits? So far I haven't seen anything that is relevant for GNU Go. The readability is not really an issue, it's almost never possible to visualize a game record without a graphical viewer anyway, regardless of coordinate representation, and from the examples I've seen XML has been worse off than sgf on readability. Character sets are a non-issue for GNU Go, information about players is simply ignored. Version control conflicts have never happened with game records and I don't foresee it for the future. But I can provide a hint for something I would find useful. If it's something I'm missing in today's sgf viewers it's a good way to dump and inspect a transposition table. It's possible to expand the transpositions into a big tree with duplicate subtrees but that makes it very difficult to traverse it efficiently. Alternatively the tree is cut off when the same position is reached again but then there's no easy way to find where the position was first reached, which is needed to follow the continuations. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
