Browsing by Author "Shan, Yi-Chang"

Now showing 1 - 9 of 9

A FRAMEWORK FOR COMPUTER MAHJONG COMPETITIONS
(2014-03-01)
Shan, Yi-Chang
;
Wei, Ching-Hsuan
;
Lin, Cheng-Hung
;
Wu, I-Chen
;
Chuang, Li-Kai
This contribution specifies a tournament framework for computer Mahjong competitions. A first version is described in Lin, Shan, and Wu (2011). The protocol between the framework and AI programs, is also described in Lin and Wu (2010). (In Chinese) The Appendices are not directly appended to the contribution; they are accessible at http://aigames.nctu.edu.tw/mahjong/protocol.html.
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.
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.
NEWS, INFORMATION, TOURNAMENTS, AND REPORTS
(2011-09-01)
Wu, I-Chen
;
Shan, Yi-Chang
;
Lin, Cheng-Hung
;
Yen, Shi-Jim
;
資訊工程學系
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.
Tournament Framework for Computer Mahjong Competitions
(2011-01-01)
Lin, Cheng-Hung
;
Shan, Yi-Chang
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
For computer Mahjong competitions, this paper proposes and designs the tournament framework and the protocol between the framework and AI programs. The issues of fairness and stability are discussed. The framework has been used in the Mahjong tournament of 2011 TCGA Computer Game Tournaments.
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.