Choose an opponent: Random Greedy Greedy Tuned Minimax Minimax Tuned

I've always enjoyed othello, so I figured it would be a great game to apply various ML algorithms to, from a simple greedy search algorithm to training a reinforcement learning (RL) agent.

In the javascript game above you can play against the following five different algorithms of increasing complexity:

Random Choice

As the name suggests this opponent uses random choices to select its move, don't expect any impressive play here.

Greedy

This greedy opponent chooses the move which flips the most tiles. Whilst tempting, this sort of short term thinking also won't lead to very impressive play.

Greedy Tuned

Like the previous greedy opponent this algorithm seeks to maximise the immediate board state. However unlike the previous greedy opponent the immediate board state is combined with additional bonuses for certain strategic tiles. This weights in favour of edges and corners, whilst down weighting tiles adjacent to edges.

Minimax

The minimax is a tree search algorithm that explores all possible sequences, up to some pre-defined depth. The name arises from the definition of the optimal move as the maximised value relative to the players choice and minimised relative to the opponent's actions. The depth here is set to 4, you will notice that even this relatively shallow search becomes very computationally demanding. More efficient searches exist with algorithms such as alpha-beta pruning and principal variation search.

Minimax Tuned

Like the previous minimax opponent this opponent uses the minimax algorithm to search for the optimal move. However unlike the previous minimax opponent the board value is not just the number of tiles owned, but also weighted by the tile values.

I am working to include more options to the online version, using agents trained with RL techniques such as Q-Learning.

If you're curious to see how I implemented this game and the opponents you can take a look at the code here.