Content

• Introduction
• The relevance
• Statement of the problem
• The methods of searching extremes of a function
• Designing an artificial intelligence system
• Summary
• References

Introduction

Artificial intelligence (AI) can be defined as the area of computer science concerned with the automation of intelligent behavior. This definition is most closely matches the considered problem. These principles are reduced to the data structures used to represent knowledge, the algorithms use this knowledge, as well as programming languages and techniques used in their implementation.

Game artificial intelligence - a set of software techniques that are used in computer games to create the illusion of intelligence in the behavior of the characters, computer-controlled. Game AI, in addition to the traditional methods of artificial intelligence algorithms also includes control theory, robotics, computer graphics and computer science in general.

The implementation of AI strongly influences the gameplay, system requirements and budget of the game, and the developers balance between these requirements, trying to make an interesting and undemanding to resources of AI low price. The approach to the game AI is very different from the traditional approach to AI - are widely used all sorts of simplification, deception and emulation. For example: on the one hand, first-person shooters error-free movement and instant aiming inherent bots, does not leave any chance to person, so these abilities artificially reduced. On the other hand - the bots have to do an ambush, acting team, etc., that are used for "crutches" in the form of control points, placed on the level.

Artificial intelligence-driven  characters of computer games divided into:

• non-player characters (NPC) - as a rule, these characters are friendly or neutral to the human player.

• Bots (born Bot) - hostile to the player characters, approaching the opportunities to game character, against the player at any given time are fighting a small number of bots. Bots are the most difficult to program.

• mobs (born Mob) - hostile to the player "low intelligence" characters. Mobs killed by players in large numbers for the sake of experience points, artifacts or training area.

The relevance

A huge body of research in artificial intelligence is the development of the game and entertainment systems of artificial intelligence that would be a worthy contender for the person in a computer game. In addition, that would have the most similar to the behavior of men. To a man, playing computer games, did not distinguish which of his enemies is controlled by the person who manages the system and which of his enemies is controlled by game AI. Now, science has come to such a level of development that the opportunity to create an artificial intelligence at different levels of complexity. However, many problems are still not resolved scientifically. One of these problems is the development of a universal artificial intelligence. Which could be applied in different settings and with different goals. Creating such AI systems would use it in various game genres and hospitality without rewriting the entire system modules or for a particular game.

Statement of the problem

The aim of this work is to design a system of artificial intelligence game that could use as input information about the world to decide on certain actions of the many available. The implementation of which will contribute to the game character maximum benefit. The adoption of the best solutions is actually finding the extremum of function of several variables, in which the arguments are available for game action the agent. Therefore, it is necessary to analyze the existing methods to search for extremes of a function of several variables.

The methods of searching extremes of a function

The simplex method

The procedure of the simplex method is based on the regular simplex. Regular simplex in N-dimensional space is a polyhedron formed by N +1 equal-spaced points. The problem with two variables simplex is an equilateral triangle, with three - tetrahedron.

The algorithm simplex search begins with the construction of the regular simplex in the space of the independent variables and evaluate the objective function at each of the vertices. In this case, discarded top, which corresponds to the largest value of the objective function.

Advantages of the method:

• Comparative simplicity of the logical structure of the method and, accordingly, the computer program;

• Using a relatively small number of pre-defined parameters;

• Algorithm is effective even in cases when the error calculating the values of the objective function is great, because in its implementation using the highest values of the function at the vertices, and no less.

Disadvantages of the method:

• There is a scaling problem, since all the coordinates of the vertices depend on a single scale factor. To avoid such problems in practical problems, all variables should be scaled so that their values were comparable in magnitude;

• Algorithm works very slowly, because obtained in previous iterations of information is not used to speed up the search;

• There is no easier way to expand the simplex. Require recalculation of the value of the objective function at all points of the sample.

Powell's method of conjugate directions

The method belongs to the category of theoretical methods of optimization. The method is aimed at solving problems with quadratic objective functions. The basic idea of the algorithm is that if a quadratic function of N variables refer to the sum of the squares, then its optimum may be found as a result of the N-dimensional search for the transformed coordinate (conjugate) directions. Conjugate directions are determined algorithmically. For our two-dimensional case, the implementation of the method requires three-dimensional search. To find the extremum of a quadratic function of N variables must perform N² one-dimensional searches.

The algorithm of the method:

Step 1. Set the initial point x₁, x₂, and the direction d. In particular, the d direction may coincide with the direction of the coordinate axis;

