Why AI is so weak?

[Xerol]

Didn't read the thread in too much detail, being on a limited internet time schedule I just skimmed it...but here's a point:
On the first move of chess, there are only 18 possible moves. When black first moves, he's got 18 choices as well, making the total number of "after first turn" possiblities 18*18 = 284.

Now look at civ3(assume 100x100 map, 7 opponents for 8 civs total):
First of all, the total number of opening "moves" is 16 for a non-expansionist Civ, and 24 for an expansionist, barring a coastal start, plus you have to include non-moving moves, so, the settler can build a city or move, 9 moves total, and the worker can move, build road, mine, (irrigate if near water). For up to 11 moves, although it's probably ten. So, for just one civ, after the first turn there's 90 or 99 possible starts. Let's round this up to 100 for simplicity.
Now, there's 7 other civs, so the total "after first turn" positions is 100^8 = 10^16 = a whole ****ing lot.

And THEN you have to decide which tile to work in your city(if you decided to settle) what tech to research and at what rate, etc etc etc. Overall, depending on which civ traits that a civ has, there's at least 10,000 possible different "starting positions" per AI civ. Keep in mind that although a lot of these are not feasible, the computer still has to spend some time sorting those out and choosing between the rest.

And I didn't even get into looking ahead, which the AI doesn't seem to do currently. But analysing just the current position takes an awful long time as it is, so in order for the AI to become "smarter", even by looking ahead just one turn, would probably slow turns down by a factor of hundreds, if not thousands or millions.

So, in conclusion, in order for the AI to get "smarter", it's not possible to do it with today's technology in a reasonable amount of time.

 

[SuperMA5TER]

Well there is a very nice discussion going on in here but i think it is going a little off-topic. The topic, as started by akot was, why AI is so weak. Not "Differences between chess or civ3" or "Which is more complex? Chess or Civ3". I'm don't mean to anger anyone out there, just wanted to say that the chess vs civ3 discussion needs another topic.

Now i come to the current topic.

First of all many have said that programming a good Ai would take too much time on a low-end system. I think thats not a very big problem. The easy solution is to provide users with high speed machines with a unique difficulty level, like Ultimate (just a name), that is available only on pcs with at least 1.7GHZ pentium and 256 MB ram. The low end users could still play the other difficulity levels which r already in civ3. This way there will be no cut-off in sales.

Then if the SMART AI is really that hard to progam, they should consider making ai smart in small, focused sections of the game. like city placements, battles or diplomacy. out of these i think diplomacy is the one easiest to make smarter. In civ3 i usually beat the diplomacy down to its knees. for example, in one game i was on continent A. I saw two civs figthing each other on continent B. Alling with one of them againt the other, i took huge benefits like techs, gold etc with no threat from the enemy cuz at that time sea warfare was nearly impossible. I never even participated in the war. That shows how dumb the ai is on diplomacy and military.
Improving this should be easy. Just have the ai check will the ally be able to take part in the war or not. Or if possible, introduce a new "Demand Units" options in diplomacy if u see that ur ally is not taking part in the war.

As said by many others. the ai is pretty good in military aspect but it still needs some improvements like effectively using the bombarding ability and taking up key positions in a battle and upgrading units constantly. All this, needs not a SuperMA5TER of programming.

DAN said that programming an AI that always beats human is possible to build at least theoratically. i beg to disagreee. human beings are really masterminds out there in the world and even if no one is winning a chess game against a super computer, doesn't mean no one can. Also the example he gave (of pong) is absolutely unconvincing since pong is not a strategy game by any means.

I good example of a good ai (no offence meant for soney or firaxis or any other) is galactic civilizations. The game isn't too deep as civ3 but its ai is really challenging. it gets alerted when u start delploying military units near borders or bases and it changes its starategy accordingly. like shifting its research path on defensive style(if it is weaker) or like starting to work on protections pacts with other civs just in case u attack them. BTW i like civ3 a lot lot lot more than gc still cuz it has so much gameplay and things that gv doesn't. Just want the ai to be at least as good as in gc

 

[akots]

Originally posted by QwertySoft
... And I didn't even get into looking ahead, which the AI doesn't seem to do currently. But analysing just the current position takes an awful long time as it is, so in order for the AI to become "smarter", even by looking ahead just one turn, would probably slow turns down by a factor of hundreds, if not thousands or millions. ...

I beg to disagree with you and agree with Supermaster's following post.

