Joachim Breitner

Bejeweled AI in Haskell

Published 2009-04-03 in sections English, Digital World.

The German online magazine „FreiesMagazin“ has started a programming contest yesterday. The task is to write an AI for a two-player bejeweled-like game, where the stones that you can match cause your opponent to lose live points.

This evening I thought that this would be a nice finger exercise in Haskell programming, and indeed it was. Most time was spent writing the code that communicates with the game supervisor (via text files) and that re-implements the game logic to simulate the next steps. The example code is in C++, so I had to do it again, but it’s rather short: 123 lines, consisting of 8 lines for the module header, 26 lines for the data definitions, 16 lines for in- and output and 73 lines for the actual rules of the game.

Writing the rest was really easy. 15 lines use a generic Haskell module to implement alpha-beta-search in Strategy.hs, and 6 lines of code to glue it all together. And I’m sure one can do better...

The program wins against the demo AI. By choosing other algorithms provided by game-tree might even improve that. Feel free to try it out!

My code is available in a darcs repository (browse) under the GPL2 or later and I invite everyone to use it as a base for contest entries. If you want to use Haskell, you can just replace the Strategy.hs and do not have to re-implement the game logic. If you submit such a program, just make sure you credit me appropriately. Also, as always, patches are welcome. If the code is too slow for your taste, you can decrease the depth parameter in Strategy.hs.


Hello Joachim,

I was pleased to see my game-tree module being used.

I looked at the code of Strategy.hs - you have a comment querying whether there is a bug because you have to negate the score for alternate players.

This is not a bug - it is a documented feature in Game_tree.hs:

-- Needs to be sensitive to whose turn it is to move.
-- I.e. it must return values of the opposite sign if the other player is to

This is a feature of negamax and other such algorithms. It makes the logic simpler compared with minimax.
#1 Colin Adams (Homepage) am 2009-04-03
Oh nice.

Hrmm. I should dig up some MTD(f) with iterative deepening code that I have lying around and adapt it to work with the GameTree library. You seem to have a nice integral board evaluation function, so that should help out quite a bit at cutting your effective branching factor.
#2 Edward Kmett (Homepage) am 2009-04-04
About the results, see:
#3 Joachim Breitner (Homepage) am 2009-06-05

Have something to say? You can post a comment by sending an e-Mail to me at <>, and I will include it here.