Українська   Русский
DonNTU   Masters' portal

Abstract

Contents

Introduction

The gaming industry has been experiencing rapid growth in recent decades. Products created by major game companies show that the creation of games can act as some art. Computer games allow you to compete between players or players and a computer. The computer is a game of artificial intelligence (AI). The main role it performs a simulation of human behavior.

Nevertheless, the main limitation on AI for games is the speed and the required resources in the process. Therefore, in the game AI the main principle is the behavior is simulated. In other words, AI for games is more artificial than intelligence. The AI system can be extremely simple and can be a set of rules, or it can be quite complex and serve as the commander of the enemy's army, with which the player has to fight [2].

This master's dissertation explores one of the principles of creating a game AI for collectible card games. Collectible card games are one of the genres of computer games, in which the goal is to accumulate game cards for the subsequent play of them with an opponent. In such games, strategic elements with elements of randomness are combined, and much depends on the cards that are encountered by the player, as well as on how it can use them [1]. The approach to creating AI is selected using a genetic algorithm.

Genetic algorithms (GA) are adaptive search methods, which have recently been used to solve optimization problems. They are used as an analog of the mechanism of genetic inheritance, and an analogue of natural selection. In this case, biological terminology in a simplified form and the basic concepts of linear algebra are preserved. Recently proposed in 1975 by John Holland [4], genetic algorithms are based on the principles of C. Darwin's natural selection. GA refer to stochastic methods. These algorithms are successfully applied in various fields of activity (economics, physics, technical sciences, etc.) [3].

2. Goals and objectives of the study

The purpose of this master's dissertation is the use of a genetic algorithm to create a game of artificial intelligence. modification of the genetic algorithm and the determination of the effectiveness of the use of GA for this task on the platform of the game of the genre of CCG. From the tasks it is possible to note:

  1. A study of GA and the choice of operators with their subsequent modifications.
  2. Development of game AI for the Dual choice platform based on GA.
  3. Development effectiveness function for functional genes (cards and abilities).
  4. Comparison of the speed and efficiency of decision making AI on the basis of GA and full enumeration.
  5. Create a possibility to select the complexity of AI using dynamic GA settings.

4. Own results

Initially for bachelor's work the game of genre CKI Dual choice was developed. Appearance of the prototype and effects can be seen in pic. 2.

Screenshot of the gaming application

Picture 2 – Prototype of the collectible card game Dual choice

While the game application is designed for two players with the transfer of the step. At the moment, it is required to investigate and create a game AI so that it can replace an opponent.

To begin with, it was required to find an approach to the creation of AI, to investigate the appropriateness of its use with subsequent implementation. For this purpose, the program is designed with a very simplified version of GA subsequent implementation.

A genotype of only 2 genes with possible 30 variants was used. Each gene acts in the form of an AI action (card selection). The position of the gene in the genotype also changes its meaning of the efficiency function. With a full search, there will be 30 * 30 = 900 options and as many possible calculations functions of the genes. Each calculation of the function takes some time, and if there are too many of them, this is a long time, which is unacceptable for game AI.

Сhoose simple operators in the test program:

  1. Mutation is a 30% chance to change a random gene in a genotype to a random different one
  2. Crossing (crossover) in the form of a single-point crossover.
  3. Selection in the form of a choice of better adapted genotypes.

We randomly define the final fitness function for the combination in the interval (0.2) and also set the random time for which it will be counted for the first time. Used pseudo caching functions.

In contrast to the given algorithm there will be a complete search of all 900 combinations, at which the result will be the best, but the calculation time is much longer. The results are tab. 1.

Population Qty. steps Improved performance (%) Impairment in efficiency (%)
20107142,5
20106524.1
14147702
14148225
10209599
10208916
Average: 801Average: 4,77

According to the preliminary experiment, further research will be carried out over the GA so that the final result is approximately the same. With a performance degradation of less than 5%, an increase in the speed of the system is 8 times. This condition will be met when caching functions.

One of the tasks is to adjust the complexity of AI. This method can create a simulation of the AI difficulty by setting the number of iterations of steps, selecting the population and possibly redefine the GA operators.

5. Investigation of the introduction of modification of the genetic algorithm in AI

The work of the modified GA can be simplified in the animation below. Forming randomly individuals and doing some number of iterations. K and D are in the form of some AI actions. K – playing a certain card with the i or j index, and D – using the active ability of the card. The number D can vary from the number of cards on the table with active abilities.

