ICGA Journal - Volume 34, issue 4 - Journals

Show:

results per page

Table of Contents / Editorial

Article Type: Other

DOI: 10.3233/ICG-2011-34401

Citation: ICGA Journal, vol. 34, no. 4, pp. 177-178, 2011

Get PDF

On Games with Random-Turn Order and Monte Carlo Perfectness

Authors: Althöfer, Ingo

Article Type: Research Article

Abstract: In a game, pure Monte Carlo search with parameter T means that for each feasible move T random games are generated. The move with the best average score is played. We call a game “Monte Carlo perfect” when this straightforward procedure converges to perfect play for each position, when T goes to infinity. Most popular games like Go, Hex, and Amazons are NOT Monte Carlo perfect. In this paper, two-player zero-sum games are investigated where the turn-order is random: always a fair coin flip decides which player acts on the next move. A whole class of …such random-turn games is proven to be Monte Carlo perfect. The result and generalisations are discussed, with example games ranging from very abstract to very concrete.2 Show more

DOI: 10.3233/ICG-2011-34402

Citation: ICGA Journal, vol. 34, no. 4, pp. 179-190, 2011

Price: EUR 27.50

An Efficient Approach to Solving the Minimum Sudoku Problem

Authors: Lin, Hung-Hsuan | Wu, I-Chen

Article Type: Research Article

Abstract: Since Sudoku was invented, it has been an open problem to find the minimum-clue Sudoku puzzles, also commonly called the minimum Sudoku problem. Solving the problem can be done by checking 5,472,730,538 essentially different Sudoku grids independently or in parallel. In the past, the program CHECKER , written by McGuire, required about 311 thousand years on one-core CPU to check these grids completely, according to our experimental analysis. This paper is to propose a more efficient approach to solving this problem. We design a new algorithm, named disjoint minimal unavoidable set (DMUS) algorithm, to help solve the minimum Sudoku problem …more efficiently. After incorporating the algorithm into the program and further tuning the program code, our experiments showed that the performance was greatly improved by a factor of 128.67. Hence, it is estimated that it only takes about 2417 years to solve the problem. Thus, it becomes feasible and optimistic to solve this problem by using a volunteer computing system, such as BOINC. Show more

DOI: 10.3233/ICG-2011-34403

Citation: ICGA Journal, vol. 34, no. 4, pp. 191-208, 2011

Price: EUR 27.50

Real-Time Search Method in Nondeterministic Game — Ms. Pac-Man

Authors: Gan, Xiaocong | Bao, Yun | Han, Zhangang

Article Type: Research Article

Abstract: A search-based method is proposed to control the real-time and nondeterministic game Ms. Pac-Man automatically. First, a detailed survey is given, including (1) some details of the game, (2) a literature review of more than 20 works from the competition organized by Simon M. Lucas and (3) some other papers. Then we propose an image recognition method for the game that can recognize partially occluded objects effectively by using corner pixels . Based on the recognition results, we use the game-tree search algorithm to make the decisions. Heuristic rules are carefully designed to ensure that the search tree can …be expanded sufficiently deep within a limited time. A vector is evaluated for each node in the tree. This vector facilitates the implementation of hand-coded rules. We achieve an average score of 67,602 and a high score of 106,980, both remarkably higher than previous works. Show more

DOI: 10.3233/ICG-2011-34404

Citation: ICGA Journal, vol. 34, no. 4, pp. 209-222, 2011

Price: EUR 27.50

Ricochet Robots is Solved

Authors: Chen, Yibo | Oon, Wee-Chong | Zhu, Wenbin

Article Type: Research Article

Abstract: Ricochet Robots is a puzzle game published by Rio Grande Games and designed by Alex Randolph. Given a starting position with four robots on a board and a target space, the objective is to move the active robot to the target space in as few moves as possible. In this note, we announce that Ricochet Robots is strongly solved, i.e., a solution with the minimum number of moves has been computed for all possible starting positions. We solved the game using a complete retrograde analysis on all one trillion (1012 ) positions on a multi-core personal computer over a …period of about a week. Show more

DOI: 10.3233/ICG-2011-34405

Citation: ICGA Journal, vol. 34, no. 4, pp. 223-226, 2011

Price: EUR 27.50