Why AI is so weak?

[akots]

Originally posted by The Last Conformist
There's also the issue of computing time. Top-end chess programmes think for hours about moving one piece. In Civ we complain if the AI takes five minutes to move hundreds of pieces. For people to play a game like Civ, it must run reasonably fast. A chess computer can analyze every possible move from a given situation, and explore many avenues of possible further moves quite a few rounds into the future. For the Civ AI, doing this would take essentially forever. On top of which Civ contains an element of de facto chance - while the RNG isn't technically random, the AI does not know what it's going to come up with any more than the human player. Given this, the infamously predictible scripted responses and the algorithmic identification of city locations are hardly to be avoided.

As for monetary resources, huge amounts of money have been spent on things like Deep Blue. Designing a chess AI, but not a Civ one, is seen as a mainstream AI research/compsci task.

By no means I am an expert in chess programming. I just have read some literature about it. There were several problems at the very beginning in the 1960s-70s.

First and major problem was how to evaluate a position. In another words, are you more close to the victory in a new position or not and how to measure this distance from a victory. In Civ3 this is solved pretty straightforward. How close you are to building a spaceship? Evident. How close you are to domination? Evident. How close you are to conquest? Evident. How close you are to cultural victory? Evident. How close you are to diplomatic victory? Evident. Everything is easily expressed in numbers. Thus, there is no problem of evaluation of position for AI. Everything is easily expressed in numbers. The more tiles you owe the closer you are to domination. The less military and cities your opponents have the closer your are to conquest. Etc. Thus, this problem is already solved.

Second problem was how to predict the moves of the opponent. In chess, there are not that many moves, thus, AI goes straightforward and analyzes all moves discarding those which will lose a lot of position point for the opponent as low probability possibility not worth analyzing. Well, with chess it is possible to lose by making one incorrect move. With Civ3 losing is more difficult. It takes several series of serious mistakes. And again, Civ3 AI is not that hopeless. It reacts to your moves trying to predict what you are going for. It is reacting somehow but not choosing the optimal pathway in most cases. Which cases, when, and how, that is what I wanted to understand.

Third, computing power. Certainly, it takes some time for AI to make a decision. How long? I can certainly wait for AI for 10-20 minutes to make a turn on a standard map. Now it takes less than 1 min on my 1.3 GHz Athlon with 128 Mb memory. Again, with chess programs, the problem was how to manage the virtual memory and clean it up efficiently after the decision is made. Without extensive virtual memory usage, this task is impossible. Civ3 AI however, as I noticed, never uses virtual memory. For example, to defeat the opponent who has 5 fortified spearmen defending a city AI has to build 10 swordsmen within next 5 turns. However, opponent can build roughly 3 spearmen during these 5 turns and thus, AI has to build and transport to that city lets say 16 swordsmen within next 8 turns to have reasonable chances of capturing the city. On the other hand the opponent can be researching Feudalism and has barracks in that city. After 8 turns, the swordsman might come to fight with 8 fortified pikemen instead of spearmen. Thus, it would be better not to build the swordsmen at all but build horsemen and then wait until Chivalry is discovered, upgrade horsemen to knights and then attack these pikemen. Certainly, some time is necessary to make this complicated decision. After the decision is made, write it down in virtual memory. Then, make another decision regarding so other issues like what to trade to whom and fro what price or what to build in which city and which tile to work depending on what is optimal for improving the situation. Then, analyze all individual decisions for contradictions, correct if necessary, make the budget, predict opponent strategy, analyze whether the situation would improve regarding the progress towards a win. If it does, good, write everything down. Then, try some other approach. For example, attack another city or make a peace or wage another war, etc. In each case record the key decisions. Then, compare progress towards victory in every case. Choose whatever is more efficient and go for it. Plain simple. With normal map should not take that long I assume. The software just has to manage the memory properly and clean it up which any accurately written bug-free software should be able to do reasonably well.

