Software developer blog

Game of Life on the GPU

Conway's Game of Life is one of the most popular code katas, and the one we will exercise on our next code retreat this Saturday. I have done this kata, quite a number of times, but this time there was a twist: I used the GPU on my Nvidia GTX 560 to calculate the steps of evolution, and to draw them as well. Here is how the result looks like:

Puffer train in Game of Life

Puffer train in Game of Life. Living cells are green, they increase the blue chanel by 1 in each generation, and leave a faiding red trail after they die.

The igniter of this exercise was that I read a book on CUDA programing, and it was quite a disappointment. The examples were really far from anything I would call clean code, or at least easy to understand: it was spaghetti with huge meatballs in it. That kind of examples require a lot of explanation, which basically took up most of the books volume, and there was little left for the useful stuff. So I got curious: is it CUDA that promotes bad code, or the writers of the book didn't care enough? I had a preconception that there was nothing wrong with CUDA  - and actually it's a pretty neat language - so I set out on a quest to code Game of Life in CUDA, and try to make it as clean as possible.  I don't claim, that my code is perfect, but I hope it's going to be an easy read for anyone who tries.

You can download the result of my quest by clicking here, or just browse it as HTML by clicking here. The rest of the blog entry - basically a retrospective of the project, and a few remarks on CUDA features - might not make much sense without looking at parts of the code. If you'd like to compile, than you will need the nvcc compiler for CUDA, the CUDA Toolkit, GLUT and GoogleTest to run my unit tests. Please note, that the code is not production quality: it may well throw exceptions at you, it's only tested on Ubuntu, and it is not performance optimized in any way. (Even the algorithm is the most naive one.)

@ //

Snake cube

Few weeks ago one of my colleagues showed me this puzzle:

Snake cube

Snake cube puzzle

It's basically composed of 27 cubes, which are linked together by their faces. Each pair can be rotated around their common face. The aim is to fold the snake into a cube like this:

Solved snake cube

The snake cube once it is solved

Needless to say, my first thought was to write a backtracker that solves the cube for me. After all it's more fun to write the program, than to play around with it for hours. It didn't take long. After I was done with that, I started to ask myself questions like:

  • Are there other combinations with a single solution?
  • Are there combinations with more than one solution?
  • Are there palindromic snakes, that are solvable?
  • How many different solvable snakes are there?

I quickly found the answers to those on Jaap's Puzzle Page. I won't repeat the results that are available there, go and check it out if you are interested. On the other hand, it did not contain the source code for the backtracker, so I decided to show you how something like that could be done.

@ //

Gomoku perfect play

The other day I had a very boring job to do. I had to listen to a sound recording of a workshop I've been attending few weeks ago and sum up the ideas that appeared during brain storming. I couldn't come up with any other solution, but to listen to it while playing Gomoku. It's not a time critical game so I could switch back to writing LaTeX code whenever I needed, and since it's quite an easy game, I still had the brain computing power to multitask. (By the way I use GNU screen to manage my terminal sessions, and vim to code so it just seemed convenient to use the BSD Games implementation of Gomoku... pretty old school, huh?)

Anyhow... as most of you probably know Gomoku is a pretty unfair game, as the first player has a winning strategy... but how hard is it to memorize the winning strategy? Is it even possible? Well... I set out on a journey to find out about that. I spent about half an hour to research Google for any existing perfect play algorithms, but didn't have much luck. Next I tried to find out how computer plays Gomoku... The key concept seems to be Minimax search and Alpha-Beta Pruning, but that is a highly heuristic approach, and since I could beat the algorithm as second player, it does not result in a perfect play either. (Although I could guess that even without winning against the computer.)

Well... I'm stuck at this point. I think I'll read what L. Victor Allis has written on the topic in his thesis. But before doing so, I'll have to get back to coding for food. (-;

@ //