Research Project Paper Report

Research Project Paper Report

Battle Simulator 2002

An exploration of artificial intelligence and agent systems

Kinoshita Research Lab

David Chen

2002

Table of Contents

Research abstract.……………………………………………………………….. 3

Introduction……………………………………………………………………… 5

Overview of the program………………………………………………………… 6

Troop AI…………………………………………………………………………. 7

Taisho AI………………………………………………………………………… 9

Battlefield Agent…………………………………………………………………. 10

GUI Agent……………………………………………………………………….. 11

Problems and Future Developments……………………………………………… 12

Conclusion………………………………………………………………………... 13

Research abstract

Background:

A lot of recent researches in the field of AI have been made toward developing agent technologies. Agents are basically autonomous objects or programs that can learn from experience and react to environment changes. From network security to customer service, agent technologies are used in various situations.

Goal:

The goal of this project is to design a battle simulator that simulates a battle between multiple armies during the zenkoku jidai (period of war) in Japan. The focus is on designing intelligent agents to represent the troops and taishos. The taishos will issue commands to their troops after evaluating all the information available to them such as troop positions and troop types. The troops will try to follow the orders as well as they can, taking into consideration their ability to move, their attack range, etc.

Basic layout of the project:

The entire project will be developed in TAF[1] and Java. As shown in the diagram on the next page, the Battlefield agent will be in charge of central communications between all the agents. It also keeps track of all the state variables of the simulation as well as the positions of all the troops. The taisho agents request information from the Battlefield and issue commands to their troops through the Battlefield. The troop agents request information from the Battlefield about their surroundings and then try to follow the orders they received to the best of their abilities. The battlefield is modeled to be 2D where each troop occupies one cell of the grid. The output of the simulation is done through the GUI agent. The GUI agent receives information about the current state from Battlefield and then proceeds to use an external Java swing program to display the state of the battle.

Introduction:

Advancement in computer technology has made many traditional tasks much simpler. From word processing to large-scale management, computers are used everywhere to help perform monotonous work.

However, as hardware speed has been doubling every 1.5 years, computers now have the ability to perform even more complicated tasks. Consequently, numerous researches are focused on what is called “artificial intelligence.” Computer programs are no longer confined to do only the things the programmer has specifically programmed for. They now possess the ability to learn from experience and to negotiate with one another to resolve a problem.

More specifically, computer program that are called “agents” are becoming more and more popular now. These programs are literally like an agent for their owner. They possess unique properties, certain strategies to deal with issues, and their past experiences. Agents can be used in many areas such as planning a trip, managing network traffic, or teaching someone how to program a vcr. The most important property of agents is that they have memory and are constantly updating themselves to keep up with the current situation. Compared to traditional computer programs that need to be constantly restructured and updated manually, a properly designed agent can have a much longer life span with minimal maintenance

In this project, agent system, or a system consisting of many agents, is used to simulate battles between two or more groups of samurai armies. Agent system is a very convenient tool in performing simulations. The programmer only need to specify the rules for how each object in the simulation acts without knowing how the simulation works overall. This simplifies the problem tremendously since the programmer only needs to be concerned with one object at a time without worrying about how everything else in the system works. However, this is of course only possible with well-defined protocols and common language with which all the objects in the system communicate through. This project represents each group of troop and each taisho with an agent. Thus, it is only necessary to specify how each troop and each taisho should react to changes in their environments without knowing how each simulation will turn out. The use of an agent system also keeps the program object oriented and easy to modify and debug.

Overview of the program:

Before we can start discussing the implementation of each part of the simulation program, it is important to understand the general idea of the simulation and the simplifications that were made in order to reduce the complexity of the simulation. The ideal goal of the program is to simulate realistic battles between multiple samurai armies. However, as it is impossible to implement all the features in a real battle, we need to first reduce the problem into tangible terms.

First of all, troops move in grids instead of free terrains. This reduces the complexity of movement tremendously as there are much less choice of where the troops can move to.

Second of all, the simulation will be turn based instead of real time. What this means is that troops will take turn in moving as opposed to real life where everyone can move simultaneous at the same. The choice of turn-based simulation avoids the problem of deadlock where multiple parts of the program all want to use the same resources. For example, if two troops both want to move to the same grid, it is hard to decide who gets the space in a real time simulation.

Of course there are many other simplifications in the simulation as the program is only as realistic as the programmer makes it. However, as there are infinitely many things to consider in a perfect simulation, it is reasonable to model only the important attributes first.

As mentioned before, the simulation is realized through an agent system. An agent represents each troop and each taisho. Each of these agents keeps a set of rules on how to react to situations. The troop agents are responsible for knowing how to move around and attack enemy troops. The taisho agents are responsible for issuing commands to their troops and telling the troops where to go and who to attack. There is a central agent called the battlefield agent that is in charge of overlooking the entire simulation. The battlefield agent is responsible for managing any communications between the other agents, resolving all the battles, and keeping the states of the simulation. There is also a GUI agent that is responsible for displaying the current state of the simulation by utilizing an external java GUI program.

