Difficulty level should not be done by CHEATING!

[Masquerouge]

Ten years ago, who would have thought an Ai the level of CIV3 would be possible ? Who would have thought an AI in a video game was possible ?
So I say let's wait another 10 years. And in the meanwhile we'll have PTW to fight worthy human opponents

 

[Hurricane]

Originally posted by Mullet Crusader
Yeah, its impossible to PROVE something CAN'T be done

Not true. Take one classic example; Fermat's theorem, where he already in 1630 claimed that a simple equation could NOT be solved.

Fermat's Last Theorem states that (n = to the power of)

xn + yn = zn 
has no non-zero integer solutions for x, y and z when n > 2.

It took until 1995 until it was proved that the theorem is true, i.e. the equation CAN`T be solved.

Click this Link for more information about this theorem.

 

[sumthinelse]

Originally posted by Hurricane


Not true. Take one classic example; Fermat's theorem, where he already in 1630 claimed that a simple equation could NOT be solved.

Fermat's Last Theorem states that (n = to the power of)

xn + yn = zn 
has no non-zero integer solutions for x, y and z when n > 2.

It took until 1995 until it was proved that the theorem is true, i.e. the equation CAN`T be solved.

Click this Link for more information about this theorem.

Wow, an intelligent post!

The proof of this theorem was greatly aided by computers. Mortimer Adler (of the Great Books of the Western World) had stated that one of the differences between mathematics and science is that mathematicians do not experiment but this proves that he was wrong. (I think it's true that not all mathematicians make mathematical experiments).

Back on topic. So many people on this forum keep repeating that hardware limitations keep us from developing a stronger AI. The problem is that they are determining the requirements for a program that has not been designed yet!

 

[Aeson]

Nothing can be proven for certain, so it's not much of an argument for or against anything. Just leave that argument out. Except for metaphysical debates about whether absolute certainty is possible there is no point to the debate. Reasonable certainty is all we can hope to attain in any matter.

You can predict, by the number of variables, how many calculations would be required to make a 'smart' AI. As the number of variables increases, the number of calculations also does, exponentially. The exponent would be the depth of the search.

For example, take Tic-Tac-Toe. There is a static board which never changes. On the first play there are 9 options, and no variations on those options. The next player has 8 options, so you have 72 possible outcomes. Then 7, 6, 5... till the board is filled. This is a 'perfect' game as we can map out all possibilities and use that information to design an AI which will never be beat.

Chess is a much higher level game which probably will never be perfect. Not only are there more peices and board tiles, but different peices have different functions, and each move has many more options. It still has a static board though. Chess programs can be very smart, but it takes a very advanced computer and years of programming to get to the level where it can compete and win at the highest level.

Then look at Civ3. There are up to 16 players, without a set number. That alone adds a huge complexity to the game. Imagine a chess game with room for 16 players, and the extra permutations in possible actions each turn.

Also, not only are there more types of peices, but their numbers are variable and the limit is much higher. There can be thousands of units on a Huge map. Doubling the number of units would quadrouple the number of possibilities on the second turn. To be 'smart' an AI would have to look several turns into the future. On this point, Chess becomes simplistic in comparison. Not only that, but these units can have more than one function, and that function can vary depending on the unit's location.

Then you have a board which isn't static, either in size or composition. Just getting the AI's to build cities intelligently would be a huge undertaking. A city site has to account for initial, and potential; commerce, production, food, defense, overlapping, not to mention strategic function which in and of itself would dwarf a Chess AI.

Now add in Culture, Tech, Improvements, Diplomacy... and make it scalable to each difficulty level, map settings, the actual map result, number of players.

I hope you are beginning to see the orders of magnitude in complexity that we are dealing with in Civ compared to Chess. I don't care to do the math, but an AI with Blue's level of competence in Civ3 would probably take weeks to determine a late game action, and have to make hundreds or thousands of decisions like that each turn (ie. move units, change production, make trades, start wars, found cities, prepare for future moves, production, trades, wars, cities...).

I think it's fair to say that with our current technology it is beyond the scope of probability. We can figure out a few tricks to teach the AI, and program it to take advantage of those, but anything approaching game sentience (even remotely) is out of reach for now.

 

[sumthinelse]

Aeson, I agree that it would be impractical (and thus, from a business point of view, impossible) for Firaxis to try to make an AI that played as strongly as a chess program. And if I were Firaxis, I would not have the resources to attempt it. So if I imagine a very strong CIV3 AI, it would be done by dedicated, talented individuals who were given money by an eccentric, rich "CIV3 Fanatic."

So I am looking forward to PTW as the real solution.

Your post is very well stated but:

Originally posted by Aeson
Chess programs can be very smart, but it takes a very advanced computer and years of programming to get to the level where it can compete and win at the highest level.

If the best human players at CIV3 had reached the same level as the best chess players, humans would have been playing CIV3 for about 600 years. (And, I admit, the fact that humans have been playing chess so long helps the effort to make stronger chess programs). How long do you think you would have to study chess to beat the Fritz program running on a home computer? One reading your post might believe that cheap chess programs running on home computers do not play strongly, and they play very strongly indeed. So if we had a CIV3 program that played CIV3 as strongly as a $30 commercial program plays chess, it would beat every human CIV3 player.

What is the weakest aspecy of the AI's play? I honestly don't know. There may be some improvements in 1.29f, and I am not well acquainted with it yet.

First we fix the glaring stupidities, like declaring war against a civ halfway around the world, and marching its units 50 turns until they, now obsolete, are slaughtered by the technologically superior enemy. Then we decide what the weakest part of AI play is (production/city placement, strategy/tactics in war, etc.) Break the problem into smaller parts!

Let's say we begin with a civilization at war with the human. You can leave the production, diplomacy, and other mechanisms alone for the time being. A unit might be able to move to hundreds of squares along railroads. Each move might involve the unit in combat, and each combat is determined by a "random number." (We don't want the computer to look at the random number, because that would be "cheating." .) So we give each move a score, which is the expected plus or minus to the AI's score.

