Investigation into Computer AI, and the Math Behind It.

 

Joseph F. Pegues

Shepherd University

Mathematics

Dr. Christopher E Elmer – Advisor

 

Computer artificial intelligence is a ever growing field of computer science. Yet despite being born in that field, AI has unlimited potential to help in any number of different fields. This project is to examine the workings behind computer AI programming and show that the only limitation of the number of jobs an AI can perform is the imagination and skill of the coder.

    To prove this, computer AI code will be examined the limited environment of Quake 2. Bots, acquired from the internet, will be examined and studied. Then these same bots will be modified to perform different types of jobs then what they were originally intended. The hope is that by showing a bots that can perform a variety of jobs even in a limited environment, it will show that bots when outside of that environment can do an untold number of different functions; thereby, expanding artificial intelligence into a greater number of fields.

 

 

Hello. If you’ve made it to this page, then you’ve come across my Math 329 Project page. This project is designed to not only help with my understanding of computer code and the design of computer artificial intelligence, but also to help me better understand the math that works behind the scenes of computer code. For this project I will be using Quake 2 and online community provided bots.

 

Originally this project had a 5 week time line. It looked like the following:

 

Week 1: Go through the 42 files of bot 3ZB2 and understand how they work together.

Week 2: Model 3ZB2’s code mathematically, and begin going through bot GLADIATOR’s code.

Week 3: Finish going through GLADIATOR’s 141 files and understanding how they work.

Week 4: Model GLADIATOR’s code mathematically, and begin making modifications to 3ZB2’s code.

Week 5: Finish modeling GLADIATOR, and produce as many variations of 3ZB2 as possible.

 

After week one though, it became quite clear that the timeline had far too much in it. As such it was changed to this:

 

Week 1: Go through the 42 files of bot 3ZB2 and understand what the files are trying to achieve.

Week 2: Begin understanding how the bot works by going through the code line by line.

Week 3: Try to finish going through as much of the bot code as possible.

Week 4: Begin making modified bots by altering 3ZB2’s code.

 

 

After it was all said and done though, the time line really looked like this:

 

Week 1: Go through all 42 files of bot 3ZB2, and gather a basic understanding of what the file is for, and the types of functions they have in them.

Week 2: Begin going through the bot code – Study how the bot actually functions.

Week 3: Continue with what started in week 2. Try to locate where the artificial intelligence actually begins.

Week 4: Start to modify the bot to perform different jobs.

Week 5: Finish the last of the bot varients. Also gain greater understanding of how the bot operates.

 

This page is a record of how the project developed, and what was gained. Each week will have recorded events, and towards the end video will be shown of each bot developed. Hope you enjoy the ride.

 

 

Over the course of the project, the goal was to develop multiple variations of 3ZB2. This is the original list of bots that I came up with to create:

 

1.)  A bot that will not attack until it has a completely full inventory and then will completely unload before hunting for more items.

2.)  A bot that will not attack, but will instead give other players items that it has collected.

3.)  A bot that cannot map, but has knowledge of every item on the map.

4.)  A bot that can map, but has no knowledge of item locations on the map.

 

As I figured out the code more, I realized that the bots that dealt with mapping just weren’t feasible. As such I created four bots to replace them.

 

1)    A bot that will stay in a constant combat state.

2)    A bot that will never enter combat state.

3)    A bot that move too quickly, and as such many of its calculations are wrong.

4)    A bot that moves backwards, and as such many of its calculations are wrong.

 

A seventh bot was attempted, but never reached completion.

 

 

Background

 

          Before we get in too deep into what was done for this project, a bit of background knowledge is necessary. For example what is a bot? A bot is a computer controlled player in a multiplayer video game. It’s purpose is to ‘stand in’ for a human opponent when enough can’t be found. The hope is that the bot can perform as well or better than your average human. To do this the bot must have the ability to think though. It must use logic patterns to come up with its next course of action, and must be able to interact well with the environment around it. This means that a bot is a artificial intelligence program, and depending on the environment it may be simple or extremely complex.

          For the environment of this project Quake 2 was used. Quake 2 is a 1997 first person shooter video game. It is considered a classic ‘old school’ game, with a simple environment that is designed for ‘frag fest’ style gaming. It was chosen as the environment because: it was easy to obtain, the source code is available for those who purchase it, and bots can be acquired online for free. Also its simple environment makes understanding how the game and the bots work easier.

 

          The bot studied for this project was one called 3ZB2. This bot was created by Ponpoko (Online name) and hosted at his site: http://ponpoko.tri6.net/3zb2/. The bot focuses on gathering information about the environment around it and making a decision without planning into the future. This means the bot reacts to the environment every game frame. This may not seem like a strong thinking pattern, but it allows the bot to move and react to any situation it finds itself in without taking time to think because the plan it had gets messed up. It is very fast, and very strong within its environment.

          And here’s a video showing it off:

 

 

 

 