With chess, probability is also a big issue probably until 1000 GHz PC is around. There are just too many variations to calculate within a reasonable time to completely solve the game. And Deep Blue team consumed lots of resources because they used expensive hardware. BTW, they started about 10 years ago and at that time 100 PentiumPro 200 were really expensive. Well, it was a big and extremely inefficient Cray superpower. Which is now easily beaten by any normal PC.

All I wanted to say is that it is known how to make a good AI because strong chess AI is a good model for any strong AI. In RTS you have the time limit, whereas in turn-based strategy, time is of minor importance. Just take the chess AI model and adapt it for Civ3 rules and units and strategies. And again, DeepBlue and any other serious chess AI builders used grandmasters for help not only during testing but also during writing how the AI makes the key decisions. Because only a strong player knows which decisions should be optimal and how they can be reached. An algorithm of looking for a decision is very important.

 

[akots]

Originally posted by Gengis Khan


LOL!! Well that would be hundreds wouldn't it??

I wanted to say a thousand, but I'm too lazy to look up the exact date(which probably isn't known). And I didn't want some smart-@ss coming back and saying it was invented 998 years ago not 1k

Well, to tell the truth, chess as a game known to the modern world with modern rules is less than 400 years old. That game which was described 1500 years ago has similar idea but really, these rules make a BIG difference. It is like Civ1, Civ2, and Civ3.

 

[Padma]

Chess is a game with simple rules (I will not deny its strategic complexity, however). You have a board consisitng of 64 identical squares. You have 16 "units" of 6 different types, on each side. Each type of unit can move in certain explicit ways. There is only one opponent, and one "Victory COndition". Much of the strategy in chess involves "thinking ahead": what is my opponent likely to do in response to this move? What should I do in response to that? etc. The further ahead the AI can "think", the more optimal its movement choices.

Civ3 has a much more complex ruleset: The "board" can range in size up to 360x360. Each square can be any of 9 possible basic types, with modifications possible (e.g., jungle, forest, resources). The number of unit types is huge, and more types can be added, if desired. The number of units each player has is variable, and grows from a minimum start of 2 to any size up to a max of 4096 units total in the game (And may be reduced as well, all the way down to zero when the game is lost). The number of opponents is variable; anywhere from zero to 32. There are currently 6 possible victory conditions. While all units can move in any direction, there are constraints based on the type of square moved to, and whether or not movement-enhancing overlays (i.e., roads) are present.

Assume a 32-civ game played on a 360x360 map. Allow each civ 100 units. For each unit, the AI would have to contemplate the possible reactionary moves of 3100 other units. It would have to do this for each direction each unit can move, and for each possible number of sqares moved, up to its max movement allowance. There are some "moves" that can be ignored as obvious "position-detracting", such as disbanding, but if you are not engaged in warfare, how do you determine if a move detracts, and can be discarded?

Which victory condition should the AI pursue? I agree Domination is a pretty straight-forward calculation. Conquest, pretty much so, also. Cultural, maybe a little more difficult, but not a lot. Histograph - yeah, that's just straightforward score. Spaceship, well, you know where you are, but how far along are the other Civs? Diplomatic ... How the heck do you determine how close you are to diplomatic victory? Say you are just a couple turns from builing the UN, and are on Gracious terms with most of the other civs. Then some fool starts a war, and you get dragged into it via MPP, etc., and half your "friends" are now furious with you. You just went from "almost there" to "a long way off". And which VC should a given AI civ pursue? Obviously it must make the decision each turn, based on the optimal path at that time.

You said you "can certainly wait for AI for 10-20 minutes to make a turn on a standard map". I think, looking at the whole situation, that you are being optimistic with your calculations. I wouldn't be surprised at 3 - 5 minutes per AI Civ in the late game. Not many of us here would be willing to do that. Look at the howls of rage when it was found that playing a Huge map, with 16+, civs resulted in waiting over five minutes! And that is with the *simple* AI we have now! And that is with 1Gig and faster processors. Now, how about designing this AI to run on a 486, with 128M RAM. That is not an uncommon system for these games to be played on. How many hours are you willing to wait between turns?

 

