Re: [Computer-go] Congratulations to Zen!
I found the game between Zen19 (white) v.s pachi2 (black) in round 8 quite interesting. A big pachi2 group (left side) was killed and pachi2 kept adding stones to the dead group, while Zen19 seemed to understood the situation and played only to prevent eye forming moves. However, Zen19 failed two chances to prevent pachi2 from making the group into seki. With this group alive, pachi2 should have won the game, however, the official result is white (Zen19) win over resign. Am I missing something? Why didn't Zen19 see the seki situation? and why didn't pachi2 know that its group is already dead? Best, Fuming ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Congratulations to Zen!
Here is my understanding of it: The group is on the right side, not the left. White killed it, probably before move 170. Black wasted four moves (177, 261, 265, 281) enlarging it and leaving it dead in gote. At the end of the game it was still dead: White can kill by playing q6 to make the coolie's hat shape. That's right. Since it's lefted on the board, I just thought it was seki, and I counted wrong as well. Without killing the black group, the score is B=178, W=183 (splitting the two remaining points). So all is well, and Zen19 was in control all the time. Still, I'm wondering what's inside Zen19's head, removing all other dead stones while leaving just that big group, and predicting all those wasted moves by pachi2 leading to just 2 points win :) Best, Fuming ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Pachi Mailing List
(Also, we have finally set up a real (though simple) homepage for Pachi at http://pachi.or.cz/.) Happy go research, According to information on Pachi's homepage, Pachi won a 7h game against Zhou Junxun 9p, who is an active 9p player and has won at least one world title. I would say this put Pachi at top amature or beginning pro level. On the other hand, Pachi is around 3d on KGS, which I am not very familar, but I am guessing that it only proves that Pachi is at about median amature level. What's your assessment, and thinkings about this difference (if there is a difference in your assessment)? Best, Fuming ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Computing CFG distance in practice
I think I understand what CFG is. CFG distance between two string is the shortest distance between any stones of the two strings, is that right? Thanks, Fuming On Tue, Jan 25, 2011 at 1:58 PM, Aja ajahu...@gmail.com wrote: Common Fate Graph (CFG) was proposed in the paper Learning on Graphs in the Game of Go ( http://research.microsoft.com/apps/pubs/default.aspx?id=65629). In the game of Go, Except location proximity, I think liberty proximity is also important. That is to say, it's good to play proximity to the previous move, and also good to play proximity to the liberty points of the string that contains the previous move. Aja - Original Message - *From:* Fuming Wang fuming...@gmail.com *To:* computer-go@dvandva.org *Sent:* Tuesday, January 25, 2011 1:38 PM *Subject:* Re: [Computer-go] Computing CFG distance in practice how to calculate CFG distance? Fuming On Tue, Jan 25, 2011 at 3:49 AM, Brian Sheppard sheppar...@aol.comwrote: I use CFG distance only in the tree. The playout uses the concept adjacent which is trivial to compute. The only distance I am concerned about is the distance to the last move, and there are only 4 classes: distance 1,2,3, and 3. So it is cheap. The advantage is in semeais. Moves at CFG distance 3 are the outside liberties of the opponent's string. There was not a big difference compared to the other two heuristics. I found that - CFG is best - max(dx, dy) + (dx + dy)/2 is second best - Manhattan is third. Brian -Original Message- From: computer-go-boun...@dvandva.org [mailto:computer-go-boun...@dvandva.org] On Behalf Of Jacques Basaldúa Sent: Monday, January 24, 2011 2:41 PM To: computer-go@dvandva.org Subject: [Computer-go] Computing CFG distance in practice Hi, I got a lot of improvement recently (something you all did long time ago) with proximity heuristics. I am using Manhattan distance: d = max(dx, dy) and d = max(dx, dy) + (dx + dy)/2 where dx = abs(ex - ox) and dy = abs(ey - oy) But many people report CFG distance to be superior. What do you do: a. Compute it in root. Then build a lookup table and use the LUT during playouts and tree search. b. Compute the shortest path from (ox, oy) to (ex, ey) connected by the stones on the board each time you need to evaluate a distance. I don't like a because it looks inefficient as the board changes a lot during the search. I don't like b because it looks computing intense unless there is some smart idea I am missing. Jacques. ___ 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 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 mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Computing CFG distance in practice
Hi Brain, Thanks for the explanation. I understand the procedure would give a more meaningfull distance between an empty site and the last move. I went through the original paper again, and still could not figure out how this caluculation procedure is derived from that paper. CFG is a graph as defined in the paper, and it is used to train some neuro-network for Go playing. Could you or anyone point me to the place that CFG distance is first used? Best, Fuming On Tue, Jan 25, 2011 at 10:41 PM, Brian Sheppard sheppar...@aol.com wrote: CFG distance: 1) Start at the last move. That is the full set of points at distance 0. 2) Iterate, starting at N=1. Calculate the points at distance N by: 3) If an empty point is not at distance N and is adjacent to a point at distance N, then it is at distance N. 4) If an occupied point is not at distance N and is adjacent to a point at distance N, then all of the points on that string are at distance N. 5) I stop iterating at N=3. I have not checked whether there is useful information at higher N. Brian *From:* computer-go-boun...@dvandva.org [mailto: computer-go-boun...@dvandva.org] *On Behalf Of *Fuming Wang *Sent:* Tuesday, January 25, 2011 5:22 AM *To:* Aja; computer-go@dvandva.org *Subject:* Re: [Computer-go] Computing CFG distance in practice I think I understand what CFG is. CFG distance between two string is the shortest distance between any stones of the two strings, is that right? Thanks, Fuming On Tue, Jan 25, 2011 at 1:58 PM, Aja ajahu...@gmail.com wrote: Common Fate Graph (CFG) was proposed in the paper Learning on Graphs in the Game of Go ( http://research.microsoft.com/apps/pubs/default.aspx?id=65629). In the game of Go, Except location proximity, I think liberty proximity is also important. That is to say, it's good to play proximity to the previous move, and also good to play proximity to the liberty points of the string that contains the previous move. Aja - Original Message - *From:* Fuming Wang fuming...@gmail.com *To:* computer-go@dvandva.org *Sent:* Tuesday, January 25, 2011 1:38 PM *Subject:* Re: [Computer-go] Computing CFG distance in practice how to calculate CFG distance? Fuming On Tue, Jan 25, 2011 at 3:49 AM, Brian Sheppard sheppar...@aol.com wrote: I use CFG distance only in the tree. The playout uses the concept adjacent which is trivial to compute. The only distance I am concerned about is the distance to the last move, and there are only 4 classes: distance 1,2,3, and 3. So it is cheap. The advantage is in semeais. Moves at CFG distance 3 are the outside liberties of the opponent's string. There was not a big difference compared to the other two heuristics. I found that - CFG is best - max(dx, dy) + (dx + dy)/2 is second best - Manhattan is third. Brian -Original Message- From: computer-go-boun...@dvandva.org [mailto:computer-go-boun...@dvandva.org] On Behalf Of Jacques Basaldúa Sent: Monday, January 24, 2011 2:41 PM To: computer-go@dvandva.org Subject: [Computer-go] Computing CFG distance in practice Hi, I got a lot of improvement recently (something you all did long time ago) with proximity heuristics. I am using Manhattan distance: d = max(dx, dy) and d = max(dx, dy) + (dx + dy)/2 where dx = abs(ex - ox) and dy = abs(ey - oy) But many people report CFG distance to be superior. What do you do: a. Compute it in root. Then build a lookup table and use the LUT during playouts and tree search. b. Compute the shortest path from (ox, oy) to (ex, ey) connected by the stones on the board each time you need to evaluate a distance. I don't like a because it looks inefficient as the board changes a lot during the search. I don't like b because it looks computing intense unless there is some smart idea I am missing. Jacques. ___ 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 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 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
Re: [Computer-go] Computing CFG distance in practice
Got it. Thanks! Best, Fuming On Wed, Jan 26, 2011 at 4:51 AM, Brian Sheppard sheppar...@aol.com wrote: I believe it was a suggestion of the Mogo team. One of their papers refers to a topological distance defined as the Manhattan distance but where all points on the same string are at the same distance. it should be clear how this definition leads to the algorithm below. Brian *From:* computer-go-boun...@dvandva.org [mailto: computer-go-boun...@dvandva.org] *On Behalf Of *Fuming Wang *Sent:* Tuesday, January 25, 2011 3:42 PM *To:* computer-go@dvandva.org *Subject:* Re: [Computer-go] Computing CFG distance in practice Hi Brain, Thanks for the explanation. I understand the procedure would give a more meaningfull distance between an empty site and the last move. I went through the original paper again, and still could not figure out how this caluculation procedure is derived from that paper. CFG is a graph as defined in the paper, and it is used to train some neuro-network for Go playing. Could you or anyone point me to the place that CFG distance is first used? Best, Fuming On Tue, Jan 25, 2011 at 10:41 PM, Brian Sheppard sheppar...@aol.com wrote: CFG distance: 1) Start at the last move. That is the full set of points at distance 0. 2) Iterate, starting at N=1. Calculate the points at distance N by: 3) If an empty point is not at distance N and is adjacent to a point at distance N, then it is at distance N. 4) If an occupied point is not at distance N and is adjacent to a point at distance N, then all of the points on that string are at distance N. 5) I stop iterating at N=3. I have not checked whether there is useful information at higher N. Brian *From:* computer-go-boun...@dvandva.org [mailto: computer-go-boun...@dvandva.org] *On Behalf Of *Fuming Wang *Sent:* Tuesday, January 25, 2011 5:22 AM *To:* Aja; computer-go@dvandva.org *Subject:* Re: [Computer-go] Computing CFG distance in practice I think I understand what CFG is. CFG distance between two string is the shortest distance between any stones of the two strings, is that right? Thanks, Fuming On Tue, Jan 25, 2011 at 1:58 PM, Aja ajahu...@gmail.com wrote: Common Fate Graph (CFG) was proposed in the paper Learning on Graphs in the Game of Go ( http://research.microsoft.com/apps/pubs/default.aspx?id=65629). In the game of Go, Except location proximity, I think liberty proximity is also important. That is to say, it's good to play proximity to the previous move, and also good to play proximity to the liberty points of the string that contains the previous move. Aja - Original Message - *From:* Fuming Wang fuming...@gmail.com *To:* computer-go@dvandva.org *Sent:* Tuesday, January 25, 2011 1:38 PM *Subject:* Re: [Computer-go] Computing CFG distance in practice how to calculate CFG distance? Fuming On Tue, Jan 25, 2011 at 3:49 AM, Brian Sheppard sheppar...@aol.com wrote: I use CFG distance only in the tree. The playout uses the concept adjacent which is trivial to compute. The only distance I am concerned about is the distance to the last move, and there are only 4 classes: distance 1,2,3, and 3. So it is cheap. The advantage is in semeais. Moves at CFG distance 3 are the outside liberties of the opponent's string. There was not a big difference compared to the other two heuristics. I found that - CFG is best - max(dx, dy) + (dx + dy)/2 is second best - Manhattan is third. Brian -Original Message- From: computer-go-boun...@dvandva.org [mailto:computer-go-boun...@dvandva.org] On Behalf Of Jacques Basaldúa Sent: Monday, January 24, 2011 2:41 PM To: computer-go@dvandva.org Subject: [Computer-go] Computing CFG distance in practice Hi, I got a lot of improvement recently (something you all did long time ago) with proximity heuristics. I am using Manhattan distance: d = max(dx, dy) and d = max(dx, dy) + (dx + dy)/2 where dx = abs(ex - ox) and dy = abs(ey - oy) But many people report CFG distance to be superior. What do you do: a. Compute it in root. Then build a lookup table and use the LUT during playouts and tree search. b. Compute the shortest path from (ox, oy) to (ex, ey) connected by the stones on the board each time you need to evaluate a distance. I don't like a because it looks inefficient as the board changes a lot during the search. I don't like b because it looks computing intense unless there is some smart idea I am missing. Jacques. ___ 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
Re: [Computer-go] Computing CFG distance in practice
how to calculate CFG distance? Fuming On Tue, Jan 25, 2011 at 3:49 AM, Brian Sheppard sheppar...@aol.com wrote: I use CFG distance only in the tree. The playout uses the concept adjacent which is trivial to compute. The only distance I am concerned about is the distance to the last move, and there are only 4 classes: distance 1,2,3, and 3. So it is cheap. The advantage is in semeais. Moves at CFG distance 3 are the outside liberties of the opponent's string. There was not a big difference compared to the other two heuristics. I found that - CFG is best - max(dx, dy) + (dx + dy)/2 is second best - Manhattan is third. Brian -Original Message- From: computer-go-boun...@dvandva.org [mailto:computer-go-boun...@dvandva.org] On Behalf Of Jacques Basaldúa Sent: Monday, January 24, 2011 2:41 PM To: computer-go@dvandva.org Subject: [Computer-go] Computing CFG distance in practice Hi, I got a lot of improvement recently (something you all did long time ago) with proximity heuristics. I am using Manhattan distance: d = max(dx, dy) and d = max(dx, dy) + (dx + dy)/2 where dx = abs(ex - ox) and dy = abs(ey - oy) But many people report CFG distance to be superior. What do you do: a. Compute it in root. Then build a lookup table and use the LUT during playouts and tree search. b. Compute the shortest path from (ox, oy) to (ex, ey) connected by the stones on the board each time you need to evaluate a distance. I don't like a because it looks inefficient as the board changes a lot during the search. I don't like b because it looks computing intense unless there is some smart idea I am missing. Jacques. ___ 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 mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Fwd: News on Tromp-Cook ?
Hi Aja, On Sun, Jan 2, 2011 at 1:29 AM, Aja ajahu...@gmail.com wrote: Hi Fuming, C*RAVE+(1-C)*UCT C is computed dynamically in search, but not set to a fixed value. Maybe you mean UCT_C, UCT=UCT_mean+UCT_C*exploration_term What Petr and Olivier do, I think, is set UCT_C to 0, to disable the exploration_term, not the weight of RAVE. Without the exploring term, the UCT is just mean win rate, so there's no point in calling it UCT or UCB. Basically, what people have been saying is that currently the tree search is based on combination of sequence dependent rate (average win rate) and sequence independent/almost independent (rave rate) instead of combination of exploitation (win rate) and exploration (UCB term). Is this understanding close? Fuming ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Fwd: [computer-go] Experiments with UCT
Got it. Thx. Fuming On Fri, Dec 31, 2010 at 10:25 PM, Go Fast fas...@gmail.com wrote: -- Forwarded message -- From: Rémi Coulom remi.cou...@free.fr Date: Tue, Jul 25, 2006 at 8:22 AM Subject: [computer-go] Experiments with UCT To: computer-go computer...@computer-go.org Hi, I mentioned UCT in one of my previous messages to the list: http://zaphod.aml.sztaki.hu/papers/ecml06.pdf I tried it in Crazy Stone. I found that the algorithm described in the paper does not work well, but I managed to improve it a lot with a small change: I used 1/sqrt(20) instead of 1/sqrt(2) for the C_p constant. It now seems to work very well. Here is a summary of how it works: - Use probability of winning as score, not territory - Use the average outcome as position value - Select the move that maximizes v + sqrt((2*log(t))/(10*n)) v is the value of the move (average outcome, between 0 and 1), n the number of simulations of this move, and t the total number of simulations at the current position. In case a move has n = 0, it is selected first. Here are experiment results with Crazy Stone. 170 games are played against GNU Go 3.6 at level 10, from 85 different starting positions, alternating colors, at various time control (time per game), 1 CPU at 2.2 GHz. version 0005 UCT 2 min 40% 46.7% 4 min 48.2% 56.6% 8 min 52.9% 64.7% 16 min 57.4% 67.6% 32 min 66.6% 71.6% I have tried hard to improve it, but it seems very difficult. Using a more clever backup operator may help, but I have not managed to measure a significant difference yet. I thank Yizao for letting me know about UCT. His program, MoGo, seems to be doing very well on CGOS. Maybe Yizao can tell us more about his experiments. Rémi ___ computer-go mailing list computer...@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ 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
Re: [Computer-go] How to Research Brilliantly?
On Fri, Dec 31, 2010 at 3:49 PM, David Fotland fotl...@smart-games.comwrote: Monte Carlo go was around for a long time. See Bouzy's papers for example. The UCT formula for balancing exploration and exploitation came from research on the one-armed bandit problem, not related to go. Mogo and Crazystone's contributions were to show that monte carlo go could be competitive with traditional programs, after a decade or more when monte carlo was weaker. Exactly, without Mogo and Crazystone, we would still be just as good as traditional programs, i.e. not as good as today's strong programs. Regards, Fuming ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Fwd: News on Tromp-Cook ?
Hi Remi, Thanks for the suggestions. Sorry for inaccuracies in my previous statements. Now I have read your paper more carefully, I find in the appendex many discussions related to improvements on playout move selections. On another note, I find that formula you gave on variance calculation very interesting. I am a little confused on the meaning of symble sigma in the formula, is it the number of wins of S trials? If that's the case, then the meaning of sigma_sup(2) can not be easily understood. Best regards, Fuming On Fri, Dec 31, 2010 at 8:31 PM, Rémi Coulom remi.cou...@free.fr wrote: Hi, I'd like to advise against using the exact algorithm I described in my 2006 paper. I compared it to UCT at that time, and UCT performed better. I am sorry I don't have a reference to my data any more. I posted the results to the mailing list. It used to be archived at that link: http://computer-go.org/pipermail/computer-go/2006-July/005737.html I hope somebody kept an archive an can forward it to the list. The title of that message was Experiments with UCT. It is too bad that the archive of that time is gone. Is it available anywhere? The google archive starts later. The biggest difference between the general MCTS idea I proposed and the UCT-like algorithms everybody is using today is that the backup operator was not the mean of playouts. I tried to consider selectivity and backup independently. I still believe it is a powerful idea. My feeling is that a good backup operator should be able to make a good decision independently of selectivity. That is to say, even if all the moves are explored uniformly, the backup operator should converge to min/max. Backing up the mean forces current programs to be extremely selective so that they rapidly converges to min/max. The only part of the tree where it is not important to converge rapidly to min/max is the root. I am aware of some experiments that indicate that being less selective at the root may improve strength. The efficiency of root parallelization may also be an indication that current algorithms are too selective at the root. So my vague intuition is that it may be worth trying to find a good backup operator that works with less selective search. Anyway, tweaking the MCTS formula you are using will never make your program very strong. Clever playouts are immensely more important, especially for 19x19. Rémi On 31 déc. 2010, at 07:02, Fuming Wang wrote: -- Forwarded message -- From: Fuming Wang fuming...@gmail.com Date: Fri, Dec 31, 2010 at 1:50 PM Subject: Re: [Computer-go] News on Tromp-Cook ? To: Aja ajahu...@gmail.com Hi Aja, Remi and S. Gelly's paper both come out in 2006,and I just checked that they did not reference each other. I just read Remi's paper again, and realized that CrazyStone's tree search approach is actually different from the popular UCT method. Similar to you, I haven't been able to get good results from the popular UCT method, so I might try CrazyStone's method for a change. In Remi's paper, CrazyStone is only having around 30% winning rate against Gnu Go 3.6, and now Erica is winning world competitions,this actually proves that high quality MC simulation (realized for the first time in MoGo) is more important than tree search algorithms. Best regards, Fuming ___ 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
Re: [Computer-go] News on Tromp-Cook ?
That was such an amazingly crazy period. I am sure some day, some one will write a book (or two) about all of this, so that latecomers get to know all the details. Best Wishes! Fuming On Sat, Jan 1, 2011 at 12:22 AM, Ingo Althöfer 3-hirn-ver...@gmx.dewrote: ... but championship events are relatively poor predictors of skill because of their limited number of sample points. something like cgos ranking over time (among those who participate) is a pretty good way to compare computer go playing programs. Both types of competition do have their justification. It is similar to sports: the one with the best average 100 meter speed (taking over the summer) will be top in a list, and the winner of the olympic gold medal will have lots of prestige. At least some programmers use CGOS and KGS simply for testing this and that, and only at the big events (like computer olympiads) their seemingly strongest version (including opening book, pattern data bases and so on) is presented. My list was meant in a slightly different sense: MoGo as a Go program simply was not there in 2006, when Crazy Stone started to run up the charts. And it is typically easier (also psychologically) to attack some goal when someone else has shown before that it is in principle possible to achieve. Happy new year, Ingo. -- GMX DSL Doppel-Flat ab 19,99 Euro/mtl.! Jetzt auch mit gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl ___ 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
Re: [Computer-go] News on Tromp-Cook ?
This is certainly a good time to sit back and look at what got us here. The following key ideas have been mentioned so far: UCB, MCTS, RAVE, Pattern and Go knowledge during MC simulation.These ideas are all essential to a strong MC based Go program.If we want to pick the most important idea that got us here, I would say it is the realization that adding Go Pattern and Go Knowledge to MC simulation can significantly improve the quality of board evaluation. This is amount to the important sampling concept in MC integration, which is very import for Monte Carlo applications in many fields. MC simulation with importance sampling give us for the first time a reasonablly accurate evaluation function for Go. UCB, MCTS, RAVE are certainly very important, however, it is still possible that new approaches that can achieve good results with just importantly samples MC simulation. So, I think MoGo is the most important break-through. Happy New Year, everyone! Fuming On Fri, Dec 31, 2010 at 9:20 AM, Aja ajahu...@gmail.com wrote: Hi Jeff, When, do you think, did Mogo started dominating all the KGS computer events and CGOS, and also was the first to extend that dominance from 9x9 to 19x19.? In Computer Olympiad 2007, Steenvreter was gold medal on 9x9. At the final match of 19x19, it's easily to see that Mogo and Crazy Stone were close (finally Mogo 1st and CS 2ed). But, at the end of 2007, Crazy Stone defeated Mogo and won the UEC Cup (19x19). Afterwards, Many Faces won 9x9 and 19x19 on 2008. Zen and Erica won 2009 and 2010, both continuing Crazy Stone thread. Mogo's biggest contributions, so far, in my view, are 1.Applied UCT to computer Go, and such application came from the idea MCTS that proposed in 2006 by Remi Coulom. Crazy Stone was using MCTS to win 9x9 in 2006 Computer Olympiad. 2.See 3x3 patterns around the previous move. 3.RAVE (strictly speaking, it is invented by David Silver). UCT and RAVE are for both for the tree search. I think Crazy tone's contribution for the playout is of same/or more important, because the quality of simulations decide the playing strength much. From this view, we should give Crazy Stone more and more credit. I don't mean to raise any debate. Mogo does has important contributions, but it's not so hard to assign credit to Crazy Stone. By the way, we should not forget Fuego and MyGoFriend. Anyway, I think SenSei's description is out-of-date. Aja -原始郵件- From: Jeff Nowakowski Sent: Friday, December 31, 2010 5:43 AM To: computer...@computer-go.org Subject: Re: [Computer-go] News on Tromp-Cook ? On 12/30/2010 01:58 PM, David Fotland wrote: You should also give more credit to CrazyStone as an early strong program that contributed many ideas, comparable to Mogo. Remi is Aja's advisor, so Erica continues the CrazyStone thread. I did mention CrazyStone, and the Sensei's page lists it first as the program that started the new wave of MCTS programs by winning the 9x9 gold medal at the ICGA Computer Olympiad, in 2006. Like I said in my first message, though, it's hard to assign credit, and I don't mean to slight other programs. However, MoGo was the program that really got people to sit up and take notice, because it started dominating all the KGS computer events and CGOS, and also was the first to extend that dominance from 9x9 to 19x19. I believe the biggest breakthroughs were made with MoGo (building, of course, on earlier ideas). This is easily verified by going back to the archives and seeing how many people patterned their program after MoGo. ___ 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 mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
[Computer-go] Fwd: News on Tromp-Cook ?
-- Forwarded message -- From: Fuming Wang fuming...@gmail.com Date: Fri, Dec 31, 2010 at 1:50 PM Subject: Re: [Computer-go] News on Tromp-Cook ? To: Aja ajahu...@gmail.com Hi Aja, Remi and S. Gelly's paper both come out in 2006,and I just checked that they did not reference each other. I just read Remi's paper again, and realized that CrazyStone's tree search approach is actually different from the popular UCT method. Similar to you, I haven't been able to get good results from the popular UCT method, so I might try CrazyStone's method for a change. In Remi's paper, CrazyStone is only having around 30% winning rate against Gnu Go 3.6, and now Erica is winning world competitions,this actually proves that high quality MC simulation (realized for the first time in MoGo) is more important than tree search algorithms. Best regards, Fuming On Fri, Dec 31, 2010 at 12:41 PM, Aja ajahu...@gmail.com wrote: Hi Fuming, The idea of improving the quality of simulation is more earlier, than Mogo’s paper, in the Appendix A of Remi Coulom’s CG2006 paper “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search”( http://remi.coulom.free.fr/CG2006/CG2006.pdf): The choice of a more clever probability distribution can improve the quality of the Monte-Carlo estimation I am not sure if Remi was the first one proposing this concept in Computer Go field, but Mogo definitely was not. I was in Amstertam attending Computer Olympiad 2007, in the team of Chinese chess program “Deep Elephant”. I played with Crazy Stone, Mogo and was very surprised to see they beat me. Afterwards, Mogo’s paper is so easy to understand/implement for me that trigger me to work on Computer Go. Indeed, Mogo has huge contributions, especially in the popularization of MCTS. I don’t mean to weaken or deny it, but just want to point out Crazy Stone’s great contributions. In Erica, I use CrazyStone-like simulations successfully. Mogo-type simulation almost does not help Erica at all. If we want to numerate the strongest programs, we cannot forget Fuego(2010 UEC Cup winner) and MyGoFriend(Computer Olympiad 2010, 9x9 winner). For academic progress, we cannot forget Crazy Stone. For practical development usage, we cannot forget GnuGo and GoGui released by Fuego team. There were really too many contributors in the past. Happy New Years to all. Aja *From:* Fuming Wang fuming...@gmail.com *Sent:* Friday, December 31, 2010 10:16 AM *To:* Aja ajahu...@gmail.com ; computer-go@dvandva.org *Subject:* Re: [Computer-go] News on Tromp-Cook ? This is certainly a good time to sit back and look at what got us here. The following key ideas have been mentioned so far: UCB, MCTS, RAVE, Pattern and Go knowledge during MC simulation.These ideas are all essential to a strong MC based Go program.If we want to pick the most important idea that got us here, I would say it is the realization that adding Go Pattern and Go Knowledge to MC simulation can significantly improve the quality of board evaluation. This is amount to the important sampling concept in MC integration, which is very import for Monte Carlo applications in many fields. MC simulation with importance sampling give us for the first time a reasonablly accurate evaluation function for Go. UCB, MCTS, RAVE are certainly very important, however, it is still possible that new approaches that can achieve good results with just importantly samples MC simulation. So, I think MoGo is the most important break-through. Happy New Year, everyone! Fuming On Fri, Dec 31, 2010 at 9:20 AM, Aja ajahu...@gmail.com wrote: Hi Jeff, When, do you think, did Mogo started dominating all the KGS computer events and CGOS, and also was the first to extend that dominance from 9x9 to 19x19.? In Computer Olympiad 2007, Steenvreter was gold medal on 9x9. At the final match of 19x19, it's easily to see that Mogo and Crazy Stone were close (finally Mogo 1st and CS 2ed). But, at the end of 2007, Crazy Stone defeated Mogo and won the UEC Cup (19x19). Afterwards, Many Faces won 9x9 and 19x19 on 2008. Zen and Erica won 2009 and 2010, both continuing Crazy Stone thread. Mogo's biggest contributions, so far, in my view, are 1.Applied UCT to computer Go, and such application came from the idea MCTS that proposed in 2006 by Remi Coulom. Crazy Stone was using MCTS to win 9x9 in 2006 Computer Olympiad. 2.See 3x3 patterns around the previous move. 3.RAVE (strictly speaking, it is invented by David Silver). UCT and RAVE are for both for the tree search. I think Crazy tone's contribution for the playout is of same/or more important, because the quality of simulations decide the playing strength much. From this view, we should give Crazy Stone more and more credit. I don't mean to raise any debate. Mogo does has important contributions, but it's not so hard to assign credit to Crazy Stone. By the way, we should not forget Fuego and MyGoFriend
Re: [Computer-go] intel i5 760 vs amd Phenom II X6 1055T
I have bought a AMD phenom II x4 965 with 4 cores at 3.6 GHz. I have tested against intel i5 760 with 4 core at 2.8 GHz. I made two tests, one with pure integer operation (MC Go simulation), another with some floating point operation (some other type of MC simulation). The result is quite interesting. The intel cpu is 20% faster on simulation containing some floating point operation, while the AMD cpu is 20% faster on pure integer operation (MC Go simulation). So, basically, what i found is that intel i5 and AMD phenom II of same frequency has similar performanc(5% slower) on pure integer operation. So amd 1090T with six cores would have about 50% performance gain on i5 760 with 4 cores. Hope this is helpful to people who building Go playing clusters. Best, Fuming On Tue, Nov 30, 2010 at 7:49 PM, Fuming Wang fuming...@gmail.com wrote: I have settled on i5 760, but I'm thinking of purchasing a 1090T soon, so hopefully, I will have a report soon. Fuming On Tue, Nov 30, 2010 at 10:46 AM, Petr Baudis pa...@ucw.cz wrote: On Tue, Nov 30, 2010 at 10:30:49AM +0800, Fuming Wang wrote: I am not doing any tree updates, just pure MC simulation. Ok, I see! 1090T has 6 core and i5 has 4 core, however i5 is better at level 3 caching (I've been told), so don't know which factor dominates. I do not think you really need L3 for anything in case of just pure MC simulation, unless your board structure is prohibitively large? i7 920 with 6 core should definitely better than 1090T. i7-920 has just four cores. And the benchmarks I have seen had been _far_ from clearly in favor even of the i7 iterations newer than 920. Overally, it seems to boil down to the particular workload. So I'm really curious. Petr Pasky Baudis ___ 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
Re: [Computer-go] Congratulations to Zen!
Thanks Nick. Sorry for the delay caused by sf9x9bot. I think I have got the kgs-genmove_cleanup command handled correctly after the last round. The followings are some tips that may be helpful for new comers of kgs tournaments: (1)I read the kgsGtp document, but failed to realize that kgs-genmove_cleanrup actually has an arguement instead of just the command itself. So instead one token from 'kgs-genmove_cleanup', I got two tokens from 'kgs-genmove_cleanup b', with the argument stating the color of my engine. This messed up my gtp processing code, and it took a while for me to found this cause. (2)kgsGtp sends a 'quit' command to engine after a game. Initially, I ignored this command, then stuff happens, like resigning at the first move, or sending ridiculous moves at the beginning of the game (first or second move on edge). I think the reason is that kgsGtp send multiple copies of a message to the server, and when the next game starts immediately after the previous one, messages from the previous one can be delivered to the next game. I fixed this by terminate the engine process after receiving the 'quit' command, and causing either kgsGtp to restart the engine again or kgsGtp itself get restarted again, this seems to have fixed the problem. There are other issues are mainly relate to my engine implementation. Anyway, thanks a lot for making this happen, and I'm already looking forward to the next tournament. Fuming On Tue, Dec 7, 2010 at 5:51 AM, Nick Wedd n...@maproom.co.uk wrote: Congratulations to Zen9, winner of yesterday's KGS 9x9 bot tournament! My report is now at http://www.weddslist.com/kgs/past/66/index.html Nick -- Nick Weddn...@maproom.co.uk ___ 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
Re: [Computer-go] intel i5 760 vs amd Phenom II X6 1055T
I have settled on i5 760, but I'm thinking of purchasing a 1090T soon, so hopefully, I will have a report soon. Fuming On Tue, Nov 30, 2010 at 10:46 AM, Petr Baudis pa...@ucw.cz wrote: On Tue, Nov 30, 2010 at 10:30:49AM +0800, Fuming Wang wrote: I am not doing any tree updates, just pure MC simulation. Ok, I see! 1090T has 6 core and i5 has 4 core, however i5 is better at level 3 caching (I've been told), so don't know which factor dominates. I do not think you really need L3 for anything in case of just pure MC simulation, unless your board structure is prohibitively large? i7 920 with 6 core should definitely better than 1090T. i7-920 has just four cores. And the benchmarks I have seen had been _far_ from clearly in favor even of the i7 iterations newer than 920. Overally, it seems to boil down to the particular workload. So I'm really curious. Petr Pasky Baudis ___ 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] intel i5 760 vs amd Phenom II X6 1055T
These two has simular prices. Any one know which cpu is better for Go MC simulation? ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] XMU-FPGA
No, I am not familar with Zeon-FPGA. Could you post a link? Google search is not very informative. Thanks, Fuming On Fri, Nov 19, 2010 at 5:47 AM, terry mcintyre terrymcint...@yahoo.comwrote: I am curious, what sort of hardware was used for XMU-FPGA? Are you familiar with Convey's Zeon-FPGA hybrids, which use an FPGA as a coprocessor? Terry McIntyre terrymcint...@yahoo.com Unix/Linux Systems Administration Taking time to do it right saves having to do it twice. ___ 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
Re: [Computer-go] XMU-FPGA
Found it. Convey Computer Corporation. There is quite a difference though. They are providing a general computing platform with customizable instructions, while we just designed a circuit for a specific application. Fuming On Fri, Nov 19, 2010 at 8:46 PM, Michael Williams michaelwilliam...@gmail.com wrote: Try the correct spelling instead -- Convey Xeon FPGA. On Fri, Nov 19, 2010 at 6:45 AM, Fuming Wang fuming...@gmail.com wrote: No, I am not familar with Zeon-FPGA. Could you post a link? Google search is not very informative. Thanks, Fuming On Fri, Nov 19, 2010 at 5:47 AM, terry mcintyre terrymcint...@yahoo.com wrote: I am curious, what sort of hardware was used for XMU-FPGA? Are you familiar with Convey's Zeon-FPGA hybrids, which use an FPGA as a coprocessor? Terry McIntyre terrymcint...@yahoo.com Unix/Linux Systems Administration Taking time to do it right saves having to do it twice. ___ 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 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
Re: [Computer-go] 9x9 opening data (was: XMU-FPGA)
Darren, I was able to parse the file without any problem. I considered all board configurations in file as GOOD positions, so that any move that can reach any board position in the file is considered a good move or a hit. I was testing against GNU Go,and wasn't get much hit after 2 moves, which is about the same as my small open book build out of 100 professional games, which seems strange to me. Anyway, I could have made a mistake here or there in rush of time because I was preparing for the competition. I will test it again, now I have more time. Fuming On Fri, Nov 12, 2010 at 9:01 AM, Darren Cook dar...@dcook.org wrote: By the way, I tried to use the game record data you posted on the web, but has pretty low hit-rate during tests. So I had to use my own calculated one for the competition. It seems strange to me that you have so many games recorded and has such low hit-rate. Can you tell me how you used it? Did you have any trouble with the format? Perhaps you have some advice for other people starting to look at it? (It is difficult to write documentation as the author, as everything is obvious.) I imagine it is difficult to use it as-is for an opening book, without some processing. (E.g. putting all the positions into an alpha-beta tree and scoring all nodes that way, then storing the joint-best moves from each node.) Did you do anything like that? Poor hit rate could be due to weak opponents who play bad moves and leave the book early? It is also quite focused on the tengen-opening. (E.g. roughly 30,000 games (*) from 5,5; 10,000 from 3,4, 5000 for each of 4,4 and 3,4.) Darren *: where a game is defined as the first 12 moves of the game. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] XMU-FPGA
Here is a link that has information about the competition event we participated. It is in Chinese, but has a few pictures. http://caai.cn/contents/15/2335.html Fuming On Tue, Nov 9, 2010 at 8:42 PM, Fuming Wang fuming...@gmail.com wrote: Our FPGA implementation of 9x9 Go, XMU-FPGA, had just participated a national Computer games competition event in Beijing, China. There are 6 participant in 9x9 Go category, with one of them quite strong (Lingo), while 3 others with reasonable strengths,including XMU-FPGA (about as strong as gnu go 3.8). XMU-FPGA did quite well, and finished second place after Lingo. Details of our FPGA implementation has been published at a recent conference, and people interested can send me email in private for a copy of the paper. Best regards, Fuming Wang ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] XMU-FPGA
Other than Beili Cup, which is better than google's North Li Cup, the google's translation is slightly more understandable than Bing's. Fuming On Thu, Nov 11, 2010 at 11:01 PM, Brian Sheppard sheppar...@aol.com wrote: To my surprise, Bing translated that page to quite understandable English. *From:* computer-go-boun...@dvandva.org [mailto: computer-go-boun...@dvandva.org] *On Behalf Of *Fuming Wang *Sent:* Thursday, November 11, 2010 5:33 AM *To:* computer-go@dvandva.org *Subject:* Re: [Computer-go] XMU-FPGA Here is a link that has information about the competition event we participated. It is in Chinese, but has a few pictures. http://caai.cn/contents/15/2335.html Fuming On Tue, Nov 9, 2010 at 8:42 PM, Fuming Wang fuming...@gmail.com wrote: Our FPGA implementation of 9x9 Go, XMU-FPGA, had just participated a national Computer games competition event in Beijing, China. There are 6 participant in 9x9 Go category, with one of them quite strong (Lingo), while 3 others with reasonable strengths,including XMU-FPGA (about as strong as gnu go 3.8). XMU-FPGA did quite well, and finished second place after Lingo. Details of our FPGA implementation has been published at a recent conference, and people interested can send me email in private for a copy of the paper. Best regards, Fuming Wang ___ 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] XMU-FPGA
Our FPGA implementation of 9x9 Go, XMU-FPGA, had just participated a national Computer games competition event in Beijing, China. There are 6 participant in 9x9 Go category, with one of them quite strong (Lingo), while 3 others with reasonable strengths,including XMU-FPGA (about as strong as gnu go 3.8). XMU-FPGA did quite well, and finished second place after Lingo. Details of our FPGA implementation has been published at a recent conference, and people interested can send me email in private for a copy of the paper. Best regards, Fuming Wang ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] monte carlo weakness
I am amazed at the rating that Valk3.5_100 got with just 100 playouts/move. There are usually around 50 candidate move, and 100 playouts would give each candidate just 2 playouts. It still amazes me how you can get reasonable statistics with just 2 playouts. Statistically, this is unthinkable. I am guessing that your playout engine has a lot of Go ability in itself, so that every playout gives meaningful feedback, instead of relying on the statistics of lots of playouts. Please enlight me. Regards, Fuming On Wed, Sep 8, 2010 at 5:37 AM, valky...@phmp.se wrote: Quoting Dave Dyer dd...@real-me.net: But you have never (to my knowledge) layed out what way that is. You're quite right here. I'm not advocating a specific change, just pointing out that all the effort going into building faster monte carlo engines may be irrelevant, because the programs actually need better steering. I have been working on Valkyria since 2006. Everytime I do something it becomes slower. Meanwhile it has become about 1000 Elo points stronger (Only 200 Elo is due to faster computer). If you talk about people on running their programs on as large clusters as possible, then I may agree, but otherwise I think you misunderstand completely what people are doing to improve their programs. I know we disagree on this point, but I believe chess has reached it's current state of success MOSTLY because of Moore's law. It always was believed that Go was would have to be solved by other means, perhaps even (gasp!) understanding the game. Monte carlo has given some credibility to the theory that Moores law may be enough after all. I'm arguing not. Monte-carlo search *is* the other means. Random exploration is exactly what I do when I play go. The only difference is that my search is goal directed so many playouts is just a 3-10 ply deep locally. As consequence I am weaker than MC-program in actually evaluating the whole board position. This weakness means I have to painfully compensate for it by counting territory to set the ambition for the goals I search. I sometime have a great intutions about playing some vital point. This caused by nothing else but the human variant of AMAF. Sure I do have a rich set of concepts that pop up in my thinking. But I am afraid that this are just labels that I attach to my search results. I think higher level concepts are very important for communicating about go, but they are irrelevant for actually playing well. The kind of knowledge about go that actally is essential for computers and humans is the ability to play tactically correct quick and without error. This means undrstanding LD, seki, semeai, ladders and so on. And this is also what makes Valkyria strong. The reason Valkyria is not yet unbeatable is that the knowledge the playouts have is still on a kyu level and very fragmented. There are situations where I see the obious move in an instant where Valkyria needs to search using several 100 playouts to get it right. In many cases it plays perfect 100% of the time. Get the fundmental knowledge right + MCTS = strong go This has nothing to do with Moores Law. Valk3.5_100 is rated 1881 for 9x9 which is stronger than Gnugo. It only plays 100 playouts. When I started doing MC evaluation with Viking5 in 2005 I had to spend 10 playouts to get close to beating gnugo. Just another perspective Magnus ___ 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 mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Fuego 04 native Windows
Rene, On Tue, Jun 22, 2010 at 9:58 AM, René van de Veerdonk rene.vandeveerd...@gmail.com wrote: Fuming and Petr, I was giving the tree-search some thought over the weekend and made some crude estimates based on my own MCTS implementation. I did not make fresh timing measurements, just added/subtracted some numbers to get to where I want to be. Assuming you want to maintain RAVE and win-rate information, I am guesstimating that for my quasi-heavy playouts I find an overhead of about 17% for the tree-search part (50,000 playouts total). My quasi-heavy playouts run at 20,000 playouts/second, and I am estimating that if you appropriately break the tree-search portion in descend, update, copy, and misc threads, you can get the overhead to come down to, say, 5%. Then, if you completely outsource the playouts to the FPGA, i.e., you make them cost-free (ignoring communication costs), you would be able to boost the playouts twenty-fold, to 400,000, at which point you become CPU limited. Assume further that my coding can be further improved by another 2x (not unreasonable at all), and you get to 800,000. I it is feasible to send playouts out to the FPGA, because playouts are dynamic, depending on the structure of the tree, therefore, FPGA has to run simulations on small number of playouts very fast, which FPGA is not good at, It is good at running playouts of one board position for thousands of times quickly (at least our implementation is like this). Fuming, are you planning to run a version of your program on KGS/CGOS at some time in the future? Than we can all see it in action. We have not such plans. Right now, the system requires human intervention to start and end a game. We went to a national computer go event in Shenzhen, China, but performed poorly. We have made improvements since, maybe it will do better this year. Best, Fuming ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Fuego 04 native Windows
Petr, Do all the games have to start synchonously? Games are started one clock at a time. I think it would still be much better than alpha-beta with MC to do a UCT search with m * n playouts where you run m parallel descends with n playouts evaluated in the leaf. It is probably good idea to spread the descends using virtual loss, not sure if adding 1 or n losses would be better, perhaps a depth-dependent fraction rounded up would be best... Of course, having strongly pre-biased node values would help a lot here, I guess. m would be tuned so that you could pre-descend m times for next set of playouts while FPGA would walk the first m. The disadvantage of course is that you are descending on a tree that is missing (2*m-1)*n samples (you are doing basically 2*m samples in parallel). If the FPGA supports asynchronous game queuing, it would be of course much better as you could queue next set of games right after the descent, so the obsolescence factor would be just m*n (m+1 samples in parallel). I do not quite understand your description. I'm guessing that you mean to have n playouts at a time instead of one playout at a time like the regular UCT algorithm. Nonetheless, FPGA based method are very static in structure, and can not adapt easily to the dynamic changes of a game tree like a software implemented tree structure. So I don't know how to implement UCT type dynamic tree search algorithms in FPGA right now. Fuming ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Fuego 04 native Windows
Hi Rene, You guesses about our FPGA implementation are quite to the point. The 167 games are moving through the 167 pipelined stages of one module instead of 167 modules. As this material is a cross between digital circuit design and computer gaming, not quite sure which refereed journal is most suitable for this material. Do you or any readers of this list has any suggestions? Thanks, Fuming On Thu, Jun 17, 2010 at 8:09 AM, René van de Veerdonk rene.vandeveerd...@gmail.com wrote: Hi Fuming, Thanks for your answer, it makes much more sense to me now. We are using pipelining in different ways. When I referred to it for a CPU-based single-threaded application, I was thinking about speculative execution. If I understand it correctly, that does not exist in FPGA's, as these are advertised as deterministic in their execution and process flow. In the FPGA case, I imagine that pipelining refers to unrolling the program, and having different boards physically move across the chip from module to module, as if they are on a production line, all in various states of simulation (board #...@module #101: black to move; board #12@ module #100: white to move; etc.). How you have designed your program in detail would be an interesting read, there are a lot of high-level design trade-offs that you must have dealt with. These will be very different from how you would do it for a CPU-based program. One difference that I imagine, for instance, is the length of the simulation. A CPU-based program stops when the game ends (or you exceed some limit, or you force an early decision, or ...), whereas for FPGA you may end up with a fixed game-length (ready or not, i.e., no early out option) and you may have to simulate pass moves until you reach the end of the production line in case the game ended early (is this what you do?). In any case, your impressive numbers suggest that this can be done very efficiently. How you harness all this raw simulation power in a tree-search is yet another research topic that is very interesting and almost orthogonal. Do you think your approach could be mapped to a GPU as well? In any case, I hope you will make a pre-print available to this list when the time is there. In another response in this thread, you mention that you are simulating 167 board in parallel. Does that mean that you unrolled your program for 167 moves, moving a board between 167 separate modules every cycle and seed/harvest one complete board per cycle? Or do you have multiple (shorter) production lines in parallel? Or something else entirely? As you may have noticed, I am looking forward to your paper, René On Tue, Jun 15, 2010 at 7:03 PM, Fuming Wang fuming...@gmail.com wrote: Hi Rene, Our design is fully pipelined, so we are able to simulate multiple games simultaneously. The way way in which simulations are run in FPGA and in CPU is quite different, so direct comparison is not easy. If we want to simulate just one game, FPGA implementation is not 10x faster, however, if we want thousands of games simulated for a single board position, than FPGA is 10x faster. So, we are getting 1500k GAMES/sec, but only in the second sense. The clock rate of our FPGA board is only 125 MHz, so with better board/chip, we will still have 10-100 times improvement over the current result. best, Fuming On Wed, Jun 16, 2010 at 1:28 AM, René van de Veerdonk rene.vandeveerd...@gmail.com wrote: Fuming, Could you please explain your approach a little bit? From the numbers you quote, this sounds extreme positive, but I have a hard time understanding how you achieve them. Taking 100k playouts/sec for 9x9 on my 2.4 GHz labtop for my single-threaded bitmap based light-playout implementation as an example, with 110 moves/playout, this results in a little less than 240 clock-cycle/move. When I quickly looked up the Cyclone III specification, I saw that the clock-speed for this FPGA tops out around 240 MHz, yet you achieve 15x the throughput, i.e., you are 150x more efficient. This means 1.8 clock-cycle/move. Without being able to make use of pipe-lining inside the CPU (someone measured ~2 assembly instructions/clock-cycle for my bitmap approach), this leads me to questions. First, are you running a single threaded application, or playing on multiple boards at once? Second, are you just replaying moves, or also generating them on the fly (about half of the time is spend there in my implementation, more if you include updating the data-structure to make that possible)? Third, are we using the same definitions? For instance, I would find it much more comprehensible to believe that you achieved to do 1500k moves/second instead of 1500k playouts/sec (with each playout being ~110 moves). 200 clock-cycles/move sounds do-able if you can avoid branching, memory lookups, or miscellaneous calculations by creating fine-level parallelism in your FPGA-code and specializing functions
Re: [Computer-go] Fuego 04 native Windows
We are able to run 167 games in parallel. Unfortunately, it is not easy to incorporate FPGA based simulation into UCT based MCTS scheme. So, we are trying the traditional alpha-beta type tree search method to try to evaluate the usefulness of our FPGA based MC simulation. Best, Fuming On Wed, Jun 16, 2010 at 11:21 AM, Mark Boon tesujisoftw...@gmail.comwrote: I must admit I had completely misread this. I thought it said 1500 playouts/sec. and didn't give it a second glance, thinking this is just a first effort. 1500K playouts/sec. is a completely different ball-game. I suppose the question is: how many games do you need to compute in parallel to achieve this speed? And would you still be able to collect AMAF information on the playouts? Interesting... Mark On Tue, Jun 15, 2010 at 4:03 PM, Fuming Wang fuming...@gmail.com wrote: Hi Rene, Our design is fully pipelined, so we are able to simulate multiple games simultaneously. The way way in which simulations are run in FPGA and in CPU is quite different, so direct comparison is not easy. If we want to simulate just one game, FPGA implementation is not 10x faster, however, if we want thousands of games simulated for a single board position, than FPGA is 10x faster. So, we are getting 1500k GAMES/sec, but only in the second sense. The clock rate of our FPGA board is only 125 MHz, so with better board/chip, we will still have 10-100 times improvement over the current result. best, Fuming On Wed, Jun 16, 2010 at 1:28 AM, René van de Veerdonk rene.vandeveerd...@gmail.com wrote: Fuming, Could you please explain your approach a little bit? From the numbers you quote, this sounds extreme positive, but I have a hard time understanding how you achieve them. Taking 100k playouts/sec for 9x9 on my 2.4 GHz labtop for my single-threaded bitmap based light-playout implementation as an example, with 110 moves/playout, this results in a little less than 240 clock-cycle/move. When I quickly looked up the Cyclone III specification, I saw that the clock-speed for this FPGA tops out around 240 MHz, yet you achieve 15x the throughput, i.e., you are 150x more efficient. This means 1.8 clock-cycle/move. Without being able to make use of pipe-lining inside the CPU (someone measured ~2 assembly instructions/clock-cycle for my bitmap approach), this leads me to questions. First, are you running a single threaded application, or playing on multiple boards at once? Second, are you just replaying moves, or also generating them on the fly (about half of the time is spend there in my implementation, more if you include updating the data-structure to make that possible)? Third, are we using the same definitions? For instance, I would find it much more comprehensible to believe that you achieved to do 1500k moves/second instead of 1500k playouts/sec (with each playout being ~110 moves). 200 clock-cycles/move sounds do-able if you can avoid branching, memory lookups, or miscellaneous calculations by creating fine-level parallelism in your FPGA-code and specializing functions on a per grid-point basis. In a CPU-based application, this results in code-bloat that will become counter-productive at some stage, may not be feasible in all instances, and is more difficult to maintain. For an FPGA-based application, however, this sounds entirely possible (not knowing anything about FPGA's). Thanks, René van de Veerdonk On Sat, Jun 12, 2010 at 10:37 AM, Fuming Wang fuming...@gmail.com wrote: Cyclone III 120,000 logical elements cycle time is linear to the number of moves to finish a game, which is approximately linear to the square of the board size. Fuming - What FPGA? Virtex-6? Spartan-6? - What size is the core in LUT's? - Is your cycle time linear in the board size or in the number of squares (i.e. quadratic in board size)? Or something else? -- GCP ___ 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 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 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
Re: [Computer-go] Fuego 04 native Windows
My understandings is that light playout should implement Bruegmann's original proposal, which is Go rule plus basic patterns that avoid self-eye filling. Our FPGA implementation does this while cutting 2 corners, (1)ko violations are not checked; (2)suicides are allowed. We have tested in software,and found no significant difference in MC's ability to evaluate board positions with or without these 2 corners. I wonder what corners did libego cut? Gathering pieces of information in this thread, it seems that the light playout implementation on CPU is between 90k-170k/core on the latest hardware i7 3.2 GHz. (1) libego: 40k/GHz - 40k x 3.2= 130k @ 3.2GHz (2) libego: 130k @ 2.5GHz - 170k @ 3.2GHz (3) Mark boon's implementation: 70k @ 2.6 - 90k @ 3.2GHz Thanks for the responses. Fuming On Sat, Jun 12, 2010 at 2:52 AM, Mark Boon tesujisoftw...@gmail.com wrote: On Thu, Jun 10, 2010 at 11:09 PM, Erik van der Werf erikvanderw...@gmail.com wrote: Lukasz Lew's libego used to have the fastest light playouts. IIRC some years ago it already got over 100k playouts per second for 9x9 on one core. I guess it should now be possible to get over 200k light playouts per second. Others on this list may have more accurate numbers. Cores didn't really get much faster recently, so what makes you think it could be twice as fast now? A while ago I took a peek at his code, but I found it hard to understand. In a logical sense I saw some places that seem sub-optimal from an algorithmic point of view. But I figured the numbers speak for themselves. At the time it was reported it did something like 40K playouts per Ghz. But I didn't manage to verify this as I never got his code to compile. It's probably a bit too Linux specific in its setup. The main reason I didn't look into it further (apart from lack of time) is that AFAIK it doesn't keep liberties. But I think it does keep a few other useful things. People refer to 'light' playouts but may mean different things. I like to at least make the distinction between playouts that keeps correct liberty counts and playouts with pseudo liberties. In my personal code, pseudo liberties is only marginally faster than real liberties so I find it highly preferable to keep real liberties so it can be used by a tactical module. But I didn't spend nearly as much time as Lukasz trying to optimize it. The other thing that needs care when touting playout speeds is whether this is purely measuring playouts, or playouts while building a MCTS tree (or hashtable). My Java implementation of light playouts with liberties does something like 30K-35K per second on one core. I think it's similar on a 2.6Ghz i5 as on an older 2.8Ghz. The same code directly translated to C is about twice as fast. Mark ___ 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] Fuego 04 native Windows
Hello Ernest, Thanks for making the binary. Could you tell me whether the 40-60k games/sec results is for a single core in your overclocked i7, or is it for all 4 cores in your i7 cpu. Thanks, Fuming * The binary does around 36k games/sec in the opening rising to 50-60k ** later. Which is a lot ** more than the 23.5K of the cygwin version. AFAIK it works Ok with ** multithreading with ** and without locking. It is also much smaller and has no .dll dependencies. * ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Fuego 04 native Windows
Not yet, we are working on it. Fuming. On Fri, Jun 11, 2010 at 9:41 AM, Broccard, Frederic fbrocc...@ucsd.eduwrote: hi, I recently begun working on machine learning and computer Go and I'm new to the list. We have implemented 9x9 light playout on a FPGA chip, and we are getting 1500k playouts/sec, so I am interested in how this compares with speeds on the latest cpu, which I don't have right now. Did you publish somewhere the work on the FPGA chip ? Couldn't find anything online and would be interested on it. Thanks, fred ___ Computer-go mailing list Computer-go@dvandva.orgmailto:Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.orgmailto: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 mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
