[Beginner] Game tree search on GPU

Hi all,

I’ve recently started work on my diploma project “Game tree search on GPU”. My goal is to implement an engine for the game “go” (that is my original idea, but there is a possibility to choose another game) in jCuda to help the player to win. The algorithm (engine) should be based on game tree search and run on cuda-enabled GPU. I have read some documentation, tutorials etc but there is plenty of information and I probably won’t be able to manage to read it all. I am a newbie in GPGPU so I need a help.

Has anyone of you ever written such code (for any game) in either Cuda or jCuda? I would really appreciate anything - source codes, parts of codes, documentation…
I do NOT want to copy it, I just need something to start with, some code to study, learn and write the engine for my game “go” and implement it in jCuda.

Also If you could give me some ideas where to get proper material to this problematics or some sample codes, existing solutions. etc, I would be really thankful.

Thanks in advance.

Andrej

Hi all,

I’ve recently started work on my diploma project “Game tree search on GPU”. My goal is to implement an engine for the game “go” (that is my original idea, but there is a possibility to choose another game) in jCuda to help the player to win. The algorithm (engine) should be based on game tree search and run on cuda-enabled GPU. I have read some documentation, tutorials etc but there is plenty of information and I probably won’t be able to manage to read it all. I am a newbie in GPGPU so I need a help.

Has anyone of you ever written such code (for any game) in either Cuda or jCuda? I would really appreciate anything - source codes, parts of codes, documentation…
I do NOT want to copy it, I just need something to start with, some code to study, learn and write the engine for my game “go” and implement it in jCuda.

Also If you could give me some ideas where to get proper material to this problematics or some sample codes, existing solutions. etc, I would be really thankful.

Thanks in advance.

Andrej

Hi andrej,

i think the best thing to do for you is

  1. study the problem and choose the game before start implementing code

  2. implement the algorithm in java or another high-level language

  3. migrate the code to cuda .

for the 1st and the 2nd step there are tons of materials in internet, in particular for the 1st step i suggest you the book “Artificial intelligence, a modern approach”

for the cuda implementation, once you’ll have a well-working java/C/python version of your algorithm, the main problem will be to translate the code

in cuda. to do this i can suggest you books “programming massively parallel processors” or “CUDA by examples”, they are not expensive, not too big (about 250 pages) and easy to read for a beginner.

Andrea.

Hi andrej,

i think the best thing to do for you is

  1. study the problem and choose the game before start implementing code

  2. implement the algorithm in java or another high-level language

  3. migrate the code to cuda .

for the 1st and the 2nd step there are tons of materials in internet, in particular for the 1st step i suggest you the book “Artificial intelligence, a modern approach”

for the cuda implementation, once you’ll have a well-working java/C/python version of your algorithm, the main problem will be to translate the code

in cuda. to do this i can suggest you books “programming massively parallel processors” or “CUDA by examples”, they are not expensive, not too big (about 250 pages) and easy to read for a beginner.

Andrea.

i agree. its often easier to start w/serial code and then translate. just keep in mind that when you move it over to the gpu you’ll have a LOT more parallel processing power (literally thousands of threads). so keep this in mind as you’ll probably want to use an algorithm that can take advantage of this. in fact, if the algorithm doesn’t parallalize well, it will probably perform worse on the gpu. i’d recommend reading the first 2 chapters of the programming guide before you begin, so that you can get a basic overview of the programming model you’ll eventually have to fit your algorithm into. (it’s very short, like 10 pages.) and then like the above poster said, start it in c or java or whatever you’re comfortable with. and then once you got it working there, start on translating it over. hell, i’m no newbie and i STILL do it that way.

i think Go would be a good choice and it sounds like it would be a fun project.

i agree. its often easier to start w/serial code and then translate. just keep in mind that when you move it over to the gpu you’ll have a LOT more parallel processing power (literally thousands of threads). so keep this in mind as you’ll probably want to use an algorithm that can take advantage of this. in fact, if the algorithm doesn’t parallalize well, it will probably perform worse on the gpu. i’d recommend reading the first 2 chapters of the programming guide before you begin, so that you can get a basic overview of the programming model you’ll eventually have to fit your algorithm into. (it’s very short, like 10 pages.) and then like the above poster said, start it in c or java or whatever you’re comfortable with. and then once you got it working there, start on translating it over. hell, i’m no newbie and i STILL do it that way.

i think Go would be a good choice and it sounds like it would be a fun project.

There was a developer summit talk on this at GTC last month:

