ICGA Journal - Volume 37, issue 3

Article Type: Other

DOI: 10.3233/ICG-2014-37301

Citation: ICGA Journal, vol. 37, no. 3, pp. 129-130, 2014

Authors: King, David W. | Peterson, Gilbert L.

Article Type: Research Article

Abstract: Epaminondas is a two-person, zero-sum strategy game that combines long-term strategic play with highly tactical move sequences. The game has two unique features that make it stand out from other games. The first feature is the creation of phalanxes , which are groups of pieces that can move as a whole unit. As the number of pieces in a phalanx increases, the mobility and capturing power of the phalanx also increases. The second feature differs from many other strategy games: when a player makes a crossing , a winning move in the game, the second player has an opportunity …to respond. This paper presents strategies and heuristics used in a Min-Max Alpha-Beta agent that plays at a novice level. Furthermore, it defines the state-space and game-tree complexities for Epaminondas . Finally, a new version of MCTS is implemented that uses the Alpha-Beta heuristic function during node selection to guide MCTS to more promising areas of the search tree. Additionally, in an effort to overcome the MCTS tactical weakness, the MCTS player implements the Alpha-Beta search once the game reaches 15 turns. Results show that the added heuristic value and the switch to Alpha-Beta for endgame play, positively impact the performance of MCTS, surpassing novice Alpha-Beta win ratios at certain time intervals. Show more

DOI: 10.3233/ICG-2014-37302

Citation: ICGA Journal, vol. 37, no. 3, pp. 131-143, 2014

Authors: Uiterwijk, Jos W.H.M.

Article Type: Research Article

Abstract: This is Part 2 of three articles on the impact of safe moves on perfectly solving Domineering boards. In Part 1 (Uiterwijk, 2014b) we provided an exact analysis of 1-step safe moves obtainable in the very first phase of a Domineering game. In this part we show that, provided the board is wide or high enough, a player may obtain additional (multi-step) safe moves. Such multi-step safe moves can be divided into two categories. The first category contains safe moves resulting from making double-threats, of which only one can be prevented, the so-called 2-step safe moves. …Their number depends on the exact dimensions of the board and on the counter strategy used by the opponent. The second category contains so-called x-step safe moves. We show that threatening to play extended double-destroying (xDD) moves possibly leads to an additional x-step safe move. Finally, we show how these two categories of multi-step safe moves should be combined with 1-step safe moves in order to achieve more accurate lower bounds for the number of safe moves obtainable by a player. We incorporated the findings of this extended analysis in our rules for perfectly solving Domineering boards. Using these enhanced rules, 35 more Domineering boards have been perfectly solved, 20 being a win for Vertical, 15 for Horizontal. Among the newly solved boards are 4 boards for which the game-theoretic values were not known so far, i.e., 6 × 19, 10 × 15, 14 × 15, and 18 × 15, all being a win for Vertical. Show more

DOI: 10.3233/ICG-2014-37303

Citation: ICGA Journal, vol. 37, no. 3, pp. 144-160, 2014

Authors: Browne, Cameron

Article Type: Research Article

Abstract: Artificial intelligence (AI) applications typically involve encoding expert knowledge in machine form to find optimal solutions for a given problem. However, this paper deals with the opposite process of extracting new and human-comprehensible insights from emergent AI behaviour. Some examples of useful game-related insights drawn from observing AI players in action are presented.

DOI: 10.3233/ICG-2014-37304

Citation: ICGA Journal, vol. 37, no. 3, pp. 161-165, 2014

Authors: Haworth, G.McC.

Article Type: Research Article

DOI: 10.3233/ICG-2014-37305

Citation: ICGA Journal, vol. 37, no. 3, pp. 166-168, 2014

Authors: Posthoff, Christian | Steinbach, Bernd

Article Type: Research Article

Abstract: In this note we use Boolean models to generate new results in Combinatorics. On the one hand, the new results answer actual questions which have not been solved so far. On the other hand, the new results can immediately be useful for future applications. We emphasize a new sequence of numbers which we call, due to the analyzed problem, the sequence of Bishop Numbers . The study of the methodology applied leads to a new fruitful observation. Any problem that can be converted into a Boolean model can be solved for a broad range of parameters in a constructive …way. Thus, it is not only known that there are solutions, the results will be fully available as well. This relates particularly to all constraint-related problems, even when the Boolean models are quite complex. Show more

DOI: 10.3233/ICG-2014-37306

Citation: ICGA Journal, vol. 37, no. 3, pp. 169-177, 2014

Authors: Hyatt, Robert M.

Article Type: Research Article

Abstract: The problem of short principal variations (PVs) due to exact transposition / refutation (ttable) matches has been discussed frequently over the past 50 plus years. Richard Greenblatt introduced the idea of a transposition/refutation table in his 1967 article on Mac Hack, and the topic has since been discussed many times (CCC11, Greenblatt et al., 1967, Slate, 1977). The issue of exact score hash matches creates several problems that have led to draconian solutions that are generally worse than the original problem. For example, the most popular solution is not allowing exact hash matches on PV nodes, which does avoid …the short PV problem, but at a computationally expensive cost. We have already reached this position once, and completed a full search. We now have reached it again, but we choose to repeat the search to extract the remainder of the PV, rather than using the ttable information to avoid this search completely. The author describes a simple and effective solution that all but eliminates this problem with no measurable computational cost or loss of efficiency. Show more

DOI: 10.3233/ICG-2014-37307

Citation: ICGA Journal, vol. 37, no. 3, pp. 178-181, 2014

Authors: Hartmann, Dap

Article Type: Book Review

DOI: 10.3233/ICG-2014-37308

Citation: ICGA Journal, vol. 37, no. 3, pp. 182-183, 2014

Article Type: Other

DOI: 10.3233/ICG-2014-37309

Citation: ICGA Journal, vol. 37, no. 3, pp. 184-184, 2014

Authors: Yeh, Kun-Hao | Liang, Chao-Chin | Wu, Kuang-che | Wu, I-Chen

Article Type: Research Article

DOI: 10.3233/ICG-2014-37310

Citation: ICGA Journal, vol. 37, no. 3, pp. 185-186, 2014