[Interview] The challenge of creating Chessaria's mission-based Chess engine

Meet Enrique Sánchez Acosta, Ph.D. computer scientist, R&D software engineer and computer chess programmer behind the engines Chessaria A.I.C.E. & Alfil.

In this interview Enrique discusses the challenge of creating an asymmetric mission-based chess engine for the needs of Chessaria, a turn-based fantasy game that combines Chess battles and story-based missions. The game was developed by Pixel Wizards and released on Steam earlier this year.

Hi Enrique, for how long have you been developing chess engines?

Enrique: Hi, I started to develop chess engines around 1998. Since then I have made several engines for different platforms (Windows, Linux, Android). Between 2000 and 2002 I published several chess video games while I was working in other video games companies developing football video games.

I am an amateur player and started playing chess at university and I still play in some competitions whenever I can.

What makes Chessaria’s engine so different from the other chess engines and how did it influence the game design?

Enrique: The chess engine developed for Chessaria is something completely different from what is developed today. Of course, the base is very similar to other chess programs, but the engine’s goal is to be a strategy engine for turn-based battles, where thanks to a new communication protocol between the interface and the engine, different rules can be assigned to the engine. Those new rules are completely different from the rules used in classical chess and other kinds of chess variants that exist today. For example, there is no limit on the number of pieces you can play and you can even play without kings. The game engine supports new kind of pieces like holes, walls, collectibles and new rules  for the pieces’ movements, etc. In addition to missions that have nothing to do with the rules of a game of chess but rather with a battle between two sides. Everything is possible in the new engine, which drastically increases its complexity, but allows the creation of new scenarios never seen until today on a chessboard.

Could you describe the biggest challenge you faced while working on Chessaria’s engine?

Enrique: The biggest challenge I faced when it came to create the engine was not to create the logic for the new pieces or the new rules, but creating the missions that the A.I. has to complete.

The engine needed to be able to support different type of missions to win the game, which were not the typical checkmate. It included capturing a series of pieces or securing a series of positions, and not only that, but they can be mixed in an asymmetrical way. So, the A.I. must not only complete its mission but also has to be aware of the opponent’s mission and prevent him from completing it. You may be playing to capture a square with a piece and the other side to kill a series of pieces and win with it. This greatly complicates the A.I. of any chess engine, but after much joint effort by the entire Chessaria development team, spectacular results have been achieved and the Chessaria engine has become a new approach to strategy games with great possibilities of expansion.

How did you come to join Chessaria’s team?

Enrique: When the Pixel Wizards team contacted me, I thought they just wanted a version of a chess engine, but when they started telling me everything they had in mind, it seemed like such an interesting and novel idea that I could not pass up the opportunity to work with them, I had to be there! It was a great challenge.

Now I am grateful to be part of this project that has allowed me to create a new chess engine much more versatile and adaptable for many more approaches.

How does the engine take advantage of multithreading and what are the benefits for multicore CPUs?

Enrique: The engine can use up to 16 CPUs at the same time (at least for the moment) which increases the calculation power of the engine. However most users playing against the engine don’t require the use of so much power, since a single CPU produces enough computing power to defeat 90% of human chess players from all over the world.

How powerful is Chessaria’s chess engine?

Enrique: The engine uses all the latest knowledge acquired during years of development of other chess engines, so its level is very high. Chessaria’s engine can beat the vast majority of chess players so it was necessary for the team to find an algorithm capable of adapting the game’s capacity to the different levels of players. The engine can be configured to play based on 16 different levels of difficulty to adapt to the ELO of each player. The design team made sure the game would adapt to the player’s learning curve as he progresses in the adventure.

Can we talk about Elo Score?

Enrique: ELO is a classification of force used to classify chess players. An amateur player usually starts playing well with 1400 ELO and a master with 2300. The great masters and professionals have more than 2700 ELO. The Chessaria engine can play at the level of the great masters, approximately 2800 ELO or more.

How good would a Grandmaster (GM) do against Chessaria AICE running on a 16 core computer?

Enrique: Chessaria AICE could be a good training engine! I believe a GM would be able to put a chess engine like Chessaria’s in a tight spot as he would know how to find specific positions that require a lot of computing which would tip the balance in his favor. Only a few of the best engines in the world can play face to face against the greatest GMs. Chessaria AICE can win against many of them but defeating the world champions isn’t an easy task!

Can you tell us a bit more about how the engine evaluates the moves? How does it handle asymmetrical missions?

