Skip to content

Playing with AI

Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn

By 2017, AI had advanced far enough for AlphaGo, a specialised AI that can play the highly complex board game Go, to beat the major Go players in the world and be awarded professional 9-dan by the Chinese Weiqi Association. Go, however, is a fully deterministic game like Chess, with no random elements. Probabilistic games like Pandemic, on the other hand, are even trickier for AI to play efficiently, as the randomness of dice rolls or shuffled cards makes it much harder for computers to crack them. This problem inspired me (Konstantinos Sfikas) to attempt to create an AI that can play the Pandemic board game.

In the summer of 2018, I started working on this problem as part of my Thesis for the MSc in Digital Games (Institute of Digital Games, University of Malta), under the supervision of Dr Antonios Liapis.

Konstantinos Sfikas, student

At the core of our methodology lies Rolling Horizon Evolution (RHE), a planning algorithm that makes decisions by optimising action sequences through artificial evolution (introduced by University of Essex researchers in 2013). In order to make a single decision, RHE initially composes a population of random action sequences and evaluates them by simulating their potential result. Then an iterative process of optimisation takes place: the action sequences are randomly mutated, generating a set of offspring. The offspring will either replace their parents or be discarded, based on a quality comparison. While this process repeats, the overall quality of the population tends to increase. After a predefined number of iterations, the agent simply selects the first action of the best-found sequence and applies it to the actual game. 

Based on RHE, we designed the Policy-Based Rolling Horizon Evolution Agent (PB-RHEA), which operates on a higher level of abstraction, using a set of “policies” (artificial behaviours) as an indirect encoding of action sequences. When composing or mutating sequences, PB-RHEA does not consider the full amount of potential single actions (as RHE does), but rather selects among a much smaller set of possible behaviours that translate into specific actions and approximates their probable outcome through repeated randomised simulations. Through this technique, the agent’s operation was greatly enhanced in terms of computational efficiency and overall performance.

During my thesis and the two publications that followed (both co-authored with my supervisor Dr Antonios Liapis), we performed a large number of computational experiments, analysing the agent’s behaviour and optimising its performance. One of the most challenging aspects of our research was to design a set of heuristics that approximate the quality of any given game-state, thus allowing the agent to evaluate the outcome of an action-sequence. Another challenge was to define the set of policies that the agent would use as building blocks in such a way that they are both efficient and expressive. Finally, fine-tuning the algorithm’s parameters through trial and error was another critical aspect of the agent’s degree of success. The results overall showcase that our proposed methodology exhibits a good performance against a hard problem and leaves clear avenues for further improvement.

From an academic perspective, the main contribution of our research is that it clearly expanded the knowledge on planning algorithms like RHE and, more precisely, their applicability on complex problems like Pandemic. Agents like the PB-RHEA can be used to play alongside human players in the digital versions of board games or even be used in the context of automated play-testing during the development phase of board games. Although gamers have been playing alongside AI for a long time, will game developers also adopt AI as a partner when designing their games?

This research was carried out as part of an MSc in Digital Games at the Institute of Digital Games, University of Malta, under the supervision of Dr Antonios Liapis.

Further Reading

Sfikas, K., Liapis, A., & International Conference on the Foundations of Digital Games. (2020). Collaborative Agent Gameplay in the Pandemic Board Game.

Sfikas, K., & Liapis, A. (2021). Playing against the Board : Rolling Horizon Evolutionary Algorithms against Pandemic.

More to Explore

How Smart Insoles Can Save Feet of People Living with Diabetes

In Malta, around 10% of the local population is affected by diabetes. This is especially alarming considering that diabetes can affect the blood and nervous system and eventually even lead to foot amputations. Researchers from the University of Malta (UM) and Mater Dei Hospital are trying to address this problem in their project Sit_Diab: Smart Insole Technology for the Diabetic Foot. They developed a novel method of detecting foot complications early enough to take action in time to help save limbs.

Ignite’s ‘Ugo Sultan’

Taking a look back at the events that occurred on our islands more than a hundred years ago, ‘Ugo Sultan’ will transport you to a 1920s Malta full of notable people that shaped the history of our country. However, it wouldn’t be an Ignite production if it didn’t have its own unique twist. Though based on real events and people, ‘Ugo Sultan’ is a satirical, fictional comedy that is sure to bring a smile on our audience’s faces.

Why don’t Ants Take Fall Damage?

Do you ever recall those moments in nature, where tiny insects seem to mistake you for a tree? Not only do they walk vertically upwards with incredible grip, but as they are brushed off and fall to the ground, they just nonchalantly walk away. No big deal. Except, when put into perspective, an ant falling from your arm is as though a person fell off a rooftop and walked away untouched. Why do small insects, and ants specifically, never seem to take any fall damage?

Comments are closed for this article!