Week 1

 

          The first week of this project was spend glancing at the files and their code. The idea was not to understand what everything did perfectly, but rather try to understand where everything was. Gaining perfect understanding of how the bot performs and works can take a great deal of time, and since the project was on a time limit, rather than figure everything out it is better to just have an idea of where everything is so that if you need it, you’ll automatically know where to find it.

          The results of this week can be found in these text documents: file 1, file 2.These files haven’t been messed with since the beginning of the project. There maybe some information overlap as a result.

 

          Sadly as the project went on, most of the information in those files turned out to be wrong. It was discovered later that when creating mods, modification projects, for Quake 2 that one actually uses Quake 2 source as a base. This means that only the bot files, the files that say bot, are really what is where the bot information is stored. Some other files have been modified to take into account for the bot, but most of them have remained untouched.

 

 

Week 2

 

            Quake 2 is built using the programming language c. All of it’s code and the bots code is also written in it. Being unfamiliar with the language greatly slowed down this week’s progress. A great deal of time was spent figuring out how pointers work, and certain information that the bot seemed to carry around.

 

          The most important of this information is a data structure called edict_T. Created in g_local.h, it is used across the entire game programming and the bot uses it heavily for its logic. It houses many variables and even links itself to new data structures, some of them even being edict_T type. The information stored in it is used for everything from inventory management to movement. \

          Two sources that were a great deal of help when studying it were: at http://developer.valvesoftware.com/wiki/Edict_t and http://ponpoko.tri6.net/quake2/q2struct/.

 

          Some work from week two can be read in file 3.

 

Week 3

 

        Week three continued working with information gained in week two. Little was gained though because only when modifications begin to true understanding of the code begin.

 

 

Week 4 and 5

 

          Week four begin the actual modifications to the bot. And as this work began, how the bot actually performed started to become clear.

 

          Packrat

          Packrat is a modification of how 3ZB2 handles inventory data. For combat purposes the bot cares only about inventory data to make sure it can still fire weapons at its opponent. In the case of Packrat this has been changed. Packrat must first horde items before it can engage any enemy. That is  to say that packrat must obtain a high level of every gun and ammo in the game before it is allowed to attack an enemy. For presentation purposes though these numbers were lowered, because this bot can take a very long time to get off the ground.

          Packrat is not a modification of how 3ZB2 gathers or interprets inventory data. Instead the bot examines the data at a new location in its code and makes a decision based off of it.

 

          Packrat’s thinking logic looks very similar to this: packrat. And here is a video presentation of packrat:    

 

 

            Santabot

          Santabot is a modification of how 3ZB2 engages an opponent. Normally a bot must see an opponent than decide if it wishes to go into a combat state. Once in this combat state it will then engage the opponent. Santabot instead never goes into combat mode. Rather than engage an enemy, Santabot gives away items to an enemy that is sees. It does this by checking what it has available in inventory and then uses the drop item function to drop an item.

