Browsing by Author "Wei, Ting Han"

Now showing 1 - 3 of 3

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.
SOFTWARE DEVELOPMENT ARCHITECTURE FOR JOB-LEVEL ALGORITHMS
(2015-09-01)
Wei, Ting Han
;
Liang, Chao-Chin
;
Wu, I-Chen
;
Chen, Lung-Pin
;
資訊工程學系
Recently, Wu et al. introduced a general distributed computing approach, named Job-Level (JL) Computing. In JL computing, a search tree is maintained by a client process, while search tree nodes are evaluated, expanded, or generated by leveraging game-playing programs. These node operations are encapsulated as coarse-grain jobs, each requiring tens of seconds or more of running the programs. This article presents an abstraction of the JL computing approach and develops a general JL search framework so that common modules may be reused for various JL applications, making JL development easier. We describe in detail the implementation of the JL Proof-number Search (JL-PNS) and JL Upper Confidence Bound Search (JL-UCT) as case studies in the application of the JL search framework. In our case studies, only hundreds of lines of code are required for new JL applications, while the code for the JL framework consists of more than ten thousand lines of code. It demonstrates that this framework can be used to greatly reduce new JL application development and software maintenance efforts.
SOLVING HEX OPENINGS USING JOB-LEVEL UCT SEARCH
(2015-09)
Liang, Xi
;
Wei, Ting Han
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
Recently, Pawlewicz and Hayward successfully solved many Hex openings based on the Scalable Parallel Depth-First Proof-Number Search algorithm (SPDFPN), which was performed in a single machine with multiple threads. However, further parallelization is limited by the number of cores a single machine can possess. This article investigates adapting this SPDFPN solver to a distributed computing environment, using the previously proposed job-level upper-confidence tree algorithm (JL-UCT) in order to further increase parallelism. To improve on the adapted JL-UCT solver system, we make a new attempt to support transposition information sharing among jobs in JL implementations on top of a JL framework. A mix of shared-memory and database techniques was used to achieve this improvement. Our experiments show that the adapted JL-UCT solver is able to solve positions faster as the number of cores increases. Additionally, using a single machine with 24 cores, the adapted method is able to solve Hex openings with less time than the previous SPDFPN solver in four of five test cases. Overall, for the five test cases, the adapted JL-UCT solver, using 6 nodes each with 24 cores, obtained speedups of 1.6 to 2.6 over those for the SPDFPN solver using one node with 24 cores.