Frontiers in Computing and Intelligent Systems ISSN: 2832-6024 | Vol. 3, No. 1, 2023 130 Design and Realization of Surakarta Chess Game Program Tao Zhang, Yefeng Jiang School of Computer and Software Engineering, University of Science and Technology Liaoning, Anshan 114051, China Abstract: At present, the research on Surakarta game is relatively less than other games. Aiming at this situation, a Surakarta chess game program is designed. This program implements basic algorithms such as board representation, move generation, game evaluation, and game tree search. The evaluation of the chess game takes into account the number of pieces, moving range, attacking range, attacking power of pieces, board value, arc value, etc. The game tree search algorithm uses the Alpha-Beta pruning algorithm. The whole program is fully functional and has a strong game level, which provides reference significance and reference value for related research. The program won the second prize at the national level in the computer game competition for college students in China, and the second prize at the provincial level in the computer game competition for college students in Liaoning Province, which verified the feasibility of the game program algorithm. Keywords: Surakarta Chess; Evaluation Function; Game Tree Search; Alpha-Beta Pruning Algorithm. 1. Introduction As an important branch of the field of artificial intelligence, computer game is a research field related to countermeasures and wits. It belongs to the problem solving and search technology in artificial intelligence. It is an important aspect to test the development level of artificial intelligence. Its research is artificial intelligence Bringing many important methods and theories. Board games are intelligent, so they have been valued in the field of artificial intelligence for a long time, and they are called the "fruit flies" of artificial intelligence. From Chess Deep Blue, which defeated the world chess champion Garry Kasparov, to the Go game program AIphaGo, which defeated Lee Sedol, computer games have once again attracted widespread attention in the industry. At the same time, the 16th China College Student Computer Game Competition has been successfully held in the college student competition, and Surakarta chess is one of the competition events. Compared with other chess games, the board of Surakarta is special, the rules are interesting, and the moves are changeable, which has attracted the attention of many machine game enthusiasts in recent years, so this paper conducts in-depth research on it. 2. Introduction to Surakarta Surakarta is a two-player game that originated from Surakarta in Java, Indonesia. Six sides horizontally and vertically form a square chessboard, and 36 intersections are chess positions. Each side is connected by 8 arcs, usually represented by 2 different colors. At the beginning of the game, each side has 12 pieces arranged in 2 rows. The chessboard is shown in Figure 1. The rules are as follows: 1). Participants toss a coin to decide who starts first. Only one pawn can be moved at a time. Two chess players take turns playing chess. 2). If there is no chess piece in the moving direction, any chess piece can move 1 square in 8 directions (up, down, left, right, upper left, lower left, upper right, and lower right). 3). If you want to capture the opponent's pieces, you must walk horizontally and vertically, and at least cross an arc tangent to the path, and the moving path cannot be blocked by your own pieces. 4). The sunspots can eat the red ones, and the red ones can also eat the sunspots in the opposite direction of the same path. 5). When all pieces of one side on one interface are captured, the game ends, and the side with remaining pieces wins. 6). Generally speaking, in computer games, if each game lasts more than 30 minutes, both sides will stop, and the side with more pieces remaining will win the game. Figure 1. Surakarta pieces, board and initial layout 3. Chessboard Design The chessboard generally adopts bit chessboard representation or array chessboard representation. In this paper, bit sequences are used to represent the position of each chess point on the board, and two-bit sequences are used to represent chess pieces of different colors. Use the following two sequences in the program to represent the position of the chess pieces on the board: bitset<36>ourSide("0000000000000000000000001111111 11111"); bitset<36>otherSide("11111111111100000000000000000 0000000"); 131 4. Move Generation In the Surakarta chess game system, move generation is to enumerate all valid moves in the current board state. According to the basic rules of Surakarta chess, it can be deduced that the paths of the capture behaviors that can occur on the chessboard are all on the inner and outer rails of the chessboard. Usually, the move generation needs to traverse the boards on both sides, constantly set the chess pieces as the starting point and end point of the movement, and judge whether the move is legal. This method needs to traverse the chessboard on both sides, so the space complexity is high and the search speed is slow. It can be seen that the speed of move generation is particularly important, which is related to the depth of the search algorithm and chess power. The basic idea of optimizing the generation of moves: set the own chess pieces on the chessboard as the starting point of the movement, and then look for the position where they can fall in the track. The specific algorithm is as follows: The movable positions of chess pieces are divided into capture movement and non-capture movement. The way of moving without capturing pieces is easy to realize, and only needs to search around one's chess pieces; while the way of moving with capturing pieces is relatively cumbersome. In the initialization chessboard, the positions of the inner track and the outer track are stored in two vectors respectively; after that, first find the own chess piece, and judge whether it is in the inner track or the outer track, or whether it is in the inner track or both. There are two situations when the inner and outer tracks are located: one is on a special point, that is, the inner track intersection or the outer track intersection; the other is not on a special point. If the chess piece is not at a special point, then find the position of the chess piece in the orbit vector, find the opponent’s chess piece upwards or downwards, and then judge whether to go through the arc to get the way; if the chess piece is at a special point, the position of the chess piece is in the orbit vector There will be two times, respectively find the positions of these two times and get the way according to the above method. 5. Evaluation of Chess Game 5.1. Chessboard Analysis The Surakarta board looks complex at first glance, but it is actually symmetrical. If the chessboard is divided into 4 symmetrical regions, the analysis of the whole chessboard can be simplified into a pair of local region analysis. One of the upper right areas is selected for analysis, as shown in Figure 2. Figure 2. Table of points on the chessboard This region contains a total of 9 points and 2 arcs. Since this area is axisymmetric, the 9 points can be divided into 6 types according to their positions in the area, corresponding to points A to F in the figure. In this area, both the outer arc and the inner arc have one intersection with itself, and the intersection points are point A and point D. There are 2 intersections between the outer arc and the inner arc, and the intersection point is the symmetrical point of point B and point B. Since the 4 areas in the chessboard are the same, there are 4 points in the chessboard for points A and D respectively, and 8 points for point B in the chessboard. The role of these points in the game is crucial. Sort according to the importance of chess pieces: B>A=D>E=C>F. 1) Point B is the most aggressive position on the chessboard, and it is also the most important point on the chessboard. Because point B passes through the outer arc counterclockwise to attack the opponent's pieces on the outer arc in the upper left area, and crosses the inner arc clockwise to attack the opponent's pieces on the inner arc in the lower right area. If there is no particle blocking outside the shown area, then the attacking range of this piece can cover the double lines of the outer arc, and the position of point B can also prevent the opponent from going around the inner arc of our side to eat the chess piece on the upper right of our side. 2) Points A and D are second only to point B in importance. The chess piece located at point D can attack the opponent's chess piece on the inner arc of the upper left area through the inner arc clockwise, and can attack the opponent's chess piece on the inner arc of the lower right area through the inner arc counterclockwise. If there is no particle blocking outside the indicated area, the attack range of the particle can cover the entire inner arc. Correspondingly, if the chess piece is positioned at point A, it will have a similar effect on the outer arc. 3) Although point C and point E are not as important as point A and point D, their role in the chess game cannot be ignored. The premise for the above points to exert maximum attack power is that there is no interference from other particles in the shown area. There are our chess pieces at point D and point E, and the chess piece at point D is blocked by the chess piece at point E, and will not be able to attack the opponent's chess piece through the inner arc. Therefore, points C and E can play the role of "advance can be attacked, retreat can be defended". 4) The position of point F is very special, it cannot be attacked by any point, but it cannot attack any other point either. The existence of these similar points does not seem to have much impact on the chess game, but in fact it is not, because it only needs to move one step, and the chess pieces on the point can go to the inner arc and enter the attack state, or the chess pieces on the inner arc will be attacked. Threatened pawns are transferred to a safe state. On the board, the only positions that cannot be attacked are at F, the 4 corners of the largest square on the board. After the above analysis of the key points, the value of each point on the chessboard can be defined. The more important the point, the higher the corresponding point value, and the point with a value of 0 is the only point on the chessboard that cannot be attacked. Then the chessboard value matrix corresponding to the value of each point can be obtained. 5.2. Evaluation Function Factors The setting of the evaluation function not only requires the basic knowledge of chess games, but also uses a series of methods such as direct quantification, model quantification, random evaluation, and fuzzy evaluation. For example, in chess, each chess piece and position can be scored, while for 132 Go, it is necessary to extract the formula and match the pattern. For the analysis of the Surakarta chessboard, the evaluation function in this paper mainly considers the number of chess pieces, moving range, attack range, attack power of pieces, board score and arc value for the black side and the red side respectively. 1) The number of chess pieces The number of chess pieces refers to the number of chess pieces left by all parties in the current situation. Under normal circumstances, whoever has more remaining seeds has a greater advantage. 2) Range of movement The moving range refers to the range in which the pieces can move. There are 8 directions, up, down, left, right, upper left, lower left, upper right, and lower right. Not all directions can be used when moving chess. At this time, it is necessary to combine the move function to judge the direction of the chess piece. 3) Attack range The attack range is related to the movement range. Firstly, the movement range is obtained. The initial value of the attack range is equal to the movement range. If the next piece in the movement range is an enemy piece, the attack range will be increased by 1. 4) Element attack power Piece attack power refers to the ability to capture the opponent's pieces. A major feature of Surakarta chess is that if the enemy captures one of our pieces first, and we have the opportunity to capture the opponent's piece, but if we do not capture, it will become a disadvantage. Under the same conditions It is especially important to play the first move, and strive to capture more chess pieces in each exchange with the opponent, so as to gain an advantage. Whoever has more remaining chess pieces had a greater advantage, which can be effectively evaluated according to this point. Therefore, if you can attack the opponent's pieces, you must attack the opponent's pieces first. In other cases, the attack power of the sub-force needs to be calculated according to the attack range. The relationship between the attack range and the attack power is introduced in detail in the analysis of Surakarta above. Mathematically speaking, the attack power of the sub- force is equal to the sum of the attack range. 5) Disk value The board score is the sum of the values of all the pieces that are still on the board. That is, the value corresponding to the position of the chessboard occupied by the black (red) pieces is added to obtain the situation evaluation value. For the value parameters of the position of the chessboard, please refer to the value matrix of the chessboard. 6) accounted for arc value The occupied arc value refers to the number of occupied arcs. According to the characteristics of Surakarta chess, the more arcs are occupied, the greater the effectiveness of the attack. The formula for calculating the arc value is ArcValue=O*5+E*5 Among them, 0 is the number of arcs occupied by our side (opponent), E is the number of arcs not occupied by the opponent (our side), and the calculated ArcValue is the value of arcs occupied by our side (black side). 5.3. Implementation of the Evaluation Function Considering the above 5 factors comprehensively, we can get the evaluation value of our side (assuming we are black side) situation. The specific implementation algorithm of the evaluation function is as follows. Step1 Traverse each point of the chessboard and calculate the Blacknum value of the number of our chess pieces; Step2 Calculate the BlackMoveRange value of the movement range of our pieces; Step3 Calculates the attack range BlackAttackRange value of our chess piece; Step4 Calculate the attack power of our pieces BlackAttack value; Step5 Calculate our disk value BlackPValue value; Step6 Calculates the value of our accounted arc value BIackArcValue; Step7 Calculate our final evaluation value BlackValue. BlackValue=Blacknum*6+BlackMoveRange*1+BlackAtt ack*2+BlackPValHe*l+BlackArcValue*1. Step8 Similar to our calculation of the other party's evaluation value RedValue. Step9 Calculate Evalue=BlackValue-whiteValue; Step10 IF Evalue>0 means that our side has an advantage at this time Else the other side has an advantage. According to the current chessboard information, combined with the score obtained by the evaluation function, the score value of the current situation that is beneficial to our side is returned through the game tree search to form a move. 6. Game Tree Search At present, there are Alpha-Bate algorithm[2-3] and UCT algorithm which have high search efficiency in Surakarta chess. However, since there are fewer positions available for each move, the Alpha-Beta algorithm will be more accurate when the evaluation function is used well. The Alpha-Bate algorithm is changed from the max-min algorithm. The difference between the two is that the Alpha-Beta algorithm can continuously perform "pruning" to eliminate situations with low value, thereby improving search efficiency. Therefore, the Alpha-Bate pruning algorithm is used in the game tree search of this program, and its pseudocode is as follows: int AlphaBetaSearch(int depth, int alpha, int beta,int color) { if (depth <= 0 ||GameOver()) { return Evalue(); } int count = CreateMoves(color); for (int i = 0; i < count;i++) { Makemove(); value = -AlphaBetaSearch(depth - 1, -beta, -alpha, color ^ 3); Undo(); if (value > alpha) { alpha = value; } if (value >= beta) { break; } } return alpha; } 7. Summary According to the characteristics of Surakarta itself, this 133 paper studies Surakarta from the aspects of board representation, move generation, game evaluation, game tree search and so on. And on this basis, using algorithms such as Alpha-Beta pruning, designed and implemented Surakarta chess game program. After the implementation of this program, it won the second prize at the national level in the computer game competition for college students in China, and won the second prize at the provincial level in the computer game competition for college students in Liaoning Province, which verified the feasibility of the game program algorithm. Acknowledgements Fund support: 2023 College Students Innovation and Entrepreneurship Training Program Project. References [1] Li Dongxuan, Hu Wei, Wang Jingwen. Research on Surakarta Game System Based on Alpha-Beta Algorithm [J]. Intelligent Computer and Application, 2022,12(2):123-125. [2] Che Xiaofei, Xu Yong, Jiang Zonghua. Design and Implementation of Surakarta Chess System [J]. Information and Computer, 2021,33(6):70-73. [3] Zhang Liqun. Realizing the Capturing Algorithm of Surakarta Chess Network Game Platform [J]. Computer Engineering and Application, 2016,52(7):62-66. [4] Li Shuqin, Li Jingbo, Han Yuhua, Tao Situo. Research on Evaluation Function in Surakarta Game System [J]. Journal of Beijing Information Technology University: Natural Science Edition, 2012,27(6):42-4561. [5] Wang Yajie, Qiu Hongkun, Wu Yanyan, Li Fei, Yang Zhoufeng. Research and development of computer games [J]. Journal of Intelligent Systems, 2016,11(6):788-798. [6] Lu Yanhui, Gong Ruimin. Research on Valuation Algorithms and Game Training in Computer Games [J]. Computer Engineering, 2012,38(11):163-166. [7] Wang Jiao, Xu Xinhe. Computer Game: Frontier Field of Artificial Intelligence--National Undergraduate Computer Game Competition [J]. Computer Education, 2012(7): 14-18. [8] Zhang Mingliang, Wu Jun, Li Fanchang. The design of evaluation function of Gobang machine game system [J]. Computer Application, 2012,32(7):1969-19721990.