If this brute-force kind of approach gets too slow, we could "prune" some of the unlikely-looking moves from the tree. This would cause the AI to make some mistakes, but the current AI makes mistakes too.

This chess-type algorithm might not work well for other aspects of the game. Where do you place a city? This might be a difficult problem for a human player.

This is not a black-and white question. I believe that CIV3's AI can be improved, but it would be foolish to expect it to play as strongly as a chess program. I don't have all the answers, but I distrust statements that claim that it is impossible to make significant improvements to any program.

 

[Masquerouge]

Actually, there WAS improvements between CIV1, 2 and 3... But it's hard to tell if these improvements were due to the increase of processing power or to a better programming. I guess I will surprise everyone of you if I say : both, probably
Furthermore, evolution - of any kind - is very rarely a continuous and stable process ; it's more often breakthrough, violent changes, revolutions...
Let's pray for a genius to be hired by Firaxis and discover the secret of offensive artillery

 

[ainwood]

Man! Three threads that I have read in a row, all lamenting the "no offensive artillery", and I was attecked by offensive artillery last night!

Anyway: On Topic: Anyone familiar with the game "Go"? No-one has been able to write an effective AI for that either. There is a rather large prize being offered, and yet its still very difficult - for such a simple game (well, the concept and complexity of the rules at least).

I am with the "its too hard" camp on this one.

 

[Masquerouge]

Hey Ainwood I was not complaining about artillery, I was making fun of people complaining about artillery... Zouave's new fight, it seems.
But I'm glad you were attacked... As I posted before, I've got a feeling this will turn out as a "Spearmen are invicible" rambling...

 

[sumthinelse]

Originally posted by ainwood
Anyone familiar with the game "Go"? No-one has been able to write an effective AI for that either

Have you tried to beat the best "Go" programs? The problem is that the best human "Go" players, like the best chess players, are very, very strong.

Average players playing against a good chess or Go program can actually learn to become better chess or Go players against humans, but CIV3 players beat the AI by setting research to zero and buying techs from the AI. That's not going to work against truly strong human CIV3 players.

 

[Masquerouge]

