The goal of this project is more in the realization of a generic platform for board games than in the implementation or the study of the best algorithm existing in this field. It is therefore important to clearly define the constraints that we want to fulfil in order to sketch the solution accordingly.

Of course, the performance of AIs is crucial as it is not interesting to face an opponent who is too weak. But there is no need here to match the stratospheric level of the best dedicated programs (for example as for go or chess). It would indeed be difficult to rise to the same level of committed solutions because of the significant computing power required for training their underlying neural networks.

An engine to play them all

What I wanted above all from the start was to have a solution on which to be able to implement all kinds of board games, knowing that they may require to incorporate many mechanisms such as chance, hidden information, various turn orders, actions where players make simultaneous choices, etc. It was therefore necessary to embrace all the mechanisms common to board games with the sole restriction of being limited to turn-based games.

Even though we won’t tackle the subject of AI right away, it was clear from the start that we would have to cope with neural networks training at some point, for algorithms that rely on this sort of means. This means being able to easily collect learning data from game episodes where the machine is fighting itself.

Finally, it was important for me to have the possibility that the games could be played in a web browser through a nice graphical interface, but without the code running entirely on the client side.

These constraints are somewhat different from the numerous projects or tutorials that can be found in the field of board games. The OpenSpiel solution developed by DeepMind, for example, is heavily research driven. It aims to implement as many algorithms and tools as possible to cover the state of the art, but requires knowing what to use and how, and does not offer any graphical interface. As for the many tutorials that can be found on the web, they usually only focus on a single game or on a single type of algorithm, leaving aside performance or genericity.

Personally, I rather oriented towards a solution built on three components:

• A library responsible for implementing the general logic, the AI, as well as the fine mechanics of each of the board games;
• A server encapsulating the library and enabling it to run on a remote machine through a dedicated API;
• The Web client that takes care of games rendering in a browser.

This allows a lot of flexibility in the final usage, as shown in the deployment figure below.

The right part contains the aforementioned library libBuddyCore, as well as a BuddyCore Server application exposing its interface through a Websockets based communication means. The WebSockets protocol appeared to be the solution of choice since it offers all the flexibility of two-way TCP/IP communication, but is also compatible with all Web browsers. Bidirectionality is important so that the server can send all notifications that occur during a game (selected moves, stats, requests, etc.) on its own, thus avoiding the need for unwanted polling. Furthermore, the message content is built in JSON, because this format has the great advantage of being readable and thus considerably facilitates development. There is no need to resort to a more compact encoding here given the low rate of messages exchanged during a game.

The left part illustrates two ways to interface with the server. The first one is a Web client taking care of the communication with the server, of the general game management mechanisms, as well as the graphic rendering specific to each game. For information, the rendering is carried out by drawing in an HTML5 canvas and I was impressed by the ease, quality and fluidity with which it is possible to achieve this. Having never programmed in JavaScript before and being more used to native graphics applications, it was honestly a pleasant surprise. Finally, it is naturally conceivable to interface with the server by means of any other language, as illustrated with the Python part in the lower block.

If this separation between client and server is very interesting for real deployment of the application, it also complicates the operations. It is, however, possible to make much more convenient use of the library by interfacing directly with it, as shown in the image below. This is actually how the library is used to perform tests or to collect large quantities of data for training neural networks.

For each task the right language

Once the main lines of the architecture have been laid down comes the question of the languages to be used to develop the different components. The graphical part running in a browser is then the easiest to decide, because there is little or no choice apart from JavaScript. In a second hand, neural networks training requires to go through libraries such as TensorFlow or PyTorch, which are mainly used in Python. However, training AI algorithms is a task that only takes place on the fringes and has no impact on the final exploitation afterwards.

The most important point then concerns the choice of language for the libBuddyCore library. This one aims to efficiently implement all kinds of AI algorithms that certainly have to be executed as quickly as possible while offering very efficient memory management. The compelling reason for us to focus on efficiency is that these algorithms are inherently very expensive in computing time and memory. Thinking about the next move to play comes down, in one way or another, to evaluating as many of them as possible in order to select the most promising one. An algorithm running twice as fast can therefore explore twice as much within the same period of time. It is also an algorithm that will be able to collect training data twice faster. Likewise, an algorithm requiring half the memory will be able to be parallelized all the more easily to gain further execution speed.

