Content:

1. Preface
2. Actuality
3. Research results
4. Pathfinders
5. Results of using architecture under study in the simplest game simulator
6. Summary
7. References

Preface

Artificial intelligence is the name for science discipline and technology of intellectual machines creation, particularly intellectual software. It can be described as the branch that is engaged in Intellectual Behavior modeling. This description has one serious flaw: it's hard to understand what the intelligence exactly is. AI can be narrowed down to intelligence in general: whether it is something solid or contains from different odd characteristics. AI at the moment is the subject and testing model for Intelligence Theories: they can be formulated in computer languages and afterwards tested. There are a lot of algorithms and approaches to GAI creation. AI could be created using the basis of Boolean algebra and predicate calculus extended by object symbols introduction, relationships between them, universal and existential quantifier. Another common handling is structural, that is supposed to model structure of human's brain, one of the first attempt to achieve this was made by F.Rosenblatt (perceprton). The central point in such a modeling usually is model of neuron. Rather wide usage has also evolutional approach. Here the significant part of system is to build up initial state and identify rules for farther evolution. For initial model's state can be used any approach. In what follows only models with the best characteristics will be selected to generate new one by some rules and so on.

Actuality

Last decade, thankfully to game industry development, necessity of virtual foes that can effectively imitate intelligence solving tasks, occurs more and more often. Even though spirit of Rivalry's maintenance demands developers to resort to various tricks, GAI operates the same methodology as the eponymous science discipline. More attention is payed to feasibility of games. And it concerns not only graphics and voicework but also behavior of characters. This is achieved mainly with GAI tools, so that's why new algorithms discovery, optimization and improvement of existing ones is so important.

Research results

The most part of research was pointed to creation of architecture that is maximum abstracted from specific task. This was achieved by distinguishing decision-making mechanism from data gathering one. At every step agent as minimal structural instance of Game World has some restricted set of possible actions. System asks agent regarding effectively of each particular action in context of task to be solved by AI and makes decision that is passed to agent thereafter. So the main point is to execute the most effective step in every time-point. Adaptation to actual user wasn't taken into attention due to low-priority of this task in comparison with other parts of current research. By far more important is structure of universal data input containing full description of Game World current state. Efficiency determination task can be solved in few ways, which can vary depending on activity type and subject area. At the moment our researches moved to methodic of searching for multidimensual function extremums (here gradient descent is used). One of the most important system parts is module that finds minimal distance to the target. When we examine effectively of action we should estimate path and time for execution, that's why mentioned module is so important.

Pathfinders

There are a lot of method for distance finding between the graph vertices. One of the most popular – A* algorithm. In computer science, A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. Noted for its performance and accuracy, it enjoys widespread use. A* uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way. The example of A* algorithm process illustrated at picture 1.

Picture 1 – The pathfinder examlpe with А* algorithm using (animation: size – 58.2 KB, frames count – 25, resolution – 280 х 285)

In the 2011 was created the modification of A* algorithm – Jump Point Search. JPS - an online symmetry breaking algorithm which speeds up pathfinding on uniform-cost grid maps by “jumping over” many locations that would otherwise need to be explicitly considered. JPS is faster and more powerful than RSR: it can consistently speed up A* search by over an order of magnitude and more. Unlike other similar algorithms JPS requires no preprocessing and has no memory overheads. Further, it is easily combined with most existing speedup techniques — including abstraction and memory heuristics. JPS can be described in terms of two simple pruning rules which are applied recursively during search: one rule is specific to straight steps, the other for diagonal steps. The key intuition in both cases is to prune the set of immediate neighbours around a node by trying to prove that an optimal path (symmetric or otherwise) exists from the parent of the current node to each neighbour and that path does not involve visiting the current node.

Picture 2 – Jump Point Search main idea.

Jump points