For example, AI decided to build a wonder. By having embassies with other Civ who are also building that wonder, the AI can easily check how these other cities are doing. Then a human player would try to balance this city growth to maximize shield production and coordinate this with worker movement and improvement. What is so complicated about this? Absolutely nothing. Just simple optimization trend problem with easy algebraic equation. Then, AI would think whether it can beat the other civs considering that these civs would use the same tactics in cities wich build their wonders. The main issue is that the current AI is not even bothered to try to do this. Certainly, if AI can beat the opponents, it is better to have a peaceful time because during the war, some GLs can appear. On the other hand, if AI cannot beat the opponent and is militaristic, it can try to start a war aiming to produce a GL. I personally always try to use this tactics and build Pyramids early in the game. WIth Pyramids the player has HUGE advantage in population growth and the game is essentially done even on higher levels. Is this problem complicated? Certainly not! Is it crucial for the game? Absolutely yes!

With chess programmimg, "brute force" is no longer important. "Brute force" is a feature of some 10-year-old soft like Chessmaster 5000. It cannot be efficiently used unless the game is possible to solve completely which is not yet possible. With Civ3 it would not be possible at all because of variable chance-luck random component. Also, as I have written earlier, there is no point to validate and evaluate the consequences of every given move because Civ3 is not lost or won in a single move or build. One can agrue about diplo victory but it really takes a lot of effort and is actually rarely possible at all. probably this is even more true in a multiplayer game. The trick is to improve the AI tactics by making it more flexible without human being hadicapped that much on higher difficulty levels which is completely unfair.

 

[akots]

Originally posted by Dan Magaha FIRAXIS

... in theory, at least, writing game AI that can always win is a lot easier than writing game AI that puts up a good fight but sometimes loses. ...

With regard to this comment, I would say a couple of words about Conquest expansion. Again repeating, that Firaxis has created the best product of Civ series and probably the game of the games.

As I understood, the Conquest aims to more complicated rules and variable tech trees. This certainly adds more historical accuracy and should greatly improve the educational value of the game. Which ia already extremely high. But really, to master something, you have to learn from somebody-something stronger that you are. Many people don't like to lose but most understand that unless you lose you don't learn. After playing ping-pong with PC for a couple of days, one can easily beat any human because this dramatically improves the playing skill.

However, Civ3 is a lot different. The rules are fairly complicated but still possible to comprehend and hold them in the head every time the game is played. And because it is a turn-based strategy, human has enough time to think. And repeating again, people would only benefit from some AI that would beat them all the time which I personally doubt is possible in such a complex game. As for now, the Civ3 AI is too dumb to be considered a serious opponent.

 

[Smidlee]

