Could Deep Blue play a smarter AI ?

[jcikal]

I was at an AI convention in 1885 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.'

1885? If they were discussing AI that far back, we're in deeper trouble than I thought

Seriously though, I sure hope we can "improve" the AI once the SDK is released. That would bring good longevity to the series.

 

[pholkhero]

I think all those people at that 1885 convention are now working on QA for Take 2 ~ 100+ years for a good chess program, "a few weeks" for the new patch...makes sense to me!

 

[Breunor]

1885? If they were discussing AI that far back, we're in deeper trouble than I thought

Seriously though, I sure hope we can "improve" the AI once the SDK is released. That would bring good longevity to the series.

Don't you guys know I'm older than you?

Thanks for the correction, obviously its 1985.

(I'm still older than almost all of you!)

Best wishes,

Breunor

 

[NapoléonPremier]

All of this is interesting.
However, most of the posts don't really answer my question. I can see why you can't program the Civ AI like a Chess AI with a possibiliy tree and all. But my real question is : with more or less unlimited hardware and financial resources (so not for a general commercial release), would it be possible to get a really smarter, almost human-like AI ? Some people, like Jeremiahrounds seem to think that yes, inevitably. And apparently others, like Warpus (very good analysis btw) seem to think that no, not really, due to the intrinsic nature of the route that has to be used to program a Civ-like AI.

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".

But then :
- As you mentioned, the dawning of quantum computers seems very promising as far as almost unlimited brute force capabilities go. Although still more or less conceptual as yet, they may very well become a practical reality soon - maybe in the next two or three decades.
- Even with the necessary "set of rules" instead of "possibility tree" type of programming, do you really think that having massive computing power like Deep Blue or equivalent and dedicated in-depth programming (just as an experiment, remember, not for general release) would still make it impossible to get something like a "smart" AI ?

 

[NapoléonPremier]

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.

One thing we should probably never do with science is say : "that's never gonna happen ; it can't ; it won't."
If you had told folks in 1900 than less than 70 years later men would walk on the moon, they would probably have laughed at you. Or at the beginning of World War II that about five years later you would be able to destroy a whole city with just one "atomic" bomb, same thing. And so on.

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...

Since that match against Kasparov (which, it's true, he lost mostly due to the stress of the event), there has been another series with Russian grandmaster Wladimir Kramnik, one of the top best in the world. Although Kramnik won on the whole, he said that "it was extremely difficult", and that Deep Blue was "a fearsome opponent". Right now, it's true that humans (at least the few best of the best) are probably still better than the best chess AIs. But only by an inch. And the general consensus amongst chess & AI experts is that if the same amount of time and money keeps being invested in improving the chess AIs, within the decade, it's very likely that no human will ever be able to beat them again on a regular basis. Then, they say, you might have chess competitions between AIs, in the "first league", and then in the "second league", the current competitions among the poor human grandmasters... Or as somebody put it : "once you perfect the automobile to a certain level, you still can have foot races, and it can be fun, but you can't reasonably have races of human against machine to see which one is fastest..." ****in' Skynet is on the prowl, I'm tellin' ya... Dont you see ?!? We gotta do something, for ****'s sake! We're all gonna die !!!

 

[jeremiahrounds]

I think civ4 escapes one of go's issues. Gos branching tree problem is aggrevated by the fact that there isnt any strong hueristics to evaluate boards. What i mean is the AI cant tell if what its doing is helping itself or helping its opponent.

Its not even a matter of putting up the best defence its a matter of "16 archers looses but 15 archers wins but nobody has made a rule that tells the AI that ahead of time". That would be the nearest translation of go's woes to civ4 speak. Civ4s issues are incremental. Thats a little better thats a little worse. But go's issues are in discrete revolutionary changes based on single events.

Its the difference between continuity (civ4) and extremely jerky functions that arnt continious.

Its key to understand that before trying to say civ4 is in Go's ballpark. Take a defence of your cities without knowing where an attack will come from. Each different configuration of units on the board is a vector. Certainly there is a best or a surface in n dimensions describing a best vector. However if you get away from the best by one archer your only incrementally worse without knowing where the attack will come from [here the probability of many different attacks results in smoothing]. Your off by an archer.

Thats why prior to starting wars we usually set up a reasonable pattern for our units then dont get to involved with figuring out which units go where. We know reasonable is only off by perfect from a bit. Contrast with once the units start coming at us we get really specific because we know that off by a bit might be loosing [but this is tactics and tactics is the least of the worries of a civ4 ai]


Go is much different. If your off by "an archer" in go then your defence will be loosing. Now before anyone gets to hasty there is a key point here. prolly one flubbed in my language but not really undermining my gist. In that is this: In go a human can see the loosing configurations. In civ4 a human cant see the loosing configurations prior to the conflict starting. Defenses are inherintly undefendable.

This is a remarkable fact. Before a war starts a human cant really see when one archer difference in civ4 will result in loosing the whole empire. You might very well be able to construct them however nobody can see them ahead of time. However in go people can see them! But people dont know how to tell the AI to do what humans do.

And thats a little bit like the woes of trying to make logic that can spot a letter in noise. Its very hard to do but the human brain makes it look easy in ways that we cant put into logic. Thats whats going on in Go games. The human brain can spot loosing configurations however we dont know quite how to tell the AI to do it.

Now civ4 might be different if every player had perfect information. Its actually the lack of information that keeps the AI from being at to much of a disadvantage to humans. However even though there would be marked gains in the humans advantage of learned intuition if the entire board was always revealed i think the breadth of information might be overwhelming.


This disadvantage really doesnt exist in civ4 position considerations though. Ehh off by an archer. who knows? Make a reasonable defence and wait for someone to show their hand.

So anyway just saying go has a huge branching factor is only half the problem in go and the only problem that it really has in common with Civ4.

And lastly the learning the AIs tactics and exploiting them is a whole different set of problems. The reason is exploited tactics have obvious avenues of patching with unlimited resources.

One might argue that the AI is already very good relative to humans if humans patch the way the AI gets exploited everyday. In this idea we note that the way we approach beating the AI is by predicting what it has done. However if a human is working daily to review games and pull that rug out from under your predictions then you would find the AI much more challenging without much evolution. Someone else can argue that this might just be you playing the human at a metagame where civ4 is only a game piece in the struggle.

Perhaps but i think the quickest way to frustrating players is to simply work on the AI being less predictable. In this capacity im kind of disrespecting how good players think they are. I think we typically map out a set of expected behaviors out of the AI and play the expectations. And thankfully the AI never gets to far from that. But the reason that option is even available to us is fraxis thought a predictable set of personalities would be more fun then a pure wanton player destructions.

So anyway yes im bullish about civ4s potential. And lastly at the human level i just dont see how anyone can reasonably say that an AI that is NOT the result of competition amoung various AI approaches over time is anywhere near best. That would be remarkable.

Thats not to say again that this isnt fine engineering. However i think people overestimate how hard civ4 is based on the workings of one or two people taking their first stab at a civ4 AI and releasing it. When really when you talk about AIs that represent the max theoretical potential your talking about AIs that get worked and challenged and reworked. I would go so far to say that they are kidding themselves if they believe the AI in civ4 is equal in achievement to the best GO AIs. But how to know without objective measurement and competition?

 

[Zombie69]

with more or less unlimited hardware and financial resources (so not for a general commercial release), would it be possible to get a really smarter, almost human-like AI ?

Not with the current advancement of AI technologies. When the science of AI has made quite a few more steps forward, and new AI programing methods have been invented, then yes, probably. But we're just not there yet.

However, it would be really easy to do better than the AI we have in the game now.

 

[Breunor]

Chess vs. computers

Throughout the late 90's, the chess computers had caught up with the grandmasters, really, with one exception -- Kasparov. Deep Blue really just wasn't there.

Deep Blue and Kasparov basically were about even in their three matches. Unfortunately for the chess world, though, Kasparov really isn't as good as he used to be. It wasn't the same Kasparov. So humans had a powerful claim.

Regardless, the new computers like Hydra are really invincible. They are now way beyond even the best players. Adams just got smashed by Hydra. Its not really a contest any more. Even Kasparov at his best couldn't handle it.

Best wishes,

Breunor

 

[megalomaniac]

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.

The idea of a chess AI has been going on a little longer than that. Here is a rather interesting read on the subject.

 

[·Imhotep·]

Chess vs. computers

Throughout the late 90's, the chess computers had caught up with the grandmasters, really, with one exception -- Kasparov. Deep Blue really just wasn't there.

Deep Blue and Kasparov basically were about even in their three matches. Unfortunately for the chess world, though, Kasparov really isn't as good as he used to be. It wasn't the same Kasparov. So humans had a powerful claim.

Regardless, the new computers like Hydra are really invincible. They are now way beyond even the best players. Adams just got smashed by Hydra. Its not really a contest any more. Even Kasparov at his best couldn't handle it.

Best wishes,

Breunor

I'm not so sure about that. I play chess myself in a club and have around 2000 Elo, so compared to an IM or GM I understand nothing of chess. But if you have observed the results and the play of both Kramnik and Adams you may well say that they were out of their form when the contests vs. the AI took place. And Adams is a wonderful opponent for an AI chess program anyway - his strength against humans results out of his doughtiness and his skill to create the maximum amount of problems when facing a difficult position. It has a lot to do with psychology too because everybody knows Mickey for these skills. An AI chess program is totally unaffected by psychology and emotions and thus is very likely to win a winning position, which sometimes doesn't happen for a human player just because of emotions and psychology. So I would state that the Adams contest isn't much of a proof for the advance of chess AI over human players. More interesting is it that Kramnik could beat the program and was not in a good shape. Well, his playing style is just perfect against a chess AI program.

I'm not so convinced that Kasparov couldn't beat Hydra too. I'm still hoping that Kasparov will return to professional chess, but it's not very likely. He has had a retirement in grand style with winning Wijk an Zee (or was it Linares ?) without any major problems. You have to admit that the challenge human player vs. chess AI is very much like human player vs. Civ IV Deity AI. The chess AI gets a huge amount of advantage, otherwise it would be much harder to stand a chance. First of all all these programs are running on especially chess fitting designed ultra high end computers. Hydras strength results to a great amount on its hardware architecture. It's not mere processing power but the way the modules work and interact that makes Hydra quite strong. Run any of these programs on a normal PC and an average GM will not have great problems with it - at least he won't lose. Second thing to consider is the amount of data that the machines have available. In all these contests the chess AI had not only a great opening book stored, but an opening book especially designed for the current opponent, in most cases with stored values of variants. Big advantage for the AI. Third thing one must have in mind that on all these players who face a chess AI in a public contest lasts an immense pressure. This "I must defend the honour of mankind" - thing is a hard psychological pressure. It even worked on Kasparov and resulted in some blunders which cost him games and the contest.

Concerning Civ IV I would say that in my opinion the AI plays quite good compared to the amount of information it has to consider. The whole game is so broad - from settling choices to military and diplomatic aspects, not to mention trading - that it takes a lot of thinking to find good decisions. A human player can adapt his playing style to the given situation, and that is a big adavantage over any AI nowadays. It's just impossible to hardcode rules that fit for most of the situations that can arouse in a Civ IV game. Of course the AI would play better if it would ran on an especially designed hardware setup - but without any advantage it still wouldn't be able to beat the best humans, I think.

Regards,

LT

 

[vinstafresh]

I don't think it will be possible...

Chess has a fixed board (8x8), fixed units with fixed moves, fixed game mechanics and most important of all no luck/randomness. A pawn will always defeat a queen if the pawn enters the square of the enemy queen.

In chess the entire outcome of all moves can be predicted precisely and thus the best moves can be calculated by following the tree of possible moves (like was stated earlier).

In civilization only the strategies can be thought out and modeled. For every strategy the AI uses now, the player can think of a counter-strategy. In SP, this can be AI-exploits, to which the AI always reacts the same and digs its own grave doing it. In MP, players come up with a counter-counter-strategy, etc. 'Come up with' implies creativity, which a computer is not capable of.

With limitless resources, money and perfect technology, I do think that for each patch the AI could be improved. There are more strategies thought out, AI-exploits are discovered and can be countered by the programmers. So after each patch, the AI gains more experience (and demands more resources for the bigger decision-trees it has to explore). The adaptation which human players can do instantly needs to be programmed in order for the AI to learn.

 

[Dusty Monkey]

In all these contests the chess AI had not only a great opening book stored, but an opening book especially designed for the current opponent, in most cases with stored values of variants. Big advantage for the AI. Third thing one must have in mind that on all these players who face a chess AI in a public contest lasts an immense pressure.
LT

I think you are looking at this rather one-sided.

Anti-computer chess techniques have not only been around for ages, even Kasparov *exploited* these techniques vs Deep Blue. Keep the position quiet looking to shore up positional advantages in the middle game which wont manifest themselves to the A.I. until the endgame, where its too late to use its endgame tables because its a forced loss.

Hello lovely horizon.

When the position got complicated, Kasparov always croaked. He resigned a won position on (I think) game 6 too! He got psyched out by silicon! The reality is his anti-computer strategy had crumbled several dozen moves previously and inspite of winning on the board, he *felt* he had lost so he resigned.

 

[Aldor]

Well, I think that currently you can not make a superb CIV AI, even with a lot of resources. But you could take a lot of single aspects of the game and make them better, and the end result would be a stronger AI. Some aspects that can be worked on:

- city micro management (population management): this is just number stuff, perfect for computers. The governor right now is OK, but we all usually turn him off at higher levels, because we can do better. Better algorithms, some extra rules and/or more calculation power could make the AI equal to human here, or at least very close.

- city placement: who uses the blue circles? It seems quite simple, a better algorithm, using some extra rules should do a lot better.

- worker AI: I think this would be fairly easy to improve. Right now, one of the weakest aspects of AI civs.

As you see, I suggest only areas which are - more or less easily - computable. By focusing on such things, I believe the current AI's could become quite a bit better already. Other things like "strategy" or "goals" however are much harder to improve, so I have some doubt that there will be major improvements any time soon.

 

[warpus]

like Warpus (very good analysis btw) seem to think that no, not really, due to the intrinsic nature of the route that has to be used to program a Civ-like AI.



But then :
- As you mentioned, the dawning of quantum computers seems very promising as far as almost unlimited brute force capabilities go. Although still more or less conceptual as yet, they may very well become a practical reality soon - maybe in the next two or three decades.
- Even with the necessary "set of rules" instead of "possibility tree" type of programming, do you really think that having massive computing power like Deep Blue or equivalent and dedicated in-depth programming (just as an experiment, remember, not for general release) would still make it impossible to get something like a "smart" AI ?

Thanks.

To clarify my position: A decision-tree like AI would be pretty much impossible for CIV unless we get to play with quantum computers. It'd be possible once those are around, imo. And I'm not just talking about a quantum computer with a couple registers, I'm talking about a full-blown personal quantum computer mark 3.

The faster hardware gets, the more time we can allow for the computer to think in between turns.. This gives the developers a lot more flexibility. It allows them to examine more variables before the AI makes its move. So yes, as hardware gets faster, the AI SHOULD in theory get better/smarter. I think that a lot more is possible with the current speeds we have to work with, but if you look at the progression of AI from civ to civ4, I hope you'll agree that we've been making progress, generally.

Humans don't use a decision-tree approach to solve problems though - we use the neural net we have in our head. Somebody in this thread did mention a neural thread approach.. To be honest, the last time I read about neural nets was 5 or so years ago, so I'm not quite sure how far we've gotten with that technology.. but from what I remember we were making some pretty interesting moves forward.

A neural net would require a lot more complicated code than what is being used now, for the AI. Sure, it's easy enough to set up a neural net, but to build one specifically designed for a game with very specific rules, would be hard. How do you weigh the neural connections? How do you quantify whether move A is better than move B? It's hard to do in a game like civ; you'd often have to wait many turns to see which move was more beneficial - this implies a decision-tree like AI.

Damn I'm tired! I hope all of this makes sense

 

[vinstafresh]

We make decisions based on real life experiences, experiences in other games and we have a different perception of what we see than an AI would have. In this we have a major advantage off the bat, which cannot be programmed (deep blue has a book of openings stored somewhere apparantly). The only disadvantage a human player has is that we cannot think through thousands of possibilities in the blink of an eye. And like someone else already said, AI lacks emotion. It will not backstab, be angry (and makes rushed decisions), be eager (and has increased concentration and brainpower) or feel pity and have his/her actions be influenced this emotion.

 

[Upright]

To my recollection - Kasparov won Game 1 in the series loss to Deep Blue.

Infact it was a surprisingly easy win - which is why Game 2 caught him offguard.

The thing is Deep Blue was changed from game to game in that series - giving it a different playstyle each game. Kasparov wasn't prepared for playing against 6 different opponents - and was conviced that the dramatic playstyle between games 1 & 2 were down to human intervention. A point he came back to frequently in his press confrences after subsequent games.

Basically he lost the plot during/after game 2.

 

[d80tb7]

NapoléonPremier almost answered his question in the first post. The AI in CiV 4 is better than in CIV3 which is better than Civ2 etc etc. All that has changed in the mean time is (a) the hardware has got better and (b) the coders have had more time to improve the AI. If in 1990, when CIV 1 came out, we had given Microprose (as was) the very best hardware available at the time, and 1000 of the world's top programmers and told them to work soley on a Civilization AI then I'm sure they could have come up with something at least as good as the CIV4 AI within a year or two. Do the same thing today and I'm sure you'd get an AI of similar ability to that which will appear in civilization games 10 years from now.

The question is then whether this 'civilization 10' AI would be any good. Here are my predictions.

1. If you put the average civ player against the AI, they would struggle to consistently beat it within a reasonable amount of playing time (say 1 game a day for a few months) so long as they were not allowed to discuss their tactics with anyone else. I base this on the assumption that many people on this forum would find playing CIV4 at noble fairly challenging if they had to independently discover tactics such as chop rushing, cottage spamming etc.

2. If you released the game generally then the good players would be able to defeat it. These players would post their methods on forums such as this one and lesser players would pick up tips (much as we all do at the moment). As I doubt that this new AI would be able to adapt its tactics, soon everyone who was willing to read the forum and put a bit of time in would be able to beat the game.

As an aside to this, it would be really interesting to see how long it would take the average gamer to beat CIV4 at nobel if they couldn't discuss tactics with anyone else.

 

[Pawel]

I think you guys are on the right track, but you vastly overestimate the level of the Civ4 AI. Im not complaining, but you forget that the amount of work that goes into any real AI project is immeasurably larger. The Civ4 AI probably has considerably less than one man-year of effort put into it, and overall probably isn't smarter than a push-free vacuum cleaner. And it will never get much better simply because it is good enough. Spending money on games that have stable conditions (like chess and go) is bad enough (modern chess programs are not fancier than Deep Blue - they just have more brute force), but how can you justify it for a game that has a limited shelf life?

Now, would a better AI be more difficult to beat? That is not a given. I think the main objective of the AI is to punish simple strategies that lets the human player win with litte effort. A more flexible AI that understood what was going on would maybe let you win - but you would have to work much more to do so. And this is very much like in real life.

Thus the main objective of the Civ4 AI (even the current one) is not to calculate the probability of achieving a certain type of victory, but to try to respond to circumstances in what appears to be a reasonable way. This is a much greater challenge. There are, however, very advanced techniques to deal with this type of interactions in much more complex environments than that of Civ4. But they are costly, so we can't expect them to appear unless some enthusiast with a degree in computer science and civ4 as a hobby actually implements them!

 

[cabert]

my 2 cents:
I don't want an AI that beats me to dirt.
SO what is a GOOD AI?
In my opinion a good AI is one that adapts somehow to your playing level/ the level you chose. A good deal of the players don't want a tough challenge. Many like to win with only half backed strategies!

I'd like the AI to look at how you're playing and learn from it above certain level (noble should be where the scale tips). It sounds very difficult but in fact isn't.
What actions come often (like every game)?
What goals are pursued, and what are the common actions when pursuing those goals? When i say goals, i mean victory conditions/relations toward a specific AI. I think the AI should know when you're going to attack, the same way you know the AI (personnality dependent) is going to attack.
Of course, that means a database of your playing style is constructed on your hard drive, used only by high level AI, with numerous information, used or not depending on the level.
For example, the AI could remember what stacks you used the few last games, when you attacked. And he could use this to build his defence even before you attack on higher levels. Of course you can trick it, but just like you could trick a human player. Much more predictable still, since you could know what it knows, unlike human players where you must look hard to see if the guy knows you, and adapts or not.

 

[Azash]

Cabert, I think there is already a game that adapts to your skill. Forgot the name, but I think it was a pretty popular game.