http://developer.download.nvidia.com/compu#RANGE!A178

There was a developer summit talk on this at GTC last month:

http://developer.download.nvidia.com/compu#RANGE!A178

go is particularly interesting because the number of possible game permutations is explosive. even chess pales in comparison. professional human players are usually much better than even the best computer players. so there’s presumably some interesting algorithms for solving go that we haven’t found yet.

go is particularly interesting because the number of possible game permutations is explosive. even chess pales in comparison. professional human players are usually much better than even the best computer players. so there’s presumably some interesting algorithms for solving go that we haven’t found yet.

I didn’t post the link to say “the problem is solved, so don’t waste your time”, I posted it so that the OP could see how the researcher implemented their game-tree algorithms on the GPU and then adapt their techniques for Go.

Anyway, there’s also a Go engine which uses some kind of Monte Carlo algorithm to do the game tree search, which might map to the GPU’s capabilities quite well (even across multiple GPUs):
[url=“UCT at Sensei's Library”]http://senseis.xmp.net/?UCT[/url]

I didn’t post the link to say “the problem is solved, so don’t waste your time”, I posted it so that the OP could see how the researcher implemented their game-tree algorithms on the GPU and then adapt their techniques for Go.

Anyway, there’s also a Go engine which uses some kind of Monte Carlo algorithm to do the game tree search, which might map to the GPU’s capabilities quite well (even across multiple GPUs):
[url=“UCT at Sensei's Library”]http://senseis.xmp.net/?UCT[/url]

Hi,

I’m familiar to game tree searching algorithms and CUDA, but unfortunately not in combination. What algorithms do you want to implement? Alpha Beta Pruning? Zero Window search? I would recommend starting with an easier game like NIM. If you got your algorithms working on a small problem, you can adapt the state and transitions to another game like go.

Regards,

Kwyjibo

Hi,

I’m familiar to game tree searching algorithms and CUDA, but unfortunately not in combination. What algorithms do you want to implement? Alpha Beta Pruning? Zero Window search? I would recommend starting with an easier game like NIM. If you got your algorithms working on a small problem, you can adapt the state and transitions to another game like go.

Regards,

Kwyjibo

we’ll we are on the subject i had an idea for a go player on the gpu. essentially it’s evolving four small nueral nets, one for empty intersection, one for player occupied, one for enemy occupied, and one for border. then these neural nets would be connected in a grid just like the board is, and would interact like reaction-diffusion. when a predetermined “channel” in the nn’s is above a certain threshold for all nn’s, the empty-intersection nn with the highest value in another predetermined channel is the chosen move.

then you’d just use a genetic algorithm or something similiar to evolve the ai.

it’s too ambitious of a project for me. if anyone wants to take a crack at it, have at it. i’d be anxious to see the results.

we’ll we are on the subject i had an idea for a go player on the gpu. essentially it’s evolving four small nueral nets, one for empty intersection, one for player occupied, one for enemy occupied, and one for border. then these neural nets would be connected in a grid just like the board is, and would interact like reaction-diffusion. when a predetermined “channel” in the nn’s is above a certain threshold for all nn’s, the empty-intersection nn with the highest value in another predetermined channel is the chosen move.

then you’d just use a genetic algorithm or something similiar to evolve the ai.

it’s too ambitious of a project for me. if anyone wants to take a crack at it, have at it. i’d be anxious to see the results.

thank you all for expressing your opinions and giving ideas.

I’ve started reading some CUDA development guides and implementing pieces of code to get in touch with CUDA. I’ve given up the original idea of the game “go” because this would be too complicated for me to start with. I will probably implement the game-tree search algorithm for reversi or checkers. As soon as I have problems I will bother you again:)

Anyway, if you find some game-tree search algorithm implemented in cuda, please share with me;)

thanks,

Andrej

thank you all for expressing your opinions and giving ideas.

I’ve started reading some CUDA development guides and implementing pieces of code to get in touch with CUDA. I’ve given up the original idea of the game “go” because this would be too complicated for me to start with. I will probably implement the game-tree search algorithm for reversi or checkers. As soon as I have problems I will bother you again:)

Anyway, if you find some game-tree search algorithm implemented in cuda, please share with me;)

thanks,

Andrej

A one person game is usually called a puzzle. They still have game trees, but can be easier to program.

Look at SameGame, Morpion Solitaire or even Sodoku.

A one person game is usually called a puzzle. They still have game trees, but can be easier to program.

Look at SameGame, Morpion Solitaire or even Sodoku.