Super-powering computer go

[vash3g]

http://www.theregister.co.uk/2012/12/07 ... cking_rig/

Using 25 ATI GPU's this researcher can crack a 14 character hashed password in six minutes. Regular brute force methods will take 5.5 hours. Has any of this been applied to computer go at all? It's been a known fact for some years that using GPU's for processing does 5-6x the processing that regular CPU's can do. CUDA is the future, is anyone using it yet?

[speedchase]

http://www.theregister.co.uk/2012/12/07 ... cking_rig/

Using 25 ATI GPU's this researcher can crack a 14 character hashed password in six minutes. Regular brute force methods will take 5.5 hours. Has any of this been applied to computer go at all? It's been a known fact for some years that using GPU's for processing does 5-6x the processing that regular CPU's can do. CUDA is the future, is anyone using it yet?

You completely misunderstood the article. 5.5 hours is how long it takes to break for a different type of hash, not a different to use a different method of cracking it. GPU's are for processing graphical information. Not so much useful for go related calculations, although with a good GPU, the virtual board the moves would be played on would look beautiful.

[lovelove]

http://www.theregister.co.uk/2012/12/07 ... cking_rig/

Using 25 ATI GPU's this researcher can crack a 14 character hashed password in six minutes. Regular brute force methods will take 5.5 hours. Has any of this been applied to computer go at all? It's been a known fact for some years that using GPU's for processing does 5-6x the processing that regular CPU's can do. CUDA is the future, is anyone using it yet?

You completely misunderstood the article. 5.5 hours is how long it takes to break for a different type of hash, not a different to use a different method of cracking it. GPU's are for processing graphical information. Not so much useful for go related calculations, although with a good GPU, the virtual board the moves would be played on would look beautiful.

GPU processing are also used in non-graphic processing, for its fast speed.

[speedchase]

http://www.theregister.co.uk/2012/12/07 ... cking_rig/

Using 25 ATI GPU's this researcher can crack a 14 character hashed password in six minutes. Regular brute force methods will take 5.5 hours. Has any of this been applied to computer go at all? It's been a known fact for some years that using GPU's for processing does 5-6x the processing that regular CPU's can do. CUDA is the future, is anyone using it yet?

You completely misunderstood the article. 5.5 hours is how long it takes to break for a different type of hash, not a different to use a different method of cracking it. GPU's are for processing graphical information. Not so much useful for go related calculations, although with a good GPU, the virtual board the moves would be played on would look beautiful.

GPU processing are also used in non-graphic processing, for its fast speed.

true, but their use outside of graphical processing is limited. How they could be applied to go playing algorithms is questionable, and it still doesn't solve the problem, it would just make a solution a little faster when it is found, if it could even do that.

[kivi]

MCTS is an embarrassingly parallel algorithm. So it is easy to move it to GPUs. Bots on KGS are already running on multi-core, or even clusters, afaik.

But I kinda remember a statement about Zen, that it doesn't benefit much from more computational power after it is able to do N playouts per move. E.g., if the computer is weak, and it can do N/2 playouts then it is 1-2 stones weaker than usual, but if it can do 10xN playouts it is not really stronger. I am not sure where I read this, or if this is true - does anybody know?

[Phelan]

MCTS is an embarrassingly parallel algorithm. So it is easy to move it to GPUs. Bots on KGS are already running on multi-core, or even clusters, afaik.

But I kinda remember a statement about Zen, that it doesn't benefit much from more computational power after it is able to do N playouts per move. E.g., if the computer is weak, and it can do N/2 playouts then it is 1-2 stones weaker than usual, but if it can do 10xN playouts it is not really stronger. I am not sure where I read this, or if this is true - does anybody know?

I also remember something like this being posted somewhere in the forum. Not sure if it was Mike Novack or if it was Remi Coulon that talked about it, but I think it was one of them.

[badukJr]