[SolarFlare]

Originally posted by akots
In chess, there are not that many moves

You're missing something here. There are "not that many moves" for any given movement, but each turn doesn't take into account just that turn alone (how often have you seen a grandmaster move a queen to a square where he will lose it? Never, because you've probably never seen a grandmaster play, it would bore you to death, but that's not the point ). Each move takes into account many of the next moves. Imagine there are only 50 possible moves for each player. To think just two turns ahead, that's {this move, opp. move, next move, opp. next move, 2 moves ahead, opp. 2 moves ahead} = 50^6 possibilities = 15625000000. A move cannot be disregarded because it looks like a bad move; there are such things as sacrifices.

Originally posted by Padma
There is only one opponent, and one "Victory COndition".

I beg to differ. A good player knows when to go for the win and when to play for a draw. That makes two victory conditions right there. Within "draw" there are several ways for that possibility to arise, which I will refrain from listing here.

 

[The Last Conformist]

I cannot see how telling how close to a Conquest win is reasonably straightforward, unless you've just parked 200 MA outside the last enemy city. Evaluating how good your present situation is in the middle of a major war is not trivial, especially not when, thanks to military alliances, a 3-1 numberic advantage can be reversed instantly.

 

[Padma]

Originally posted by SolarFlare
I beg to differ. A good player knows when to go for the win and when to play for a draw. That makes two victory conditions right there. Within "draw" there are several ways for that possibility to arise, which I will refrain from listing here.

I thought about that before I posted, but a "draw" is not a win.

Originally posted by The Last Conformist
I cannot see how telling how close to a Conquest win is reasonably straightforward

You are quite right. Until you have that 200 MA parked outside the last enemy city, the best you can do is calculate relative troop strengths and number of cities, and come up with a "Well, Conquest appears possible, at this point in time" position.

 

[SolarFlare]

Originally posted by Padma
I thought about that before I posted, but a "draw" is not a win.

If you want to get technical, it's an objective. It is an outcome that an AI will strive to achieve or avoid, depending on the situation. In that sense, it is quite signifigant no matter what word you use to describe it.

 

[Dan Magaha FIRAXIS]

A few points to make here. First a disclaimer. I'm not a programmer. I'm sure Soren could comment more eloquently on this topic, but he's out of the office at the moment. With that said:

1) We are an independent developer, so any discussion of Infogrames/Atari's financials is really irrelevant to the topic of whether a game company has the resources to devote to AI. I'm not saying any of the points made in those posts are right or wrong, just that Atari's financials don't have a whole lot to do with our development budget.

2) Ultimately of course any software developer (be it business software, games, websites, whatever) has a finite pool of resources to devote to the development of a product. The primary objective in a business is to produce a product that will make a profit. With game companies we have the added personal incentive of wanting to make a great, fun game as well. So you've got a lot of tradeoffs to make, not the least of which is, which features should we concentrate on? With Civ III, I think we improved the AI as much as we could while also getting in the myriad other things that we wanted to get into the game.

Compared to prior Civ-style games, most players generally view Civ III's AI as a huge step up, and for that we can thank Soren. I can personally tell you that when I was the webmaster, right after the game was released, I got a TON of emails from players who thought the game was far, far too hard, even on the lower difficulty levels.

3) Without stepping into this Civ vs Chess landmine, I think it's safe to say the Civ AI could have been made to be much more complex. One problem with this is that added complexity costs the player CPU cycles. Sure, some of you with the 2.8Ghz rigs can deal with that, but the min spec for Civ III is very low. This was a conscious choice to keep the game as accessible to as wide an audience as possible.

4) Warren Spector was quoted in an interview once remarking that he used to think the goal of AI was to beat the player, but he now realizes a good AI's job is to challenge the player, but never to prevent the player from having fun. I think that's an important point. It's not that difficult (from what I understand) to write an AI that will pummel a player every single time. What's difficult is to write an AI that challenges a player and makes the player feel a sense of accomplishment (not frustration, mind you) when he wins.

