Wanted: Cheating AI

[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

[benp]

quote:

---

Originally posted by Courageous:

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 ***.

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

---

Different people have different opinions about this, ranging from "the AI should not cheat at all", through, "it can cheat if you can't tell", to "do whatever you have to to give a challenge".

When we did the AI for Imperialism II we took roughly the middle choice above. It wasn't because we were lazy, it was because we didn't want to make a game that was easy for an experienced strategy game player to beat after a couple of tries. (Although I'm afraid we went a bit overboard on the difficulty.)

Our determination of what was an acceptable "cheat" was based on our belief that it was important that it feel like the AI is playing the same game as the human. We ended up with few information related cheats, but not global knowledge about what the human is doing. For example, the AI knows what units the human has in each place, but does not know what moves the human has entered for those units for the following turn.

I prefer this kind of limited cheating because I've never seen a game without it that can give me much of a challenge, but many others disagree with me.

Ben Polk