Browsing by Author "Wu, I-Chen"

Now showing 1 - 20 of 104

2017 "CITIC Securities Cup" - The 1st World AI Go Open
(2018-01-01)
Shih, Chung-Chin
;
Liu, An-Jen
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
2048-like games for teaching reinforcement learning
(2020-01-01)
Guei, Hung
;
Wei, Ting-Han
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
2048-like games are a family of single-player stochastic puzzle games, which consist of sliding numbered-tiles that combine to form tiles with larger numbers. Notable examples of games in this family include Threes!, 2048, and 2584. 2048-like games are highly suitable for educational purposes due to their simplicity and popularity. Numerous machine learning methods have been proposed to play 2048-like games; the application of these techniques can help students gain first-hand experience in implementing machine learning algorithms. This paper proposes a guideline for using 2048-like games for teaching reinforcement learning and computer game algorithms, while also summarizing our experience of using 2584 and Threes! as pedagogical tools that were well received judging by student feedback in two graduate level courses.
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.
A new family of k-in-a-row games
(2006)
Wu, I-Chen
;
Huang, Dei-Yen
;
資訊工程學系
;
Department of Computer Science
This paper contains three contributions. First, it introduces a new family of k-in-a-row games, Connect (M,n,k,p,q). In Connect(m,n,k, p,q), two players alternately place p stones on an m x n board in each turn, except for the start when the first player places q stones at her(1) first move. The player who first obtains k consecutive stones of her own first wins. The traditional game five-in-a-row, also called Go-Moku, in the free style is Connect (15,15,5, 1, 1). For brevity, Connect(k,p,q) denotes the game Connect (infinity, infinity, k,p,q), played on infinite boards. Second, this paper analyzes the characteristics of these games, especially for the fairness. In the analysis of fairness, we first exclude the ones which are apparently unfair or solved. Then, for the rest of games, we argue that p = 2q is a necessary condition for fairness in the sense that one player always has q more stones than the other after making a move. Among these games, Connect(6,2,1) is most interesting to this paper and is named Connect6. Third, this paper proposes a threat-based strategy to play Connect(k, p,q) games and implements a computer program for Connect6, based on the strategy. In addition, this paper also illustrates a new null-move search approach by solving Connect (6, 2, 3) where the first player wins. The result also hints that for Connect6 the second player usually should not place the initial two stones far away from the first stone played by the first player.
A New MCTS-Based Algorithm for Multi-Objective Flexible Job Shop Scheduling Problem
(2015)
Chou, Jen-Jai
;
Liang, Chao-Chin
;
Wu, Hung-Chun
;
Wu, I-Chen
;
Wu, Tung-Ying
Multi-objective flexible job-shop scheduling problem (MO-FJSP) is very important in both fields of production management and combinatorial optimization. Wu et al. proposed a Monte-Carlo Tree Search (MCTS) to solve MO-FJSP and successfully improved the performance of MCTS to find 17 Pareto solutions: 4 of Kacem 4x5, 3 of 10x7, 4 of 8x8, 4 of 10x10, and 2 of 15x10. This paper proposes a new MCTS-based algorithm for MO-FJSP problem by modifying their algorithm. Our experimental results show that our new algorithm significantly outperforms their algorithm for large problems, especially for Kacem 15x10. This shows that the new algorithm tends to have better potential of solving harder MO-FJSP problems.
A portable AWT/Swing architecture for Java game development
(2007-06-01)
Wang, Yi-Hsien
;
Wu, I-Chen
;
Jiang, Jyh-Yaw
;
資訊工程學系
;
Department of Computer Science
Recently, the performance of Java platforms has been greatly improved to satisfy the requirements for game development. However, the rendering performance of Java 1.1, which is still used by about one-third of current Web browser users, is not sufficient for high-profile games. Therefore, practically, Java game developers, especially those who use applets, have to take this into consideration in most environments. In order to solve the above problems, this paper proposes a portable window toolkit architecture called the CYC Window Toolkit (CWT) with the ability to: (1) reach high rendering performance particularly in Java 1.1 applications and applets when using DirectX to render widgets in CWT; (2) support AWT/Swing compatible widgets, so hence the CWT can be easily applied to existing Java games; (3) define a general architecture that supports multiple graphics libraries such as AWT, DirectX and OpenGL, multiple virtual machines such as Java VM and NET CLR, and multiple operating systems (OSs) such as Microsoft Windows, Mac OS and UNIX-based OSs; (4) provide programmers with one-to-one mapping APIs to directly manipulate DirectX objects and other game-related properties. The CWT has also been applied to an online Java game system to demonstrate the proposed architecture. Copyright (C) 2006 John Wiley & Sons, Ltd.
A special issue on artificial intelligence in computer games: AICG
(2012-10-01)
Fujita, Hamido
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
Achieving high and consistent rendering performance of Java AWT/Swing on multiple platforms
(2009-05-01)
Wang, Yi-Hsien
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
Wang et al. (Softw. Pract. Exper. 2007; 37(7):727-745) observed a phenomenon of performance inconsistency in the graphics of Java Abstract Window Toolkit (AWT)/Swing among different Java runtime environments (JREs) on Windows XP This phenomenon makes it difficult to predict the performance of Java game applications. Therefore, they proposed a portable AWT/Swing architecture, called CYC Window Toolkit (CWT), to provide programmers with high and consistent rendering performance for Java game development among different JREs. They implemented a DirectX version to demonstrate the feasibility of the architecture. This paper extends the above research to other environments in two aspects. First, we evaluate the rendering performance of the original Java AWT with different combinations of JREs, image application programming interfaces, system properties and operating systems (OSs), including Windows XP, Windows Vista, Fedora and Mac OS X. The evaluation results indicate that the performance inconsistency of Java AWT also exists among the four OSs, even if the same hardware configuration is used. Second, we design an OpenGL version of CWT, named CWT-GL, to take advantage of modern 3D graphics cards, and compare the rendering performance of CWT with Java AWT/Swing. The results show that CWT-GL achieves more consistent and higher rendering performance in JREs 1.4 to 1.6 on the four OSs. The results also hint at two approaches: (a) decouple the rendering pipelines of Java AWT/Swing from the JREs for faster upgrading and supporting old JREs and (b) use other graphics libraries, such as CWT, instead of Java AWT/Swing to develop cross-platform Java games with higher and more consistent rendering performance. Copyright (C) 2009 John Wiley & Sons, Ltd.
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 Efficient Approach to Solving Nonograms
(2013-09-01)
Wu, I-Chen
;
Sun, Der-Johng
;
Chen, Lung-Ping
;
Chen, Kan-Yueh
;
Kuo, Ching-Hua
A nonogram puzzle is played on a rectangular grid of pixels with clues given in the form of row and column constraints. The aim of solving a nonogram puzzle, an NP-complete problem, is to paint all the pixels of the grid in black and white while satisfying these constraints. This paper proposes an efficient approach to solving nonogram puzzles. We propose a fast dynamic programming (DP) method for line solving, whose time complexity in the worst case O(kl) is only, where the grid size l x l is and k is the average number of integers in one constraint, always smaller than. In contrast, the time complexity for the best line-solving method in the past is O(kl(2)). We also propose some fully probing (FP) methods to solve more pixels before running backtracking. Our FP methods can solve more pixels than the method proposed by Batenburg and Kosters (before backtracking), while having a time complexity that is smaller than theirs by a factor of O(l). Most importantly, these FP methods provide useful guidance in choosing the next promising pixel to guess during backtracking. The proposed methods are incorporated into a fast nonogram solver, named LalaFrogKK. The program outperformed all the programs collected in webpbn.com, and also won both nonogram tournaments that were held at the 2011 Conference on Technologies and Applications of Artificial Intelligence (TAAI 2011, Taiwan). We expect that the proposed FP methods can also be applied to solving other puzzles efficiently.
AN EFFICIENT APPROACH TO SOLVING THE MINIMUM SUDOKU PROBLEM
(2011-12-01)
Lin, Hung-Hsuan
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
Since Sudoku was invented, it has been an open problem to find the minimum-clue Sudoku puzzles, also commonly called the minimum Sudoku problem. Solving the problem can be done by checking 5,472,730,538 essentially different Sudoku grids independently or in parallel. In the past, the program CHECKER, written by McGuire, required about 311 thousand years on one-core CPU to check these grids completely, according to our experimental analysis. This paper is to propose a more efficient approach to solving this problem. We design a new algorithm, named disjoint minimal unavoidable set (DMUS) algorithm, to help solve the minimum Sudoku problem more efficiently. After incorporating the algorithm into the program and further tuning the program code, our experiments showed that the performance was greatly improved by a factor of 128.67. Hence, it is estimated that it only takes about 2417 years to solve the problem. Thus, it becomes feasible and optimistic to solve this problem by using a volunteer computing system, such as BOINC.(2,3)
An Energy-Efficient Accelerator with Relative-Indexing Memory for Sparse Compressed Convolutional Neural Network
(2019-01-01)
Wu, I-Chen
;
Huang, Po-Tsang
;
Lo, Chin-Yang
;
Hwang, Wei
;
電子工程學系及電子研究所
Deep convolutional neural networks (CNNs) are widely used in image recognition and feature classification. However, deep CNNs are hard to be fully deployed for edge devices due to both computation-intensive and memory-intensive workloads. The energy efficiency of CNNs is dominated by off-chip memory accesses and convolution computation. In this paper, an energy-efficient accelerator is proposed for sparse compressed CNNs by reducing DRAM accesses and eliminating zero-operand computation. Weight compression is utilized for sparse compressed CNNs to reduce the required memory capacity/bandwidth and a large portion of connections. Thus, ReLU function produces zero-valued activations. Additionally, the workloads are distributed based on channels to increase the degree of task parallelism, and all-row-to-all-row non-zero element multiplication is adopted for skipping redundant computation. The simulation results over the dense accelerator show that the proposed accelerator achieves 1.79x speedup and reduces 23.51%, 69.53%, 88.67% on-chip memory size, energy, and DRAM accesses of VGG-16.
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.
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.
BIT WINS CONNECT6 TOURNAMENT
(2009-06-01)
Lin, Ping-Hung
;
Wu, I-Chen
;
Hsu, Shun-Chin
;
資訊工程學系
;
Department of Computer Science
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.