something that is stated in Civ 3 ptw strategy guide(i took a look at it before in the store) is the AI doesnt play to win unlike humans . when i play i play to win either in sp or mp . even in chess this is true . the AI doesnt know the difference between winning or losing positions, it will play the same (unless iit's program otherwise). I have to admit i lose my first game of civ 3 ,civ 2 ,and galactic civilizations . but after a few games i can find holes in any AI because i learned but the AI stays the same. even galactic civilizations has expliots i found i can use againest the AI . BUT AI will never find expliots in a game .
i would recommand everyone try Carnage Heart on the playstation . it this game you learn how the make simple AI programs for your Mechs and watch them in battle . I have a little more understand about AI programming since i play that game .the game makes programing simple by useing program chip that you place on your motherboard of your Mechs(in CH they r called OKE). i first thought this would be easy until i put my OKE to the test . it took me a while to finnally programing an average AI that could hold they own on the batlefield .... So i can understand it would be tough to make a strong AI without cheating or extra bonuses. hopely Conquest AI will have some improvement that makes the AI itself more challenging with it's SID level. but in my opinion Civ 3 has a very good AI compare to others games .ps. i like the AI in Gal Civ too but for different reasons. in Gal Civ Diplomacy is a lot better but the combat isnt as balance as CIV 3. the five different AI is very fun and interesting in Gal Civ.

 

[anarres]

akots,

I skimmed the thread quickly, and the main thing that leaps out at me about your argument is that you think that Chess has less complexity than Civ.

I'm not sure what your background is, but you certainly seem to know something about Chess. All I can say is that you can't have any real understanding of Mathematics or programming. I thought about arguing with you about it, but unless you really want to learn about what Complexity is (in a mathematical sense), there is little point. The thrust of this is that you have it wrong. Civ is much more complex than Chess, a number of times more complex.

As complexity increases the computation time increases exponentially, the AI intellignece is actually quite an acheivement that it can do anything at all.

One of the most difficult things to program an AI for games like Civ is focus. The AI plays a very balanced game, if it tried to play any other way it would fare very badly, and this is something I can live with, understanding the nature of how hard these things are to program.

The main area I can see improvements in AI behaviour is managing food/production better in cities, as Last Conformist says, having 13spt will take the same amount of time to build a spearman as having 10spt would (and yes I know build costs are different for the AI ).

I guess you need to understand more what goes in to AI programming, and maybe more importantly what Complexity really is. Unless you are willing to do that you will not understand why the AI 'behaves' the way it does...

 

[Norlamand]

Great discussion. I agree that the AI could stand some improvement, but I understand the practical considerations that come into play. It would seem to be all about the number of variables in each game. Chess clearly has a finite number of variables (only 6 unit types, 64 possible spaces to occupy, etc) that the computer has to contend with. Even a simple civ game (tiny world with 2 civs barbarians off etc) has significantly more variables that must each be independantly considered. As the chess game progresses the number of variables remains relatively stable, while in a civ game the number expands constantly with time. For even a powerful workstation to attend to each variable with the same attention that a top of the line chess AI would the game would quickly bog down to an unacceptable pace for enjoyable play. As it is the game can be intolerably slow in the late part of games with a huge world and many civs. Its a $#itty little AI but its the only one we got, to paraphrase a ripped line.

 

[SolarFlare]

Originally posted by Norlamand
Chess clearly has a finite number of variables (only 6 unit types, 64 possible spaces to occupy, etc) that the computer has to contend with.

Chess may be a game of the finite, but with today's computing standards, we've got a long while to go before it can be handled that way.

[edit: long long long while]

 

[Bigfoot]

Originally posted by anarres
akots,

I skimmed the thread quickly, and the main thing that leaps out at me about your argument is that you think that Chess has less complexity than Civ.

I'm not sure what your background is, but you certainly seem to know something about Chess. All I can say is that you can't have any real understanding of Mathematics or programming. I thought about arguing with you about it, but unless you really want to learn about what Complexity is (in a mathematical sense), there is little point. The thrust of this is that you have it wrong. Civ is much more complex than Chess, a number of times more complex.

As complexity increases the computation time increases exponentially, the AI intellignece is actually quite an acheivement that it can do anything at all.

One of the most difficult things to program an AI for games like Civ is focus. The AI plays a very balanced game, if it tried to play any other way it would fare very badly, and this is something I can live with, understanding the nature of how hard these things are to program.

The main area I can see improvements in AI behaviour is managing food/production better in cities, as Last Conformist says, having 13spt will take the same amount of time to build a spearman as having 10spt would (and yes I know build costs are different for the AI ).

I guess you need to understand more what goes in to AI programming, and maybe more importantly what Complexity really is. Unless you are willing to do that you will not understand why the AI 'behaves' the way it does...

Anares,

I can see why Civ is more complex than chess, at least from a 'brute force' programming standpoint. But I think most people who play both games would agree that chess is by far the harder game to master. It takes most people years to achieve anything like a master chess rating, and in fact only a minority of dedicated chess players ever achieve that rank. By contrast most Civ III enthusiasts can use the tips on this site to beat the AI, even on the highest levels.

Is this merely a paradox? Or are there other (non-brute force) programming approaches that could be applied? It seems to me that there are subtler programming designs that could give the AI a more coordinated approach to the game (IE to make more 'strategic' decisions).

(BTW, I think the current AI does a remarkable job. Just curious if an alternative approach could be applied.)

 

[AlanH]

Originally posted by bigfoot
But I think most people who play both games would agree that chess is by far the harder game to master. It takes most people years to achieve anything like a master chess rating, and in fact only a minority of dedicated chess players ever achieve that rank. By contrast most Civ III enthusiasts can use the tips on this site to beat the AI, even on the highest levels.

You are comparing two entirely different achievement standards. Chess Masters achieve their rankings as a result of competition with other chess Masters, so they are learning to play at or near the highest (known) levels of performance. A CivIII player who can beat the AI has learnt to do .... just that. A good performance against the AI is no indication of how well a player would do in a multi-player game.

The AI has had maybe half a dozen opportunities to improve its game since it was first released? And the AI's objective is to give lots of paying customers a good time. Humans improve every time they play, and aren't trying to entertain the computer.

This thread is very interesting, but it seems to be all about the fact that the AI doesn't present the sort of challenge that 16 or 24 human opponents would offer. But isn't that what PTW is all about?

Originally posted by bigfoot
Is this merely a paradox? Or are there other (non-brute force) programming approaches that could be applied? It seems to me that there are subtler programming designs that could give the AI a more coordinated approach to the game (IE to make more 'strategic' decisions).

Humans are good at subtle strategic thinking, recognising patterns and responding to them and myriad other complex thought processes we still don't understand.

Computers are good at counting, and that's all chess programs do. The basic chess program structure has NOT changed in ten years, just the implementation details and the hardware performance and the sizes of the opening and end game lookup tables and such. They still "calculate" a strategy by selecting the sequence of moves with the best outcome they can find out of all the possible sequences they can calculate in the time available. To do those same brute force counting tricks in CivIII, as Anarres has said, would simply cost too much computing time.

No one has yet programmed a computer to think about game strategy the way a Grand Master does, so I doubt that a progrramming team in Firaxis is going to make a breakthrough that has eluded the finest minds in AI research.

 

[SirPleb]

I just read through this thread and want to add my two bits.

I think I'm fairly well qualified to talk about this. I consider myself a better programmer than I am a Civ3 player, and I'm not bad at Civ. I've written a few programs which would qualify as AIs.

First, although I agree it is a bit off-topic, about Civ3 vs. Chess: There really isn't much comparison here. The techniques used by most Chess programs (and I think all of the good ones) are essentially mini-max tree search algorithms, with lots of fancy pruning to allow deeper searches. This technique can't be applied to Civ3. As others have described eloquently already on this thread, the exponential nature of a tree search approach, combined with the number of choices one can make in a turn of Civ3 result in an insane number of moves to be evaluated. Applying a tree search approach to a Civ3 AI would result in move times longer than the expected life of our sun Note that all this has nothing to do with "complexity". The game of Go is at heart simpler than Chess but it also resists any tree search based attempt to build a good AI - it has too many choices at each turn for a tree search approach to be reasonable. Bottom line: The work done on Chess AIs is largely inapplicable to an AI for Civ3.

Can the AI ever out-play the best human players on a level playing field? (No cheats or advantages for the AI.) In this particular game I very much doubt it. There are too many factors intertwined. The Civ3 AI must of necessity be a large (relative to games such as Chess or Go) set of rules of thumb which evaluate and control many aspects of the game. The human brain's pattern recognition abilities reign supreme in this arena for the forseeable future. Computer programs to date can be made to tree-search, they can be made to learn to some degree, and they can do limited pattern recognition. With the huge number of variables coming into play in a Civ map these techniques can not offset the human brain's pattern recognition abilities.

It seems to me that a number of things have been done superbly in the existing AI. An example is the use of weighted random numbers to choose between actions such as exploration direction and next tech to research. The combination of rule of thumb weightings with a random element in the final choice makes the AI less predictable in these areas, resulting in more feel that it is intelligent, and thus resulting in better replayability.

Can the AI be improved? I believe it can, without a huge amount of work. And I don't think it is yet anywhere near the stage of sophistication where computing power is a factor. Many things could still be done to improve it which wouldn't have a perceptible impact on its response time. I think a few man-months of programming could raise the AI at least one level, i.e. make it as hard to play against with no bonuses as it currently is when playing it at Monarch. And I think Firaxis knows all this. It really comes down to a commercial decision for them. At the end I think they have to boil it down to a question like "would this result in selling an additional 20,000 units?" And that of course is their call

 

[Smidlee]

comparing Civ 3 to chess isnt off the subject . when someone calls Civ 3 AI weak is must be compared to a strong AI to ask why it's weak. the only game i know where a AI can play a human on even ground is Chess . can anyone name another? without comparing it to chess ,How can someone say CIV 3 AI is weak . of course even a good AI has room to improve which i hope they do in Conquest . if you compare any AI againest a human brain (even in chess ) in time the AI will lose . i learned even in a strong Chess program that if i can hold my own until the endgame i can draw and sometimes beat the AI .( i havent played any of the new Chess lately with my new PC . ) the fact is if i'm beat by the AI it has to be in the beginning of the game ,for as the game goes on and i can hold my own i will almost always win (in chess atleast draw) the game . so probably the Conquest Sid level will try to take you out in the beginning of the game where the AI's has the best chance of winning . p.s notice the most of the time Civ 3 AI will leave you alone in the beginning of the game when you r the weakest . play any MP games you better be ready for war in the very start .

 

[SolarFlare]

There's a difference between Civ early game and Chess early game. In chess one of the characteristics of the game is that it's a free-info game; i.e. even in the opening everything your opponent does affects your next move. In civ, you can go a very long time without being affected by AI early moves. Therefore early game is not as important as, say, mid game. Unfortunately, this is where the AI struggles most.

 

[SuperMA5TER]

SirPleb! You r absolutely right.

The AI algorithms applied in chess (Mainly brute force) are simply not applicable to Civ3.

Then whats the solution?

I presented one before (not much clearly i think) as well. Right now i shall elaborate that in an understandable manner.

The AI in civ should act randomly or at least how it acts in the present civ games when there isn't any Big Thing happening anywhere near it. However, it (AI) should periodically (and intelligently) respond to some big and small events. As soon as these events show up, AI should made a decision about its future stategy based on the current cirumstances. Example of such events may include;

1) Any known civ initiating or completing a great wonder. At this event the ai should decide what strategic benefits the builder civ would get from this wonder. It should remeber them for any upcoming battles against that civ. Moreover, it should spend some money to inspect the city in which the wonder was built (through espionage) and see how many shields that city is producing. Then if none of his own cities is producing that much shields it should manage one automatically so as to make building of such wonders possible.

