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.
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.
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.
Martin Sonesson 