Brute Force AI

[smalltalk]

Consider chess:

8 x 8 grid
6 different units
32 units max

These days, only the very best human players are able to stand up to a computer. Chess computers do win by brute force and not by sheer intelligence.

A chess computer does a lot of number crunching, calculating as fast as it can, each and every possible move, ruling out the bad ones according to some preset weight function. (i.e. a bishop is about 3 pawns; holding a center field is more valuable than an off-center field).


Now consider Civ

a horribly BIG grid
awfull LOTS of different units
TERRIFYING lots of units max

might there ever be a brute force AI ?
(given fast enough computers)

implementing difficulty levels as calculation depth ?
implementing civ traits as different weight functions ?
i.e. (barracks + 3 swordsman) > (temple + settler) for military civs

or would it be more like the chinese game of GO
where there is still no computer program available to outplay man.

(Uhm, I bet, I could do as well as Deep Blue and Deep Fritz, if I was given their algorithm and enough time

 

[stormbind]

I play chess and have a rating of around 1500. I hate brute force!

The problem with brute force is that it is blind to patterns, but the human mind is tricked into repeating patterns... so when thinking five or six turns ahead, your brain fails to see all the possibles and repeats known moves from memory.

At least that's my view.

I prefer playing computer opponents that use a library of moves and very little brute force. This is more fair for most human players, and it's less stress on the computer.

Using libraries, a Commodore 64 can beat most grand masters with only a short time (several minutes) to think, so clearly processing power isn't that essential.

It would require a little "fussy logic" to get a Civ3 to work as well, but the engine would only need to be written once.

I have no idea what the AI is like in Civ3 atm, it may already be superior to what I am suggesting... doesn't feel it though.

Edit: I was thinking in terms of pieces and battles, not resource management.

On second thoughts, it wouldn't work for Civ3. The pieces don't move in set ways, so it does need brute force to check all possibilities.

My bad!

 

[Illustrious]

@smalltalk: I think your mention of Go is pretty important. There is only one type of piece in the game (well, two if you count black and white), so the complexity arises solely from the positional combinations possible. Since no-one yet can build a brute-force paradigm to win at Go, it seems likely that Civ3 will also hold out - imagine a game of Go where every counter could be one of a dozen or so different types with different abilities...

Pattern-recognition seems a more likely way to go.

@stormbind: I have only just noticed your signature. You're right, that will have to go! I suggest something along the lines of "Memoria mihi benigna erit, qui eam perscribam".

 

[bike]

Compared to chess (and even go) there is a huge other difference with Civ, being that chess is a game where all information is available to all parties. In Civ not all terain is visible all the time, and (maybe even worse) outcomes of battles are dicided by dices. That won't work with brute force.

However, there is much improvement to be expected with AI if it would use plans instead of going for the best moves every turn. This could work for workers, so that they improve tiles in a proper order, it could also work for wars, when, instead of running towards the least defended city each turn (with the human moving defenders in and out), the AI decides, I'm going after those 2 cities, I expect 2x4 spearmen, so I take 10 swordsmen, and that should to the job. (And if it is on another continent, don't come with 2 swordsmen at a time )

Of course that involves a quiet different approach for programming AI, but it sure would make gameplay more challenging. In civ VI (or AC II) I prefer less graphics, and more AI.

 

[china444]

This is the most confusing thread Ive ever read.

 

[ssmith619]

I think that it is theoretically possible for there to be a brute-force Civilization AI, however I think that it would have to be incredibly complex. Even programming the damned thing would take far longer than it took to program the AI in the original game. Think about all of the variables, not to mention the fact that the AI doesn't (or at least should be programmed not to) know much of what is going on. Even thinking about how one would go about doing this is mind-boggling.

Even if you got past the logistics, imagine the sheer amount of power needed to run this thing. Just think about how long it takes in between turns. Sure, there is a small amount of graphics processing done, but most of it is done behind-the-scenes so there are no graphics calculations involved.

