ICGA Journal - Volume 40, issue 3

Authors: Wu, I-Chen

Article Type: Editorial

DOI: 10.3233/ICG-190088

Citation: ICGA Journal, vol. 40, no. 3, pp. 127-128, 2018

Authors: Uiterwijk, Jos W.H.M.

Article Type: Research Article

Abstract: When solving k -in-a-Row games, the Hales–Jewett pairing strategy [Trans. Amer. Math. Soc. 106 (1963 ), 222–229] is a well-known strategy to prove that specific positions are (at most) a draw for the first player. For non-overlapping possible winning lines (groups) it requires two empty squares per group to be marked, i.e., with a coverage ratio of 2.0. In this paper we present a new strategy, called Set Matching .1 1 This work is an extension of research presented at the ACG 2017 conference, which was published [in: Advances in Computer Games: 15th International Conference, ACG …2017 , Springer, 2017 , pp. 38–50]. A matching set consists of a set of nodes (the markers), a set of possible winning lines (the groups), and a coverage set indicating how all groups are covered after every first black move. This strategy needs less than two markers per group. As such it is able to prove positions in k -in-a-Row games to be draws, which cannot be proven using the Hales–Jewett pairing strategy. This work is an extension of research presented at the ACG 2017 conference, which was published [in: Advances in Computer Games: 15th International Conference, ACG 2017 , Springer, 2017 , pp. 38–50]. We show several efficient configurations with their matching sets. These include Cycle Configurations, BiCycle Configurations, and PolyCycle Configurations involving more than two cycles. Depending on configuration, the coverage ratio can be reduced to as low as 1.14. Many examples in the domain of solving k -in-a-Row games are given, including the direct proof (not based on search) that the empty 4 × 4 board is a draw for 4-in-a-Row. To illustrate the power of the method we also show two applications, which prove that 9-in-a-Row and 8-in-a-Row on infinite boards (and hence on any finite board as well) are draws, in a much more rigid way than by case analysis. Show more

DOI: 10.3233/ICG-180053

Citation: ICGA Journal, vol. 40, no. 3, pp. 129-148, 2018

Authors: Lin, Ching-Nung | Chen, Jr-Chang | Yen, Shi-Jim | Chen, Chan-San

Article Type: Research Article

Abstract: The game of Block Go was invented in 2009 as a simplified version of Go. Block Go is played on a 13 × 13 Go board, and each player has nine blocks. This game is suitable for beginners and is popular in most children Go institutes in Taiwan. In this paper, we apply Deep Convolutional Neural Network and Monte Carlo tree search to develop a Block Go program. As a case study, we describe the program named ILEP, which won the Block Go tournament in the Computer Olympiad 2017.

DOI: 10.3233/ICG-180074

Citation: ICGA Journal, vol. 40, no. 3, pp. 149-159, 2018

Authors: van den Herik, H. Jaap

Article Type: Review Article

Abstract: Computer chess has stimulated human imagination over some two hundred and fifty years. In 1769 Baron Wolfgang von Kempelen promised Empress Maria Theresia in public: “I will invent a machine for a more compelling spectacle [than the magnetism tricks by Pelletier] within half a year.” The idea of an intelligent chess machine was born. In 1770 the first demonstration was given. The real development of artificial intelligence (AI) began in 1950 and contains many well-known names, such as Turing and Shannon. One of the first AI research areas was chess. In 1997, a high point was to be reported: …world champion Gary Kasparov had been defeated by Deep Blue. The techniques used included searching, knowledge representation, parallelism, and distributed systems. Adaptivity, machine learning and the recently developed deep learning mechanism were only later on added to the computer chess research techniques. The major breakthrough for games in general (including chess) took place in 2017 when (1) the AlphaGo Zero program defeated the world championship program AlphaGo by 100-0 and (2) the technique of deep learning also proved applicable to chess. In the autumn of 2017, the Stockfish program was beaten by AlphaZero by 28-0 (with 72 draws, resulting in a 64-36 victory). However, the end of the disruptive advance is not yet in reach. In fact, we have just started. The next milestone will be to determine the theoretical game value of chess (won, draw, or lost). This achievement will certainly be followed by other surprising developments. Show more

DOI: 10.3233/ICG-180075

Citation: ICGA Journal, vol. 40, no. 3, pp. 160-176, 2018

Authors: Browne, Cameron | Neller, Todd W. | Chen, Jr-Chang

Article Type: Meeting Report

DOI: 10.3233/ICG-180073

Citation: ICGA Journal, vol. 40, no. 3, pp. 177-181, 2018

Authors: Krabbenbos, Jan | van den Herik, Jaap | Haworth, Guy

Article Type: Meeting Report

DOI: 10.3233/ICG-190080

Citation: ICGA Journal, vol. 40, no. 3, pp. 182-193, 2018

Authors: Krabbenbos, Jan | van den Herik, Jaap | Haworth, Guy

Article Type: Meeting Report

DOI: 10.3233/ICG-190079

