Could Deep Blue play a smarter AI ?

Status
Not open for further replies.
Joined
Feb 18, 2006
Messages
108
Location
Paris, France
This question remains somewhat intriguing to a non-programmer : why, all in all, does the AI remain pretty dumb ?
This is not to criticize the programmers, which I'm sure did the best job possible given the technical and financial limitations. The AI keeps getting better and better with eveny new version of Civ. In Civ 3, it was some sort of psycho robot, throwing huge hordes of zombie units at you, and gangbanging on each other like maniacs - which, to many, was fun, despite all the exploits possible. Some points remained strangely weak : the AI was pretty lethal with bombers, but unable to handle artillery, which was of course a major exploit. In Civ IV many flaws have been corrected, but new weaknesses had to be generated to prevent greater problems - AI turtling up in cities, few AI-AI wars, AI always going for space race and so on - creating (necessary ?) unfun elements, but resulting in a more interesting game.
But all in all, a bland fact remains : the AI is, on the whole, pretty stupid. Put to play against a decently competent human with no handicaps whatsoever, it doesn't stand a chance. And then a comparison with another game comes to mind : chess. Chess programs, on the contrary, are frighteningly efficient, even in standard commercial versions. In fact, in most of the chess programs you buy, the expertise for the AI is to be able to dumb itself down to be able to play at your level. Not even to mention the professional computers and programs, like the famous IBM's Deep Blue and its fearsome hardware power, which is now practically at the level of the very best players in the world. Of course, one might say, chess is not civ. Chess is a pure result of strict mathematical combinations, thus ideal for a computer to work on. But still, Civ is in fact not that different from chess. Sure, it has a lot more more parameters and uncertainties, but in essence it's pretty close.
So here is my question, and I guess it's primarily addressed to people with expertise in AI programming : is this limitation of the Civ AI just a matter of computing power and financial resources to do more in-depth programming ? Or are there some fundamental limitations in our AI programming capabilities at present that wouldn't allow for a very different result, even with more resources.
To put it differently : if a (very) wealthy sponsor was able to rent the Deep Blue hardware and engineers and the whole Firaxis crew for, say, a year, with no financial limitaions, do you think it would be possible to come up with an AI that pretty much plays the way a human do (real initiative, real adaptation, playing to win, ability to evaluate the real balance of power at any given moment to support or hamper different players, selecting a victory condition best adapted to its personality and position in the game, etc...) ? Well, if yes, I guess you will know how to spend your first million dollars if you're really a Civ fanatic...:cool:
 
Why play the AI when there are humans to play with?

Humans have FEAR, anger, spite! They have loyalty, compassion, they are sneaky and treacherous other times.

Nothing will ever simulate a human. The best games are multiplayer (aslong as no one quits and no one lags, disconnects, goes out of sync or any other technical issues)
 
theres a few things going on.

To get you pointed into the right mindset note this:
chess engines didnt spring from the box as efficient as they are. There was series of ideas and implementations to one up the implementations of competitors and fellow hobbyist. Litterally years of developement went into modern chess engines with lots of lesser attempts.

Further those developements were objectively rated for success by their performance relative to their peers.

Lesser performances motivated improved efficiency and seeking clearer thinking about how to approach the problem. Greater performances merited copying.

Further chess has the advantage of context. You know who is a good chess player prior to designing the AI. Who is a good civ4 player prior to designing the AI? You might be able to point to some now but it seems kind of subjective when your in an alpha doesnt it?

AI of tgese commercial games arnt subject to that kind of scrutiny, objective measurement, experimentation, and evolution.

Now some folks will tell you the problems of civ4 in AI are insurmountable. I think thats a cop out. If civ4 were scrutinized by scientist, hobbyist, bored phd students, and way to smart engineering experimenters for the next 10 years the AI that resulted would just flat out embarress the release box AI I promise you.

None of this disrespects the effort of the original designers. Its a commendable piece of software. But you asked why do some computer areas seem "smarter" then other areas. And the answer is they are well worked and advanced by people that could afford to take a risk just to try a new idea.
 
NapoléonPremier said:
But still, Civ is in fact not that different from chess.

This is where you're wrong.

At the beginning of the game white has 20 possible moves. Next move, black has 20 possible moves. The reason computers are so good at chess is because they're able to analyze all the possible moves in advance.

In the first 5 moves of a chess game there are almost 5 million possible scenarios. A human could analyze a handful of those 5 million moves in 1 minute. A computer could analyze them all and pick the best possible move.

A chess AI program usually builds a tree. It starts with 1 node (representing the beginning of the game) and connects other nodes to that. Other nodes are added to subsequent nodes. The tree grows geometrically

/ \
/ | \
/ | \
/| |\ |\ etc..

A computer is able to analyze many moves in the future like this because at any point in the game there are around 20 possible moves a player can make. This equates to ~20 new branches from each node. The reason Deep Blue is so good is simply because it's very fast: it's able to buid, store, and analyze a huge tree in memory - this equates to many moves in the future. It's also able to do this fairly quick.