Step 2. Produce a one-dimensional search of the point x₁ in the direction of d and get a point y₁, which is the extreme point on a given direction;

Step 3. Search of the point x₂ in the direction of d and get a point y₂;

Step 4. Calculate the direction (y₂ - y₁);

Step 5. To a one-dimensional search of the point y₁ (or y₂) in the direction (y₂ - y₁) with access to x*.

Designing an artificial intelligence system

Game AI can represent a realization of how the behavior of one opponent, and many opponents and allies human player. Each such entity that is responsible for decision-making will be called the agent. To implement the gaming AI requires at least one agent. Agents are able to perform a limited set of actions D, each of which leads to a change in the state of the agent or the game world.

Before each agent faces a number of challenges T. In this paper, it is considered that the optimal solution to each of these problems is the goal of existence of an agent in the gaming world. Each of these tasks can be associated with priority:

The higher the priority, the more important task, and the greater the likelihood that the actions necessary to achieve it, will be implemented in the first place.

For simplicity, assume that one unit of time an agent can only perform one action. For each task, this action has a certain measure of effectiveness:

Calculation of this parameter can be implemented in various ways depending on the type of action and the characteristics of the domain to which the game is developed.

Thus, each time unit can assess the effectiveness of the action of each of d, available agent:

For maximum efficiency, the agent must be in each unit of time to perform the most effective action:

Therefore, to select the most useful for the agent of action is to find the extremum of a multidimensional function whose arguments are the available actions. To solve this problem the most suitable method is the simplex method. Since it does not require finding the derivative of a function, which in our case is an important advantage over the gradient method and the simplex method allows for a small number of iterations to find the extreme value with a specified accuracy.

The developed system is a multi-agent. In this case, each agent has its own AI system that is independent from the others and makes decisions based on the information received about the world around him.

All data that passes the agent in the system are represented as a vector of integers. The basis of assessment of the agent and its position relative to other objects of the game world is searching for extremes of a function whose arguments are the input vector data. Each task agent is a separate function. Tasks can have priority.

The system architecture may remain unchanged and thus can be used in various games. For correct operation of artificial intelligence need only provide external data received from the agent, in the form of the input vector, and the system will search for the extreme in this set of function arguments.

The system simulates any of the available agents act by asking him about efficiency. Only when the best state in the context of an agent facing artificial intelligence tasks decides whether to make exactly this effect. The selected action is transferred to the agent execution.

After designing the system has been tested on a simple game. The essence of the game is that on the randomly placed agents with artificial intelligence and resources that will be collected by them. One of the agents, controlled by the player. The goal - to collect as many "food", but it must be wary of opponents who can attack the game agent. Screenshot of the gameplay is presented in the figure below.

The behavior of agents playing was quite predictable. They are usually collected "food", and in its absence - attacked each other.

Summary

In this paper we analyzed the methods of extremum function of several variables, as well as gaming system is designed artificial intelligence, which used as input information about the world, decides to commit certain actions of the many available.

In the course of the work have been built data flow diagram and class diagram. The system architecture is designed so that the AI can be applied to various game genres. This flexibility is provided by independent, so-called "brain" of the system, which accepts a generic set of data, analyzes it and produces the result.

The main attention was paid to the design of precisely defining the structure of the transmitted data as well as the right, at the same time independent, the process of data processing and decision-making. This approach breaks the most rigid connection between the gaming genre and artificial intelligence.

References

1.       Портал искусственного интеллекта [Электронный ресурс]. – Режим доступа : http://www.aiportal.ru/

2.       Gamma E., Helm R., Johnson R., Vlissides J. Design Patterns / R. Helm, R. Johnson, J. Vlissides : Addison Wesley, 1994. – 416 с.

3.       Искусственный разум – принципиальная схема [Электронный ресурс]. – Режим доступа : http://habrahabr.ru/post/166333/

4.       Rabin S. AI Game Programming Wisdom / Rabin Steve : 2001. – 314c.

5.       Ножов И.М. Практическое применение искусственного интеллекта в компьютерных играх / Ножов И.М. – М. : РГГУ, 2008. – 140 с.

6.       Методы поиска экстремума функции [Электронный ресурс]. – Режим доступа : http://www.scriru.com/14/31294432384.php

7.         Метод Нелдера-Мида [Электронный ресурс]. – Режим доступа : http://ru.wikipedia.org/wiki/Метод_Нелдера_—_Мида