We're always looking that direction, and I think we've done a pretty good job of it -- based on the number of colorful posts I see on forums where players talk about how Elizabeth's always stabbing them in the back or how Gandhi is a deceptively dangerous opponent. When I see this kind of thing I feel pretty good.

Just some random thoughts from a non-programmer.


Dan

 

[akots]

Originally posted by SolarFlare

You're missing something here. There are "not that many moves" for any given movement, but each turn doesn't take into account just that turn alone (how often have you seen a grandmaster move a queen to a square where he will lose it? Never, because you've probably never seen a grandmaster play, it would bore you to death, but that's not the point ).

Hey, SolarFlare! That’s the point, which is PROBABILITY. To play with a grandmaster is one thing, to win is another. I was fortunate enough to do the first one many times and even had a couple of wins. It is not more difficult than for a tank defeating fortified mech infantry in a megapolis on a river. You just keep trying.

Thanks for you comments.

 

[akots]

Originally posted by Padma
Civ3 has a much more complex ruleset: The "board" can range in size up to 360x360. Each square can be any of 9 possible basic types, with modifications possible (e.g., jungle, forest, resources). The number of unit types is huge, and more types can be added, if desired. ...

Assume a 32-civ game played on a 360x360 map. Allow each civ 100 units. For each unit, the AI would have to contemplate the possible reactionary moves of 3100 other units. ...

Which victory condition should the AI pursue?...

Dear Padma! There are 6 unit types in Civ3, - military, bombard, air, navy, transport, worker. All others are a combination of them. For example, MA moves 3 tiles and spearman moves 1 tile. In chess, rook moves from 1 to 7 tiles. Certainly, taking 360 x 360 map is a bad example. 100 x 100 should suffice for most of the games. Out of these, 95% are not accessible at a single time point. In chess, every square counts. Terrain has 7 characteristics which are shields, food, trade, resource, luxury, movement cost, defense bonus. In chess, every square is unique and its value and importance is not fixed during the game. Out of 100 units you have probably more than a half are fortified as military police and defenders and should not be moved anyhow. Thus, you end up with 50 working units versus 32 in chess at the beginning. Civ 3 has basically 9 reasonably possible outcomes (victory-loss) which are all clear. Chess has 5 clear outcomes and 1 unclear when draw is unavoidable but not evident to a person who has not sufficient skill to see that. In Civ3 victory conditions should be pursued all simultaneously. This is not so difficult because they are very closely linked. Unless you play a scenario and check only some of them which disables the others. For space race, I believe, there is a space race button for the AI as well. And certainly, the AI can know the exact culture numbers which human can get out of the histogram with a help of a rule overlay over the screen. Diplo victory has a certain probability as well as other victories. Certainly, a war can happen and friends become enemies but at a certain probability which is pretty easy to calculate. With chess, all outcome conditions are unclear especially from the starting position. THUS, CIV3 IS NOT MORE COMPLEX THAN CHESS. Probably, more simple. Just consider how the Civ3 engine is inefficient. It run more slowly in PTW because there are more graphics to load! This is ridiculous. There are essentially no graphics in the game compared to other RTS or action games. And looking for a 50 Kb file with diplo head of Ceasar bowing for 5 seconds through the hard drive is beyond any critique. BTW, modern chess programs run well on low-end computers, they are just not so strong because of the time limit since they can process less moves ahead. I am not talking about city management which is a pure calculator function devoid of any AI. To any chess player with minimal qualification (Elo rating above 1800) all this is evident.

 

[SolarFlare]

Originally posted by akots
Hey, SolarFlare! That’s the point, which is PROBABILITY. To play with a grandmaster is one thing, to win is another. I was fortunate enough to do the first one many times and even had a couple of wins. It is not more difficult than for a tank defeating fortified mech infantry in a megapolis on a river. You just keep trying.

You're absolutely right; the random nature of Civ makes it fundamentally different from chess on the most basic level.

 

[Padma]

One last remark, because I will obviously never convince you, nor you, me.

