RE: [computer-go] monte carlo
Many Faces of go is currently much slower. On 9x9 it does about 18k playouts per second, on two CPU cores, so about 9K per thread. The average 9x9 game is about 92 moves, so there are about 1.6 million board-settings per second. The playouts are far from random. Many moves are local responses to the last move, and when there is no forced local response, the global moves are not fully random either. My original light code did about 55K playouts per second on one CPU core, but was far weaker. David > > > May I ask: how many board-settings (one move + all evaluation) do your > > programs calculate per second? > > Depends on the hardware. ;-) We usually count in number of complete > playouts per second. > > On 9x9, libego can play i think about 100k playouts per second on decent > CPU, but is very light. Pachi can do 35k light playouts per second and > 15k heavy playouts per second on the same CPU (single-threaded). Both > Pachi and libego are written in a compiled language; when your speed is > in the right order of magnitude, I've found playout move selection > improvements much more profitable than further optimizing for speed. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] monte carlo
On Sun, Oct 25, 2009 at 10:16:58PM +0100, Folkert van Heusden wrote: > > > What method are you guys using for the monte carlo search? What do you > > > do? > > > I pick at random a move, then for the resulting board that comes out of > > > that pick another move and so on. > > > Then, after that I evaulate the number of stones etc. > > > > Do you mean you count the score? Make sure you actually count the stone > > right, and (quite important) that you are picking out moves really at > > random, not skewed in any way. > > Yes, the score indeed. Well, only the number of stones removed from the > board. I did not implement an algorithm to count areas belonging to a > color yet. That would seem to have only quite limited correlation with winning the game. > May I ask: how many board-settings (one move + all evaluation) do your > programs calculate per second? Depends on the hardware. ;-) We usually count in number of complete playouts per second. On 9x9, libego can play i think about 100k playouts per second on decent CPU, but is very light. Pachi can do 35k light playouts per second and 15k heavy playouts per second on the same CPU (single-threaded). Both Pachi and libego are written in a compiled language; when your speed is in the right order of magnitude, I've found playout move selection improvements much more profitable than further optimizing for speed. -- Petr "Pasky" Baudis A lot of people have my books on their bookshelves. That's the problem, they need to read them. -- Don Knuth ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] monte carlo
> > What method are you guys using for the monte carlo search? What do you > > do? > > I pick at random a move, then for the resulting board that comes out of > > that pick another move and so on. > > Then, after that I evaulate the number of stones etc. > > Do you mean you count the score? Make sure you actually count the stone > right, and (quite important) that you are picking out moves really at > random, not skewed in any way. Yes, the score indeed. Well, only the number of stones removed from the board. I did not implement an algorithm to count areas belonging to a color yet. > > What do you guys look at to select a move using monte carlo? > People use heuristics to prefer captures, escaping atari, play local > moves that match certain 3x3 patterns etc. - there is plenty of papers > covering this, I recommend you look at them. It's fairly important to > have all the heuristics somewhat randomized (depending on other parts of > my engine, I've found any value between 60% to 90% probability of > applying each heuristic optimal). Yeah, I rated most of them equally. Some are weighted in depending on applicability. May I ask: how many board-settings (one move + all evaluation) do your programs calculate per second? Folkert van Heusden -- Ever wonder what is out there? Any alien races? Then please support the s...@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://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] monte carlo
On Sun, Oct 25, 2009 at 06:52:56PM +0100, Folkert van Heusden wrote: > What method are you guys using for the monte carlo search? What do you > do? > I pick at random a move, then for the resulting board that comes out of > that pick another move and so on. > Then, after that I evaulate the number of stones etc. Do you mean you count the score? Make sure you actually count the stone right, and (quite important) that you are picking out moves really at random, not skewed in any way. > What do you guys look at to select a move using monte carlo? People use heuristics to prefer captures, escaping atari, play local moves that match certain 3x3 patterns etc. - there is plenty of papers covering this, I recommend you look at them. It's fairly important to have all the heuristics somewhat randomized (depending on other parts of my engine, I've found any value between 60% to 90% probability of applying each heuristic optimal). -- Petr "Pasky" Baudis A lot of people have my books on their bookshelves. That's the problem, they need to read them. -- Don Knuth ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] monte carlo
What method are you guys using for the monte carlo search? What do you do? I pick at random a move, then for the resulting board that comes out of that pick another move and so on. Then, after that I evaulate the number of stones etc. What do you guys look at to select a move using monte carlo? On Sat, Oct 17, 2009 at 05:02:33PM +0200, Folkert van Heusden wrote: > People, > > I'm trying to implement a monthecarlo algorithm in my go program. Now > the results are dramatic: the elo-rating of my go program drops from > 1150 to below 700. I tried: > - evaluate the number of captured stone > - evaluate strategic elements (without MC this strategic eval gives >that 1150 elo). > Currently my program can evaluate 500 scenes per second and I let it > "think" for 5 seconds. > What could be the cause of this dramatic results? Wrong evaluation? Not > enough nodes processed? Folkert van Heusden -- www.vanheusden.com/multitail - multitail is tail on steroids. multiple windows, filtering, coloring, anything you can think of -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
