Update #5

This might not sound like the most exciting update, but it took a lot of work to get this feature done:

Cascade Cafe now has a whole new AI behind the scenes, which should make the game much more of a challenge.

The previous AI did have some general smarts to it. It wasn't completely random (even though it seemed like it sometimes), and it would try to figure out the best move to play. However, it had one major drawback - it lacked the ability to look further ahead than it's current turn. By that I mean it would only try to figure out what the best possible move for the current turn is, and not take into account what corners it would paint itself into. This could be seen in plays where the AI would place a tile down with all bridges facing a wall, which looked pretty silly.

The new AI uses a concept called the Monte Carlo Tree Search. It's actually what Alpha Go uses underneath the mountains of machine learning they have placed on top. But the general concept is the same - rather than trying to calculate only the best move this turn, play out simulations of the game from each possible play available with your current tiles and build out a tree which shows wins/loses. Then when the timer runs out, pick the node from the tree that had the best results.

In the original version of the game, I only had to run one simulation for the given turn - now I had to run not just hundreds of simulations, but possibly thousands in just a second or two! Turns out there were a LOT of tweaks to the game logic I needed to make in order for this to be possible. I was able to get maybe 20 simulations per second at the beginning, but after spending most of my holiday break on it, I managed to get it up to 5000-6000 simulations in 1-2 seconds. I'm pretty happy with that.

Previously it was mentioned by Captain_Guile that the level 10 AI wasn't that hard to beat. While there's still lots of tweaks to the AI, it should win more often than it loses now. I know I lost a few in a row (and saw a few ideas for plays I hadn't thought of before).

Just one extra note - for testing this I found it useful to add a CPU-Vs-CPU mode to the game. I'm thinking of setting up a stream with all the tree search weights and constants visible in a debug box on screen. Then I can have the CPU play against itself all day and record the wins and losses, and see which values lead to the best results. Might be fun.

Ok that's it for now. The next series of updates will probably be around the story mode and adding an extra character to the game. There's always more work to be done!

If you have any questions about the MCTS implementation, come and ask and say hi on the forums.