My Elo rating is 2000.

 

[SolarFlare]

Originally posted by Padma
My Elo rating is 2000.

=Electronic Literature Organization?

 

[akots]

Originally posted by Padma
One last remark, because I will obviously never convince you, nor you, me.

Dear Padma! Never? Why so. You are not my enemy, and I'm not arguing with you. BTW, my Elo not so different, 2150.

Again, I'm trying to make a point and asking for your help as a moderator. Would you let us know of your opinion about the Firaxis post above?

Thank for comments.

 

[akots]

Originally posted by SolarFlare

=Electronic Literature Organization?

Elo is international chess player rating system named after its inventor Prof. Elo. All more or less qualified chess players have a certain rating. For example, the highest about 2800 has Kasparov. Average Elo for grandmaster is about 2450, for international master 2350-2400, for national master starting from 2150 to 2300. Computation is based on a table derived from trigonometric exponent regression. Elo rating is used extensively for over 35 years with great success by FIDE - International Chess Federation.

 

[akots]

Originally posted by Dan Magaha FIRAXIS

1) We are an independent developer, so any discussion of Infogrames/Atari's financials is really irrelevant to the topic of whether a game company has the resources to devote to AI....
2) ...The primary objective in a business is to produce a product that will make a profit. With game companies we have the added personal incentive of wanting to make a great, fun game as well. ...
Compared to prior Civ-style games, most players generally view Civ III's AI as a huge step up...
3) ...I think it's safe to say the Civ AI could have been made to be much more complex. ...
4) Warren Spector was quoted in an interview once remarking that he used to think the goal of AI was to beat the player, but he now realizes a good AI's job is to challenge the player, but never to prevent the player from having fun....Dan

I have spent a fair amount of time thinking of what you have written, so please don’t take these comment as an impulsive.

1) You are saying that Firaxis is an independent developer. For our argument it would be of interest to know which resources did you have indeed to make Civ3 and how they were used. Well, at least, where did all the profit of Civ3 go and how an information about your budget or whatever is relevant can be obtained.

2) I’m not saying that the game is easy. And certainly Civ3 is the best game of games of all times. But really when people play the game they find it as something of more than a little game. It is a good working model of the world. That is why it is so popular and amazingly interesting. Certainly, by creating a model something has to be cut away from the original. Other things remaining have to be less complex than they are. AI is good and may be even the best it can be considering the circumstances. And no one would criticize Soren for the quality of the AI especially considering the challenge.

3) I do agree 100%. With one exception. Civ3 FOR MOST PLAYERS IS MORE THAN A GAME.

4) Really? Is this true? That would be great! I mean stronger AI.

3 and 4) With chess and Civ3 it is quite possible to make a parallel regarding a chess game with handicap and stupid mistakes made by one player. When the players see the AI doing stupid mistakes and winning as a result of this being handicapped by 60%, this is not fun. Certainly, a human is absolutely satisfied in this case. However, in chess and in between qualified chess players such kind of a game means that the game is of poor quality. What games are more valuable? When both players make no evident stupid mistakes and still one of them wins because of a good combination (lets say, in Civ3 it can be a diplo win or nuke war with destruction of an AI-ruled civ through a military alliance) or a good strategy play focused on weak point of the rival or strong points of the player. This can be considered as a domination, space race, or cultural victory, something more solid and more predictable. Regarding the point 1), this kind of game might have a smaller market but probably more serious buyers willing to pay more for a game. May be even some business schools would include it as an obligate test for education of officers required to make important decisions in a company or in a government. Or imagine world championship with 1 million dollar prize. Just joking, don’t take this all too seriously.

However, a word from top players would be appreciated. Also from those who can get a very high score by accurate milking after domination. Is that a thing which should be allowed or AI can surrender in this case ending the game which is pretty much obsolete?

 

[The Last Conformist]

