Browsing by Author "Chen, Jr-Chang"

Now showing 1 - 17 of 17

AlphaZero for a Non-deterministic Game
(2018-01-01)
Hsueh, Chu-Hsuan
;
Wu, I-Chen
;
Chen, Jr-Chang
;
Hsu, Tsan-sheng
;
資訊工程學系
The AlphaZero algorithm, developed by DeepMind, achieved superhuman levels of play in the games of chess, shogi, and Go, by learning without domain-specific knowledge except game rules. This paper investigates whether the algorithm can also learn theoretical values and optimal plays for non-deterministic games. Since the theoretical values of such games are expected win rates, not a simple win, loss, or draw, it is worthy investigating the ability of the AlphaZero algorithm to approximate expected win rates of positions. This paper also studies how the algorithm is influenced by a set of hyper-parameters. The tested non-deterministic game is a reduced and solved version of Chinese dark chess (CDC), called 2x4 CDC. The experiments show that the AlphaZero algorithm converges nearly to the theoretical values and the optimal plays in many of the settings of the hyper-parameters. To our knowledge, this is the first research paper that applies the AlphaZero algorithm to non-deterministic games.
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.
An investigation of strength analysis metrics for game-playing programs: A case study in Chinese dark chess
(2018-01-01)
Hsueh, Chu-Hsuan
;
Wu, I-Chen
;
Hsu, Tsan-Sheng
;
Chen, Jr-Chang
;
資訊工程學系
For developers of game-playing programs, it is an important but non-trivial task to measure the strengths of the programs, especially with respect to the theoretically optimal players. The optimal players are hard to obtain in practice since many real-world games are too hard to solve entirely. In this paper, a reduced version of Chinese dark chess (CDC), 2 x 4 CDC, which has been solved, is used as a testbed to analyze the strengths of game-playing programs for CDC, a non-deterministic game. Absolute strength is then defined to be the win rates against the optimal player. Experiment results show that win rates against designated baseline programs are a good metric, since these win rates are highly correlated to absolute strengths. The stronger the designated baseline programs are, the higher the correlations of win rates are to the absolute strengths. In addition, it is shown that prediction rates and mean squared errors are other good metrics and have high correlations to the absolute strengths. The experiment results also show that the win rates obtained in 2 x 4 CDC have a high correlation to those in the original 4 x 8 CDC, except for those using the technique of progressive bias.
Chimo wins Chinese chess tournament
(2018-01-01)
Tseng, Wen-Jie
;
Chen, Jr-Chang
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
Comparison Training for Computer Chinese Chess
(2020-06-01)
Chen, Jr-Chang
;
Tseng, Wen-Jie
;
Wu, I-Chen
;
Wei, Ting-Han
;
資訊工程學系
This paper describes the application of modified comparison training for automatic feature weight tuning. The final objective is to improve the evaluation functions used in Chinese chess programs. First, we apply n-tuple networks to extract features. N-tuple networks require very little expert knowledge through its large numbers of features, while simultaneously allowing easy access. Second, we propose a modified comparison training into which tapered eval is incorporated. Experiments show that with the same features and the same Chinese chess program, the automatically tuned feature weights achieved a win rate of 86.58% against the hand-tuned features. The above trained version was then improved by adding additional features, most importantly n-tuple features. This improved version achieved a win rate of 81.65% against the trained version without additional features.
DARKKNIGHT WINS CHINESE DARK CHESS TOURNAMENT
(2013-09-01)
Yen, Shi-Jim
;
Chen, Jr-Chang
;
Chen, Bo-Nian
;
Tseng, Wen-Jie
;
資訊工程學系
DarkKnight Wins Chinese Dark Chess Tournament
(2017-01-01)
Tseng, Wen-Jie
;
Chen, Jr-Chang
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
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.
HAPPYNOGO WINS NOGO TOURNAMENT
(2013-09-01)
Tseng, Wen-Jie
;
Chen, Jr-Chang
;
She, Pohsuan
;
Wu, I-Chen
;
資訊工程學系
Job-Level Alpha-Beta Search
(2015-03-01)
Chen, Jr-Chang
;
Wu, I-Chen
;
Tseng, Wen-Jie
;
Lin, Bo-Han
;
Chang, Chia-Hui
An approach called generic job-level (JL) search was proposed to solve computer game applications by dispatching jobs to remote workers for parallel processing. This paper applies JL search to alpha-beta search, and proposes a JL alpha-beta search (JL-ABS) algorithm based on a best-first search version of MTD(f). The JL-ABS algorithm is demonstrated by using it in an opening book analysis for Chinese chess. The experimental results demonstrated that JL-ABS reached a speed-up of 10.69 when using 16 workers in the JL system.
Merging Metrics of Special Rules in Chinese Chess Endgame Databases
(2019-01-01)
Tseng, Wen-Jie
;
Chen, Jr-Chang
;
Wu, I-Chen
;
交大名義發表
;
資訊工程學系
Perpetual check and perpetual chase are two special rules in the endgame phase of Chinese chess. Two metrics, distance-to-check and distance-to-chase, respectively record the distances measured in plies from the current position to the positions where the two rules apply in endgame databases. In the past, the two metrics are separately recorded at different levels in the databases. However, the endgame strategy is not efficient if the distances of the two metrics are not compared. Moreover, the more the number of levels is, the bigger the database is. In this paper, we modify retrograde analysis, an algorithm to build endgame databases, to merge the two metrics for special rules. The experiments show that the endgame strategy becomes efficient and the sizes of endgame databases are reduced as well.
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
;
資訊工程學系
On solving the 7,7,5-game and the 8,8,5-game
(2020-05-02)
Hsu, Wei-Yuan
;
Ko, Chu-Ling
;
Chen, Jr-Chang
;
Wei, Ting-Han
;
Hsueh, Chu-Hsuan
An mnk-game is a kind of k-in-a-row game played on an m x nboard, where two players alternatively mark empty squares with their own colors and the first player who gets k-consecutive marks (horizontally, vertically, or diagonally) wins. In this paper, we present an AND/OR search tree algorithm specifically for proving mnk-games. We first propose three novel methods to reduce the branching factor of AND/OR search trees. We also propose a new method to find pairing strategies, which further accelerate the proof of mnk-games. The combined methods drastically speed up the proof for the 7,7,5-game, which is solved in 2.5 seconds. Moreover, this paper is the first to solve the 8,8,5-game, which is proven as a draw within 17.4 hours. (C) 2020 Elsevier B.V. All rights reserved.
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 %.
TCGA 2013 COMPUTER GAME TOURNAMENT REPORT
(2013-09-01)
Tseng, Wen-Jie
;
Chen, Jr-Chang
;
Chen, Lung-Ping
;
Yen, Shi-Jim
;
Wu, I-Chen
TCGA 2014 COMPUTER GAME TOURNAMENT
(2014-12-01)
Lin, Shun-Shii
;
Chen, Chih-Hung
;
Hsu, Shun-Chin
;
Wu, I-Chen
;
Yen, Shi-Jim