You bet ! I can imagine a game with 8 human players, all of them setting research to zero... And in 2024 AD one wins because he discovered "The Wheel" in a goody hut

 

[sumthinelse]

Usually "constructive criticism" threads turn into "b**ching" threads. Could the reverse happen here? We have seen some coherent posts on both sides here lately.

 

[PCHighway]

Originally posted by provolt


Your right! I have inside information that Firaxis actually has a really good AI that is smart and is able to learn. Those bastards at Firaxis have been hiding from us. It's a highly parallel program and running on the secret server farm buried deep within the Firaxis bunker. It's in the middle of the 4th turn now, but with advances in computing technology they hope to complete one game before the heat death of the universe.

If you didn't notice the sarcasm, what I'm trying to say is that you CANNOT have a "smart" AI that learns from it's mistakes the runs on commerical hardware. An AI for anything much more complicated than checkers that can actually keep up with humans is not going to run fast enough for anyone to actually play

Yes, I have seen many, while Civ iii does not have, by any means bad Ai There are many strategy games, AoE series comes to mind, That have absolutely Crappy AI, although this doesn’t take away from the series fun-factor. You or anyone who has played it, would know this. However Good AI usually comes, ill admit, from Scripting. While I have never witnessed a perfect Ai I remember once In a fps title Called Ghost Recon I would send the team into a street that looked Hostile. I sent a scout, only to watch him be shot to pieces by hidden Ai, the next one I sent went Around the building and attacked from the Back,Even though I had given him the same command as the last scout, While I attacked from the Front . Other times I had team members just shoot straight at the sky. The point is, it had highs and Lows.

In AoK I put three Archers right by some trees, (where the Ai was sending Villagers to gather wood) Did it stop them? No, in fact they just kept making Villagers and sending them to the same spot, to get killed. They wasted so much food,(each unit costed either food, gold, or wood) by the time I invaded, I only encountered 2 villagers, and a couple swordsman.

To everyone who doubts it, Good Ai, is entirely possible. But in Strategy games? Maybe someday, But as far as im concerned, the Civ iii Ai is good as it is.

BTW I wish Padma would come back and Answer some Questions about Programing...

 

[Jabba Jr]

I think the biggest problem is that the AI seems to be afraid of big non-human civs, and settle with being a small civ instead of attacking the big guys. The human player "always" expand their territory on the expense of their neighbours, therefore they are much more powerful in the late-game.

I've actually played games where there were no wars until the moderna era....

If the AI was more willing to fight itself and not only the human, we would see bigger civs in the late game, giving us a run for our money.

Only problem is civ3 would turn into a full-time wargame, although I'm sure this could be regulated.

 

[Mullet Crusader]

Originally posted by Hurricane


Not true. Take one classic example; Fermat's theorem, where he already in 1630 claimed that a simple equation could NOT be solved.

Fermat's Last Theorem states that (n = to the power of)

xn + yn = zn 
has no non-zero integer solutions for x, y and z when n > 2.

