Creating an AI for Risk board game

Introduction

I am currently working on a Javascript-based implementation of the classic boardgame Risk. It is written using ES2015 JS-syntax and I use Babel for transpiling. Currently I have a fully functional game engine so that two players can play on the same computer (hotseat) against each other. In the future I hope to implement online mutliplayer so that several human player can play against each other, each on their own computer, but this is not something that I am realistically going to finish anytime soon. In the meantime though I wanted to enhance the singleplayer aspect by adding an AI to play against. The goal was to make the AI at least fairly competent at the game so that it would provide a decent challenge to play against, playing against a bad AI that just do nonsensical moves at random would not be very fun.

You can find the project in question here.

The rules of Risk

Before I go about explaining my approach towards creating the AI I need to go over some of the rules of Risk (don’t worry, I won’t recite the entire rulebook, just the relevant parts). In classic Risk you play against each other on a game board of the world map. The goal is to conquer land, expand your territory, defeat your opponents and become as powerful as possible. In classic Risk you win by simply taking over every single territory on the map, but for my implementation of the game I have added the ability to choose the desired percentage of map control to achieve victory. This is because a game of Risk where you have to conquer 100% of the map can sometimes take an excruciatingly long time to finish, and it’s often quite clear anyway after a certain point who will most likely win.

The world map on the Risk game board is divided into regions (continents), each of which are then in turn broken down into territories. For instance in the game of Risk the region of Africa consists of 6 different territories. If a player holds every territory in a region then the player will recieve additional reinforcements each turn as a region bonus. Because of this, it is highly prioritized for players to try and secure entire regions and then try to hold them as they are very important for reinforcements.

1462528836773051681

There are three different phases to a players turn; deployment, attack and movement phase. During deployment you get additional troops to deploy. In the attack phase a player attacks and tries to take over other territories and in the movement phase the player may make one strategic movement of troops from one territory to another.

If you have won at least one battle during a turn you may draw a card from a pile. These cards can be collected and traded in as a combination of 3 cards during the deployment phase to gain additional reinforcements.

Theory

Contemplating important factors

For all three phases of a turn there are important factors that a player needs to consider. For instance in the reinforcement phase you have to think one step ahead and try to deploy troops in good positions from where you can then attack in the attack phase, but also you need to identify territories that are especially important to protect and therefore reinforce them if they are threatened (for instance if an opponent has lots of troops in an adjacent territory). Let’s say a player controls the entire region of South america. There are only two territories in South america that borders to other regions, Venezuela (that borders to central america) and Brazil (that borders with North africa). Because of this these two territories are especially important to reinforce if they are adjacent to enemy territory, since they are the entry points into South america. Placing lots of troops in Argentina though would not make sense because they can’t protect the region from there. These are all things that a player, and therefore also my AI, needs to take into account when planning deployment.

Capture

As for attacking this goes pretty much hand in hand with the deployment phase, because when a player deploys troops to a specific territory he usually have an attack target in mind to attack from there. There are also many things to take into account when attacking. For instance you always ideally want a numerical advantage of troops, especially since in Risk the defender has an advantage. Also a player needs to take into account the overall strength of the player to attack. Let’s say you’re playing a 3 player game, both player 1 and 2 are very strong with large territories but player 3 is very small and weak. In this scenario it might be more important for player 1 to try to prepare against and attack player 2, because he/she is the largest threat, player 3 however does not constitute as large of a threat and therefore does not need to be prioritized as much as a target. However let’s say player 3 is so weak that he/she is on the verge of being eliminated, let’s say player 3 has just one territory left that is badly defended, then it’s probably worth it for both player 1 and 2 to try and eliminate player 3 because that would mean one less enemy and also when you eliminate an opponent in Risk you may gain all of his or her cards. All of these are factors that also need to be accounted for when deciding where to attack and where to deploy.

Third and finally is the movement phase. Here it also very important to make a wise decision. You only get to make one movement, you can’t do everything that you might want to do, so you have to try and make the most optimal movement. Just like with deployment, it’s important to think about which territories are especially important to protect and that are under threat of being attacked, for instance a territory that acts as a choke point frontline.

Basically I tried to analyze whatever factors I try to take into account when playing Risk and I wrote them all down, for these are also the factors I’d like for my AI to contemplate.

Initial approach

Importance points

