Author Topic: More about the inner workings of the AI in AI War.  (Read 12992 times)

Offline x4000

  • Chris McElligott Park, Arcen Founder and Lead Dev
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,651
More about the inner workings of the AI in AI War.
« on: June 01, 2009, 07:30:09 am »
UPDATE:  This has been fleshed out into a much more informative and detailed series of articles:  

Designing Emergent AI, Part 1: An Introduction
Designing Emergent AI, Part 2: Queries and Code
Designing Emergent AI, Part 3: Limitations
Designing Emergent AI, Part 4: Asymmetrical Goals


Quoting from a discussion over at Gamers With Jobs:

Quote from: x4000
Quote from: Lucan

Hey, can you tell me more about the AI. I assume it's still rule based even though there are more agents involved. Can you elaborate on the structure you used to set those rules up? I'm interested in how it internally works.

Hey, sure thing -- I'm going to be writing a full article on this topic in the next couple of weeks, but here's a quick rundown.  First, the way that AI systems in most games work is via giant decision trees (IF A, then C, IF B, then D, etc, etc).  This can make for human-like behavior up to a point, but it requires a lot of development and ultimately winds up with exploitable flaws.  My favorite example from pretty much every RTS game since 1998 is how they pathfind around walls; if you leave a small gap in your wall, the AI will almost always try to go through that hole, which lets human players mass their units at these choke points since they are "tricking" the AI into using a hole in the wall that is actually a trap.  The AI thus sends wave after wave through the hole, dying every time.

Not only does that rules-based decision tree approach take forever to program, but it's also so exploitable in many ways beyond just the above.  However, to emulate how a human player might play, that sort of approach is generally needed.  I started out using a decision tree, but pretty soon realized that this was kind of boring even at the basic conceptual level --if I wanted to play against humans, I could just play against another human.  I wanted an AI that acted in a new way, different from what another human could do, like playing against Skynet or the Buggers from Ender's Game, or something like that.  An AI that felt fresh and intelligent, but that played with scary differences from how a human ever could, since our brains have different strengths and weaknesses compared to a CPU.

The approach that I settled on, and which gave surprisingly quick results early in the development of the game, was simulating intelligence in each of the individual units, rather than simulating a single overall controlling intelligence.  If you have ever ready Prey, by Michael Crichton, it works vaguely like the swarms of nanobots in that book.  The primary difference is that my individual units are a lot more intelligent than each of his nanobots, and thus an average swarm in my game might be 30 to 2000 ships, rather than millions or billions of nanobots.  But this also means that my units are at zero risk of ever reaching true sentience -- people from the future won't be coming back to kill me to prevent the coming AI apocalypse, haha.  But I can get much more intelligent results with much less code and fewer agents.

There are really three levels of thinking to the AI in AI War: strategic, sub-commander, and individual-unit.  So this isn't even a true swarm intelligence, because it combines swarm intelligence (at the individual-unit level) with more global rules and behaviors.  How the AI decides which planets to reinforce, or which planets to send waves against, is all based on the strategic level of logic -- the global commander, if you will.  The method by which an AI determines how to use its ships in attacking or defending an individual planet is based on a combination of the sub-commander and individual-ship logic.

Here's the cool thing:  the sub-commander logic is completely emergent.  Based on how the individual-unit logic is coded, the units do what is best for themselves, but also take into account what the rest of the group is doing.  It's kind of the idea of flocking behavior, but applied to tactics and target selection instead of movement.  So when you see the AI send its ships into your planet, break them into two or three groups, and hit a variety of targets on your planet all at once, that's actually emergent sub-commander behavior that was never explicitly programmed.  There's nothing remotely like that in the game code, but the AI is always doing stuff like that.  The AI does some surprisingly intelligent things that way, things I never thought of, and it never does the really moronic stuff that rules-based AIs occasionally do.

