Computer Science Canada [Lesson] Introductory to AI

Author:  Tony [ Fri Mar 05, 2004 8:00 pm ]
Post subject:  [Lesson] Introductory to AI

Artificial Intelligence (commonly known as AI) is an important part of any program, but is most visible in games. A good AI greatly adds to playability of the game, unfortunately the concepts of AI are not even remotely covered in most of computer science courses (or anything else of importance). Hopefully this tutorial will familiarize you with AI well enough to use it in your next project.

AI is a part of the program that resembles intelligence, something that calculates the next step. In reality, AI is really just a function that takes available information as its arguments and returns the next step(s) to take to achieve the objective.

AI's complexity largely depends on the objective for which steps are to be calculated. Students will often program two player games and freak out when seeing A next to I on their assignment sheets. Some students in my school convinced our compsci teacher to drop the AI part of the final project, leaving just a 2 player tic-tac-toe (15 mins program in VB - been there, done that, timed myself). I don't blame them though, concept was not covered and they didn't even know where to start. I blame the teachers who tell arguments for syntax, but don't explain any concepts. That said, Professor Tony will start his lecture with the simplest AI ever.

Rock Paper Scissors
We are going to start easy and gradually move up though different AIs. For now, who knows how to program an AI for...

everybody tosses their notes and jumps to hide under desks
Prof. Tony -"sigh Rock Paper Scissors"

Just think about the game itself for a moment, both players independently and randomly pick one of three objects and compare. Since actions are done independently, the whole objective is reduced to randomly picking 1 of 3 objects - rock, paper or scissors . Assuming the user will not get tired of this pointless game and throws a finger, it seems simple enough.

 code: function AI() :int result Rand.Int(1,3) end AI

Simple, isn't it?
Prof. Tony - "see, AI doesn't bite, yet , so get out from under your desks and lets continue our lesson."

Pong
A lot of students program pong at one point or other, since it's quite simple yet playable (unlike our Rock Paper Scissors playmate). AI for pong is also really easy. AI's purpose is to replace 2nd player whose objective is to not let the ball pass the line behind his paddle. Now many might be thinking "ok, plot balls trajectory and find where ball will try to intersect the goal line". Though here our purpose is to replace the 2nd player - who obviously can't calculate that info as the ball hits the other paddle. AI would win the pong match every time, but fail our purpose. What 2nd player can do is follow the ball back and forth.

 code: function AI(ballX :int) :string if ballX < paddleX then result "left" else result "right" end if end AI

That would be much more human. The AI is there to play with. If the puddle would stand in one place, it would be too easy to win. If AI would know the trajectory of the ball for the next 10 hits, it would be impossible to beat. It is important to not only achieve the objective, but to do so fairly, based on user's skill level as well(you would often find AI's skill level settings under many games' options).

BlackJack(and other card games)
Card games have rules. If you want to know them, grab your fake ID and head over to a local casino. The AI has to follow game rules, but make decisions based on its cards and known cards of others. Now you got to understand that known cards and cards in user's hand are separate arrays. Known cards are those that were revealed and user took. This memory array should have max size and life-time based on AI's skill. (if you want to add complexity, face cards can have a longer lifespan in memory since players pay more attention to them)

Back to blackjack though... AI is usually the dealer. I'm not sure if it's an actual rule or not, but the dealer always hits until he has 16+. That is it actually for the AI"¦

 code: function AI(cardSum :int) if cardSum < 16 then result "hit" else result "end" end if end AI

Prof. Tony - "hey you! Wake up, no sleeping on the keyboard, your drool might short circuit.. something... or other"¦"

Alright, sorry for being boring, but we had to cover AI basics, understand that it's not hard.

Prof. Tony - "boo! AI!"
-"did I scare you? No?"
-"Good, that means we're now friends with AI and can move on to more complex systems.

