Wanted: Cheating AI

[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

[Courageous]

"Checkers, IIRC, a comparably simple game (at most... 24 pieces IIRC, on 32 squares with fairly limited branching factor) has actually been solved, 'tho."
----
Right. It's worthy of note to observe that even if we could represent a game like SEIV correctly using classical search (given the complexities and configurational flexibility, this is in doubt), it would actually be IMPOSSIBLE with today's hardware to solve the SEIV AI (or similar) problem using the same kinds of techniques which are used for Chess, Go, and Checkers. The combinatorial expansion is simply enormous.

As for Ben and Imp II, congratulations. I believe you pulled off an outstanding solution to computer "AI," and while I often had to play that game on easy, that's the way it should be.

Oh, BTW: CHEATER!!!

C//

[Courageous]

Oh, by the way, my only real complaint regarding Imperialism II was not the AI, but the way that it became nearly impossible to bust cities in the late game. That was frustrating; you should have had a siege model or something.

C//

[Talenn]

Ben Polk:

Imperialism II has to be one of my favorite games of all times simply BECAUSE the AI was so challenging! I LOVED the way it did the 'dog pile on the rabbit' if you were the weakest. And the best part is that it seemed to jump on the weakest regardless if it was a Human or AI controled nation...as it should be. Boy did it ever suck to be even perceived as having the weakest military... All the nation of Europe were like a pack of wild dogs smelling fresh meat!

I tend to agree with Courageous on the late game though. It did become a bit tedious reducing forts but overall its still one of the best games every published IMO. I've often cited I2's AI as the best AI in a PC game specifically because it DID appear to be playing by the same rules a human player (with a few exceptions).

Now if only you guys had allowed for tactical combat in multiplayer games....

Talenn