Browsing by Author "Kao, Kuo-Yuan"

Now showing 1 - 9 of 9

Chilled Domineering
(2010-01-01)
Kao, Kuo-Yuan
;
Wu, I-Chen
;
Shan, Yi-Chang
;
Lin, Hung-Hsuan
;
資訊工程學系
This paper introduces a new game named Chilled Domineering, together with its mathematical analysis. Chilled Domineering is modified from the Domineering game by allowing a player placing a 1x1 domino while unable to place a 2x1 domino at a position. After modifying the rule, each position in the game becomes an infinitesimal. Many interesting infinitesimals are found in this new game. This paper calculates the game values of all sub-graphs of 3x3 squares and presents a rule to determine the outcome of any sum of these positions.
Design and Implementation of Chinese Dark Chess Programs
(2015-03-01)
Yen, Shi-Jim
;
Chou, Cheng-Wei
;
Chen, Jr-Chang
;
Wu, I-Chen
;
Kao, Kuo-Yuan
Chinese Dark Chess is an old and very popular game in the Chinese culture sphere. This game is a stochastic game with symmetric hidden information. This paper reviews alpha-beta search with chance nodes and proposes heuristics on Chinese Dark Chess programs. We propose an application of nondeterministic Monte Carlo Tree Search with random nodes for tackling partial observation. The proposed methods were implemented in the program Diablo, which won four Chinese Dark Chess tournaments in TAAI 2011/2012, TCGA 2011/2012 computer game tournaments. Diablo also played hundreds of games with different human players and programs based on alpha-beta search. These results show that the nondeterministic MCTS equipped with our heuristics is promising for Chinese Dark Chess.
Incentive Learning in Monte Carlo Tree Search
(2013-12-01)
Kao, Kuo-Yuan
;
Wu, I-Chen
;
Yen, Shi-Jim
;
Shan, Yi-Chang
;
資訊工程學系
Monte Carlo tree search (MCTS) is a search paradigm that has been remarkably successful in computer games like Go. It uses Monte Carlo simulation to evaluate the values of nodes in a search tree. The node values are then used to select the actions during subsequent simulations. The performance of MCTS heavily depends on the quality of its default policy, which guides the simulations beyond the search tree. In this paper, we propose an MCTS improvement, called incentive learning, which learns the default policy online. This new default policy learning scheme is based on ideas from combinatorial game theory, and hence is particularly useful when the underlying game is a sum of games. To illustrate the efficiency of incentive learning, we describe a game named Heap-Go and present experimental results on the game.
Job-Level Proof Number Search
(2013-03-01)
Wu, I. -Chen
;
Lin, Hung-Hsuan
;
Sun, Der-Johng
;
Kao, Kuo-Yuan
;
Lin, Ping-Hung
This paper introduces an approach, called generic job-level search, to leverage the game-playing programs which are already written and encapsulated as jobs. Such an approach is well suited to a distributed computing environment, since these jobs are allowed to be run by remote processors independently. In this paper, we present and focus on a job-level proof number search (JL-PNS), a kind of generic job-level search for solving computer game search problems, and apply JL-PNS to solving automatically several Connect6 positions, including some difficult openings. This paper also proposes a method of postponed sibling generation to generate nodes smoothly, and some policies, such as virtual win, virtual loss, virtual equivalence, flagging, or hybrids of the above, to expand the nodes. Our experiment compared these policies, and the results showed that the virtual-equivalence policy, together with flagging, performed the best against other policies. In addition, the results also showed that the speedups for solving these positions are 8.58 on average on 16 cores.
NONOGRAM TOURNAMENTS IN TAAI 2011
(2012-06-01)
Sun, Der-Johng
;
Wu, Kuang-che
;
Wu, I-Chen
;
Yen, Shi-Jim
;
Kao, Kuo-Yuan
SELECTION SEARCH FOR MEAN AND TEMPERATURE OF MULTI-BRANCH COMBINATORIAL GAMES
(2012-09-01)
Kao, Kuo-Yuan
;
Wu, I-Chen
;
Shan, Yi-Chang
;
Yen, Shi-Jim
;
資訊工程學系
This paper shows a new algorithm to calculate the mean and temperature of multi-branch combinatorial games. The algorithm expands gradually, one node at a time, the offspring of a game. After each step of expansion, the lower and upper bounds of the mean and temperature of the game are re-calculated. As the expanding process continues, the range between the lower and upper bounds is little by little narrowed. The key feature of the algorithm is its ability to generate a path of which the outcome is most likely to reduce the distance between the lower and upper bounds.
SOLVING 9 LAYER TRIANGULAR NIM
(2010-01-01)
Shan, Yi-Chang
;
Wu, I-Chen
;
Lin, Hung-Hsuan
;
Kao, Kuo-Yuan
;
資訊工程學系
Triangular Nim, one variant of the game Nim, is a common two-player game in Taiwan and China. In the past, Hsu strongly solved 7 layer Triangular Nim while some of the authors recently strongly solved 8 layer Triangular Nim. The latter required 8 gigabytes in memory and 8878 seconds. Using a retrograde method, this paper strongly solves 9 layer Triangular Nim. In our first version, the program requires four terabytes in memory and takes about 129.21 days aggregately. In our second version, improved by removing some rotated and mirrored positions, the program reduces the memory by a factor of 5.86 and the computation time by a factor of 4.38. Our experiment result also shows that the loss rate is only 5.0%. This is also used to help improve the performance.
Solving Nine Layer Triangular Nim
(2012-01-01)
Shan, Yi-Chang
;
Wu, I-Chen
;
Lin, Hung-Hsuan
;
Kao, Kuo-Yuan
;
資訊工程學系
Triangular Nim, one variant of the game Nim, is a common two-player game in Taiwan and China. In the past, Hsu [9] strongly solved seven layer Triangular Nim while some of the authors recently strongly solved eight layer Triangular Nim. The latter required 8 gigabytes in memory and 8,472 seconds. Using a retrograde method, this paper strongly solves nine layer Triangular Nim. In our first version, the program requires four terabytes in memory and takes about 129.21 days aggregately. In our second version, improved by removing some rotated and mirrored positions, the program reduces the memory by a factor of 5.72 and the computation time by a factor of 4.62. Our experiment result also shows that the loss rate is only 5.0%. This is also used to help improve the performance.
XT Domineering: A new combinatorial game
(2012-10-01)
Kao, Kuo-Yuan
;
Wu, I-Chen
;
Shan, Yi-Chang
;
資訊工程學系
;
Department of Computer Science
This paper introduces a new combinatorial game, named XT Domineering, together with its mathematical analysis. XT Domineering is modified from the Domineering game in which 1 x 2 or 2 x 1 dominos are allowed to be placed on empty squares in an m x n board. This new game allows a player to place a 1 x 1 domino on an empty square s while unable to place a 1 x 2 or 2 x 1 domino in the connected group of empty squares that includes s. After modifying the rule, each position in the game becomes an infinitesimal. This paper calculates the game values of all sub-graphs of 3 x 3 squares and shows that each sub-graph of 3 x 3 squares is a linear combination of 8 elementary infinitesimals. These pre-stored game values can be viewed as a knowledge base for playing XT Domineering. Instead of searching the whole game trees, a simple rule for determining the optimal outcome of any sum of these positions is presented. (C) 2011 Elsevier B.V. All rights reserved.