Enrique: Artificial intelligence algorithms like chess programs are called "zero-sum games": The number of points is the same on both sides of the board so a side wins points because the other side loses points. Therefore, the rules of the game are generally the same for both sides.

However, when you integrate asymmetrical and different type of missions, the evaluation system has to change completely. Designing an engine that can support missions so different from one level to the other, was without a doubt, one of the biggest challenges we faced!

We had to create a series of equivalence so that the evaluation of a side was equivalent to the opposite side. The objective being to be able to compare the two sides of the board by making sure the zero-sum’s algorithms were still valid as without proper equivalence in the evaluation, points can’t be added or subtracted, since their value would be different.

This could be compared to playing football were one side wins by scoring 3 goals while the other side wins by being in possession of the ball for 30 minutes. The side that tries to score 3 goals can’t just evaluate the situation based on the number of goals scored, but must also take into account the time the other team has been in possession of the ball even if it isn’t it’s mission. The other team, has to stop goals from being scored without losing sight of their objective of keeping the ball for as long as possible.

The situation is similar with asymmetrical chess missions: All the rules introduced in the game must be taken into account in order to establish a strategy and decide if it is better to opt for a defense or an attack depending on the position and the missions assigned to each team.

How powerful is Alfil and what differentiates it from Chessaria?

Enrique: Alfil is a chess engine I started working on a few years ago that was commercialized for the first time in 2000. I stopped developing it  in 2013, mainly due to lack of time I could devote to it. With an ELO of 2740, it was listed among the 30 best chess engines in the world, and competed in different online tournaments.

A few years ago I decided to make a new chess engine based on knowledge acquired during the creation of Alfil and the most advanced chess engines. This new engine was written in C# and follows the basic rules of chess.

With Chessaria AICE, I had to turn things around completely to be able to support the unique features that the game requires while keeping it compatible with predefined tournament protocols (UCI). Chessaria AICE differs completely, both from the C++ and the new C# version of Alfil. The large number of new rules introduced to support Chessaria’s gameplay makes it the most versatile and powerful chess engine I have created.

Without telling us any secrets: What techniques do you consider to be important to write a program with an estimated rating of 2800? (aggressive pruning techniques, bitboards, secret algorithms?)

Enrique: The first chess programs of the last century already used pruning algorithms such as alpha-beta or minimax to optimize search and in depth evaluation, without the need of analyzing all possibilities. Nowadays, there aren't any secret algorithms to write a chess engine as “almost” all the research has been  published, no matter how innovative they may be. Some of the most important ones that have contributed to the power of today’s most advanced engines are public.

Here are three technical examples:

- Bitboards and hash tables (thanks to Albert Lindsey Zobrist who invented the Zobrist Hashing) that allows thanks to the XOR operation that two 64-bit numbers can be operated to form another one and eliminated by recovering the previous one. It's great for storing 64-cell boards and being able to operate with them.

A XOR B = C
C XOR A = B

This means that we can move parts by operating the numbers, which is enormously fast for computers, and also storable together with their evaluation in the hash tables.

- Another great advance is multi-processors evaluation.

- End tables which are archives of evaluated positions. Usually end positions with only a few pieces, even though some programs use tables of up to 7 pieces. These are mostly useful in classic chess situation but tend to occupy a lot of space and are unadapted to the nature of Chessaria’s gameplay.

- The use of neural networks in programs like AlphaZero, for the evaluation of positions, is also currently being investigated. So far expert rules from GMs are used to evaluate a position. Values ​​were put to the pieces and the advantages in each position. Neural networks evaluate millions of positions to determine the rules by themselves, without the need of chess experts and capable of achieving surprising results!

What precious advice would you give someone interested in developing its own engine? Any mistakes to avoid?

Enrique: The development of a chess program is very complex and takes a tremendous amount of time to develop, but it’s exciting!

The most important thing is to take the time to learn before starting to write: How chess programs work, what parts they have in common, etc. It is also very important to use a common communications protocol as UCI to be able to compete against other engines and see the progress you make during the development of your engine.

I recommend to start by reading Tom Kerrigan's blog (http://www.tckerrigan.com/Chess/TSCP/) which contains many examples and explains step by step how to create a simple chess program.

Another interesting read is Chess Programming Wiki (https://chessprogramming.wikispaces.com/) that will help you apprehend from the simplest to the most complex elements of chess programming.

Also, remember to always structure your project in blocks, from the most general to the most specific elements.