No excuse for poor ai/ai tech article

[MadRat]

Chess is pretty complex alright.

There is still no computer that can win human in it.
And they count millions of moves in a second.

I'd qualify that that the win/loss ratio of a PC versus human is more proportional to the experience of a human player. A PC will beat scrub players but it will have hard time versus a GM. It is determined by how it is coded. If there is no database of openings/games then on average the PC will lose more often. This is because humans don't calculate every combination they play from memory. If a PC is given the same advantage they will beat most humans. So millions of calculations is not an advantage at all if 99% of those calculations are pointless. Thus more modern chess programs are in fact more like expert systems than true AI. Any real decision making is done at very specific points where the game leaves the "book" , but the upside is there are usually far LESS pieces and easier calculations to be done - for humans and PCs.

Rat

 

[MadRat]

The reason why computers are bad at chess is that humans have intuition and can train that intuition, while the computer always has to consider all possible moves.

Your post is very perceptive and I agree for the most part. This is where i have the largest divergence.I would attribute it more to memory and memory training than just intuition of hunch work. A person who is very skilled in that situation (like martial artist) memory and repetitions will appear like instinct or intuition. In essence, skill in may areas, like chess, is about the deja-vu. Hence, why we call skilled people "experienced" is because they have done it before. Most AI 'algorithms' have no memory they recalculate the same thing over an over because they have never "seen it before", while a human will not do that. They rely on what they have seen before. The best chess programs are not those that constantly calculate - they actually use databases.

In theory this can apply to anything. You don't need to be specifically more intelligent or naturally talented to do many occupations, you just need to have done the process over and over enough times. A street bum can become surgeon if he's just shown how to do it enough times.

Rat

 

[Jediron]

32 chess units can each use one of 64 tiles.

hahaha. Wrong from the start. Take a pawn for example, it cannot walk backwards and sideways; so there are 17 places allready, where a pawn never can go. But it can only move forwards, by 1 place and only from this starting tile, 2. So that's only 2 tiles MAX for ANY pawn on both sides, at the start. Then you have bishops, handicaped from the start, where the bishop never can change colors as what he is starting on; Standing on white, that means only 32 tiles to go for a bishop, throughout the whole game! And even then, at the start; none other then the horses can make a move, two moves a horse on both sides, that's 8 moves in total .

So, your math is very simplistic and uttterly wrong. Try again ;-)

Adjusting those weights can make a huge difference, and so can rules that prevent some of the more stupid things the AI does, but the game only just came out, and to implement either of these properly requires experience with how people actually play the game.

They have beat-tester, you know. Surely, i can understand they won't see ALL mishaps through beta testing and feedback from customers can help them iron out those mistakes. But i think CIV 5 have not been tested very well, to say it gently. Infact, i call it very poor. And that is unforgivable.

I mean, don't you think we are crossing a line here; when you see gamers come up with plans, to improve the AI's battle style. Not just a wild idea, but thouroughly desribed every piece of the concept ? Is this the new trend, that we, the customers, are taking over the development of a good game; do the hard thinking for them, while apperently the developers themself fail or don't have the abbility to do that themselves. I surely hope not. I expect that a gamedeveloper take their job more seriously then that.

 

[Doctor Phibes]

dannythefool has summed it up very well. Brute force computing is not going to work for the sort of combinatorial explosion you get with look-ahead trees here. It's not just the tactics, there are the strategic layers - and chess is a game of perfect information, both players know where every piece is. But even if we just look at Civ5 as a wargame, for example, it's a straightforward feint tactic to draw out some of the opponent's units so they can be destroyed by a bunch of your units currently out of sight. Any human general has to allow for the fog of war. So a 'brute force' AI would have to factor in not just the moves it can see as possible but an enormous number of possibilities based on things it can't see.

And that's just one example. I don't think this approach is fruitful. I think other possibilities could be explored though. Right now, the 'AI' is essentially just a bunch of heuristics that remain fairly static. But humans aren't static, we adapt to the map and the opponents, so it seems to me that the computer needs learning strategies, perhaps even to the point of retaining some of what it's learnt from one game to the next. While I haven't the foggiest about how you start impementing this with Civ, plenty of work has been done in this area in other AI spheres.

 

