Wanted: Cheating AI

[Daynarr]

Thanks Courageous. I really appreciate your Last post. I mean it.
I think I didn't use the right expression, when I said 'cheating AI'. I should have clarified it much better. I was referring the AI that uses that cheating extensively in order to cover up bad design behind it. Most of the games I have seen (if not all) use some sort of cheating AI, and I don't find them to have bad AI. Just like you said, it is smart way to cover up for the advantages that human player has in comparison to the computer.
Now I see why you misunderstood me and I have to apologize, because it probably sounded like an insult to you. I just didn't expected it to be misinterpeded in such way, but I guess we all learn from our mistakes.
I do have some questions for you regarding the subject:
1) What methods are used to determine AI behavior in certain situations other than scripting?
2) I know that in chess AI uses its ability to process huge amount of information to decide its next move (the decision is based on points), so in that way it makes up for luck of human thinking ability (experience been one of them). I would like to know if that method used in chess programs only, or some designers use it for their projects too?

Again, thanks for that Last post.

[LintMan]

I really don't like cheating AI's - when I play a game, I want it to be challenging, but I also like it to be on even terms. Handicapping myself or giving the AI big advantages in order to make a challenging game doesn't appeal to me.

But given that, I'd say that #'s 4 and 6 shouldn't be considered AI cheating - if the data is available or can be derived, the AI can and *should* make use of it.

I also would be in favor of making certain information available to all players, if it would help the AI. ie: If the AI was able to make good use of the stats info from the "Scores" screen (such as if the AI used how much intel points an enemy is generating to decide how much if needs to put into intel/counter-intel to keep up), then I'd make the "show all players scores" standard instead of an option.

I also wouldn't mind seeing some of the game's rules and data changed in ways that might make things easier for the AI. For instance, the tactical AI is highly vulnerable to the shoot-and-run tactic. Going to a simpler combat model (say where shooting uses all remaining movement) or improving the combat model to fight that (say, by adding opportunity fire) would be ways to help the AI out without cheating.

If I HAD to accept cheating in some form, I'd probably prefer the AI to have bonus information over bonus resources.

To put my 2 cents in on the lazy programmer thing - in general, I disagree that it's laziness that's the cause for lousy or cheating AI's in games. I'd place the blame on 1) budget considerations and 2) lack of AI programmer expertise. What I mean is that programming a truly tough, non-cheating AI for a complex strategy game would be hard, and that translates to expensive, both cost- and time-wise. And since AI flaws are only visible to gamers after they've bought the game and played a while, it's much easier to skimp there than on, say, graphics. I fully believe it's possible to write a kick-butt non-cheating AI for a complex strategy game, but I don't think any developer's willing to budget for it.

As for #2, I'm not slamming game programmers - I just don't think many gaming companies hire programmers with their AI skills/knowledge in mind - I think there's more focus on graphics, animation, sound, and network programming skills. Writing good AI code is a skill like writing good netcode is, and the skill sets don't necessarily overlap, so if a game company isn't shopping for a good AI programmer, it's just luck if they happen to get one. (And even then it's back to the budget issue - if they won't spend the man-hours to test and fix the AI, it doesn't matter how good the programmers are.)

But then, of course, looking at Command and Conquer 2 (I haven't played RA2), I see a game they had several years to make, at a big-name big-budget developer, and it has virtually no improvements over it's predecessor...and I start wondering if it was laziness, too. :-)

[Courageous]

"I was referring the AI that uses that cheating extensively in order to cover up bad design behind it".
---
The best way of putting it might be to say that "cheating AI" is often used to mask the fact that a legitimate non-cheating solution to the problem was not known by the programmer. This leaves open a wide variety of explanations, some of them being that they are "lazy" or "bad designers," but many of them being simply that the problem was really, really hard -- or that there weren't enough programmers on the team -- or that there just wasn't enough of a budget -- or that some marketing guy redirected the programmers from AI to eye candy.

C//

[Courageous]

"But given that, I'd say that #'s 4 and 6 shouldn't be considered AI cheating - if the data is available or can be derived, the AI can and *should* make use of it. "
---
I personally believe you have chosen the best two ways for an AI to "cheat". In the game Imperialism II, I believe that they make use of both of these strategies and disguise them quite well. It's worthy of note that Imperialism II has to be one of the most difficult strategy games of all time. That game will bust your ***.

