It's 2005, why does the AI still need to cheat?

[Orcrist]

Originally posted by Azuarc
I'm going to make a very asinine and headstrong comment

Yes.

Originally posted by Azuarc
I know, easier said than done. But if I had a year to work on it with at least some crude game mechanics in place, I think I could do it. Am I being too cocksure? Probably. But I'd take the chance if someone offered it to me. For an hour, anyway.

Why waste your time on this? Get to work on a cure for cancer if you've got the brainpower to do better in a year in a field where you're not even trained than those who have been working on this problem for at least 50 years. In fact that goes for all of you who seem to have this vague idea that "it could be so much better". I mean, specific suggestions (*very* specific) might very well be valid, but shouldn't common sense alone tell you that if AIs could truly accomplish the kind of strategic thinking you people are talking about, the army (you know, the U.S. army which has a research budget in the *billions*) might have come up with something like at least an automated tank? You might have noticed, that the best they have come up with so far is surveillance drones and the like.

So, you must either think the CIV programmers are the most underrated geniuses in the world (who are just too lazy), or... actually I can't think of another explanation

-chris

[padillah]

Originally posted by Azuarc
I'm going to make a very asinine and headstrong comment, but, even though I am by no means the best Civ player, and not a CS major, I think I could make an AI for this game.
... snip ...
Am I being too cocksure? Probably. But I'd take the chance if someone offered it to me. For an hour, anyway.

(wipes away tear of laughter)

That is one of the funniest things I've read in a long time.

Thank you. In all seriousness, thank you.

Please, check out some of the links below and if you can offer them any help, I'm sure they would love it.

http://www.cyberlife-research.com/

http://www.cs.stir.ac.uk/~lss/NNIntro/InvSlides.html

http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html

http://www.inns.org/

I don't know if you can pull this off but, you're a funny guy!

Tom P.

[padillah]

Originally posted by Orcrist
... if AIs could truly accomplish the kind of strategic thinking you people are talking about, the army (you know, the U.S. army which has a research budget in the *billions*) might have come up with something like at least an automated tank?

-chris

I remembered this. I looked it up and the one from last year (2004) was 300 miles long and the robots could only get less than 8 miles into it.

http://edition.cnn.com/2004/TECH/ptech/03/14/darpa.race/

This year they shortened it to 131 miles and five teams completed it.

http://www.darpa.mil/grandchallenge/

Please note the competitors: Stanford, CalTech, Princeton, Cornell... not unintelligent people.

And they weren't even going for AI. They just had to automate a vehicle.

Tom P.

[nbarclay]

Originally posted by Azuarc

The AI needs to do the following:

Re-evaluate the present needs/wants weighting from the last turn, which has probably changed very little unless something drastic happens. (If you declare war, they suddenly should want more military units.)

Based on those needs, evaluate each one of the decisions I mentioned above by considering each possible option and which seems best

The words "seems best" are the limiting factor. Evaluations of what "seems best" in a game as complex as Civ cannot rely on brute-force computational power, but instead have to rely very heavily on the strategies built into the AI by its programmers. To the extent that strategies can be based on mathematical analysis, the computer could engage in analyses that human players would never be willing to take the time for. But the concepts of "seems best" built in by AI programmers will never be as flexible as what top human players can come up with over a period of time, especially when they discuss their strategies with each other.

Worse, the cost of building in enough different AI behavior patterns that human players can't figure out how the AI acts and use that knowledge to their advantage would be prohibitive. AIs have to be equipped to cope with all manner of widely different human strategies, including strategies that no one had thought of at the time the AIs were created. In contrast, human players can figure out how the AI thinks, zero in on whatever weakneses it has, and take advantage of those weaknesses to gain an advantage. Human players can change their strategies to shore up weaknesses, but AIs don't have the same adaptability, so humans can take advantage of AI weaknesses over and over.

Ciould you make an AI for Civ 4 if you put enough time into it? Probably, at least with suficient help translating your ideas into code. Could you make one that could play evenly with human players who are just as good as you are, and who can study how your AI behaves in order to exploit its weaknesses? No way; at least not and meet a product development schedule.

[Zinegata]

