The Intelligence of Game-Playing Software

Nice article. As I maybe mentioned before, I once had to do an AI (Artificial Idiot) that could play Hnefatafl. It wasn't bad, and could even beat me quite often. It wasn't so hard to program either - just give it a few strategies and let it go. A good trick was getting it to change strategies in mid-game, suddenly becoming very aggressive or very defensive for no good reason.

It's a pity the rest of the CD-rom was complete rubbish...

I've worked in the game business since 1995 and worked specifically on Civ III. Your points are completely spot on. The development versions of Civ III allowed one to remove the fog of war and the amount of handicapping was actually quite staggering... besides the fact that not only does the "AI" know all the rules, and it does not forget to do everything it can possibly do in a turn, but then it goes off and simply cheats because it is not constrained by the fog of war, like you are.

AI for a game like Civ has strategic and tactical AI, written by different people and tested by a very small number of folks (who may actually be weak players). The example you gave may simply be that the strategic AI programmer's bias is to meet strength with strength, the AI certainly knew the other cities were undefended. If a "better" player does not test the system then it's Garbage In, Garbage Out.

On the other hand, if I were allowed to opine and agreeing with you that the AI is just a rule based system, the best way to give a pleasurable experience is for the AI to elicit a strong emotional response from the player. What I'm referring to is that moment when the AI does something, maybe unexpected, to piss you off and you stop thinking of the AI as an "it". Something like that can transcend a game to an experience, and all of a sudden it becomes "your favorite game" even though it may in fact be judged weak.

I think this is the quality that Civ II has which is missing from III and IV (arguably I as well), or from *my* favorite game, Master of Orion II.

Paddy, Count, good to know we agree! Civ is a fine game, but I did feel let down when I realised that it cheats. On the other hand, I cheat too by a) being reasonably intelligent, b) saving and restoring.

I once worked with a woman who had the distinction of being the first person ever beaten by a computer at chess. When they got the first computer chess program working in the early days at Los Alamos, they went down the hall asking people if they knew how to play. She was the first person who said no!

Point #1: Neither you, nor I, nor anyone else knows how the human brain plays chess, or performs any other high-level task. Chalking it up to "emergent properties," scare quotes and all, is just another way of saying that you have some vague idea about what the base-level components are doing, but no idea how they work together. You could just as easily attribute the operations performed by a computer to the emergent properties of its transistors. In the case of the chess-playing computer program, all those transistors emergently follow an intricate but basically deterministic algorithm. There is no a priori reason to believe that the human brain isn't emergently following a similar algorithm. Psychologists gave up on introspection as a reliable tool for investigating the operation of the brain before there were computers on which to build artificial intelligences. Just because you aren't conscious of the algorithm doesn't mean it isn't there. Indeed, humans can play chess pretty well, and they do so by only consciously considering a small number of moves, so they must be following some sort of algorithm, even if they can't describe why they choose to consider that limited selection of "good" moves.

Point #2: Offering Civilization IV as an exemplar of artificial intelligence programs is a total straw man. Marketing hype and reality are often not the same thing.

Concluding Point #3: There is no question that humans are still much smarter than computers at most problems, but the hardest problems for computers tend to be things that even a 5 year old can master, like vision or language. On the other hand, I think it is unfair to say that chess playing computer programs are not intelligent in any meaningful way. They are simply intelligent in one very particular way. Just as we might marvel at an autistic savant who requires supervision to dress and cook but can calculate square roots in his head, the chess program is behaving intelligently in an extremely limited class of situations. Intelligence is as intelligence does. Just because you can draw back the curtain and see the internal mechanisms does not make it something other than intelligence, just as you would still be intelligent even if you were simulated in transistor-based computer rather than a neuron-based computer.

If we could actually agree what the definition of "intelligence" is, we'd be much further along, but there's no argument that at some point in the near to far future, machines will acheive "intelligence".

Jason, I think (i.e., it is my own opinion and what I believe Martin is saying in his original post) that a meaningful measure of inelligence is to be able to correlate all known facts (including experience) to arrive at a conclusion which has no apparent connection to those facts. In other words, imagination, not the raw power of calculation.

A machine could be taught to make correlations... but frankly, they would then only make the correlations they were taught. Humans aren't necessarily taught to make correlatios or to imagine, they just do so.

The architecture of CPUs and computers as we know them today is an "evolutionary" dead end and it is not a matter of of how much memory a computer has, how fast it is or how it is programmed. They simply have not been designed to achieve intelligence. Maybe, hand-in-hand with intelligence is a necessity to make mistakes... who knows?

The ability to dream and imagine requires a different kind of hardware than a calculator.

Chess is not the best candidate for computer A.I. It's essentially a sophisticated math problem, but the rules are strictly defined, straightforward and easy to program. You can't "cheat" by thinking outside the box like you can in other games.

