Heuristic approach to the game of darts by using Genetic Algorithm and Ant Colony Optimization. Kamil Ksia˛żek∗ , Wojciech Masarczyk† , Iwona Nowak ‡ Faculty of Applied Mathematics Silesian University of Technology Gliwice, Poland ∗ Email: kamiksi862@student.polsl.pl † Email: wojcmas042@student.polsl.pl ‡ Email: Iwona.Nowak@polsl.pl Abstract—A paper illustrates the use of two metaheuristics: operators like mutation or crossover. ACO is a type of Swarm Genetic Algorithm and Ant Colony Optimization in darts play. Intelligence based on real ants behaviour. The results obtained The goal of the game is to hit on the centre of the dartboard. in both methods and approptiate comparison is also presented Both the creation of physical model and the optimization of the problem (based on heuristic algorithms) are presented in details. at the end of work. Two approaches are discussed and compared with respect to the The article is divided into several sections. In section 2. results. it will be explained physical model playing darts. Genetic Algorithm, genetic operators like mutation and crossover, Index Terms—metaheuristics, genetic algorithm, Ant Colony selection and other details connected with this topic will be Optimization, darts, physical model analyzed in section 3. In section 4. there is described second metaheuristic: Ant Colony Optimization. In the last section, the results of both methods will be compared. I. I NTRODUCTION Heuristic algorithms are versatile method to solve many II. P HYSICAL M ODEL problems in which, for various reasons it is difficult to find In dart game player is obliged to collect fixed sum of a solution. These methods do not guarantee obtaining the points that are signed to his account only if a thrown dart hits optimal solution, but found with their help solutions are an appropriate part of the dartboard. Considering this short usually accurate enough and sufficient to deal with analyzed description of rules it seems obvious that accuracy of throw problems. plays main role in dart game. In the presented approach the The word ’heuristic’ comes from the Greek ’heurisko’ model simulates trajectory of a throw based on three variables: (it means: I find) [18] These are rules which help to find speed, α and β angles; speed is initial speed of a dart, α angle (discover) best approximation of solution. Various applications lies between vertical and horizontal components of velocity of these methods show that evolutionary computation can help and β describes angle between horizontal and side velocity as in decision support systems. Heuristic methods are efficient shown on Fig. 1. in image processing [13], [15] but also voice recognition Friction force was skipped because its role is negligible - it is [10], while devoted combinations of artificial intelligence assumed that competitions take place in closed spaces. Dart is approaches are implemented together with other solutions into treated as a point. General formula to determine trajectory of complex systems [8] and robotics [17]. The paper presents use a thrown dart is: of two population heuristics in darts play. Darts is a game in g which darts are thrown at a dartboard fixed to a wall [1]. y = x · tan(α) − · x2 , (1) 2 · vx2 Generally, the accuracy of hitting into the appropriate pole of the dartboard is the main goal of the game. Appropriate where speed and angle of throw is necessary to obtain success. x − distance, In the paper the main goal is to demonstrate how to use g − standard gravity (about 9.80665 m s ), heuristics in order to choose the parameters mentioned. It vx − horizontal speed. will be also analyzed a situation in which the setting of the player is not optimal, ie. when he stays not directly in front Distance obtained by a dart may be expressed as: of the dartboard. To solve the problem, the Genetic Algorithm and Ant Colony Optimization (ACO) is applied. Evolutionary x = vx · t, (2) algorithm is treated as the classical metaheuristic using genetic hence g · t2 Copyright c 2017 held by the authors. y(t) = vx · t · tan(α) − . (3) 2 33 where d − vertical distance from a perfect position (2.37m), r − difference between optimum position and actual position of a player. The last step is introduction of (5) into equation (1) and on the basis of it, to determine the vertical position of the dart. Both vertical and horizontal distance from center of the dartboard will be used to judge the value of fitness function. III. G ENETIC A LGORITHM A. History Genetic Algorithm is a multi-agent algorithm based on idea of evolution that leads to survival only the best genotypes in whole population. Genetic algorithms have grown in pop- ularity through the work of John Holland, especially by his book [2]. Until Genetic Algorithm Conference in Pittsburgh (Pennsylvania), the research was mainly theoretical, however Figure 1. The Physical Model of thrown after that more and more applications has been introduced. Evolutionary methods are one of the most popular and they begin to play significant role of classical heuristics. This makes that the action of heuristics of different types are compared with the work of GA. B. Description The main body of the Genetic Algorithm consists of mod- ules that might be modified up to needs of user. Three basic modules of an algorithm are: • Selection • Genetic Operators – Mutation – Crossover • Succession General structure of GA is presented below in a form of pseudocode. Figure 2. Curvature of dart’s trajectory h] Pseudocode of Genetic Algorithm Input: number of genotypes in population: m, number of iteration: I, boundary of the domain, coefficients: The formula (3) describes height of a dart dependent on time probability of crossover pc , probability of mutation pm while the rest of unknowns are treated as parameters. In order Output: coordinates of minimum, value of fitness function to describe the curvature of dart’s trajectory the following Initialisation: formula can be used: Creating the initial population P1 = {x1 , x2 , ..., xm } c = vz · t, (4) Searching xbest in initial population P1 ; xopt = xbest . Calculations: where i=1 vz − initial side speed of the dart (shown on Fig. 1), while i < I do t − time. Pi = Selection(Pi ) Fig. 2 presents view of Fig. 1 on plane y = 0. There are shown Oi = Genetic Operators(Pi ) dependencies between vx and vz . Pi+1 = Succcession(Oi , Pi ) To estimate the accuracy of a throw we need to know when Searching xbest in Pi+1 . j exactly a dart hits the wall. According to official rules of a if xbest is better than xopt then j dart game the distance between dartboard and players has to xopt = xbest j be exactly 2.37m. Once it is assumed that player may stand end if not perfectly in front of the dartboard the whole horizontal i++ distance will be as followed: end while p x = d2 + r 2 , (5) end 34 At the beginning, the algorithm randomly generates genotypes. by Marco Dorigo [4] - he used it to solve combinatorial In presented case each genotype consists of three genes: speed, problem (more specifically, travelling salesman problem). The α and β. Every genotype is separately graded by fitness approach presented in the paper was developed by M. Duran function: Toksari [7] - he applied Ant Colony Algorithm in continuous problem. It is not the only proposition of ACO for solving p Φ(vx , α, β) = | d2 + (d · tan β)2 · tan(901◦ −β) − s| + continuous problem. Other modification of this algorithm p based on different approach was analyzed by K. Socha and + | d2 + (d · tan β)2 · tan α − (6) M. Dorigo [11]. The idea of Ant System Algorithm is based 2 β)2 + 0.5 · g · d +(d·tan vx2 − (p − h)|, on behaviour of real ant colony. In the presented case ants where are solutions (optimum of a function). Ants during search can s − distance from perfect position, communicate with each other by using chemical substance vx − speed of dart, called pheromone. On more attractive roads ants leave more h − height of throw. quantity of pheromone so next ants know which path is more g − standard gravity promising. Furthermore, pheromone is evaporating from non- d − vertical distance from a perfect position (2.37m) used paths. It means that pheromone is impulse to search. On p − height of a center of a dartboard (1.73m) the following iterations search area is narrowed so ants try perfect position − a thrower is standing exactly on the to find more accurate solution and they abandon unpromising center in front of a dartboard roads. Selection module picks two genotypes selected randomly B. Description and compares their fitness functions. The better one is picked to temporary population. Whole procedure is repeated until h] Pseudocode of Ant Colony Optimiza- new population has m genotypes in it. This classical approach tion is called Tournament Selection. Input: number of ants: m, number of iteration inside: I, Mutation is an genetic operation which works on single number of iteration outside: n, boundary of the domain, genotype and probability of its occurrence is usually smaller initial parameters: α, β, coefficients: λ, ω than 10%. The following formula presents mechanism of Output: coordinates of minimum, value of fitness function averaging mutation: Initialisation: Creating the initial colony of ants. C1 = {x11 , x21 , ..., xm 1 } y = xki + ξr (7) Searching xbest in initial colony; xopt = xbest . where Calculations: xki − the i − th genotype of k − th population, i=1 ξr − vector random generated with normal distribution while i < n do N (0, 1) j=1 while j < I do Crossover process takes two parental genotypes from tem- Moving the nest of ants - defining new territory of porary population to evolve them into one new genotype ant colony. by mixing their genes. There also exist modifications where Searching xbestj in present colony. e.g. each gene is mixed separately with different genotypes, if xbest j is better than xopt then however to keep this procedure simple and transparent the first xopt = xbest j approach was implemented: end if end while y = xki + ξU (0,1) (xkj − xki ) (8) Defining new search area (narrowing of the territory). where end while xki − the i − th genotype of k − th population, end ξU (0,1) − number randomly generated from uniform After fixing input parameters, the algorithm is generating m distribution U (0, 1), ants in form:   Elitism Succession relies that the population Pi+1 is formed xki = xk,1 k,2 k,S i , xi , ..., xi , (9) by picking m best solutions from set Pi ∪ Oi , where Oi is a set of offsprings − solutions coming from genetic operators. where k − number of ant, k = 1, ..., m, S − number of dimensions. IV. A NT C OLONY O PTIMIZATION i − number of iteration A. History Then is necessary to find the best ant in population in Ant Colony Optimization is biologically inspired multi- current iteration: xbest (it is best solution until this iteration). agent algorithm. The base of this algorithm was invented Additionaly, it is assumed xopt = xbest . The next step is 35 attempt to find a better place for the nest, what is realized by formula: ∀k xkj = xopt + dx, (10) where  dx = dx1 , dx2 , ..., dxS − vector of pseudorandom value, dxi ∈ [−αj , αj ] in the case of angles, dxi ∈ [−βj , βj ] in the case of speed, αj , βj - parameters of ACO procedure, j − number of iteration. This part of program is intended to exploration the domain. Now it should be checked if colony found better place to the nest. If at least one point has better value of fitness function (xbest j is better than xopt ), then the nest is moving (xopt = xbest j ). Last step is decreasing the length of jump (searched domain will be smaller). αj = λ · αj−1 , λ ∈ (0; 1) (11) βj = ω · βj−1 , β ∈ (0; 1) (12) Figure 3. Result no. 3 (ACO): the values of the alpha angle during successive iterations In this case λ is responsible for reduction of domain during finding angles: α and β. ω is in charge of narrowing neigh- bourhood in search of speed. Then calculations are continued in smaller domain. The parameters λ and ω should be chosen carefully. If the domain is wide, λ and ω could be greater than 0.5. If a territory for ants is relatively narrow, λ or ω may be close to 0.1. In multi-dimensional problems it may define other parameter for every coordinate. V. R ESULTS The purpose of this paper is presenting heuristic approach to the game of darts. Two algorithms have been tested: Genetic Algorithm and And Colony Optimization. It was done for the same input data and results were compared in Tab I, obviously both algorithms had exactly the same fitness function (6). The stopping criterium was number of iterations. In the case of Genetic Algorithm it was 50 iterations for all measurements while researches by using of Ant Colony Optimization was done by 20 internal iterations and 30 external iterations. Generally Ant Colony Optimization algorithm provides higher precision results (in two tested positions of thrower results was better by using Genetic Algorithm − font is bold in Figure 4. Result no. 3 (ACO): the values of the beta angle during successive better scores). It was explored different distances from center iterations position and height of thrower. In every case it was obtained great approximation of perfect throw. Graphic interpretation of our results is presented on the Fig. 6-7, what can be treated VI. F INAL REMARKS as warranty that given results are right data. In the physical model it was applied Manhattan metrics Heuristic algorithms are one of the best option in problems [12] in order to describe the distance between center of a hard to optimization. The simple idea and in consequence dartboard and the point where dart hits. Due to the fact that implementation makes that these methods are often used by heuristic algorithms give only approximate results it is unlikely researchers in many fields. It is possible to find results with to obtain fitness function equal to 0, however presented results, high precision by using these methods. especially from Ant Colony Optimization are close enough to The calculations, which results were presented, were de- claim that presented algorithms solve this problem really well. signed to study the mechanism and capabilities of both heuris- 36 Table I R ESULTS - G ENETIC A LGORITHM AND A NT C OLONY O PTIMIZATION Initial values Genetic Algorithm Ant Colony Optimization number number distance height Alpha Beta Speed Fitness Alpha Beta Speed Fitness func- of points from center [m] Function tion value [m] value 1) 20 0.3 1.72 1.54827 7.09627 20.7708 0.01295 0.563096 7.15305 46.9301 0.00101282 2) 20 0.3 1.42 9.03306 6.4393 20.0802 0.000873 7.69221 7.15355 46.8414 0.000348181 3) 30 -0.3 1.72 1.8878 -7.1609 20.2996 0.000938 1.87287 -7.14723 20.3986 0.00136371 4) 20 0 1.72 2.5794 0.8024 16.8526 0.033815 0.502524 0.00657695 49.9034 0.000544269 5) 20 -0.5 1.72 2.00376 -11.647 21.893 0.016154 0.430806 -11.6467 59.7989 0.00139404 6) 40 -0.5 1.72 2.11129 -11.411 19.7369 0.016178 0.779071 -11.656 36.2781 0.00188963 7) 40 -1 1.72 2.8478 -21.164 18.6461 0.041302 1.12286 -21.4121 28.2772 0.00188559 8) 40 -1 1.52 6.2153 -21.425 21.7337 0.0000581 6.12793 -11.687 24.0042 0.000631615 Figure 5. Result no. 3 (ACO): the speed during succesive iterations Figure 6. Result no. 1: graphic interpretation tics. All solutions are on satisfactory level what proves that [6] D. Połap, M. Woźniak, C. Napoli, E. Tramontana, R. Damasevicius, “Is both the mathematical model and optimization procedure have the colony of ants able to recognize graphic objects?,“ in International Conference on Information and Software Technologies. pp. 376–387, been chosen correctly. One can use heuristic algorithms to Springer International Publishing, DOI: 10.1007/978-3-319-24770-0_33. solving other real problems, perhaps another game or some [7] Toksarı, M. Duran, "A heuristic approach to find the global optimum more complicated models. of function." Journal of Computational and Applied Mathematics 209.2 (2007): 160-166. [8] D. Połap, M. Woźniak, “Introduction to the Model of the Active R EFERENCES Assistance System for Elder and Disabled People,“ in Communications in Computer and Information Science, vol. 639, pp. 392–403, 2016, [1] https://en.wikipedia.org/wiki/Darts (Retrieved January 31, 2017) DOI: 10.1007/978-3-319-46254-7_31. [2] J. H. Holland, “Adaptation in natural and artificial systems.“ (1975). [9] S. Cicciarella, C. Napoli, E. Tramontana, “Searching Design Patterns [3] Á. E. Eiben, R. Hinterding, Z. Michalewicz. “Parameter control in evo- Fast by Using Tree Traversals,“ in International Journal of Electronics lutionary algorithms.“ IEEE Transactions on evolutionary computation and Telecommunications, vol. 61, no. 4, pp. 321–326, 2015, DOI: 3.2 (1999): 124-141. 10.1515/eletel-2015-0041. [4] M. Dorigo, T. Stützle, “Ant Colony Optimization“, MIT Press, Cam- [10] D. Połap, “Neuro-heuristic voice recognition,“ in 2016 Federated Con- bridge, MA, 2004 ference on Computer Science and Information Systems, FedCSIS 2016, [5] D. Połap, M. Woźniak, C. Napoli, E. Tramontana, “Is Swarm Intelli- Proceedings. 11-14 September, Gdańsk, Poland, IEEE 2016, pp. 487– gence Able to Create Mazes?,“ in International Journal of Electronics 490, DOI: 10.15439/2016F128. and Telecommunications, vol. 61, no. 4, pp. 305–310, 2015, DOI: [11] K. Socha, M. Dorigo, "Ant colony optimization for continuous do- 10.1515/eletel-2015-0039. mains." European journal of operational research 185.3 (2008): 1155- 37 Figure 7. Result no. 8: graphic interpretation 1173. [12] M. Barile, "Taxicab Metric." From MathWorld A Wol- fram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/TaxicabMetric.html (Retrieved January 31, 2017) [13] M. Woźniak, “Novel Image Correction Method Based on Swarm Intel- ligence Approach,“ in Communications in Computer and Information Science, vol. 639, pp. 404–413, 2016, DOI: 10.1007/978-3-319-46254- 7_32. [14] C. Napoli, G. Pappalardo, E. Tramontana, R.K. Nowicki, J.T. Star- czewski, M. Wozniak, “Toward Work Groups Classification Based on Probabilistic Neural Network Approach,“ in Artificial Intelligence and Soft Computing (ICAISC), Lecture Notes in Computer Science, vol. 9119, pp. 79–89, 2015, DOI: 10.1007/978-3-319-19324-3_8. [15] M. Woźniak, D. Połap, C. Napoli and E. Tramontana, “Graphic ob- ject feature extraction system based on Cuckoo Search Algorithm“ Expert Systems with Applications, vol. 60, pp. 20–31, 2016, DOI: 10.1016/j.eswa.2016.08.068. [16] D. Połap, M. Woźniak, C. Napoli, E. Tramontana, “Real-time cloud- based game management system via cuckoo search algorithm,“ in International Journal of Electronics and Telecommunications, vol. 61, no. 4, pp. 333–338, 2015, DOI: 10.1515/eletel-2015-0043. [17] L. Zmudzinski, A. Augustyniak, P. Artiemjew, Control of Mindstorms NXT robot using Xtion Pro camera skeletal tracking, Technical Sciences, vol. 19, no.1, pp. 71-81, Olsztyn, UWM Publisher, 2016. [18] K. Trojanowski, “Metaheurystyki praktycznie“, Warsaw School of In- formation Technology, p.7, Warsaw 2008. 38