-All kinds of games force continuous development of not only hardware technologies, but also solutions that increase playability. One of such aspects is the way the world interacts with the user. The effect of this is the technique of opponents action, which enforces a certain degree of difficulty on the player and is constantly driven and motivates to pass the game faster and more efficiently. In this work, I present the strategy of reaching a certain point on the board by the computer through the use of a modified heuristic algorithm, ie a Cuckoo Search Algorithm. The proposed solution has been described, tested and discussed due to the advantages and disadvantages of this solution.
The computer market develops through a lot of competition, as can be seen from the AMD and NVIDIA companies that produce graphics cards. Releasing a product of one of these companies, forces a lot of pressure on the other one. It results in the release of another card within a few months. Graphics cards are one of the basic requirements of computer games so the pressure to produce more efficient and cheaper cards is also on the side of game producers. Developers put more requirements for hardware due to improvement realism and computer graphics used in their products. An additional burden for computers are engines, which are based on the methods of artificial intelligence. The goal is to increase playability and quality of products
Creating games is about applying and modifying advanced
solutions to achieve the greatest effectiveness. Effectiveness is
understood as the time of action, computing power, the quality
of the effects obtained and the impact on playability. One
of the basic elements due to the programmers is designing
the world, or maps on which the user can move. In [
Heuristic algorithms find an increasing application in game
theory due to their advantages. Not the predictability achieved
by random movements, as well as low computing power. In
[
Cuckoo Search Algorithm’s (CSA) [
The natural behavior of these birds resulted in the creation of a model originally used as a minimization of continuous functions. Algorithm assumes that cuckoo is interpreted as a point (x; y) on the solution space. In these case it is a board of size w h. Additionally, some assumptions must be done to adapt the algorithm to a new operating environment potential nests are random points on the board, each cuckoo has only one egg to lay, total number of cuckoos is constant in each iteration. best nests means the points located closest to the goal, hosts may detect thrown eggs egg with probability p 2 h0; 1i. In this case the egg is thrown out of the nest and new cuckoo is placed randomly on the board.
At the beginning of the models, some parameters of CSA must be defined as number of cuckoos and number of iterations (which can be interpreted as number of cuckoo’s moves). The initial population of birds are chosen at random on the whole solution space. In each iteration, the best nest is chosen after some steps. The first one is the movement of each birds according to x = x
L(x; d; c); (1) where addition or subtraction is selected at random with the equal probability 50% and L( ) is modified Levy distribution burdened with the ceiling function so the obtained values are integers. This action is enforced by the solution space, which is indexes of the height and width of the board. This function can be formulated as
L(x; ; ) = &r
e 2 (x ) ' 2 p(x )3 where the variables ; 2 R are randomly generated and x is a spatial coordinate of the mother-cuckoo.
The second step of the algorithms is the host decision. After, 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 1 p drop the egg 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) pw + h; 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 action forces you to move towards the goal you have found. The used function d( ) is Euclidean metric defined as vu 2 d(x; t) = tuX(xi i=0 ti)2; where x and t are points in two dimensional space. The pseudo-code of these version is shown in Alg. 1 Algorithm 1 Modified Cuckoo Search Algorithm 1: Start, 2: Define all required coefficient, number of cuckoos n, fitness function g( ), number of iterations and static position of enemies, 3: Create initial population of n cuckoos at random, 4: t:=0, 5: while t T do 6: Drop the egg according to Eq. (1), 7: Make the host decision using Eq. 3, 8: t + +, 9: end while 10: Find the cuckoo with the best adaptation according to fitness condition, 11: Return the best cuckoo, 12: Stop. (2) (3) (4) (5)
III. GAME STRATEGY BASED ON HEURISTIC ALGORITHM
Let us assume that a computer walks around a certain board of size w h. His task is to catch all opponents in as few moves as possible, so in the shortest possible time. Enemies are scattered on the board in a random way. In the case when two players play the game, its task is to collect at least half of all points (for one enemies is one point) to win the game. Of course, each player is placed in the opposite corner of the board. The player can make one move in one step, alternately.
In the game, several signs have been used. "@" as a player, "%" as a computer, and "#" as an enemy. The visualisation of these game is presented in Fig. 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) but only when it is possible. The move will be impossible to do if the player wants to move outside the board.
The proposed strategy consists of two stages. The first step is to check the nearest neighbors. As a neighborhood, we understood a matrix (which the maximum size is 3 3), where the player is in its center. If the target is achievable after taking one movement, it is performed without the slightest hesitation. If the cost of obtaining a goal is a maximum of 3 moves, movement towards it is carried out. The cost is calculated by the Euclidean metric described in Eq. (5).
The second step is based on the existence of a case when the target is not in the player’s neighborhood. And here, the Cuckoo Search Algorithm is used. A random population of cuckoos is spread on the board and shifted during a certain number of iterations. Individuals are looking for a goal using the fitness function. At the end of algorithm’s performance, the best adapted cuckoo is returned relative to the current position of the player. The player makes one move towards the position Algorithm 2 Proposed Game Strategy 1: Start, 2: Define the position of player, 3: neighbor:= f alse, 4: for each direction in set {north, south, west, east} do 5: if the target position is a neighbor then 6: neighbor:= true, 7: break the loop, 8: end if 9: end for 10: if neighbor is true then 11: Make a move towards the goal, 12: else 13: for each position in the neighborhood of size 3 3 do 14: if the target position is a neighbor then 15: Make a move towards the goal, 16: neighbor:= true, 17: break the loop, 18: end if 19: end for 20: end if 21: if neighbor is f alse then 22: Use Cuckoo Search Algorithm described in Alg. 1 to find the goal, 23: Make a move towards the target found by the cuckoos, 24: end if 25: Stop. found by the cuckoo. The use of heuristic allows to search the whole board, not to move randomly when the target is not nearby and the board is large. The main idea of the proposition is presented in Alg. 2.
The proposed solution has been implemented in C# and tested in terms of the duration of the performance and number of moves needed to complete the game or to win. All obtained results were averaged in the following way n
X vi vavg = i=0 ; (6) n where vavg is the average value based on n trials (where the results are marked as vi). Based on 100 games, the average percentage of the player’s winnings and the proposed technique was calculated. The result is shown in Fig. 2. In the conducted experiments, the player and the computer algorithm participated together in the game, which directly allowed to compare the game’s cope. It is easy to see that the computer still has an major advantage over the player, although it is slightly less than the intended effect of 100% winnings.
The next parameter was the time needed to win as opposed to the other player (see Fig. 3). It is clear that the computer is doing better because it always ends the game in almost twice as fast compared to the human opponent. It was also noticed that the results of the algorithm are more convergent than the player, which allows to assess the accuracy of the algorithms as sufficient for conducting subsequent experiments. Applying linear regression on the obtained results shows some stability of the proposed technique – the time of which increases very slowly in relation to the increase the number of movements. For people, the average results are quite chaotically distributed, which may be due to the randomness of the points arrangement. The mentioned randomness turns out to be insignificant for the algorithm with the average number of samples. In Fig. 4 illustrated the average movement results in relation to the number of points in the game obtained for described method. The computer needs an average of one second to make a move 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.
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.