Could Deep Blue play a smarter AI ?

[dbergan]

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.

This comment needs a little perspective. If in the 1600s you had said (as many scientists did) that you would never get gold from lead via a chemical process you would have been right. Later on we found out that both gold and lead were elements. Science isn't magic. It can't do everything.

 

[Breunor]

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.

Its also important to remember that Kasparov wont he first match with deep blue. When the second match turned, it was big news -- however the first match seems to be 'forgotten' by non-chess players.


Best wishes,

Breunor

 

[Dusty Monkey]

- city micro management (population management):
- city placement:
- worker AI:

All of these require strategic knowledge and are NOT easily computable as you suggest.

If I am in error, please at least loosely define an algorithm for one of them.

 

[Azash]

Mine green, irrigate brown (Or reverse, I've forgotten ) shouldn't be too hard.

EDIT: Oh sorry, it's the CivIV forum. Well, there's usually an optimum thing to place on any tile, and one could program the game to check what would be the most useful improvement at any given time.

 

[dbergan]

I think there is one thing that people are overlooking... the amount of time it takes the AI to make a move. Currently it is programed to do a civ's turn in under a second (most of the AI's time is updating the graphics on our screen... when you don't see a civ, their turn is over almost immediately). Computers have the processing power to do more, but do players want to wait? Are we willing to wait 10+ minutes for a good move like what a chess program does on its top settings?

 

[Breunor]

Hi Timon!


I thought I already posted, did it get deleted -- sorry if this is a double post.

I guess I'm a little more negative onthe humans vs' the computers. You are a little better than I am at chess (I'm 1820 right now) -- I bet I'm a little older but don't know that for a fact. Its good to see some other chess-players here!

I do go the Manhattan chess club, and even the GM's view that Hydra has passed them. Right now, I think its rated between 3000 and 3100. Kasparov at his best was what, about 2850?

I agree that he modern computers like Hydra may be 'cheating'. As you said, Hydra on a Pentirum III and it may have trouble with an IM. They have computers now built specifically to play chess!

The 'cheating' part comes from simply typing in opening books. Should humans be allowed to bring opening books?

Noentheless, as a 3000+ machine, I think its passed where humans are now.

And, at the end of the day, it doesn't matter. Computers will still get better yet. Kasparov held them off in the 90's. Maybe a Botvinnik, Kasparov, or a Fischer will still be a little competive, but as done now, chess AI has passed humans besides possibly people in the greatest palyer of all time debate. And, as I said, computers will still get better, but I don't think humans will be a lot better than Fischer or Kasparov.

Anyway, that's my take!

BTW, Andy Soltis I know was shocked at how easily Adams was defeated.



As an aside, (this maybe belongs on a different thread, sorry!) people ask me about chess vs. CIV. Its hard to answer -- I don't know myself. To me they are totally different experiences. Now that I'm in my 50's the chess scene is a little more recreational. How do you view this?

Best wishes,

Breunor

 

[5cats]

The amount of factors in Civ4 vs Chess are exponential. As was mentioned, Chess has a small board, limited pieces and one move per turn. Although 20 turns may have millions of possible outcomes, in Civ4, in mid-game, 20 turns would have millions to the power of millions of outcomes. (ie- a whole whacking bunch!) Brute force wins in Chess, but not Civ4.
Or Go, which has more squares, fewer pieces but much more complex rules.
Try Diplomacy AI, remember how bad Avalon Hill's AI was? (shudder) in Diplomacy there's limited squares, small number of pieces and simultanious turns. WAY too much for the AI to handle.
Even with unspeakalbe Star Trek like computers (which allegedly use "quardrary" or 4 units rather than "binary" which uses only 2. That alone makes them exponentially more powerful) playing Diplomacy would be tough for a computer.
ALSO: think of a game (civ4 or Diplomacy) with 6 humans and 1 AI. As opposed to 6 AI and 1 human. Assume the humans can't tell which is which & you'll really see just how poor AI really is.

 

[5cats]

Oops, pressed Post insted of Advanced...
To continue Sentient Computers, the Holy Grail of computerdom, will simply never happen. Making 'wetware' ie- a copy of a biological brain, doesn't count! Even then, though, the software could never actually be sentient.
To summerize: Chess: 1 vs 1, no luck, limited board & pieces, very simple rules. Computers can cruch billions of numbers really fast & win.
Go: 1 vs 1, no luck, limited board & pieces, complex rules, computers cannot simply crunch numbers to win, so they lose.
Civ4, Diplomacy: 1 vs 6, luck, huge board & pieces, very complex rules, interaction with other players required to win (usually). Computers are whipped!

Although the AI can be improved, certianly, it'll never actually beat a top human player, except through pure luck. Even with massive computers, even with decades of software developement, not happeing.

 

[thordk]

no one has yet discovered what intellect is. what makes humans able to adapt to all kinds of environments with ease, solve completely unknown problems and so on.

some approaches to ai try to immitate how the human brain works. there has been AIs who have been trained what has been thought to be the basics of human knowledge when they're born. after years of learning this AI had the smartness of a watery tomato.

but i'm certain that someday mankind will learn what makes the human mind (even if some say this isn't possible, based on gödel).

scientists of the past said the sun is revolving around the earth.
scientists of the past said it will never be possible to travel faster than 30 km/h.
scientists of the past said nothing can travel faster than light.

they all were proven wrong. noone can know what future scientists will develop. things that now look like they're proven impossible may be possible in some years.

 

[Dusty Monkey]

Mine green, irrigate brown (Or reverse, I've forgotten ) shouldn't be too hard.

EDIT: Oh sorry, it's the CivIV forum. Well, there's usually an optimum thing to place on any tile, and one could program the game to check what would be the most useful improvement at any given time.

ok, whats the optimum thng to place on a grassland? How about a grassland hill? tundra?

Even the "masters" of Civ4 disagree about how to put together a commerce city. I think everyone agrees that fast growth is essential.. but what beyond that? Should the plains or the grass get irrigated for the late game?

And it seems to me that your notion of 'optimum' is flawed because you neglect to specify the conditions which would lead you to believe that its optimum. Ie, an overall strategy or goal.

 

[Dusty Monkey]

The 'cheating' part comes from simply typing in opening books. Should humans be allowed to bring opening books?

Humans have been memorizing chess openings since long before any of us were born. It is silly to call it cheating when a computer does it, but turn a blind eye when a human does it. You need to make up your mind!!!

Maybe a Botvinnik, Kasparov, or a Fischer will still be a little competive, but as done now, chess AI has passed humans besides possibly people in the greatest palyer of all time debate. And, as I said, computers will still get better, but I don't think humans will be a lot better than Fischer or Kasparov.

Ok just so this is understood really really well I am going to say this all by itself in large letters:

Kasparov was *NEVER* the best at playing against computers. He was the best at playing against humans. There isnt an official "vs computer" championship but I think its well understood that of the top GM's, Kramnik is the best at demolishing computers - well above the ability of Kasparov in that regard

.

 

[·Imhotep·]

Hi Timon!


I thought I already posted, did it get deleted -- sorry if this is a double post.

I guess I'm a little more negative onthe humans vs' the computers. You are a little better than I am at chess (I'm 1820 right now) -- I bet I'm a little older but don't know that for a fact. Its good to see some other chess-players here!

I do go the Manhattan chess club, and even the GM's view that Hydra has passed them. Right now, I think its rated between 3000 and 3100. Kasparov at his best was what, about 2850?

I agree that he modern computers like Hydra may be 'cheating'. As you said, Hydra on a Pentirum III and it may have trouble with an IM. They have computers now built specifically to play chess!

The 'cheating' part comes from simply typing in opening books. Should humans be allowed to bring opening books?

Noentheless, as a 3000+ machine, I think its passed where humans are now.

And, at the end of the day, it doesn't matter. Computers will still get better yet. Kasparov held them off in the 90's. Maybe a Botvinnik, Kasparov, or a Fischer will still be a little competive, but as done now, chess AI has passed humans besides possibly people in the greatest palyer of all time debate. And, as I said, computers will still get better, but I don't think humans will be a lot better than Fischer or Kasparov.

Anyway, that's my take!

BTW, Andy Soltis I know was shocked at how easily Adams was defeated.



As an aside, (this maybe belongs on a different thread, sorry!) people ask me about chess vs. CIV. Its hard to answer -- I don't know myself. To me they are totally different experiences. Now that I'm in my 50's the chess scene is a little more recreational. How do you view this?

Best wishes,

Breunor

@Breunor:

Whew, Manhattan Chess Club ! This is one of the greatest clubs and by all I've heard a legendary one too. I would be glad to play in such one, but I'm only playing in a local town club. Still, I'm now the best player there, which has its pleasures . You're right - I'm way younger than you. I have not reached my 30s yet, though they begin to peep over the wall, as one might say .

At his best Kasparov was 2851 Elo I think, but Elo ratings are not a measure when it comes to the comparison between human and AI players. Of course Hydra racked up a 3000+ performance in the match vs. Adams, but Karpov and Kasparov had done that before too. Nonetheless you are right that on the uttermost ends of hardware configurations only the best 2 or 3 players in the world will stand a chance against the chess AI. And the opening books play a big role, as well as the designing or adjusting the machine on different opponents. In fact that's nothing other than human GMs do - they will prepare for their opponent too (which often results in those boring, home analyzed draws).

What brings hope to me is that the AI still can't see moves a true genius can play. Take Botvinniks bishop sacrifice (bishop a3) against Smyslov or any of those brillant moves Kasparov or Topalov have displayed. Some the AI can see, but some still not. It is the deep creative genius which will always bring up new ideas and new plans - a thing the AI will not be able to until it is really "intelligent" in the meaning of the word.

Comparing Civ IV experience to chess is a hard thing. I enjoy both, but I'm not really good at both . Still im more ambitios when playing chess, especially when playing on team contests. Civ IV for me is only a means of fun and stress killing - and a damn good one. I don't know if I would prefer Chess over Civ or vice versa - but luckily I don't have to choose and play both .

I'm glad to have met you here, chess players are always worth a discussion...

LT

 

[AutomatedTeller]

To beat Civ at the highest levels, you need to be either A) very good or B) stack the deck against the AI.

mainly the issue is that the AI isn't doing long-term planning - the AI's don't say "ok, I'm going for space race in this game" and they don't say "I hate Zulu, so I'm going to kill them" They are reacting.

That's one reason why Civ is infinitely harder to write an AI for than chess - there is one win condition in chess, which is checkmate. There are 7 win conditions in Civ3, so it;s very difficult to even know what the end game looks like.

If you put a bunch of PhD's and 2-3 years of effort into it, then yes - you could build an AI that blows away the current one. And it wouldn't really need to be deep blue - you could do it fairly simply by encoding a strategy engine, and a set of rules that are specific to strategies, such as "set up settler factory", and allow patching of those rules with new rules down the road. When I say fairly simply, I don't mean it's easy - it's a lot of work - but it doesn't have to be a supercomputer doing it.

That said, the expense of doing such a thing would cause the game to cost $100's and $1000's of dollars - and who cares? I mean - the game kicks new people's butt at levels above chieftain...

 

[dbergan]

Is the SDK going to allow AI manipulating? I think that would make things very interesting... could even get some AI vs AI tournaments going to see who makes the best script.

Now that I think of it, though, a 1v1 bot would be a different animal than a 1v1v1v1v1v1v1 bot. You could make a monster Julius Caesar AI to rule in 1v1 (small map)... but I doubt that it would win a long game with several opponents where some distant ones play for tech while he marches over his neighbors.

 

[warpus]

To continue Sentient Computers, the Holy Grail of computerdom, will simply never happen. Making 'wetware' ie- a copy of a biological brain, doesn't count! Even then, though, the software could never actually be sentient.

Why not? Humans are after all biological machines. What would prevent other machines (be it hardware or software) from being sentient as well? If nature can construct a machine that is sentient, so can we (assuming that we have the necessary technology, of course).

what makes humans able to adapt to all kinds of environments with ease, solve completely unknown problems and so on.

Our brains are incredibly powerful pattern matching neural nets. This is why we're able to look at a new situation and immediately relate it to other problems we might have solved before.

 

[Pawel]

Is this thread about chess or Civ? I think that many of the AI problems are quite simple. You just introduce several layers.

For instance, how do I improve the terrain for a city? Well, develop all resources and try to get at least two food from each square. That may not be optimal, but is good enough. What improvements should I build? See which ones give you the best ratio between invested shields and output (hammers, money, culture, etc). Sometimes it is even simpler, you just have to build an aqueduct for your city to grow. The AI does these trivial things pretty well.

You can then introduce a higher level of decision making with higher priorities. Where should I build my wonders? How do I connect my cities? Again, not very hard.

Then comes, what should I research? Well, picking the cheapest usually is not a bad choice. The real AI is much more refined. But again this is easy.

The big decisions are how to interact with the others. What does it mean that I see forces on my border? Should I attack someone who is overexpanding and probably is vulnerable? The AI rarely does this. It is bad in assessing who is the greatest threat, and tends to deploy forces evenly, not taking into account that it might be better to have more either at a central location from which it could reinforce a sector under threat using inner lines, or having more units where the threat is the largest to begin with. In forming relations it usually rarely shows a strategy. To simplify a little, it just dislikes its neighbors.

While I am not saying that it is bad, it is not really very advanced either, and could be improved very easily by adopting a better tree of rules, or by optimizing the hierarchy of decision making. These things are not very hard! They just take a lot of time.

I am sure that rather than adopting a more fundamental approach to developing the system of rules for Civ4, it was mostly done by rules of tumb and trial and error. To use, for instance, neural networks or some other optimizing methods is too time consuming.

But the result isn't that bad!

 

[warpus]

Pawel:

You're right, problems like "how should I improve this tile?" or "how many units should I have defending this city?" seem pretty trivial and probably don't really require advanced AI techniques to implement well.

What's hard to code is AI that is able to see the "big picture", and that's what's required to build human-like AI.

 

[Pawel]

Well, the AI doesn't have to be very human like. It just has to have an optimized set of rules. This optimization can be put in "by hand", or it can evolve during a learning process. During the latter the program makes some decision and receives feedback. This feedback is used to strengthen behavior that is successfull, and suppress behavior that isn't. Not too different from humans, perhaps, but one has to remember that we have a very different interpretation of what is going on. We see civ as symbolic of an extremely complex world history. The AI doesn't care. Its world is much simpler.

Now, this learning process can be done in advance, or it can be improved continuously. I bet, however, that in Civ4 it wasn't the AI that did it itself at any stage. It was the programmer that saw if a certain choice of parameters worked, and if not, they were adjusted a little. This approach is good in getting something to run quickly, but it never finds the really good solutions...

 

[warpus]

During the latter the program makes some decision and receives feedback. This feedback is used to strengthen behavior that is successfull, and suppress behavior that isn't.

That's fine and dandy, but how exactly do you quantify how successful or not a decision was?

Even if you had a human sitting at the computer and adjudicating every single decision that the computer made, you still wouldn't be able to quantify the success rate of certain decisions. Sure if "move warrior from [52,44] to [53,44]" and "there is an enemy swordsman in [53,44]" results in "warrior dead" that's easily marked as "BAD, don't do this again".

But what about something like "move knight from [11,20] to [12,21]". Nothing happens. Was this a good move or a bad move?? If you adjudicate it to be "good", does that mean that the computer should make more diagonal moves with knights?

Some decisions just don't make sense unless viewed in a larger context - the "big picture". Humans are reallllllllllly good at finding patterns in things - this allows us to make sense of the big picture. Computers are horrible at it. Assigning a 'weight' to every single decision a computer makes might sound like a good idea at first, but then you start realizing that it just won't work (in this case anyway)

 

[Pawel]

As you say, it is not the details that need to be evaluated. Certainly, it makes sense to approach a city from, say, a forest rather than open plains, but moving troops around isn't really that challenging. Much more important is to decide what mission to give them (attack city, pillage, etc). This the AI does reasonably well. More difficult is to, for instance, coordinate attacks. However, as you point out, the main flaws lie in the high level functions.

There are seveal ways of developing systems for evaluating success. One is very natural. At some high level the AI adopts a strategy. It can be "let's take that city", or "I want to be the first to finish wonder x". Then it sees if it succeeds using a certain approach, which is chosen from a set of strategies at a lower level. It knows when it fails. Now you just have to implement a learning step so that it is less likely to do the same thing again.

There is also a higher level, "which goals should I choose", but basically it works the same way. Complex problems usually appear insurmountable only before you start breaking them down. Now, the implementations of different learning strategies can vary, and there is a lot of work in the details, but there is no magic! Nor does it have to involve as many brute force searches (limited by CPU time) as in a deterministic game like chess.

EDIT: Again, note that learning doesn't have to be done at runtime. You can just use it to optimize your parameters. By the way, have you ever played 20 questions?