Browsing by Author "Yen, Shi-Jim"

Now showing 1 - 20 of 29

An analysis for strength improvement of an MCTS-based program playing Chinese dark chess
(2016-09-06)
Hsueh, Chu-Hsuan
;
Wu, I-Chen
;
Tseng, Wen-Jie
;
Yen, Shi-Jim
;
Chen, Jr-Chang
Monte Carlo tree search (MCTS) has been successfully applied to many games recently. Since then, many techniques are used to improve the strength of MCTS-based programs. This paper investigates four recent techniques: early playout terminations, implicit minimax backups, quality-based rewards and progressive bias. The strength improvements are analyzed by incorporating the techniques into an MCTS-based program, named DARKKNIGHT, for Chinese Dark Chess. Experimental results showed that the win rates against the original DARKKNIGHT were 60.75%, 71.85%, 59.00%, and 82.10%, respectively for incorporating the four techniques. The results indicated that the improvement by progressive bias was most significant. By incorporating all together, a better win rate of 84.75% was obtained. (C) 2016 Elsevier B.V. All rights reserved.
An Improved Differential Evolution Algorithm with Priority Calculation for Unit Commitment Problem
(2014-01-01)
Yen, Shi-Jim
;
Chen, Wei-Liang
;
Chen, Jr-Chang
;
Hsu, Shun-Chin
;
Wu, I-Chen
Unit Commitment Problem (UCP) is a high-dimensional, discrete and non-linear optimization problem which is complicated so that it is difficult to find the optimal solution. This paper proposes a new method, called improved priority differential evolution (IPDE), based on differential evolution algorithm and priority calculation to solve UCP. We increased the speed of convergence and the accuracy of solution by means of adjusting individual, using penalty function and calculating priority. Compared with other algorithms, IPDE obtains better feasible solutions in different complexity.
DARKKNIGHT WINS CHINESE DARK CHESS TOURNAMENT
(2013-09-01)
Yen, Shi-Jim
;
Chen, Jr-Chang
;
Chen, Bo-Nian
;
Tseng, Wen-Jie
;
資訊工程學系
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.
HAPPYNURI WINS NURIKABE TOURNAMENT
(2010-12-01)
Wu, I-Chen
;
Sun, Der-Johng
;
Yen, Shi-Jim
;
資訊工程學系
;
Department of Computer Science
Human vs. Computer Go: Review and Prospect
(2016-08)
Lee, Chang-Shing
;
Wang, Mei-Hui
;
Yen, Shi-Jim
;
Wei, Ting-Han
;
Wu, I-Chen
The Google DeepMind challenge match in March 2016 was a historic achievement for computer Go development. This article discusses the development of computational intelligence (CI) and its relative strength in comparison with human intelligence for the game of Go. We first summarize the milestones achieved for computer Go from 1998 to 2016. Then, the computer Go programs that have participated in previous IEEE CIS competitions as well as methods and techniques used in Alpha-Go are briefly introduced. Commentaries from three high-level professional Go players on the five AlphaGo versus Lee Sedol games are also included. We conclude that AlphaGo beating Lee Sedol is a huge achievement in artificial intelligence (AI) based largely on CI methods. In the future, powerful computer Go programs such as AlphaGo are expected to be instrumental in promoting Go education and AI real-world applications.
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 ALGORITHMS FOR CONNECT6 OPENING BOOK CONSTRUCTION
(2015-09-01)
Wei, Ting Han
;
Wu, I-Chen
;
Liang, Chao-Chin
;
Chiang, Bing-Tsung
;
Tseng, Wen-Jie
This article investigates the use of job-level (JL) algorithms for Connect6 opening book construction. In the past, JL proof-number search (JL-PNS) was successfully used to solve Connect6 positions. Using JL-PNS, many opening plays that lead to losses can be eliminated from consideration during the opening game. However, it is unclear how the information of unsolved positions can be exploited for opening book construction. For this issue, the current article first proposes four heuristic metrics when using JL-PNS to estimate move quality. The article then proposes a JL upper confidence tree (JL-UCT) algorithm and three heuristic metrics that work with JL-UCT. Of the three, the best way to estimate move quality for JL-UCT is the number of nodes in each candidate move's subtree. In order to compare the heuristic metrics among the two algorithms objectively, we proposed two kinds of measurement methods to analyze the suitability of these metrics when choosing best moves for a set of benchmark positions. Experimental results show that the node count heuristic metric for JL-UCT outperforms all other heuristic metrics, including the four for JL-PNS. We then verify the results by constructing three separate opening books using the top three performing heuristic metrics. Competitive play also shows that the node count heuristic metric for JL-UCT is most suitable among the currently proposed heuristic metrics for Connect6 opening book construction.
Job-Level Algorithms for Connect6 Opening Position Analysis
(2014-01-01)
Wei, Ting-Han
;
Wu, I-Chen
;
Liang, Chao-Chin
;
Chiang, Bing-Tsung
;
Tseng, Wen-Jie
This paper investigates job-level (JL) algorithms to analyze opening positions for Connect6. The opening position analysis is intended for opening book construction, which is not covered by this paper. In the past, JL proof-number search (JL-PNS) was successfully used to solve Connect6 positions. Using JL-PNS, many opening plays that lead to losses can be eliminated from consideration during the opening game. However, it is unclear how the information of unsolved positions can be exploited for opening book construction. For this issue, this paper first proposes four heuristic metrics when using JL-PNS to estimate move quality. This paper then proposes a JL upper confidence tree (JL-UCT) algorithm and some heuristic metrics, one of which is the number of nodes in each candidate move\'s subtree. In order to compare these metrics objectively, we proposed two kinds of measurement methods to analyze the suitability of these metrics when choosing best moves for a set of benchmark positions. The results show that for both metrics this node count heuristic metric for JL-UCT outperforms all the others, including the four for JL-PNS.
LONGCAT WINS MAHJONG TOURNAMENT IN ICGA 2013
(2013-09-01)
Tseng, Wen-Jie
;
Chuang, Li-Kai
;
Wu, I-Chen
;
Lin, Shun-Shii
;
Yen, Shi-Jim
MOBILE6 WINS CONNECT6 TOURNAMENT
(2013-09-01)
Wei, Ting-Han
;
Tseng, Wen-Jie
;
Wu, I-Chen
;
Yen, Shi-Jim
;
資訊工程學系
MODARK WINS CHINESE DARK CHESS TOURNAMENT
(2010-12-01)
Yen, Shi-Jim
;
Chiu, Shih-Yuan
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
MORETHANFIVE WINS CONNECT6 TOURNAMENT
(2010-09-01)
Wu, I-Chen
;
Lin, Ping-Hung
;
Yen, Shi-Jim
;
資訊工程學系
;
Department of Computer Science
NCTU6 wins Connect6 tournament
(2006-09-01)
Wu, I-Chen
;
Yen, Shi-Jim
;
資訊工程學系
;
Department of Computer Science
NEWS, INFORMATION, TOURNAMENTS, AND REPORTS
(2011-09-01)
Wu, I-Chen
;
Shan, Yi-Chang
;
Lin, Cheng-Hung
;
Yen, Shi-Jim
;
資訊工程學系
NEWS, INFORMATION, TOURNAMENTS, AND REPORTS TAAI 2012 COMPUTER GAME TOURNAMENTS
(2014-03-01)
Su, Tsan-Cheng
;
Yen, Shi-Jim
;
Chen, Jr-Chang
;
Wu, I-Chen
;
資訊工程學系
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.
SHIGA WINS CHINESE-CHESS TOURNAMENT
(2011-06-01)
Yen, Shi-Jim
;
Su, Tsan-Cheng
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
Strength Improvement and Analysis for an MCTS-Based Chinese Dark Chess Program
(2015)
Hsueh, Chu-Hsuan
;
Wu, I-Chen
;
Tseng, Wen-Jie
;
Yen, Shi-Jim
;
Chen, Jr-Chang
Monte-Carlo tree search (MCTS) has been successfully applied to Chinese dark chess (CDC). In this paper, we study how to improve and analyze the playing strength of an MCTS-based CDC program, named DARKKNIGHT, which won the CDC tournament in the 17th Computer Olympiad. We incorporate the three recent techniques, early playout terminations, implicit minimax backups, and quality-based rewards, into the program. For early playout terminations, playouts end when reaching states with likely outcomes. Implicit minimax backups use heuristic evaluations to help guide selections of MCTS. Quality-based rewards adjust rewards based on online collected information. Our experiments showed that the win rates against the original DARKKNIGHT were 60.75 %, 70.90 % and 59.00 %, respectively for incorporating the three techniques. By incorporating all together, we obtained a win rate of 76.70 %.