No excuse for poor ai/ai tech article

Joined
Nov 14, 2006
Messages
11,676
Location
Las Vegas
For many years I have accepted the excuse that a proper AI cannot be made for a game as complex as Civ. It has thousands of squares (now hexes) not just a couple dozen of a chess board people say. And then I see this article.

http://www.cnbc.com/id/39594637

If google can make a car that can drive in traffic by itself (just think how many different things it has to react to), how can we not get a decent ai? I'm just not buying the excuses for poor AI anymore. To me, this car looks amazing. It has more than just a few thousand hexes to contend with. It has many square miles to contend with (although arguably it only has to deal with small numbers of square miles at a time equal to appox. the stopping distance of the car).

So what are your thoughts. Can a decent AI be made for this game? I'm not asking for something like chess that can think 100 turns ahead. But it would be nice is the AI could at least think 5 turns ahead in a war, with generalized long term goals for peace and objectives for war.

Anyone driving the twists of Highway 1 between San Francisco and Los Angeles recently may have glimpsed a Toyota Prius with a curious funnel-like cylinder on the roof. Harder to notice was that the person at the wheel was not actually driving.

The car is a project of Google [GOOG Loading... () ], which has been working in secret but in plain view on vehicles that can drive themselves, using artificial-intelligence software that can sense anything near the car and mimic the decisions made by a human driver.

With someone behind the wheel to take control if something goes awry and a technician in the passenger seat to monitor the navigation system, seven test cars have driven 1,000 miles without human intervention and more than 140,000 miles with only occasional human control. One even drove itself down Lombard Street in San Francisco, one of the steepest and curviest streets in the nation. The only accident, engineers said, was when one Google car was rear-ended while stopped at a traffic light.

Autonomous cars are years from mass production, but technologists who have long dreamed of them believe that they can transform society as profoundly as the Internet has.

Robot drivers react faster than humans, have 360-degree perception and do not get distracted, sleepy or intoxicated, the engineers argue. They speak in terms of lives saved and injuries avoided — more than 37,000 people died in car accidents in the United States in 2008. The engineers say the technology could double the capacity of roads by allowing cars to drive more safely while closer together. Because the robot cars would eventually be less likely to crash, they could be built lighter, reducing fuel consumption. But of course, to be truly safer, the cars must be far more reliable than, say, today’s personal computers, which crash on occasion and are frequently infected.

The Google research program using artificial intelligence to revolutionize the automobile is proof that the company’s ambitions reach beyond the search engine business. The program is also a departure from the mainstream of innovation in Silicon Valley, which has veered toward social networks and Hollywood-style digital media.

During a half-hour drive beginning on Google’s campus 35 miles south of San Francisco last Wednesday, a Prius equipped with a variety of sensors and following a route programmed into the GPS navigation system nimbly accelerated in the entrance lane and merged into fast-moving traffic on Highway 101, the freeway through Silicon Valley.

It drove at the speed limit, which it knew because the limit for every road is included in its database, and left the freeway several exits later. The device atop the car produced a detailed map of the environment.

The car then drove in city traffic through Mountain View, stopping for lights and stop signs, as well as making announcements like “approaching a crosswalk” (to warn the human at the wheel) or “turn ahead” in a pleasant female voice. This same pleasant voice would, engineers said, alert the driver if a master control system detected anything amiss with the various sensors.

The car can be programmed for different driving personalities — from cautious, in which it is more likely to yield to another car, to aggressive, where it is more likely to go first.

Christopher Urmson, a Carnegie Mellon University robotics scientist, was behind the wheel but not using it. To gain control of the car he has to do one of three things: hit a red button near his right hand, touch the brake or turn the steering wheel. He did so twice, once when a bicyclist ran a red light and again when a car in front stopped and began to back into a parking space. But the car seemed likely to have prevented an accident itself.

When he returned to automated “cruise” mode, the car gave a little “whir” meant to evoke going into warp drive on “Star Trek,” and Dr. Urmson was able to rest his hands by his sides or gesticulate when talking to a passenger in the back seat. He said the cars did attract attention, but people seem to think they are just the next generation of the Street View cars that Google uses to take photographs and collect data for its maps.

