Browsing by Author "Hsueh, Chu-Hsuan"

Now showing 1 - 12 of 12

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 Agent for EinStein Wurfelt Nicht! Using N-Tuple Networks
(2017-01-01)
Chu, Yeong-Jia Roger
;
Chen, Yuan-Hao
;
Hsueh, Chu-Hsuan
;
Wu, I-Chen
;
資訊工程學系
This paper describes the implementation of an agent that plays EinStein wurfelt nicht!. The agent is based on the common Monte-Carlo tree search (MCTS) which is especially good at dealing with the randomness in a game. For the agent, this paper proposes to use n-tuple networks trained by Monte-Carlo learning. In the agent, the trained n-tuple network is used together with MCTS by the following three approaches: progressive bias, prior knowledge and c-greedy. The experimental results show that epsilon-greedy improved the playing strength the most, which obtained a win rate of 61.05% against the baseline agent. By combining all three approaches, the win rate increased a little to 62.25%. And the enhanced agent also won the first place in the EinStein wurfelt nicht! tournament in Computer Olympiad 2017.
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 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.
Applying Hueristic Algorithms to Portfolio Selection Problem
(2015)
Kang, Po-Ya
;
Wu, I-Chen
;
Hsueh, Chu-Hsuan
;
資訊工程學系
;
Department of Computer Science
In this paper, we solve the portfolio selection problem. In our approach, we first propose a modified immune algorithm (IA) to reuse the memory cells we got in earlier stages, so that more information can be utilized in the next stages. Our experimental results show that the modified IA can successfully obtain significantly higher return than genetic algorithm (GA) and particle swarm optimization (PSO). Second, we. also propose a hybrid of IA and PSO (IA-PSO), and a hybrid of GA and PSO. From our experiments, the hybrid IA-PSO maintains the high return while becoming more stable.
Belief-state Monte-Carlo Tree Search for Phantom Games
(2015)
Wang, Jiao
;
Zhu, Tan
;
Li, Hongye
;
Hsueh, Chu-Hsuan
;
Wu, I-Chen
Playing games with imperfect information is a very challenging issue in AI field due to its high complexity. Phantom game is a kind of such games, which usually has a large game-tree complexity and has little research achievements until now. In Phantom games, rational human players commonly select actions according to their beliefs in the game, which can be represented as a concept of belie f-state. To the best of our knowledge, our paper is the first article to incorporate belief-states in the Monte-Carlo Tree Search, and the proposed algorithm is named BS-MCTS (Belief-state Monte-Carlo Tree Search). In BS-MCTS, a belief-state tree, in which each node is a belief-state, is constructed and the search procedure is in accordance with beliefs updated by heuristic search information. We also present two novel implementations in the belief learning, that are Opponent Guessing and Opponent Predicting, concerning the probability on the possible states and on future actions of the opponent respectively. To prove the effectiveness of our algorithm, BS-MCTS is applied to Phantom Tic-Tac-Toe and Phantom Go against other Monte-Carlo methods. The experimental results demonstrate that our method is outstanding and advanced. Moreover, based on BS-MCTS, our Phantom Go program had consecutively won three championships in Chinese National Tournaments.
Combining Deep Deterministic Policy Gradient with Cross-Entropy Method
(2019-01-01)
Lai, Tung-Yi
;
Hsueh, Chu-Hsuan
;
Lin, You-Hsuan
;
Chu, Yeong-Jia Roger
;
Hsueh, Bo-Yang
This paper proposes a deep reinforcement learning algorithm for solving robotic tasks, such as grasping objects. We propose in this paper a combination of cross-entropy optimization (CE) with deep deterministic policy gradient (DDPG). More specifically, where in the CE method, we first sample from a Gaussian distribution with zero as its initial mean, we now set the initial mean to DDPG's output instead. The resulting algorithm is referred to as the DDPG-CE method. Next, to negate the effects of bad samples, we improve on DDPG-CE by substituting the CE component with a weighted CE method, resulting in the DDPG-WCE algorithm. Experiments show that DDPG-WCE achieves a higher success rate on grasping previously unseen objects, than other approaches, such as supervised learning, DDPG, CE, and DDPG-CE.
EWIN wins EinStein Wurfelt Nicht! tournament
(2019-01-01)
Hsueh, Chu-Hsuan
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
Multistage Temporal Difference Learning for 2048-Like Games
(2017-12-01)
Yeh, Kun-Hao
;
Wu, I-Chen
;
Hsueh, Chu-Hsuan
;
Chang, Chia-Chuan
;
Liang, Chao-Chin
Szubert and Jaskowski successfully used temporal difference (TD) learning together with n-tuple networks for playing the game 2048. However, we observed a phenomenon that the programs based on TD learning still hardly reach large tiles. In this paper, we propose multistage TD (MS-TD) learning, a kind of hierarchical reinforcement learning method, to effectively improve the performance for the rates of reaching large tiles, which are good metrics to analyze the strength of 2048 programs. Our experiments showed significant improvements over the one without using MS-TD learning. Namely, using 3-ply expectimax search, the program with MS-TD learning reached 32768-tiles with a rate of 18.31%, while the one with TD learning did not reach any. After further tuned, our 2048 program reached 32768-tiles with a rate of 31.75% in 10,000 games, and one among these games even reached a 65536-tiles, which is the first ever reaching a 65536-tiles to our knowledge. In addition, MS-TD learning method can be easily applied to other 2048-like games, such as Threes. Based on MS-TD learning, our experiments for Threes also demonstrated similar performance improvement, where the program with MS-TD learning reached 6144-tiles with a rate of 7.83%, while the one with TD learning only reached 0.45%.
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.
Solving 7,7,5-game and 8,8,5-game
(2018-01-01)
Hsu, Wei-Yuan
;
Ko, Chu-Ling
;
Hsueh, Chu-Hsuan
;
Wu, I-Chen
;
資訊工程學系
An mnk-game is a kind of k-in-a-row game played on an m x n chess board, where two players alternatively mark empty squares with their own colors and the first one to get k-consecutive marks wins. This paper solves 7,7,5-game and 8,8,5-game as draws. In the proof, we propose some methods based on pairing strategies and potential weights, and then use a program implementing these methods to solve 7,7,5-game in about one minute and 8,8,5-game in about three days.
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 %.