Episode 180: Thinking Machines

[Rob Zacny]

Soren Johnson and Cryptic Comet's Vic Davis return to talk with Julian and Rob about artificial intelligence, its limitations, and their changing views on what to do about it.

Listen

[biz]

It's sad that the genre is still stuck on making competent AI and hasn't progressed towards making interesting opponents.

it would be nice if more developers took the asymmetrical approach or actually prioritized AI, because they are completely failing with their current approach (in terms of game quality)

most strategy games being made are still very symmetrical in terms of starting resources and abilities and goals, and the mechanics are still designed for competitive play in an adversarial setting (not like e-sports competitive, but competing in combat, competing for land/resources, competing for victory, etc.)

gamers are in this odd situation where a typical strategy game is kind of useless once you learn how to play it. (oddly enough, a lot of games are also kind of useless until you learn how to play... that alone says a lot about the health of the genre)

It should be the other way around, like in board games, which become way more fun after you learn the rules.

the actual strategy game is the gap between learning the rules (boring chore) and mastering it (mindless execution).

from a design level, the games are really good (imagine if the opponents were human), but that rarely translates successfully to singleplayer.

There are some solutions though that don't involve giving up symmetry.

• The AI development could be outsourced. Community-driven AI probably won't work if you need an AI to ship with the game, but it's probably more efficient to have a team of AI specialists work on a game during the few weeks/months before release rather than to have each studio maintain its own AI group (which can't really specialize in AI because it isn't relevant during all phases of development). It doesn't help that so many strategy games are these low-budget passion projects that don't have an AI group.
  
• The game could be asynchronous. Instead of trying to plan moves for each opponent one by one in the fraction of a second between turns, they could do it while the player is making his move. this way, each opponent can think independently and therefore in parallel (utilizing our supercomputers or the cloud). (That's 100-1000x more thinking time. It's how 1 move ahead becomes 3 moves ahead)
  
• The AI could cheat. Developers use this as a quick-fix, but they tend to implement it poorly. It's probably because they haven't mastered the game and don't really know what to scale and what to leave untouched and how to do the scaling. Units moving in stupid ways is still a dumb AI, regardless of how many extra units there are.
  

[ShadowTiger]

In response to biz:

1. There are several contract AI programmers which do as you suggest, travel between games and only work on AI.

2. Having the AI decide its actions during your turn is a basic principle that developers should use when possible. It can be very complex though, Fallen Enchantress has it but it likely contributes to the instability of the beta. It doesn't really help much if the player is hammering the end turn button in a 4x game.

3. The AI can't always cheat. In a game like Chess... the only way it could cheat is by making the game asymmetrical, like defeat the opponent without one of your pawns. If you want a fair challenge, then you have to have an AI that performs well. Also, many players despise cheating AI, here is a small forum thread that shows that: http://forums.elementalgame.com/404724

In response to podcast:

As a modder, I think that allowing the community to modify and improve the AI for the game is usually a good idea. I am not sure how well this would work for smaller indie titles as there may not be enough talented people in their audiences.

I think that one big thing that all game developers should do to help their AI is to simply budget some post-release work on the AI. There are several games which put little or no work into the AI after release, often failing to patch exploits and bugs that are easy to fix and would improve the game greatly.

For games that are multiplayer, like Civ, but lack a fun way to engage in multiplayer, I have another suggestion. Instead of making the AI really fun to play against and simulating a human opponent, maybe it would be better to ease up on the AI and focus more resources on improving the multiplayer experience. I think theres lots of simple things we can do, perhaps looking at iOS games or other examples and find a way to get people engaged and committed to finishing a session in multiplayer. I guess this mostly involve social engineering to incentivize players to keep at it and also improving the UI and communication tools so that its easy to drop in and out of your sessions. Perhaps designing the game so that players can do stuff while its not their turn would also help things out, or simply a refinement of simultaneous turns.

As a programmer for a multiplayer game, I had to write an AI for the single player campaign as well as skirmish battles to let players practice in a low-stress environment. The AI I wrote was really simple and only a tiny fraction of the total effort spent on the game's code. However, it can beat even experienced players even though it doesn't understand many basic game mechanics. Since our game is chess-like, simply understanding the concept of where pieces can move and what spaces they threat is 90% of the battle. The AI's main advantage is that the game is an RTS so it can control several units simultaneously and react very quickly.

I found that part of making the AI fun to play against involves putting limits on things like reaction time and how many units it control at once. It will probably be user-adjustable eventually so top tier players can challenge themselves but for the average players it makes it less frusterating. In a RTS if the player is good at Macro and the AI is good at micro, you are essentially playing 2 different games. Supreme Commander and Age of Empires tend to annoy me with an AI that behaves like a swarm of insects rather than a coordinated army. Games like Dawn of War that limit the amount of micro to something I can manage tend to be more enjoyable.