akots: if the AI does not even consider moving those of its units on defense/MP duty, no wonder if it sucks in war. Of those hyppthetical 50 defenders/MPs, most probably 40 aren't doing anything worthwhile at any given moment in a war, and for each a decision should be made each turn whether they should remain in place because the city they're in may become under threat of attack or civil unrest, or sent to the front to fight the enemy immediately.

That 95% of all tiles are usually not reachable for a given unit at a given time isn't true - with a Pangaea, RR and RoP, it may be closer to 5% of all (land) tiles that are not reachable. On top of which you need, in civ as in chess, consider what you're doing several turns in advance, which of course makes the total of combinations skyrocket.

Dan Magaha: No disrespect, but I'm going to doubt you (pl) are able to write an Civ AI which pummels every player every time, unless you allow for all AI's to automatically gang up on the human, or AI production advantages à la the higher levels. At least not without a major and well-funded effort, à la what they did in chess.

 

[eg577]

In my opinion, a chess like approach to AI -- where you consider a subset of all possible choices and evalute the resulting positions -- works for chess because that is more or less the way a human plays chess. We certainly do not play civ that way (and neither does the current AI), so I don't think one even needs such a sophisticated brute force method of AI to make it competitive.

The way we play civ is by forming long and short term goals and think how we can achieve each goal. It is interesting to note that these goals are rarely chosen directily by which is the best way to win the game. E.g: Consider the following long term goal decision: "by which method should I pursue to beat the game (spaceship, conquest etc.)?" A human decides this by first eliminating completely infeasible goals and then selecting one based on fun factor. In addition, we tend to be very stubborn; We don't change this goal when a different way to win becomes more appealing, we change our goal only when the current way becomes unappealing or impossible.

I would love to see this style of thinking hardcoded into the computer AI. For example, at some point in the game the AI civ randomly decides on how he wants to win the game. The probabilites could be somewhat skewed to fit the 'civ personality', such as militaristic civs being somewhat more likely to choose domination but the choice should not affected by the current situation (e.g., it should not give domination a higher probability if it was #1 in power while only say #3 in culture) Once the choice is selected the civ wouldn't deviate from its choice until it considered it too infeasible (so while weak to moderaterly strong civs will still try for domination victories they will give up if they fall too far behind in tech or something)

Not only do I think this is a good idea to improve how fun civ games are, if AI's had a haphazardly selected goal on how to win it allows one to remove the haphazardness in how the AI decides what to build, which is one of the major failings of the AI.

 

[sabo]

Originally posted by Dan Magaha FIRAXIS

3) Without stepping into this Civ vs Chess landmine, I think it's safe to say the Civ AI could have been made to be much more complex. One problem with this is that added complexity costs the player CPU cycles. Sure, some of you with the 2.8Ghz rigs can deal with that, but the min spec for Civ III is very low. This was a conscious choice to keep the game as accessible to as wide an audience as possible.



Dan

Dan I appreciate Firaxis keeping the game specs so you dont have to go out and buy a "super computer" to play it, I think alot of developers make this mistake and they discover that even though they have a great product, they can't sell it as no very few can play it.

Personally I think the AI is fine in CivIII, I have been playing steady for over a year now and there have been very few games created that can keep my interest that long, I disagree with the poster that Deity is too weak, I think Deity is too hard, I usually play at Emporer level because you can actually still build some wonders and you can even get ahead in techs, where as in Deity it's alot of luck, the right Civ and if you build anything but improvements that increase your cash flow it's pretty much a waste of time, but the one nice thing about Deity is it's such a challenge where as other games I'm usually able to beat the highest difficulty setting within a month.

 

[Falcon02]

Just to put in my two cents, a MAJOR difference between Civ III and Chess (rules aside) is players.

Chess you are basically locked at war with one person and no one else is there to effect your actions. You don't have to deal with MA's or MPP's with other people. And war doesn't even have to be declared. Politics and Diplomacy don't even exist in Chess, let alone having to worry about advancing in tech.

A "better" AI won't be around for a while IMHO. Also, don't forget modern game AI's are really "psuedo-AI's" which have no true intelligence, just sits there and responds to preprogramed situations.