Santa 2.JPG

          The purpose of this bot is to show that even though Quake 2 is designed for frag fest style gaming, it is possible to create objects within the game that can interact with the environment but do so without attempting to harm the player.

 

          A quick glance at Santabot’s logic can be found here. And here is a video presentation of Santabot.

 

 

 

          Teleport and Backwards

          Packrat and Santabot took about a week for their creation, and since time was an issue a new pattern for bot creation emerged. Teleport and Backwards are bots that are not heavy modifications of 3ZB2’s code, but rather they alter variables within the code to create new logics and new bots. These two bots are both modifications of speed. Speed is used for logic that involves aiming and movement. The hope was that modifying these variables that new logic patterns emerged.

 

          Teleport was created by multiplying the bot’s base speed by ten. The result is a bot that moves so fast that it looks like it’s teleporting most of the time. What is truly interesting about the bot though, is that it acts in a almost chaotic behavior. This behavior is caused by the bot thinking that it’s going to end up somewhere and then overshooting that mark. As a result it can never get to where it wants and then must make a completely new logic pattern to adjust for how much the world around it has changed. Teleport is most often found wielding the base gun, because it has difficulty acquiring any other weapon.

 

          Backwards was created by multiplying the bot’s base speed by negative one. The result is a bot that moves backwards of course. The bot’s aiming and directional capabilities are off, but are not greatly hampered. Aiming is only minorly effected, since it is only slightly off mark, and at a close distance this matters little. Movement is hampered by walls as the bot can get easily stuck by not being able to move in the direction it is trying and walking up a  corner and then being unable to leave. What is interesting though is that the bot can still operate what appears to be normally some of the time. Particularly in open spaces, the bot has little trouble moving about.

 

          These bots are good examples to use because they show that bots do not have to use the same rules as players or even other bots. Teleport could easily be seen as a cheat device, if it wasn’t constantly killing itself. And since they don’t follow the same rules as players then the environment interaction is different.

 

          And here is a video presentation of the two bots:

 

 

 

          EnemiesAbound and GhostsAbound

          Much like Teleport and Backwards these bots are born of opposite logic patterns. These bots however deal with the bot readiness to enter combat readiness as opposed to speed.

         

          EnemiesAbound was created by putting the bot into a constant state of combat readiness. The distinction between this bot and 3ZB2 is quite remarkable. To start with this bot is smarter and acts more human like the 3ZB2. It always targets the nearest opponent, and never untargets them if it looses sight. As a result this bot will attack from places the 3ZB2 will rarely attack from, and it’ll chase a player down. Also the bot seems to use the environment more to help it win against enemy players. And for reasons that are not understood the bot also fancies the rocket launcher above all other weapons in the game, and will even seek it out if it does not have it.

 

          GhostsAbound is a much simpler but in terms of logic. Unlike EnemiesAbound, this bot can never enter combat readiness. This means that no matter what it comes in contact with it can’t attack any opponent even if shot at. While not interesting as it is, this could be expanded upon easily to create bots that interact with the environment in interesting ways. Perhaps one that does not attack when not attacked? Or one that starts off unable to attack but the more it is attacked the more aggressive it becomes (till it finally becomes enemiesabound)?

 

          And here is a video presentation:

 

 

          Guardbot

          Guardbot was the final bot that was attempted for the project. The hope was to develop a bot that could seek out an item in the game and then guard it from other players. Unfortunately the bot was never completed because I mistook how the movement logic worked. This did lead into an investigation of how that logic works, and how to implement such a bot.

          3ZB2 works by first selecting an item to hunt out if it doesn’t have one. Once it is selected the bot will then try to move in that direction. But along with this direction the bot also tries to move along prerecorded routes that are stored in another file. To accommodate for both movements the bot tries to alter what route it is on, by where it is in accordance to all routes on the map. This is used so that the bot can travel on the map freely, and picks up items that it has not targeted with the seek item function. This creates a behavior that is very close to what human players do.

          Unfortunately this logic also makes having the bot guard one item very difficult since the routes are already compiled and I do not have access to that information. The creation of such a bot if one had the route data should not be too difficult however. One would only need to create route data that put the bot where it is needed to guard. Then by removing the item seeking command, the bot would not leave its route. Or this bot could be created using point data on the map. This way it knows to never go beyond those certain boundaries when following the routes on the map.

 

          An example of the code I had attempted for this project can be found here.

 

 

Conclusion

        It is the conclusion of this project that the goal has been reached. Although most of the bots presented are very simple, they do show how bots can interact differently with the environment then what is normal. This is impressive because Quake 2 is a very simple environment at its core. It is designed to do one thing well, and it does.

          As far as continuing this project, I do not think I will be do so with Quake 2. Quake 2 is a great environment, but it is old and outdated. By using newer environments it would be possible to show even greater variations in the bots. Something like Half-Life 2 would be a good choice. If I did continue using Quake 2 then I would stop using 3ZB2. A different bot might have different logic pattern, but the best thing to do would probably build one from scratch and see if planning could be implemented into the bot.

 

          If you’re interested in this project then I ask that you check out 3ZB2 here. And if you would like to see my bots then here and here they are. They are already compiled in one. To see them in action simply place the folders in your Quake 2 main folder then click the 3ZB2 bat file to get them started. Press ` and then type “sv spb #” without the quotations.

          A copy of the research paper that goes with this can be downloaded here, and the poster can be downloaded here.

 

          Thank you for reading. And thanks to NASA WV Space Grant Consortium for the grant it offers that led to the creation of the project, Dr. Elmer for guiding my work, FRAPS for its recording software, and Aaron Robertson for helping me with code and logic thinking.

 

This page was last updated Dec.  10, 2009.