Racing Games
We're still dealing with an easy AI here, the main problem is that AI will be driving differently then the user, and that confuses beginner programmers. Unlike the user who "drives straight until a turn is seen", AI follows a path of waypoints placed throughout the track, it doesn't see turns, but calculates how much off-track it is and what way to turn to get back on laid out path. The AI can be driving a supped up tank with its windshield painted black and still complete the race. All it really does is drives towards the next waypoint and follows speed instructions from last waypoint (such as 'drop to 40' before turn).

In a way, such kind of an AI can be considered an animation.

Strategy Games
Prof. Tony - "no, no... Come back, we are going to start with something simple, say chess or checkers for example."

The idea here is to analyze a bunch of possible moves and decide on the best one. The most famous chess playing programs are Deep Blue and later Deep Blue Junior (available commercially), thought they participated in matches with a dozen programmers to twick the program in between matches and a truckload of electronics. Programs analyze crazy amount of moves per second and make decisions based on which move will result in better position 10-20 moves ahead. We are not going to do that, just play with idea of analyzing environment (present or future).

In chess, analyzing is so much more then counting number of pieces. You've got to take all the tactics involved into the count. Forks, x-rays, pins, screws, defense/offence of strategic locations...

Strategy games as we know them are much the same way, but because of fog of war and our goal of humanizing the AI, we don't have to worry ourselves, wondering if its better to move a marine 10 pixels to the right or not. There's usually a build plan that AI follows.

"¢ Build town hall
"¢ Build 5 workers
"¢ Build farm
"¢ Build barracks
"¢ Etc.

Blizzard provides a number of build orders for StarCraft, even more on fan sites. What AI has to do is to just decide on the location to place the building.

Unlike the chess, you don't have to worry about the minor details. If you have (and you should) have a unit AI, you don't need to program any micromanagement, just "group 2, attack X/Y", units will pick what to shoot at themselves (though you'd have to program that too, but that's separate and much simpler since it's on a smaller scale). Your strategy is your build order. You should edit it based on environment and events:

"¢ If on a small island - delay defense production since ships are further down the tech tree.
"¢ If opponents are known to have more of a certain unit type, rebalance defense build.

Analyzing is still important. Especially before ordering an attack. Your units vs. estimate of theirs for example. If there are multiple entrances to base, see which one is less defended by ordering a unit to scout.

StarCraft has got to be one of the strategy games with most info written for. You can easily find build orders and unit combination tactics. Reading such material will help you to put together an AI for your strategy game.

As for the unit's AI, you look just at area around it. Stick close to the group and shoot at unit with the least HP within range.

 Author: wtd [ Fri Mar 05, 2004 9:18 pm ] Post subject: Nicely done, but perhaps lessons like this should be broken up in the future, with one handling Pong, one for Strategy games, etc. Give people opportunities to ask frequent focused questions and you help ensure "students" aren't asking questions on chapter 1 halfway through chapter 10.

 Author: jonos [ Fri Mar 05, 2004 9:28 pm ] Post subject: nice, really helpful, helped me out with my 3d pong cause im too stupid to figure it out,

 Author: shorthair [ Fri Mar 05, 2004 9:51 pm ] Post subject: Very well done , but it does not cover true AI , i mean you can major in it for a university degree, so obviuosly AI isnt hte easiets of things , but the only true ai is one that learns and thinks for itself dpending on hundreds of variables , not ranom or set actions

 Author: Maverick [ Sun Mar 07, 2004 12:19 am ] Post subject: hey really good job. Thanx alot.

 Author: Acid [ Thu Mar 11, 2004 12:03 am ] Post subject: Wicked tutorial. I programmed a game of pong once. It ended up not working, and I quit.

 Author: Rip_leyLp13 [ Thu Mar 11, 2004 1:35 pm ] Post subject: I really find this being helpfull thanks

 Author: gamer [ Sun Apr 18, 2004 2:34 pm ] Post subject: gj tutorial

 :