And the best part is that it is fairly un-trickable.  Not to say that the system is perfect, but if a player finds a way to trick the AI, all they have to do is tell me and I can usually put a counter into the code pretty quickly.  There haven't been any ways to trick the AI since the alpha releases that I'm aware of, though.  The AI runs on a separate thread on the host computer only, so that lets it do some really heavy data crunching (using LINQ, actually -- my background is in database programming and ERP / financial tracking / revenue forecasting applications in TSQL, a lot of which came across to the AI here).  Taking lots of variables into effect means that it can make highly intelligent decisions without causing any lag whatsoever on your average dual-core host.

Fuzzy logic / randomization is also another key component that I forgot to mention earlier.  A big part of making an unpredictable AI system is making it so that it always make a good choice, but not necessarily the 100% best one (since, with repetition, the "best" choice becomes increasingly non-ideal through its predictability).  If an AI player only ever made perfect decisions, to counter them you only need to figure out yourself what the best decision is (or create a false weakness in your forces, such as with the hole in the wall example), and then you can predict what the AI will do with a high degree of accuracy -- approaching 100% in certain cases in a lot of other RTS games.  With fuzzy logic in place, I'd say that you have no better than a 50% chance of ever predicting what the AI in AI War is going to do... and usually it's way less predictable than even that.

Bear in mind that the lower difficulty levels make some intentionally-stupid decisions that a novice human might make (such as going for the best target despite whatever is guarding it).  That makes the lower-level AIs still feel like a real opponent, but a much less fearsome one.  Figuring out ways in which to tone down the AI for the lower difficulties was one of the big challenges for me, actually.

Lastly, the AI in AI War follows wholly different economic rules than the human players (but all of the tactical and most strategic rules are the same).  For instance, the AI starts with 20,000+ ships in most games, whereas you start with 4 ships per player.  If it just overwhelmed you with everything, it would crush you immediately.  Same as if all the bad guys in every level of a Mario Bros game attacked you at once, you'd die immediately (there would be nowhere to jump to).  Or if all the enemies in any given level of an FPS game just ran directly at you and shot with perfect accuracy, you'd have no hope.  Think about your average FPS that simulates your involvement in military operations -- all of the enemies are not always aware of what you and your allies are doing, so even if the enemies have overwhelming odds against you, you can still win by doing limited engagements and striking key targets, etc.  I think the same is true in real wars in many cases, but that's not something that you see in the skirmish modes of other RTS games.

In AI War, to offer procedural campaigns that give a certain David vs Goliath feel (where the human players are always David to some degree), I made a separate rules system for parts of the AI versus what the humans do.  The AI's economy works based on internal reinforcement points, wave countdowns, and an overall AI Progress number that gets increased or decreased based on player actions.  This lets the players somewhat set the pace of game advancement, which adds another layer of strategy that you would normally only encounter in turn-based games.  It's a very asymmetrical sort of system that you totally couldn't have in a pvp-style of skirmish game with AI acting as human standins, but it works beautifully in a co-op-style game where the AI is always the enemy.

Hopefully this answers most of what you wanted to know, although this is kind of a surface-level overview despite how long it turned out to be.  I'll do a more structured, in-depth article in the next few weeks, like I said.  But if you have any other specific questions about how the AI works, don't hesitate to ask!  I'm not shy about talking about the inner workings of the AI system here, since this is something I'd really like to see other developers do in their games. I play lots of games other than my own, just like anyone else, and I'd like to see stronger AI across the board.
« Last Edit: August 17, 2009, 03:30:26 pm by x4000 »
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Sorceresss

  • Newbie Mark II
  • *
  • Posts: 14