The project is the brainchild of Sebastian Thrun, the 43-year-old director of the Stanford Artificial Intelligence Laboratory, a Google engineer and the co-inventor of the Street View mapping service.

In 2005, he led a team of Stanford students and faculty members in designing the Stanley robot car, winning the second Grand Challenge of the Defense Advance Research Projects Agency, a $2 million Pentagon prize for driving autonomously over 132 miles in the California desert.

Besides the team of 15 engineers working on the current project, Google hired more than a dozen people, each with a spotless driving record, to sit in the driver’s seat, paying $15 an hour or more. Google is using six Priuses and an Audi TT in the project.

"If you look at the vehicle code, there are dozens of laws pertaining to the driver of a vehicle, and they all presume to have a human being operating the vehicle."

Bernard Lu
Calif. Dept. of Motor Vehicles

The Google researchers said the company did not yet have a clear plan to create a business from the experiments. Dr. Thrun is known as a passionate promoter of the potential to use robotic vehicles to make highways safer and lower the nation’s energy costs. It is a commitment shared by Larry Page, Google’s co-founder, according to several people familiar with the project.

The self-driving car initiative is an example of Google’s willingness to gamble on technology that may not pay off for years, Dr. Thrun said. Even the most optimistic predictions put the deployment of the technology more than eight years away.

One way Google might be able to profit is to provide information and navigation services for makers of autonomous vehicles. Or, it might sell or give away the navigation technology itself, much as it offers its Android smart phone system to cellphone companies.

But the advent of autonomous vehicles poses thorny legal issues, the Google researchers acknowledged. Under current law, a human must be in control of a car at all times, but what does that mean if the human is not really paying attention as the car crosses through, say, a school zone, figuring that the robot is driving more safely than he would?

And in the event of an accident, who would be liable — the person behind the wheel or the maker of the software?

“The technology is ahead of the law in many areas,” said Bernard Lu, senior staff counsel for the California Department of Motor Vehicles. “If you look at the vehicle code, there are dozens of laws pertaining to the driver of a vehicle, and they all presume to have a human being operating the vehicle.”

The Google researchers said they had carefully examined California’s motor vehicle regulations and determined that because a human driver can override any error, the experimental cars are legal. Mr. Lu agreed.

Scientists and engineers have been designing autonomous vehicles since the mid-1960s, but crucial innovation happened in 2004 when the Pentagon’s research arm began its Grand Challenge.

The first contest ended in failure, but in 2005, Dr. Thrun’s Stanford team built the car dubbed Stanley that won a race with a rival vehicle built by a team from Carnegie Mellon University. Less than two years later, another event proved that autonomous vehicles could drive safely in urban settings.

Advances have been so encouraging that Dr. Thrun sounds like an evangelist when he speaks of robot cars. There is their potential to reduce fuel consumption by eliminating heavy-footed stop-and-go drivers and, given the reduced possibility of accidents, to ultimately build more lightweight vehicles.

There is even the farther-off prospect of cars that do not need anyone behind the wheel. That would allow the cars to be summoned electronically, so that people could share them. Fewer cars would then be needed, reducing the need for parking spaces, which consume valuable land.

And, of course, the cars could save humans from themselves. “Can we text twice as much while driving, without the guilt?” Dr. Thrun said in a recent talk. “Yes, we can, if only cars will drive themselves.”
 
Funy as it seems, but there are less parameter involved by driving a car . For example: all other different things you speak of, you can group toghether under one argumeny: objects. Most of the time the goal is not to hit them or keep a distance to it.

And don't forget that the cars "ai software" gets input from electronical devices; such as detectors. In a game ALL have to be coded, there is NOT a single electronic device that can help gathering info.

Now we take a game Civ 5; it's like chess (or worse). The more units on the map, the harder it gets, then you have the number of other CIVs, your of their standings towards each other. Number of cities and city placement, borders, where to defend which hex to go, etc.etc.etc.

Now while i think the AI can be better then it is now; the AI seems just as bad as with CIV1, it will take a long time it comes close to human mind. In any case, with this type op gaming.

