ICGA Journal - Volume 40, issue 4

Authors: Huang, Kuo-Chan | Yeh, Jia-Jun | Huang, Wei-Chiao | Guo, Yan-Rong | Chen, Lung-Pin

Article Type: Research Article

Abstract: This paper presents our experimental studies on improving the speed of solving nonogram puzzles. Our approach is based on the algorithm developed by Wu et al. A puzzle solving program, named LalaFrogKK, implementing the algorithm has won several nonogram tournaments since 2011. The algorithm consists of three major parts: propagation based on line solving, fully probing, and backtracking. Fully probing, running before backtracking, contributes to solving a nonogram puzzle in two ways. The first is to paint more pixels after propagation. The second is testing each unpainted pixel for providing backtracking with more accurate guidance when choosing pixels to …guess. However, we found that different probing sequences can lead to significant differences in the numbers of painted pixels after fully probing. Therefore, in this paper, we investigate into the effects of different fully probing sequences, and propose several new fully probing mechanisms. Experimental results show that the new mechanisms can significantly outperform the original fully probing method. One of the new fully probing mechanisms achieves a speedup of more than two times in solving nonogram puzzles. Show more

Keywords: Nonogram, propagation, fully probing, backtracking

DOI: 10.3233/ICG-180069

Citation: ICGA Journal, vol. 40, no. 4, pp. 397-405, 2018

Authors: Neller, Todd W. | Luo, Ziqian

Article Type: Research Article

Abstract: We describe a means of mixed logical and probabilistic reasoning with knowledge in the popular game Clue. Using pseudo-Boolean constraints we call at-least constraints , we more efficiently represent cardinality constraints on Clue card deal knowledge, perform more general constraint satisfaction in order to determine places where cards provably are or are not, and then employ a WalkSAT-based solution sampling algorithm with a tabu search metaheuristic in order to estimate the probabilities of unknown card places. Finding a tradeoff between WalkSAT-heuristic efficiency in finding solution samples and the sampling bias such a heuristic introduces, we empirically study algorithmic variations in …order to learn how such sampling error may be reduced. Show more

Keywords: Clue, Cluedo, at-least constraints, cardinality constraints, extended clauses, sampling, logical reasoning, probabilistic reasoning, WalkSAT, tabu search

DOI: 10.3233/ICG-180063

Citation: ICGA Journal, vol. 40, no. 4, pp. 406-416, 2018

Authors: Brown, Joseph Alexander

Article Type: Research Article

Abstract: This monograph examines the game pitch document written by Condor, Inc. for Diablo , released in 1996 by Blizzard Entertainment, and places the game in the context of developments of Procedural Content Generation, marketing of Loot Boxes, and the impact of the collectible card game Magic: The Gathering on its development.

Keywords: Diablo, Magic: The Gathering, Procedural Content Generation

DOI: 10.3233/ICG-180066

Citation: ICGA Journal, vol. 40, no. 4, pp. 417-424, 2018

Authors: Uiterwijk, Jos W.H.M.

Article Type: Research Article

Abstract: In this paper we investigate the game of Cram, which is the impartial version of Domineering. We have built Cram endgame databases for all board sizes < 30 squares. We developed a program that fills the databases with their Combinatorial Game Theory (CGT) values. Since Cram is an impartial game, all CGT values for Cram positions are so-called nimbers, indicated by ∗ n . The nimber value of a position not only directly determines the game-theoretic value (first- or second-player win), but also provides an optimal playing strategy. When analyzing the resulting databases we observed the following …facts. Firstly we confirmed that the CGT values of all investigated empty boards are in agreement with results published in the literature. Since the value of an empty board depends completely on the values of many partially filled positions in the database, this is a strong indication that our process of filling the database with CGT values is correct. Secondly, although the series of values for 2 × n boards is completely regular, namely a value ∗ 0 for n being even and ∗ 1 for n being odd, this was not proven formally so far. We were able to provide such a proof. We also investigated the databases for their contents. So far we encountered nimber values up to ∗ 11 among single-fragment Cram positions. It appears that for a ∗ n value to occur a board size with ≈ 3 n squares is needed, some more for very tall boards (1 × n ), some less for wider boards (4 × n ). So far no single-fragment Cram positions were encountered with nimber values ⩾ ∗ 12 , although we show a construction of larger multi-fragment positions with nimber values from ∗ 12 up to ∗ 15 . In a preliminary experiment we incorporated the CGT endgame databases constructed into a simple alpha-beta solver for the game. Results revealed a large improvement in solving power. Show more