Note that #6 isn't an all-or-nothing affair. One can give an AI more information than it ought to have, but do it sparingly enough so that it doesn't look like it has perfect information.

Personally I don't find AI's which cheat over information to be offensive at all. That's just my opinion, though.

C//

[LintMan]

quote:

---

Originally posted by Courageous:
Personally I don't find AI's which cheat over information to be offensive at all. That's just my opinion, though.

---

For me, it depends a lot on what information it is the AI is being given... If it always knows the positions of all your ships, then stealth tech is useless, which would be a big disappointment in a game like SEIV which has lots of stealth tech. On the other hand, if it always knew my resource/research/intel amounts, I wouldn't mind much.

[Courageous]

Sure, I can see that. Suppose that you had a game with both stealth and limited range sensor technology. Then suppose that there was some small probabibility each turn that the AI would "correctly guess" where to search for you with sensor ships, based on some probabilities. While this is obviously cheating, from our perspective, it can easily justified (within reason) that you are SIMULATING the human ability to make good guesses. Such an implementation might not even be obvious to the player, actually.

C//

[LintMan]

quote:

---

Originally posted by Daynarr:

1) What methods are used to determine AI behavior in certain situations other than scripting?
2) I know that in chess AI uses its ability to process huge amount of information to decide its next move (the decision is based on points), so in that way it makes up for luck of human thinking ability (experience been one of them). I would like to know if that method used in chess programs only, or some designers use it for their projects too?

---

I'm not an expert on this stuff, but I did a bit of graduate coursework on AI and neural networks in the (sadly) increasingly distant past, and I'm in the mood to discuss AI stuff so I'll give the answers a go.

1) I would guess in a game like SEIV, much of the core AI behavior would be coded into the game. So you might have a primary AI routine called DoAITurn() which then calls subroutines to do all the steps the AI might take during its turn. These steps might be similar to what you would do on your turn, like responding to political Messages, scanning your systems for enemy incursions, moving your exploraction ships around, modifying your build and research queues, etc. Each of those steps could be a subroutine written to analyze the available data and decide what to do.

How does it decide what to do in those subroutines? Well, that's the tricky part. With scripting, the behavior is determined by the current state variables (ie: at war, exploring, etc) and what's in the script. So when building ships, it uses the ship building script to decide what ships to build. If you didn't want to use scripting, you might instead write a routine that examined an enemy's known designs, observed/spied out tech levels, and actual fleets and used that information to direct research and ship design to most effectively fight that enemy. For example, if the enemy seemed to have primarily missile ships, the AI might emphasize point defense research and place extra pdc's on its designs. Or if an enemy was using Allegiance Subverters, the AI might go for Master Computers. This type of decision making could make for a much more flexible AI opponent, but it is much harder to do, since so many more variables and special situations must be taken into account. This type of "If X and if Y, the do Z" would probably be called an "expert system", and in a sense, it is like a script, but with more conditional behavior control.

Other things an AI could do might be for it to do a cost-benefit analysis of weapons to decide which it wants to research. Potentially, a script could already take that sort of analysis into account, but your AI could be written to dynamically do it based upon its current needs. (In SEIV, this wouldn't be that beneficial, since Phased Polaron beams seem to be the optimal choice for beam weapons in nearly all situations).

Another decision making method used by AIs sometimes is randomness. Say the AI meets a race for the first time - Should the AI's ship immediately attack that race's undefended colony? A hostile AI race could be set to a 75% chance of doing so, while a less hostile one might only be 25% likely to do so. Certainly you'd hope such decisions were made in a more informed manner, but for smaller decisions, randomness can keep the game more varied.

There's all sorts of other possibilities for what the AI can do, but that's a few anyway.

2) The main power of chess-type AI's is that they use their computing power to essentially "look into the future" to see the results of the moves they are considering to make. So basically, for some or all of its potential moves, it guesses what it's opponent's best counter-moves to those moves would be, then it picks its best moves in response to those, and then the opponent's, etc. Each level of forward-looking is called a "ply". Picture a tree with, say, 20 branches on the trunk, and each branch having then having 20 sub-branches, and each sub-branch having 30 sub-sub-branches, etc. As it moves into future turns (moves up a branch level), if it sees the situation turn bad, it rejects that move and looks for an alternate one (thus "pruning" that branch and following a different one). Once it has picked out what it thinks is its best move, it may then analyze that one move a few plys further along to try to make sure there was't bad news lurking over its horizon.