I think alot has to do with the time and effort needed to make a more or less good AI, is too costly for the game-developers. Maybe they start of with good intentions, but as time goes by, realise (or told) it can't be done , due to a number of reasons; most of the time though: time and cash.
 
And don't forget that the cars "ai software" gets input from electronical devices; such as detectors. In a game ALL have to be coded, there is NOT a single electronic device that can help gathering info.

This is a non-issue, the game doesn't need sensors because it already knows everything about the world.

Apart from that, I agree. A previous employer of mine actually had a car that was half automated. Avoiding crashing into the scenery is easier than you'd think, and beyond that, an automated car doesn't need to do much more than a non-automated one with a GPS device and maybe some proximity sensors. And what it does is all very short term decision making, no strategies that have to be viable for hundreds of turns. (This was almost ten years ago though so this specific experimental car was constrained by other limitations, like the battery only providing the four PCs in the back with power for about 20 minutes...)
 
Ow, yes. Bad example :lol:

Anyway, about computer AI. See how many games (if not all) have problems which something simple (to us) as path-finding. It's somewhat better these days, but once and a while you bump into it again. From time to time. You can even notice it in CIV ;-)
 
Wanna know what ruined the development of the AI during last years ?

Kiddish Consoles
 
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.
 
There are too many variables in gaming, believe it or not. That's sort of like asking why you can't program a robot to do improvisational jazz.

Civ V AI is worse than Civ 4 because one unit per hex doesn't work at the scale of civilization, and there are serious problems with even the logistics of movement. There is a good discussion about that here.
 
Managing a Chess board is complexer than Civ for a computer.
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 :confused:
 
Believe it or not, the AI for playing Civ V is actually more complex than the AI for driving a car, albeit in a different way. My last job was actually with a company who works on autonomous vehicles. Driving a car is as much a matter of processing as decision making. It's a matter of quickly locating the objects around you (the vehicles around you, the lines marking lanes and the edge of the road, relevant street signs etc.) and then establishing rules to abide by. Keeping a certain distance from the car in front of you, slowing down/accelerating at the right time, etc. I am curious how/if they handle street signs, as that is a problem of pattern recognition.

Civ V is also a problem of pattern recognition. This is something the human brain excels at, but computers struggle with. You can look at a given map in Civ V, look at what units you have available, what units you're fighting, and instantly formulate a sound strategic plan. A computer can't mathematically calculate that. In Civ IV combat was a math problem to be solved, maximize production and make a big stack of mixed units. Civ V's AI unfortunately doesn't have that luxury =p

As for the question in the OP of "Can a decent AI be made for this game?" The answer is absolutely. It just can't really be compared to driving a car. Establishing a couple simple rules like don't march one unit at a time into the grinder, attack a unit/city if you can, and don't walk back and forth two tiles away from a city would do wonders for the combat AI =p
 
I am curious how/if they handle street signs, as that is a problem of pattern recognition.

Civ V is also a problem of pattern recognition.

It's a completely different type of pattern recognition. There are some patterns that are quite easy to find in a picture, like straight lines or circles. Identifying an unobstructed street sign is not that hard since they are standardized at least on the country level. There is a generic approach that you can follow, basically you make a probability function that determines the probability for a specific sign being present in the image based on what features and relations can be detected. At no point do you have to consider multiple possible meanings. All you have to do is identify a sign that always looks the same. (As a side note, it's more realistic that autonomous cars won't use video cameras to interpret road signs, instead they will use a combination of a database like many GPS navigation systems already know the maximum allowed speed on any given road, and electronic signalling as used by high speed trains that are de facto autonomous, because no human can react fast enough to drive anything at 400 km/h.)

If you look at humans playing a strategy game on the other hand, you don't have a standardized pattern you can identify. Every situation is always ambiguous. Simple example: If I move my entire army right next to my neighbour's border, that doesn't mean one specific thing. The AI is written so that it views this as a threat, with all the military close to its border, but that's just an educated guess based on what counter strategy is the most viable one. It views it as a threat because it can - and has to - defend against the hypothetical threat while it can do nothing - and neither needs to do anything - about the other possibilities like maybe I'm just neatly organizing them on my screen so I can take a screenshot of my military might ;-) There are no simple cues like "limit speed to 50 km/h".
 
