Browsing by Author "Wei, Ting-Han"

Now showing 1 - 12 of 12

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.
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.
Database Caching for Job-Level Computing
(2016-01-01)
Chiang, Han
;
Wei, Ting-Han
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
This paper improves upon Job-Level (JL) computing, a general distributed computing approach. In JL computing, a client maintains the overall search tree and parcels the overall search into coarse-grained jobs, which are then each calculated by pre-existing game-playing programs. In order to support large-scale problems such as solving 7x7 killall-Go, or building opening books for 9x9 Go or Connect6, JL computing is modified so that the entire search tree is stored in a database, as opposed to simply being stored in the client process' memory. However, the time cost of accessing this database becomes a bottleneck on performance when using a large number of computing resources. This paper proposes a cache mechanism for JL search trees. Instead of the previous approach, where the entire search tree is stored in the database, we maintain parts of the search tree in the memory of the client process to reduce the number of database accesses. Our method significantly improves the performance of job operations. Assuming that each job requires 30 seconds on average, the JL application with this cache mechanism can allow for the use of 5036 distributed computing resources in parallel without database accesses becoming the performance bottleneck.
Dependency-Based Search for Connect6
(2014-01-01)
Wu, I-Chen
;
Kang, Hao-Hua
;
Lin, Hung-Hsuan
;
Lin, Ping-Hung
;
Wei, Ting-Han
Allis proposed dependency-based search (DBS) to solve Go-Moku, a kind of five-in-a-row game. DBS is critical for threat space search (TSS) when there are many independent or nearly independent TSS areas. Similarly, DBS is also important for the game Connect6, a kind of six-in-a-row game with two pieces per move. Unfortunately, the rule that two pieces are played per move in Connect6 makes DBS extremely difficult to apply to Connect6 programs. This paper is the first attempt to apply DBS to Connect6 programs. The targeted program is NCTU6, which won Connect6 tournaments in the Computer Olympiad twice and defeated many professional players in Man-Machine Connect6 championships. The experimental results show that DBS yields a speedup factor of 4.12 on average, and up to 50 for some hard positions.
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.
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.
Job-Level Computing With BOINC Support
(2016-01-01)
Chang, Chia-Chuan
;
Wei, Ting-Han
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
Recently, Wu et al. introduced a general approach based on distributed computing named Job-Level (JL) Computing. JL Computing has been successfully used to construct the opening books of game-playing programs. In order to support large-scale computing problems such as solving 7x7 killall-Go, or building opening books for 9x9 Go or Connect6, record databases are used to store JL computing results. In this paper, we further design a mechanism that combines the JL computing system with BOINC (Berkeley Open Infrastructure for Network Computing), so that we can leverage more computing power from volunteers to solve even larger problems. A preliminary experiment has been done to demonstrate the feasibility of the design.
MOBILE6 WINS CONNECT6 TOURNAMENT
(2013-09-01)
Wei, Ting-Han
;
Tseng, Wen-Jie
;
Wu, I-Chen
;
Yen, Shi-Jim
;
資訊工程學系
Multilabeled Value Networks for Computer Go
(2018-12-01)
Wu, Ti-Rong
;
Wu, I-Chen
;
Chen, Guan-Wun
;
Wei, Ting-Han
;
Wu, Hung-Chun
This paper proposes a new approach to a novel value network architecture for the game Go, called a multilabeled (ML) value network. In the ML value network, different values (win rates) are trained simultaneously for different settings of komi, a compensation given to balance the initiative of playing first. The ML value network has three advantages: 1) it outputs values for different komi; (2) it supports dynamic komi; and (3) it lowers the mean squared error (MSE). This paper also proposes a new dynamic komi method to improve game-playing strength. This paper also performs experiments to demonstrate the merits of the architecture. First, the MSE of the ML value network is generally lower than the value network alone. Second, the program based on the ML value network wins by a rate of 67.6% against the program based on the value network alone. Third, the program with the proposed dynamic komi method significantly improves the playing strength over the baseline that does not use dynamic komi, especially for handicap games. To our knowledge, up to date, no handicap games have been played openly by programs using value networks. This paper provides these programs with a useful approach to playing handicap games.
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 Adjustment and Assessment for MCTS-Based Programs [Research Frontier]
(2020-08-01)
Liu, An-Jen
;
Wu, Ti-Rong
;
Wu, I-Chen
;
Guei, Hung
;
Wei, Ting-Han
This paper proposes an approach to strength adjustment and assessment for Monte-Carlo tree search based game-playing programs. We modify an existing softmax policy with a strength index to choose moves. The most important modification is a mechanism which filters low-quality moves by excluding those that have a lower simulation count than a pre-defined threshold ratio of the maximum simulation count. Through theoretical analysis, we show that the adjusted policy is guaranteed to choose moves exceeding a lower bound in strength by using a threshold ratio. Experimental results show that the strength index is highly correlated to the empirical strength. With an index value between ?2, we can cover a strength range of about 800 Elo ratings. The strength adjustment and assessment methods were also tested in real-world scenarios with human players, ranging from professionals (strongest) to kyu rank amateurs (weakest). For amateur levels, we tested our mechanism on two popular Go online platforms - Fox Weiqi and Tygem. The result shows that our method can adjust program strength to different ranks stably. In terms of strength assessment, we proposed a new dynamic strength adjustment method, then used it to evaluate human professionals, predicting reliably their playing strengths within 15 games. Lastly, we collected survey responses asking players about strength perception, entertainment, and general comments for different aspects of analysis. To our best knowledge, this result is state-ofthe- art in terms of the range of strengths in Elo rating while maintaining a controllable relationship between the strength and a strength index.
Using 2048-like games as a pedagogical tool for reinforcement learning
(2018-01-01)
Guei, Hung
;
Wei, Ting-Han
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
2048-like games are games that have similar properties with 2048, a single-player stochastic sliding puzzle game. 2048-like games are highly suitable for educational purposes due to 2048's relatively simple rules and its popularity. When using 2048-like games as a tool for machine learning education, these games have the additional benefit of being a well-known topic of research. Numerous machine learning methods have been proposed in the past for 2048, which provides a good opportunity for students to gain first-hand experience in applying these techniques. This paper summarizes the experience of using the game 2584, a 2048-like game, as a pedagogical tool for teaching reinforcement learning and computer game algorithms in 2017. 2584 is similar to 2048, with the only difference being the tiles values are Fibonacci numbers instead of powers of two. A two-player variant was designed to further teach adversarial game techniques. With a class of 33 undergraduate and graduate students, the average win rate for the single-player version of the 2584 reached 96%.