The reason AI in civ is nowhere near as good as chess AI is because it'd be impossible to build such a tree for civ. How many possible moves does a player have each turn? Hmm let's think about this.. Each unit can move in 8 directions max, plus it could possibly sentry, fortify, disband, or perform some other function: plant a forest, bomb, etc. Multiply that by the number of units you might have. But is that all the possibilities? Nope. You could trade technology A for technology B with civilization C.. or technology B for technology Z with civilization U. You could change to civic D. You could declare war on civilization M. You could change production to unit G in city X. I could go on and on. There very well might be an infinite number of combinations of moves a player could make any given turn.

This is why the developers can't use chess AI strategy when designing the civ AI. To build such a tree and keep it in memory would take IMMENSE amounts of memory.. not to mention processing time.. not to mention that it might be impossible since there might be an infinite number of combinations of moves that a player can make.

This is why we aren't capable of building AI that can beat an average player at GO. GO is much closer to chess than civ, and yet.. the sheer number of possible moves per turn prevents us from coding AI that will be able to beat a human.. even a novice GO player!

This is why developers have to take a much different route when designing AI for a game like civ (or most other games for that matter). It's probably a bunch of rules stored in a lookup table.. ie.. "if this, do this". They have to keep these rules pretty vague.. ie. the can't possibly base them on every single aspect of the game - there would be far too many rules. "if human player 20% weaker than me, and diplomatic modifier -2 or worse, and ___, and ____, then declare war on the human." is pretty much what they have to work with..

I'm not sure if it's evident to you, but this way of designing AI pretty much forces the programmers to give the AI bonuses on harder levels, instead of making it "smarter".
 
As it already is a total memory-hogger, to program a version of Civ4 with an AI comparable to a human player would demand so vast an increase in available memory as to put an adequate computer far beyond the reach of (probably) the entire gaming community unless they all ganged up financially. Then there'd be the problem of which gamer was actually going to be the human player. Despite the quirks and oddities which are the subject of so many threads, on the whole the present AI does a very reasonable job - certainly better than the program manages with the purely arithmetic aspects of the game.
 
warpus said:
There very well might be an infinite number of combinations of moves a player could make any given turn.

Their can't possibly be an infinite number of moves in a single turn. Even in a whole game their isn't an infinite number of possibilities. Even if you take every single possible map with every single possible combinations of rules, their isn't an infinite amount of moves possible. Why?
Because everything in civ is finite, and their is no way of getting an infinite number using only finite number (I refuse to discuss division by 0);)

Mind you the number of possible games of civ is still very big. Even if you could play an entire game in a single second, the universe is probably too young for you to have played every single possible game (even if you never played the same game twice)
 
One other advantage chess programs have is the body of knowledge of many thousands of games that can be programmed into a database for openings.
 
I don't see what memory has to do with it.

There is only one A.I. technique that I know of which is so memory-bound that it is unworkable on modern 512M+ system.. and thats Cogent Confabulation which is related to an area of A.I. known as machine learning.

Machine learning doesnt apply to the type of A.I. needed to play a board game (however, it might be used in-preparation for the game)

A.I. techniques are more often than not CPU limited rather RAM limited.

Warpus is entirely right in his post above. Civ4's gametree expands far too fast for techniques such as AlphaBeta() or MTD(f) and we wont be seeing machines with that kind of power in our lifetimes or even our great great great grandchildrens lifetimes.
 
warpus said:
There very well might be an infinite number of combinations of moves a player could make any given turn.

WRONG! Sorry, I had to. :p
 
Deep Blue had a lot of custom-coding written specifically to defeat the best chess players in the world - it wasn't "general" rules like "middle squares are stronger". I wouldn't even be surprised if they collected transcripts of previous games to exploit Kasparov's tendencies specifically.

And wasn't there a rematch where Kasparov changed tactics and won? Computers aren't real good at that yet (adapting)...
 
Lord Olleus said:
Why?
Because everything in civ is finite, and their is no way of getting an infinite number using only finite number (I refuse to discuss division by 0);)

I've been thinking about this and I think that you might be right about there only being a finite number of possible scenarios at the end of each move. After all, that's all that matters, right? -> What the board looks like at the end of the move. You could in fact perform an infinite number of moves (trade coal for oil, cancel, trade, cancel, trade, cancel, etc.), but the only thing the AI would be concerned about is the state of the game at the end of the turn.

The question is, would we have an infinite number of possible states, or finite? It's likely finite, but keep in mind that randomization is a part of the game.. which means real numbers.. which could mean an infinite number of states.

In any case, none of this really matters - it's impossible to build a viable decision tree even if there's a finite number of states at the end of each turn.