[mamuz]

Wow. What a statement. Can you enlight me a little, cause i can't see why that should be the case.

CIV5:
-many more hexes
-many more units, cities, mountains, water to take into the calculation
-many more different types of units
-more unit are come into place, by building/buying them
-Air, land and Sea units
-last but not least; more players involved

vs Chess:
- 32 units total (16 vs 16)
- 6 types of units
- 64 tile playfield, static

And yes, a good CIV -AI also needs to calculate alot AHEAD, for a good strategy. Just like chess-players think 6,7,8 or more turns AHEAD.



Really, your assumption puzzles me

I'm not a specialist, but in Civ IV all can be ordered and calculated. By calculating things, you directly know how much power you will win or loose.
In chess, it's not true. There's "nothing" to order. All is about analysis (or, worst, feelings). For sure, loosing the Queen is generally a bad move, but it can be the good one. It depends. This "it depends" is really hard for a computer to conceptualize.

In Civ V, there are more "it depends" than in Civ IV, especially during battle (but to improve cities, too). That's why i think AI in Civ V is complexer to implement than AI in Civ IV.

 

[mercury529]

Allow me to simplify this to two questions:

How many Civ players have the intellectual capacity necessary to drive a car: nearly 100%
How many Civ players should expect to win a game against an average Civ player: 50% (by definition)

 

[mamuz]

Your post is very perceptive and I agree for the most part. This is where i have the largest divergence.I would attribute it more to memory and memory training than just intuition of hunch work. A person who is very skilled in that situation (like martial artist) memory and repetitions will appear like instinct or intuition. In essence, skill in may areas, like chess, is about the deja-vu. Hence, why we call skilled people "experienced" is because they have done it before. Most AI 'algorithms' have no memory they recalculate the same thing over an over because they have never "seen it before", while a human will not do that. They rely on what they have seen before. The best chess programs are not those that constantly calculate - they actually use databases.

In theory this can apply to anything. You don't need to be specifically more intelligent or naturally talented to do many occupations, you just need to have done the process over and over enough times. A street bum can become surgeon if he's just shown how to do it enough times.

Rat

As a pure materalist, i agree. Memory leads to intuition. I've no evidence of it but it's... hum... an intuition !

 

[silentknight111]

Since when does Firaxis/2k have the resources Google has? That's like saying that since a lion can take down an antelope relatively easily, a house cat should be able to as well.

 

[Jolly Rogerer]

Driving is not an adversarial search activity....

Well, that depends on where you're from to some extent...

 

[DaveGold]

Any human general has to allow for the fog of war. So a 'brute force' AI would have to factor in not just the moves it can see as possible but an enormous number of possibilities based on things it can't see.

This argument actually works against the complexity needed. Once you have some algorithms to determine the danger from fog of war you can apply them repeatedly with little processing. The more units that become fogged the less processing is required.

I'm pretty sure that the AI works on an 'out of sight, out of mind' basis at the moment and forgets that you have an archer on a hill as soon as it kills the spearman that could see it. Some sort of memory of the opponent's forces will eventually be needed to make a good AI opponent. It is not needed to make a playable AI that's significantly better than the one we have now.

 

[Jolly Rogerer]

dannythefool has summed it up very well. Brute force computing is not going to work for the sort of combinatorial explosion you get with look-ahead trees here. It's not just the tactics, there are the strategic layers - and chess is a game of perfect information, both players know where every piece is. But even if we just look at Civ5 as a wargame, for example, it's a straightforward feint tactic to draw out some of the opponent's units so they can be destroyed by a bunch of your units currently out of sight. Any human general has to allow for the fog of war. So a 'brute force' AI would have to factor in not just the moves it can see as possible but an enormous number of possibilities based on things it can't see.