As I started working on the AI I had the idea, inspired by “minxmax” decision making, that for each turn phase I should determine every possible move and then try to find the best one(s). For instance for the deployment phase I would for each possible option (territory to deploy to) determine the value/importance of that option. I would then take into account all the relevant factors for each option by basically validating a series of different conditions.

  • Is the territory adjacent to a territory belonging to a player that can be easily eliminted?
  • Is the territory adjacent to a player that can be considered a big threat?
  • Is the territory a part of a region that I currently control that is therefore important to me?
  • Is the territory a part of a region that I am close to capturing completely?
  • If yes to previous statement, then also, how good is this region (considering they all have different region bonuses dependenat on how hard or easy they are to capturing)?
  • Is the territory adjacent to a viable target that can be taken in order to break up another players controlled region, thus denying him/her a reinforcement bonus?

After answering all of these conditions for every possible move I am then able to use this to calculate a value used to symbolize the importance of the move. By making this into a number I can easily then sort the list and then pick the move or moves with highest importance ratings. Codewise it would look a bit like this (simplified):

possibleTerritoriesToAttack.forEach(territory => {
    territory.importancePoints = 0;
    territory.importancePoints += territory.opportunityToEliminatePlayer ? 5 : 0;
    territory.importancePoints += territory.belongsToBigThreat ? 3 : 0;
    territory.importancePoints += territory.mostTroopsInThisRegion ? 3 : 0;
    territory.importancePoints += territory.closeToCaptureRegion ? 6 : 0;
    territory.importancePoints += territory.canBeAttackedToBreakUpRegion ? 5 : 0;
    territory.importancePoints += territory.lastTerritoryLeftInRegion ? 3 : 0
});

(There are actually more conditions in the actual game but for this article I’m choosing to cover these ones)

By the snippet you can see that for different conditions I add different “importancePoints” to the total for each move. I didn’t include the code where I determine all of these different factors for each condition as I figured there would be too much, but you can analye the entire code by reading this file.

After having finished calculating the importancePoints for each possible move I can simply sort my list by importancePoints and then the first move in the list should be the best possible choice, assuming my current model for determining that is working.

Threat

As mentioned above, some of the conditions for determining importancePoints also take into account the “threat” of the player owning the viable attack target. To determine such a thing I also needed some sort of system of calculating overall threat of another player, and I ended up using a very similar approach to how how I calculate importancePoints. Here is the function:

calculateStandingsWithThreatPoints() {
    const currentStandings = getCurrentOwnershipStandings(this.gameEngine.map, this.gameEngine.players);
    currentStandings.forEach(standing => {
        standing.threatPoints = 0;
        standing.threatPoints += standing.totalTroops;
        standing.threatPoints += (Math.floor(standing.totalTerritories / 2));
        standing.threatPoints += (standing.cardsOwned * 2);

        standing.regionsOwned.forEach(region => {
            standing.threatPoints += (Math.floor(this.gameEngine.map.regions.get(region).bonusTroops * 1.5));
        });
    });
    currentStandings.sort((a, b) => a.threatPoints - b.threatPoints);
    return currentStandings;
}

Basically the threat of a player is determined by:

  • How many total troops the player has across all territories
  • The amount of territores controlled by the player
  • How many cards the player currently has on hand
  • How many regions the player controls and how big reinforcements bonuses they
    each give

This way we can, just like with importancePoints, calculating a value called “threatPoints” for each player which can then be used when determining importancePoints. As you can see in the code snippet there are also modifiers to some of these threatPoints, for instance:

standing.threatPoints += (Math.floor(standing.totalTerritories / 2));
standing.threatPoints += (standing.cardsOwned * 2);
standing.regionsOwned.forEach(region => {
    standing.threatPoints += (Math.floor(this.gameEngine.map.regions.get(region).bonusTroops * 1.5));
});

This way the amount of threatPoints for a given condition can be modified and adjusted. In this example for instance each card owned equals 2 threat points, whereas each territory owned is just worth 0.5 threat points. That is because holding many territories is not really in and of itself a very significant thing, what’s important in Risk is to control entire regions (which explains the 1.5 modifier for each region reinforcement bonus). Similarly having many cards on hand is also very powerful as these can be turned in for a lot of extra troops, which is why they’re considered valuable. By having these modifiers I can then later readjust and tweak the system in order to optimize the calulation. More on this later.

Movement

For movement I wen’t with pretty much the exact same approach as with reinforcement/attack phase. Basically just devise a strategy to calculate a value for each possible option, determine which option is the best by sorting by this value and then choosing the top ranked option as the move to use. For movement I had some different conditions though to consider when calculating my importance value:

  • Is the territory (to move to) a frontline that borders with enemies?
  • If so, do my enemies have many troops adjacent to the territory which would constitute a big threat of being invaded?
  • If the territory borders with an enemey, how strong is that enemy compared to me? (Based on threat points once again)
  • Is the territory an important defensive strategic position for holding a currently controlled region?