Still, my guess is that real A.I. will first emerge in computer games. Your Civilization example simply points out that most programmers still take the easy "brute force" approach to computer decision making. The rules are still hard coded and repeated again and again. They aren't really trying to out think a human.

Design a game that rewards the computer for simply surviving and allow it to change its decisions in response to a player's actions and pretty soon you'll see some unique and complicated strategies develop.

Count, I don't think it's really a hardware problem. Network enough PCs and run the right software, and you can simulate a brain (running very slowly). But writing that software is non-trivial.

Jinchi, how painful to be the test pilot who plays the first 2000 games while the computer learns...

Mr. The Count,

Chess programs can indeed "correlate all known facts (including experience) to arrive at a conclusion which has no apparent connection to those facts," so long as you accept experience which is hard-coded in and you restrict your attention to the game of chess. They perform this correlation of known facts (about the current chess game) using a basically deterministic algorithm. I see no difference between properly applied "raw calculation" and "imagination," except that you have no idea where the imagination came from whereas you can describe the method of the raw calculation exactly. If the sole critereon for calling an apparently intelligent process (like playing chess) "actually intelligent" is lack of knowledge as to how it's doing what it's doing, you might consider draping a black cloth emblazoned with the word "imagination" over your computer and pretending you don't know what's inside.

I'm sure there exist chess programs that learn their strategy; they're just not as good as those which are hand-crafted to beat grand masters. But really, that is irrelevant. If God plopped you down just as you are today, specifying all your memories by hand, I hope you would still be willing to call yourself intelligent, even though none of your skills were learned in the traditional fashion. I suppose I just can't imagine a definition of intelligence which is dependent upon learning. Maybe that means I'm not intelligent. Much of what you claim humans can "just do" has been hard-wired in by evolution. Hell, you can walk with only your spinal cord. (Granted, you'll bump into and trip over things, but the action of walking is hard-wired. The corresponding experiments have been done with cats.) The brain is not a blank slate. The computer equivalent is not a processor with a formatted hard drive.

Mr. Turing completeness (e.g., http://en.wikipedia.org/wiki/Turing_completeness) says that a computer can potentially do whatever you can do. Perhaps much slower, as the brain is massively parallel and modern computers are woefully serial, but computation is computation.

PS - I know I'm being mildly inflamatory here, but what's the fun of arguing if you don't do it with feeling?

Hmm... "Mr. The Count", I like that! :)

I don't think that the concept of thinking being equivalent to computing is valid. I would agree that one could simulate (fake) intelligence with said mass of PCs, but it would still be a puppet.

Before we go on, please don't think that I believe that the brain is some special organ that cannot be reproduced or comes from some god given drivel. I just do not think that the electrical architecture and logical functions of a CPU are how our brains work.

On the other hand, I cannot say I have much of a leg to stand on, since I'm only an occasional AI programmer and a former electrical engineer. Besides perusing the relevant literature, I don't have the ability to perform research... so the best I can do is philosophise. :)

I *have* given the problem of a "thinking AI" a bit of professional thought, however, and what I see from my perspective is the lack of proper hardware, the lack of a proper programming language and even the lack of a proper specification to accomplsh even the most basic function. I'm even pretty sure you can't do it effectively with a binary (ones and zeroes) based machine.

Heh, I can also admit that most of the time I'm wrong, but have never been accused of not thinking outside the box. As fas as argument, not a problem, I believe in the "best brains" concept. Everyone can contribute, not everyone can be right all the time and discussing/modifying ideas makes for better ideas.

Last but not least, I originally came here via PZ, and have been quietly reading the blog after PZ linked to an article of Martin's. Having experience with games, AI and Civ prompted me to speak up. My wife, The Countess, is a good friend of PZ's and has had a blog of the same name for the last five or so years. She used to write about feminist/mother's rights issues and now writes about sex, which is finally generating a profit for her (sex sells on the intertubes, don'cha know).

Jinchi, how painful to be the test pilot who plays the first 2000 games while the computer learns...

You don't have to play 2000 games. Imagine a first person shooter like Half-Life. You've got multiple characters on every level coming after you - each one has a set of strategies to stop you in your tracks, and more importantly not to get killed by the player.

Of course, each of these characters is played by the computer, and the computer almost always falls for the same tricks, regardless of how many times it encounters them. A simple code could put a cost to any tactic - rush, retreat, evade, ignore, etc. and dynamically change that cost factor every time it succeeded or failed.

In any case, the game at first would start out no worse than it currently is, but would improve over time. And there are plenty of people spending hours of time on the games we have today.

... And as for why I think true AI will first develop via computer games. Games are the one area where a computer program is at least attempting to compete with a human. Most programmers create characters that are initially better than the player. What they need to do is devise a program that's capable of becoming better than the player.

