AI in Digital Board Games

Digital board game AI is having a bit of a moment. I don't know if patient zero was Raiders of the North Sea, but that's certainly when I started seeing larger discussions around the topic. In case you missed it, Raiders was released as a fantastic app loaded with features and looking amazing, but the AI at time of the initial release was really bad. Bad enough to relegate an otherwise amazing app to online play only (it has improved since). The board game geek announcement thread took off in an AI deep dive with multiple developers chiming in. The discussions are hardly a blip on the board game radar, but are practically an earthquake compared to the usual discussions surrounding digital ports.

Is AI even important in digital board games? The most commonly asked questions about board game apps I see all revolve around multiplayer. Be it async, cross-platform, real-time, or pass-and-play, players always seem to be focused on a specific multiplayer mode or feature. Developers, however, say the usage stats in their apps tell a different story. Theresa Duringer from Temple Gates Games notes “Based on our metrics, most boardgame apps are played in solo mode against the AI.” This is despite the fact that their games, Race for the Galaxy and Shards of Infinity, feature some of the best implemented online experiences in existence.

To put some numbers behind that claim, John Arnold, lead developer at Handelabra Games, provides some interesting stats. “Overall across platforms, 92% of games are played locally, and 8% are played online.” Offline, in this case, does include local pass-and-play, but 92% is a staggering number.

We have established that AI is a very important feature of digital board games, so how do developers go about building up opponents worthy of challenging even the best humans?

One place to start this discussion is Race for the Galaxy, specifically with Keldon Jones’s online AI for Race for the Galaxy. Sure, digital board games existed before this, but not many. To summarize Keldon’s story; he created a very strong AI for this game back in 2009, iterated on it for the next five or so years, and has released the source code for a somewhat crude digital version of the game. Jones has publicly discussed how he does not enjoy working on the UI side of things and actually worked on a failed initial attempt at bringing the game to the digital world.

Enter Temple Gates Games. Duringer says “with Race for the Galaxy, Keldon had already done pretty much everything prior to us even taking on the project. He pretty much dropped off the code - which was already robust from years of development and fixes. He also answered some questions for us about how it worked.” The successful partnership between Temple Gates and Keldon continued with work on a Roll for the Galaxy port (still in the works, by the way). Duringer and her team were able to use that work on the Roll AI, which started from scratch after Race, as the starting point for their work on Shards of Infinity. Work on the Shards AI continues now, even months after the game’s release. “The nice thing about working on boardgames with lots of expansions is that we can patch in these improvements as we learn,” says Duringer.

Tysen Streib is an independent board game AI developer who has been a contractor for Digidiced for the past two years and has probably developed AI for some games you really like. His credits include Indian Summer, Patchwork, Cottage Garden, Isle of Skye, Stockpile, and Castles of Burgundy. Streib is currently working on the AI for Digidiced’s highly anticipated Viticulture port. A self-described lifelong “quantitative geek”, Tysen got his start in the online poker boom of the mid 2000’s, eventually writing advanced AI and co-writing some very popular poker strategy books. He turned his attention to digital board games as a personal side project, which eventually led to his work with Digidiced. It’s hard to qualify these things, but he may be the single person with the widest breadth of digital board game AI experience in the world.

Streib has had many great successes in his AI development, but also some noteworthy disappointments. The first project he took on with Digidiced was an attempt to create a better Terra Mystica AI. This process was detailed at length in a great Board Game Geek piece, you can read it in full here. They knew going in it was going to be a difficult challenge. Stieb comments, “we decided to gamble and see if we could make a deep neural network version work. We were ultimately unsuccessful. Terra Mystica is a tremendously complicated game and the amount of computing power needed to train an AI for it was just too expensive for a small company.”

This gets to the crux of the issue that comes in creating good board game AI; time and money. As the BGG article dives into, the machines training the famous AIs you might have heard about in the news for games like chess and Go are massive and something that digital board game companies simply can’t afford. Streib comments, “given enough time and money, you could make a solid AI for any game, but it may have such large memory requirements that it would not be able to run on a phone.”

Therein lies another major problem; whatever AI is developed must be fast and slim enough to be packaged up with the rest of the app to fit into phones of all shapes and sizes. On the speed front, it is imperative that these games work on a huge range of phones (especially on Android). The oldest OS versions will get cut off eventually, but at the time of this writing about 15% of all Android devices in the wild were running an Android 5.x version, dubbed Lollipop, which debuted in 2014. Additionally, digital board games often require a hefty download size between the numerous art and sound assets, there’s only so much room for AI to fit in. Developers quickly start to feel the squeeze from all sides.

Beyond resources and computing power, are there aspects of certain board games which make them more or less learnable by AI? “The easiest games to make a super-strong AI for are 2-player games with no randomness and no hidden information. You also want games where each player doesn’t have too many choices of moves to make and where individual turns don’t have multiple steps” says Streib. Adding, “the most difficult games are usually those where a human player can make a long-term plan based on the situation. Things like ‘if I do move X now then I’ll be able to do Y later’ can be very difficult for AI’s to figure out if ‘later’ is beyond its search horizon. Some of Digidiced’s games weren’t able to have killer AIs because of this.”

