I came across a game recently - a variation of chess called Capture The Sarrum - and I decided I wanted to win against one of my friends. Being not very good at chess myself, I came up with a bright idea - why not write a computer program to play on my behalf?

The full source code is available on Github.

The Game

As I mentioned, Capture The Sarrum is a variation of chess. It was designed for the computing A-level course. The main difference between this game and chess is that in this game most of the pieces are only able to move one square at a time. When starting out, I thought this would make it easier to build an AI for than chess, though I am now doubting that...

MinMax

The algorithm I chose to use for the AI was the minmax algorithm. When I chose it, I thought it would be fairly simple to implement - the concept is fairly simple.

The algorithm gives each game state a rating. Normally 1 is used to represent victory and -1 loss. The key part of the algorithm is that each state's value is based entirely on the ratings of the subsequent states. In states where it is the AI's turn, the state gets the value of the highest rated subsequent state. In states where it is not the AI's turn, the state gets the value of the lowest rated subsequent state. This is where it's name comes from. Minimum rating then maximum rating.

This algorithm works on the assumption that the opponent will play the best move.

Performance

There is one thing I haven't mentioned though. In Capture The Sarrum, games can continue infinitely - which makes it impossible to rate states using only the above rules - you will never finish calculating all possible states. Instead, we may calculate some number of moves ahead and rank each state based on a set of rules - then use the minmax on these. When the program was calculating all possible states within a few moves, it was slow but worked ok until the rooks were developed. In Capture The Sarrum, these were the only pieces that could move any distance, which meant there were far more possible states when they were moving. This caused the program to consistently exceed its 1GB RAM limit half way through a game and crash. This issue needed to be fixed.

I first reduced the memory footprint of each state calculation, but it was still too much. I found out the AI was processing over 15 million states at times! This number had to be cut down. I could easily see that the majority of the states weren't even worth processing, some extremely bad moves should be dismissed immediately. I needed a way to trim states that weren't worth processing. I will say I didn't do a particularly good job of this, but it was functional...

Ranking Rules

Deciding how to rank positions effectively was not easy. The most obvious method is based on how many pieces the AI has compared to its opponent. However, I found the AI didn't bother developing its pieces, though it would move its pieces to safety if threatened and would take pieces if given the opportunity. This behaviour would have been easy to achieve without minmax.

I then added several other metrics for success such as taking the centre, moving pieces forward, pinning pieces and defending pieces. These created more interesting and more successful game play. Each of these things were given a weight which dictated how important they were compared to each other. I even added a system which allowed different weights for these things near the beginning and end of a game. Despite this, the ranking was far from perfect. The AI played some silly moves at times because it thought pins were worth more than a bishop.

I had just set all of the weights by hand and needed a way to get some better values for them. However, there were over 40 weightings that needed to be adjusted. I decided I needed an automated way to decide on them. Read my article on genetic algorithms to find out how.