Re: [computer-go] Lockless hash table and other parallel search ideas
The rules are exactly the same for 9x9 as for 19x19. The boardsize is different and that changes the game some. I would suggest that if a top go player plays a game of chess immediately after first learning the rules, he would lose very badly to even mediocre players or even advanced beginners. I really doubt this would be the case with 9x9 go. I don't think you can really make a strong argument that 9x9 isn't go or that it's not the same game.You CAN argue that the characteristics of the game are different and different aspects of the game are emphasized. Some really strong players may not be specialists in 9x9 and may lose to players who specialize in 9x9 but are otherwise a few stones weaker at 19x19, but that's not remarkable. In chess you can also be weakened significantly and be thrown off your game by a surprise opening - or we could imagine a game where your opening is decided for you and it would make you very uncomfortable. My guess (and it's only a guess) is that strong players playing on the 9x9 board are simply very uncomfortable but probably do not play as weak as they imagine.In chess I heard that someone once did a study to find out if playing speed chess weakened the performance of some players more than others and despite the fact that many players imagine that it does, it turned out that there was a remarkable correlation, although no doubt some players who specialize at different time controls would have an edge. - Don On Wed, 2008-09-10 at 11:27 +0900, Hideki Kato wrote: Christoph Birk: [EMAIL PROTECTED]: On Tue, 9 Sep 2008, Olivier Teytaud wrote: testbed for parallelization because it's more difficult) and as real targets (as there are players for both). Sorry, but there are (almost) no players for 9x9. To repeat D.Fotland's earlier comment: 9x9 is just for beginner's practice. It's not go. Other than the match CS vs. Kaori Aoba 4p, which Rémi reported recently, there was a 9x9 match CS vs. Meien O 9p with no komi at FIT2008. CS (B) won by 3 points. I'd like to emphasize 9x9 is Go. Hideki Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
I'm not sure about the strength of professional players on 9x9 but basically agree with Don. Of course, there are no definition what Go is. So, I'd just like to introduce some in Japan. - Meien O 9p is radical in some sense. He wrote in his book that Go is already unified in the sense that baseball is unified. Say, although the size of the ball, for example, is different in US and Japan, people don't say threre are two baseballs or Japanese baseball is not a baseball, at lease these days :-). So, according to his idea, 9x9 is, of course, Go. #Oh, if you can read Japanese, please visit the site below titled Kanpai, Monte-Carlo. http://taisen.mycom.co.jp/taisen/contents/igo/meien/meien_30.htm Kanpai here has two meanings, perfect loss and to toast. - There had been a TV program of professional 9x9 Go for years (some member of this list have the records of the games played in this program). Takemiya 9p and Yuki 9p were the strongest. - A vert famous and one of the strongest 9p in Japan, Chikun Cho is well known by his research about 9x9 Go. So, I'm sure all professtonal Go players in Japan think 9x9 is Go. - There are threads for discussions and online 9x9 games (by beginners, kyu and dan players) on the largest BBS in Japan. - Finally, Mr. Okasaki, a researcher of the game of Go, sometime argued 9x9 is not Go. He sometime also argued computer's Go is not Go :). Hideki Don Dailey: [EMAIL PROTECTED]: The rules are exactly the same for 9x9 as for 19x19. The boardsize is different and that changes the game some. I would suggest that if a top go player plays a game of chess immediately after first learning the rules, he would lose very badly to even mediocre players or even advanced beginners. I really doubt this would be the case with 9x9 go. I don't think you can really make a strong argument that 9x9 isn't go or that it's not the same game.You CAN argue that the characteristics of the game are different and different aspects of the game are emphasized. Some really strong players may not be specialists in 9x9 and may lose to players who specialize in 9x9 but are otherwise a few stones weaker at 19x19, but that's not remarkable. In chess you can also be weakened significantly and be thrown off your game by a surprise opening - or we could imagine a game where your opening is decided for you and it would make you very uncomfortable. My guess (and it's only a guess) is that strong players playing on the 9x9 board are simply very uncomfortable but probably do not play as weak as they imagine.In chess I heard that someone once did a study to find out if playing speed chess weakened the performance of some players more than others and despite the fact that many players imagine that it does, it turned out that there was a remarkable correlation, although no doubt some players who specialize at different time controls would have an edge. - Don On Wed, 2008-09-10 at 11:27 +0900, Hideki Kato wrote: Christoph Birk: [EMAIL PROTECTED]: On Tue, 9 Sep 2008, Olivier Teytaud wrote: testbed for parallelization because it's more difficult) and as real targets (as there are players for both). Sorry, but there are (almost) no players for 9x9. To repeat D.Fotland's earlier comment: 9x9 is just for beginner's practice. It's not go. Other than the match CS vs. Kaori Aoba 4p, which Rémi reported recently, there was a 9x9 match CS vs. Meien O 9p with no komi at FIT2008. CS (B) won by 3 points. I'd like to emphasize 9x9 is Go. Hideki Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
It is true that a pro would probably do rather well against a moderate amateur at 9x9 go, but nonetheless, the pro has a great deal of knowledge which is specific to 19x19 go. Several authors have very recently mentioned that their programs have to be tuned to play well at 9x9 go; important parameters differ compared to 19x19. Many joseki for the 19x19 board involve subtle tradeoffs of territory versus influence. The value of influence depends on how close opposing stones are. On 9x9, everything is close. Giving one's opponent a large corner in exchange for great influence can be a winning strategy on a 19x19 board; on 9x9 the same sequence of moves would probably lose badly. 9x9 go is an extremely tactical game; every play strongly affects the entire board. It might be the case that top programs can already beat pros at 9x9 go - especially if the program is free of bugs related to nakade, seki, and ko fights. A pro could certainly not give a two-stone handicap to a top program on a 9x9 board, assuming that the program knows how to make use of those handicap stones. Terry McIntyre [EMAIL PROTECTED] Go is very hard. The more I learn about it, the less I know. -Jie Li, 9 dan - Original Message From: Don Dailey [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, September 10, 2008 5:12:57 AM Subject: Re: [computer-go] Lockless hash table and other parallel search ideas The rules are exactly the same for 9x9 as for 19x19. The boardsize is different and that changes the game some. I would suggest that if a top go player plays a game of chess immediately after first learning the rules, he would lose very badly to even mediocre players or even advanced beginners. I really doubt this would be the case with 9x9 go. I don't think you can really make a strong argument that 9x9 isn't go or that it's not the same game.You CAN argue that the characteristics of the game are different and different aspects of the game are emphasized. Some really strong players may not be specialists in 9x9 and may lose to players who specialize in 9x9 but are otherwise a few stones weaker at 19x19, but that's not remarkable. In chess you can also be weakened significantly and be thrown off your game by a surprise opening - or we could imagine a game where your opening is decided for you and it would make you very uncomfortable. My guess (and it's only a guess) is that strong players playing on the 9x9 board are simply very uncomfortable but probably do not play as weak as they imagine.In chess I heard that someone once did a study to find out if playing speed chess weakened the performance of some players more than others and despite the fact that many players imagine that it does, it turned out that there was a remarkable correlation, although no doubt some players who specialize at different time controls would have an edge. - Don On Wed, 2008-09-10 at 11:27 +0900, Hideki Kato wrote: Christoph Birk: : On Tue, 9 Sep 2008, Olivier Teytaud wrote: testbed for parallelization because it's more difficult) and as real targets (as there are players for both). Sorry, but there are (almost) no players for 9x9. To repeat D.Fotland's earlier comment: 9x9 is just for beginner's practice. It's not go. Other than the match CS vs. Kaori Aoba 4p, which Rémi reported recently, there was a 9x9 match CS vs. Meien O 9p with no komi at FIT2008. CS (B) won by 3 points. I'd like to emphasize 9x9 is Go. Hideki Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
- There had been a TV program of professional 9x9 Go for years (some member of this list have the records of the games played in this program). Takemiya 9p and Yuki 9p were the strongest. I'm afraid the answer is no, but: are these records free and available somewhere ? Thanks for your interesting informations around Go and 9x9 Go :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Maybe these are the same? http://gobase.org/9x9/ Erik On Wed, Sep 10, 2008 at 4:38 PM, Olivier Teytaud [EMAIL PROTECTED] wrote: - There had been a TV program of professional 9x9 Go for years (some member of this list have the records of the games played in this program). Takemiya 9p and Yuki 9p were the strongest. I'm afraid the answer is no, but: are these records free and available somewhere ? Thanks for your interesting informations around Go and 9x9 Go :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
On Sep 10, 2008, at 2:12 PM, Don Dailey wrote: The rules are exactly the same for 9x9 as for 19x19. The boardsize is different and that changes the game some. I would suggest that if a top go player plays a game of chess immediately after first learning the rules, he would lose very badly to even mediocre players or even advanced beginners. Usually i hesitate commenting just upon 1 statement out of an entire story. Additionally you have the advantage of the native English skill; kind of Obama type statement that you can still define an 'advanced beginner' as being a titled player who doesn't make money with it. But we must correct you here in case you no longer see yourself as a beginner or as an advanced beginner. Directly after learning the games of chess, a strong go player will be able to win from you. Strategically and tactically they're that much above your level that they will completely annihilate you. Regarding that there are big differences between 9x9 and 19x19 i agree. 9x9 is a very simple game compared to 19x19. From computer algorithms viewpoint seen that hard forward pruning is tougher to do there; explaining why the current random searching methods do so bad in 9x9 and a lot better at 19x19, relatively spoken. In absolute sense the will fail at both games of course. The only proof the current random searching methods give in go is that searching deeply in random manner is better than searching short lines in super-dubious manner. IMHO this is logical. The fact that there is zero fulltime salary prospects to get clever guys interested in putting in years of fulltime effort into 9x9, is the reason why the programs play this still so weak, as just a single one of them would raise the game quality a lot. It is of course a combination of evaluation and search. What you typically see is that players with little domain knowldge in chess nor go, are busy with it now, doing a brute force attempt. Note that computer-go has one big advantage over computer-chess; because there is little sales possible to achieve, there is little money at stake, that gives the advantage that the programmers at least communicate with each other in a forum like this and at tournaments. In computerchess it is very difficult to find talkative persons. The main progress that happens in computerchess is simply by debugging other persons code. It goes that far that a Russian author has even simply automatically converted the program Rybka 1.0 back from assembler into C code, it is called strelka. This communicative skills problem is why progress in computerchess goes relative slow. Still many brilliant guys get lured into it, because chess gets played in 105+ nations. You see clearly now that they do not do much effort for it nowadays, as just like computer-go there is nearly no money to make with an engine (in contradiction to GUI). In doing that, it is selfexplaining that those who have a parallel go- program, still didn't figure out what computerchess already knew in the 80s, namely that to run parallel you need to avoid central locking, and need to search with a global hashtable (Feldmann, somewhere in the 80s) and a decentralized form of doing the search. That sure involves locking in case you want a good speedup, something Leiersonco with CILK did not manage nor Feldmann, but that is all very well solvable with a big effort. Yet those big guys who were busy with chess in the past years, who already knew back in the 80s a lot about decentralizing the parallel search, in computer-go they seem absent. Vincent I really doubt this would be the case with 9x9 go. I don't think you can really make a strong argument that 9x9 isn't go or that it's not the same game.You CAN argue that the characteristics of the game are different and different aspects of the game are emphasized. Some really strong players may not be specialists in 9x9 and may lose to players who specialize in 9x9 but are otherwise a few stones weaker at 19x19, but that's not remarkable. In chess you can also be weakened significantly and be thrown off your game by a surprise opening - or we could imagine a game where your opening is decided for you and it would make you very uncomfortable. My guess (and it's only a guess) is that strong players playing on the 9x9 board are simply very uncomfortable but probably do not play as weak as they imagine.In chess I heard that someone once did a study to find out if playing speed chess weakened the performance of some players more than others and despite the fact that many players imagine that it does, it turned out that there was a remarkable correlation, although no doubt some players who specialize at different time controls would have an edge. - Don On Wed, 2008-09-10 at 11:27 +0900, Hideki Kato wrote: Christoph Birk: Pine.LNX. [EMAIL PROTECTED]: On Tue, 9 Sep 2008, Olivier Teytaud
Re: [computer-go] Lockless hash table and other parallel search ideas
Erik van der Werf: [EMAIL PROTECTED]: Maybe these are the same? http://gobase.org/9x9/ Yes but a part. Unfortunatelly, whole records is temporary not available. Following is the reason (and history) which I can remember now. All records were published (but not sold) in a few booklets. Dr. Saito and Mr. Okasaki made them computer readable ten or more years ago. They are copyrighted by Yomiuri TV but Mr. Okasaki has a grant to distribute them for research purposes. They had been distributed under his permission for years. Last year, Mr. Okasaki studied them precisely and found so many errors that he asked me to stop distribution. I have no idea when I will be able to restart. Hideki Erik On Wed, Sep 10, 2008 at 4:38 PM, Olivier Teytaud [EMAIL PROTECTED] wrote: - There had been a TV program of professional 9x9 Go for years (some member of this list have the records of the games played in this program). Takemiya 9p and Yuki 9p were the strongest. I'm afraid the answer is no, but: are these records free and available somewhere ? Thanks for your interesting informations around Go and 9x9 Go :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
On Sep 10, 2008, at 8:27 AM, Vincent Diepeveen wrote: Note that computer-go has one big advantage over computer-chess; because there is little sales possible to achieve, there is little money at stake, that gives the advantage that the programmers at least communicate with each other in a forum like this and at tournaments. In computerchess it is very difficult to find talkative persons. I'm not sure this statement is true. It has been estimated that the overall market for the amateur level Go programs has been around 5-10 million dollars. I imagine that this market will only expand as the programs become stronger, China enters the software marketplace, and Go becomes more popular worldwide. What would you estimate the worldwide chess program market to be? I agree that the Go community is refreshingly open about their techniques. Even commercial authors like Bruce Wilcox and David Fotland wrote extensively about their programs' internals. In chess, the authors have their trade secrets which they keep as long as they can make sales. The one blight on the computer Go community was the North Korean KCC Igo plagiarism scandal. Ian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Hi Vincent, What does this possibly have to do with me? But we must correct you here in case you no longer see yourself as a beginner or as an advanced beginner. Directly after learning the games of chess, a strong go player will be able to win from you. Strategically and tactically they're that much above your level that they will completely annihilate you. Ok, since you seem to be so interested ... I don't currently play chess and haven't for over 20 years. But I think an excellent description of the way I used to play chess is mediocre which means, Of a middle quality; of but a moderate or low degree of excellence Middle quality is just about right. I played tournament chess for about 2 years. The median tournament chess player at that time was between 1500-1600 ELO I believe. My PEAK rating was 1914 which is not much more than median (I was still in the fat part of the Bell shaped curve even if I was above average.) And low degree of excellence fits because plenty of players exist hundreds of ELO stronger than myself. I think I would be a very good candidate for this experiment, even though the last thing on my mind was using myself as an example and I'm flattered that you choose to pick on me. So if you can locate a very strong GO player who has never heard of chess, I would very happily give you a day to teach him the rules of the game and to coach him on strategy. I think I would easily win a 10 game match. In fact, I believe a player significantly weaker than myself would easily win a 10 game match. Please note that a player of my weak ability rarely produces good games. I have rarely produced a game of chess I am proud of, my games being laced with errors that even I can see on further analysis. Chess is all about errors until you get to the really high levels, and then it's still all about errors. You never see chess players showing off their lost games. However it makes me laugh to think that you believe someone who has never even learned the rules of the game would play close to USCF master level immediately after learning the rules. You said that they would be able to completely annihilate me. What does it mean to completely annihilate someone? If you assume that means they will win 90% of the time, this implies they would have to be at least USCF master strength. There is no point even talking about this, unless you can actually arrange this experiment. Your statement is so ridiculous that I wonder if you have lost your mind. Please don't come back at me with another rant - produce this player who can immediately beat me even though he doesn't even know the rules. - Don On Wed, 2008-09-10 at 17:27 +0200, Vincent Diepeveen wrote: On Sep 10, 2008, at 2:12 PM, Don Dailey wrote: The rules are exactly the same for 9x9 as for 19x19. The boardsize is different and that changes the game some. I would suggest that if a top go player plays a game of chess immediately after first learning the rules, he would lose very badly to even mediocre players or even advanced beginners. Usually i hesitate commenting just upon 1 statement out of an entire story. Additionally you have the advantage of the native English skill; kind of Obama type statement that you can still define an 'advanced beginner' as being a titled player who doesn't make money with it. But we must correct you here in case you no longer see yourself as a beginner or as an advanced beginner. Directly after learning the games of chess, a strong go player will be able to win from you. Strategically and tactically they're that much above your level that they will completely annihilate you. Regarding that there are big differences between 9x9 and 19x19 i agree. 9x9 is a very simple game compared to 19x19. From computer algorithms viewpoint seen that hard forward pruning is tougher to do there; explaining why the current random searching methods do so bad in 9x9 and a lot better at 19x19, relatively spoken. In absolute sense the will fail at both games of course. The only proof the current random searching methods give in go is that searching deeply in random manner is better than searching short lines in super-dubious manner. IMHO this is logical. The fact that there is zero fulltime salary prospects to get clever guys interested in putting in years of fulltime effort into 9x9, is the reason why the programs play this still so weak, as just a single one of them would raise the game quality a lot. It is of course a combination of evaluation and search. What you typically see is that players with little domain knowldge in chess nor go, are busy with it now, doing a brute force attempt. Note that computer-go has one big advantage over computer-chess; because there is little sales possible to achieve, there is little money at stake, that gives the advantage that the
Re: [computer-go] Lockless hash table and other parallel search ideas
Yes. I use Sylvain's fpu and decrease it a little before starting a simulation, say, fpu *= 0.99. This is very simple and fast. Ok. Perhaps I'm wrong (I might misunderstand your solution and I might be wrong whenever I've understood :-) ); but - I think that this does not avoid redundancies in the tree, if I understand well. - also, even in a final node in a tree, it does not avoid redundancies for moves which have already been simulated. - finally, in a final node in a tree and for moves which have not yet been simulated, it only avoid redundancies if 0.99 is sufficiently small. Avoiding redundancies is very important in SMP parallelization. The limited speed-up of MPI parallelization in 9x9 is also probably due to redundancies, but for that we have no good solution - whereas in 19x19 (or even 13x13), the speed-up of the MPI parallelization is great (both in our results and other published papers), in 9x9 it is limited. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Olivier Teytaud: [EMAIL PROTECTED]: Yes. I use Sylvain's fpu and decrease it a little before starting a simulation, say, fpu *= 0.99. This is very simple and fast. Ok. Perhaps I'm wrong (I might misunderstand your solution and I might be wrong whenever I've understood :-) ); but - I think that this does not avoid redundancies in the tree, if I understand well. - also, even in a final node in a tree, it does not avoid redundancies for moves which have already been simulated. - finally, in a final node in a tree and for moves which have not yet been simulated, it only avoid redundancies if 0.99 is sufficiently small. Perhaps yes. I use _no_ pre-knowledge yet, ie, the initial value of fpu is a constant, 1.10. Avoiding redundancies is very important in SMP parallelization. The limited speed-up of MPI parallelization in 9x9 is also probably due to redundancies, but for that we have no good solution - whereas in 19x19 (or even 13x13), the speed-up of the MPI parallelization is great (both in our results and other published papers), in 9x9 it is limited. Although I'm parallelizing in not SMP systems but a cluster of loosely coupled (small) computers connected through moderate speed networks using broadcasting positions, this may not change the vlaue of avoiding redundancies. I'll study more when implementing pre-knowledge or some. Thanks. Best regards, Hideki Best regards, Olivier inline file ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Although I'm parallelizing in not SMP systems but a cluster of loosely coupled (small) computers connected through moderate speed networks using broadcasting positions, this may not change the vlaue of avoiding redundancies. I'll study more when implementing pre-knowledge or some. Thanks. Do you have the winning rate of your best parallel algorithm against the sequential version in 9x9 Go in such a setting without shared memory ? We stay below 80% for this form of parallelization (but this speed-up can be cumulated with SMP speed-up), whenever we use fast networks (infiniband). In 19x19, it's much better, but the MPI parallelization of 9x9 Go is challenging. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Olivier Teytaud: [EMAIL PROTECTED]: Although I'm parallelizing in not SMP systems but a cluster of loosely coupled (small) computers connected through moderate speed networks using broadcasting positions, this may not change the vlaue of avoiding redundancies. I'll study more when implementing pre-knowledge or some. Thanks. Do you have the winning rate of your best parallel algorithm against the sequential version in 9x9 Go in such a setting without shared memory ? We stay below 80% for this form of parallelization (but this speed-up can be cumulated with SMP speed-up), whenever we use fast networks (infiniband). Not yet. I have many benchmarks now but only against GNU Go level _0_ on 9x9 and 13x13. The best WR on 9x9 is 72% using four quad-core PCs on a GbE private LAN with 0.16 second per move (less than 10 seconds per game) but the speed-up (strength-speedup by G. Chaslot) against 1 PC is just 1.6. This may be improved in longer time settings but I'm not sure. # I can use only 4 x 4 cores in hand now so that it's very hard to have benchmarks on 19x19. In 19x19, it's much better, but the MPI parallelization of 9x9 Go is challenging. Strongly agree. Even in 13x13, it's much better. Best, Hideki Best regards, Olivier inline file ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
On Tue, 9 Sep 2008, Olivier Teytaud wrote: In 19x19, it's much better, but the MPI parallelization of 9x9 Go is challenging. The bright side here is that 9x9 is not really important but just a test bed. If it works for 19x19, that's good. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
The bright side here is that 9x9 is not really important but just a test bed. If it works for 19x19, that's good. People moderately intested in Go could also claim that both 9x9 and 19x19 are just testbeds for power plant management :-) In my humble opinion, both are intesting, both as testbeds (9x9 is a good testbed for parallelization because it's more difficult) and as real targets (as there are players for both). But, I guess it's a controversial political issue :-) Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
On Tue, 9 Sep 2008, Olivier Teytaud wrote: testbed for parallelization because it's more difficult) and as real targets (as there are players for both). Sorry, but there are (almost) no players for 9x9. To repeat D.Fotland's earlier comment: 9x9 is just for beginner's practice. It's not go. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
On Sep 8, 2008, at 11:45 AM, Olivier Teytaud [EMAIL PROTECTED] wrote: By my recent experiments, 8~9 * (threads - 1) ELO is lost. This matches my earlier result well. Do you have tricks for avoiding redundancies between simulations ? I suggest simple tricks like do not go to node X if there is a thread currently in node X (simply by setting the score of the moves leading to node X to zero until you get out of the node). Are there any tricks for adding in transposed search results without locking? I currently re-scan children to pick up the free search results. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Christoph Birk: [EMAIL PROTECTED]: On Tue, 9 Sep 2008, Olivier Teytaud wrote: testbed for parallelization because it's more difficult) and as real targets (as there are players for both). Sorry, but there are (almost) no players for 9x9. To repeat D.Fotland's earlier comment: 9x9 is just for beginner's practice. It's not go. Other than the match CS vs. Kaori Aoba 4p, which Rémi reported recently, there was a 9x9 match CS vs. Meien O 9p with no komi at FIT2008. CS (B) won by 3 points. I'd like to emphasize 9x9 is Go. Hideki Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
By my recent experiments, 8~9 * (threads - 1) ELO is lost. This matches my earlier result well. Do you have tricks for avoiding redundancies between simulations ? I suggest simple tricks like do not go to node X if there is a thread currently in node X (simply by setting the score of the moves leading to node X to zero until you get out of the node). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
On Mon, Sep 8, 2008 at 11:45 AM, Olivier Teytaud [EMAIL PROTECTED] wrote: By my recent experiments, 8~9 * (threads - 1) ELO is lost. This matches my earlier result well. Do you have tricks for avoiding redundancies between simulations ? I suggest simple tricks like do not go to node X if there is a thread currently in node X (simply by setting the score of the moves leading to node X to zero until you get out of the node). That doesn't sound like a good idea to me, since it would force most threads out of the interesting moves at the root. If you are using UCT, you can simply increment the number of plays when a thread starts exploring this branch; the number of victories will be incremented later, if it needs to be incremented. This way other threads will be discouraged from taking this move, but not disproportionally. By the way, are people aware that you can do atomic increments with one line of assembly code? Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Olivier Teytaud: [EMAIL PROTECTED]: By my recent experiments, 8~9 * (threads - 1) ELO is lost. This matches my earlier result well. Do you have tricks for avoiding redundancies between simulations ? Yes. I use Sylvain's fpu and decrease it a little before starting a simulation, say, fpu *= 0.99. This is very simple and fast. For detailed info, you can read my implementation of PMCTS (parallel MCTS) submitted to GPW 2007. Though it's written in Japanese, pseudo code are in English and abstract and captions are written in both. http://www.geocities.jp/hideki_katoh/publications/gpw2007/gpw07-private.pdf If you have any trouble on downloading or reading, please let me know. Hideki I suggest simple tricks like do not go to node X if there is a thread currently in node X (simply by setting the score of the moves leading to node X to zero until you get out of the node). inline file ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Rémi Coulom: [EMAIL PROTECTED]: snip I'll run tests to try to figure out how much strength is lost by parallelization (ie, what is the winning rate of 10,000 sequential playouts vs 1,000 playouts over 10 processors). Hideki ran similar tests against GNU Go, and found 25 Elo loss with 4 CPUs. So 54,193 playouts per second over 16 CPUs will certainly not perform as well as 54,193 sequential playouts. By my recent experiments, 8~9 * (threads - 1) ELO is lost. This matches my earlier result well. Hideki -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Olivier Teytaud wrote: Hi, I have got a lockless hash table to work, and I thought I'd share the results. [...] Great! For networks of 4-cores, it is not very useful, but for highly smp machines it could be great - with your grid5000 account, you might run crazystone on a 16-core machine and have a very impressive crazyStone. Olivier Thanks for the tip. Here are the results on 9x9: cores playouts/s 118,025 233,749 348,165 462,268 575,539 687,136 7 100,840 8 115,862 10 134,185 12 158,491 14 174,274 16 205,379 (speedup = 11.4) and on 19x19: 13,780 27,427 3 11,009 4 13,905 5 17,684 6 21,265 7 24,418 8 27,907 10 34,710 12 40,975 14 48,000 16 54,193 (speedup = 14.3) Hardware is 8x Dual Core AMD Opteron 875, 2.2 GHz I'll run tests to try to figure out how much strength is lost by parallelization (ie, what is the winning rate of 10,000 sequential playouts vs 1,000 playouts over 10 processors). Hideki ran similar tests against GNU Go, and found 25 Elo loss with 4 CPUs. So 54,193 playouts per second over 16 CPUs will certainly not perform as well as 54,193 sequential playouts. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Hi, I have got a lockless hash table to work, and I thought I'd share the results. [...] Great! For networks of 4-cores, it is not very useful, but for highly smp machines it could be great - with your grid5000 account, you might run crazystone on a 16-core machine and have a very impressive crazyStone. Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Don Dailey wrote: These are used in parallel chess programs, and it's very common. A pretty good article on this written by Hyatt (Crafty programmer and author of former world computer chess champion Cray Blitz) and it's called A lock-less transposition table implementation for parallel search chess engines, I see an on-line version of a similar article here: http://www.cis.uab.edu/hyatt/hashing.html - Don Hi Don, Yes, I knew Bob's paper. In his approach, an entry will be lost in case of a collision. In my Go program, I never replace hash entries of the current search, because I have enough memory to store them all. I only have to be careful when allocating a node for the first time, so that two threads do not allocate the same slot. This happens rarely enough that the cost of a Test-And-Swap is negligible, so I prefer to do it that way. What I do is essentially the beginning of the Google talk I indicated yesterday, without resizing. I believe it is a lot cleaner than Bob's idea, although atomic increments are costly. In fact, now that I think a little more about it, Bob's scheme would probably not work at all, because updating counters would mean updating the hash code, and any collision would cause a loss of the hash entry. It does not matter for alpha-beta, but losing an entry near the root in MC search would be very bad. Really ugly stuff would be necessary to repair the consequences of such a collision. So, I believe Bob's idea would not work. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
I'll take a look at the references you posted - they look pretty interesting from an initial glance at them. - Don Rémi Coulom wrote: Don Dailey wrote: These are used in parallel chess programs, and it's very common. A pretty good article on this written by Hyatt (Crafty programmer and author of former world computer chess champion Cray Blitz) and it's called A lock-less transposition table implementation for parallel search chess engines, I see an on-line version of a similar article here: http://www.cis.uab.edu/hyatt/hashing.html - Don Hi Don, Yes, I knew Bob's paper. In his approach, an entry will be lost in case of a collision. In my Go program, I never replace hash entries of the current search, because I have enough memory to store them all. I only have to be careful when allocating a node for the first time, so that two threads do not allocate the same slot. This happens rarely enough that the cost of a Test-And-Swap is negligible, so I prefer to do it that way. What I do is essentially the beginning of the Google talk I indicated yesterday, without resizing. I believe it is a lot cleaner than Bob's idea, although atomic increments are costly. In fact, now that I think a little more about it, Bob's scheme would probably not work at all, because updating counters would mean updating the hash code, and any collision would cause a loss of the hash entry. It does not matter for alpha-beta, but losing an entry near the root in MC search would be very bad. Really ugly stuff would be necessary to repair the consequences of such a collision. So, I believe Bob's idea would not work. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
These are used in parallel chess programs, and it's very common. A pretty good article on this written by Hyatt (Crafty programmer and author of former world computer chess champion Cray Blitz) and it's called A lock-less transposition table implementation for parallel search chess engines, I see an on-line version of a similar article here: http://www.cis.uab.edu/hyatt/hashing.html - Don Rémi Coulom wrote: Hi, I have got a lockless hash table to work, and I thought I'd share the results. A lockless hash table is very important, because the usual approach that consists in using a global lock during tree search and update does not scale well, especially on 9x9. But it is possible to create a completely lockless hash table data structure that works with multiple threads. Here are some links that give some indications of how such a thing can be done: http://video.google.com/videoplay?docid=2139967204534450862 http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html http://www.cs.rug.nl/~wim/mechver/hashtable/index.html Some of those links may look intimidating, but that is because the resize part of the algorithm is complicated. In my implementation, I do not resize the table, so it is very simple. Also, I update counter in each node with atomic increments and decrements (no need to lock). Here is some preliminary experimental data for 9x9 up to 8 cores, running 840,000 playouts, from a tactical middle-game position: (Cores / Playouts per second with spinlock / Playouts per second with lockless hash table) 1 22,477.9 22,447.9 2 37,769.8 43,076.9 3 55,888.2 60,825.5 4 61,448.4 79,470.2 5 64,665.1 95,346.2 6 62,407.1 110,092.0 7 66,508.3 130,638.0 8 59,196.6 146,341.0 BTW, using a pthread mutex is a lot worse than a spinlock, in my experience. I used the fair spinlock from the Linux kernel. But any implementation should work. So, it is pretty cool. This was measured on only one run. Since it is not deterministic, performance may vary from one run to the other (especially since it does not always select the same best move). But it still clearly shows the superiority of the lockless hash table, and seems to indicate that it would still scale beyond 8 cores. I believe I could improve further by reducing the number of atomic operations. Also, thinking about how to reduce atomic operations led me to imagine a scheme that may works as a distributed hash table over a network of PCs. A simple scheme that would work on a single PC would consist in storing one counter per thread in the table. This way, it would not be necessary to use atomic operations to increment counters, and the cache coherency mechanism of the CPUs would handle sending data from core to core. The cost would be that in order to get the node counters, it would be necessary to add N values. Also, some information may arrive a little late to some threads (but I believe it is better to go run a playout rather than wait for data). This scheme is a bit equivalent to using a separate hash table for each thread, and could be generalized to a distributed hash table over a network: each PC would have its own hash table, and each node of the tree would contain two counters: my_counter and other_counter. Every now and then, for instance when my_counter reaches a threshold, this PC would broadcast my_counter to the whole network, so that everybody updates other_counter. I have not implemented this yet, but I will probably try it. Right now, I will test the lockless hash table more, and will probably connect to 9x9 CGOS with that machine sometime during the week-end. If you wish to implement your own lockless hash table, you should read Intel's documentation about its memory architecture. It can be found there: http://www.intel.com/products/processor/manuals/index.htm In particular, it is important to read Architecture Memory Ordering White Paper, and about the lock prefix, the cmpxchg operation, sfence, lfence, and mfence. The primitives I used in my algorithm are a store fence, atomic increment, atomic decrement, atomic compare and swap. If you understand what they do, you should be able to make your own lockless hash table. Have fun, Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