It took until 1995 until it was proved that the theorem is true, i.e. the equation CAN`T be solved.

Click this Link for more information about this theorem.

Wait, im a little lost, i'm a lot more Philisophicla than i am Mathmatical, so that went right by me that sounds like a bunch of gobbledy gook to me, grrrr, stupid numbers, math has never been my friend. I don't understand the equation but the way i figure it, you can't prove something can't be done, its impossible to prove something CAN'T be done, because you never know if someone is gonna be able to do it, like when people said it would be impossible for us to travel into space. now XN + YN = ZN sounds to me like 1 + 2 = 3, but then again im not very Math-minded, so i'm just gonan have to take yer word on XN + YN = ZN

 

[Mullet Crusader]

Originally posted by Aeson
Nothing can be proven for certain, so it's not much of an argument for or against anything. Just leave that argument out. Except for metaphysical debates about whether absolute certainty is possible there is no point to the debate. Reasonable certainty is all we can hope to attain in any matter.

You can predict, by the number of variables, how many calculations would be required to make a 'smart' AI. As the number of variables increases, the number of calculations also does, exponentially. The exponent would be the depth of the search.

For example, take Tic-Tac-Toe. There is a static board which never changes. On the first play there are 9 options, and no variations on those options. The next player has 8 options, so you have 72 possible outcomes. Then 7, 6, 5... till the board is filled. This is a 'perfect' game as we can map out all possibilities and use that information to design an AI which will never be beat.

Chess is a much higher level game which probably will never be perfect. Not only are there more peices and board tiles, but different peices have different functions, and each move has many more options. It still has a static board though. Chess programs can be very smart, but it takes a very advanced computer and years of programming to get to the level where it can compete and win at the highest level.

Then look at Civ3. There are up to 16 players, without a set number. That alone adds a huge complexity to the game. Imagine a chess game with room for 16 players, and the extra permutations in possible actions each turn.

Also, not only are there more types of peices, but their numbers are variable and the limit is much higher. There can be thousands of units on a Huge map. Doubling the number of units would quadrouple the number of possibilities on the second turn. To be 'smart' an AI would have to look several turns into the future. On this point, Chess becomes simplistic in comparison. Not only that, but these units can have more than one function, and that function can vary depending on the unit's location.

Then you have a board which isn't static, either in size or composition. Just getting the AI's to build cities intelligently would be a huge undertaking. A city site has to account for initial, and potential; commerce, production, food, defense, overlapping, not to mention strategic function which in and of itself would dwarf a Chess AI.

Now add in Culture, Tech, Improvements, Diplomacy... and make it scalable to each difficulty level, map settings, the actual map result, number of players.

I hope you are beginning to see the orders of magnitude in complexity that we are dealing with in Civ compared to Chess. I don't care to do the math, but an AI with Blue's level of competence in Civ3 would probably take weeks to determine a late game action, and have to make hundreds or thousands of decisions like that each turn (ie. move units, change production, make trades, start wars, found cities, prepare for future moves, production, trades, wars, cities...).

I think it's fair to say that with our current technology it is beyond the scope of probability. We can figure out a few tricks to teach the AI, and program it to take advantage of those, but anything approaching game sentience (even remotely) is out of reach for now.

Aeson is right on here, if someone was to teach Deep Blue Civ3 it would take the thing weeks to figure out its moves, a human can look at its screen and think in a couple seconds, "I'm gonna go for a conquest victory!" then when he gets beaten back in a war and is forced to surrender, he thinks of the next best possibility for winning. "I'm gonna go for a spaceship victory!" now give that to a big smart computer, it would take the thing forever with current technology to even consider going to war. "I could gain land, but how useful is this land, lets examine, jungles oculd cause disease to my cities and ect. ect. ............ and" while the computer is working out every single propable outcome ot somehting, the human takes a look, goes "hmmmmm" and makes a desicision. To make a computer that could play an inteligent game of Civ 3 and wouldn't take forever would cost massive amounts of time and money, which is something Firaxis doesn't have time for, sadly, so we're just stuck with cheating AI whether we like i or not

And Sumthinelse i'm gonna be up all night trying to figure out that damn formula

 

[Masquerouge]

It just says that when n is greater than 2, there is no x, y and z, integers (numbers without commas) to the equation x^n+y^n=z^n.
For instance, if n=2 and x=3, y=4 and z=5, you've got
3^2+4^2=5^2. That's correct, because 9+16=25
You will never be able to find a solution with n=3...

Is that clear, now ?

 

[Scientia]

Originally posted by Hurricane


Not true. Take one classic example; Fermat's theorem, where he already in 1630 claimed that a simple equation could NOT be solved.

Fermat's Last Theorem states that (n = to the power of)

xn + yn = zn 
has no non-zero integer solutions for x, y and z when n > 2.

It took until 1995 until it was proved that the theorem is true, i.e. the equation CAN`T be solved.

I believe that the claim that Fermat's Last Theorem (FLT) made was not that the equation could not be solved, but rather that there were no solutions to the equation for n> 2 (when n = 2 it is simply the pythagorean theorem a^2 + b^2 = c^2)