2) Forming a new city. On it, the possible decisions r, like how much chances r there for the city to flip to another culture(if it is near to border of another civ then the chances r high and increase with time). if the chances r high, it should build cultural improvements more than other improvements in that city.

3) Anyone other civ forming a new city. Ai should calculate how far the opponent is from achieving a domination victory. If its is near then act accordingly.

4) Two civ signing mutual protection pact.
5) Any civ deploying troops near borders.
and so on(The list won't be very large)

The suggested actions are just a suggestion (not to be taken seriously). A better method would be to make ai take those actions, which a civ master gamer would have taken on such events taking place.

I think it is the only workable AI model that is applicable to civ3 games. It might already be based on it, but if it is, it takes the actions that a dumb (or nearly) gamer would have taken. too bad!

Sirpleb! there is one point i disagree with u on
The ai selecting randomly the next tech to research is one of the main reasons why ai is weak in this game. See my post before this one with refrence to galactiv civs to see why i think so.

 

[akots]

Originally posted by SirPleb
... I think I'm fairly well qualified to talk about this. I consider myself a better programmer than I am a Civ3 player, and I'm not bad at Civ. I've written a few programs which would qualify as AIs.
...Can the AI ever out-play the best human players on a level playing field? (No cheats or advantages for the AI.) In this particular game I very much doubt it. ...
Can the AI be improved? I believe it can, without a huge amount of work. And I don't think it is yet anywhere near the stage of sophistication where computing power is a factor. ...

Surely that is the point of the problem. Since SirPleb is one of the best players around here, the opinion should be at least respected. And the AI already has a huge advantage due to its calculator properties. For example, in chess, especially the games of human players played in public, the players always make rough mistakes. It is not uncommon for a grandmaster to give away a pawn or even a knight or a bishop to another player just because humans make mistakes. Since in Civ3 there are many units to move, probability of these mistakes made by a human is greatly increased. And don't forget these slippery old mice. Even though gotm you can play at home in a quiet house (makes player annoyed) with full stomach (makes player sleepy), still a common oversight is a huge factor. This can at least partially compensate for the lack of sophisticated AI.

May be Firaxis needs a sponsor? May be some grant from some department (of Defence) or big company? Lots of chess-programming efforts were funded by big companies like IBM as well as private sponsors who liked the game and wanted to know whether the AI can beat a world champion.

Certainly, one can say: Play the multiplayer.

 

[Qitai]

Originally posted by anarres
The main area I can see improvements in AI behaviour is managing food/production better in cities, as Last Conformist says, having 13spt will take the same amount of time to build a spearman as having 10spt would (and yes I know build costs are different for the AI ).

My biggest unhapiness about this game. Why can't we just have shields and food roll over to the next production? And then, this will not become an issue at all.

 

[SolarFlare]

Originally posted by Qitai
My biggest unhapiness about this game. Why can't we just have shields and food roll over to the next production? And then, this will not become an issue at all.

Because we know that in real life, every city improvement is always completed on December 31st of some year. Duh.

 

[The Last Conformist]

Qitai; gotta agree on that point.

'Nother point: The AI have obviously been taught how to launch an amphibious invasion. We complain about how pathetically it fails in this regard, but it's got the basics right - load troops into a transport, drop off next to target, and attack. That it almost invariably fails is due to its failure to apply any concentration of force in this circumstance; surely this must be relatively easy to fix?

 

[SolarFlare]

Well, as with any "fix," you have to think about versatility. One of the reasons someone could site as showing that the Civ3 AI is great is its ability to play correctly in mods. You can't just say "attack like that, only more." There's a lot that goes into a command like that.

 

[Qitai]

Just to put in a logic like this - attack a city only if it has enough forces to actually take it in a turn. Enough can be define by Sum of Attack*Hitpoint > Sum of defenders defense*hitpoint. And yes, this would be another AI cheating having know the numbers. But I wouldn't mind this.