We don't care much if the software on our cell phones or in a word processor or email program can predict our actions. But games get boring once you've figured out how to always beat the machine.

"Here, instead, the programmer has to establish rules-of-thumb for the software to follow, and it can never be any better at the game than the person who formulated those gaming methods."

By this logic, shouldn't the person who formulated the gaming methods also be able to beat the chess master? We know that this is not neccesarily the case. Otherwise the computer programmer would have just played the chess master himself!

The fact that a human created the program doesn't neccesarily mean that the human is as good at the game as the software he/she creates.

However, I don't think that this makes the computer smarter than the master chess player. It's true that the software was able to beat a human. But this is most likely because the human is much more used to playing with other humans. Humans who give off subtle cues that may suggest the next move or hesitate just slightly over one pawn or flick their eyes towards the next space, etc. The human chess player may not even conciously realize that they are taking these cues into account while they calculate their moves. Now this is true intelligence!

I believe that with enough time, the human would eventually learn to beat the computer, no matter how good the software is.

Angela, the software that plays chess and Civ respectively works on different principles. Chess software does something a human could never do, viz. looks at all possible moves and calculates the likely outcome of each. Civ software has a finite toolbox of methods telling it how to react on certain stimuli. The difference is due to the much lower level of complexity with chess.

Not trying to beat a dead horse here, but if I may, I'd like to provide a simplistic take on game AI. AI usually has two components, a rule (aka expert) based system and a predictive (aka feedback) system.

Simplistically, the rule based system says that if the AI oserves situation A, then do move Z, if situation B then do Y and if a combination of situations A and B then do X. The better the rules, the more granular the rules, the more flexible the rules, the better integrated the rules etc. the better that component of the AI will be.

One trap is that this component can be written, intentionally or not, to be reactive and by reactive I specifically mean AI that waits for the player to do something first. I say intentionally, because cometimes the CPU cycle budget, type of in-game application, project schedule, project finances or designer/coder expertise does not allow for more.

Purely reactive AI is usully easy to spot and exploit by gamers and is generally considered weak. In games that allow me to, I like to let the AI play itself while I observe. I have seen one game, "D-Day: America invades", literally do nothing in such a case. Reactive AI is also the common AI for MMORPG mobs.

Programming "AI initiative" is not necessarily rocket science either. The most common type is the unit rush many RTS games inflict on players. This AI relies on the superior organizing power of a computer; one CPU cycle after a unit is built it is building the next one vs the human's "oh damn, I got so busy fiddling with my headphones that I forgot to build those units". One problem *for me* is that this is not overly satisfying. It is often the equivalent of an arcade game overwhelming the poor human's response time. These games. however, can be more easily beaten by finding and making it cross the "line" where it becomes reactive. Somewhere in its programming, there's a threat pattern which causes the switch, your job is to find it.

In Civ III it is size that matters. :) Not to spoil it, but dangle a big enough army (but not too big or it will sit back and go completely defensive), especially if it is in AI territory, and the AI will home in on it. It will also *utterly* ignore the second army that is precisely X times or less smaller (and so as not to completely spoil it, you get to figure out X) which you are marching around capturing AI town after AI town after AI twon. Here's a case of an AI with initiative being forced into reacting to your large army but since you've inferred its rules you're letting the AI be defeated by its own rules.

The predictive part determines the "goodness" of applying a particular rule. This is where, as Martin says, a simple system such as chess, checkers or go allows the calculating power of a computer to be unleashed, by allowing it to model the system and then see the outcome X number of plys (moves) down the line. Obviously the greater the number of plys it looks ahead, the smaller the return because each ply becomes subject to the variance in likelyhood of possible responses. By the same token, chess AI gets very strong in the end game with fewer pieces which allow fewer responses which allow the AI to calculate more plys. In the same vein, once there are few enough pieces, chess end game algorithms come into play and you are royally screwed if you don't know them all (this part also applies in human vs human games). The first trick is to essentially beat the AI by mid game so it does not have the board position or the pieces to mount an effective threat in the end game, because it *can* outcalculate you and in a game with no random element, can usually recognize a bluff or ploy for what it is. The same is not true in human vs human games.

The first chess playing algorithms did only that. They were purely reactive, but they could beat some human players by staying out of trouble and relying on human mistakes. These early AIs had human coaches to do the rule based parts. Later AIs would incorporate, into their programming, rules based on the various gambits played and recorded through history. The second trick is to survive, in decent shape, into the mid-game (aka break out of the gambit you're in), because decent chess AI has hundreds of gambits and variants in it's database.

The mid game is where the AI is on its own and has to rely on the rules programmed in... which is why the AI is only as good as whomever designed the rules. As an example, a while ago I found out through the grapevine that the AI designer for the 1998 Hasbro Interactive Axis & Allies game had never played the A&A board game... which explains a lot about the computer game version.

Oh, BTW, yes, I ramble on a lot... just tell me to shut up! :)

