|
Some Thoughts on Artificial Intelligenceby Shannon Appelcline I should start off by saying I'm not even close to an expert on artificial intelligence design. I did take a class on the topic over ten years ago at UC Berkeley, but the professor was much more interested in his next career as a highly-paid executive at Sun Microsystems then his then-current one as a professor (which is pretty ironic, because he was still one of my best teachers at Cal--which in turn says a lot about the university teaching system). We students took out of that course what he brought in. I vaguely recall programming in a much despised language called Common Lisp and I know I did put together some type of game playing engine, for Checkers or Chess or some other classic game. I've had one other notable experience with AI. A year or so later, when I was working at NASA, I was around when the programmers built an AI system to monitor our satellite when no one human was around (all as part of cost-cutting measures). I didn't have anything to do with it per se, but I did hear lots of discussions about how it worked. And that's the extent of my formal experience with AI. Nonetheless, artificial intelligence comes up from time to time in game design. As an industry, I think we're largely moving away from it, or at least not developing it in any particularly exciting ways, because more and more we're realising that other players make the most interesting opponents, not computerized NPCs. Still, AI designs do show up here and there. Both The Eternal City and Grendel's Revenge have simple AIs for fighting computerized opponents. Gang of Four recently introduced some AI players for when other players aren't around. We even have some basic AI systems in Castle Marrach as part of our various NPCs systems. It's to a certain extent a necessity in populating a game sufficiently. But none of that is what has brought AI to the forefront of my thought in recent days. For the last couple of weeks I've been running a roleplay game of Galactic Emperor: Hegemony. These RP games require some simple AI because I can't both oversee a game and make decisions for the NPC forces, as I have too much information (and not enough time). I think the "organic AI" system that I use for Hegemony is cool and unique in some ways, because it's not laid out the way a standard AI system is. But, before I get there, it's worth talking about how most folks have done AI to date. Expert RulesArtificial Intelligence is a pretty magic-sounding thing. People might thing of C3PO or that obnoxious little robot in The Black Hole--critters that generally seem to think like humans do. Unfortunately, that's not how most modern-day AI works at all. Instead, most modern-day AI is built on what we call "expert rules", which is a fancy way of saying "conditionals" or "if ... thens". In other words, most modern-day AI is built on a long list of "if you see this particular situation, then do this particular thing". To understand this more completely, I think it's worth considering Gang of Four as an example; this game now has a set of maybe a half-dozen "robots", each with different expert-rules lists. I don't know how they work exactly, but I can guess. To start off, it's worth mentioning that Gang of Four is a card game, where it's your objective to get rid of the 16 cards from your hand. Leads can be either singletons, pairs, triples, or 5-card Poker hands; following cards must match the number of cards of the lead and must be of higher value. Plays continue until everyone passes in turn, at which point the person who played the last card wins the trick and gets to make the last lead. (Some folks call this style of play "rolling trick", because it's not a simple trick where everyone plays one card.) The game also includes a special "Gang of 4" (4 cards of the same rank) which may be used to "trump" any other play. There's one other semi-notable rule: at the start of a hand, if you won the last hand, the loser pases you his worst card and you pass back a card of your choice. If I were going to write a really dumb set of expert-rules for Gang of Four, it would look something like this:
That's AI, and I expect it's not terribly far from the "Dumb Bot" AI that Gang of Four uses. As an alternative set of rules, I could have told the AI to play the "highest" card value it could have when it was led to and when it was leading, with the hope that the 'bot would get to hold on to the lead. This, I expect, is not far from the "Aggressive Dumb Bot" used at Gang of Four (a 'bot that I hate because it plays so unlike most good players). In truth, neither of these 'bots is very good. The real trick of AI is to keep refining rules until you get to the point where the AI does many of the things that a good player would. If I were to keep refining my expert rules for Gang of Four play, I might come up with something like this:
I could keep refining this AI until I had a system that played like an average player. I'm not there yet with my updated expert rule list, though it's better, and with a good set of expert rules, put together by an expert player, you can have a halfway decent opponent. Gang of Four Online has managed this with a "Griffon Bot". I've only lost to it once, on a particularly bad game, but it can still be pretty dangerous, and does most things "right". Unbeatable AIFor most expert rules lists, the object is to keep adding to the list until you've got an AI to act like a half-decent player. Still, the majority of game players will complain that the AIs aren't good enough. Surprisingly, there's a subclass of games where AIs can be all but unbeatable with some pretty simple programming. These are mostly "cost-benefit" games, where every decision is a valuation; usually you're purchasing some type of resource (or using time to earn some resource) which will later be directly turned into profit. Human players probably just make many of these valuations by the seat of their pants, but computers can instead do every required calculation, quickly and correctly, and thus have an advantage over their human foes, mainly because their expert-rule decision-matrix has much better input. Empire Builder was, I thought, a game that fit into this category. In this railroad game you get demand cards which tell you goods to deliver to certain locations, with three choices per card. Each delivery has two clear costs: money to build the track from any one of several possible sources tothe destination; and time to move your train to the source, then to the destination. No human is ever going to precisely chart out all the costs in money and time to decide which demands are the best to take, but a computer could easily do so. I was thus quite leary when I started playing a computer version of Iron Dragon, an Empire Builder variant, especially when I saw that its AI players really did do a huge mass of calculations against all the possible sources and destinations for all the demands. Somehow, though, the computer in Iron Dragon loses badly. I'd have to guess that it includes expert rules that just aren't that bright (e.g., it starts building track toward a destination that it can't actually afford to reach), and with bad expert rules, the most superior input in the world won't help. Nonetheless, the core point is a valid one. If you're building a particularly computational game, be careful with your AI systems, as the computer's input might be so much better than the human players', that with a good set of expert rules, it might be unbeatable. (In which case you probably have to start dialing back the AI, so that it takes, say, the 80% best choice, rather than the 100% one.) Cheating AIBefore closing the book on traditional AI design, it's worth mentioning one last feature commonly used: cheating. That's right, some designers, rather than actually taking the time to figure out a good set of expert rules for their computers instead just let them cheat, usually by getting free resources or cheaper resources, having more dangerous units, etc. Players seem to hate this, so it's not a method I particularly suggest. Organic AIWhen I put together my first roleplay game for Galactic Emperor: Hegemony, a few years ago now, I knew I needed an AI system, but I had little desire to write up a complex expert-rules system. Thus I came up with another method for implying artificial intelligence, which I like. I call it "organic AI", and it only works because of the generally organic nature of Hegemony. Hegemony, if you're not familiar with it, is a space-conquest game. There are about 150 stars in the galaxy, and your goal is to take control of as many as you can with starships which slowly jump from system to nearby system, allowing you to spread across the galaxy. Usually you issue commands in Hegemony in real-time. You tell a fleet at planet A to jump to planet B (which will then take some number of realtime hours). However, early in our development of Hegemony, we came up with a new method of command called "standing orders". You could associate an order with a planet, to say, "if there are more than X ships on planet A, send the rest of them to planet B". Thus, whenever ships arrived at planet A they'd immediately move on to planet B. My first thoughts for an organic AI system for Hegemony centered on these simple standing orders. I envisioned a spiral galaxy game with a large force of NPCs starting (and breeding) at the center of the spiral. Every planet in the galaxy would then have a standing order for the NPC forces: if you arrive at this planet, go on to the next one in the spiral. It would have sort of worked, but it would have been totally unwieldly as 150 planets would have needed precise orders--and if a planet had ever gotten destroyed, the whole thing would have gotten clogged up. It was an interesting idea, but not really usable. And so I came up with the core of the idea I used instead. I came up with three "special" standing orders, only used by the NPCs. They were:
These may sound simple (and they are), but they allow for some surprisingly complex behaviors. In two roleplay games I've run, I've used the same basic configuration. First, I start off with a high-value production planet in the middle, and give it an attack order with a high garrison (that is, a high defending force). Then, I put a few strongly defended planets around it, and give each of those planets an attack order too. Then, I give each other planet in the galaxy a disperse order. The result? If anyone ever gets too close to the outlying planets, they attack, and after they attack their fleets then disperse, trying to take every planet near the original infiltration (and looking a lot like a counter attack). Conversely, if anyone ever manages to take one of the strongly defended planet, they're almost immediately attacked from the core home planet, with the attacking fleet probably moving on afterward. Again, some simple, discrete orders give the strong indication of an intelligent force behind them. My organic AI still does stupid things. The disperse orders are random, so there's a lot of time spent moving between the NPCs' own planets rather than going for the enemy. Likewise, the attack orders don't differentiate between "important" planets that are taken and "unimportant" planets, nor do they respond with a fleet size appropriate for the infiltrator's fleet size. I could do a lot to improve them. First up, I think I'd introduce some new order types, such as a "support", which would add ships to planets that had been attacked and maybe an "inward" and an "outward" order to try and control general directions of movement toward and away from the center of the board. I suppose this is all still expert rules of a sort, as each individual location is given a rule to follow, and those individual rules could also be improved (such as by making the "attack" rule more discerning). However, I also think this system pushes AI in a different way than is normal for the field. Rather than building long, master lists of rules, you're sort of building an organic entity, like the human body. You're naming some locations to attack, some to defend, and some to support, and by doing so you're create a whole that is more intelligent (or at least looks more intelligent) than any of the individual pieces. It only works if some sort of master design is possible, but I think it's a neat way to look at the field. |