For my game I would love to spend a month creating a system where the AI chooses strategies, then assigns orders to its units like sniper, guarding, healer, etc to fulfill those strategies. The thing is that the AI is sufficient for our purposes so it can't really be justified spending that much time. The Designer for our game is more concerned that the AI uses all the game mechancis properly and that it is consistent. I would love for the AI to be unpredictable, to lay traps, to try and read the player's strategy with complex formulas. The Designer wants it to be deterministic so that players can defeat the AI by learning its pattern. I think that since our game will have plenty of multiplayer access since a match takes less than 15 minutes and its an online-only game, he is probably right about what our priorities should be.

That being said, I really do think it is possible by simply using "high school" programing and a creative mind to design much better AI than we have seen. I am mostly thinking about Tactical Battles in RTS and 4x games, which is my favorite aspect of video games. I am confident that I could write better AI than most games have, it usually has to do with understanding the interactions between various concepts. I think that scripting the AI is a flawed approach and by simply structuring the AI so that it is data-agnostic and simply understands the core rules, it will be very competent. Basically don't hard code the AI and it will probably do better in the long run.

On the subject of designing the game around the AI, I think it is a great idea as long as you let the players have the final word. In Fallen Enchantress, heroes that die get resurrected with a simple injury as punishment as well as some mana being lost. Compared to other 4x games with permadeath, this is pretty tame and makes it so that you are killing the AI heroes over and over until they are begging to be put out of their misery with broken legs, missing eyes, mental trauma, and infectious diseases. Several players complained about this but it was put in because the AI sucks at keeping its heroes alive, and heroes are a very important source of military power. In other 4x games its generally easy to snipe enemy heroes and remove them from play, and humans make better use of heroes than AI players do. So I can understand the motivation to make the AI much stronger and save much coding time to prioritize their survival, but in the end I think it makes the game less enjoyable. A balance between design thats easy for AI and fun for players will be hard to reach in some cases.

If you made it this far, sorry if I am unloading a years worth of internal dialogue in a public forum, but hopefully its entertaining/insightful. The last topic is the 4x that I have been designing. I am flirting with the idea of having a combat system where the outcome is mostly per-determined before the battle happens. You have officers which are a limited resource that you assign to armies to boost their tactical prowess. Each officer would gain experience and learn new techniques, and you could have them teach each other tactics if you can get them in the same tent. Essentially the AI that controls your units in battle is a limited resource which you must carefully devote to certain battles, knowing that if you are defeated you have a chance of losing that officer forever. So instead of changing the game to suit your AI, by making the AI an intrinsic part of the game I think you can sidestep many of the pitfalls and create a fun and innovative experience.

To give players a bit of added control I was thinking they could have a commander unit which gives them direct control of any battles where that one unit is present. This could be interesting because it adds another limited resource, but it also might water down the concept or over-complicate the system. In the end, a simple spell casting system where on important occasions they can intervene with a lightning bolt to a certain enemy or with a sudden storm to give an advantage to certain unit types is probably a better way to give players that tasty morsel of control they will crave.

[Gwardinen]

This has been posted on these boards before, but

in strategy games generally and in Civilization in particular. Seems relevant.

[Flynn]

You guys touched a bit on whether general learning AIs could ever make AI in general more effective (machine learning, genetic algorithms, etc.) without requiring the designer to intimately know every best strategy about the game and construct the perfect decision trees and whatnot, which is never feasible.

One approach that has been more successful and easier to integrate is Monte Carlo based systems. That's what the latest Go AIs that are finally giving humans a run for their money use.

It's also what powers Mu and Tichu AIs, here's the developer talking about it: http://hfog.blogspot...01_archive.html

These approaches really are limited by current CPU cycles -- if there was 10,000 more cycles available, you can really go crazy.

I believe this absolutely brutal Race for the Galaxy AI was generated using machine learning (trained over a period of months of computing time) http://www.keldon.net/rftg/

He talks about it in this thread: http://www.boardgamegeek.com/thread/438698/race-for-the-galaxy-ai/page/37

Some of the AI neural nets for the Brink of War are only partially-trained; the AI performance in big games is way too slow and takes weeks to train. I'll need to fix that both so that players won't have to wait and to improve training speed.

[Illykai]

As Flynn says, Monte Carlo methods, in particular Upper Confidence bounds for Trees search (UCT), are the state of the art in academic game playing AI at the moment. Every year the Association for the Advancement of AI (AAAI) runs the General Game Playing (GGP - so many acronyms!) competition at its main conference. In the GGP, programs are given descriptions of game rules in a machine readable language and then compete to play the games as well as possible. The idea is that, unlike with Chess or Go playing programs, the programs have to take a general enough approach that they can compete well with any possible rule set. CADIAPlayer is the current champion and three time winner. You can check out AAAI GGP competition details here and CADIAPlayer, including its source code, here.