Citation: ICGA Journal, vol. 40, no. 3, pp. 194-206, 2018

Authors: Krabbenbos, Jan | van den Herik, Jaap | Haworth, Guy

Article Type: Meeting Report

DOI: 10.3233/ICG-190078

Citation: ICGA Journal, vol. 40, no. 3, pp. 207-210, 2018

Authors: Schneider, Frank

Article Type: Meeting Report

DOI: 10.3233/ICG-190083

Citation: ICGA Journal, vol. 40, no. 3, pp. 211-212, 2018

Authors: Hernandez, Nelson

Article Type: Meeting Report

DOI: 10.3233/ICG-190082

Citation: ICGA Journal, vol. 40, no. 3, pp. 213-215, 2018

Authors: Haworth, Guy | Hernandez, Nelson

Article Type: Meeting Report

DOI: 10.3233/ICG-190081

Citation: ICGA Journal, vol. 40, no. 3, pp. 216-223, 2018

Authors: Gao, Chao | Yan, Siqi | Hayward, Ryan | Müller, Martin

Article Type: Research Article

Abstract: The game of Hex can be played on multiple boardsizes. Transferring neural net knowledge learned on one boardsize to other boardsizes is of interest, since deep neural nets usually require large size of high quality data to train, whereas expert games can be unavailable or difficult to generate. In this paper we investigate neural transfer learning in Hex. We show that when only boardsize independent neurons are used, the resulting neural net obtained from training on one base boardsize can effectively generalize – without fine-tuning – to multiple target boardsizes, larger or smaller. When transferring to larger boardsizes, fine-tuning provides …faster learning and better performance. The strength of the transferable network can be amplified with search: with a single neural net model trained on games from a base boardsize, we obtain players stronger than MoHex 2.0 on multiple target boardsizes. Show more

Keywords: Hex game, deep learning, transfer learning, neural network

DOI: 10.3233/ICG-180055

Citation: ICGA Journal, vol. 40, no. 3, pp. 224-233, 2018

Authors: Bonnet, François

Article Type: Research Article

Abstract: Kriegspiel Hex (aka. DarkHex) is a variant of Hex in which players do not see the opponent’s stones. Due to incomplete information, there exist boards for which neither player has a (pure) winning strategy. The main contribution of this paper is a classification of small boards based on the outcome of the game for optimal players; (i) first player can win, (ii) second player can win, or (iii) neither player can win. For boards without winner, optimal players must follow mixed strategies that maximize their winning probabilities. In this context, solving the game means computing the corresponding Nash Equilibrium (NE). This paper provides …then a brief introduction on how to compute these NEs and some preliminary results are given for the 4 × 3 board. Show more

Keywords: Hex, incomplete information, kriegspiel, Nash equilibrium, pure/mixed strategy

DOI: 10.3233/ICG-180057

Citation: ICGA Journal, vol. 40, no. 3, pp. 234-245, 2018

Authors: Hsu, Wei-Yuan | Ko, Chu-Ling | Hsueh, Chu-Hsuan | Wu, I-Chen

Article Type: Research Article

Abstract: An m n k -game is a kind of k -in-a-row game played on an m × n chess board, where two players alternatively mark empty squares with their own colors and the first one to get k -consecutive marks wins. This paper solves 7,7,5-game and 8,8,5-game as draws. In the proof, we propose some methods based on pairing strategies and potential weights, and then use a program implementing these methods to solve 7,7,5-game in about one minute and 8,8,5-game in about three days.

Keywords: k-in-a-row games, mnk-games, positional games, pairing strategy

DOI: 10.3233/ICG-180061

Citation: ICGA Journal, vol. 40, no. 3, pp. 246-257, 2018

Authors: Chetcuti-Sperandio, Nathalie | Delorme, Fabien | Lagrue, Sylvain

Article Type: Research Article

Abstract: Motus (Lingo) is a TV show based on a word game where each player has to guess a word, of which she knows only the length and the first letter. To do this, the player makes different proposals and she is given some hints based on the positions of the letters. We first show in this article that there is no strategy to find all the words with the available number of proposals. Next, we study different strategies based on aggregate functions and tie-breaks. All these strategies were tested on all the 5 to 10 letter French words, which finally …leads us to discuss the respective performance of these strategies. We show that the criteria of average number of tries used, worst case and number of fails are conflicting. Show more

DOI: 10.3233/ICG-180056

Citation: ICGA Journal, vol. 40, no. 3, pp. 258-268, 2018

Authors: Song, Zhang | Iida, Hiroyuki

Article Type: Research Article