Having said that, it is obvious that to go towards an interpreted language such as Python, although very popular in the scientific field, would be like shooting yourself in the foot. Its inability to run parallelized code, its crippling slowness as soon as you write the slightest loop (about 2 orders of magnitude compared to native code) and its lack of control over memory management really make it the one of the worst candidates you can think of. Then, if an intermediate language like Java can do the trick, it is much more interesting to turn to a compiled language to take full advantage of the capabilities of the host machine. While several choices are certainly valid, I turned to C++ simply because of my decades of experience in this language.

It is then at this stage that Python we shut the door on can get in by the back door. If we take the trouble to encapsulate the native library in a Python wrapper, it can then be used with all the ease specific to this language, while maintaining unchanged performance. This is a winning combo that can be found in many projects, TensorFlow being a perfect representative.

The bowels of the beast

The most complex part in this project certainly lies in the famous libBuddyCore library, since it has the honour of integrating the different AIs and of offering an abstract interface creation of virtually any board game. As we’ll be discussing AI in the next chapters, let’s focus here on the generic implementation of a board game engine.

Games abstraction

Le diagramme de classes de la partie concernant l’implémentation des jeux est donné dans l’image ce-dessous:

In order to expose a simple interface regarding the available games, the library manages all of them through the GameBook Singleton. The latter has a list of games that let them be known by their abstract interface Game, as is the case of the Connect4 class, for example. The main function of the Game class is the CreateGameInitState method which, as its name suggests, instantiates the initial state of the game it represents.

Any game state, that is to say all the information that is required to figure out the configuration of all its gameplay elements at a given time, is exposed through the abstract class IGameState. The latter has a set of generic functions to manipulate it in order to update the course of the game. Since the possible actions depend entirely on the game we are talking about, it is mandatory to abstract them in the same way. As a result, an action will always be represented by an integer value, the meaning of which is left to the total discretion of the game. For example, the actions of the Connect 4 game can be represented by the numbers from 1 to 7 to designate each of the columns in which a stone can be dropped. But any other numbering would do the job.

The GetLegalAction function therefore systematically returns a list of abstruse numbers that can be dependent on the state of the game itself. The ApplyAction function then makes it possible to change the state of the game according to the action number given in argument, but once again this aspect is left to the discretion of the game itself. It follows that the information that an AI can collect on the evolution of a game will be all as abstract and boil down to

• a list of available action numbers;
• the next player number;
• an optional running score;
• a flag telling if the game is over and what player won.

It is thus obvious that this game engine is not designed to implement specific AI for specific games, but rather for general AIs which can play a whole class of games sharing the same very high-level properties.

Orchestration of a game

The diagram below shows the main classes involved in the unfolding of a game episode between multiple agents, again without knowing the details of the agents or of the games. The point of contact with the outside of the library is made up of the Contest class which is responsible for bringing together one or more agents around the table. Those must all inherit from the abstract Agent class and there is also a special agent to interface with the outside of the library, in order to allow a human player or external AI to take part in the game.

The exact progress of a game is left to the care of the Scheduler class whose role is:

• to inquire about the order in which each agent should play,
• to collect the list of actions that are accessible to each of them,
• to communicate this list to them,
• to take note in return of the selected action,
• to transmit this action to the game in order to make it evolve accordingly,
• to notify agents of the new state of the game,
• to report all these steps to keep the user of the library informed of the game episode progress.

These different steps are illustrated in more detail on the sequence diagram below. In order to accommodate all kinds of patterns that may arise in a board game, an episode is sliced into a succession of Rounds, themselves organized in a sequence of Turns.

The idea of a Round is very close to what is traditionally found in a board game, that is to say that it gives the opportunity to each player to play once. This is not mandatory, however, as some players may well have to skip their turn or play multiple times. A Turn, on the other hand, allows one or more players to play simultaneously. Concretely, no agent is informed of the selected actions or of the resulting game state until this phase is not completely resolved. If no concomitant choice is required, a Turn will only involve one agent.

The content of a Round is by no means fixed, because it is the game itself that decides its content before it begins. It can therefore be modified as needed according to the circumstances and thus allows complex game patterns. In other words, an IGameState instance can decide on the exact content of a Round in terms of playing order, while the Scheduler class orchestrates the game correspondingly to pass all the information between the stakeholders.

Conclusion

This chapter was an opportunity to define the high-level objectives of this project and to review the main design choices that were implemented to achieve them. Next chapter will get to the core of the matter by starting to tackle an issue that has been avoided so far: the concrete realization of an AI.