Artificial Intelligence in Gaming Ryan Donnelly Department of Computer Science University of Wisconsin Platteville
Download 38.11 Kb.
|
- Navigate this page:
- AI in First Person Shooter (FPS-type) Games
- AI in Real Time Strategy (RTS-type) games
- AI in Role Playing Games (RPG)
- Popular AI Algorithms Used In Computer Games
- Artificial Neural Networks
| Artificial Intelligence in Gaming
Ryan Donnelly Department of Computer Science University of Wisconsin Platteville donnelry@uwplatt.edu Abstract Artificial intelligence (AI) in gaming is getting more and more realistic as we head well into the twentieth century. But will we ever be at a state where games replicate humans perfectly on a consistent basis and learn their instincts? Games are getting more complicated. This is due to the use of more advanced algorithms that are being used as well as the new hardware that allows more computations. Games wouldn’t be where they are today if it wasn’t for artificial intelligence. I will be discussing the importance of artificial intelligence in games such as RTS-type games, First Person Shooter-type (FPS-type) and sports games. I will also discuss the most popular algorithms used today for artificial intelligence in games such as A* algorithm, finite state machines, and artificial neural networks. Introduction AI in gaming refers to methods used to produce intelligence of non-player characters or computer players. The methods are usually created from existing methods in AI. There may be other methods used but it is a vastly different approach to common AI. In first person shooter (FPS) games the computer is basically cheating due to the fact that it has to know where you are at all times to try to achieve the most intelligent non-player character. In a lot of cases, the AI of the non-player character has to be lowered or tweaked to give the human player a sign of fairness and a chance to win. Programmers will want to stay away from cheating as much as possible. In a way this makes the game have an unrealistic challenge because it is not using intelligence. Cheating also draws away focus from programmers to program more human-like bots. AI can also be thought as to simulate thinking, or as representing intelligent behavior in an algorithmic way [3]. When creating AI for games, one thing should always be in the programming team’s head, “what would a human player do?” The obvious goal is to make games to have a realistic challenge for the human-players. This makes sure that the game does not get too boring and shoved under the shelf in a week. Many techniques are used to achieve human like behavior for computer players. The most popular techniques are the A* algorithm, finite machines, and artificial neural networks. Each contributes to the AI in different ways. Without these techniques AI wouldn’t be where it is today not only in games but in all other software trying to replicate human intelligence. History Videogames first entered the world in the 1960s and into the early 1970s with the likes of Spacewar!, Pong, and Gotcha [1]. These games had no AI in them but used some discrete logic because they were based on a competition between two human players. Artificial Intelligence began to get implemented into games in the 1970s with a single player mode to play against the computer enemies [1]. The enemy moved by the use of stored patterns. Stored patterns are paths that never change, and the computer-players follow the same paths that are stored in the game. When microprocessors came into play, the building of the AI became more complex due to the speed and amount of computation that the microprocessors allowed. When the game Space Invaders was released in 1978, it brought to the table distinct moving patterns, which is different from stored patterns in that there are different paths for the computer-player [1]. The following year, Galaxian was released and the AI in this game stepped it up a notch from Space Invaders in that it allowed for more complex and varied enemy movements [1]. Pac-Man debuted in 1980 and was the first popular game character. Pac-Man sold all kinds of memorabilia. As the years went on, different personalities for the enemy were introduced as well as fighting games such as Karate Champ in 1984 [1]. A big accomplishment for AI occurred in 1983 when a human player went down in defeat to a computer player in chess. This was the first victory recorded for AI against a human player at anything. This opened up many eyes in the software industry. An even bigger accomplishment for AI occurred in 1997 when Deep Blue, a chess playing computer developed by IBM, defeated Kasparov, a world champion chess player [1]. This event gave confidence to every AI developer to believe that anything can be done or programmed to what they want it to be or do. Sports games advanced game AI in the early 1990s with the use of expert systems [1]. An expert system is a program that contains knowledge on a subject of one or more human experts. An example would be the popular Madden Football series. The AI of this game tried to mock the coaching or managerial style of John Madden himself. Extensive work and time put into this game to try to maximize the accuracy of the AI. In the newer Madden games one can change the variables of the opponent to play how the user wants them to play. Most games now have a difficulty level as well which allows the user to pick a difficulty level which matches their experience with the game. Finite state machines started to enter the gaming world in the 1990s as well as artificial neural networks. Real-time strategy and first-person shooter type games first entered the market in the 90s as well. The first Real-Time Strategy games had notorious problems which included path finding problems, real-time decisions and economic playing and many more. As for an example, in the game Dune II, the enemy uses cheats and when the computer-players attack a human base, they attack in a bee line instead of attacking in random positions [1]. The RTS games did get better in the AI department and have gotten more popular. For instance, one of the most popular games are the WarCraft series, and in the 1990s the first WarCraft game was the first game to ever implement path-finding algorithms at such a big scale for hundreds of units to engage in huge battles [2]. Graphic cards also come out in the 90s and allow for more processor time to be spent on AI. What we are seeing now in the 21st century is that more games are successfully implementing artificial neural networks. Battlecruiser 3000AD was the first game to use neural networks 1996 [2]. That spawned the games Creatures and Black & White where computer-controlled characters’ learning was used for the first time. Hyper-threading processors came out in the early 2000s as well as just recently the core-duo processors which allow for even more of a complex AI engine to be built. AI in First Person Shooter (FPS-type) Games In first person shooter-type games the AI is in the opponents, teammates, and extra characters. First person shooter-type games can be created using a layered artificial intelligence structure. The bottom layers take care of the trivial tasks such as determining the best path to the target, and the top layers deal with reasoning and the behavior of the computer player [2]. When a behavior is decided, the lower-level module selects the best tactics for completing a task. After the tactic is picked, the AI of the computer player determines the best approach for the situation. For example, if the tactic picked is to fight, the approach could be to sneak up on the opponent, hide and wait for the opponent, or run at the opponent and firing. An event driven engine can also be used where action is taken based on specific events that happen. For example, some events with actions could be [3]: If enemy seen → Then attack with best weapon If wounded → Then run away or hide and find health If out of ammo → Then find ammo
Low ammo → Add 20% to restock Low health → Add 20% to flee and 10% to restock A lot of ammo and health → Add 50% to fight, remove 20% from flee and restock Lost 50% health in one hit → Add 50% to flee, add 20% to restock and remove 50% from fight.
Figure 1: Representation of the world in a FPS-type game with the red lines being a path. AI in Real Time Strategy (RTS-type) games Just like in first-person shooters, RTS-type games must implement a path-finding system. Path-finding is more important in RTS-type games in that some games require this module to have a solution for movement of hundreds of units on the map and it needs to be done in seconds. Because there are numerous computer-controlled players on the map, this module must also handle collisions between the units so they don’t run into each other. The units themselves are controlled by an event driven engine where action is taken based on events. The same rules apply here as they do in first-person shooters. It is also a good idea to use leaking buckets. Most maps are represented by a rectangular grid as shown in figure 2. A module is used to analyze the game map. This module uses a goal driven engine which works by taking the highest ranked goal and processing it. Smaller sub-goals are created as needed and are processed until the goal has been fulfilled [3]. This module has to also analyze the terrain and a settlement can be built based on the evaluation of the terrain. The same module decides when cities should be built and how reinforcements should be placed. An example which shows the interaction between the event driven engine and the goal driven engine could be as follows: a building gets blown up by an air strike. This sparks the event based engine to give a new goal to the goal based engine to increase air defenses. The goal based engine responds by moving units that are capable of air defense into position [3]. 
Figure 2: Representation of the world in a RTS-type game with the red lines being a path AI in Role Playing Games (RPG) Artificial intelligence in RPGs has historically been scarce. They have mostly been dependent on random encounters or scripted behavior. The random encounters are mostly seen in the games where there is a lot of fighting and where moving up in levels is more important [3]. Scripted behavior has some minor AI involved and is common in games where the story line is more important [3]. These games can have some fighting as well but it is usually kept to a minimum. Some games implement a combination of both scripted behavior and random encounters AI in Sports Games A lot of the AI in sports games has some sort of cheating. For example, in racing games, two paths are marked on the track: the first represents the optimal driving path; the second represents the path used when passing opponents. Basically it is the same as stored patterns. The track is also split into sectors and each sector length is calculated. These sectors are used to build a graph describing the track and to acquire characteristics of the track in the vehicle’s closest vicinity [2]. In effect, the computer-driver knows when to slow down if a curve is near because it knows what sectors are approaching. The AI system in racing games must also analyze the terrain to detect objects in the road so the computer-driver can go around it or hit it if preferred. There must also be co-operation between the AI system and the physics module [2]. The physics module provides information such as when the car is skidding and the AI system needs to react immediately to get the vehicle under control. 
Figure 3: Segmentation and driving paths of the track. Blue represents optimal path, dashed pink represents passing path. Cheating can be found in other sports games as well. A lot of times, the computer-player’s behavior or move is decided before the beginning of its turn. This is not realistic AI and should be avoided. The computer-player should evaluate the human-player’s move before deciding a move of its own. Popular AI Algorithms Used In Computer Games By having knowledge of a couple of algorithms, one can design a simple AI system for simple FPS or RTS-type games. One of the algorithms is the A-Star (A*) algorithm which is used for finding optimal paths. Another algorithm is the finite state machine which prepares behavior scenarios for the computer players [2]. One becoming more popular due to better technology is artificial neural networks. The A* Algorithm A key problem in most games is finding a path from two points on a map. Not only does the A* algorithm find a path between two points, but it finds the shortest path between two points. The computer game world has thoroughly evaluated the issue of path-finding and to this date, the A* algorithm has become a standard in games where path-finding is a huge part of the computer-player movement. Prerequisites Two prerequisites are needed for A* to work. There must be a graph or a map of the game world. The map can be divided into squares with each square containing a value. Each square will have eight neighbors unless it is located on the edge of the map or near an obstacle. A method also needs to be developed to estimate the distance between two points. This is the heuristic of the algorithm. This heuristic must underestimate the distance to ensure the algorithm will find the shortest path. If it overestimates the distance it will slightly run faster and still find a path, but it won’t necessarily be the shortest path. Method How about try all paths, and then choose the shortest? This will work, but it takes time and resources. This is where A* comes in to play. A* minimizes areas of the map to be examined by orienting the search towards the target and guaranteeing to find the shortest path. This is the main advantage of A*. It is faster and guarantees to find the shortest, most optimal path, and in today’s games, we can’t go with out it. The algorithm uses some heuristic to help orient the search towards the target. Typically, the heuristic is the estimated cost of getting to the destination or target, that is, the distance from the current point being examined to the target or destination. The heuristic must be an underestimate of the actual cost. If it is an overestimate it may run slightly faster and a path will still be found, but it doesn’t guarantee that it will be the shortest or optimal path. Optimal does not always mean the shortest. Additional factors need to be taken account such as the terrain, angle of turns, number of enemies in area, and others depending on the game [2]. Some games may have the algorithm avoid certain areas or situations occurring on the map. For example if there is a battle or firing of a weapon you may want to keep distance from teammates or friendly units. Algorithm The algorithm can be a bit confusing at first. Once there is a basic understanding of a few concepts the algorithm uses, it is not as trivial. One concept is an open list. The open list contains the nodes that need to be considered as possible starts for future growth of the path [5]. The start node is typically placed into this list at the beginning. Now that we have an open list, we will also need a closed list. The closed list contains the nodes that have had all of their neighbors added to the open list [5]. Each node in the open and closed lists has a G score. The G score indicates the distance or weight of the path leading to the node from the start node [5]. There is also an H score which is the heuristic that is used. The H score is like the G score except it represents the distance from the current node to the endpoint [5]. The tracing out of the path is not completed ahead of time so you cannot really know this score. As discussed before, a method is used to estimate this distance. Starting out, the closed list is empty and the starting point is in the open list. Each node holds its G score and the node that was used to get to the current node for backtracking [5]. Typically these nodes are referred to as parent and children nodes. The path needs to be extended until the target destination is reached. This occurs by calculating the h score for all of the nodes in the open list and then picking the node in the open list with the lowest sum of the G and H scores [5]. If the open list is empty, then there is no path from the starting point to the end point. Let’s call the point picked T. Every point that is adjacent to T and not in the closed list gets added to the open list [5]. If it is in the open list already then don’t add it again. The G scores of the new nodes in the open list are the G score of T plus the distance between the new node and T [5]. The previous or parent node for the new nodes is T. If a node was already in the open list that is adjacent to T, check if the new G score is less than the current one and if it is, update it as well as the previous pointer, otherwise do nothing [5]. If the new point is the target point, then the optimal path is found. T is moved to the closed list and the process is started over [5]. Finite State Machines A finite state machine is one of the most effective and used methods of programming AI. At the same time, they are one of the least complicated. Each object in a game can have a number of states in its life. For instance, a soldier can be arming himself, patrolling, or attacking. Objects respond in different ways depending what state they are in. The advantage of this method allows us to divide the implementation of each object’s behavior into smaller pieces, which makes debugging and extension easier [2]. A finite state machine is a model composed of states, transitions, and actions. States store information about the past [6]. Transitions indicate a state change. Typically a transition condition needs to be fulfilled to complete the transition [6]. There are four types of actions: entry action, exit action, input action, and transition action. Entry action is an action that occurs when entering a state [6]. Exit action is an action that occurs when exiting a state [6]. Input action is an action that occurs depending on input and present state [6]. Transition action is an action that occurs when performing a transition [6]. A simple diagram that illustrates this is shown below in figure 4. 
Figure 4: Finite State Machine Artificial Neural Networks An artificial neural network is a software representation of the human brain. It works by receiving input, processing the input, and communicating an output. The input is processed in hidden layers as seen in figure 5. Successful artificial neural networks must be trainable, that is, learn to solve problems from examples and use the “acquired knowledge” to solve unseen problems. 
Figure 5: Artificial neural network representation There was a debate of how to get artificial neural networks implemented into computer games. It has been a trendy topic as of late. It has been said that artificial neural networks have huge potential in computer games. Collin McRae Rally 2 was one of the first games to implement an artificial neural network successfully in 2001. The trained neural network in this game is responsible for keeping the computer player’s car on the track while trying to go around the track as fast as possible [2]. The input to the neural network could be the curvature of the road, distance from the corner, the type of road, speed of car, or the car’s properties [2]. From receiving this input, the neural network can generate an output which is optimal for the given conditions. This output is then passed to the physical layer module. The neural network’s application is limited in games due to a few problems such as [2]:
Choosing the network’s input parameters can be a serious problem. The parameters need to be chosen in a way that will let the network learn to solve situations that have not appeared [2]. A general rule of thumb is to have the input data represent as much information about the game world as possible. A set of input data is needed for training the network. Several hundred samples for most games today is normal. This process usually requires a significant amount of effort and time from the developers. The last step is to train the neural network. Simultaneous testing should be occurring with the training process to ensure that the game doesn’t get too difficult or too easy and in need of further training [2]. Fuzzy logic is often used with neural networks. Fuzzy logic allows for more human like reasoning [2]. It is usually in the form: if variable is set then action. For example, if road is dry then maintain normal speed or if road is wet then slow down. When the simultaneous use of fuzzy logic and neural networks is successful, the results are incomparable with what can be achieved by using rules hard-coded into the code with traditional logic [2]. Conclusion Where would the game world be today if it weren’t for artificial intelligence? I can guarantee it wouldn’t be where it is today with out artificial intelligence. It is not possible to create a game with out AI in today’s world. With out AI in a game is like the Earth without the sun. AI in gaming has come a long way since the 1970s. A*, finite state machines, and artificial neural networks provide games with the most human like computer player possible. Tremendous accomplishments keep occurring such as neural networks just recently being implemented into a game for the first time. We are slowly moving towards having artificial neural networks and fuzzy logic being a standard in games like the A* algorithm is now. Luckily for gamers, that day is soon here. References [1] Game Artificial Intelligence. Wikipedia Encyclopedia. September 7, 2006. http://en.wikipedia.org/wiki/Game_artificial_intelligence [2] Grzyb, Janusz. Artificial Intelligence in Games. Software Developer’s Journal. June 2005. [3] Petersson, Anders. Artificial Intelligence in Games. WorldForge Newsletter. August 2001. http://worldforge.org/project/newsletters/August2001/AI/#SECTION00020000000000000000 [4] Popovic, Zoran; Martin, Steven; Hertzmann, Aaron; Grochow, Keith. Style-Based Inverse Kinematics. 2004. http://grail.cs.washington.edu/projects/styleik/styleik.pdf [5] A*. The Game Programming Wiki. September 15, 2006. http://gpwiki.org/index.php/A_star [6] Finite State Machine. Wikipedia Encyclopedia. November 1, 2006. http://en.wikipedia.org/wiki/Finite_state_machine Directory: ~yangq -> csse411 -> csse411-materials csse411-materials -> Monte Carlo Tree Search in Board Game ai csse411-materials -> Multi-Core Software Development with Examples in C++ csse411-materials -> Web Security a Programmer’s Perspective csse411-materials -> Emotional Annotation of Text David Gallagher csse411-materials -> Christopher Pinski Department of Computer Science and Software Engineering csse411-materials -> Computer Science / Software Engineering uw-platteville csse411-materials -> Security of Mobile Devices Lon Kastenson Abstract csse411-materials -> Developing for Android Erik Nykl Abstract csse411-materials -> Spyware, Malware, and Viruses Anthony Bosnak Department of Computer Science & Software Engineering University of Wisconsin – Platteville csse411-materials -> Personal Computing: Past, Present, and Future Michael Wills Download 38.11 Kb. Share with your friends:
|