And that's just one example. I don't think this approach is fruitful. I think other possibilities could be explored though. Right now, the 'AI' is essentially just a bunch of heuristics that remain fairly static. But humans aren't static, we adapt to the map and the opponents, so it seems to me that the computer needs learning strategies, perhaps even to the point of retaining some of what it's learnt from one game to the next. While I haven't the foggiest about how you start impementing this with Civ, plenty of work has been done in this area in other AI spheres.

I've often thought this is the future for "AI". Your computer could analyze your games during down times in order to optimize its future strategies and tactics. Even better, your games could be sent to the cloud and everyone's games analyzed in a massive distributed processing effort to develop better heuristics.

 

[Bezurn]

The difference between chess and Civ is that you can see where all of your opponent's pieces are in one, and not so in the other. Thus the computer does not need to take all available squares into account when formulating a battle plan, but just to know the lay of the land so to know what sort of formations and choke points will be coming in the battle, and where your cities are.

The AI in charge of creating those formations and executing the battle plan of what it can see though is sorely lacking, as it does not seem to create any formations and just blindly pushes pieces forward, regardless of type. If the Ai played more tactfully and moved some pieces forward to scout, such as scouts or mounted with the right promotions it would be a fun challenge.

But then if the Ai is too good then that would cause the game to become unenjoyable for some, so sometimes just having a poorly played AI can be fun. In the present condition, it is a bit too simplistic, and acts more like lemmings, so all you need to do is hold a defensive posture until the enemy moves into your ranged units range and then counter attack taking all their cities as it does not build up a backup force to hold ground but just keeps zerging new units created forward in nearly all cases.

 

[MRM]

But then if the Ai is too good then that would cause the game to become unenjoyable for some, so sometimes just having a poorly played AI can be fun.

Well, that`s what different dificulties are good for - the AI can take more into account on higher levels. However, IMO it would be already a big step forward, if the AI would avoid suchobvious mistakes like "embark an unit right in front of an enemy ship" and such - it don`t have to plan 20 turns ahead to figure out, that this is a stupid idea ....

What I wonder is, if someone deliever a real good AI for Civ, would the community accept more calculation time for the AI ? I am afraid, that would be the price ...

 

[CurseUppl]

So, your math is very simplistic and uttterly wrong. Try again ;-)

Hopefully that comment isn't directed at me but regardless is very immature. Also, I certainly didn't proclaim that the maths was on any level other than basic and hopefully no one was silly enough to think that multiplying a number by itself 64 times was advanced maths

In regards to the replies, it never occured to me that chess AI's used a database. I actually believed, just for a second, that chess AI were genuinley smart... or not as half witted as gaming AI

Eh well, live and learn

 

[Doctor Phibes]

This argument actually works against the complexity needed. Once you have some algorithms to determine the danger from fog of war you can apply them repeatedly with little processing. The more units that become fogged the less processing is required.

But that's just shifting the complexity, Dave. It seems to me that the algorithms to determine the danger from fog of war have to be at least as intricate (and CPU-heavy) as those that look-ahead for visible units.

I'm pretty sure that the AI works on an 'out of sight, out of mind' basis at the moment and forgets that you have an archer on a hill as soon as it kills the spearman that could see it. Some sort of memory of the opponent's forces will eventually be needed to make a good AI opponent. It is not needed to make a playable AI that's significantly better than the one we have now.

Yeah, this seems to be the case with all Civs. I think the only thing that may give the AI pause it that it has a figure for your total military power (as you do for its). If it can only see a very few of your units or it knows it is totally overmatched, that does seem to give it pause. It doesn't substitute for a detailed memory though, I agree. The problem is, as before, how to use that detail.

I've often thought this is the future for "AI". Your computer could analyze your games during down times in order to optimize its future strategies and tactics. Even better, your games could be sent to the cloud and everyone's games analyzed in a massive distributed processing effort to develop better heuristics.

Oh, I think this is definitely the way to go if one could get a handle on it. I can imagine using BOINC (as in einstein@home) for distributed analysis. Hmmm, an AI in a cloud? We could call it Skynet. Oh, wait...

 

[Doctor Phibes]

