Re: [computer-go] Monte-Carlo Tree Search reference bot
What I did (was a "long" time ago, I don't know if it is still used in Mogo), is to compute the m best moves every so often and most of the time just do the max over those m moves. m was on the order of 5, and "every so often" was an increasing function like sqrt or log (I don't remember). That speeds up quite a lot (when the max becomes the bottleneck), and if you tune the parameters well you almost don't loose any strength at a fixed number of playouts. Sylvain 2008/12/3 <[EMAIL PROTECTED]>: > There is another speedup trick that might interest you. IIRC Lukasz Lew came > up with it, but I forget what he called it. After calculating the selected > move for an internal node (going through UCT and RAVE and whatnot) store > that move. Then, for the next N visits to that node (where N is 5 or 10 or > so), just repeat that move without having to calculate what the move would > be. > > - Dave Hillis > > -Original Message- > From: Mark Boon <[EMAIL PROTECTED]> > To: computer-go > Sent: Tue, 2 Dec 2008 11:17 pm > Subject: Re: [computer-go] Monte-Carlo Tree Search reference bot > > I have made some minor performance improvements and this is as far as I > intend to take this particular project. I might make some small changes if > necessary, but most likely I'll leave this largely unchanged from now. > > I had set myself as an arbitrary goal that it should do at least 20K > playouts. But with real liberties, AMAF and a RAVE formula I got stuck in > the 16K-17K range. According to my profiler that is mostly due to the > expensive formula used to compare nodes, where it says it spends 25% of > total time. The formula I'm using is: > > beta * (virtual-win-ratio + RAVE) + (1-beta) * (win-ratio + UCT) > > beta = 1 - log(parent-visits) / 20 > UCT = exploration-factor *sqrt( log(parent-visits) / (nr-visits+1) ) > RAVE = exploration-factor *sqrt( log(parent-visits) / > (nr-virtual-visits+1) ) > > There are probably quite a few possibilities still to tune this program with > regards to playing strength and performance. But I felt it doesn't help to > obscure the implementation by too many details. > > The implementation of the search algorithm was entirely game-independent, > until I introduced AMAF. I didn't see how to fix that, as there's no way > getting around that it's based on the fact that a move is represented by a > single coordinate, which is mapped to an array to store the statistical > values. But strip the AMAF part, which is a block of 30 odd lines of code, > and I think it can be used for other games basically as-is. I did this not > because I ever see myself program another game, but because in my experience > in doing so I get a cleaner separation between modules. > > At 2,000 playouts, it's still quite a bit weaker than the plain MC-AMAF > refbot. It wins only about 33%. But that's probably because the 1,000-2,000 > playouts range is the sweet-spot for that particular type of playing engine. > It doesn't scale from there, whereas the MCTS ref-bot only just gets warmed > up with 2,000 playouts. > > This leads me to a question. I suppose it might be of some interest to put > this bot up on CGOS. But what parameters to use? The main one being the > number of playouts, naturally. > > Mark > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > Tis the season to save your money! Get the new AOL Holiday Toolbar for money > saving offers and gift ideas. > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Tree Search reference bot
On Wed, Dec 3, 2008 at 05:17, Mark Boon <[EMAIL PROTECTED]> wrote: > I had set myself as an arbitrary goal that it should do at least 20K > playouts. But with real liberties, AMAF and a RAVE formula I got stuck in > the 16K-17K range. According to my profiler that is mostly due to the > expensive formula used to compare nodes, where it says it spends 25% of > total time. The formula I'm using is: > >beta * (virtual-win-ratio + RAVE) + (1-beta) * (win-ratio + UCT) > >beta = 1 - log(parent-visits) / 20 >UCT = exploration-factor *sqrt( log(parent-visits) / (nr-visits+1) ) >RAVE = exploration-factor *sqrt( log(parent-visits) / > (nr-virtual-visits+1) ) Hi, This is probably something you already do, but just in case you don't, here comes a simple optimization trick: since parents-visits is an integer value and in a somewhat bounded range (0..max_playouts), the logarithm can be precomputed in a table. Then even sqrt(log()) can be precomputed also. Similarly, a table with sqrt(integer()) can be used for the other values. best regards, Vlad ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Tree Search reference bot
On 3-dec-08, at 06:09, Sylvain Gelly wrote: What I did (was a "long" time ago, I don't know if it is still used in Mogo), is to compute the m best moves every so often and most of the time just do the max over those m moves. m was on the order of 5, and "every so often" was an increasing function like sqrt or log (I don't remember). That speeds up quite a lot (when the max becomes the bottleneck), and if you tune the parameters well you almost don't loose any strength at a fixed number of playouts. I thought about that, but I was afraid the code would become too obscure. After all, this is supposed to be a reference implementation. But maybe I should actually give it a try to see what it would look like. I also played with precomputing a table of the log() function but found little speedup. Instead I decided to (p)recompute the log(nr- parent-visits) only once in 8 times. According to my profiler that reduced the log() from using 8% to 1% of computation time. Another thing I did was replace log(nr-virtual-parent-visits) in the RAVE calculation by the same log(nr-parent-visits) used in the UCT calculation, cutting both the number of times I need to call log in half and reducing the amount of storage in the node a little. After these modifications I didn't notice any degradation in play. In terms of memory use, I did a few obvious things to keep storage of the nodes to a minimum. I had seen people write about memory usage of the tree, but never understood the concerns. But that was because I always expanded the tree one node at a time. Of course, if you create all the children in one go like this reference implementation does, it's a little bit a different story. But still, I have to push my computer hard to run out of space before I run out of time so I didn't see much need to reduce memory too aggressively. Using just a moderately small number of playouts before expansion is already enough to never have memory problems. But if memory is a concern to anyone I see two obvious ways to make make significant reductions. One is to flatten the data-structure, reducing the object overhead Java imposes. That could save up to a third. The other is to use smaller placeholders for nodes that have been created, but not yet visited. Once a node gets visited it can be replaced by a full-blown node, but until then all you need is the move-coordinate and the AMAF statistics. That should save up to 75% or so. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Tree Search reference bot
On Wed, Dec 03, 2008 at 09:55:07AM -0200, Mark Boon wrote: > I thought about that, but I was afraid the code would become too > obscure. After all, this is supposed to be a reference > implementation. But maybe I should actually give it a try to see what > it would look like. I agree that the reference implementation should be maximally clear code. Performance is not all that important here, correctness is. Having said that, I can't help responding to one detail: > I had seen people write about memory usage of the tree, but never > understood the concerns. One thing to remember is that more memory use means more cache misses, and more access to the main memory. On modern computers, those can cost as much as executing a thousand instructions! So memory optimizing can often pay off, also with respect to time! Of course, Java does a lot of memory management behind the scenes, so optimizing such can be harder... But when writing in C or C++, it does make sense. -H -- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Tree Search reference bot
On 3-dec-08, at 10:31, Heikki Levanto wrote: Having said that, I can't help responding to one detail: I had seen people write about memory usage of the tree, but never understood the concerns. One thing to remember is that more memory use means more cache misses, and more access to the main memory. On modern computers, those can cost as much as executing a thousand instructions! So memory optimizing can often pay off, also with respect to time! Of course, Java does a lot of memory management behind the scenes, so optimizing such can be harder... But when writing in C or C++, it does make sense. I've seen this stated often. But color me skeptical. If what you say is true, then the MC-AMAF bot, which hardly uses any memory at all and which fits in the secondary cache entirely, code and data combined, should show an enormous speed-up in terms of number of playouts per second. Instead it does only about twice the number of playouts per second as the tree-search version, which can be almost if not entirely explained by the extra work that needs to be done to traverse and maintain the tree. If this is because I use Java, then Don's concise C implementation of the MC-AMAF bot should be a lot faster than my bloated Java version. Which, ahem, is not the case at all. I think a well-crafted C program can be up to twice as fast as a similar Java program. But I doubt that has much to do with cache misses. I think in computer-Go, trying to control cache misses is futile no matter the language. Maybe you can do it for a relatively trivial, well-understood and stable sub-part. But then you risk losing the gain again as soon as it gets incorporated into a larger whole. So your efforts go to waste. So this is in the "show me" category for me. You can use C or C++ if you like, but show me a tree-search bot that speeds up the number of playouts significantly by reducing the node-size. Maybe it's possible, but I don't believe it until I see it. This could be different for Chess programs, at least I've seen it claimed often. But I don't envy them, it must be excruciatingly frustrating to deal with. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Tree Search reference bot
On Wed, Dec 03, 2008 at 11:24:22AM -0200, Mark Boon wrote: > > Heikki wrote: > >One thing to remember is that more memory use means more cache misses, > >and more access to the main memory. On modern computers, those can cost > >as much as executing a thousand instructions! So memory optimizing can > >often pay off, also with respect to time! > > > I've seen this stated often. But color me skeptical. Maybe I was quoting "common wisdom" without having checked it personally. I only remember one case - not related to go at all - where optimizing the memory stuff made a noticeable difference. I would also like to see hard evidence. But not badly enough to put in the necessary work to get some ;-) - H -- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Tree Search reference bot
I had a chess program years ago that was blindingly fast on some computers, very slow on others. It was all about the cache. The move generator was hard coded for each piece on each square. For instance a white pawn on d7 had it's very own move specialized move generator. There was a function for each piece of each color on each square. By doing this I avoided the majority of conditional tests. I did not have to test for board edge, pawn on 7th, pawn on the second rank, etc. All the logic was unrolled and I basically had to write a program to write the move generator. The machine I developed this program on had a lot of cache and it was not a problem. But when running on, for instance a laptop, it would slow down enormously - something like 4 to 1 where other cache friendly programs would slow down perhaps 25%. I don't keep up much with processor technologies now and I don't know how much data vs instruction cache modern setups have, but I know it is far better than it used to be. I bet that old program would run well on modern computers. One trick, which you are probably doing, is to keep data structures together in memory. For instance it is better to have children next to each other so that you are not accessing memory all over the place, perhaps incurring several cache misses instead of one. On Wed, 2008-12-03 at 11:24 -0200, Mark Boon wrote: > On 3-dec-08, at 10:31, Heikki Levanto wrote: > > > > Having said that, I can't help responding to one detail: > > > >> I had seen people write about memory usage of the tree, but never > >> understood the concerns. > > > > One thing to remember is that more memory use means more cache > > misses, and > > more access to the main memory. On modern computers, those can cost > > as much > > as executing a thousand instructions! So memory optimizing can > > often pay off, > > also with respect to time! > > > > Of course, Java does a lot of memory management behind the scenes, so > > optimizing such can be harder... But when writing in C or C++, it > > does make > > sense. > > > > I've seen this stated often. But color me skeptical. If what you say > is true, then the MC-AMAF bot, which hardly uses any memory at all > and which fits in the secondary cache entirely, code and data > combined, should show an enormous speed-up in terms of number of > playouts per second. Instead it does only about twice the number of > playouts per second as the tree-search version, which can be almost > if not entirely explained by the extra work that needs to be done to > traverse and maintain the tree. If this is because I use Java, then > Don's concise C implementation of the MC-AMAF bot should be a lot > faster than my bloated Java version. Which, ahem, is not the case at > all. I think a well-crafted C program can be up to twice as fast as a > similar Java program. But I doubt that has much to do with cache misses. > > I think in computer-Go, trying to control cache misses is futile no > matter the language. Maybe you can do it for a relatively trivial, > well-understood and stable sub-part. But then you risk losing the > gain again as soon as it gets incorporated into a larger whole. So > your efforts go to waste. > > So this is in the "show me" category for me. You can use C or C++ if > you like, but show me a tree-search bot that speeds up the number of > playouts significantly by reducing the node-size. Maybe it's > possible, but I don't believe it until I see it. This could be > different for Chess programs, at least I've seen it claimed often. > But I don't envy them, it must be excruciatingly frustrating to deal > with. > > Mark > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Tree Search reference bot
On Wed, 2008-12-03 at 11:24 -0200, Mark Boon wrote: > If this is because I use Java, then > Don's concise C implementation of the MC-AMAF bot should be a lot > faster than my bloated Java version. I don't remember the numbers, but my own java and C implementation were written in the same style - same basic data structure and just about the only difference was language. I did do some kind of list trick using pointers than you cannot do in java, at least not easily and efficiently but I don't think it made that much of a difference. The Java version was not that bad for speed compared to C, I think C was something like 2/3 of the speed or close to that.But if you got into heavy duty data structures Java hurts - you won't get as big a tree in Java for instance and I'm sure caching will be a bigger issue. - Don signature.asc Description: This is a digitally signed message part ___ 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/
