Software developer blog

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. (-;

@ //