Abstract: Single Conspiracy Number (SCN) is a variant concept of conspiracy number and proof number which indicates the difficulty of a root node changing its MIN/MAX value to a certain score. It makes up the drawbacks of conspiracy number on computing complexity, and can be easily applied into different search frameworks. This paper explores the potential usage of SCN as a long-term position evaluation to understand in-depth game progress patterns. Chinese Chess is chosen as a testbed for this study, whereas a strong AI engine ‘Xiangqi Wizard’ is used. It is implemented with alpha-beta search and modified to produce SCNs during …the search process. Experiments are conducted on different types of positions including tactical positions, drawn positions and opening positions. The experimental results show that SCN is more consistent and accurate for long-term position evaluation than the conventional way using evaluation function values only, and using SCN together with evaluation function values enables us to better understand game progress patterns. Show more

Keywords: Single Conspiracy Number, MIN/MAX value, game progress pattern, Chinese Chess

DOI: 10.3233/ICG-180059

Citation: ICGA Journal, vol. 40, no. 3, pp. 269-280, 2018

Authors: Guei, Hung | Wei, Ting-Han | Wu, I-Chen

Article Type: Research Article

Abstract: 2048-like games are games that have similar properties with 2048, a single-player stochastic sliding puzzle game. 2048-like games are highly suitable for educational purposes due to 2048’s relatively simple rules and its popularity. When using 2048-like games as a tool for machine learning education, these games have the additional benefit of being a well-known topic of research. Numerous machine learning methods have been proposed in the past for 2048, which provides a good opportunity for students to gain first-hand experience in applying these techniques. This paper summarizes the experience of using the game 2584, a 2048-like game, as a pedagogical …tool for teaching reinforcement learning and computer game algorithms in 2017. 2584 is similar to 2048, with the only difference being the tiles values are Fibonacci numbers instead of powers of two. A two-player variant was designed to further teach adversarial game techniques. With a class of 33 undergraduate and graduate students, the average win rate for the single-player version of the 2584 reached 96%. Show more

Keywords: 2048 game, computer science, reinforcement learning, pedagogy, education

DOI: 10.3233/ICG-180062

Citation: ICGA Journal, vol. 40, no. 3, pp. 281-293, 2018

Authors: Matsuzaki, Kiminori | Kitamura, Naoki

Article Type: Research Article

Abstract: Monte-Carlo tree search (MCTS) algorithms play an important role in developing computer players, especially for games for which good evaluation functions are hard to obtain, like Go. The performance of MCTS players is often leveraged in combination with online and/or offline knowledge, despite the lack of game-theoretic guarantees. For the games for which we already have good evaluation functions, the use of evaluation functions in MCTS algorithms achieved a success. However, the effect of evaluation functions on the performance of MCTS algorithms have not been investigated well, especially in terms of the quality of evaluation functions. In this study, we …try to address this issue by using Othello (Reversi) as the target game. Based on the evaluation function used in Zebra, a top-level open-source player, we design 15 variants of evaluation functions and use them in three ways in MCTS algorithms. We conduct a set of experiments exhaustively and analyze the effect of evaluation functions in MCTS algorithms. Show more

Keywords: Monte-Carlo tree search, evaluation functions, Othello (Reversi)

DOI: 10.3233/ICG-180060

Citation: ICGA Journal, vol. 40, no. 3, pp. 294-304, 2018

Authors: Pham, Nguyen Hong

Article Type: Research Article

Abstract: Even both Xiangqi (Chinese chess) and chess are considered to have the same origin and similar playing style, Xiangqi has a very difficult rule set for both understanding and implementing fully to judge games when repetitions happen. This paper introduces an algorithm to implement completely the rule set of Asian Xiangqi Federation (AXF Rules) and some discussions about a few controversial cases of illustrational games.

DOI: 10.3233/ICG-180054

Citation: ICGA Journal, vol. 40, no. 3, pp. 305-317, 2018

Authors: Li, Xiali | Wang, Song | Lv, Zhengyu | Li, Yongji | Wu, Licheng

Article Type: Research Article

Abstract: JIU is a variant of traditional Tibetan chess which is mainly played in Tibetan Qiang Autonomous Prefecture of Ngawa, China. The JIU game process is divided into two sequential stages: preparation and battle. The layout of stones during the preparation stage strongly influences gameplay in the battle stage. Compared with Go, computer game research on JIU is almost non-existent. We collected data for 300 JIU games recorded in Tibetan Qiang Autonomous Prefecture of Ngawa. By analyzing the data, several important strategic shapes were extracted: triangles, trinities, diagonals and squares. A chess-shape pattern-matching method based on matrices was developed to recognize …these shapes. Offensive and defensive strategies based on these shapes were proposed for the preparation stage, being ranked in terms of priority. Moving and capturing strategies based on these shapes were proposed for the battle stage. Human players of various skill levels were invited to play against the software, applying the proposed strategies, to evaluate its performance. The win rates of the software were 2%, 25% and 60%, against top, intermediate, and beginner players. These results demonstrate that the JIU game software using the proposed strategy performs slightly above the beginner level. Show more

Keywords: Computer games, pattern matching, Tibetan JIU, strategy evaluation, chess shape, SGF

DOI: 10.3233/ICG-180058

Citation: ICGA Journal, vol. 40, no. 3, pp. 318-328, 2018