=Paper=
{{Paper
|id=Vol-1852/p06
|storemode=property
|title=Heuristic approach to the game of darts by using
genetic algorithm and ant colony optimization
|pdfUrl=https://ceur-ws.org/Vol-1852/p06.pdf
|volume=Vol-1852
|authors=Kamil Ksiażek,Wojciech Masarczyk,Iwona Nowak
}}
==Heuristic approach to the game of darts by using
genetic algorithm and ant colony optimization==
https://ceur-ws.org/Vol-1852/p06.pdf
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