The mystery of FLT was intensified by the fact that Fermat didn't offer a formal proof other than some scribblings in the margins of his notes which appeared unrelated or illegible.

It wasn't until fairly recently (1993 is the correct year I believe) that FLT was proven using an indirect proof involving elliptic curves and modularity.

Fermat's "proof" of his theorem was never found and his grounds for believing in it remain a mystery.

How he came to make such an assertion remains a mystery.

 

[Mavtse]

guys of civfanatic are COOL! I didn't expect such a silly comment bring so much discussion and evolved into a maths forum

I used chess as an example only, and differnent chess program used different algorithm, not just calculating ALL possibility.

Calculating ALL possibility in CIV3 is impossible, i know that. what i want to suggest is that the AI should act with a good set of 'rules of thumb'.
i don't know if the current CIV3 is designed like that. If it is so, there's much room for improvement.
Difficulty level can be changed by how many 'rules of thumb' the AI should check and follow.

And most importantly, i'm sick of seeing AIs cheat SO OBIVOUSLY

 

[Agamemnus]

IT CAN BE DONE!!!





Chess
*The units can move to the other side of the board in just a few turns.
*Every move affects every other move.
*There is no massing of units.
*Everyone can see each other (no fog of war)
*No strategy other than to predict opponent's move.

CivIII
*Units can move to the other side of the board in just a few turns, BUT the AI does not have to account for them (city DEFENSE!)
*Every move is part of a big picture.
*There is massing.
*There is a fog of war.
*Strategy = kill loot destroy.

The AI can LEARN. It doesn't need strategy hardwired.

Current techniques in simulating the way humans learn [make that organisms evolve] can be used to create an AI learning sim:

Make 1000 concurrent AI simulation game tests.
Have the AIs test and retest their strategies on each other
Pick the "winners" (top 3 or so) in each round.
Mix some of the winners' attributes / strategies to produce offspring / do mutations in strategy learning code.
Rinse and repeat a few thousand times.

Copy & Paste in CivIII or any other similar game.

http://demo.cs.brandeis.edu/

Just need a few supercomputers..

 

[sumthinelse]

Originally posted by Agamemnus
IT CAN BE DONE!!!

http://demo.cs.brandeis.edu/

Just need a few supercomputers..

I think my posts have been misunderstood, and I expect yours to be misunderstood as well.

I think it is really too easy to dismiss suggestions to improve the AI. Now Aeson's post was well written and coherent, but it seems to assume that there are only 2 possibilities:

• the AI has to have advantages to compete with human players, and it is impossible to improve the AI by making it "smarter", given the current abilities of software and hardware.
  
• if you had a machine that was orders of magnitude faster and has massive amounts of memory, and special, expensive hardware (along the lines of IBM's chess program Deep Blue), it would be possible to make the civ3 AI play stronger, but that technology will not be available until far in the future. The software, as decribed by Aeson, would use "brute force" methods like Deep Blue, calculating every possible outcome of every AI decision. In fact, Aeson used the term game sentience to describe what would be required. I do not think that computers need to understand games in a general way in order to play one game well. I agree that such a program would not be possible on current home computers, but I think it is wrong to look at this problem as an "all or nothing" dichotomy.
  

I was thinking of an approach that was neither of the above. It could use "brute-force" calculations in specific combat situations, but certainly would not use brute force for every AI decision.

If you wanted to design a program to predict election results, it would not calculate what every voter had for breakfast, what deodorant each voter used, etc. It would look at the vote at a higher level of abstraction. It would not predict what each voter would do exactly, but it would try to make a useful prediction about what would happen.

It might not be as easy as Agamemnus thinks, but it would be nice if it could learn in some way.

Some of you keep posting that it would require better hardware or future software to improve the AI. You may be underestimating human imagination and inventiveness.

I wanted to state also that I think that Firaxis has done some excellent work to make the AI play as well as it does. I think some of the approaches made the game worse (like the AI trading, but that has been made configuable now) but Firaxis has made a good faith effort to make us happy. Not an easy task, since some of our wishes are in fact in confilct with other players' requests! And I, having done some rather serous software development myself, can testify that it ain't as easy as it looks!