Driving is not an adversarial search activity. The other cars are not out to get you, adapting their strategies and methods as needed on the fly to continually make your life as hard as possible. And as much as the AI in that car is lauded in the article, I remain skeptical that they've developed an AI system which can handle even a majority of driving situations. (70-MPH highway driving, stop-and-go traffic negotiating an accident situation and moving out of the way for an ambulance, badly marked backroads with faded speed limit signs....)

And as a brief aside, I don't think fully autonomous cars will ever get off the ground. Because after they do, someone will get into an accident while on auto-pilot and win a ridiculous lawsuit for hundreds of millions of dollars in emotional damage, and the people developing this stuff will go back to research.
 
One thing to understand with chess is the complexity, for computers, is in learning how to evaluate a position. The only real numbers in chess are material. CiV gives the computer TONS of metrics to measure decisions by. It's difficult for the computer in chess to know if it is winning or loosing in a given position. Sure, its easy for the computer to know it is up two pawns, but how do you tell the computer that the positional advantage it gave to the opponent is much stronger than those two pawns? Sure the game of a game like CiV may be more complex, but most of the problems in the game can be broken down into questions that are simpler for the computer to answer.

On another note, it actually shocks me that the AI is so atrocious at short term combat. A simple +/- decision on if the computer can win a given battle is very easy for a computer. What's difficult for a computer is deciding if attacking a given point is a good decision. For instance, give the computer a choice between two cities, one is slightly more valuable because, of say a happiness resource while the other is in a location that holds some sort of strategic importance. I would expect the computer to choose the happiness city, as that is something the computer can easily evaluate, while the AI more than likely has little to no understanding of the strategic importance of the second city.
 
So what are your thoughts. Can a decent AI be made for this game? I'm not asking for something like chess that can think 100 turns ahead. But it would be nice is the AI could at least think 5 turns ahead in a war, with generalized long term goals for peace and objectives for war.

sure they can, but you have to remember that the computer used to beat the chess champion was the size of a small warehouse that played many many games each turn to figure out the best path. here you have at best maybe a quad core processor. though i have noticed that civ v does not in any way fully utilize my 4 cores. maybe about 20%

also you have all those whining about how long it takes now to cycle between turns, LOL, if you wanted the AI to start playing ahead turns to look into better strategies, it would take a lot longer, which is something i would actually be OK with.

so you want better AI, then you will have to deal with much longer wait times between turns.
 
Before we anyone else compares CIV4 AI vs CIV5 AI lets just remember that the CIV4 AI would get the very basics right. Defend a city. If moving a unit off a hill will get it killed then fix the unit on the hill instead. Put your units into a mixed stack and use the right units at the right times.

The CIV5 AI does nothing right, near enough, and typically works by 'shoot if you can shoot, attack if you can attack, else move forward in the vague direction of an opponent'. That's all, no intelligence required. Wind the units up, point them in the right direction, and send them off.

Civ V is also a problem of pattern recognition. This is something the human brain excels at, but computers struggle with. You can look at a given map in Civ V, look at what units you have available, what units you're fighting, and instantly formulate a sound strategic plan. A computer can't mathematically calculate that.

This was the argument put forward by Gary Kasparov for why computers would never beat a grand master at chess. The CIV5 AI doesn't need to be at grandmaster level.

The simplest chess AI looks at possible moves and evaluates them exhaustively. It then picks the best one. You could set the numbers of turns ahead that the AI would evaluate, the more turns you could look ahead the better the simulation of intelligence became. I would argue that if the CIV5 AI looked just one turn ahead it would play better than it does now, no joke. Two turns ahead is probably all it would ever need.
 
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 :confused:

Okay, don't quote me on this but...

32 chess units can each use one of 64 tiles. That's 32^64 which almost gives a googol (bear in mind that is larger than there are atoms in the Universe).

At any given time in Civ5, the AI has to deal with small area of hexes, say 5x5, with a few different units available at that time. This number is but a tiny tiny tiny fraction of the googol mentioned above.

