[computer-go] MoGo/professional challenge
This Easter weekend, there will be a challenge between MoGo running on a very powerful system, and Catalin Taranu, 5-dan professional. The following is from the info of The Enclave room on KGS. It is confirmed by the page http://paris2008.jeudego.org/ quotation starts A unique challenge will be held in parallel to the Paris Go tournament : Mogo, currently one of the best Go programs in the world, will challenge the professional Go player Catalin Taranu 5P. Mogo has all the computing power of INRIA with hundreds of super-computers in a network. The winner will be chosen at the end of 9x9 games after 3 rounds of 2x30-minute sudden death. A 19x19 exhibition will be held on Sunday. Events are being followed live on KGS! They will be shown by 'iagochall'. Saturday: 3/23/08 3:00 PM Game I (9x9) Game II 9x9 Game III 9x9 Played with 1.5 hours from the start of one round to the next Sunday: 3/24/08 3:00 PM Exhibition game (19x19) Monday: 3/25/08 11:00 PM Debate with participants quotation ends The time zone quoted above is GMT; that in the http://paris2008.jeudego.org/ page is French time, GMT+1. Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
For information on the mogo/pro challenge: - during preliminary tests, mogo has won 4/0 against a very high level human; at that time we were just very very very happy :-) - some other humans, supposed to be weaker, have however won some games at that time (before the nakade correction); - the Nakade weakness is currently assumed to be solved, but I'm not sure of that - at least mogo solves the old known nakade situations and is stronger than the old mogo; at that time we were happy again :-) - another improvement is that we currently have access to much hardware than during tests above; - but, a human, supposed to be weaker (non professional level, 5Dan however) has found some trick to win against mogo; this is not the nakade, but this is seemingly stable, and I am just not able of explaining how he can do that; he has shown me situations and says that in this kind of situations, mogo makes an error, but I just don't understand the common point in these situations. If we understand something we will post details here (at least the sgf files)... - in 9x9, the MPI (multi-machine) version of mogo wins with probability 80% against the non-MPI version. The speed-up is better in 19x19 and will be detailed later, after extensive experiments - the focus was on 9x9 until now due to the challenge. - once again, very strong improvements in front of old versions of mogo leads to disappointing improvements against humans. However, I think that the best 9x9 go programs (mogo and others) are currently difficult opponents for high level players. Everything is under writing for publication and will be sent on this mailing list. Some technical details: - due to concurrency in memory access, heavier playouts come for free. If playouts are heavier (computationally more expensive) the speed-up becomes better. The nakade-problem involves heavier playouts, but the computational overhead is almost canceled by the speed-up improvement, as the speed-limit on 8-core machine is due to concurrency in memory access (for modifying the tree) more than to computational cost. - (very) unfortunately, the opening books generated for mogo without nakade are seemingly poor for mogo with nakade... this has destroyed weeks of work. If mogo wins the challenge, I'd like to point out that this is a collective success of the computer-go mailing list - without gnugo, crazystone, cgos, kgs and so on, mogo would just not exist. Thanks to all of you for that. I regret that due to some restrictions, we have not published every detail before, but it was just a matter of weeks and I'm happy that everything will be published soon, and if we loose the challenge I hope someone else will win something similar soon :-) Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
How well does the nakade improvement perform on 13x13? -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
How well does the nakade improvement perform on 13x13? no idea on 13x13, but it does not work on 19x19 (seemingly, perhaps we just need tuning...). Also, it works only, in terms of success rate against the old mogo, for sufficiently large number of simulations per move. Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
This event sounds very interesting! Saturday: 3/23/08 3:00 PM Saturday: 3/22/08 3:00 PM is right? Regards, Hiroshi Yamashita ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
Saturday: 3/23/08 3:00 PM Saturday: 3/22/08 3:00 PM is right? Hi; it's saturday 22. Olivier (stress++) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
Hi; it's saturday 22. Thanks! Regards, Hiroshi Yamashita ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
Hi, On Fri, Mar 21, 2008 at 10:14:49AM +, Nick Wedd wrote: Saturday: 3/23/08 3:00 PM Game I (9x9) Game II 9x9 Game III 9x9 Played with 1.5 hours from the start of one round to the next will this be with komi 7.5? Petr Pasky Baudis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
will this be with komi 7.5? Yes. Previous records against Guo Juan, as far as I know: - 1/3 wins with komi 7.5 - 9/14 wins with komi 0.5 (mogo black, i.e. komi in favor of mogo) Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
Olivier Teytaud wrote: Previous records against Guo Juan, as far as I know: - 1/3 wins with komi 7.5 - 9/14 wins with komi 0.5 (mogo black, i.e. komi in favor of mogo) Has the program become that much stronger on 9x9 recently? (Compared to the version was trying?) -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
The million dollar question: How well does Mogo scale on this number of processors?Can you give us at least some kind of generalization? My understanding is that on quad core machines you get most of the benefit by simply running parallel versions of the algorithm and sharing the data structure - but there must be many difficulties scaling this up to many machines over a network. Can I assume the data structure (tree) is distributed among different machines? - Don Olivier Teytaud wrote: For information on the mogo/pro challenge: - during preliminary tests, mogo has won 4/0 against a very high level human; at that time we were just very very very happy :-) - some other humans, supposed to be weaker, have however won some games at that time (before the nakade correction); - the Nakade weakness is currently assumed to be solved, but I'm not sure of that - at least mogo solves the old known nakade situations and is stronger than the old mogo; at that time we were happy again :-) - another improvement is that we currently have access to much hardware than during tests above; - but, a human, supposed to be weaker (non professional level, 5Dan however) has found some trick to win against mogo; this is not the nakade, but this is seemingly stable, and I am just not able of explaining how he can do that; he has shown me situations and says that in this kind of situations, mogo makes an error, but I just don't understand the common point in these situations. If we understand something we will post details here (at least the sgf files)... - in 9x9, the MPI (multi-machine) version of mogo wins with probability 80% against the non-MPI version. The speed-up is better in 19x19 and will be detailed later, after extensive experiments - the focus was on 9x9 until now due to the challenge. - once again, very strong improvements in front of old versions of mogo leads to disappointing improvements against humans. However, I think that the best 9x9 go programs (mogo and others) are currently difficult opponents for high level players. Everything is under writing for publication and will be sent on this mailing list. Some technical details: - due to concurrency in memory access, heavier playouts come for free. If playouts are heavier (computationally more expensive) the speed-up becomes better. The nakade-problem involves heavier playouts, but the computational overhead is almost canceled by the speed-up improvement, as the speed-limit on 8-core machine is due to concurrency in memory access (for modifying the tree) more than to computational cost. - (very) unfortunately, the opening books generated for mogo without nakade are seemingly poor for mogo with nakade... this has destroyed weeks of work. If mogo wins the challenge, I'd like to point out that this is a collective success of the computer-go mailing list - without gnugo, crazystone, cgos, kgs and so on, mogo would just not exist. Thanks to all of you for that. I regret that due to some restrictions, we have not published every detail before, but it was just a matter of weeks and I'm happy that everything will be published soon, and if we loose the challenge I hope someone else will win something similar soon :-) Olivier ___ 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] MoGo/professional challenge
On Fri, Mar 21, 2008 at 05:07:01PM +0100, Olivier Teytaud wrote: will this be with komi 7.5? Yes. Previous records against Guo Juan, as far as I know: - 1/3 wins with komi 7.5 - 9/14 wins with komi 0.5 (mogo black, i.e. komi in favor of mogo) What computing power did have that MoGo at its disposal? -- Petr Pasky Baudis Whatever you can do, or dream you can, begin it. Boldness has genius, power, and magic in it.-- J. W. von Goethe ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
What computing power did have that MoGo at its disposal? 4 cores, 2.4 GHz. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
On Fri, Mar 21, 2008 at 08:35:25PM +0100, Olivier Teytaud wrote: What computing power did have that MoGo at its disposal? 4 cores, 2.4 GHz. Thank you! That also puts the strength of CzechBot into some perspective. :-) Petr Pasky Baudis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
Has the program become that much stronger on 9x9 recently? (Compared to the version was trying?) *Parallelization: MPI == ~80% vs no mpi in 9x9 (for same number of cores). *Monte-Carlo improvement == strongly depends on number of simulations and number of cores (as the multi-core reduces the influence of the computational overhead), ~55% I guess. *Openings: 58%, for games with constant time per move (should be higher for games with given total time), if we only keep the openings which are still efficient in the new version of the code. Human-based openings do not work :-( *less interestingly, we have a better hardware than at that time (more cores, more GHz). == no doubt that this mogo is by far stronger than the one at Amsterdam 07. The improvement is much higher in 19x19, but humans are really too strong in 19x19 :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
Would you guess that mogo is 2 or 3 ranks stronger at 19x19 with all this hardware? I would love to see a fair match, perhaps a serious 2 or 3 dan player at 19x19 to be able to say with some certainty that Mogo has reached the dan levels. This assumes Mogo has reached this level of course. But if Mogo could play a few games against several 3 dan players and hold even - it would be clear evidence that it has broken the Dan barrier. Unfortunately, in order to get strong empirical evidence that it is at least a certain level, it has to overachieve significantly unless a huge number of games are played. I'm really excited about this match, but it will REALLY be exciting if Mogo wins any games at all against such a strong player, even at 9x9. - Don Olivier Teytaud wrote: Has the program become that much stronger on 9x9 recently? (Compared to the version was trying?) *Parallelization: MPI == ~80% vs no mpi in 9x9 (for same number of cores). *Monte-Carlo improvement == strongly depends on number of simulations and number of cores (as the multi-core reduces the influence of the computational overhead), ~55% I guess. *Openings: 58%, for games with constant time per move (should be higher for games with given total time), if we only keep the openings which are still efficient in the new version of the code. Human-based openings do not work :-( *less interestingly, we have a better hardware than at that time (more cores, more GHz). == no doubt that this mogo is by far stronger than the one at Amsterdam 07. The improvement is much higher in 19x19, but humans are really too strong in 19x19 :-) ___ 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] MoGo/professional challenge
The million dollar question: How well does Mogo scale on this number of processors?Can you give us at least some kind of generalization? unfortunately, using more than 10 nodes is probably not very very useful in 9x9, for the moment - but we have not tested that sufficiently, and we have not sufficiently tuned the parameters. A cluster is usefull for tuning a sequential algorithm, but we need a cluster of clusters to tune a parallel algorithm. Clearly, 1000 nodes for launching 40 mogo of 25 machines would be very helpful :-) In 19x19, we can use much more - but humans are really too strong. Winning 97% against mogo is not sufficient for winning against humans who beat mogo with probability 80%, and I'm also not sure that winning 97% against the old mogo is sufficient for winning against CrazyStone :-) One hope is that thanks to parallelization, heavy playouts come for free - this is clear in the multi-core parallelization, I guess that to some extent multi-nodes parallelization has a similar effect for different reasons. So, I believe in heavy playouts, whenever on sequential codes it might be a bad idea :-) Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
Would you guess that mogo is 2 or 3 ranks stronger at 19x19 with all this hardware? I just claim that mpi-mogo wins with very high probability against sequential-mogo in 19x19. But I'm afraid that the improvement is disappointing against humans. I hope better improvements are possible thanks to the fact that parallelization makes heavier playouts computationnally less expensive - communication and concurrency for memory access becomes negligible with heavy playouts. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo/professional challenge
Olivier Teytaud wrote: Would you guess that mogo is 2 or 3 ranks stronger at 19x19 with all this hardware? I just claim that mpi-mogo wins with very high probability against sequential-mogo in 19x19. But I'm afraid that the improvement is disappointing against humans. Hopefully it is still much stronger in reality. But I think your opponent in this case is too strong to really get much of a sense of what is happening. If Mogo really isn't improving against humans but is improving against other Mogo's and this is a substantial effect, it means something is wrong with the algorithm - I would guess this would indicate that Mogo is too selective. I feel your pain - there is no easy way to test any of this without more power yet.If you need a network of workstations to test a single processor program, then you need a several networks of workstations to test a single network of workstations! - Don I hope better improvements are possible thanks to the fact that parallelization makes heavier playouts computationnally less expensive - communication and concurrency for memory access becomes negligible with heavy playouts. ___ 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] 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. 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/
Re: [computer-go] MoGo/professional challenge
It was 2 cores 2.6GHz. (intel core2 duo). 2008/3/21, Olivier Teytaud [EMAIL PROTECTED]: What computing power did have that MoGo at its disposal? 4 cores, 2.4 GHz. ___ 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/
