Without the help of a Neural Network, the development of an Artificial Intelligence (AI) for Abak proved to be a challenging task and, in time, reached an apparent limit. However, it was a fun process to develop it, and it is still on duty to play on "easy", "normal", and "advanced" level. This is a post about how it works, and how it was made.

Fase 1, GOFAI PHP

Abak's first AI version was written in PHP and was deemed to crash the system with 'out of memory' errors, but it paved the road for a C++ version. It was the prototyping playground for me to figure out how in hell you would make an AI. The first time I run it hooked into the webserver (so I was effectively playing against it), It needed 15 very long seconds to select a move, and when I saw the server moving by itself, I went bananas and might have made a little dance. Not sure.

Fase 2, GOFAI C

So, the C/C++ Version of the AI, the first to go to a productive environment, my beloved GOFAI engine, was born over PHP ashes. It runs 29 analysis algorithms over thousand of positions in nanoseconds, and goes like this:

• Given a board position and a set of dice.
• Calculate a state
• Get every possible movement.
• Analyze each movement and give it a score.
• Select the 'best' Score.

Here is a diagram of the process.

It is composed by four main functions :

• Get Actions (Calculate Valid Movements):

  Given a Board Position and a dice roll, it calculates every valid movement.

  Valid movements can go from 0 to tens of thousands.

  In every language I have written this, I have taken an unnecessary recursive approach that makes the code so difficult to debug, but it is so beautiful. It has a couple of hundreds of lines of code but took me weeks to write, and then more weeks to translate it to C.

• Get state (Calculate Board state):

  Given a Board Position, It calculates a semantic state, they are pretty self explanatory:

  • Starting
  • MiddleGame
  • Running without Hope
  • Running with Hope
  • EndGame
  • Entering Home

• Analyse Movement (Calculate Scores for a Board Position):

  This is by far the most extensive algorithm of all. It analyzes the board features, each giving back a score, and then, based on the state calculated before, apply factors to them, so you can give importance to different aspects of the analysis based on the game-state.

  The AI started up with 8 algorithms and ended up with 29, a pinch:

  • Columns Height
  • Risk of Being hit
  • Risk of Being trapped
  • Home Strenght
  • Pivots of escape
  • Checkers at Bar
  • Safe Checkers

  Many of these algorithms were very basic at first or just didn't exist.

  Over time I worked on them, adding features and fine-tuning factors.

• Select Action (Select "Best" Movement):

  This algorithm is relatively trivial if you want just the highest score (as does the Advanced Level).

  For Normal and Easy Level, it selects a move randomly between a list of best actions; the size of it (or its tolerance to poor movements) is given by the level.

Because of C, this engine is lighting Fast, so I will always use it as the primary get-actions function.

Fase 3, GOFAI C Tune Up

To debug, troubleshoot, and fine-tune this engine, I had to build many tools to monitor the decision-making process. Unlike the Neural Network, each decision here is auditable, so you had at least that.

The process was fun but painfully slow. I played a lot against the CPU, and whenever I saw a poor move, I came to these tools to check out what went wrong. Sometimes that sent me to a path of fixing an algorithm, tunning a factor, or just building a new analysis model. Sometimes, and this was beautiful, It led me to reconsider my Abak Evolution Strategies.

In time, I had a pretty solid AI, but perfecting it more was becoming increasingly difficult. There were so many lines of code, so many scenarios, so massive operations, that debugging at code level was a heavy task, and fine-tuning factors manually was not giving results.

Fase 4, Desperation

But I wanted more because I do play Abak, and I needed a solid player to have fun, and there were not many humans that played it at the time (and even when I'm writing this).

And this approach has a lot of downsides:

• It calculates the state of the board given its current position, and that state is used to change the factors of the analysis algorithms for every valid action. That action, though, could have altered the state, but the engine doesn't take that into account.
• Manual fine-tuning of factors needed a tremendous amount of time. Fun times though, but tons nonetheless.
• The state is brutally difficult to calculate, given the number of possible scenarios. It has always been a flawed algorithm.
• Game Equity is impossible to calculate with precision, because this engine has an arbitrary score system for every analysis algorithm, and the final score does not reflect a probability of winning, it just works as a comparable score between different board positions. You can say it has a relative value instead of an absolute one.

Fase 5, The Awakening

An then, one day, on 2018, Google beat the GO Champion with its AlphaGo Neural Network, and there was so much fuss, and new awesome open source Machine Learning libraries became aviable, and were using home-GPUs to speed up the training process.

Of course, I already knew a bit about Neural Networks, but I had never built one, and honestly, I saw them as a task beyond my capabilities.

So I just couldn't resist, and expert level doesn't run on the GOFAI engine anymore, save for the get-actions part.

But this story ends here.

If you read it all through here, I'm amazed.

This text was written for SEO purposes by the honest Abak Evolution Team,
Aka. Samy Garib.