In regards to the replies, it never occured to me that chess AI's used a database. I actually believed, just for a second, that chess AI were genuinley smart... or not as half witted as gaming AI

Eh well, live and learn

I've worked with chess programmers way back (I'm mostly a user interface person myself). And, yes, chess programs do use a database, but it's known as an 'opening book' - it simply contains the details of tried and tested opening responses. Once play departs from the main line of any of the openings in the book (and that could be one move in), then moves must be calculated by traversing and pruning the look-ahead tree. That doesn't mean that a chess AI is genuinely smart in human terms, but it's not trotting out responses from a database. (Given that the number of possible games of chess has been estimated as 10^10^50, obviously that would be unfeasible, to say the least.)

 

[ChaplainDMK]

Managing a Chess board is complexer than Civ for a computer. But, the fact is AI algorithm to play chess exists for long time. A lot of research & development is already made. It simplifies things.

For Civilization, Civ V is really harder for a computer than Civ IV. Civ IV was simple : your have a trait, and one predefined way for victory, the only things to do was :
- research tech useful for ressources around you city, improve the tiles.
- built all buildings as you can starting with the ones accordingly to your predefined victory
- maintain a correct number of units
- create stacks of doom for war
Note that even if it's simple, Civ IV's AI was dumb.

In Civ V, i guess AI change the way to win (i think it's too complicated to a computer to be efficient by making that), he needs to choose which buildings in which town (it's really harder that buit all as you can) and he needs to use tactics for combat (it's harder than in Civ IV, but i agree with you here, this kind of AI engine already exist, and works nice in other game).

I think Firaxis has made a bad job for tactical AI (= Combats), but for the other things, i can understand the challenge it is. I think the best way to correct AI is to fix for each leader a predefined way for victory, and for each predefined way, help the AI with predefined humans ways of playing. Because, in general, AI can't act (only humans can). AI can only react to something. And i imagine Civ V's AI tries to act. Without a memory (which can answer to this question : "why i've chosen to not develop paladin 20 turns ago ?"), and complex algorithm, i guess it's impossible.

Chess is easier for a computer.
Its extreamly fixed, there aren't that many possibilities. Pawns move foreward, queens move diagonaly, left and right and foreward and backward etc.
In Civ 5 you have many differant units with differant bonuses, many differant terrain types, and evrey unit can move in any direction.
So preaty soon you will have tonnes of possibilites. And in Civ 5 each battle is a chessboard, you have multiple chess boards all over the world, the AI then has to anticipate what each oponent is doing and adjust its strategy (move units to borders, find aliances etc.) and manage its empire all at once.
And you can have 35 AI entities in one game etc.
And the AI for chess (the unbeatable one) alone was built over decades by the brightest minds in the industry, Civ 5 was made in 2 years by 120 guys, and probably 10 or 20 guys were making the AI.
So its not realy comparable.

 

[Endureth]

Chess is pretty complex alright.

There is still no computer that can win human in it.
And they count millions of moves in a second.

http://en.wikipedia.org/wiki/Deep_Blue_(chess_computer)

Deep Blue beat the best chess player in the world at that time and guess what happen.

The human said the computer cheated...

Also, it's worth mentioning that the rules for chess haven't changed since it's inception. Unlike Civ where new versions of the game have to be written every 5 years or so to get people to re-buy it.

 

[Doctor Phibes]

http://en.wikipedia.org/wiki/Deep_Blue_(chess_computer)

Deep Blue beat the best chess player in the world at that time and guess what happen.

The human said the computer cheated...

Also, it's worth mentioning that the rules for chess haven't changed since it's inception. Unlike Civ where new versions of the game have to be written every 5 years or so to get people to re-buy it.

That's not even true for 'common chess'. And Shogi and Elephant Chess are long-established contemporary variants that are still played widely (great fun they are too). It's not even certain what the rules for ur-chess - which is thought to have originated in C6 in NW India - were. There were many rule changes over time and our current set of rules only became completely fixed as late as C19.

 

[Kruelgor]

It's easy to make a challenging AI. All the game devs need to do is make it cheat. A cheating AI is always the best route for single player AI.