[Computer-go] Solving semeai
(I just thought I'd bring together a few recent comments and see if they inspire anyone.) Yamato wrote: Zen has some code to handle very simple semeais in the playouts. But I am not satisfied with the code. To solve the semeai issue fully, we will need a better algorithm to share the tree information with the simulation. Aja wrote: it's clear that we need something new and BIG to solve semeai, rather than heavy knowledge implementation. I believe Valkyria solves some semeai in the playouts, and I believe it does this with a large set of hand-coded patterns (i.e. heavy knowledge). E.g. The Many Faces vs. Aya game that was discussed recently, where both programs misunderstood it, Valkyria had the needed knowledge to make it simple. But Magnus goes on to say: Semeai is a good example. Valkyria is good on simple cases close to the winning capture but there are an unending amount of complex semeai where this knowledge only have an effect deep down in the playouts. Some algorithm of online learning of good tactics seems to be necessary. Darren -- Darren Cook, Software Researcher/Developer http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Direct DX11 and graphics cards for cheaper simulation
Doesn't the simple mathematics of why go is difficult make the 'faster hardware' topic a small issue? At the starting move there is on the scale of 361! = (roughly 10 ^ 300 ?) possible combinations having a very simple algorithm with a hardware improvement of 10 ^ 9 can't possibly outperform an algorithm with even minimal intelligent tree pruning? On Fri, Jun 3, 2011 at 6:18 AM, computer-go-requ...@dvandva.org wrote: Send Computer-go mailing list submissions to computer-go@dvandva.org To subscribe or unsubscribe via the World Wide Web, visit http://dvandva.org/cgi-bin/mailman/listinfo/computer-go or, via email, send a message with subject or body 'help' to computer-go-requ...@dvandva.org You can reach the person managing the list at computer-go-ow...@dvandva.org When replying, please edit your Subject line so it is more specific than Re: Contents of Computer-go digest... Today's Topics: 1. Direct DX11 and graphics cards for cheaper simulation hardware? (Jacques Basald?a) 2. Re: Direct DX11 and graphics cards for cheaper simulation hardware? (Don Dailey) 3. [Computer-go ]Congratulations to Zen! (Nick Wedd) 4. Re: [Computer-go ]Congratulations to Zen! (Andy) 5. Re: [Computer-go ]Congratulations to Zen! (Michael Williams) -- Message: 1 Date: Thu, 02 Jun 2011 20:48:16 +0100 From: Jacques Basald?a jacq...@dybot.com To: computer-go@dvandva.org Subject: [Computer-go] Direct DX11 and graphics cards for cheaper simulation hardware? Message-ID: 4de7e900.2050...@dybot.com Content-Type: text/plain; charset=us-ascii; format=flowed Don Dailey wrote: Are you trying to say that heavy playouts are better? Who is going to argue with that? I agree completely. Are you trying to make the point that there are very simple to understand positions that computers cannot easily solve? I agree with that. Are you trying to say that heavy playouts can solve many types of common positions orders or magnitude faster than light playouts? I agree with that. Are you trying to say uniformly random playouts suck? I agree with that. I do not pretend to argue. Just to clarify ideas and read what others have to say. And of course I agree on all that. In self play all MCTS programs scale. Everybody agrees and it has been tested empirically. Intuitively: If we admit that 2000 sims is better than 1000, since nodes in the tree are trees themselves, it is clear that no matter how many million simulations we play, there will always be nodes with 1000 visits and they would be better evaluated if they had 2000. The entire tree relies on the correct evaluation at the nodes so the entire tree benefits of more sims. A different question is: Can a really weak program, say vanilla MCTS with uniform random playouts, just no eye filling (no RAVE, no progressive widening) reach the strength of, say Aya, with 2500 sims (KGS 4 kyu) in 19x19 ? The answer is: Theoretically: Yes. In practice: No. Not with a trillion sims per move. You probably don't disagree since that is implicit in heavy playouts can solve many types of common positions orders or magnitude faster than light playouts. Note that this question is equivalent to: Would the current version of Zen become a pro just with hardware evolution? Jacques. -- Message: 2 Date: Thu, 2 Jun 2011 16:57:51 -0400 From: Don Dailey dailey@gmail.com To: computer-go@dvandva.org Subject: Re: [Computer-go] Direct DX11 and graphics cards for cheaper simulation hardware? Message-ID: banlktim+rn9fqxygfaatpur2vq7guy5...@mail.gmail.com Content-Type: text/plain; charset=iso-8859-1 On Thu, Jun 2, 2011 at 3:48 PM, Jacques Basald?a jacq...@dybot.com wrote: Don Dailey wrote: Are you trying to say that heavy playouts are better? Who is going to argue with that? I agree completely. Are you trying to make the point that there are very simple to understand positions that computers cannot easily solve? I agree with that. Are you trying to say that heavy playouts can solve many types of common positions orders or magnitude faster than light playouts? I agree with that. Are you trying to say uniformly random playouts suck? I agree with that. I do not pretend to argue. Just to clarify ideas and read what others have to say. And of course I agree on all that. I'm not really directing this to any specific individual, sorry it came across that way. In self play all MCTS programs scale. Everybody agrees and it has been tested empirically. Intuitively: If we admit that 2000 sims is better than 1000, since nodes in the tree are trees themselves, it is clear that no matter how many million simulations we play, there will always be nodes with 1000 visits and they would be better evaluated if they had 2000. The entire tree relies
Re: [Computer-go] [Computer-go ]Congratulations to Zen!
On 03/06/2011 02:50, Hideki Kato wrote: Thank you for the report and the tournament, Nick. The second paragraph of round 9, sideof the board, as shown to the right. If move 215 had been ^^ side of On the hardware section, please update the following: Zen19S Zen, running on six cores of a 3.3 GHz Xeon W3680 to (as in my post to this list, Message-ID: 4ddf132c.2270%hideki_ka...@ybb.ne.jp): Zen19S uses 6-core Xeon (as in the mail) for round 1 to 9 and a 6-pc personal cluster for round 10 to 20. The cluster consits of a 6 x 3.3 GHz Xeon W5680, two 4 x 3.2 GHz i7 920 and three 4 x 3 GHz Core2Quad. ^W3680 is correct, sorry. (Please feel free to modify above to match the report.) #The latter is a little bit different from (ie, slower than) Zen19D's. #Zen19S won all of the rounds with the cluster. :) Thank you for these corrections. Was it better to send a direct mail to you than posting here? I am happy with either. Other readers of the list probably prefer not to see such corrections, so I think you are right to email me directly. Nick Hideki Nick Wedd:4de7fde9.4090...@maproom.co.uk: Congratulations to Zen19S, winner of last week's slow bot tournamwent, four wins ahead of its nearest rival! My report is at http://www.weddslist.com/kgs/past/S11.2/index.html As usual, I will welcome your comments and corrections. Nick -- Nick Wedd n...@maproom.co.uk ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
[Computer-go] [Computer-go ] Congratulations to Zen!
Nick, thanks again for organizing and the new table. A conclusion that can be draw from the table is that, except for the 2nd and 3rd place of Pachi and MF which was very disputed and anyone could have won, the different ranks give very consistent results. Almost all games against lower ranked opponents are wins. And the 6th is Mogo! We really have a pool of strong programs. Congratulation to StoneGrid, I didn't know it was so strong consistently beating Mogo on these time settings. Points are harder to win than in Formula 1! But I really expect to finish this year above zero. ;-) PD. Thank you very much Aja! I am eager to try the Erica binary. I still use Silvain's Mogo despite its 15M nodes limit and Fuego of course. Erica will be welcome. I hope it can be set to fixed number of simulations and that it can run many sims with reasonable (say 2 Gb) limits. Jacques. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Direct DX11 and graphics cards for cheapersimulation
Doesn't the simple mathematics of why go is difficult make the 'faster hardware' topic a small issue? That's what the simple math says, but the complex math says that UCT is asymptotically optimal! Since math is internally consistent, it must be that increasing speed does help and the simple math is going wrong somewhere. MCTS is a selective search algorithm. The effective branching factor is very small. At most nodes you have only a handful of moves that are searched at all. Most of the nodes that are searched receive only a few trials. Increasing speed improves the outcome in two ways. First, you have more time to examine the better moves more deeply. Second, you can expand more moves at each node. A third potential advantage is to keep the tree the same size and do better analysis. That is, use the speed to reduce the error rate. If this is done by having heavy knowledge then the solution is not scalable. But you can also create online learning algorithms that improve analysis, which could be scalable. The problems that cause MCTS to hit a wall usually have to do with the RAVE heuristic, which is the preeminent selective method. If you start by disliking the best move, and the RAVE heuristic collects bad results for that move, then it could never get a trial. One of the problems is that as you scale the search you are also scaling the data collected by RAVE, so it becomes more convinced that the move is bad. There are solutions for this, though. Fuego simply turns off RAVE for a small fraction of trials. Another solution: don't use RAVE. I recall that Crazy Stone does not use RAVE. Maybe its static move ordering is really good, and Remi doesn't want to mess it up. If static move ordering is good enough, then you can get a scalable search by admitting N moves at trial f(N) where f grows exponentially. Brian ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] [Computer-go ] Congratulations to Zen!
PD. Thank you very much Aja! I am eager to try the Erica binary. I still use Silvain's Mogo despite its 15M nodes limit and Fuego of course. Erica will be welcome. I hope it can be set to fixed number of simulations and that it can run many sims with reasonable (say 2 Gb) limits. Yes, of course, it can be set to fixed number of simulations or time, with the limitation assigned by youself in the config file. Aja ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Zen19D is blitz 5d in KGS
This zen is running on 26 cores I think, so probably more like 10K to 20K simulations per second. Still, very impressive. We might find that the stronger programs do fewer simulations per second, since the recent growth in strength is mainly due to additional go knowledge, which must make playouts slower. Certainly Many Faces's playout per second on 19x19 is much lower today (at 2 dan, 2K PPS per core) than it was in 2008 (at 2 kyu, 6K PPS per core). David From: computer-go-boun...@dvandva.org [mailto:computer-go-boun...@dvandva.org] On Behalf Of fastgo Sent: Friday, June 03, 2011 5:58 AM To: computer-go@dvandva.org Subject: Re: [Computer-go] Zen19D is blitz 5d in KGS It is really amazing that on 19x19 with less than 1M simulations, it can reach 5D/6D level. Assuming 2K simulations/s, 15 seconds per move and 26 cores. I cannot even imagine a MC program could reach that level on 9x9 with only 1M simulations two years back. I would have to guess besides the smart logic in the playout side, there must be smarter logic on the tree part. If possible, it would be good to see some data from the strong bots how much each part contributes in the strength by turning off the heavy logic on the other part. On Fri, Jun 3, 2011 at 1:10 AM, Aja ajahu...@gmail.com wrote: Zen has some code to handle very simple semeais in the playouts. But I am not satisfied with the code. To solve the semeai issue fully, we will need a better algorithm to share the tree information with the simulation. Such some code to handle very simple semeais in the playouts is still very impressive. It's a pity that Yamato won't publish any paper about Zen's algorithms. But anyway it's clear that we need something new and BIG to solve semeai, rather than heavy knowledge implementation. Aja ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
[Computer-go] Computing Elo Ratings of Move Patterns in the, Game of Go (again) the MM tool
Hi, I've been busy writing some code to extract feature from position to feed the MM tool from Rémi. As I was reading the paper one more time I stopped on that sentence : Each value that these features can take is considered as a separate “individual”, and is associated to one strength parameter i. Since values within one feature are mutually exclusive, they were all updated together within one iteration of the minorization-maximization algorithm. For some reason I was feeding the MM tool differently, i.e. I have one feature per spatial pattern or game feature i.e. I don't have one feature for distance to border, I have 4 features for that (one feature for each distance). Also Rémi said he was using like 16k shapes, this would give me 16k features the way I doing atm and the MM tool would take days to output any results. To make it short, how to you feed the MM tool (I've joined the beginning of my input file). Additional question : I have millions of lines in that file since we have 1 mm game per real game move, each mm game has like 360 teams fighting on an empty board. Is that ok ? HJ. ! 419 419 1 f.0.none 1 f.1.cfg_distance_1 1 f.2.cfg_distance_2 1 f.3.cfg_distance_3 1 f.4.ft_mc_owner_0 1 f.5.ft_mc_owner_1 1 f.6.ft_mc_owner_2 1 f.7.ft_mc_owner_3 1 f.8.ft_mc_owner_4 1 f.9.ft_mc_owner_5 1 f.10.ft_mc_owner_6 1 f.11.ft_mc_owner_7 1 f.12.ft_reduce_to_1_lib 1 f.13.ft_reduce_to_2_lib 1 f.14.ft_reduce_to_3_lib 1 f.15.ft_atari_1_stone 1 f.16.ft_atari_2_stones 1 f.17.ft_atari_3_stones 1 f.18.ft_capture_1_stone 1 f.19.ft_capture_2_stones 1 f.20.ft_capture_3_stones 1 f.21.save_1_stone 1 f.22.save_2_stones 1 f.23.save_3_stones 1 f.24 1 f.25 1 f.26 1 f.27 1 f.28 1 f.29 1 f.30.border_distance_0 1 f.31.border_distance_1 1 f.32.border_distance_2 1 f.33.border_distance_3 1 f.34.selfatari 1 f.35.bad_selfatari 1 f.36.own_eye 1 sp.37.0 1 sp.38.1 1 sp.39.2 1 sp.40.3 1 sp.41.4 1 sp.42.5 1 sp.43.6 1 sp.44.7 1 sp.45.8 1 sp.46.9 1 sp.47.10 1 sp.48.11 1 sp.49.12 1 sp.50.13 1 sp.51.14 1 sp.52.15 1 sp.53.16 1 sp.54.17 1 sp.55.18 1 sp.56.19 1 sp.57.20 1 sp.58.21 1 sp.59.22 ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Computing Elo Ratings of Move Patterns in the, Game of Go (again) the MM tool
On 3 juin 2011, at 20:07, Harald Johnsen wrote: Hi, I've been busy writing some code to extract feature from position to feed the MM tool from Rémi. As I was reading the paper one more time I stopped on that sentence : Each value that these features can take is considered as a separate “individual”, and is associated to one strength parameter i. Since values within one feature are mutually exclusive, they were all updated together within one iteration of the minorization-maximization algorithm. For some reason I was feeding the MM tool differently, i.e. I have one feature per spatial pattern or game feature i.e. I don't have one feature for distance to border, I have 4 features for that (one feature for each distance). Also Rémi said he was using like 16k shapes, this would give me 16k features the way I doing atm and the MM tool would take days to output any results. To make it short, how to you feed the MM tool (I've joined the beginning of my input file). This is the wrong approach. What I call an individual is what some authors would call a binary feature, ie a bit of information indicating that a property is true or false. A feature is a collection of mutually exclusive individuals. So distance to previous move is a feature, and distance 1, distance 2, ... are different levels of that feature. distance to border is another feature. It must be another feature, because it is not mutually exclusive with distance to previous move, ie you can be at distance 1 from the previous move, and at distance 2 from the border at the same time. 3x3 shape is another separate feature, with as many levels as there are 3x3 shapes. I hope this makes things clearer. Rémi Additional question : I have millions of lines in that file since we have 1 mm game per real game move, each mm game has like 360 teams fighting on an empty board. Is that ok ? HJ. ! 419 419 1 f.0.none 1 f.1.cfg_distance_1 1 f.2.cfg_distance_2 1 f.3.cfg_distance_3 1 f.4.ft_mc_owner_0 1 f.5.ft_mc_owner_1 1 f.6.ft_mc_owner_2 1 f.7.ft_mc_owner_3 1 f.8.ft_mc_owner_4 1 f.9.ft_mc_owner_5 1 f.10.ft_mc_owner_6 1 f.11.ft_mc_owner_7 1 f.12.ft_reduce_to_1_lib 1 f.13.ft_reduce_to_2_lib 1 f.14.ft_reduce_to_3_lib 1 f.15.ft_atari_1_stone 1 f.16.ft_atari_2_stones 1 f.17.ft_atari_3_stones 1 f.18.ft_capture_1_stone 1 f.19.ft_capture_2_stones 1 f.20.ft_capture_3_stones 1 f.21.save_1_stone 1 f.22.save_2_stones 1 f.23.save_3_stones 1 f.24 1 f.25 1 f.26 1 f.27 1 f.28 1 f.29 1 f.30.border_distance_0 1 f.31.border_distance_1 1 f.32.border_distance_2 1 f.33.border_distance_3 1 f.34.selfatari 1 f.35.bad_selfatari 1 f.36.own_eye 1 sp.37.0 1 sp.38.1 1 sp.39.2 1 sp.40.3 1 sp.41.4 1 sp.42.5 1 sp.43.6 1 sp.44.7 1 sp.45.8 1 sp.46.9 1 sp.47.10 1 sp.48.11 1 sp.49.12 1 sp.50.13 1 sp.51.14 1 sp.52.15 1 sp.53.16 1 sp.54.17 1 sp.55.18 1 sp.56.19 1 sp.57.20 1 sp.58.21 1 sp.59.22 ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