You completely misunderstood the article. 5.5 hours is how long it takes to break for a different type of hash, not a different to use a different method of cracking it. GPU's are for processing graphical information. Not so much useful for go related calculations, although with a good GPU, the virtual board the moves would be played on would look beautiful.

GPU processing are also used in non-graphic processing, for its fast speed.

true, but their use outside of graphical processing is limited. How they could be applied to go playing algorithms is questionable, and it still doesn't solve the problem, it would just make a solution a little faster when it is found, if it could even do that.

I use GPUs to solve complex computational problems. They are not only for graphics.
Check out:
http://www.nvidia.com/object/cuda_home_new.html

That said, it would be non trivial to adapt the code for a many code GPU for bots, and as people stated the payoff would be questionable at best. The advantage of keeping the code for general CPU hardware is that its very portable.

[macelee]

GPUs can do floating point calculations incredibly fast. The raw power is there. The difficulty is always how to harness that power. It is still rather difficult to port many scientific algorithms to GPU. I imagine Go applications are more challenging.

[Samura]

MCTS is an embarrassingly parallel algorithm. So it is easy to move it to GPUs. Bots on KGS are already running on multi-core, or even clusters, afaik.

But I kinda remember a statement about Zen, that it doesn't benefit much from more computational power after it is able to do N playouts per move. E.g., if the computer is weak, and it can do N/2 playouts then it is 1-2 stones weaker than usual, but if it can do 10xN playouts it is not really stronger. I am not sure where I read this, or if this is true - does anybody know?

I also remember something like this being posted somewhere in the forum. Not sure if it was Mike Novack or if it was Remi Coulon that talked about it, but I think it was one of them.

Yes, Remi said one time that at certain point you start to get diminished returns for the increase of computational power.

As I understood, there is just so much you can do with a certain evaluation function. It's not enough for a program to have the reading of a 20 dan if it doesn't "know" how to distinguish better positions from worse ones.

[emeraldemon]

A GPU is what we call a SIMD processor: Single Instruction, Multiple Data. So instead of saying "add register 1 to register 2", it says "Add all the elements in this vector to all the elements in that vector". The key is that you can only take advantage of SIMD hardware if you want to do the exact same floating point operation to lots of numbers (I think newer GPUs can do ok on integers as well, I don't know very much about that). In addition, there's usually a significant cost associated with moving numbers to and from the GPU, so your task needs to do lots of these lock-step computations to take full advantage of the GPU's speed.

I don't know a lot about the details of Monte Carlo algorithms, but I'm not at all sure that GPUs would be able to speed up their progress. At a high level it is very parallel, but GPUs require a very specific kind of parallelism to be most effective.

[daniel_the_smith]

I've got half a working go bot and I've written a very small amount of GPU code previously for something unrelated. It would be incredibly annoying to write code that did playouts in a form that could run on a GPU. I think it'd be possible. You'd lose some time transferring data into and out of the GPU, and also you have to batch up a bunch of playouts (but maybe you could do that while the GPU was running).

(PS @emeraldemon, GPUs do have SIMD for doing vector math but the parallelism comes (approximately) from breaking the rectangular or cubic work area into smaller units and executing each on its own core.)

[Rémi]

http://www.theregister.co.uk/2012/12/07 ... cking_rig/

Using 25 ATI GPU's this researcher can crack a 14 character hashed password in six minutes. Regular brute force methods will take 5.5 hours. Has any of this been applied to computer go at all? It's been a known fact for some years that using GPU's for processing does 5-6x the processing that regular CPU's can do. CUDA is the future, is anyone using it yet?

The topic of using GPUs for programs comes up from time to time in the computer-go mailing list.

http://www.mail-archive.com/computer-go ... 12474.html
http://www.mail-archive.com/computer-go ... 05577.html

So far, no strong program came out of these efforts. It seems difficult to take advantage of those processors efficiently for Monte-Carlo Go. GPUs are efficient only for certain types of calculations.

Rémi