AI testing

Problem

One problem so far is that my systems in place used for determining best moves are based upon adding values together based on different conditions, but it’s pretty hard knowing how many points a certain condition should be valued as. For instance in the example snippet displayed above regarding valuePoints possible attack targets I add 3 points if the condition “belongsToBigThreat” is met and 6 points if the condition “closeToCaptureRegion” is met, but how can I know for sure that these numbers are optimal for each given condition? The answer is that I don’t, so far I have only declared these values myself by pretty much shooting from the hip, guesstimating what I think sounds reasonable, but I need to do something about this.

Solution

I figured I could optimize my declared values used for determining value of possible choices by conducting AI tests. Basically what I do is that I let an AI player play against another AI player. Player 1 uses the default values I already have declared myself whereas player 2 gets a randomized confiugration of values. They play each other until one of them wins. The winner gets to keep it’s configuration of values and the loser gets a new randomized configuration. Then they simply keep this up and play game after game against each other, all the while changing the configuration of used values so that the ones that actually seem to work and produce good results are the ones that are passed on to the next iteration. It becomes sort of an evolution. I created a game mode specifically for this task where the speed of the AI is really fast and where the game automatically resets when one of them wins and keep tracks of the games played. I decided to set something like 80% map control as win condition and then I just let my two AI foes duke it out against each other. After just about an hour or so they had already played over 3000 games against each other, so I took the last successful winning configuration and started using that as the default for my AI player.

Here’s a video of how the automated speed testing looked.

Result

I’m quite happy with the result. Even though the AI is far from perfect, considering this is the first version of the AI I think it works very well. The moves that the AI does seem logical and makes sense, at least almost every time.

Below is a video of 6 AI opponents playing against each other in a free for all. I have sped up the video quite since it was originally 8 minutes long.

Future improvements

Like I said, I consider this a first iteration of more to come regarding my Risk AI, but for now this will do just fine. I have thought about improvements I could implement to improve the AI and here are some of the things I’ve gathered:

  • MORE AI TESTING I should do even more AI testing, letting AI play against AI and let it “learn” along the way what works best. I could also make the process smarter, instead of simply generating a new configuration at random at every iteration it could somehow try to remember what has worked in the past and build on that incrementally. I haven’t come far with analyzing how this is supposed to be done though, but that’s a future problem.
  • AI FOR TEAM GAMES There are different things you need to consider when playing against many opponents as opposed to playing just 1vs1. Therefore I should also conduct AI testing where several AI players face off in a free for all. I could also add specific conditions that makes sense in these scenarios.
  • THINK AHEAD One big difference between my AI and a human player is that human player usually tries to think several steps ahead whereas the AI don’t do that. The AI assesses the best possible options move by move, it doesn’t analyze and come up with long term goals like a human would. Despite this it kind of works out quite well anyway because of the current logic I have in place. For instance the AI is configured to try to prioritize capturing regions, because of how valuable these are. In the sped up gameplay video you can also see that each AI player is actively working towards that and are trying to solidify control of regions, instead of just attacking randomly all over the map.
  • MORE AI VARIETY In the final version I would like to have more than one type of AI. There could for instance different difficulty levels for each AI. One other thing is to have AI:s that behave a bit differently and adopt different strategies. For instance one could be more defensive and play a turtle style, whereas another plays very aggressively.
  • MORE SCRIPTED DECISIONS I need to add some “scripted decisions” which basically mean that for some certain conditions my ordinary systems of value points are overruled and the AI instead follows a predetermined behaviour. An example of this would be if the AI is just one territory away from winning the game. In such a case most human players would try their best to conquer that last territory in order to win the game, even if it might mean taking a fight where the odds are not entirely in your favour, however my AI as it is right is programmed to not ever try to make risky decisions. This is why I need to identify possible scenarios where such scripted decisions are necessary.

 

Promise chains with delays and pauses

Introduction

As a part of my recent hobby development of a Javascript-based version of the classic boardgame “Risk” I have played around quite a bit with promises and I wanted to share some stuff that I found useful.

First of all, I am writing code in the recent ES2015 syntax, so the Promises am I using are the newly added native Promises, no framework needed. I am then using Babel to transpile my code thus making it backwards compatible with old browser.

Full demo can be found at the bottom of this article.

Delays

I wished to create an AI opponent to play against for my Risk-game. When it’s the AI players turn it should execute a sequence of actions such as turn in cards, reinforce territories, attack territories and lastly ordering a troop movement (those of you who have played Risk are surely familiar with these turn phases). I could just let the AI execute all of these commands one after another but it would go by so fast that a human player would not be able to see what’s happening. Because of this I want some pauses between each action.

