Re: [Computer-go] fast + good RNG
Looking at the lightest playout version of my bitmap-based 9x9 program (source-code somewhere in the archives), I spent an estimated 2% of the time generating random numbers, so 40% seems to indicate something is not right, such as re-initializing the generator all the time. The execution time of my engine breaks down sort-of like this on my MacBook: benchmarking Mersenne Twister (SFMT version [following Agner Fog]) [BRandom] = 1, [IRandom] = 1, [IRandomX] = 2, [Random] = 2, [FRandom] = 2 benchmarking playouts (clock cycles) [game] = 18051 cc, [moves] = 111.07 benchmarking playouts (wall time) [game] = 126.108 kpps, [moves] = 111.07 benchmarking board functions (calls per game/clock cycles) [select] 111/55, [play] 106/93, [score] 14, [win] 0.4251 benchmarking move generator (calls per game/clock cycles, find+pick) [moves] 111 [random] 111/17+36 This last line breaks down move-generation in finding all legal moves (17cc, using Gunnar Farneback's Brown programs definition of legal) and picking one uniformly at random (36cc). That last method uses 1-3 random numbers of 1cc each. A move takes 55 + 93 = 148cc, so 3cc represents at most 2%. Things get a bit messier to assess once you consider waterfalling moves, such as captures, atari extensions, etc. In general, though, going towards heavier playouts will only reduce the time spent on random number generation because you will have to maintain more data or perform more logic. In any case, spending more than a handful of cc on random number generation is not needed and, thus, random number generation should not be high on your resource consumption list. For reference, an old profile report for a non-bitmap heavier MCTS-player reports 1.1% of time was spent on random number generation. René BTW. The average game-length using a uniformly random move-generator is a pretty good correctness test. On Sun, Mar 29, 2015 at 10:16 PM, Petri Pitkanen petri.t.pitka...@gmail.com wrote: Assuming you are using some sensible OS there better ways profile than sample like oprofile for linux. There is similar thing for FreeBSD I think. No instrumentation san sampling gets automated Petri 2015-03-30 8:05 GMT+03:00 hughperkins2 hughperki...@gmail.com: 40% sounds pretty high. Are you sure its not an artefact of your profiling implementation? I prefer not to instrument, but to sample stack traces. You can do this using gdb by pressing ctrl-c, then type bt. Do this 10 times, and look for the parts of the stack that occur often. ___ 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 ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Learning from CGOS
Awesome Joshua! I agree with the others. Start open sourcing it right away. That's what I did with my Go bot that I started writing in a language I didn't know. And people (well, two ;)) just decided to help out. As for features. Well, I'd be happy if you just reimplemented CGOS and it were running all the time for all three sizes. ;) There are only minor things I'd like to change: 1. The standings page could update more frequently 2. The length of the usernames is a bit restricting for me as my bot is called Iomrascálaí which almost takes up all 16 (?) characters. Adding a version number and some identifiers for various command line parameters gets difficult then. 3. On that topic. Allowing characters other than ASCII in a username would be nice, too. It's 2015 after all. Other than that, I'm happy with the way it's set up. Urban On Sat, Mar 28, 2015 at 11:58 PM, Joshua Shriver jshri...@gmail.com wrote: What elements did you like about CGOS and what do you wish for? I've begun writing a new version from scratch that isn't TCL based. With the aim for future use and also open source and open to public commits. -Josh ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go -- Blog: http://bettong.net/ Twitter: https://twitter.com/ujh Homepage: http://www.urbanhafner.com/ ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Learning from CGOS
What elements did you like about CGOS and what do you wish for? I've begun writing a new version from scratch that isn't TCL based. With the aim for future use and also open source and open to public commits. A simple json interface that enables people to do automated checks for elo rating, latest match played and failures. Oh and indeed failures: currently it says illegal move; it would be great if it also could say what is illegal about the move. Maybe create a logfile accessible via the web-interface for that. Folkert van Heusden -- Always wondered what the latency of your webserver is? Or how much more latency you get when you go through a proxy server/tor? The numbers tell the tale and with HTTPing you know them! http://www.vanheusden.com/httping/ --- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
For profiling I use callgrind. Afaik it is the most accurate as it simulates a processor and counts cycles etc. As others pointed out: my playout-code is somewhat lightweight. In that 40% version it only checked if a cross is empty. I added super-ko check which gave a 10% hit on the number of pps. Currently I'm looking into doing full validity checks. It currently does +/- 20-30k pps with one core on a HT-sibling. 40% sounds pretty high. Are you sure its not an artefact of your profiling implementation? I prefer not to instrument, but to sample stack traces. You can do this using gdb by pressing ctrl-c, then type bt. Do this 10 times, and look for the parts of the stack that occur often. Folkert van Heusden -- Ever wonder what is out there? Any alien races? Then please support the seti@home project: setiathome.ssl.berkeley.edu -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] evaluating number of wins versus looses
The complex formula at the end is for a lower confidence bound of a Bernoulli distribution with independent trials (AKA biased coin flip) and no prior knowledge. At a leaf of your search tree, that is the most correct distribution. Higher up in a search tree, I'm not so sure that's the correct distribution. For a sufficiently high number of samples, most averaging processes converge to a Normal distribution (due to central limit theorem). For a Bernoulli distribution with a mean near 50% the required number of samples is ridiculously low. I believe a lower confidence bound is probably best for final move selection, but UCT uses an upper confidence bound for tree exploration. I recommend reading the paper, but it uses a gradually increasing confidence interval which was shown to be an optimal solution for the muli-armed bandit problem. I don't think that's the best model for computer go, but the success of the method cannot be denied. The strongest programs have good prior knowledge to initialize wins and losses. My understanding is that they use average win rate directly (incorrect solution #2) instead of any kind of confidence bound. TL;DR: Use UCT until your program natures On Mar 30, 2015 8:06 AM, folkert folk...@vanheusden.com wrote: Hi, When performing a montecarlo search, we end up with a number of wins and number of looses for a position on the board. What is now the proven methology for comparing these values? I tried the method described here: http://www.evanmiller.org/how-not-to-sort-by-average-rating.html ...which not only looks at how much more wins than looses there were for a position but also the total number for that position. So that a difference x with 10 playouts may be evaluated lower than a difference y with 11 playouts, even if x y. This does not seem to give good results altough other factors may be in play here (my program is in it's infant stage). Folkert van Heusden -- Finally want to win in the MegaMillions lottery? www.smartwinning.info -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ 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] evaluating number of wins versus looses
On Mon, Mar 30, 2015 at 4:09 PM, Petr Baudis pa...@ucw.cz wrote: The strongest programs often use RAVE or LGRF or something like that, with or without the UCB for tree exploration. Huh, are there any strong programs that got LGRF to work? Erik ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] evaluating number of wins versus looses
On Mon, Mar 30, 2015 at 09:11:52AM -0400, Jason House wrote: The complex formula at the end is for a lower confidence bound of a Bernoulli distribution with independent trials (AKA biased coin flip) and no prior knowledge. At a leaf of your search tree, that is the most correct distribution. Higher up in a search tree, I'm not so sure that's the correct distribution. For a sufficiently high number of samples, most averaging processes converge to a Normal distribution (due to central limit theorem). For a Bernoulli distribution with a mean near 50% the required number of samples is ridiculously low. I believe a lower confidence bound is probably best for final move selection, but UCT uses an upper confidence bound for tree exploration. I recommend reading the paper, but it uses a gradually increasing confidence interval which was shown to be an optimal solution for the muli-armed bandit problem. I don't think that's the best model for computer go, but the success of the method cannot be denied. The strongest programs have good prior knowledge to initialize wins and losses. My understanding is that they use average win rate directly (incorrect solution #2) instead of any kind of confidence bound. TL;DR: Use UCT until your program natures The strongest programs often use RAVE or LGRF or something like that, with or without the UCB for tree exploration. For selecting the final move, the move with most simulations is used. (Using the product reviews analogy - assume all your products go on sale at once, have the same price, shipping etc., then with number of buyers going to infinity, the best product should get the most buyers and ratings even if some explore other products.) I think trying the Wilson lower bound could be also interesting, but the inconvenience is that you need to specify some arbitrary confidence level. On Mar 30, 2015 8:06 AM, folkert folk...@vanheusden.com wrote: -- Finally want to win in the MegaMillions lottery? www.smartwinning.info funny in the context :) -- Petr Baudis If you do not work on an important problem, it's unlikely you'll do important work. -- R. Hamming http://www.cs.virginia.edu/~robins/YouAndYourResearch.html ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
[Computer-go] evaluating number of wins versus looses
Hi, When performing a montecarlo search, we end up with a number of wins and number of looses for a position on the board. What is now the proven methology for comparing these values? I tried the method described here: http://www.evanmiller.org/how-not-to-sort-by-average-rating.html ...which not only looks at how much more wins than looses there were for a position but also the total number for that position. So that a difference x with 10 playouts may be evaluated lower than a difference y with 11 playouts, even if x y. This does not seem to give good results altough other factors may be in play here (my program is in it's infant stage). Folkert van Heusden -- Finally want to win in the MegaMillions lottery? www.smartwinning.info -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] evaluating number of wins versus looses
On Mon, Mar 30, 2015 at 04:17:13PM +0200, Erik van der Werf wrote: On Mon, Mar 30, 2015 at 4:09 PM, Petr Baudis pa...@ucw.cz wrote: The strongest programs often use RAVE or LGRF or something like that, with or without the UCB for tree exploration. Huh, are there any strong programs that got LGRF to work? Oops, I actually meant to write criticality, though I'm a little bit confused now whether Nomitan primarily uses criticality, LGRF or both. Perhaps Simon will want to clarify... (In general, it seems apparent that many methods of information sharing are complementary to a large degree, i.e. by opting for one at the beginning, you get similar benefit as if you did a different one, especially if you tune your way to a good local optimum. But RAVE came first...) -- Petr Baudis If you do not work on an important problem, it's unlikely you'll do important work. -- R. Hamming http://www.cs.virginia.edu/~robins/YouAndYourResearch.html ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