Going deeper, Streib points out that games where strategy is predicated on attempting to surmise what actions your opponent might take can be especially tricky. The search functions used in training AIs might not be able to come up with a meaningful prediction if there are a large number of potential choices an opponent could make. As a contrast, Streib brings up Through the Ages which seemingly has a large number of choices and you need to be aware of what your opponents are doing.  He suspects that while the AI is impressive, it might not have been as difficult to create as it might appear at first glance. “You have a lot of actions you can do on your turn and there are important card-specific synergies, but not that many of them. You care about a few key statistics on your opponents – how much culture they’re generating, what their military strength is, etc.” Streib continues, “but it’s not too important for you to predict exactly what moves each of your opponents is going to do. You care about the likelihood that they’ll attack you and you don’t want to leave valuable cards for them to take, but usually you don’t need to plan out their specific moves.”

This is starting to hit at the fine, sometimes blurry line that can separate games which are ripe for strong AI and those which aren’t. Speak to experts on the subject and terms like “search horizon”, “branching”, “episode”, and “temporal based neural network” will start popping up. Generalizing, the AI behind the scenes rely on predicting as many of the possible outcomes of each turn (both the AI’s own and it’s AI and/or human opponents’) as best as possible. With each new option available to a player on their turn, that’s one more branch on the search tree the AI must consider. Each branch has its own set of sub-branches, and so on. It is easy to imagine how things could get out of hand quickly in this space, especially with the desire to look multiple turns into the future when predicting.

Additionally, creating any machine learning algorithm almost always includes a bit of art, not just science. In Roll for the Galaxy, there are up to ten six-sided dice being rolled, that leads to over 60 million possible combinations of outcomes. Do you think that a 2015 Samsung is going to have the horsepower to run through 60 million possible dice outcomes on a turn? It’s not. Instead, you need to decide how many of the most likely rolls you actually need to consider to produce a decent AI, and this is where the art comes in, at least is has up for the past few years. Theresa Duringer notes that they only modeled the 100 most likely outcomes for any set of dice rolls, however coming up with that number isn’t an arbitrary task. “This relies on Keldon’s probability math skills to identify which parts of the possibility tree to actually explore,” she continues, “what if we could use a neural network to automagically prune our simulation space? It’s not actually clear that we’ll get an improvement, because Keldon’s benefits from 10k years of human math advancements, where we would be expecting the [neural network] to independently learn dice probability math from scratch on its own. But it is an interesting option and it’s something that AlphaGo Zero has proven out to some degree!” Is this the future of AI in digital board games? Learning how to take the expert humans out of the loop? It’s an interesting proposition, to be sure.

Emiliano Conde is the founder and CEO of Decisive AI. They released Tournament of Dragons earlier this year which was primarily a showcase for their For Sale AI. “AI seems to be often a low priority. Many games are pretty good: graphics, UI, the adaptation to the mobile device are often quite well done. But the AI is not at the same level, so a board game is shifted slightly to the video game genre with quests and campaigns to keep the player engaged.” Conde adds, “I like playing board games, and a good digital version should come with artificial players that allow me to play the way the board game was meant to be played.”

Conde’s goal for Decisive is to help digital board game companies develop better AI, he notes, “We want to show this to companies that develop digital board games and help them with not just the AI, but the whole platform of artificial players that includes artificial players of all skills, a global leaderboard and smart matchmaking. The result is a board gaming experience that remains true to the board game and fun for players of all levels.”

This last part really starts to pull on an interesting thread. In Tournament of Dragons, the online community is populated not only by other human players, but with a slew of AI players. They seeded the online game with 500 AI of different levels from beginner to expert. Human players will get matched against other humans (when available) and/or AI players within their small skill range. There are multiple benefits here. First, players get matched almost instantly every time they want to play, convenience can be vital in any digital medium. Second, it ensures that human players will get a fun, appropriate challenge every time they fire up the game. If you keep winning? You’ll rank up and find more difficult AIs waiting. Condeo thinks this is the future of AI in digital board games.

So where does AI in digital board games stand today? As we’ve touched on throughout, it takes experience in machine learning, a massive amount of computing power, and a bit of magic (or just intimate subject matter knowledge). We’re at the point where quality AIs can be fairly easily trained in certain types of games, at least by experts. These experts continue to iterate and improve on their methods, making their next game a touch easier to develop. This, obviously, doesn’t always lead to great AI in released products. Some companies don’t have the time or resources to pull off the extensive development required, some choose to spend the resources elsewhere. Some games simply don’t lend themselves very well to being able to train a good AI within the requirements of fitting on a phone and running fast enough to result in a playable game.

What’s the takeaway from all of this? I’d like to say that I will be more appreciative of good AI, but I also know that calling balls and strikes correctly 98% of the time is a really tough job, but I still yell at my television whenever an umpire makes a bad call, so maybe not? I hope that developers and the physical game publishers/rights holders consider AI to be a more vital piece of the digital port puzzle as this niche continues to expand. There are some pretty convincing stats about offline vs online play, and the reaction to especially high profile recent cases of poor AI should be fair warning. For now, thank a developer for the hundreds of nodes they have in their neural networks which allow an AI to crush you mercilessly.