Any math/chess genius correct me if I'm wrong :)
 
Okay, don't quote me on this but...

32 chess units can each use one of 64 tiles. That's 32^64 which almost gives a googol (bear in mind that is larger than there are atoms in the Universe).

At any given time in Civ5, the AI has to deal with small area of hexes, say 5x5, with a few different units available at that time. This number is but a tiny tiny tiny fraction of the googol mentioned above.

Any math/chess genius correct me if I'm wrong :)

Math is very much not my strongsuit, but that doesn't seem logical to me. why do you think Civ only has to deal with a 5x5 group of hexes while chess has to take into account every one of the 64 tiles on the board? In both cases there are a number of pieces/units and a limited number of of moves each can make that do not include every tile on the board. In chess it's 16 pieces and that only decreases. For Civ that number of units can be anywhere between 2 and a crap-ton. More than chess, in other words. So I'm still not getting where you're coming from there.

As for the car, I'm not going to trust that until they can make Chrome stop crashing.
 
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.
:)
 
Okay, don't quote me on this but...

32 chess units can each use one of 64 tiles. That's 32^64 which almost gives a googol (bear in mind that is larger than there are atoms in the Universe).

The problem with using that simplistic value like 32^64, is that it will never, ever occur in a chess game. It can occur through just a random piece placing and as math model. Fischer random chess gives more starting variants; but you still wont get that many different positions.

Secondly chess playing programs don't calculate every possible position - in the opening they use chess "books" or databases and early mid game. Indeed end game theory as well has specific algorithms. The number of pieces and position sis GREATLY reduced by the time "pure" analysis occurs. Sadly this is also the point in which the AI quality takes a nosedive.

Kasparov pointed this out a while back. he mentioned he wasn't playing a computer as much as he was playing against expert-system database. In defense of AI - most grandmaster-level players aren't any more intelligent than most average players they just have memorized and experienced a lot more games and thus they are in themselves more human databases than actual strategic geniuses.

Civ on the other hand has much much harder time with random civs, random maps, variant sea/land ratios, different techs and many different win conditions. It would be much much harder to get an intelligent looking AI the a chess program because you have to analyze the board position every time versus just looking at a database.

The Civ 5 AI does suck not because it is inherently bad - but because comparable games like Civ 4, Gal Civ, SoSE, had actually more variability, but better decision making than a simpler Civ 5 with stupider results.

Rat
 
Any math/chess genius correct me if I'm wrong :)

Your main fallacy is that the number of tiles is important. It's not. The number of possible moves and possible outcomes is. And chess, as far as that is concerned, is comparatively simple. You really don't have many options at any given time, many of those are zero sum games, and many books have been written describing good and bad tactics in various stages of the game that a chess AI can use for reference. For example, a pawn can do exactly one thing most of the time: Move one step forward. At most, it can do three different moves. The opponent only has a very limited number of responses. Pieces that can't reach the pawn don't count. Most of the time, no piece or very few pieces will be able to reach it. There may or may not be a future implication that would be really good to realize when moving the pawn, but the size of the board is not relevant here; the number of turns the AI can predict is, and that directly depends on the number of moves each piece can make on each predicted turn. There also is no randomness, a chess AI knows that it will defeat that pawn if it takes one more step. And five turns earlier it knows that it will defeat the pawn in five turns if it takes five more steps. These variables never change.

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. Even simple games that require more intuition and less hard facts, such as Sokoban, are harder for a computer to solve than chess. Running around in circles on a chess board will lose you the game, not so in Sokoban. (With that said, a chess AI would still beat 99% of its player base if as many people bought chess software without being good at chess as people who are not very good at strategy games buy strategy games.)

The Civ AI works in a completely different way, though. It doesn't predict moves (and I don't think such an approach is viable). It seems to use a heuristics based approach to war, e.g. it has weights for various actions like "attack another unit", "damage city", "capture city" and so on, and the weights are chosen so that across a large number of similar situations, the outcome will be favourable most of the time. There are higher level goals that affect those weights. Gameplay based on heuristics always looks erratic, though, and thus makes mistakes appear even more glaring.

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