Picture 3 – simplified operation of GA for this task
(Animation: 700 frames, an infinite repetition cycle with the ability to stop and continue, 32 kilobytes)

The key point in the modification of GA is the efficiency functions. Adaptation of the genetic algorithm required the compilation of performance functions for each card. Each gene acts as a function. This means that genes also take some parameters that depend on the particular card to which it is attached. This circumstance will affect the balance of the game cards and the overall picture of the AI presentation.

To begin the compilation of functions, some support point is required. It will serve as the initial criterion for the formulation of the formula. For this we turn to the terminology of the CCG and find a definition to this concept as Vanilla test. This term characterizes and evaluates the card in the CCG games relying only on the quantitative indicators of the attack, health and the price of the card.

Formula 1

where A – the card attack; H – card health; C – the cost of the card.

In the base case Vanilla test It is represented as an addition of attack and health and the result is divided by price.

Vanilla test should be applied to creature cards and spell card in different ways. The effectiveness for spells that deal damage or heal can be defined as:

Formula 2

where R – the quantitative influence of the map; A – the coefficient of significance; C – the cost of the card.

There is a problem in further evaluation of maps. As a rule, the cards have active and passive skills. To establish a balance in the game, you need to indicate the effectiveness of the card as the sum of all its parameters, namely:

Formula 3

where AA – the function of calculating the usefulness of the active ability; PA – the function of calculating the utility of the passive ability.

Further research will be carried out in the master's work and this review shows only the basic support on which AI games will be guided Dual choice

Conclusions

To implement the AI was chosen GA, so that the player had the opportunity to choose from a wide range of the complexity of the game. When implementing some other algorithms of AI behavior, it is necessary to artificially degrade the result obtained in the calculation of combinations of moves or to create multiple branching algorithms for each of the proposed difficulties. This algorithm allows you not to resort to such methods, but because of this it is necessary to represent the efficiency functions for each of the cards in the database. When performing a search for a solution, not all moves are analyzed, but only those that were accidentally suggested and generated later. The difficulty is to allow you to adjust the GA stop criterion and the number of combinations in each step.

Another important reason for using GA is a significant reduction in the use of resources and the timing of the calculation of the course of AI. Studies and obtaining preliminary results made it clear in the expediency of its use.

List of sources

  1. Описание и игры в жанре Карточная стратегия (ККИ) // Apptime Games and Gadget – Режим доступа : https://app-time.ru/spravochnik-igrovyih-mobilnyih-zhanrov... .
  2. Создание искусственного интеллекта для игр // Intel Software – Режим доступа : https://software.intel.com/ru-ru/articles/designing... .
  3. Панченко, Т. В. Генетические алгоритмы: учебно-методическое пособие / под ред. Ю. Ю. Тарасевича. – Астрахань : Издательский дом Астраханский университет, 2007. – 87 с.
  4. Holland J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence. – Cambridge : The MIT Press, 1992. – 194 p.
  5. Библиотека для реализации генетических алгоритмов в .NET Framework 2.0 // jenyay.net – Режим доступа : http://jenyay.net/Programming/Genetic .
  6. Bogdanovic M. On Some Basic Concepts of Genetic Algorithms as a Meta-Heuristic Method for Solving of Optimization Problems // Journal of Software Engineering and Applications, 2011. – 4. – P. 482-486.
  7. Шампандар Алекс Дж. Искусственный интеллект в компьютерных играх: как обучить виртуальные персонажи реагировать на внешние воздействия / пер. с англ. – М. : Издательский дом Вильямс, 2007. – 768 с.
  8. Уилкинсон Б. Основы проектирования цифровых схем. – М. : Издательский дом Вильямс, 2004. – 320 с.
  9. Трубаров А.А. Организация обучения нейронной сети с помощью генетического алгоритма оптимизации // Портал Магистров ДонНТУ, 2009. – Режим доступа : http://masters.donntu.ru/2009/fvti/trubarov/... .
  10. Буга К.В. Изучение методов построения игрового искусственного интеллекта и разработка информационной технологии для ее реализации в пошаговых стратегиях // Портал Магистров ДонНТУ, 2013г. – Режим доступа : http://masters.donntu.ru/2013/fknt/buga/... .
  11. Боровик В.В. Параллельный генетический алгоритм для решения задачи коммивояжера // Портал Магистров ДонНТУ, 2013. – Режим доступа : http://masters.donntu.ru/2013/fknt/borovyk/... .