Browsing by Author "Sun, Der-Johng"

Now showing 1 - 10 of 10

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.
Efficient online algorithm for identifying useless states in distributed systems
(2011-04-01)
Chen, Lung-Pin
;
Sun, Der-Johng
;
Chu, William
;
資訊工程學系
;
Department of Computer Science
In a distributed system, detecting whether a given logical predicate is true on the global states is fundamental for testing and debugging the program. Detecting predicates by examining all global states is intractable due to the combinatorial nature of the problem. This work designs an efficient online algorithm that identifies the consistent and useless states each time a new state is reported. This paper formulates the optimality of detecting algorithms in terms of pseudo states, which are employed to represent unknown states to the monitor process. Based on this technique, memory space of the debugger can be minimized by removing the useless states without affecting the debugging results. While minimizing memory space, the proposed algorithm requires only O(p (2) M) time in total, where p is the number of processes, and M is the number of reported states.
HAPPYNURI WINS NURIKABE TOURNAMENT
(2010-12-01)
Wu, I-Chen
;
Sun, Der-Johng
;
Yen, Shi-Jim
;
資訊工程學系
;
Department of Computer Science
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.
NONOGRAM TOURNAMENT IN OLYMPIAD YOKOHAMA 2013
(2014-03-01)
Chen, Lung-Pin
;
Sun, Der-Johng
;
Tseng, Wen-Jie
;
資訊工程學系
;
Department of Computer Science
NONOGRAM TOURNAMENTS IN TAAI 2011
(2012-06-01)
Sun, Der-Johng
;
Wu, Kuang-che
;
Wu, I-Chen
;
Yen, Shi-Jim
;
Kao, Kuo-Yuan
ON DESIGN OF BROWSER-ORIENTED DATA EXTRACTION SYSTEM AND THE PLUG-INS
(2010-04-01)
Su, Jui-Yuan
;
Sun, Der-Johng
;
Wu, I-Chen
;
Chen, Lung-Pin
;
資訊工程學系
Web data extraction systems currently not only extract data on web pages but also need to navigate to the target correctly. Most traditional web data extraction systems extract URLs directly from web pages, and then access next pages using the extracted URLs. This data extraction approach is herein called the URL-oriented data extraction approach in this paper. However, currently, more and more web pages use script functions, such as Java Script, to access next pages and may hide URLs inside these functions, making it difficult to extract URLs. In order to solve this problem, a new data extraction approach, named the browser-oriented data extraction (BODE) approach, is proposed to be built on top of browser objects access pages by simulating users' operations on browsers to invoke script functions. A data extraction system based on this approach is called the BODE system. Based on the BODE approach, this paper designed a BODE system with the following contributions: (a) Define a scripting language, named the BODED (Browser-Oriented Data Extraction Description) language, which instructs the BODE system to extract data. (b) Design a plug-ins that can be used to extend the functionalities of the BODE system. (c) Design a visualization tool to support the data extraction in the BODE system. (d) Illustrate the plug-in mechanism of the BODE system by automating the playing of the game Connect6 over an Internet game site.
Solving the Slitherlink Poblem
(2012)
Liu, Tung-Ying
;
Wu, I-Chen
;
Sun, Der-Johng
;
資訊工程學系
;
Department of Computer Science
Slitherlink is one of challenging puzzle games to human and computer players. In this paper, we propose an efficient method to solve Slitherlink puzzles. After using this method, we can solve each of 10,000 25x30 puzzles given in [9] within 0.05 seconds. Without using the method, it takes at least 10 minutes to solve some of these puzzles.
THE 2010 TAAI COMPUTER-GAME TOURNAMENTS
(2011-03-01)
Lin, Hung-Hsuan
;
Sun, Der-Johng
;
Wu, I-Chen
;
Yen, Shi-Jim
;
資訊工程學系