Just thinking about doing this is giving me a headache.

Maybe a computer could program it? You know, sort of like that computer which programmed the four-color proof (I know it's difficult, but computers can be programmed to do intelligent things like proofs) where a computer proved that it is not possibly to make a map that requires more than four colors so that no two colors are adjacent to each other.

Quite the thought-provoking idea, you have proposed. ;-)

 

[sumthinelse]

Originally posted by stormbind

I prefer playing computer opponents that use a library of moves and very little brute force. This is more fair for most human players, and it's less stress on the computer.

Using libraries, a Commodore 64 can beat most grand masters with only a short time (several minutes) to think, so clearly processing power isn't that essential.

I believe you are mistaken if you think a human or computer can beat even a master (let alone grandmaster) without brute force. If you don't believe me, take all the books you want to use as reference and try to beat a human master (armed only with his limited memory of openings, no books). You will reach a position that is beyond your books and your understanding (as a player rated at 1500). Of course, I wouldn't be able to beat a master either.

 

[Mathias]

Originally posted by ssmith619
Maybe a computer could program it?

Deep Thought could do it.
Forty-two kudos to those who get this.

 

[china444]

Forty Three Kudos to whoever did this. I never really pay attention the the science formulas, I just pla ythe game.

 

[smalltalk]

stormbind:

the asthetics of computer-strategy is - well other than ours.
I have seen striking AI-moves (ouch) both in civ and chess. And dumb foolishness besides.

Computers get to the same goal (winning) by totally different means.
But also a pocket calculator can calculate faster than me and still I'm better in math.



Illustrious:

I guess, in GO it is very hard to judge whether a move is a good one or not - at least if you are a computer and do not at all understand what is going on. In Chess, a computer can just add up material advantages. But if it comes to rating the subtleties of piece-positioning, the computer is somewhat lost.


Bike:

Oh, I completely forgot about the randomness involved. So no brute force AI with todays rules.

(I have to admit, deep inside I do favour a non random combat system. Everything cause-and-effect, like in Chess. And does anyone remember the first Civilization board game ? There was only rolling dice when there was a tie.)

About the fog of war and hidden territority: the AI does know about it all beforehand and is just kind enough not to use it against you - immediately.





ssmith619:

I feel, it wouldn't be so hard to program a brute force AI, as the basic algorithm exists for about half a century. I think it would be hard to come up with a value-function more elaborate than the current power graph.

I also feel it could not be done on a current pc though. Just too many possible moves. A turn would take so long we could play in real time
1 year = 1 year

Well, about computers programming themselves, this is new to me. They certainly can be made to do things, that look like being intelligent, but it's all in the code or in a knowledge base. Except for neural nets, which can learn, but even they have to be wired and trained.


sumthinelse:

agree


china444, Mathias:

You forgot about the mice issue.

In fact, the firaxis people are training and conditioning -us- to find our ways through their Civ-maze.

 

[Praetorian]

Originally posted by china444
Forty Three Kudos to whoever did this. I never really pay attention the the science formulas, I just pla ythe game.

You hit the nail on the head

 

[Ralph-x]

I think that maby the computer could be made to play a much better game even without much change. Right now they seem to play to expand, and not win, maby if the AI was to pick a method winning, say half way through the game, based on how it was doing and then focus on just that method, instead of just hoping to win by playing the game.

Also a more pro active apporach to stopping the player winning might be nice, right now they just sit there watching you build a spaceship, knowing you will finish it before they win, and yet let you finish it without doing anything.

Also it would be nice if they did fight a little better, and know that a big clump beats a slow trickle or units.

 

[Hygro]

Deep Thought as in some scifi thing I don't know about or Deep Though like in a state of Hypnosis?

 

[Clown2TheLeft]

Mathias:

I do not understand. I need a babel fish, or perhaps you could rephrase your question in the form of some nice Vogon poetry.

Later!

--Marvin, the Paranoid Android

 