Javascript is of course single-threaded and do not have any equivalents of Thread.sleep (like in Java), but it does have some nifty timing- and interval-functions like setTimeout that executes a function after a delay.

To perform a chain of commands using setTimeout it would look something like this:

const turnInCards = () => { console.log('1') };
const deployment = () => { console.log('2') };
const attack = () => { console.log('3') };
const movement = () => { console.log('4') };

setTimeout(() => {
    turnInCards();
    setTimeout(() => {
        deployment();
        setTimeout(() => {
            attack();
            setTimeout(() => {
                movement();
            }, 1000);
        }, 1000);
    }, 1000);
}, 1000);

If you run this code in your browsers console it would output 1, 2, 3 and 4 one after another with 1 second delay between each.

Of course this looks rather horrendous, and the longer the chain would become the crappier it would look, and also becomes harder to navigate and manage the code. In Javascript there already exists a nice solution to getting out of many of these callback hells and it is of course use of Promises. By making all of our commands into functions that returns promises we can chain them together and force to execute one after another. To also have a delay between each command we also need to use some kind of delay function. I wrote one that looks
like this:

const delay = ms => new Promise((resolve, reject) => {
    setTimeout(resolve, ms);
});

Delay returns a Promise that uses the setTimeout-function by resolving itself after a given amount of time. Now we can use this delay function in a chain of promises, like this:

const turnInCards = () => { console.log('1'); Promise.resolve(); };
const deployment = () => { console.log('2'); Promise.resolve(); };
const attack = () => { console.log('3'); Promise.resolve(); };
const movement = () => { console.log('4'); Promise.resolve(); };

delay(1000)
.then(turnInCards)
.then(() => delay(1000))
.then(deployment)
.then(() => delay(1000))
.then(attack)
.then(() => delay(1000))
.then(movement);

Try to run this piece of code in your terminal (don’t forget the declared delay function) and it will produce the exact same outcome as the previous snippet, but this one looks so much cleaner because don’t get a nested tree of callbacks. Everything is on the same line. We could also refactor the code to look like this:

const turnInCards = () => { console.log('1'); return delay(1000); };
const deployment = () => { console.log('2'); return delay(1000); };
const attack = () => { console.log('3'); return delay(1000); };
const movement = () => { console.log('4'); return delay(1000); };

delay(1000)
.then(turnInCards)
.then(deployment)
.then(attack)
.then(movement);

We could just make the command functions return the delay function instead, which in turn returns a Promise, so this way the Proimse-chain becomes even cleaner and easier to follow.

Pausing

Next I wanted to be able to pause the game. If the AI opponent is in the middle of his turn I want to be able to press a pause button at which point the chain of commands pauses for as long as I like, until I unpause. For this I created a recursive promise-function called pauser that looks like this:

pauser() {
    if (!isPaused) {
        return;
    }
    return delay(500).then(() => pauser());
}

This function utilizes the delay function I already previously written. When called it checks if the game is not paused, in which case it just returns. If the game is paused however it will delay for 500 ms and then call itself, and it will continue to call itself (since it’s recursive) until the game unpauses. Now I need to add the pauser function between each command in the chain.

const turnInCards = () => { console.log('1'); return delay(1000); };
const deployment = () => { console.log('2'); return delay(1000); };
const attack = () => { console.log('3'); return delay(1000); };
const movement = () => { console.log('4'); return delay(1000); };

delay(1000)
.then(() => pauser())
.then(turnInCards)
.then(() => pauser())
.then(deployment)
.then(() => pauser())
.then(attack)
.then(() => pauser())
.then(movement)
.then(() => pauser());

In this example if you follow the chain delay is always called before pauser, so to clean up the chain a bit I could refactor so that these two are executed in the same function that utilizes both pauser and delay. It could look something like this.

const delayAndPause = () => delay(1000).then(() => pauser());

const turnInCards = () => { console.log('1'); return delayAndPause(); };
const deployment = () => { console.log('2'); return delayAndPause(); };
const attack = () => { console.log('3'); return delayAndPause(); };
const movement = () => { console.log('4'); return delayAndPause(); };

delayAndPause()
.then(turnInCards)
.then(deployment)
.then(attack)
.then(movement);

Now if the window variable isPaused is somewhere along this chain changed to true, the chain will pause and wait for it to become false again. I created a JS-Fiddle to demonstrate here:
https://jsfiddle.net/ToWelie89/dwnb3yh1/

I hope you found this post useful and informative 🙂 Feedback is always appreciated.

Peace out.