Browsing by Author "Wei, Tinghan"

Now showing 1 - 3 of 3

Job-Level UCT Search for Solving Hex
(2015)
Liang, Xi
;
Wei, Tinghan
;
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 paper 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. A mix of shared-memory and database techniques was used to achieve this improvement. Our experiments show that the adapted JL-UCT solver scales for larger problems. 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 three of four test cases. Overall, for the four test cases, the adapted JL-UCT solver, using 6 nodes each with 24 cores, obtained speedups of 1.6, 1.9, 1.8 and 2.6 over those for the SPDFPN solver using one node with 24 cores.
ON SPECIFIC 17-CLUE SUDOKU PUZZLES
(2013-09-01)
Lin, Hung-Hsuan
;
Wu, I-Chen
;
Wei, Tinghan
;
資訊工程學系
;
Department of Computer Science
Since Sudoku was invented, it has been interesting to find Sudoku puzzles with the minimum number of clues. Royle collected 49,151 17-clue Sudoku puzzles between 2005 and 2009, each of which is not isomorphic to any other, and McGuire claimed in 2012 that no 16-clue Sudoku puzzle exists. Since 2009, no new 17-clue Sudoku puzzles have been found. This paper proposes an algorithm to find 17-clue Sudoku puzzles based on the number of clues in the topmost 9x3 cells, which is called a top-block. Using this algorithm, we prove that (1) no 17-clue puzzles exist of which the top-block has fewer than three clues and (2) precisely 95 17-clue puzzles exist of which the top-block has three and only three clues. Moreover, we compared these 95 puzzles to the 49,151 collected 17-clue Sudoku puzzles and found that these 95 puzzles are already collected by Royle. Thus, a conjecture from this paper is that most of the 17-clue Sudoku puzzles have been found.
On Strength Adjustment for MCTS-Based Programs
(2019-01-01)
Wu, I-Chen
;
Wu, Ti-Rong
;
Liu, An-Jen
;
Guei, Hung
;
Wei, Tinghan
This paper proposes an approach to strength adjustment for MCTS-based game-playing programs. In this approach, we use a softmax policy with a strength index to choose moves. Most importantly, we filter low quality moves by excluding those that have a lower simulation count than a pre-defined threshold ratio of the maximum simulation count. We perform a theoretical analysis, reaching the result that the adjusted policy is guaranteed to choose moves exceeding a lower bound in strength by using a threshold ratio. The approach is applied to the Go program ELF OpenGo. The experiment results show that is highly correlated to the empirical strength; namely, given a threshold ratio 0.1, z is linearly related to the Elo rating with regression error 47.95 Elo where -2 <= z <= 2. Meanwhile, the covered strength range is about 800 Elo ratings in the interval of in. With the ease of strength adjustment using, we present two methods to adjust strength and predict opponents' strengths dynamically. To our knowledge, this result is state-of-the-art in terms of the range of strengths in Elo rating while maintaining a controllable relationship between the strength and a strength index.