I see the same thing in MMOs (massively multiplayer games). There, the "AI"'s almost never use the same tactics an intelligent player would use. For example, when you play a character that uses a "pet" - or an AI sidekick - another player would naturally go for the player unless forced to attack the pet either due to game effects (though "taunts" rarely work on players) or some overwhelming advantage the pet gives (like very high damage or a number of buffs), since the pet will despawn once the player dies anyway, and it usually doesn't give experience. Not to mention the Pet will often have more hit points than its master.

But AI's won't do any of this. They simply go by which one is generating the most "aggro" -- which is based mainly on proximity, damage done, and the effects of special abilities called "taunts".

I think the thing that fools people, though, is that using these simple rules the computer will accidentally come up with good strategies. For example, if you're not careful as a pet class moving through a group of hostiles, enemies could engage you in such a way as to separate you from your pet, making it difficult to focus your energy on one creature because unless specifically ordered, the pet will follow the same rules as the enemy AI (and it's not always a good idea to call the pet away from another enemy, lest it get killed).

The idea is, sometimes it's not so easy to tell that these creatures aren't thinking. I'm sure if I looked in the code for these creatures, there would be nothing that would lead it to make a tactical decision to separate a player from an AI pet through cooperation. It's just a simple order to attack anything that attacks it, and to attack anyone of a certain faction within a certain level range that comes near them. That's why pets, and in parties, "tank" characters, are very effective at distracting these AIs while casters, pet masters, and other ranged fighters stand back and take advantage of not being beat on while they cast their spells or shoot their arrows. Even when casters have the potential to do more harm, enemies will focus on the highly durable tank that's taunting them into fighting him.

Decent post and good comments...
But you have completely missed the point of the handicap system in golf.
OF COURSE it leads to re-evaluation of an individual's handicap in successive trials! Rather than making it pointless, that's the whole idea!

Player A is awesome, shoots par consistently.
Player B is raw, usually shoots 25 over.
If A has a bad day, and shoots much worse than his average, and B has really been working hard, and has a peak experience, we mathematically define B's performance as a "victory" in order that A and B can have fun playing together even though their relative skill levels would otherwise make the match hopeless and frustrating for B and boring and pointless for A.

And as Player B works, improves, and transforms, his handicap becomes smaller and smaller until eventually he transforms into Player A! Personal growth and transformative experiences like the challenges and responses exhibited by Player B are, in fact, what skilled programmers are hoping to model when they try to develop AI that has a more adaptive response. Human beings learn from successive trials and modify their responses.
Cool, huh?

3torches, my point is that the distinction between somebody having a good day and someone having too high a handicap is undefined.

It is one of the most well-defined sporting statistics around! The game is played internationally, by professionals and amateurs, at large and famous professional courses, to small public community courses, to prestigious and private social clubs, and at each of these places you can find teachers and coaches, and experienced players who will help newer players to improve. Many courses and clubs have "handicap commitees" to ensure consistent handicap calculations.

Calculating the handicap is done over the course of time, and represents a "moving average" which is expected to grow smaller as you improve. Your score is compared to the standard "par" score, which is a term so well-known that it has entered the language for the customary or expected total which recurs over time.
As your average score grows closer to the "par" for the course, your "handicap" grows smaller and smaller, as it is a mathematical representation of the number of strokes you typically require over and above the number of strokes a skillful player requires.
And because it is a moving average, calculated from the results of many, many successive trials, it is possible to define a "good day" as beating your 15-, 30-, 45-, or 90- day "moving average."
(Stocks are often weighted and discussed the same way, by comparing the instantaneous price to the average or cumulative price over some agreed-upon time frame.)
For mathematical purposes, it is similar (in a way) to comparing the slope of a tangent line (one game result) to the slope of a secant line (average over several games). This is one way to determine if you are getting better or worse over time.

To see the calculations and parameters, try here:
http://golf.about.com/cs/handicapping/a/howcalculated.htm

But I think you are correct to point out that as you have more "good days" your handicap is redefined...it is just that this is an intentional process, not an unintended consequence! You need many "good days" before your peers begin to regard you as improved rather than merely lucky, and your handicap comes down slowly as older higher scores are dropped from your calculations and replaced with lower scores from the new, improved you.

As a player, a "low handicap" golfer can be expected to play with a high degree of skill, and a "high handicapper" can be expected to be a less skillful player, but the results of any one trial (one match at a time) remain more unpredictable.

my computer dell duel core not responding to any game

I'm sorry to hear it.