Originally posted by Azuarc
It's actually EASIER than chess

... Actually, you're right on this one, but for the wrong reason =).

Let me repeat it again. It is easier to make a more challenging A.I. for Civilization than it is for Chess.

And before you all go ballistic on me, here is the reason why:

The Civilization A.I. can cheat!

Chess has time-honored rules. You cannot change the rules of the game or it would cease being chess anymore. I can't, for example, program the Chess A.I. to take two moves for every one move the human player makes, because the game would no longer be chess.

However, if a Chess A.I. did get two moves for every one the human makes, it would become a hell of a challenging game, even if the Chess A.I. isn't that "smart". After all, any "check" by the A.I. would automatically result in the human player losing! (The A.I. checks on the first move, and then captures the king with its second. Game over for the humans =)).

The Civilization A.I., by contrast, can cheat all it wants. In fact, it is tradition for the Civ A.I. to cheat. Properly implemented, it's effective, challenging, and very good game design!

Also, I have to say making a "smarter" game A.I. is not always the best move. Consider the case of chess. The game has only 32 playing pieces (in total), with only 64 spaces to put those pieces on (with no stacking). Yet, there are several trillion possible ways of making the first ten moves alone! If you consider how many more pieces there are in a typical Civ game, and I think you can already realize just how difficult it would be to make a "smarter" A.I.

[nbarclay]

Originally posted by Azuarc

It's actually EASIER than chess, because there is no one distinctly superior move no matter what. In Chess, there is, I hypothesize, *the* perfect chess game and a database system more powerful than anything we can create could store it so that your opponent could never win if you followed it.

Actually, we don't know what the outcome wuld be if both sides played chess perfectly because the computational power to find out does not currently exist. If it did exist, we would find out one of three things.

1) Chess is a game like tic-tac-toe where if both sides play perfectly, it is impossible for either side to win.

2) Chess is a game where if white plays perfectly, it is guaranteed to win. (For anyone who might not be aware of Chess tradition, white always moves first.)

3) Chess is a game where if black plays perfectly, it is guaranteed to win.

But in practical terms, we don't have the computing power to determine which of those three is actually the case.

[Bill3000]

It's 2005, why hasn't an AI passed the turing test!?

[Raion]

http://en.wikipedia.org/wiki/Computational_Intelligence

Someday, there are some people who ain't gonna need you!

or "Why the Future Don't Need Us!"

http://wired-vig.wired.com/wired/archive/8.04/joy.html

Pray!

May be like the Terminator Movies!

"Talk to the Hand!"

[Sarati]

Imagine that both warriors are stacked on the same space, and we will number the spaces surrounding them similar to the way the number pad on your keyboard is, so that northwest = 7, north = 8, etc.

Imagine then that the first warrior moves northwest to position 7. How many possible positions are available for the second warrior?

Answer: 9. Any of the 8 possible movements + do nothing.

Now consider that for the first warrior, there were actually 9 possibilities for how it could have moved.

To state this succintly, I refer you to the Rule of Product - a discrete mathematics theory:

If a procedure can be broken down into first and second stages, and if ther are m possible outcomes for the first stage, and if for each of these outcomes, there are n possible outcomes for the second stage, then the total procedure can be carried out, in teh designated order, in m*n ways.

[Azuarc]

Now consider that for the first warrior, there were actually 9 possibilities for how it could have moved.

To state this succintly, I refer you to the Rule of Product - a discrete mathematics theory:

If a procedure can be broken down into first and second stages, and if ther are m possible outcomes for the first stage, and if for each of these outcomes, there are n possible outcomes for the second stage, then the total procedure can be carried out, in teh designated order, in m*n ways.

That much isn't in question. However, in practicality, you aren't liable to consider what happens with that second unit until after the first one is moved and see the effect. If I start off with two warriors in the middle of nowhere, what is revealed by the movement of the first warrior is likely to cause me to evaluate my second decision. Thus after having 9 choices for the first warrior's movement, there are 9 ways as a result to move the second. We have pruned the other choices.