As you can see, in a game like chess, the number of possible branches can quickly become impossible huge after even a small number of plys, so some tricks are done to thin the number of branches to analyze out, such as by not analyzing all possible moves, but only the ones it deems best. Another way to thin the branches is that chess AI's are also scripted, in a way. They usually have "opening libraries" and "closing libraries" that basically let the AI recognize tried-and-true beginning and end game situations and know the optimal responses to them.

This kind of forward-looking AI can be very effective, and in certain simple types of games, it can be "perfect" - in other words, it is able to analyze all possible moves so that in a "fair" game, it can guarantee a victory or at least a tie. A tic-tac-toe AI could be perfect in this manner. (Perhaps even a checkers one - I'm not sure about that, though).

For a vastly more complex game like SEIV, though, it is pretty much impossible to do this sort of forward-looking in any kind of effective way to make it practical for an AI to use that approach.

Well, I hope that all made sense and was of some interest to someone! :-)

[Daynarr]

Thanks LintMan. This is interesting stuff and I am sure lots of people who read it will better understand how AI works.

[This message has been edited by Daynarr (edited 22 December 2000).]

[Courageous]

This may surprise you, but the field of "aritificial intelligence" is perhaps the most misnamed field in all of computer science. Most of the time, classical AI is about "search" algorithms of various kinds. Some game "AI" (sic) programmers are well-versed in this subject matter, but many are not. It's genuinely difficult stuff, generally only studied in detail in graduate school. Few game programmers ever made it that far, so often they use templatized distillations of the various algorithms, pathfinding being the most common one.

To get a glimmer of how difficult it might be to write game AI, ask yourself -- as a player -- which warp points do I have to defend to defend my entire empire? As a human, you can answer in a split second -- in fact it is likely that your expansion policy is based on keeping the number of entry points to your empire few in order to create the highest concentrations of defensive forces at those entry points.

This is a trivial task that you've done in a dozen similar games. And you know what? It's hard. Really hard.

C//

[Taqwus]

Agreed. SE4 is far more complicated than chess (which machines can do pretty well at), and even Go (which, to my knowledge, machines do not yet do well at). Checkers, IIRC, a comparably simple game (at most... 24 pieces IIRC, on 32 squares with fairly limited branching factor) has actually been solved, 'tho.

FWIW, chess has also been studied for a FAR longer time than SE4 :;, so there's a huge body of expert knowledge for an AI creator to use.

1. Hidden information. This is a biggie. If it plays by the same rules as the human player, normally the AI will not have minimal information about what's on your planets, what's in your ships, where your ships are, how damaged they are, and so forth.

2. Flexible rules. That is, the very customizability of SE4 is going to make it difficult for an AI to do well, since such things as the tech tree and galaxy characteristics can be altered dramatically. Ergo, the limited scripting ability for tech research, etc.

3. *More* pieces and more states. Chess has, at any one time, no more than 32 pieces on the board. Even Go has only 361 intersections, each of which has only three possible states -- occupied by a white stone, occupied by a black stone, or empty. SE4 can involve hundreds of fleets with individual ships, all of whose state matters. Don't bother trying to build a complete state-transition diagram, or even going out to a couple of ply.

4. The sheer number of options. This goes along with the previous three; players can go absolutely crazy with a basically unbounded number of distinct possible turns.


So, at least the strategy layer is going to be rather difficult. The tactical layer may be easier to program, since

a) there is no hidden information anymore,
b) there are fewer participants usually,
c) there are fewer options
d) certain things like seeker pursuit appear to be completely deterministic (e.g. if you know who is a missile's target -- say, because only one of your vessels was in range of the missile launcher -- you can determine its exact trajectory based on the locations of the missile and its target).

I'd be more tolerant of the AI "breaking the rules", at least mildly (some info cheats, as long as they were 'declared'; perhaps production bonuses, etc, but pref. nothing too outrageous like not needing minerals at all), than of blatant tactical combat hacks (bonus speed, say, or bonus damage) for these reasons.

------------------
-- The thing that goes bump in the night