Technical AI Discussion... suggestions for the Civ4 AI (NOT another Civ3 AI rant!)

[IDSmoker]

Anyone interested in a good discussion of the how/why of the Civ3 AI should check out SirP's posts on this thread: (Constructive!!!) AI Suggestion Box

Since I've noticed that there are quite a few fellow software developers playing Civ3 (and posting on CFC), this thread is dedicated to a technical discussion of what should be done about the Civ4 AI (whoever develops it... whenever).

From what I know of the principals of artificial intelligence (both in general and within the computer game industry), there are 3 main approaches to AI.

1. Considering the current situation and goals, have the computer consider all possible actions, including all possible reactions made by the user (this is the form of AI used by chess programs, from the limited forms found in hand-held chess games to Deep Blue, the first computer to ever beat a human master chess player).
2. Considering the overall goal, and a pre-defined plan of reaching the goal, the computer must determine an optimum move to further it's progress towards the goal.
3. Have the computer think and act in a manner similar to the way a human does.
   [/list=1]
   Most computer game AI's use a combination of the first 2 options. I'm sure that if you objectively evaluate the last couple of computer AIs you've interacted with, whether Civ3, a first-person shooter, or a flight simulator, you will be able to see how every one of its actions fits into one of the first 2 possibilities.
   
   Because of the sheer number of possible moves and combination of moves available in current games, programmers often find themselves spending a great deal of time trying to plug holes they originally missed while determining what a game AI should look for.
   
   What I would like to focus on is the 3rd option... way back when I was in college, circa 1990 (gawd, was it really that long ago!?!?), I remember getting to play with a 'new' technology called: neural networks. The basic concept is that you programmatically create a software version of the neuron (a basic unit of the human brain that functions as an analog switch... it has a limited number of possible states). Then you string as many computerized neurons together in a web as your hardware allows. You feed input into one end of the web and get output from the other end. Back then, I think that I read that the largest RD center was able to simulate about 1/1000th of the number of neurons in the human brain (about the same number of neurons as you could find in the average hamster)... much dumber than the most moronic dog!
   
   The theory behind neural networks, at the time, went that if you could create a computerized neural network with the same number of neurons as a human baby (way beyond the capabilities of the hardware of the time), you could then teach it to be intelligent. You teach a neural network by feeding it input, and then if the output is closer to the desired results you reward it, if it is farther from the desired result you punish it. In much the same way you teach a baby... so I've been told! (I have far more experience with computers than with babies!<grin>)
   
   Obviously, computer hardware has advanced way beyond the ability to create the requisite number of computerized neurons since then. Since AI is still a myth (unless you subscribe to the conspiracy theorists), there must be a flaw in the theory. But, I have heard that neural networks are being used in handwriting recognition (and related fields). Apparently, you construct a neural network, seed it with some starting values, feed it an input of a handwritten 'a' and if the result looks anything like a printed 'a' you reward it, otherwise you punish it. After a few (???) interations, the neural network will start producing a recogniziable 'a'... you then start inputting a handwritten 'b'... and so on, and so on... eventually you have a neural network that can convert handwriting to printing... of course you still have to vary the type of handwriting. The key, is that the network will learn from its mistakes. So, ultimately, you get the network to the point where it can 'recognize' the most common types of handwriting, and you use the 'internal values' of the network to turn the network into an executable that is not only able to recognize most forms of handwriting, but is also able to continue 'learning' new types of handwriting as it continues to receive different inputs.
   
   Now... considering the limited number of variables involved in handwriting (there are a relatively limited number of ways to position the ink within a very limited amount of space), think about applying the same technology to face/expression recognition (ever really taken notice of the variety in faces around you throughout the day?)... what about speech recognition? (listen really closely to the differences between an Irish accent, a New York accent, and a southern accent!!!). All of these are examples of the things that neural networks are being used for these days.
   
   
   I believe that at some point in time, we will see neural networks being applied to computer game AIs (if they haven't already been used in games like "Black & White", "Critters", etc.). I have to believe that at some point the number of moves and combinations of moves will exceed a point where it is more 'cost-effective' for game software development companies to implement (and train) a neural network, than it is to continue the traditional form of AI development (with its enormous potential for bugs/holes/flaws).
   
   Since the Civilization series of games is one of the most 'open-ended' games currently on the market, I think that the Civ4 AI is a prime candidate for a neural network.
   
   Intelligent thoughts/comments on this subject are welcome... especially from any software developers with more recent AI/neural network knowledge/experience than mine.

 

[Zouave]

There are TWO problems with the Civ 3 AI.

1. It is not very smart and doesn't learn well.

2. It repeatedly does stupid, illogical cheating things, many of which are designed to screw the human.

The first issue I can't address. The second is merely the result of RUSHED, SLOPPY PROGRAMMING.

 

[philippe]

Well if they sucked in it why dont you do it?I bet after a month you will didnt even had a startingpoint.Come on zouave If its not the A.I stupidity its always something else to rant on.
Be glad they made such a good game

 

[IDSmoker]

Originally posted by IDSmoker
this thread is dedicated to a technical discussion of what should be done about the Civ4 AI

I really wish people would read a thread, before posting messages to it... perhaps we would see more threads stay on-topic!!!

 

[MadScot]

I'm not a programmer or anything, but here's my thoughts anyway...

If you had a learning type of AI, what would start in the box? Would it be 'pre-taught' before I got the game, or would it learn as I played it?

If the former, it would have to be taught by the company. In which case it might not be very smart against my style of play, if that differed radically from the 'expected' style - as has been mentioned in a few other threads, all these 'perfect plans' for the game only work because the AI strategy is fairly well understood, and will likely fail against MP play. So the out-of-the-box AI might be great against a builder, say, but be clueless against a warmonger.

If the latter, is there a danger of the AI learning very bad habits against it's human opponent.

Would the game have to know who the human opponent is, in order to adjust it's tactics (say if a 'family' copy of Civ4 were being played by more than one family member)

How would the AI work in a MP Civ4. If all the separate AIs have evolved separately, how would it pick which Ai to run which civ. And is there a risk of that being a poorly educated AI?

Curious what opinions people have. (And apologies to the experts if these are 'old' AI questions)

 

[marshal zhukov]

IDSmoker.
You said that Civ4 would be a prime candidate for a neural network.
But today's PCs, I believe, are far to weak to mimic the brain and its learning capacity.
So how powerful a PC would have to be to have a neural network?
Would a PC with 10GHz of processing power be able to have an adequate neural network ?
A powerful PC today, 2.2Ghz, can't learn and it is found only in a very small portion of houses, so I believe, that AI will keep being incompetent for a very long time.
P.S. I don't know anything about PCs

 

[Lt. 'Killer' M.]

IDSmoker, as marshal says, I think the power isn't there, so where you aiming at a pre-taught AI like in chess progrmas, where they have stored the 'common' starting variants, then get awfully slow if you do something not covered by them? I so hope we get the breakthrough to fast, computation-non-intensive 'neural' network things, and I'm sure it will come, but I guess it won't be before Civ5 or Civ6

Aside from this pessimistic outlook: it should be possible to give the Ai the capability to use the 'w' command on it's units- a matter of raw power atm, since it would mean having the AI decide what it wants to do with each unit individually (as it does now!), then simploy store all that and evaluate all possible permutations of their order, then pick the best. Thus, the Ai wouldn't throw 50 Tanks at my Mech Inf, only to use 50 Artillery on them afterwards!!!!!.

Not a big thing, but a giant leap forward that is within our grasp right now!

 

[MirandaCore]

The biggest thing Firaxis need to do is give the AI a concept of overall strategy. I know its a lot easier to say than to do, but the problem with civ III is the AI responds to situations on a turn by turn basis and not with an overall strategy.

For example, I played a game in the English was sandwhiched between me and the Egyptians. The English was in a war with the Egyptians and sent over 100 units of swordsman, pikeman, etc in those big stacks at the Egyptians. While those units were in a swamp, I snuck attacked the English and took out all of their cities on that continent. Then I made peace with the English.

For the next 40 turns, instead of attacking me, those units moved back and forth in the swamp. When the Egyptians made peace, those English units moved south towards me. When the Germans declared war, those stacks of units moved north.

The ridiculous thing I saw was 7 spearman walking halfway across the continent to pillage a road next to a German city, and then deciding that the city was too heavily guarded by 1 pikeman, those 7 units marched all the way back. At least in civ II the AI would have taken a chance and attacked the German city.

What Lt. Killer said was right. The AI needs to evaluate options. For example, 10 calvary can take out a mech inf. In civ II, the AI would have tried it. But in civ III, those 10 calvary would never attack the mech inf since the difference between the calvary and mech inf's stats are so different. The computer does not understand weight of numbers.

 

[IDSmoker]

Originally posted by MadScot
If you had a learning type of AI, what would start in the box? Would it be 'pre-taught' before I got the game, or would it learn as I played it?

Both!!! <grin> The 'base' settings of a neural network is the level of 'knowledge' it possesses when it is born/compiled. The network will then refine it's own settings every time it runs. So the developer's use internal alpha and beta testing to refine the starting point (they can check the internal settings after the network has run for awhile... imagine everyone in an open beta sending in their settings to be combined in the final release!). Out-of-the-box, the AI would have a base intelligence that would adapt itself to your playing style.

So the out-of-the-box AI might be great against a builder, say, but be clueless against a warmonger.

Yes, but unlike the current form of game AI, a neural network would 'learn' to beat a warmonger, without having to download a patch.

If the latter, is there a danger of the AI learning very bad habits against it's human opponent.

Yes. Unfortunately, if you successfully model the human model of thinking, you get the negatives as well as the positives.

How would the AI work in a MP Civ4. If all the separate AIs have evolved separately, how would it pick which Ai to run which civ. And is there a risk of that being a poorly educated AI?

Very good question, I had been thinking in terms a single neural network, but it might be possible to have a different set of 'internal network values' be loaded and saved for each enemy civ, which would cause each one to 'develop' differently. I don't know if this is possible with the current neural networks.

Originally posted by marshal zhukov
You said that Civ4 would be a prime candidate for a neural network.
But today's PCs, I believe, are far to weak to mimic the brain and its learning capacity.
So how powerful a PC would have to be to have a neural network?

I'm not so sure.... when I was playing with neural networks in college, we were able to build one with 3000-5000 neurons on a 286. Of course, the human brain has trillions (or is it billions) of neurons, but still, a 286!?! <grin>

Unfortunately, I don't know how far they have come since then, but I am encouraged from hearing that they are using neural networks to handle the handwriting recognition being used on those "Palm Pilot"-type devices, since I know they don't have much processing power.

As for what this might imply about the neural networking capability of a Pentium 4 though... I guess we'll have to wait for someone with some more current knowledge to post a message...

Originally posted by MirandaCore (and in different words, by Lt. 'Killer' M.)
The biggest thing Firaxis need to do is give the AI a concept of overall strategy.

Unfortunately, by the very nature of software development, the more complex you make the standard type of AI code, the more likely you will introduce bugs.

The current 'limited' AI in Civ3, must already amount to an incredible amount of code, based on Firaxis's inability to fix seemingly minor 'holes' (unlike some people in the Civ3 community, I believe that the Firaxis people are probably very good programmers, so if a 'hole' hasn't been plugged, it must be because of the complexity of the code).