DOI: 10.3233/ICG-180064

Citation: ICGA Journal, vol. 40, no. 4, pp. 425-437, 2018

Authors: Chen, Yen-Chi | Yeh, Jia-Fong | Lin, Shun-Shii

Article Type: Research Article

Abstract: In this paper, we present the techniques, such as bitboard, iterative-deepening aspiration search algorithm, endgame tablebase, used in our Surakarta program Fuchou. A bijective function similar to Schadd’s is developed to map a Surakarta board position to a unique address of the endgame tablebase. The function is one-to-one and onto and can be computed very quickly using some techniques compared to conventional methods. We have implemented it on our Surakarta program FuChou. Experimental results show that we have gotten advantages of speedup as well as accuracy on the endgame boards.

Keywords: endgame tablebase, alpha-beta search, bitboard, iterative-deepening aspiration search, computer games, Surakarta

DOI: 10.3233/ICG-180071

Citation: ICGA Journal, vol. 40, no. 4, pp. 438-449, 2018

Authors: Ito, Takeshi

Article Type: Research Article

Abstract: In games with a large number of legal yet complicated moves like Shogi, the number of candidate moves that can be performed are considerably large especially for beginners; therefore, often, beginners encounter situations where they cannot select the next move to play. The hint function in the existing Shogi programs provides support by directly showing candidate moves. However, such direct hints may not only deprive the pleasure of playing the game intellectually, but also instigate players to avoid thinking about the next steps entirely. Therefore, a method to provide indirect hints is required, which retains the objective and fun of …the game. Thus, in this study, a method that presents the future position in the game, which is generated by self-play of Shogi AI, is proposed. In particular, the proposed system displays the next position, position after 5 steps, or position after 9 steps in advance using the Shogi AI. Then, the learning effect based on the evaluation experiment was analyzed and discussed. Show more

Keywords: Assistance dilemma, learning support system, future position, indirect instruction, computer Shogi

DOI: 10.3233/ICG-180068

Citation: ICGA Journal, vol. 40, no. 4, pp. 450-459, 2018

Authors: Chen, Chih-Hung | Wu, Wei-Lin | Chen, Yu-Heng | Lin, Shun-Shii

Article Type: Research Article

Abstract: The average reward problem in the traditional Monte-Carlo tree search algorithms troubles the sudden death games for a long time, because of the average reward criterion will reduce the probability of a deterministic result. But this does not bother the non-sudden death games, such as Go, which can focus only on higher win rates rather than higher scores. In this work, we propose the miniMax-Monte-Carlo tree search with depth rewards to Outer-Open Gomoku (a variant of Gomoku) to discover a forced win/lose without any human knowledge, evaluation function, or pre-training. And it can solve not only the average reward problem …but also the inaccurate win-rate problem in deep playout simulation in sudden death games. Finally, we propose a new integrated framework named BBQ (Big, Best, Quick win) MCTS for improving the performance of traditional MCTS. Show more

Keywords: Monte-Carlo tree search, miniMax search, depth rewards, sudden death games, Outer-Open Gomoku, Tic-Tac-Toe

DOI: 10.3233/ICG-180065

Citation: ICGA Journal, vol. 40, no. 4, pp. 460-470, 2018

Authors: Chen, Jr-Chang | Lin, Ting-Yu | Hsu, Tsan-Sheng

Article Type: Research Article

Abstract: The accurate measurement for opening positions in a game is an important issue in computer games. Evaluation functions used in game-playing programs are designed for the middlegame, and may not suitable for the opening phase. This paper proposes a method, named the number of effective moves , which is composed by a set of opening heuristics. It can be seen as an evaluation function for the opening. In addition, we implement a GUI tool based on an opening book to facilitate adjustments. The tool helps to discover new opening lines in practice and to assist move selection in the opening.

Keywords: The number of effective moves, evaluation functions, Chinese chess

DOI: 10.3233/ICG-180070

Citation: ICGA Journal, vol. 40, no. 4, pp. 471-478, 2018