It turns out this is a bit of a coup, because as far as I know GGP was originally set up as a reaction to results in Chess and Checkers, where the world class programs use approaches that are highly optimized for those specific games. The idea with GGP was meant to be that researchers would have to think harder about how to get computers to understand the structure of a rule set in order to perform well. The fact that randomized search does amazingly well, without really having to consider rule structure at all, is both surprising and a bit annoying.

Monte Carlo methods are doing ridiculously well in several other domains too. In probabilistic planning some of the best planners are based on UCT, such as this one, and in robotics one of the most successful motion planning approaches uses RRTs, another Monte Carlo approach.

[SamS]

Dear Vic

Please, please, please port AE to the iPad.

TIA.

[King]

Writing a good AI is a very hard thing to do, and even worse to debug. This is because you can have several points of failure. Even if you do develop a system that allows you to identify what the AI is doing and improve it, it is still not a trivial task to make the AI better. I am going to come back to one of the more interesting experiments in AI, which was Hearts of Iron 3. In the game you had a system that allowed you to delegate control of units to the AI. This was brilliant from a testing perspective because we could quickly identify problems in the system. I played a test game as Italy, where after Ethiopia was conquered I asked the AI to transfer most of the troops to Libya, but the AI refused to do it. The system allowed to quickly identify and fix a bug in the naval transport AI. If we hadn't had that system, I would be playing away as Italy, invade Egypt and then find no troops there. Then you start looking for the problems, did it not build enough? Did it not prioritise Egypt enough? Was it prioritising somewhere else too much? These list of questions give you a flavour of what a developer is up against when trying to get the AI to work, all are valid possibilities for why there are no troops there. Of course the best bit of all, was that even with the system we had which sped up AI development dramatically, we still couldn't write an AI that was good enough to please players.

In some ways AI development is more like a death march than anything else, it will kill you before you get there. Also AI is a hard sell to players, Hearts of Iron 3 was, without doubt, our best AI to date. How do you sell that players? Telling people that doesn't get people excited, because this isn't something that people can get excited about. Saying it is a better AI while truthful, doesn't generate buzz in the way a game mechanic does. A game mechanic is something people can easily see and get their head around, AI isn't the same. Working for a studio that does put a high priority on AI, we know in a way it is costing us sales, because that same work could be used to do a shiny feature, adding polish or balance work that will give us more sales.

[robc]

...

In some ways AI development is more like a death march than anything else, it will kill you before you get there. Also AI is a hard sell to players, Hearts of Iron 3 was, without doubt, our best AI to date. How do you sell that players? Telling people that doesn't get people excited, because this isn't something that people can get excited about. Saying it is a better AI while truthful, doesn't generate buzz in the way a game mechanic does. A game mechanic is something people can easily see and get their head around, AI isn't the same. Working for a studio that does put a high priority on AI, we know in a way it is costing us sales, because that same work could be used to do a shiny feature, adding polish or balance work that will give us more sales.

In some games it may be hard to spot a good AI, but players can usually spot a bad AI. Well, at least players can spot when an AI doesn't behave in what seems to be a reasonable manner. In some cases a player may think the AI is bad because of a lack of transparency into the logic of how the AI works. The AI may have a good reason for taking a particular action that isn't apparent to the player.

Unfortunately, for the most part AI just can't compete with a competent human player without cheating, unless it can just overwhelm the player with its ability to make decisions quickly and manage a large number of units. For more complex games, the AI rarely seems to know how to use all the features. The AI in Unity of Command is better than most probably because the system the AI needs to work with isn't too complex. Game developers shouldn't make single player games that their AI just doesn't know how to play. I can appreciate the amount of work it takes to create even a basic game AI that isn't that competitive without cheats. Hopefully the industry as a whole decides it is important to improve in this area or computer opponents will continue to underwhelm. None of these criticisms are leveled against Paradox in particular.

[Gormongous]

Of course the best bit of all, was that even with the system we had which sped up AI development dramatically, we still couldn't write an AI that was good enough to please players.

I imagine that the biggest pitfall with AI is that the more experienced a player gets, the more likely he is to notice flaws. Other features like graphics or gameplay mechanics don't have that going on, and it's a fine line to walk. Either the AI is omnicompetent and the player quits prematurely (probably with accusations of cheating), or the AI possesses some weakness and the player quits once it becomes obvious (probably with accusations of laziness). I don't find it a very enviable situation, being subject to the Chick Parabola in a field where there's clearly still a lot of learn.