Re: More about the inner workings of the AI in AI War.
« Reply #1 on: June 01, 2009, 01:28:35 pm »
Extremely interesting stuff ... even though it is sometimes way over my head (since I'm not a programmer).

Two questions (for now). You say :

"The AI runs on a separate thread on the host computer [...] Taking lots of variables into effect means that it can make highly intelligent decisions without causing any lag whatsoever on your average dual-core host."

I read elsewhere that in a MP game, you recommend that the host computer have a dual-core processor.

Q1 > Does your quote imply that those of us who still have single-core processors (mine is an old 2.8 GHz P4) will experience significant problems running the game in SP mode (even if we never dare host a MP game) ?

Q2 > What game-setup options should then be unchecked to reduce those potential problems ? In other terms : what are the specific game-setup options that will cause the most processor usage by the A.I. players ?


Offline x4000

  • Chris McElligott Park, Arcen Founder and Lead Dev
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,651
Re: More about the inner workings of the AI in AI War.
« Reply #2 on: June 01, 2009, 02:19:17 pm »
I read elsewhere that in a MP game, you recommend that the host computer have a dual-core processor.

Q1 > Does your quote imply that those of us who still have single-core processors (mine is an old 2.8 GHz P4) will experience significant problems running the game in SP mode (even if we never dare host a MP game) ?

Q2 > What game-setup options should then be unchecked to reduce those potential problems ? In other terms : what are the specific game-setup options that will cause the most processor usage by the A.I. players ?

Answer 1 - We don't differentiate between single and multiplayer games.  In a single player game, the sole computer is the "host," so yes, having a multicore processor can be a help.  However, with a 2.8 Ghz computer you should be fine.  I've run the game on a 2.4 Ghz single-core machine without lag, and on a 1.8 Ghz machine with very little lag.  The main issue is that your machine would not be a very good choice for hosting a larger multiplayer game, and you might want to stick to 80 planet maps instead of 120 planet maps.  Especially if you are playing on the lower difficulties, you shouldn't see any issues whatsoever.

Answer 2 - Well, playing with fewer players, on smaller maps, with lower AI difficulties all reduces the load on the CPU.  If you are playing by yourself on 80 planet maps, you should be able to play pretty much any AI difficulty with your setup.  Even if you start playing against the very hardest AIs like that, if there is any slowdown it would most likely be not very noticeable.

Great question!
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Sorceresss

  • Newbie Mark II
  • *
  • Posts: 14
Re: More about the inner workings of the AI in AI War.
« Reply #3 on: June 01, 2009, 03:16:21 pm »
Thanks for your very informative reply.

I'll never get very good at RTS games like yours, so I guess that I should experiment with more modest game-setup parameters, as you recommend, for my single-core, 2.8 GHz Pentium.

Anyway, at home, we have another machine which has a more powerful processor : a 3.4 GHz Pentium D (which is a type of dual-core processor). I guess that if I ever want to tackle a more difficult A.I., I can try it on that other machine.

By the way, I just posted your whole, lengthy OP on a Demigod-forum thread, where A.I. was discussed. See reply #15 at :

http://forums.demigodthegame.com/354259/#2236552


Offline x4000

  • Chris McElligott Park, Arcen Founder and Lead Dev
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,651
Re: More about the inner workings of the AI in AI War.
« Reply #4 on: June 01, 2009, 03:26:07 pm »
Hi Sorceresss,

Well, I think it mostly just takes practice and experimentation to get really good at RTS games like AI War. I've been playing them since the mid-90s and I know that I'll never be truly world-class.  Same reason I was never a grandmaster a chess, or anything like that, I just don't have enough natural talent or infinite time to devote to them.  That's why I tailored the upper levels of the AI to be better than I can actually play against myself, so that the truly amazing players out there would have something to do.

For people new to RTS, I think that AI War is easy enough on the lowest difficulties -- the AI really doesn't put up much of a fight most of the time in there, unless you get really unlucky -- but at the same time, my chief worry was that players would find the game too overwhelming when they started.  So far that doesn't seem to be the case most of the time, hope that is not the case with you, either.  If there is some sort of other information / training material that you think might ease the transition into a game this complex, let me know!

Thanks for the link over the the Demigod forum, by the way -- I'll post some additional thoughts over there. :)
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

 

SMF spam blocked by CleanTalk