Hey Everyone! Iâm Dave Churchill, lead AI programmer on Prismata. While working for Lunarch Iâm also finishing up my PhD in video game AI at the University of Alberta. In 2013 my StarCraft AI bot UAlbertaBot won the AIIDE StarCraft AI Competition, which we have been hosting at UofA since 2010. There are a lot of similarities between the AI for StarCraft and for Prismata, and weâve been able to use some state-of-the-art RTS AI research techniques with new twists. For those not familiar with it, Prismata is a hybrid strategy gameÂ that combines ideas from RTS games, card games, and tabletop strategy games. A "how to play" video is available here. Some people describe Prismata as a "real-time strategy game without the real-time". However, Prismata presents many new and unique challenges that make it different from a traditional RTS in terms of AI design. Letâs dive into an overview of the AI in Prismata: from initial motivations all the way to implementation details.
âVideo game AI is about making agents in the game do things that engage the player and make them have funâ. - Max Dyckhoff Â (AI programmer for the Halo series)
This was our goal in Prismata â to design an intelligent, dynamic, and flexible AI system to allow players to have the most fun. The AI was designed with several goals mind. We want itÂ to:
In game theoretical terms, PrismataÂ has the following properties:
Part of making a fun AI is making an intelligent AI that can play the game well.
A common myth among beginners:Â âPrismata is simple, you can just solve it!â
Actually,Â Prismata is a very complex game. In order to prove this, letâs take a look at the two most popular ways to measure game complexity:
This is the term used to describe the number of possible positions (or states) a game can have. Take for example the game tic-tac-toe, which has 9 possible spaces and 3 possible values for each space: Blank, X, O. If each of the 9 spaces has 3 possible values, then we have 3 to the power of 9, or 3^9 = 19683 possible tic-tac-toe boards. If we then subtract the number of impossible states (ie: all Xâs) and the states thatÂ are equal due to symmetry, that number shrinks to 765 states, which is easily solvable by computers. More interesting games have much larger state spaces. Checkers is the largest game that has ever been solved by computers. With approximately 5*10^20 (five hundred billion billion) states, it took over 200 computers 18 years to solve (finally completing in 2007). More complex games like Chess (with 10^47 states) have not been solved, even though AI researchers have been working on them since the 1950s.
In Prismata, we can calculate a rough estimate of the state space as follows. In a typical Base + 8 game players have access to 11 base units and 8 random units, for a total of 19 units per player, or 38 in total. If we give a conservative average supply limit of 10 per unit per player, then the number of possible combinations of units on the board at one time in Prismata is 11^38. We then have to consider that each unit can have different properties, can be used or unused, have different amounts of hit points or stamina, etc. If we give a very conservative estimate of an average of 30 units on the board at a time, each with 3 possible states, then we get 3^30 combinations of properties of those units, or about 10^14. Now factor in the fact that Prismata has about 70 units (so far) of which 8 are selected randomly, and we have about 10^10 possible starting states in Prismata.
Multiplying this all together gives a very low estimate of 10^64 for the state space of Prismata, or about a billion billion times more complex than Chess. Good luck solving it!
There are about 10^80 atoms in the universe, so 10^64 is pretty big. Prismata has at least as manyÂ possible states as atoms in the Milky Way Galaxy!
This is the term thatÂ describes the number of possible moves you can do at any given time in a game. You can consider the action space as a measure of complexity because it shows how hard it is to make a single decision in a game. In a typical board game like Chess, your turn consists of taking a single piece and moving it to another position on the board. An average chess turn has approximately 30 possibilities. Taking a turn in Prismata consists of 4 main strategic decisions: Â How to defend, what to buy, how to activate abilities, and how to breach your opponent. Even if we consider these problems individually, each of them has an exponential number of possible sequences of actions. In computer science we call these type of problems NP-Hard. In other words, Good luck trying to solve them! Letâs take buying unitsÂ as an example.
Buying unitsÂ in Prismata is what is known as a Knapsack problem in Computer Science. If we consider unit prices to be objects, and our total resources to be a knapsack, we are trying to fit as many of those objects into our knapsack that we can. For example, with just 8 gold and 2 energy in Prismata, there are 18 possible combinations of units that can be bought! (For the Prismata-inclined, they are: Nothing, E, EE, EEE, EEEE, D, DD, ED, EED, C, CC, EC, EEC, DC, B, EB, DB, A, EA.) By the middle of the game, the number of possible buying actions can easily reach tensÂ of thousands. If we combine this with the number of ways to block, use abilities, and breach, we find in most mid-game situations, there are literally millions of different ways in which we can play a single turn!
With these resources, there are over 25,000Â combinations of units that can be purchased... in the Prismata base set alone!
Writing AI for complex games is very difficult, and often times game developers will take âshort cutsâ with the AI in order to make the AI look stronger than it actually is. In Prismata, both players have access to all information about the game. There are no decks, hands, or RNG. This makes writing an AI for Prismata more difficult than most games, for several reasons:
There is no âlooking intelligentâ in Prismata. The AI is either is intelligent, or it isnât. We need to use state-of-the-art artificial intelligence techniques in order for the AI to play the game at a competent level.
We canât solve Prismata by brute force, so we need a way to manage the complexity. To drive the AI in Prismata, we use a method called Game Tree Search. Game tree search is essentially a method thatÂ checks âIf I do this action, then my opponent does that, then I do thisâŚ which is the best move?â You may have heard of grandmaster chess players who are able to look 10 to 20 moves into the future in order to choose a good move. They are actually executing a form of game tree search! The specific algorithm we use to perform the game tree search is called Monte-Carlo Tree Search (MCTS). This algorithm and variants of it have been used by several world champion computer programs for playing board games such as Go. Basically, the algorithm does many simulations of the game (called "playouts") to predict what will happen in the future if a player makes a certain move. Each time a playout is performed, the algorithm gains more information about which moves are better and which are worse, eventually deciding on one it thinks is the best. There are several advantages of using MCTS in a game like Prismata:
The Prismata AI in action! :)
If youâve been following along, you might now be thinking âbut you just got finished saying that there could be millions of actions in Prismata, surely even MCTS canât handle that many actions.â And youâd be right. This is why weâve developed a system for dramatically reducing the number of moves that MCTS deals with from possibly millions down to just a few dozen good candidates. Part of my research in Real-Time Strategy Game AI was writing algorithms to control how units attack in StarCraft, or âunit microâ as players call it. This is another scenario where a player has a bunch of units, each with their own possible actions to perform, resulting in an exponential number of moves possible at any given time.
We found a technique that works very well in these domains, called a âportfolioâ approach: instead of trying every possible move thatÂ we can perform, instead we use a âportfolioâ of algorithms to generate a much smaller, yet more intelligent set of moves to search over. It turns out that Prismata has some nice properties thatÂ make this method especially powerful. Prismata has 3 distinct game phases: Defense, Action, and Breach, each with their own rules and set of goals. In the defense phase you are trying to most efficiently keep your units alive, in the action phase you are trying to perform actions to generate attack and kill your opponent, and in the breach phase you are trying to most effectively destroy your opponentâs units. We can break these 3 phases down even further by considering the action phase as two separate sub-phases: using abilities, and buying units, leaving us with 4 phases. While these phases are technically all part of the same turn, even the best human players often consider them as independent problems thatÂ they try to solve separately, as the entire turn would be too much to mentally process at the same time.
We combine this idea of separately solving phases with the computational power of game tree search. Prismataâs AI has a number of algorithms for attempting to choose good actions for each individual phase. For example, in the defense phase we could have one algorithm that tries to minimize the amount of resources you will lose if you block a certain way, while another algorithm would try to maximize the amount of attack you have remaining to punish your opponent with. Similarly, one algorithm for the card-buying phase could try to maximize your economic output for the next turn, while another could try to buy as much defense as it could to thwart an incoming enemy barrage.
We then search over all combinations of these algorithmically-generated moves in the high-level MCTS algorithm to decide which combination of phase moves results in the best overall move for the turn. This reduces the number of possible moves searched by MCTS from (possibly) millions down to something manageable. By not considering all possible moves this does mean we might miss the perfectly optimal move for a turn, but that optimal move was nearly impossible to find in the first place! Right now, the number of moves that our MCTS algorithm searches per turn is somewhere in the range of 10-40, depending on the complexity of the scenario.
An important goal for the Prismata AI was also to have multiple difficulty settings for the AI so that players of any skill level can enjoy it. The portfolio approach actually makes different difficulty settings quite easy to manage. We start with the hardest AI, then we can turn off certain algorithms thatÂ make the AI play well in specificÂ situations. For example, the main difference between the Easy and Medium AI is that the Easy AI does a really poor job of buying defensive units, leaving it vulnerable to attacks. All of the AI settings and parameters are completely data-driven, meaning that we only need to change a value in a text file to change how the AI behaves. In fact, starting from the Master Bot, all the other difficulty settings were created in about 15 minutes without editing a single line of code!
âBut isnât simulating the entire Prismata game state thousands of times really slow?â It really is, especially in ActionScript. For this reason, the entire Prismata engine was completely re-written in C++, minus the GUI, networking and animation logic. This stripped-down version of the engine is highly optimized for speed, and is compiled from C++ back into ActionScript using a tool called CrossBridge. CrossBridge takes the optimized C++ assembly output and converts it into ActionScript bytecode, yielding code that is several times faster than if it was coded in ActionScript in the first place (around 10x slower than native C++ code). This ActionScript code is then injected back into the Prismata engine, and runs in a separate thread.
Whenever Prismata wants a decision to be made by the AI, it sends off the current game state information to the AIÂ thread and waits for the result. This means that we donât have to interleave the AI logic with the animation / game logic, resulting in far more available CPU thinking time for the AI. A nice byproduct of this process is that there actually exists a native C++ version of the Prismata engine, which is capable of performing millions of moves per second. We can use this C++ engine offline for a number of tasks, such as automated QA testing, AI performance tuning, and game balance testing. This engine also has its own simple GUI written in OpenGL so that we can test AI functionality without requiring it to be compiled back into the PrismataÂ client, resulting in much faster AI development cycles. Here's a short video showing some of the AI testing in action.
As an experiment to see how the most recent version would perform in the wild, we decided to secretly test the AI against human players on the Prismata ranked ladder. For 4 hours one morning, the bot automatically queued and played ranked games under the name "MyNameIsJeff" and climbed from its initial Rank III up to 50% into rank VI with a record of 20-13. By adding random time delays to the bot's clicking, we also seemed to have passed the Prismata Turing Test, with nobody saying that they felt that they were playing against a bot. Here is a screenshot of the bot's home screen after we turned it off:
By now, you should have a pretty good understanding of the AI in Prismata: Why we did it, how complex it is, and how we have implemented it. The AI in Prismata will never be âfinishedâ. It will always continue to be improved with new features, difficulties, and playing strength improvements. I really hope that you have fun playing against the bots, and feel free to give us any feedback about the AI at any time :) Â