Warpus is entirely right in his post above. Civ4's gametree expands far too fast for techniques such as AlphaBeta() or MTD(f) and we wont be seeing machines with that kind of power in our lifetimes or even our great great great grandchildrens lifetimes.

A quantum computer would be able consider every single possibility at the same time.. making chess-like AI viable for Civ. Not really sure how far away we are from quantum computers, but I'd be surprised if it didn't happen within our lifetimes.

edit: added 2nd part of post
 
The only thing which is close to infinity in the game is unit health. If it was stored to an unlimited of decimal place then their is no limit to the different amounts of health a unit can have. However i think that the game stors it to 3 dp. Everywhere else where randomness is used, it is to decide, in a list of predetermined outcome, which one is chosen.
 
While Dusty Monkey may be right that no exhaustive search algorithms will be used for civ in our lifetime, having rules still involves searching. The trick is not to make the rules specific to each situation. It is to make the whole set of rules optimal. This is something that the AI developers can improve without increasing CPU requirements. And the improvements can be dramatic! Having an explosive increase in the number of decisions that can be made is thus not a good excuse for giving us a crappy AI! :lol: In fact, once the SDK is released, I am sure that someone will apply standard machine learning techniques to build an optimized rules data base - or perhaps even make a neural network!
 
The main reasons are the following :

1. Complexity
Civ is a lot more complicated than chess.

2. Available data
Unlike Deep Blue, civ AIs don't have access to a database of thousands of games played by world champions, especially before the game has even been released.

3. Time
Chess AI has been worked on and improved upon for decades.

4. Money
When you produce a computer chess game, your #1 priority, and therefore the place where most of the company's money is being directed, is the AI. With a game like Civ, the priorities are graphics, design and sound. Very little commitment is being put into making a decent AI. There just isn't enough monetary incentive for companies to produce a good AI.

Any single point above would be sufficient to explain why a Civ AI can never be as good as a chess AI. In this case, all 4 apply!
 
Lord Olleus said:
The only thing which is close to infinity in the game is unit health. If it was stored to an unlimited of decimal place then their is no limit to the different amounts of health a unit can have. However i think that the game stors it to 3 dp.

Unit Health (hit points) are an integer from 0 to 100, and run as integer variables.

Unit Strength is run as a Float, but it is simply (Base Str * (Hit Points / 100)) * (Sum of modifiers such as promotion bonuses, fortify bonus, etc)


- Sirian
 
Also, i would like to add that Deep Blue would make an absolutely horrible Civ player, even if you worked on it for a full year. The kind of AI needed in each game it completely different. Deep Blue uses mostly databases of previous games, and a brute force approach. Both of these would be pretty much useless for Civ, which is much better served by an AI using a a set of rules, which is a lot closer to expert systems (for example, those used to provide a medical diagnosis).
 
Tom183 said:
Deep Blue had a lot of custom-coding written specifically to defeat the best chess players in the world - it wasn't "general" rules like "middle squares are stronger". I wouldn't even be surprised if they collected transcripts of previous games to exploit Kasparov's tendencies specifically.

And wasn't there a rematch where Kasparov changed tactics and won? Computers aren't real good at that yet (adapting)...

In fact the IBM Deep Blue team worked with a team of Grandmasters (one of them was the german GM Christopher Lutz) on the openings Deep Blue would play against Kasparov. If you've followed the contest you may know that Kasparov only lost the first contest because he made some quite astonishing blunders compared to his amount of skill. I guess he could beat the AI still in any given time. Sad thing that he has retired...

Even a chess AI is not able to play like a human would. The modern chess AIs are terribly strong in tactics and have gained some ground on strategy - but still cannot counter some plans and ideas a skilled player can find. Of course they are playing better than 99.9% of all the chess players - but that's not a big difference to Civ IV... :D

LT
 
I've posted the history of chess AI many times on this site, so I'm not going throught the whole song and dance. The chess/AI debate began in the late 1960's when a chess master (not a world class player like a grand master) named David Levy made a bet that no computer could beat him in 10 years.

Programmers laughed. They were sure they would have the world champion soon. Of course, 1978 passed and they weren't even close. It would take another 15 years!

Building a chess machine that could beat humans was a HUGE priority for the computer industry. I was at an AI convention in 1985 when one of the speakers said, 'The best thing that could happen to our industry is to build a program that could beat the world champion at chess.'

Literally MILLIONS of dollars ahnd programming hours were spent on it. Computers like Deep Blue (Hydra now is better) that do NOTHING but play chess! Openings were typed in, databases, etc.

So, for chess, the programming/computer industry built a computer that good as a means unto itself. It was not done for any sense of cost effectiveness. NO computer game amnufactuere can put ain anything close to the kind of resoureces IBM put into Deep blue and the other programs, let alone all of the work done at other companies.


And, as people have said, chess is a relatively 'easy' game for a computer . CIV IV would be much harder.

Best wishes,

Breunor
 
Status
Not open for further replies.
Top Bottom