[Clown2TheLeft]

PS: Deep Thought is a computer in HITCHHIKER'S GIUDE TO THE GALAXY, for the uninformed...

--TCttL

 

[redhat]

Is this something to do with CivIII?
AI in CivIII worked the same way?

 

[bike]

Even if the AI knows all everybody's doing, and even if the battles outcome would be decided by a non-random system, even then, brute-force AI is not going to work.

In chess, in a normal position some 20-30 moves are possible. With not so much trouble 50% of them can be disregarded very quickly (skip details here), meaning some 10-15 moves need investigation. The problems with a good Go program is that these numbers are much higher. In a starting game of go there are 19x19 possible moves. This makes it very hard for even a big computer to calculate deeply.
In Civ this situation is even worse. In a game one can quickly have over 100 units, each of them *can* walk into (max) 8 possible directions, but if they have multiple moves, the number of squares is something like 25, and things get worse when there are roads, and much worse when there are railroads...
Of course these things could be turned down to essentials for AI, like, he can meet me with his tanks within 6 turns so I have to act now.

Like I said before, I think that AI would improve with having plans instead of calculating the best situation.

Some other things: If people see they're going to loose, they panic, they start to do weird things, take high risks, just to avoid to loose. At least, I do, I hate losing. I would like to see that with AI.

In my first lines I write about the AI using the expected outcome of the battle in their calculations. I realize this would be a horrible thing, everytime you get attacked by the AI, you loose , since it makes no sence for the AI to attack when he won't win...

 

[Park Ranger]

Originally posted by smalltalk

Well, about computers programming themselves, this is new to me. They certainly can be made to do things, that look like being intelligent, but it's all in the code or in a knowledge base. Except for neural nets, which can learn, but even they have to be wired and trained.

[/B]

Great article in a recent Scientific American about computers using Darwinian/natural selection principles to "evolve" electronic circuits. They duplicated 11 patented inventions in about a week. Because evolution/natural selection uses "brute force" principles, I think this is the direction computer AI is heading and someday sooner or later programmes that use these techniques to rewrite or add subroutines will be commonplace, maybe even in time for civ4.

@Mathias - you've got me thinking. Maybe civ4 already exists...keep your eyes open for oddly behaving white mice!

 

[stormbind]

Originally posted by sumthinelse
I believe you are mistaken if you think a human or computer can beat even a master (let alone grandmaster) without brute force. If you don't believe me, take all the books you want to use as reference and try to beat a human master (armed only with his limited memory of openings, no books).

It is said the best players are the way they are because they remember all their previous games - effectively, an extensive library of moves.

They can look at a board and remember what happened last time they saw the scenario, and are therefore able to make judgements for many turns ahead without fully investigating them. The small number of scenarios covered by books are of no value to an experienced player.

When using a library to combine moves ontop of moves, you end up with something I visualise as being a fractal. A human trying to achieve the same level of comprehension using brute force would take forever and a day.

I'm not saying it has no value at all, it just has more effort or less reward. Modern computers can crunch numbers at a staggering rate and the brute-force methods allow the computer to find quality moves that haven't been done before, thereby finding ways around the human players knowledge.

If you play online, it's not ussually hard to tell if your oponent is a computer or a human.

 

[sumthinelse]

Originally posted by stormbind
It is said the best players are the way they are because they remember all their previous games - effectively, an extensive library of moves.

Human masters do something like that, but some of their knowledge goes beyond knowing move sequences. They do remember specific move sequences like openings, but what really makes them masters is that they learn to recognize characteristics of classes of positions, and what is likely to work or not work in that class of position. Beyond that, they need more than memory -- the best players can determine what to do in new positions.

The totality of recorded games is more information than Kasparov carries in his brain. But if a computer had every game ever played in memory, that would not be enough. It still has to find good moves in unknown positions.

If they could teach computers to recognize the characteristics of positions - like how to play the Maroczy Bind - we might have some unimaginably strong computer programs.