Adding the AI ability to 'look' forward and anticipate, would raise the size/complexity of the AI code by an order of magnitude. This would mean a concomitant increase in the number of holes/bugs in the AI.

This limitation in current game AI technology is why I suggested neural networks in the first place. As I see it, the only way we are going to see a significant improvement in the quality of AIs in complex games like Civ, is if there is a significant change in the software developement tools used to create those AIs. Neural networks might provide that improvement... of course, there is probably some technology out there that I've never heard of that might be the 'next great thing'...

 

[HuckFinn]

Now this is very interesting thread, considering I am a computer science student who is very interested in artificial intelligence!

Last spring I spent quite a long time writing a little paper on board games which use a neural network evaluation function that is trained by using a "temporal difference" learning rule. That's how I got to dig deep into some existing implementations of such an architecture and to see results regarding their capabilities and limitations.

By an "evaluation function" I mean any rule that takes a state of a game (say, a position in a chess game) and maps this to a number that tells how good the position is. A neural network is practically just a function computing device that takes an input and gives an output. The learning procedure yanks the network weights so that the error is minimized.

I have played with the idea of Civilization neural network evaluation, and frankly, I feel Civ has a lot of things in it that make neural network evaluation complex.

First of all, Civilization has an immense number of states. Even a chessboard can have around 35^100 different configurations (sorry if I remember the number wrong, but it's a lot anyway), and neural networks have enough trouble fitting those states into their memory. The memory capacity of a network can be increased by adding neurons (vertices of graph), but chess already (and easily) causes currently used networks to have to just fix as many states in the memory as they can and interpolate when they meet a state they have not managed to stuff in.

Interpolation (guessing a value between two values you know) works as long as there are no abrupt changes in the value of the evaluation function. Both Civ and chess do cause a lot of discontinuity in the function, because a few dumb moves can turn the tide of the whole game.

Related to actual state space size is its dimensionality. Civ has a HUGE number of variables, which means the state space has a lot of dimensions. In order to adequately represent a Civilization state, you need to include a lot of information. This potentially makes learning slow and computationally costly. It also makes us need a lot of neurons in the input layer of the network already.

Because the network is big, state space is huge, input vector is long, game is complex... we can assume long training times. We could try teaching the networks though self-play, but I am sure the training time would be prohibitive. It would take (at least) millions of games to learn anything, and considering how long civ games are by turn count... I don't think it would happen.

The above applies to the case where we're trying to evaluate the whole game state with a single neural network. A more interesting prospect would be to use the hierarchical AI architecture already in use in Civ3 and plug small "specialist" neural networks in it to make smaller decisions. Of course, to train the specialist AIs we would need some sort of specialized training data... we might have for example a "leader AI neural network" that would observe just some general variables of the game and then draw the grand lines of the future of the empire.

About learning while playing against the end user of the game... any kind of automated learning is a theoretically and computationally complex issue, and we have not really seen it done for real in games yet. Black & White is an interesting example, however... but even in B&W the learning is far more limited in scope than what would be required in chess, not to even speak of Civilization. Even if we had a neural network system in Civ4, it would be trained before boxing the game. Of course we could implement a learning rule, you'd just have to play millions of games against the computer to see any kind of change in behaviour...

Personally I believe that for a long time, Civ-type AIs will rely strongly on heuristics, i.e. rules of thumb that are applied to a given situation, and some simple evaluation functions combined to localized shallow searches. The small specialist networks might make an appearance though, and it would be interesting to see how well they do at their task.

 

[murewa]

i don't think neural network-ing a game such that it learns to do what is right and wrong is practical for the current demands pressed on current developers. i've seen it on informational videos that just for a program to learn very simple information and do the needed correction takes such a long time. sure the nice thing is that the program itself can reprogram itself such that it really learns what is needed. but the equipment and online time for this to be of any significance is too steep to say meet an early deadline (think of dozens of computers 'feeding' a single program code and as time passes by that code itself rewrites itself over and over again).

i do know of one game that has quite a very simple version of this (CounterStrike Realbot). it has a character log in which AI will read and write to making it just a weeny bit more 'intelligent' from each game session. another is computerized chess. this i think is the most successful at such since entire million dollar hardware and online hours are especially supplied for it.

but all this takes time and time Firaxis (and the host of software developers out there) doesn't have - for their customers and for their financiers. imagine them saying "Uh...we can't release it yet because the game's brain is still smaller than an ant's."

And to sum this all up - try to measure human achievement in terms of this neural network-ing and the like. Has it produced enough brainpower to at least mimic an ant's? You know that the positive answer still lies in the future - but very near.

 

[HuckFinn]

Learning from the player wouldn't happen anyway, there is simply not enough material to learn from. The teaching would have to take place during software development using clustered computers or something like that. Besides, I am positive that in Civilization you can get closer to the absolute truth of perfect civilization playing strategy by massive pre-training than active learning from the stupid single human being..

Chess is a good example of where not to use neural networks, by the way. It is a proven fact that it is a game in which just brute search in the game tree always dominates any evaluation function. In other words, use the CPU cycles searching deeper in the game tree and use as stupid an evaluation function as you can, for example just counting material value. It pays off, and easily defeats any neural network architecture. It just goes to show that neural networks are not the holy grail of AI, especially in very limited, thoroughly known domains such as chess (few pieces, clearly defined small set of rules).

What neural networks are good at, however, is achieving a level of "fuzziness" where clear-cut true/false decision systems fall apart.

Take the "overall game leader AI" I mentioned. We might train a neural network that takes in some values about the current game, say number of cities, number of different types of units, income per turn, etc... nothing too specific, but things that will give you an overall picture of how the game is going. The network would then compute a function to a set of values that would guide the overall development of the empire, such as production type in each city and peace/war status with neighbours.

With proper training, a neural network might demonstrate far smoother situational awareness than the current Civ AI seems to. It also might not "snap into a mode" so obviously either.

Anyone up to implementing this in freeciv?

 

[IDSmoker]

Originally posted by HuckFinn
...we can assume long training times. We could try teaching the networks though self-play, but I am sure the training time would be prohibitive. It would take (at least) millions of games to learn anything, and considering how long civ games are by turn count...

Good point, but if there was a built-in 'self-play' mode... you could eliminate most of the graphics (which is what really slows down the length of a turn), then you could configure a game where all of the civs play themselves. It still might take some time to play millions of games on a computer, but you are now working with a problem that is processor bound... throw money at the problem and it goes away! <grin>

Of course, this approach would require a way to make definitive 'attitude/strategy' differences between civs. At least, you would more than is currently available in Civ3.

On the plus side, once the AI is set, this same 'self-play' mode could be used to tweak the strengths/weaknesses of each civ to help with play-balancing.

... A more interesting prospect would be to use the hierarchical AI architecture already in use in Civ3 and plug small "specialist" neural networks in it to make smaller decisions.

Good idea! Limiting the scope of the 'specialist' networks would solve some of the size/complexity/training time issues. You could even break these down into 'low level specialists', responsible for deciding "How to capture an enemy city" and the like, and 'high level specialists', responsible for deciding "When/How to declare War". Each specialist would still use similiar amounts of information, but the low level would focus on immediate information on the 'board' (like how far to the enemy city, what enemy units are in range, etc.), whereas the high level would use information about the entire civ's empire as well as the known information about the enemy civs.

... Even if we had a neural network system in Civ4, it would be trained before boxing the game. Of course we could implement a learning rule, you'd just have to play millions of games against the computer to see any kind of change in behaviour...

Perhaps, but how many games will be played during the Civ4 open beta (assuming there is one)? I can't help but feel that the game developers would have some use for the revised network settings that could be sent in by everyone participating in the beta. Of course, putting that information into a usable format might be more trouble than it's worth! <grin>

Personally I believe that for a long time, Civ-type AIs will rely strongly on heuristics, i.e. rules of thumb that are applied to a given situation, and some simple evaluation functions combined to localized shallow searches...

You may be right, but I've been playing games for a long time now (my first computer game came on a cassette tape! <grin>), and lately, I've started feeling that we are seeing developer's reach a limit in AI development. When you increase the complexity (or intelligence) of a 'heuristic' AI, you are increasing the lines of code required to create the AI. It's a sad fact of software development, that the more lines of code you have, the more bugs that will find themselves into the system, and the harder it will be to find and fix those bugs.

It just seems like if we want games that are more complex, or AIs that are more intelligent, we will have to find a new method of creating those game AIs to provide a satisfying single-player experience. I think this approaching 'limit' is contributing to the popularity of multi-player games... both in the user's desire to play against a challenging opponent, and in the developer's desire to control development costs (many new games are being created that have no AI at all).

...considering I am a computer science student who is very interested in artificial intelligence!

Have you learned of any AI technologies 'on the horizon', besides neural networks, that could be adapted to game AIs?

I really didn't intend this to be a "Neural Networks Thread" but that is the only AI tech I could think of that might improve things for Civ4.

 

[HuckFinn]

Good point, but if there was a built-in 'self-play' mode... you could eliminate most of the graphics (which is what really slows down the length of a turn)

If we were pre-training, which I do feel is the only way to go, we'd just have the very core of the game running at a few dozen computers and a weight server that would keep track of the achieved results. Not anything unneccessary taking up resources.

This way Civ games might get shorter by actual time, but they still are long "by turn count". This is a learning problem in itself - it becomes difficult to figure out what exactly was the role of a single move when the sequence of moves is long. Did that one spearman killing the tank cause the fall of Rome? That's what the temporal difference learning rule is though, but that's very technical...

Of course, this approach would require a way to make definitive 'attitude/strategy' differences between civs. At least, you would more than is currently available in Civ3.

Weight the rewards differently. Say that Bismarck gets double the negative feedback for military losses, and over time he will become far more docile than he currently is. I kind of like the idea..

You could even break these down into 'low level specialists', responsible for deciding "How to capture an enemy city" and the like, and 'high level specialists', responsible for deciding "When/How to declare War".

Exactly. Also it's worth noting that at some point we reach such a low level, that we no longer need the generalization ability of a neural network... we can just juse a traditional algorithmic method. Of course for example in capturing an enemy city a neural network might be nice in guiding the search for the (near) optimal movement/attack order... even a localized "city capture game tree" can be pretty big.

I can't help but feel that the game developers would have some use for the revised network settings that could be sent in by everyone participating in the beta.

I feel that computers would play in a day just as many games as the beta testers could play in a few months. Besides, there is the problem of bad players who don't really contribute to the learning, but can, on the contrary, lead the AI astray. Sometimes learning game programs end up predicting the bad opponent's blunders because those of course give a massive boost to the AI's side of the game... but without the AI having played brilliantly.

Self-play would be always constructive because the AI would always have an opponent that is a good match to its abilities... it would also be quick and controllable. I don't think that adding humans to the mix of opponents would contribute anything, as long as there is enough variety in the game situations encountered in automated self-play.

That can be a problem for deterministic games in which there is no randomness. That's because the AI always chooses the solution which looks best at the time, without ever taking risks and examining other options. We need to be able to force the AI to look lines of play that seem sub-optimal at first. This can be done through randomness (spearman kills tank) or alternating opponents. Actually the Civ3 AI would be a good starting opponent for the Civ4 AI..

Of course, putting that information into a usable format might be more trouble than it's worth!

You'd just add up all the separate weight vectors to get one big weight vector.

When you increase the complexity (or intelligence) of a 'heuristic' AI, you are increasing the lines of code required to create the AI.

This is very true. One of the reasons why a teachable system that would hold its information implicitly in some set of parameters would be cool.

Have you learned of any AI technologies 'on the horizon', besides neural networks, that could be adapted to game AIs?

Bayesian networks, maybe. They are very "hot" these days in AI. A form of combining connectionism as in neural networks to statistical inference in symbolic logic.

I really didn't intend this to be a "Neural Networks Thread" but that is the only AI tech I could think of that might improve things for Civ4.

Agreed... at least they would be worth the try as a way to implement certain subsystems of the AI.

I must say that personally I am slightly sceptical about the future of AI in our current computer architecture. The serial computer we're using these days is very lame in computing ability, as is evidenced by the very strong and limiting theory by Turing and friends. NP-completeness -- a difficult type of "computational toughness" -- comes up a lot in many interesting AI problems... and we just need to figure out ways to approximate the answers to get them in decent time as compared to the exponential time it (probably) takes to get the optimal answer.

If there was a holy grail of AI that would let us solve these nice AI problems fast, then we probably would also have the algorithm to solve these NP-complete problems in polynomial time... and if someone figured out that, he'd be eternally known as the Einstein of computer science....

 

[Exsanguination]

Originally posted by IDSmoker


I really wish people would read a thread, before posting messages to it... perhaps we would see more threads stay on-topic!!!

sorry, I didn't read anything but the first post, and all I have to say is:

Do you know how expenisve/hard to program/make Deep Blue? It is vastly superior to any computing program out there, especially for commercial uses. What you're asking for is a slightly toned down Deep Blue for civ3's AI. NOT gonna happen.

 

[HuckFinn]

Just have to quickly comment on the Deep Blue remark. Deep Blue is a specialized chess program... it does its own job well, it plays chess great. But this doesn't mean that it would play Civilization well.

Chess has a limited number of pieces, a small board, a simple set of rules. This means that it is feasible to compute the game forward as the game tree's "branching factor" -- how many options to move forward there are in a given position -- is manageably small. Also, chess behaves so nicely that we can actually prune the tree and search much less positions...

Chess is really very dull as far as artificial intelligence goes... we can consider the problem solved, we have computers that play "well enough" and better. In the end there is not even much algorithmic difficulty involved.

Civilization is a whole different animal... of course we could spend lots of money on a machine that had neural networks wired straight into hardware etc to increase brute processing speed... but that is the easy part. The big question is HOW in the first place we construct the civ AI... if we use neural networks, are they capable of learning anything meaningful from the Civ domain, and if so, how to make this process easier?

 

[IDSmoker]

Originally posted by Exsanguination
Do you know how expenisve/hard to program/make Deep Blue? It is vastly superior to any computing program out there, especially for commercial uses. What you're asking for is a slightly toned down Deep Blue for civ3's AI. NOT gonna happen.

I attended Carnegie-Mellon University (CMU) during the mid-80s, when most non-geeks still believed that it would always be impossible for a computer to ever beat a chess grandmaster. I actually met Feng Hsu (the 'father' of Deep Thought, the predecessor of Deep Blue) while he was still working on his doctorial thesis, as well as some of the guys he hung out with. From what I recall, in addition to the specialized software (that HuckFinn has already explained), Deep Thought had some pretty specialized hardware. If you are interested in the details, there are quite a few sites devoted to the subject.

The thing that most non-geeks don't realize (as well as far too many of the young geeks) is that computing power has come a really long way in the past 20 years. In the 80s, the Cray supercomputer was considered the ultimate in computing power. When Pixar introduced its computer-generated video titled "Luxo Jr.", it required 75 hours of Cray supercomputer time to render EACH SECOND of photo realistic animated video. Today's GeForce 3 chip can now render similar video in real time!!!!

Does anyone still believe that the rate at which computer technology is continuing to advance will slow down in the foreseeable future?

Please don't take this as a personal attack... I'm just an old geek who's getting cranky in his old age. <grin>

Originally posted by HuckFinn
...Besides, there is the problem of bad players who don't really contribute to the learning, but can, on the contrary, lead the AI astray.

Interesting point, but I would tend to think that by their very nature, a franchise game's open beta would tend to attract players who are already familiar with the franchise. who would tend to learn the game faster than complete newbies (who would probably wait until the game was released). I wonder if there is anyone who can confirm/refute this theory?

I don't think that adding humans to the mix of opponents would contribute anything, as long as there is enough variety in the game situations encountered in automated self-play.

I have to disagree with you here... It is going to be a long time before a computer can match a human beings creativity, not to mention sheer contrariness! If the AI only learns from 'self-play', then it will never be able to handle the unorthodox, yet successful, strategies that will inevitably be discovered by the players. Whether you consider it an 'exploit' or a 'successful strategy', the AI should be able to learn to handle it.

• Of course, putting that information into a usable format might be more trouble than it's worth!

You'd just add up all the separate weight vectors to get one big weight vector.

But wouldn't you have to throw out the more extreme values (from the players with the more extreme playing styles)?

Bayesian networks, maybe. They are very "hot" these days in AI. A form of combining connectionism as in neural networks to statistical inference in symbolic logic...

...The serial computer we're using these days is very lame in computing ability, as is evidenced by the very strong and limiting theory by Turing and friends. NP-completeness -- a difficult type of "computational toughness"...

Bayesian... NP-completeness... computation toughness...

Sorry, but I haven't heard these terms before... could you define them?

 

[Sirp]

I think that using a neural network, or any other technology which involves the computer adaptively learning, is far beyond current technology levels to apply to a Civilization-type game. Neural networks have been applied in interesting ways, but the areas in which they have been applied simply haven't been nearly as complex as playing Civilization.

I think that a much better AI could be achieved, using roughly the current techniques, however. Making the AI at least a little stateful would be a good start. Also, the AI should really shine in economic management. It should be able to make calculations as to the optimal place to build cities, optimal place to have workers work, etc etc.

Also, in terms of combat, many improvements could be done. I am sick of seeing 4 longbowmen march up to my city; I mean, if they really want to give my veteran knights 4 advancement opportunities, it's their choice, but it does get a little old after a while.

As for advancement in computing technology, sure, computers have surpassed many obstacles that were said to be insurmountable. What is not so often remembered, is that they have not come near to some goals people claimed they would have easily reached by now. In the 1960s, many computer scientists predicted we would have machines that could pass the Turing Test by now; we're nowhere close.

Further, I don't think that Civilization is something that can be solved as easily by raw computing power, than by a well-written program. Sure, a little computer power would be needed, but I don't think it's as important as well-written software.

I am becoming interested in writing an AI which plays a Civilization III-like game. Mainly just to see if I can do it. I'm still in the stages of writing a framework (i.e. the part that implements the Civilization rules, rather than the actual AI), but if anyone is interested in collaborating, send me an email (dave@whitevine.com)

 

[HuckFinn]

An exchange that IMHO characterizes a lot of "computers can do this and that" talk:

IDSmoker:

Does anyone still believe that the rate at which computer technology is continuing to advance will slow down in the foreseeable future?

IDSmoker takes the positive outlook on things... however...

Sirp:
What is not so often remembered, is that they have not come near to some goals people claimed they would have easily reached by now.

We do get raw processing power at quite an impressive speed, but some problems just simply are beyond the scope of a traditional algorithm, as proved by Turing. Some other problems are of the nature that they neccessarily seem to demand an exponentially growing time when the input grows. This is unacceptable even when you could build as fast a computer as you can... just add some length to the input and your cool new supercomputer feels like a 286. This subject is about theory of computation and thus off-topic, but suffice to say that there is something about the "quality" of certain problems (which are found in abundance in AI, unfortunately) that makes them hard to solve... encryption for example relies on this.

It just happens to be that simply increasing the MHz number of your CPU won't make Civ AIs any brighter...

Sirp:

Neural networks have been applied in interesting ways, but the areas in which they have been applied simply haven't been nearly as complex as playing Civilization.

I second that. That's why we won't be seeing a neural network playing the entire game of Civilization. The domain is just simply too complex. However, using a neural network in smaller parts of the problem might be beneficial.

I might for example first build an AI and then check out at what parts the AI relies on the value of an evaluation function. Then if appropriate, I'd learn and compute the evaluation function using a neural network. This would be good especially if the function in question is unknown, as this is where the adaptive learning part comes to play. Currently these functions (say, the "goodness" of a city site on map) are probably weighted sums, and the weights are parameters which are heuristically chosen by the programmer - that is, "guessed". A neural network could learn the optimal parameters on its own...

Further, I don't think that Civilization is something that can be solved as easily by raw computing power, than by a well-written program. Sure, a little computer power would be needed, but I don't think it's as important as well-written software.

I second that 100%. Civilization is too complex for brute force. If you try to solve it through that, you'll just need too much of it. Chess can be solved through raw computing power, Civilization not. We need good, polished heuristics at the core, augmented with searches and possibly some nice tricks such as local neural network evaluation...

IDSmoker:

If the AI only learns from 'self-play', then it will never be able to handle the unorthodox, yet successful, strategies that will inevitably be discovered by the players.

... which are also strategies that will inevitably be found in automated self-play, and much quicker than when waiting for the human players to show them to us..

Human creativity doesn't create anything outside the set of existing solutions, it's just that creative people are able to get there faster than non-creative ones...

Also, I don't think we should include an adaptive game-learning system in the "end product". There is no sense in teaching "how to play" from ground up to our system... an interesting form of adaptivity would be a per-game-basis adaptive learning AI player personality. Take the Black and White "creature" for example. Beat it and it'll grow insecure, stroke it and it'll like you. The AI won't be learning the rules of the game this way, but it will learn *who you are* as a player, at least as far as the current game is considered.

But wouldn't you have to throw out the more extreme values (from the players with the more extreme playing styles)?

No. If that playing style indeed is extreme, the vector representing it will be rare in the distribution of weights obtained from the testers. Therefore, there will be plenty of more mainstream examples to yank the overall sum vector in the "right" direction.

Bayesian... NP-completeness... computation toughness... Sorry, but I haven't heard these terms before... could you define them?

Bayesian networks and NP-completeness are defined all over the internet

Another interesting method currently in use are support vector machines. Definition also on the internet... I heard the Black&White creature uses a SVM.

Sirp:
I am becoming interested in writing an AI which plays a Civilization III-like game.

Very, very interesting. Ever thought of writing it as a computer player for freeciv, an open source Civilization clone?

 

[Sirp]

HuckFinn: The main reason I wouldn't write it for FreeCiv, at least at this stage, is that they still only support Civilization II rules, which imho are much less interesting than Civilization III rules. Also, as far as I can tell, they don't have a diplomacy model.

Which brings me to another topic. I think one thing that would be very nice in an AI, is a better diplomacy model. Allowing more complex deals, like, "I want a right of passage through your territory - to move troops along this corridor (drawing a corridor through their territory on the map) so I can get to here", rather than just a general RoP agreement. Also perhaps, if you have an alliance with someone against someone else, you could say "ok, you attack this city, and I will attack that city" and so on.

As for neural networks, I think that they are theoretically useful, in some areas such as selecting city sites. However, in reality, for such applications I think that just coding it using heuristics would give indistinguishable results, and would be much easier.