It does not help either that what you are attempting to create or emulate artificially has many definitions, some of them conflicting. Of course I speak of intelligence, whatever it is.

That is indeed one of the major problems with AI technology today- we can make up Turing Tests and lists of reasoning tasks, but there is simply no agreed-upon definition of what constitutes full artificial intelligence. To make matters worse, (as I mentioned a long time ago) AI in games usually isn't true AI in the computer science sense at all (even though one could think of a strategy game as a modified Turing test). AI itself is also a giant field- Wikipedia has a comprehensive (and very obtuse) list, but I've seen it summed up better as follows:

• Robotics: Irrelevant to games, and for that matter not terribly relevant to me and the research I'm doing. Robotics pretty much covers any way that the machine can influence its own environment. For the research I'm doing, we have dedicated mechanical and electrical engineers for that. The closes I get is making simulations, and the other people always just feed me the specifications for those.
• Computer Vision: Also not terribly useful, computer vision is exactly what it sounds like- making computers capable of gathering visual data. This is a LOT more difficult than it sounds, and a bit above my pay grade.
• Speech recognition/language processing: speech recognition involved turning audible sounds into words. Language processing involved turning those words into meaningful ideas. At the moment, the technology is pretty weak (as Siri users can attest), but once it takes off I think it could have a big effect on games, particularly in expanding the diplomacy system- imagine computer players that you could actually negotiate with, or conversable characters in RPGs.
• Knowledge representation & reasoning: the first one is actually already done for us- knowledge representation basically just means putting the game in a computerized format. Reasoning is... kind of the holy grail of strategic AI- it can think rationally, like a human, and solve problems through logic. There has been some success using reasoning in mathematics, but I very much doubt anyone has put it in a game as it becomes VERY computationally intensive.
• Machine learning: ML has grown a lot recently, and is being used in everything from Facebook to spambots. Using machine learning, a computer can build associations between causes and effects, predicting events in systems that are too complicated to calculate directly. I don't honestly see that much application in games, although it could guess at player strategies or make very broad decisions about the course of the game. The big problem is that machine learning requires massive databases to learn from- that means game histories would have to be uploaded to some central location in order to train the thing in a timely fashion. The BIGGER problem is that machine learning starts out with very high error margins on its predictions- I don't know how many people would play a game where the AI had to be constantly updated, and started out as a very poor player.
• Planning. Planning is mostly searches. I've talked about search trees a bit before here, but the short version is that it's computationally intensive (although not as bad as reasoning), and used by things like chess programs. It's rare, but not unheard of, in game AIs.

 

it depends on the game

 

chess is not a complex problem for current technology, so any advantage would be too much

 

in Starcraft-like games, it's not even hard to write an AI that can beat humans with something like 10% advantage. I think with enough effort, an AI with just 2% advantage can compete at the highest level. but that is ONLY because of the advantage, and SC is a game about turning advantages into exponential disparities

 

Civ-like games are more complicated, so maybe more leeway is acceptable, but it's the same basic model

 

my point is that it's absolutely ridiculous that 4X game developers have not put in the effort to even make the AI competent enough even with a huge advantage of 25%. it's an arbitrary number that does a decent job illustrating how backward the current state of development is.

AIs are also naturally going to perform better at real-time strategy games as opposed to turn-based because of an inherent advantage- they don't need to scroll to their units and click on them to make them move.

 

Yes, an AI does have a faster reaction time than a human, but, can it micro-manage those units well enough to take advantage of that reaction time? At least your typical game AI, not those like the Berkeley Overmind.

Probably not as well as a human could if you gave him/her a pause-and-issue-commands button and limitless attention span, but it certainly helps (and if programmers spent an unusual amount of time making a very detailed reflex-agent AI, they might be able to get something that can play on equal level with a human, since micromanagement is fairly procedural).

 

Also ran a quick Google search for the "Berkeley Overmind" you mentioned, and the AIIDE Starcraft competition it competes in. Very cool project. It reminds me of the Loebner Prize, but with less grandstanding and more complex AIs. I kind of wish it was better publicized and funded.

I think I have to disagree, as far as 4X games go. I think one of the main advantages of an AI in an RTS is what Scoutdog said: they're real time and the AI has perfect control over its units (i.e. it can react instantly with all its units and coordinate them "perfectly" because it doesn't have to click a mouse). I also think that RTS games are generally easier for AI because they're smaller in scale--there are many fewer "things to do" and fewer wacky rules (i.e. spells vs heroes vs armies, etc).

I think for evidence we have the fact that 4X AI's need more help. Do you really think that it's laziness (or, more politely, lack of resources) that's holding 4X AI back? Maybe, because after all Blizzard knew that Starcraft 2 was going to sell a bajillion copies and could afford to put a bunch of resources into the AI. I'm not sure at all that it's "absolutely ridiculous".

Yes, in general, RTS AIs can get an edge with APM, but I'm really just talking about the decision-making at a high level - the part that actually relates to strategy

