Triskelion and the minimax algorithm

A couple of years back I wrote about a game called Trippples.

This patented strategy game requires you to move your transparent marker from one corner of the game board to the other before your opponent. The games unique feature is that your available moves are determined by arrows under your opponent’s marker.

The patent expired long ago, so I started working on a digital version of the game at the end of last year. I thought I’d lost the data in a hard drive failure, but managed to salvage the C# classes from the Unity project and finished v1 of the game a couple of months ago.

You can play my version, called Triskelion, on newgrounds.com.

The reason I wrote a digital version was because I wanted to write an AI for the game. I settled on using a simple minimax algorithm.

Minimax is a recursive algorithm that can be used to select the best move in a game by assigning a score to the position resulting from each available move, then assigning a score to the position resulting from each available counter-move, and so on. The score indicates how good the move is for the player. This recursion creates a tree of all available moves and counter-moves which stops either after a given distance from the “root” of the tree, or when the game is finished in all branches.

The scores are then evaluated. For each move in the tree the best move is the one that maximises the player’s score while also avoiding giving the opponent opportunities to minimise the player’s score (hence minimax). A single best move is selected based on the evaluation.

The minimax algorithm works well for simple games like nought-and-crosses or tic-tac-toe because there are a limited number of moves and a maximum of 9 turns before the game is finished. It doesn’t take much computing power to completely determine the course of the game.

Minimax can be used for more complex games, even chess. But the large number of available moves and the length of games mean that, realistically, it can only be used to look ahead a few moves at a time. It works well for end-games, though, once there are fewer pieces on the board and, therefore, fewer moves available.

For Triskelion, minimax is realistic because there are usually only three moves available each turn, so the move tree isn’t “wide”. However, games can last a large number of moves, so the recursion normally has to be limited by “depth”. In my implementation, I decided to use three levels of AI that looked ahead either 1 move, 3 moves or 5 moves.

The tricky bit was deciding how to assign a score to each position. The goal of the game is to get your piece to your home square before your opponent so a big part of the score was based on the distance to the home square for eaach player. But that score alone would be a very naive algorithm ignoring strategic subtleties.

So, I also added a mobility based on how much theoretical freedom of movement each position had. Being on the edge is worse than the centre of the board, and blank squares that blocked movement also affect the mobility score.

The actual number of moves available in each position was also factored into the total score. A position with only one available move scored worse than a position with three or even more moves.

Each factor is given a different weight so that it affects the final calculation more or less depending on how important it is to the overall strategy. So the most important factor was the distance to home and the least important was the theoretical mobility.

When I started, I had had high hopes of using some sort of genetic algorithm to optimise these weights but that idea was quickly abandoned. Instead, I just guessed a few values and tweaked them until the AI seemed to be playing OK.

You can see some of the “thought processes” by playing the game and turning on the web console of your brower. The AI outputs a log of the different scores assigned to each move ordered clockwise starting from 12 o’clock.

Sadly, the scores by themselves aren’t very revealing. Hopefully I will have a chance to (a) revisit the genetic algorithm idea and (b) display the outcome of the minimax algorithm in a more human-readable format to help understand the strategy.

So, at the moment, the game works and is playable but it’s a project that is still a long way from being finished.