Node x is currently being expanded. The arrow indicates the direction of travel from its parent, either straight or diagonal. In both cases we can immediately prune all grey neighbours as these can be reached optimally from the parent of x without ever going through node x.

Picture 3 - Neighbour Pruning

Node x is currently being expanded. The arrow indicates the direction of travel from its parent, either straight or diagonal. Notice that when x is adjacent to an obstacle the highlighted neighbours cannot be pruned; any alternative optimal path, from the parent of x to each of these nodes, is blocked.

Рисунок 4 – Forced Neighbours

We apply these pruning rules during search as follows: instead of generating each natural and forced neighbour we instead recursively prune the set of neighbours around each such node. Intuitively, the objective is to eliminate symmetries by recursively “jumping over” all nodes which can be reached optimally by a path that does not visit the current node. We stop the recursion when we hit an obstacle or when we find a so-called jump point successor. Jump points are interesting because they have neighbours that cannot be reached by an alternative symmetric path: the optimal path must go through the current node. The details of the recursive pruning algorithm are reasonably straightforward: to ensure optimality we need only assign an ordering to how we process natural neighbours (straight steps before diagonal). I will not attempt to outline it further here; the full details are in the paper and my aim is only to provide a flavour for the work. Figures 3 gives two examples of the pruning algorithm in action. In the first case we identify a jump point by recursing straight; in the second case we identify a jump point by recursing diagonally.

Picture 5 - Jumping Examples

Node x is currently being expanded. p(x) is its parent. (a) We recursively apply the straight pruning rule and identify y as a jump point successor of x. This node is interesting because it has a neighbour z that cannot be reached optimally except by a path that visits x then y. The intermediate nodes are never explicitly generated or even evaluated. (b) We recursively apply the diagonal pruning rule and identify y as a jump point successor of x. Notice that before each diagonal step we first recurse straight (dashed lines). Only if both straight recursions fail to identify a jump point do we step diagonally again. Node w, which is simply a forced neighbour of x, is generated as normal.

Results of using architecture under study in the simplest game simulator

For research of introduced architecture's possibilities simple game simulator was developed with game field containing Agents and Food. Goal of each agent is to gather as many as possible Food. Visibility area for agent is restricted. Besides that, there are also barriers on the field. Game is finished when all food is gathered. Player can manage one from the Agents. At the beginning of the game all game elements are placed in random order. Agent, when gets right to move, updates visible area and makes calculations of effectively of possible farther way using some predefined function (Jump Point Search).

Picture 6 - Game proccess

Summary

As a result of this study were described architecture and main modules of GAI. System architecture was developed in such a manner to be applicable in different game genres. This universality was achieved by abstracting central AI module from characteristics of data input and delegation data manipulating functions to Agent. This level of abstraction was one of the main points in current study.

References

• Bandi, S., Cavazza, M., and Palmer, I. “Situated AI in Video Games”. / S. Bandi : University of Branford
• Shortest path [Electronic resource]. – Access : http://harablog.wordpress.com/2011/09/07/jump-point-search//
• Портал искусственного интеллекта [Electronic resource]. – Access : http://www.aiportal.ru/
• Gamma E., Helm R., Johnson R., Vlissides J. Design Patterns / R. Helm, R. Johnson, J. Vlissides : Addison Wesley, 1994. – 416 с.
• Искусственный разум – принципиальная схема [Electronic resource]. – Access : http://habrahabr.ru/post/166333/
• Ножов И.М. Практическое применение искусственного интеллекта в компьютерных играх / Ножов И.М. – М. : РГГУ, 2008. – 140 с.
• Основы подхода к построению универсального интеллекта [Electronic resource]. – Access : http://habrahabr.ru/post/145467//
• Rabin S. AI Game Programming Wisdom / Rabin Steve : 2001. – 314c.
• Скатов Д.С. Искусственный интеллект/ Д.С. Скатов, В.В. Окатьев, Т.Е. Ратанова – Киев : Диктум, 2011. – 46 с.