Board games always need algorithms for players to be a challenge for people. The only way to increase playability for people is to create an algorithm that will be intelligent enough to beat a human. In our paper we decided to implement an algorithm based on reward and punishment, which decides every turn which move is the best, considering the situation on the board.
in diferent fields [6, 7, 8] .
Last year brought diferent types of reality games Game development is important due to many diferent like virtualcit [9] or augmented [10, 11] which are still factors, and above all entertainment. It is notewor- improved. In [12], the authors presented the results of thy that players drive their development by placing their analysis that games help students learn. Again greater and greater requirements regarding the story in [13], the idea of gamification is described with some as well as the quality of the game. This means that results based on conducted experiments. newer games need more computing power, so the de- In this paper, we propose a solution for playing checkvelopment of equipment that allows them to run is ers, where the current iteration of the game is analyzed driven very fast. The plot, the world surrounding the on the basis of the reward and punishment technique. hero are also important and quite often both elements are generated by algorithms that must be constantly developed and improved. In addition, the behavior of 2. Checkers’ rules opponents is important for the whole game, which is commonly called as artificial intelligence. All these Checkers are one of the most known classic board gaelements are constantly being developed in order to mes based on strategic thinking. They were invented improve the quality of multimedia games production. probably in the XII century and since then there were Improvements in network for remote gaming are also created many variants of board and play. The basic envisaged [1]. and the only one being sport discipline is International
The development of game analysis strategies and Checkers also called Polish Checkers, where the board artificial intelligence activities point to milestones in is 10 × 10 tiles and each player has 20 checkers. Howthis field. One of the biggest is the algorithm that de- ever, the most played by people is the English variant feated the world champion in the game of Go, which is with 8 × 8 board and 12 checkers per player. considered much more dificult than chess [2]. Other The board is divided into black and white tiles artypes of games are also analyzed by the researcher ranged alternately, which in our program is grey and what can be seen in [3]. The authors proposed a new yellow to better recognition of checkers, which also strategy for solving fuzzy matrix games. In [4], the are black-white. We used an English variant with checkauthors described a sequential model for the predic- ers set on black tiles. According to the assumption tion of poker moves. Again in [5], the idea of using each player has 12 checkers set on the opposite edges eye gaze to play cards with the use of artificial neural of the board in three rows. This arrangement of ponetworks was presented. In fact the neural networks sition is shown in Fig. 1. The goal of this game is to have proved to be a very powerful tool for predictions take of all enemy’s checkers – then the winner is the player who has at least one checker on the board.
IVUS 2020: Information Society and University Studies, 23 April 2020, This game requires strategic thinking and considerKTU Santaka Valley, Kaunas, Lithuania ing possible movements of the enemy, and, which is " Alicja.Lidia.Winnicka@gmail.com (A. Winnicka) the most important, ability to change a plan depend© 2020 Copyright for this paper by its authors. Use permitted under Creative ing on the situation on the board.
CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g CCoEmUmoRns WLiceonrsekAsthtriobuptioPnr4o.0cIneteerdnaitniognasl ((CCC EBYU4R.0)-.WS.org) We assume that checkers can move only diagonally
• checkers can take kings, on the black tiles and they can move one tile per turn. 3. Algorithm The situation, when we want to take an enemy’s checker in the neighborhood. Then tile behind this tile must The purpose of our algorithm is to find the best option be empty and our checker jumps over enemy’s one, to move during one turn. We may divide it into a few so it moves over two tiles. Changing the checker to parts. "King" is a second exception. King can move over the whole board diagonally on black tiles. 3.1. First Step
One of these movements is treated as one turn, but after taking an enemy’s checker player can move again Let us assume that a checker is on (, ). In this sitin the same turn. A second player’s turn starts when uation, depending on the position, it can have maxithe first player will move without taking his checker. mally four directions to move, which are checked to
According to the description above, we had to set a classified as possible or not possible to move. It will few basic assumptions: be classified as not possible when our checker is on the edge of the board or a checked tile is not empty. • checkers can move backward, For example, the checker marked as red in Fig. 2 has two options to move – left-up and right-up – because • checkers can take others checkers backward, two tiles below him are used by other white checkers. • taking checkers is not obligatory, Because our coordinates starts in top left corner, these tiles are on ( − 1, − 1) and ( + 1, − 1). • king can move in diagonal line through whole
board, • board is 8 × 8, • checkers move on black tiles, • player with white checkers starts. 3.2. Second Step After finding all the options for a turn, we have to calculate which of them is the best option. This calculating is based on the sum of rewards and punishment connected to these movements. As a reward, we treat being close to changing into the king and taking the enemy’s checker. Alternatively, punishments mean being possibly taken in the next enemy’s move.
Let us set (, , ) as this sum for the one movement. According to our function, it will be a sum of three values: • reward for being closer to be a king:
A basic assumption in this option is the fact, that being closer to being a king means being closer to the enemy’s edge of the board. Additionally, it is important, how many checkers have the player.
It will be more urgent to have a king when the number of checkers is smaller – it would be very useful to have a king when there is only one left checker on the board.
We needed a function, which will increase with increasing tile counter – a number of tiles between player’s edge of the board and a checker – and which will have bigger values for a smaller number of checkers . We defined a function: (, ) = | sin( ) |
(1) • reward for taking enemy’s checker:
The second reward is the situation when a player can take the enemy’s checker. Because it is a goal of the game player should be focused on this – so if the player can take enemy’s checker it must be his priority - unless his winning is in danger. Additionally, this move causes the possibility of the next move, so another value to the reward – all these rewards are calculated as a reward of this turn.
It is worth noticing that the less enemy’s checkers, the better is the player’s situation. According to this, we assumed that it is more urgent to take enemy’s checkers’ when there are fewer of them – to finish the game quickly. We needed a function dependent on a number of enemy’s ifned simple increasing function: checkers and player’s checkers and we de 1
, (, ) = , ∈ [1, 12]
(2) • being taken: equation:
In this situation our will be defined with following (, , ) = (, ) + ( ) − (,
) + edge, where ∈ [0, 8] is number of tiles from player’s andV alu∈e(o0f, 1is)caislcrualnadteodmfovraeluaec.h possible move in this turn (so each possibility for each checker) and the next algorithm finds the best of them, which is equivalent to the biggest one. This value is treated as the best option to move considering the situation on the board.
(4)
was added to make small difersmall diferences between them. ences between possibilities which are simple moves towards the end of the board and where is the same.
became predictable, because it would choose the first of the option with the same value. allowed to make
Being killed must be punished – we have a similar situation to the taking enemy’s checker. If the move will cause the possibility of being taken
tile. between taking and being taken we used the same options for the move: function as punishment, but we will subtract it: smaller to avoid this. To balance the diference by the enemy’s checker, a value of has to be edge to the enemy’s edge and on the to reward . On this figure we can see two considered
is calculated • move towards enemy’s edge without taking or (, ) =
1 ∗ , , ∈ [1, 12] (3) being taken,
an enemy may do the move which was not included in • taking the eighth enemy’s checker. chosen series of moves.
First, one is our (, , ) and is assigned to blue It means, that our algorithm is more exact than for functions on the Fig. 3 They are changing in the con- example minimax algorithm, but is faster and better nection to a number of player’s checkers. This func- for a quick game. tion is a function corresponding to the need of havipnlagyaerk’isncghaenckdeirnsc.rReeadsefsuwncitthioan dmeecarenasstihneg rneuwmabrderfoorf 5. Conclusions taking the eighth enemy’s checker. In this paper, we showed a reward and punishment
We noticed that taking the enemy’s checker is more based algorithm as a possible algorithm deciding how rewarded in any place of the board for more than five to move in checkers. Our algorithm turned to be good player’s checkers. The situation is more complicated enough to play against an intelligent person, however when a player has five or fewer checkers – for five with a trend to lose checkers at the beginning of the checkers and for the fifth tile algorithm will choose to game. It is much better in choosing how to move when go further to be a king. a number of player’s and enemy’s checkers changes
This whole algorithm decides about priorities dur- dynamically during the game. ing the play but is not good enough to choose always In future papers, we will focus on increasing the efthe best option from a human’s point of view. An ex- fectiveness of the algorithm at the beginning of the ample of a bad decision is shown in Fig. 4. game.
Here we have the same two options which are mentioned above, but this time after taking one enemy’s checker, the player can take another two, decreasing References the number of enemy’s checkers to 10. It will do it if player’s checkers are mostly above 3, but for 1, 2 or 3 [1] G. Ciccarella, R. Giuliano, F. Mazzenga, F. Vatacheckers, it will still go to the edge of the board, ignor- laro, A. Vizzarri, Edge cloud computing in ing the opportunity to take three enemy’s checkers. telecommunications: Case studies on perfor
Another situation is visible on the bottom of the mance improvement and tco saving, IEEE Fig. 4 – when the player has even his full set of 12 Int. Conference on Fog Mobile Edge Computing and the enemy has 12 too, the player will choose to (FMEC 2019) (Rome, Italy, Jun. 2019) 113–120. go further instead of taking one enemy’s checker. [2] D. Silver, J. Schrittwieser, K. Simonyan,
One of the most popular algorithms for games is the I. Antonoglou, A. Huang, A. Guez, T. Huminimax algorithm. This algorithm finds the best op- bert, L. Baker, M. Lai, A. Bolton, et al., Mastering tion for the chosen player, considering possible moves the game of go without human knowledge, Jourfor both players and finds the best option from every nal of Artificial Intelligence and Soft Computing combination of moves. It ensures that literally the best Research 550 (2017) 354—-359. of all moves will be found, however simultaneously re- [3] A. Mansoori, M. Eshaghnezhad, S. Efati, Recurquires much more computing power during each turn rent neural network model: a new strategy to to check if the best option is still the best one – because solve fuzzy matrix games, IEEE transactions on neural networks and learning systems 30 (2019) 2020, pp. 7–12.
2538––2547. [9] D. Połap, K. K˛esik, M. Woźniak, Accident pre[4] R. Radziukas, R. Maskeli ̄ nas, R. Damăevi ̆ ius, vention system during immersion in virtual rePrediction of poker moves using sequential ality, in International Conference on Multimemodel and tensorflow, International Confer- dia and Network Information System. (Springer, ence on Information and Software Technologies 2018) 565––573.
(Springer, 2019) 516––525. [10] D. Połap, Human-machine interaction in intel[5] Q. Hu, S. Yean, J. Liu, S. Lee, D. Rajan, ligent technologies using the augmented reality, R. Phattharaphon, Using eye gaze to play mind Information Technology and Control 47 (2018) card-game using neural network, Proceedings 691––703. of The Fifth International Conference on Elec- [11] D. Połap, M. Woźniak, C. Napoli, E. Tramontana, tronics and Software Science (ICESS2019) (Japan, Real-time cloud-based game management sys2019) 54. tem via cuckoo search algorithm, International [6] F. Beritelli, G. Capizzi, G. Lo Sciuto, C. Napoli, Journal of Electronics and Telecommunications F. Scaglione, Rainfall estimation based on the in- 61 (2015) 333–338. tensity of the received signal in a lte/4g mobile [12] J. Hamari, D. J. Shernof, E. Rowe, B. Coller, terminal by using a probabilistic neural network, J. Asbell-Clarke, T. Edwards, Challenging games IEEE Access 6 (2018) 30865–30873. help students learn: An empirical study on en[7] F. Bonanno, G. Capizzi, G. Sciuto, C. Napoli, gagement, flow and immersion in game-based Wavelet recurrent neural network with semi- learning, Computers in human behavior 54 parametric input data preprocessing for micro- (2016) 170—-179. wind power forecasting in integrated generation [13] M. Sailer, J. U. Hense, S. K. Mayr, H. Mandl, How systems, 2015, pp. 602–609. gamification motivates: An experimental study [8] G. Capizzi, C. Napoli, S. Russo, M. Woźniak, of the efects of specific game design elements Lessening stress and anxiety-related behaviors on psychological need satisfaction, Computers by means of ai-driven drones for aromatherapy, in Human Behavior 69 (2017) 371—-380. in: CEUR Workshop Proceedings, volume 2594,