SC AI is easy to write because the game is extremely simple. The AI I wrote that beat the Overmind was less than 50 hours of work. Now that's nowhere near enough time for a good AI, but it barely scratches the surface of what's possible. It's just sad that professional developers do so little when they have so many resources to spend.

I actually think that those AI competitions are counter-productive, because they are about real-time games which shift the focus to a bunch of things that have nothing to do with artificial intelligence. The vast majority of work that goes into any quickly-made but competitive Starcraft AI will have nothing to do with strategy. I hope we get more stuff like that, but it should not be Starcraft.

4X games are a lot more complicated than Starcraft, but nowhere near as resource intensive. 10 years ago, compute resources were truly limited and we totally excused crappy AI, but that excuse doesn't fly anymore, especially for today's turn-based games.

It's really just a matter of effort and prioritization. It's hard to really understand how backward development is without being a programmer yourself, but for those of us who have grasps on both strategy and programming, it's a truly pathetic situation. It's holding back strategy games so much, and it's tragic.

I'm going to have to disagree with you there, at least for classical AIs. I just finished a project wherein I had to make an adversarial-search AI for a very simple game (wherein two melee units had to chase down and kill a ranged unit on a totally blank map), and by the time I started searching down about six levels in the game, it was taking the computer about a minute of solid pondering to calculate each turn. And that was with ASCII graphics. Game AIs are better, obviously (probably because they are written by more than a single undergrad with a Minecraft account!) but computational limits are still a serious problem. And compared to AI reasoning, which I consider the best avenue for creating truly sentient machines, adversarial searches are extremely fast- it can take a supercomputer hours to work through a simple reasoning problem (although, and we computer scientists are still trying to figure out why, many hideously complex problems can be solved almost instantly). There is a procedure called alpha-beta pruning that, in Laymanese, speeds up the search by eliminating hordes of obviously stupid moves (chess is well-suited to this algorithm, which is why computers are so good at it), but it requires the development of heuristics to estimate a move's value, and those have to be devised and tuned by humans. The value of these competitions is actually a huge fighting point in the computer science community. Those opposed to them cite many of the same reasons you do. I honestly haven't decided yet. Mostly because I don't know my professor's position and don't want to piss him off.

 

Part of the problem may be in the different memory systems used by computers and humans. Even though there have been some advances on that front thanks to artificial neural networks.

That's actually a bit above my pay grade. It sounds reasonable, though.

 

UPDATE:

I talked about this with one of my professors today. It turns out that simulated reasoning is slow mainly because it "thinks" in a REALLY unnatural way, by looking at all the known facts, randomly generating concepts of the entire universe, and seeing which ones fit and which don't (that is, of course, the universe in the sense of the game space. As much as I wish it were otherwise, AIs do not model the entire cosmos! (\B):vulcan:(\B) ). However, there is a technique called automated planning that is more goal-directed. I could easily see it being used in a TBS game, but I don't know of anyone who has done so.

 

Pretty much like attempting to solve a math problem by plugging in every possible answer until the right one is found.

That is, in fact, exactly what the algorithm does.

Things like this are why I loathe having dyscalculia. I can comprehend generalities, but complex mathematics is beyond me and likely always will be. I will never be able to fully pin down why a particular example of AI (game or otherwise) is "good" or "bad" in a specific sense, because my brain simply can't comprehend the mathematics underlying it. All I can discuss is my own entirely subjective experience of playing against it.

Fascinating subject nonetheless, though.

people often focus on why AIs will never be perfect and how how hard a lot of problems are. it's not about solving NP-hard problems and finding the best solution - it's about finding a competent course of action that can present a challenge to the player, and making sure that challenge fits within the design parameters of the game.

In a symmetrical game, how well the player is challenged is what determines "good" versus "bad" playability. For AI purposes, "good" and "bad" are just a measure of competence, so if two AIs provide the same challenge to the player, the one that cheats less is the stronger artificial intelligence.

The point is that for almost all strategy games, good AI = good playability and bad AI = bad playability. This is because the games are symmetrical and are completely designed around opponents playing by the same rules.

Games like Civ simply stop working with bad AI because the level of cheating is so ridiculous that it completely changes all the gameplay elements. When a game is about racing (racing for technology, racing for wonders, racing for land, racing for military strength), then the race kind of needs to be fair - or at least seem that way in the eyes of the player.

Without the possibility of loss, there cannot be challenge. And when losing is not perceived to be player-driven, then the game sucks. Designers are absolutely horrible at making the player think that they lost because of poor play when they actually lost because some AI got 75% cheaper everything

 

10 years ago, there was 1 CPU and it basically had to be entirely devoted to just running the simulation and rendering all the fancy graphics. There was at least an excuse for the horrible AI, even for the turn-based games. Now that excuse is gone for the turn-based games, even if resources are still too limited for really great stuff.