Introduction to Nonogram Programs Developed at CGI Lab

This page introduces the history of Nonogram programs, mainly LalaFrogKK, developed in Computer Games and Intelligence (CGI) lab, led by Professor I-Chen Wu, at Department of Computer Science, National Chiao Tung University, Taiwan. The program LalaFrogKK won ALL the Computer Nonogram tournaments that we participated. This page also wants to acknowledge all the contributors involved in the development.

Early design of Nonogram programs (2010-2011)

Nonograms as well as other puzzle games were chosen as projects in the course, Theory of Computer Games, taught by Professor I-Chen Wu in 2010. Some strong programs were written by Hung-Hsuan Lin (林宏軒), Ching-Hua Kuo (郭青樺), and Kan-Yueh Chen (陳干越). They used different kinds of heuristics.

Authors

Hung-Hsuan Lin (林宏軒) 2010-2011 Wrote a program named HappyNono.
Ching-Hua Kuo (郭青樺) 2010-2011 Wrote a program named NonoFrog.
Kan-Yueh Chen (陳干越) 2010-2011 Wrote a program named NonoLala.
I-Chen Wu (吳毅成) 2010-2011 Supervised the whole project.

Competitions

The following two competitions were conducted in a two-player-game manner as described in the document (in Chinese). In breif, all participants genereates 100 puzzles. Each participant solves all other participants' puzzles. Among two participants, the one solves more puzzles wins.

Year Competitions Place
2010 TAAI computer game tournaments 1st, 2nd, 3rd
2011 TCGA computer game tournaments 2nd, 3rd

Note: the winner of TCGA 2011 was Naughty by Kuang-Che Wu, who was a senior engineer in Google Taiwan.

The core design of LalaFrogKK (2011-2013)

After being beaten by Naughty, Kan-Yueh Chen (陳干越), Ching-Hua Kuo (郭青樺) and Hao-Hua Kang (康皓華) coworked and redesigned a new program, named LalaFrogKK (named after their nicknames, Lala, Frog, and KK). Then, Der-Johng Sun (孫德中) wrote a paper about it and modified it following the paper, which was written and published in IEEE Transactions on CIAIG (see below). The program had won all the champions of all Computer Olympiad/TAAI/TCGA Nonogram tournaments, since TAAI 2011 and till Computer Olympiad 2015. The program participated in the tournaments is now available openly at Github.

Authors

Kan-Yueh Chen (陳干越) 2011-2012 Wrote LalaFrogKK.
Ching-Hua Kuo (郭青樺) 2011-2012 Wrote LalaFrogKK.
Hao-Hua Kang (康皓華) 2011-2012 Wrote LalaFrogKK.
Der-Johng Sun (孫德中) 2012-2013 Wrote a paper about it and modified the program following the paper.
I-Chen Wu (吳毅成) 2011-2013 Supervised the whole project.

Features

Competitions

Two kinds of nonogram tournaments were held in TAAI 2011. One is described as the above. The other is Nonogram solver as described in the document (in Chinese). In breif, all participants solve the same set of 1,000 puzzles provided by tournament organizer. The program solves the most puzzles wins. After TAAI 2011, only nonogram solver tournaments remained.

Year Competitions Place
2015 Computer Olympiad (Solver) 1st place (Gold)
2013 Computer Olympiad (Solver) 1st place (Gold)
2013-2014 TAAI computer game tournaments (Solver) All 1st place (Gold)
2012-2015 TCGA computer game tournaments (Solver) All 1st place (Gold)
2011 TAAI Nonograms 1st place (Gold)
2011 TAAI Nonogram Solver 1st place (Gold)
* TAAI 2012 did not include Nonogram tournaments.

Publications

  1. I-Chen Wu, Der-Johng Sun, Lung-Ping Chen, Kan-Yueh Chen, Ching-Hua Kuo, Hao-Hua Kang, and Hung-Hsuan Lin, "An Efficient Approach to Solving Nonograms", the IEEE Transactions on Computational Intelligence and AI in Games (SCI), Vol. 5, No. 3, pp. 251-264, September 2013.
  2. Der-Johng Sun, Kuang-Che Wu, I-Chen Wu, Shi-Jim Yen, and Kuo-Yuan Kao, "Nonogram Tournaments in TAAI 2011", ICGA Journal, Vol. 35, No. 2, pp. 120-123, 2012
  3. TCGA 2015 Nonogram Tournament Result, http://aigames.nctu.edu.tw/~hsuehch/nonogram/tcga2015/
  4. TAAI 2014 Nonogram Tournament Result, http://aigames.nctu.edu.tw/~hsuehch/nonogram/taai2014/
  5. TCGA 2014 Nonogram Tournament Result, http://aigames.nctu.edu.tw/~mike79212001/nonogram/tcga2014/
  6. TAAI 2013 Nonogram Tournament Results, http://aigames.nctu.edu.tw/~mike79212001/nonogram/TAAI2013/
  7. TCGA 2013 Nonogram Tournament Result, http://aigames.nctu.edu.tw/~mike79212001/nonogram/tcga2013/
  8. TCGA 2012 Nonogram Tournament Result, http://aigames.nctu.edu.tw/~mike79212001/nonogram/tcga2012/