Browsing by Author "Lin, Hung-Hsuan"

Now showing 1 - 13 of 13

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)
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.
Connect6 Programs on Mobile Devices
(2012)
Zheng, Ji-Hong
;
Hu, Chia-Yun
;
Wu, I-Chen
;
Tseng, Wen-Jie
;
Wei, Ching-Hsuan
In this demonstration, we port our current Connect6 program, NCTU6, to mobile devices, such as iOS devices, Android devices. However, computing powers of mobile devices are also relatively weaker when compared with high-end machines. For example, the CPU speeds of mobile devices are about 1/5 to 1/8 of those of desktops; and the memory of mobile devices is usually limited to several megabytes. In this demonstration, we tune the program NCTU6 to fit in mobile devices, while maintaining reasonable strength. The program also won the silver medal in TCGA 2012. In addition, we also support Connect6 puzzles in the program.
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.
Job-Level Proof Number Search
(2013-03-01)
Wu, I. -Chen
;
Lin, Hung-Hsuan
;
Sun, Der-Johng
;
Kao, Kuo-Yuan
;
Lin, Ping-Hung
This paper introduces an approach, called generic job-level search, to leverage the game-playing programs which are already written and encapsulated as jobs. Such an approach is well suited to a distributed computing environment, since these jobs are allowed to be run by remote processors independently. In this paper, we present and focus on a job-level proof number search (JL-PNS), a kind of generic job-level search for solving computer game search problems, and apply JL-PNS to solving automatically several Connect6 positions, including some difficult openings. This paper also proposes a method of postponed sibling generation to generate nodes smoothly, and some policies, such as virtual win, virtual loss, virtual equivalence, flagging, or hybrids of the above, to expand the nodes. Our experiment compared these policies, and the results showed that the virtual-equivalence policy, together with flagging, performed the best against other policies. In addition, the results also showed that the speedups for solving these positions are 8.58 on average on 16 cores.
Job-Level Proof-Number Search for Connect6
(2011)
Wu, I-Chen
;
Lin, Hung-Hsuan
;
Lin, Ping-Hung
;
Sun, Der-Johng
;
Chan, Yi-Chih
This paper proposes a new approach for proof number (PN) search, named job-level PN (JL-PN) search, where each search tree node is evaluated or expanded by a heavy-weight job, which takes normally over tens of seconds. Such JL-PN search is well suited for parallel processing, since these jobs are allowed to be performed by remote processors independently. This paper applies JL-PN search to solving automatically several Connect6 positions including openings on desktop grids. For some of these openings, so far no human expert had been able to find a winning strategy. Our experiments also show that the speedups for solving the test positions are roughly linear, fluctuating from sublinear to superlinear. Hence, JL-PN search appears to be a quite promising approach to solving games.
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.
SOLVING 9 LAYER TRIANGULAR NIM
(2010-01-01)
Shan, Yi-Chang
;
Wu, I-Chen
;
Lin, Hung-Hsuan
;
Kao, Kuo-Yuan
;
資訊工程學系
Triangular Nim, one variant of the game Nim, is a common two-player game in Taiwan and China. In the past, Hsu strongly solved 7 layer Triangular Nim while some of the authors recently strongly solved 8 layer Triangular Nim. The latter required 8 gigabytes in memory and 8878 seconds. Using a retrograde method, this paper strongly solves 9 layer Triangular Nim. In our first version, the program requires four terabytes in memory and takes about 129.21 days aggregately. In our second version, improved by removing some rotated and mirrored positions, the program reduces the memory by a factor of 5.86 and the computation time by a factor of 4.38. Our experiment result also shows that the loss rate is only 5.0%. This is also used to help improve the performance.
Solving Nine Layer Triangular Nim
(2012-01-01)
Shan, Yi-Chang
;
Wu, I-Chen
;
Lin, Hung-Hsuan
;
Kao, Kuo-Yuan
;
資訊工程學系
Triangular Nim, one variant of the game Nim, is a common two-player game in Taiwan and China. In the past, Hsu [9] strongly solved seven layer Triangular Nim while some of the authors recently strongly solved eight layer Triangular Nim. The latter required 8 gigabytes in memory and 8,472 seconds. Using a retrograde method, this paper strongly solves nine layer Triangular Nim. In our first version, the program requires four terabytes in memory and takes about 129.21 days aggregately. In our second version, improved by removing some rotated and mirrored positions, the program reduces the memory by a factor of 5.72 and the computation time by a factor of 4.62. Our experiment result also shows that the loss rate is only 5.0%. This is also used to help improve the performance.
Solving the Minimum Sudoku Poblem
(2010-01-01)
Lin, Hung-Hsuan
;
Wu, I-Chen
;
資訊工程學系
;
Department of Computer Science
It is known that solving the minimum Sudoku problem can be done by checking 5,472,730,538 essentially different Sudoku grids, which can be checked independently or in parallel. However, the program Checker, written by McGuire, requires about 311 thousand years on one-core CPU to check these grids completely, according to our experimental analysis. This paper proposes a new algorithm, named a disjoint minimal unavoidable set (DMUS) algorithm, to help solve the minimum Sudoku problem. Then, incorporate the algorithm into the program and further tuning the program code. In our experiment, the performance was greatly improved by a factor of 128.67. Hence, the improved program by us requires about 2417.4 years only. Thus, it becomes feasible and optimistic to solve this program using a volunteer computing system, such as BOINC.
THE 2010 TAAI COMPUTER-GAME TOURNAMENTS
(2011-03-01)
Lin, Hung-Hsuan
;
Sun, Der-Johng
;
Wu, I-Chen
;
Yen, Shi-Jim
;
資訊工程學系
THE 2010 TAAI COMPUTER-GO TOURNAMENTS
(2011-03-01)
Yen, Shi-Jim
;
Chou, Cheng-Wei
;
Lin, Hung-Hsuan
;
Wu, I-Chen
;
資訊工程學系