There aren't 729 choices for moving 3 units one space. There are 3 to decide who to move first, 9 to move it, 2 to decide the second, 9 to move it, and then 9 to move the last, for a total of 32 total evaluations. Unless the act of evaluating which unit to move first becomes significantly more rigorous than taking them in their natural unit order - which it might if you are attacking a city or some other closely interdependent situation - I could argue this would even be reduced to merely 27. (And in that exception case, calling it 32 is misleading since it would be effectively much more. Perhaps even the 729...times 3 factorial.)

(wipes away tear of laughter)

That is one of the funniest things I've read in a long time.

Thank you. In all seriousness, thank you.

...

I don't know if you can pull this off but, you're a funny guy!

Glad someone got something out of my post. =p

My overall intent for the post wasn't humor, but I knew some would take it as such, since I have no doubt I'd be biting off more than I could chew. Nevertheless, for someone without formal training specifically in A.I., I might have a chance in hell. My degree is in math, and I have always been good at finding analytical approaches to non-analytical situations.

That doesn't negate the fact that I'd probably give up after an hour, though.

[Lootimer]

If they did develop a good AI, dont you think there would be a few better uses for it than playing a computer game?



Enslaving Nebraska comes to mind..

[padillah]

Originally posted by Azuarc
Glad someone got something out of my post. =p

My overall intent for the post wasn't humor, but I knew some would take it as such, since I have no doubt I'd be biting off more than I could chew. Nevertheless, for someone without formal training specifically in A.I., I might have a chance in hell. My degree is in math, and I have always been good at finding analytical approaches to non-analytical situations.

That doesn't negate the fact that I'd probably give up after an hour, though.

I hope you didn't take offense. I was joking.

With a degree in math however you may come closer than I can with years of programming. It's the math that's killing me.

It's really high-level (as you can tell from those links).

Tom P.

[Drachasor]

Just adding a little bite of info (not sure if it has already been said)...

The computers we have today, even the most powerful desktops quite frankly do not have the mental processing power of a fly*, let alone a human being. Wait 50 years.

-Drachasor

*Now naturally a game doesn't have to worry about keeping the fly alive, so "neurons" wouldn't be spent on autonomic systems. However, unless the game is very limited in what can possible happen--such as chess--this doesn't get rid of the difficulty. Chess Computers don't win by thinking, but by brute-forcing an answer: they look at all the possible boards X turns from now for a given move and then make the move that leads to the best branch of posssibilities. This is inherently impossible for something like Civ since there are parts of the board that you have no information about. For all you know there is a huge army there. And that ignores the greater number of units, larger map, and many other differences.

[nbarclay]

Originally posted by Azuarc

There aren't 729 choices for moving 3 units one space. There are 3 to decide who to move first, 9 to move it, 2 to decide the second, 9 to move it, and then 9 to move the last, for a total of 32 total evaluations.

The catch to that approach is that it does not allow the AI to coordinate its units effectively. That's not a problem if the units are so far apart that their activities are essentially independent of each other. But when higher levels of coordination are needed, the AI can't afford to wait until after it's moved its first unit before it starts thinking about what to do with the second. It has to consider all of the things it might want to do with its second and third (and so on) units - not just in that turn, but also in future turns - as part of the process of deciding what to do with the first unit it moves. Once the AI does that, you're back into the realm of very, very steep exponential complexity.

Because of that, an AI can consider only a tiny fraction of everything that could possibly happen over the next few turns. The vast majority of the AI's skill has to come from rules the programmers give it regarding what to do in what kinds of situations rather than from the use of raw computing power. And while an AI can be more precise than a human in performing whatever mathematical calculations are involved in executing a strategy, AIs do not have anything resembling a human level of flexibility in adapting strategies to fit specific situations or in creating entirely new strategies.

[nbarclay]

Originally posted by Lootimer
If they did develop a good AI, dont you think there would be a few better uses for it than playing a computer game?

Current-day AIs are extremely specialized. They are designed to be as good as people can make them at particular tasks, but have little or no capability to do anything else. Thus, the ability to make an AI that could match any but the very best humans in Civ IV without any special advantages, even if it could be done, would not imply that the same techniques would necessarily have much value for purposes other than making AIs that do well playing strategy games.