The following sections discuss the implementations for each part of the agent system in more details.

Troop AI:

Movement

Being able to move around the battlefield is one of the basic functions for troops. The goal is to have each troop move around freely and always take the optimal position according to the objective they have at the time. Since each troop only knows information about itself, it needs to query the battlefield agent to find out which spots it can move to. The problem basically reduces to a typical path finding problem where each agent try to find the shortest path possible to their destination and move as close to their target area as possible.

The first implementation had a very simple algorithm. The troop repeatedly checks the four spots immediately adjacent to itself and moves to the square that gets it closer to their desired destination. This is not a very good algorithm of course as the troop gets stuck very often. For example, if a troop wants toward the right side, and there is an obstacle immediately to its right, it will stay where it is since none of the three spots it can move to will get it closer to the right. The troop does not consider about the possibility of moving around obstacles.

The current implementation fixes the problem by having each troop look at all the spaces it can move to in the current turn and move to the spaces closest to its destination. This improves the situation a lot since the troop considers all the spaces it can move to instead of just the spaces immediately adjacent to itself. Of course, this improved algorithm is useless if the troop can only move one space every turn. Thus, in our design, we make sure that each troop can always move multiple spaces in a turn.

The current situation is still not ideal though. A perfect AI for movement would actually consider several moves ahead and think beyond the current turn. Of course, there is always a problem of making the AI too smart to be realistic. In this case, it is unrealistic if each troop can see the entire battlefield at all time. Thus, a better design would probably be to implement a sight range for each troop and have each troop consider only all the spaces it can “see.”

The reason for not implementing the features mentioned above is actually partly due to performance issues. The current platform, namely TAF, is not efficient enough to perform large path finding computations. Thus, if each agent is made to consider even more spaces than it does now, the simulation will be very slow and run out of memory very fast.

Attacking

Another basic function for the troops is the ability to attack. The basic goal of attacking is very simple. When a troop receives an attack command from its taisho, it moves as close to its target as possible until the target is within its attack range, and then it proceeds to assault the target troop. However, several extra features are implemented in this project to make the troop a little bit smarter in deciding its action.

First of all, all the troops take advantage of their attack ranges. Instead of always moving closer to their targeted enemies, the troops move to the optimal spot to attack. The optimal spot is basically the space that is the farthest away from the enemy but within the troop’s attack range. Thus, a troop will sometimes actually move away from its enemy to take advantage of its attack range.

Another extra feature implemented is that the troops will try not to waste its turn. For example, if their targeted enemy is out of their attack range in the current turn, they will of course first move as close to the target as possible since they ultimately want to assault the targeted troop. However, after they have done moving, they will automatically search all the spaces within its attack range to see if there is another enemy troop within its attack range. Thus, the troops do not waste their turns sitting there idly if there is an enemy troop right next to them. Of course, this feature is not always good as it may sometimes be smarter to avoid battles to reduce loss. However, in most cases it is advantageous to take the offensive so it makes sense to have this feature.

The last extra feature implemented is for realistic effect. Morale is quite important in real battles. In real life, if a troop is surrounded by multiple enemy troops, it will most likely run away instead of fighting the enemies. However, the actual rule implemented in this project is quite simplified. Each troop basically compares the strength of their attack target to theirs and decides whether to fight or run. The troops do not consider whether they are surrounded or not, or if there are friendly troops around them. A possible improved system would have each troop keep track of its own morale that changes according to the situation of the entire battle, the position the troop is in, and the strength of the taisho.

Most of the decisions for attacking are left for the taishos. Just like in real battles, the individual troops do not have a lot of choice in deciding where to go or who to attack. They simply follow their taishos’ commands.

Taisho AI:

The taishos have the most complicated job in this simulation. Unlike the troops, which have simple clear goals, it is often not clear what the best decisions for the taishos are. Taisho AI is very important since it could change the outcome of the battle completely depending on how smart the AI is. This is similar to reality since real battles often depend on the ability of the commanding taisho instead of just troop strength and number.

The basic job for the taishos is to command the individual troops on where to move to and who to attack. In the simplest case, the taisho tells the troop to attack the closest enemy to that troop. However, this is not always the smartest thing to do. Depending on troop type and strength, sometimes it is more effective to attack enemy troops that are further away. For example, yari samurai are especially effective against cavalries. Thus, the taisho will actually tell the yari samurais to attack the cavalries even if the group of cavalries is not the closest enemy troop present. Similarly, the taisho will generally pick ranged enemies to be the target first since ranged troops usually have less armor and are weaker.

Another issue that the taishos have to consider is the order of issuing commands. Since the simulation is turn based and the troops cannot move simultaneously, it is important in which order the taishos issue their commands. The current system only has the basic rule of always issuing commands to the troop closest to the enemies first. The major problem in implementing this feature was to avoid the problem of deadlock. Deadlock occurs when enemy troops appear in multiple directions and two troops are in each other’s ways to their designated targets. The taisho cannot decide who to move first since they are both closer to the enemy depending on which perspective you look at it. The problem is solved by arbitrarily letting one troop move first when a deadlock occurs.