[King]

In some games it may be hard to spot a good AI, but players can usually spot a bad AI. Well, at least players can spot when an AI doesn't behave in what seems to be a reasonable manner. In some cases a player may think the AI is bad because of a lack of transparency into the logic of how the AI works. The AI may have a good reason for taking a particular action that isn't apparent to the player.

Unfortunately, for the most part AI just can't compete with a competent human player without cheating, unless it can just overwhelm the player with its ability to make decisions quickly and manage a large number of units. For more complex games, the AI rarely seems to know how to use all the features. The AI in Unity of Command is better than most probably because the system the AI needs to work with isn't too complex. Game developers shouldn't make single player games that their AI just doesn't know how to play. I can appreciate the amount of work it takes to create even a basic game AI that isn't that competitive without cheats. Hopefully the industry as a whole decides it is important to improve in this area or computer opponents will continue to underwhelm. None of these criticisms are leveled against Paradox in particular.

There are a couple of problems here, working for a strategy game developer I get to read our forum. Our fans tell as two things, one they don't want an AI that cheats and two they love complexity. This creates a problem for a developer, your two routes out of the AI conundrum are hit with posts that either say your AI cheats how dare it or you are dumbing down your games. I think the player base needs to think a bit more about what they actually want. At the moment it feels like the players are being unrealistic with their demands for the game. If players and developers can reach an understanding here then we can develop an AI that works with the game, but at the moment you are stuck in a situation were you are simply trying to the best job possible.

[King]

I imagine that the biggest pitfall with AI is that the more experienced a player gets, the more likely he is to notice flaws. Other features like graphics or gameplay mechanics don't have that going on, and it's a fine line to walk. Either the AI is omnicompetent and the player quits prematurely (probably with accusations of cheating), or the AI possesses some weakness and the player quits once it becomes obvious (probably with accusations of laziness). I don't find it a very enviable situation, being subject to the Chick Parabola in a field where there's clearly still a lot of learn.

This is espeically true in a historical game. The historical outcome of World War II is that Germany loses. So people expect a game where Germany loses more often than not. We are essentially required to write an AI that playes the game in a suboptimal fasion, otherwise people complain that the game is not historical. Then players can take advantage of thier historical hindsight to game the system.

[biz]

Turn-based strategy developers are basically in this mode where they design an extremely incompetent AI and try to make up for it with an extreme amount of cheating

The difficulty comes entirely from learning the unnecessarily complicated rulesets and then learning the AI's patterns. almost none of it is actually from making non-obvious and informed strategic decisions

When players are upset at cheating, it usually isn't because of the cheating. If they hated the cheating, they would never pick that difficulty level in the game setup screen... It's because it negatively impacts what they really want out of the strategy game, which usually involves some combination of interesting decisions, challenge, and victory

When someone is heavily invested in a strategy and it fails solely because the computer cheats, then the player is upset (eg. going for a wonder or religion in Civilization games)

When the player actually achieves what he made the optimal sequence of moves trying to do, he isn't upset if the computer cheats. He might even feel a greater sense of accomplishment

Players hate cheating opponents because the path to victory usually involves randomly manipulating and exploiting AI weaknesses instead of making informed decisions based on the cost/benefit analyses with which the game was designed. Completely closing off entire strategies and subsystems to the human is such bad game design... and it's so commonplace.

[robc]

There are a couple of problems here, working for a strategy game developer I get to read our forum. Our fans tell as two things, one they don't want an AI that cheats and two they love complexity. This creates a problem for a developer, your two routes out of the AI conundrum are hit with posts that either say your AI cheats how dare it or you are dumbing down your games. I think the player base needs to think a bit more about what they actually want. At the moment it feels like the players are being unrealistic with their demands for the game. If players and developers can reach an understanding here then we can develop an AI that works with the game, but at the moment you are stuck in a situation were you are simply trying to the best job possible.

I definitely don't envy the task you have cut out for you. I used to be a software developer and while I never did any game AI programming I can speculate how it can get complicated very quickly, even for a simple game. I've only been an occasional player of Paradox games (Europa Universalis and Hearts of Iron primarily), so I don't have the experience to say whether those games have acceptable AI. I like the approach to difficulty where the player can choose an easier side to play or a more difficult one, but the AI plays by the same rules and doesn't cheat. I don't think sides need to be perfectly balanced. There is no reason why a game needs to allow the world to be conquered by Haiti. I wish a game like Civilization would have ways to make the game more challenging without giving the AI large bonuses. I don't like playing beyond the King difficulty level because it makes getting wonders very difficult and that is where a lot of the fun lies for me. I have to believe a better AI could have been written for Civ if a greater priority was placed on it.