The Opponent’s Movement Mechanism in Simple Games Using Heuristic Method Alicja Winnicka Institute of Mathematics Silesian University of Technology Kaszubska 23, 44-100 Gliwice, Poland Email: winnicka.alicja@10g.pl Abstract—All kinds of games force continuous development of only expanded but virtual reality is developed using these not only hardware technologies, but also solutions that increase algorithms [1], [2]. playability. One of such aspects is the way the world interacts Heuristic algorithms find an increasing application in game with the user. The effect of this is the technique of opponents action, which enforces a certain degree of difficulty on the player theory due to their advantages. Not the predictability achieved and is constantly driven and motivates to pass the game faster and by random movements, as well as low computing power. In more efficiently. In this work, I present the strategy of reaching [9], game balancing was achieved by the use of one of these a certain point on the board by the computer through the use of algorithms. Moreover, it is interesting to create hybrids of a modified heuristic algorithm, ie a Cuckoo Search Algorithm. various classic techniques in games such as decision trees with The proposed solution has been described, tested and discussed due to the advantages and disadvantages of this solution. fuzzy logic [8] or heuristics [14]. Of course, for large param- eter values, each algorithm will need more power. For this I. I NTRODUCTION reason, parallelization and use of the full available processor power can be used what has been shown in [12]. The computer market develops through a lot of competition, II. H EURISTIC ALGORITHM as can be seen from the AMD and NVIDIA companies that Cuckoo Search Algorithm’s (CSA) [21] name derives from produce graphics cards. Releasing a product of one of these the model of cuckoo’s behavior. During the breeding period companies, forces a lot of pressure on the other one. It results cuckoos do not hatch their eggs by themselves, but search for in the release of another card within a few months. Graphics another nests belonging to others birds and leave their eggs in cards are one of the basic requirements of computer games there. They look for nests where the probability of being and so the pressure to produce more efficient and cheaper cards hatching their offspring is greatest. is also on the side of game producers. Developers put more The natural behavior of these birds resulted in the creation requirements for hardware due to improvement realism and of a model originally used as a minimization of continuous computer graphics used in their products. An additional burden functions. Algorithm assumes that cuckoo is interpreted as a for computers are engines, which are based on the methods of point (x, y) on the solution space. In these case it is a board artificial intelligence. The goal is to increase playability and of size w × h. Additionally, some assumptions must be done quality of products to adapt the algorithm to a new operating environment Creating games is about applying and modifying advanced • potential nests are random points on the board, solutions to achieve the greatest effectiveness. Effectiveness is • each cuckoo has only one egg to lay, understood as the time of action, computing power, the quality • total number of cuckoos is constant in each iteration. of the effects obtained and the impact on playability. One • best nests means the points located closest to the goal, of the basic elements due to the programmers is designing • hosts may detect thrown eggs egg with probability p ∈ the world, or maps on which the user can move. In [6], h0, 1i. In this case the egg is thrown out of the nest and the authors presented procedural approach to generating game new cuckoo is placed randomly on the board. maps. Again in [3], the idea of prediction player’s move is At the beginning of the models, some parameters of CSA analyzed by the use of neural networks. This solution can must be defined as number of cuckoos and number of itera- improve, especially, the playability of games by blocking the tions (which can be interpreted as number of cuckoo’s moves). execution of reflex movements. An interesting aspect is the The initial population of birds are chosen at random on the analysis of information for a given game and use for a similar whole solution space. In each iteration, the best nest is chosen purpose as before [16]. In [15] presented the famous algorithm after some steps. The first one is the movement of each birds that beat the World Champion in GO. Artificial intelligence according to techniques have found application in protecting the lives of x = x ± L(x, d, c), (1) players while using phones in augmented reality [11]. Not where addition or subtraction is selected at random with the Copyright held by the author(s). equal probability 50% and L(·) is modified Levy distribution 12 burdened with the ceiling function so the obtained values are III. G AME STRATEGY BASED ON HEURISTIC ALGORITHM integers. This action is enforced by the solution space, which A. Initial settings is indexes of the height and width of the board. This function Let us assume that a computer walks around a certain board can be formulated as &r ' of size w × h. His task is to catch all opponents in as few η e−2η(x−ζ) moves as possible, so in the shortest possible time. Enemies L(x, ζ, η) = p (2) are scattered on the board in a random way. In the case when 2π (x − ζ)3 two players play the game, its task is to collect at least half where the variables ζ, η ∈ R are randomly generated and x is of all points (for one enemies is one point) to win the game. a spatial coordinate of the mother-cuckoo. Of course, each player is placed in the opposite corner of the The second step of the algorithms is the host decision. After, board. The player can make one move in one step, alternately. the cuckoo toss the egg, the host need to decide whether egg will stay or not in the nest. Of course, there is a chance that host will not notice tossed egg. Both situation are modeled by one condition as ( p drop the egg . (3) 1−p leave the egg The algorithm returns the best cuckoo in the last iteration. To make this possible, the cuckoos must be compared. This is possible by introducing the fitness function that will clearly define which one is the best. It is made by the following formula √ g(x) = d(x, t) ± w + h, (4) where t is the nearest goal in the neighborhood. The sign of action depends on whether the cuckoo’s position is the goal of the game. If so, the value is subtracted, otherwise added. This Figure 1: Created board game with enemies "#" and two action forces you to move towards the goal you have found. players marked as "&" and "@". The used function d(·) is Euclidean metric defined as v u 2 In the game, several signs have been used. "@" as a player, uX d(x, t) = t (xi − ti )2 , (5) "%" as a computer, and "#" as an enemy. The visualisation of i=0 these game is presented in Fig. 1. B. Game strategy where x and t are points in two dimensional space. The pseudo-code of these version is shown in Alg. 1 Each player can take only one step in each round. The step can be made in one of four directions (north/south/west/east) Algorithm 1 Modified Cuckoo Search Algorithm but only when it is possible. The move will be impossible to do if the player wants to move outside the board. 1: Start, The proposed strategy consists of two stages. The first step 2: Define all required coefficient, number of cuckoos n, fit- is to check the nearest neighbors. As a neighborhood, we ness function g(·), number of iterations and static position understood a matrix (which the maximum size is 3×3), where of enemies, the player is in its center. If the target is achievable after taking 3: Create initial population of n cuckoos at random, one movement, it is performed without the slightest hesitation. 4: t:=0, If the cost of obtaining a goal is a maximum of 3 moves, 5: while t ≤ T do movement towards it is carried out. The cost is calculated by 6: Drop the egg according to Eq. (1), the Euclidean metric described in Eq. (5). 7: Make the host decision using Eq. 3, The second step is based on the existence of a case when 8: t + +, the target is not in the player’s neighborhood. And here, the 9: end while Cuckoo Search Algorithm is used. A random population of 10: Find the cuckoo with the best adaptation according to cuckoos is spread on the board and shifted during a certain fitness condition, number of iterations. Individuals are looking for a goal using 11: Return the best cuckoo, the fitness function. At the end of algorithm’s performance, the 12: Stop. best adapted cuckoo is returned relative to the current position of the player. The player makes one move towards the position 13 Algorithm 2 Proposed Game Strategy of moves needed to complete the game or to win. All obtained 1: Start, results were averaged in the following way 2: Define the position of player, n X 3: neighbor:= f alse, vi 4: for each direction in set {north, south, west, east} do i=0 vavg = , (6) 5: if the target position is a neighbor then n 6: neighbor:= true, where vavg is the average value based on n trials (where 7: break the loop, the results are marked as vi ). Based on 100 games, the 8: end if average percentage of the player’s winnings and the proposed 9: end for technique was calculated. The result is shown in Fig. 2. In the 10: if neighbor is true then conducted experiments, the player and the computer algorithm 11: Make a move towards the goal, participated together in the game, which directly allowed to 12: else compare the game’s cope. It is easy to see that the computer 13: for each position in the neighborhood of size 3 × 3 do still has an major advantage over the player, although it is 14: if the target position is a neighbor then slightly less than the intended effect of 100% winnings. 15: Make a move towards the goal, The next parameter was the time needed to win as opposed 16: neighbor:= true, to the other player (see Fig. 3). It is clear that the computer is 17: break the loop, doing better because it always ends the game in almost twice 18: end if as fast compared to the human opponent. It was also noticed 19: end for that the results of the algorithm are more convergent than the 20: end if player, which allows to assess the accuracy of the algorithms 21: if neighbor is f alse then as sufficient for conducting subsequent experiments. Applying 22: Use Cuckoo Search Algorithm described in Alg. 1 to linear regression on the obtained results shows some stability find the goal, of the proposed technique – the time of which increases very 23: Make a move towards the target found by the cuckoos, slowly in relation to the increase the number of movements. 24: end if For people, the average results are quite chaotically distributed, 25: Stop. which may be due to the randomness of the points arrange- ment. The mentioned randomness turns out to be insignificant for the algorithm with the average number of samples. In Fig. found by the cuckoo. The use of heuristic allows to search 4 illustrated the average movement results in relation to the the whole board, not to move randomly when the target is not number of points in the game obtained for described method. nearby and the board is large. The main idea of the proposition The computer needs an average of one second to make a move is presented in Alg. 2. based on the assumption that the heuristics operates on 100 individuals and moves them during 1000 iterations. Such a result is satisfactory considering the amount of calculations. V. C ONCLUSION In this paper, the use of a heuristic algorithm as a help in controlling the player on large boards and the pursuit of randomly set points has been presented. This type of solution is characterized by high randomness, albeit with a small amount of calculations. The obtained results indicate a great potential in the use of heuristics as a gaming support technique. Especially in the action of the opponent or the second player. The level of difficulty can be adapted to the number of iterations/individuals in the population. R EFERENCES [1] B. Burgh and K. Johnsen. Effects of tracking scale on user performance in virtual reality games. In Everyday Virtual Reality (WEVR), 2017 IEEE 3rd Workshop on, pages 1–4. IEEE, 2017. Figure 2: Average number of wins. [2] P. Gamito, J. Oliveira, C. Coelho, D. Morais, P. Lopes, J. Pacheco, R. Brito, F. Soares, N. Santos, and A. F. Barata. Cognitive training on stroke patients via virtual reality-based serious games. Disability and IV. E XPERIMENTS rehabilitation, 39(4):385–388, 2017. [3] C. Gao, R. B. Hayward, and M. Müller. Move prediction using deep The proposed solution has been implemented in C# and convolutional neural networks in hex. IEEE Transactions on Games, tested in terms of the duration of the performance and number 2017. 14 Figure 3: A graph of time dependence on the average number of movements needed to win the game for a man and the proposed algorithm. Figure 4: Graph of the number of movements in relation to time. [4] G. Graditi, M. L. Di Silvestre, R. Gallea, and E. R. Sanseverino. 2016. Heuristic-based shiftable loads optimal management in smart micro- [9] M. Morosan and R. Poli. Automated game balancing in ms pacman grids. IEEE Transactions on Industrial Informatics, 11(1):271–280, and starcraft using evolutionary algorithms. In European Conference on 2015. the Applications of Evolutionary Computation, pages 377–392. Springer, [5] T. Kapuściński, R. K. Nowicki, and C. Napoli. Comparison of effective- 2017. ness of multi-objective genetic algorithms in optimization of invertible [10] D. Połap. Neuro-heuristic voice recognition. In Computer Science and s-boxes. In International Conference on Artificial Intelligence and Soft Information Systems (FedCSIS), 2016 Federated Conference on, pages Computing, pages 466–476. Springer, 2017. 487–490. IEEE, 2016. [6] L. H. Lelis, W. M. Reis, et al. Procedural generation of game maps with [11] D. Połap, K. K˛esik, K. Ksiażek, ˛ and M. Woźniak. Obstacle detection as human-in-the-loop algorithms. IEEE Transactions on Games, 2017. a safety alert in augmented reality models by the use of deep learning [7] N. Liu, Q. Chen, J. Liu, X. Lu, P. Li, J. Lei, and J. Zhang. A heuristic op- techniques. Sensors, 17(12):2803, 2017. eration strategy for commercial building microgrids containing evs and [12] D. Połap, K. K˛esik, M. Woźniak, and R. Damaševičius. Parallel pv system. IEEE Transactions on Industrial Electronics, 62(4):2560– technique for the metaheuristic algorithms using devoted local search 2570, 2015. and manipulating the solutions space. Applied Sciences, 8(2):293, 2018. [8] M. Mohammadi, R. Tavakkoli-Moghaddam, A. Siadat, and Y. Rahimi. A [13] D. Połap, M. Woźniak, C. Napoli, and E. Tramontana. Real-time cloud- game-based meta-heuristic for a fuzzy bi-objective reliable hub location based game management system via cuckoo search algorithm. Interna- problem. Engineering Applications of Artificial Intelligence, 50:1–19, tional Journal of Electronics and Telecommunications, 61(4):333–338, 15 (a) (b) (c) Figure 5: Tested boards for different amounts of goals. 2015. International Conference on Artificial Intelligence and Soft Computing, [14] N. Sephton, P. I. Cowling, E. Powley, and N. H. Slaven. Heuristic move pages 660–671. Springer, 2015. pruning in monte carlo tree search for the strategic card game lords [19] M. Woźniak, D. Połap, C. Napoli, and E. Tramontana. Application of war. In Computational Intelligence and Games (CIG), 2014 IEEE of bio-inspired methods in distributed gaming systems. Information Conference on, pages 1–7. IEEE, 2014. Technology And Control, 46(1):150–164. [15] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, [20] M. Wózniak, D. Połap, R. K. Nowicki, C. Napoli, G. Pappalardo, and A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al. Mastering the E. Tramontana. Novel approach toward medical signals classifier. In game of go without human knowledge. Nature, 550(7676):354, 2017. International Joint Conference on Neural Networks (IJCNN), pages 1– [16] I. J. Sledge and J. C. Príncipe. Analysis of agent expertise in ms. pac- 7. IEEE, 2015. man using value-of-information-based policies. IEEE Transactions on [21] X.-S. Yang and S. Deb. Cuckoo search via lévy flights. In Nature & Games, 2018. Biologically Inspired Computing, 2009. NaBIC 2009. World Congress [17] M. Woźniak and D. Połap. Bio-inspired methods modeled for respiratory on, pages 210–214. IEEE, 2009. disease detection from medical images. Swarm and Evolutionary Computation, 2018. [18] M. Woźniak, D. Połap, M. Gabryel, R. K. Nowicki, C. Napoli, and E. Tramontana. Can we process 2d images using artificial bee colony? In 16