Research

(This page may not contain up-to-date information which can be found here.)

All current research interests in this lab are related to computer games and mathematical optimization.

  • Computer games (mainly related to AI games, such as board games, card games, puzzle games etc.)
  • Machine learning for computer games and mathematical optimization.
  • Cloud computing (including volunteer computing clouds for computer games).
  • Mobile gaming (including platforms for iOS/Android games).
Welcome to join us!!

Research Topics and Achievements

List our research topics as well as achievements (since 2005).

New games

  • Present a new family of k-in-a-row games, including the new game Connect6 in 2005. Also see publications.
    • Connect(m,n,k,p,q): Black plays first and puts only q black stone on unoccupied intersections (also called grids) of an mxn board. Subsequently, Black and White alternately put p of their own stones on unoccupied grids. The one who first gets k or more consecutive stones (horizontally, vertically or diagonally) of her/his own wins. Modern Connect6 is Connect(19,19,6,2,1).
    • It has become a computer game tournament in Computer Olympiad since then.
    • The game has been supported in some game sites, e.g., www.cycgame.com, www.littlegolem.net, pente.org, www.renrousousuo.com, BrainKing.com, etc.
    • ...
  • Present a new Domineering game, named XT Domineering. Also see publications.
    • The game is much more complicated than Domineering with the same size.
    • The game includes a large number of infinitesimals in terms of combinatorial game theory.

Solving open problems

  • Solve some Connect(k,p), where Connect(k,p) is Connect(infinity,infinity,k,p,p). Also see publications.
    • Connect(11,2) is a draw.
    • Consider all p >= 3. Let P(d-1) < p <= P(d), where P(d) = 6*2^d - d - 4. Then, Connect(3p+3d+8, p) is a draw.
  • Solve several Connect6 openings based on job-level computing. Also see publications.
    • Include the well-known Mickey Mouse opening and Straight opening.
  • Solve a Nim game, called Triangular Nim. Also see publications.
    • Triangular Nim with size 9 are solved with the first player winning, in both normal and misere versions.
  • Solve the minimum Sudoku problem. Also see publications.
    • No 16-clue puzzles exist. BOINC was used to solve it after 2 years and 8 months or so. We are the second team to solve this, independently developed from the first team led by Professor McGuire.
    • All 17-clue puzzles with 3 clues in one column/row block are solved.

Game-playing programs for perfect information games

  • Develop game-playing programs for Connect6.
    • Many new techniques were developed, including relevance-zone-oriented threat-space search, job-level proof-number search, TD-learning, dependency-based learning, dovetaling for parallelization, etc. Also see publications.
    • A developed program, named NCTU6 (交大六號), is at the level of top human players.
      • NCTU6 attended Computer Olympiad in 2006 and 2008, and won the gold medal each time. Also see honors.
      • NCTU6 won against top human players in the first/second/third annual Man-Machine Connect6 Championship, in 2008/2009/2011. Also see honors.
    • Another, named mobile6 based on NCTU6, is a mobile version. Note that mobile devices generally run about 10 times slower and support much smaller memory (about 2M bytes only are used in mobile6). Also see publications.
      • Still won the gold medal in Computer Olympiad 2013. Also see honors.
    • NCTU6 was used to help build Connect6 puzzle generator (in connect6.org).
  • Develop game-playing programs for Chinese chess.
    • Some new techniques were developed, including M&M, Dynamic Tree Splitting for parallelization, etc. Also see publications.
    • A developed program, named Chimo (棋謀), at about 7-8 dan, won silver medals in the past three Computer Olympiad. Also see honors.
  • Develop game-playing programs for NoGo.
    • Some new techniques were developed, including MCTS, RAVE, etc.
    • A developed program, named HappyNoGo, won NoGo tournament in Computer Olympiad in 2013. Especially, it won against BobNoGo, which won the following tournaments without any losses, BIRS 2011, TAAI 2011, Computer Olympiad 2011, TCGA 2012. Also see honors.
    • Another developed program, named PohsuanNoGo, won the silver medal in the same NoGo tournament of Computer Olympiad in 2013. Also see honors.
  • Develop game-playing programs for Go.
    • Some new techniques were developed, including MCTS, RAVE, MCTS parallelism, etc.
    • A developed program, named HappyGo, won the silver medal in TAAI 2010 tournament.
    • Another program, named Amigo (renamed CGI abbreviated from "CGI Go Intelligence"), was in the fourth place in Computer Olympiad in 2013.

Game-playing programs for imperfect information games 

  • Develop game-playing programs for Mahjong.
    • Some new techniques were developed, including PO-MDP (partially observable Markov decision process), etc.
    • A developed program, named LongCatMJ, won Mahjong tournament in Computer Olympiad in 2013. Also see honors.
  • Develop game-playing programs for Dark chess.
    • Some new techniques were developed, including MCTS, etc.
    • A developed program, named DarkNight, won Dark chess tournament in Computer Olympiad in 2013. Also see honors.

Game-playing programs for puzzle games

  • Develop 2048-like AI games based on the technique of TD (temporal difference) learning.
    • A new TD learning technique was developed to improve AI programs for 2048-like games. Also see publications [C 56].
    • Honor: A 2048 AI program, named CGI-2048, won the second place in the 2048 group of Taiwan 2048 Bot Tournament in 2014. Also see honors
      The performance of CGI-2048 is still improving. The table (below) shows the performances of the early CGI-2048 (the one for the tournament), the latest improved CGI-2048, and Xificurk's program. To the best of our knowledge, Xificurk's outperformed all the known 2048 programs (see below) at the time before Octobor 2014. In November 2014, our latest CGI-2048 is able to perform better than Xificurk's. More importantly, ours runs about 300 times faster.
      Early CGI-2048 Xificurk's Program Latest CGI-2048
      2048 100.0% 100.0% 100.0%
      4096 100.0% 100.0% 100.0%
      8192 94% 99.1% 99.5%
      16384 59% 92.7% 93.6%
      32768 0% 31.7% 33.5%
      Max score 367956 829300 833300
      Ave score 251794 442419 446116
      Speed 1200 moves/sec 2-3 moves/sec 661 moves/sec
    • Honor: A Threes! AI program, named CGI-Threes, won the first place in the Threes group of Taiwan 2048 Bot Tournament in 2014. Also see honors. To the best of our knowledge (in August 2014), our program outperforms all the known Threes AI program. Its performance is as follows.
      384 100%
      768 100%
      1536 97.2%
      3072 68.6%
      6144 10.8%
      Max score 790,416
      Ave score 229,717
      Speed About 300 moves/sec
  • Develop puzzle game solvers.
    • Some new techniques were developed, including fully-probing techniques, line-painting, etc. Also see publications.
    • A Nonogram solver, named LaLaFrogKK, won Nonogram tournament in Computer Olympiad in 2013. Also see honors.
    • A Nuricabe solver, named HappyNuri, won Nuricabe tournament in Computer Olympiad in 2010. Also see honors.
    • Some solvers were developed for some other puzzle games, e.g., Slitherlink, Lightup, etc.
  • Mathematical optimization problems

    • Develop a program to solve MO-FJSP (Multi-Objective Flexible Job Shop Scheduling Problem).
      • The first MCTS-based algorithm that can find the 17 best Pareto solutions for Kacem benchmark problems.

    Cloud/grid/software environments

    • Propose the job-level (JL) computation model. Also see publications.
      • Develop JL proof number search to help solve many Connect6 openings.
      • Develop JL alpha-beta search to help build Chinese chess opening book.
    • Develop a desktop grid for developing computer games, named CGDG (computer game desktop grid). Also see publications.
      • Support volunteering computing and job-level algorithms.
      • Include at least 1000 cores, collaborated by at least six research organizations in Taiwan.
    • Develop a Generic Board Game Development Framework, which facilitates the developments of computer game. Also see publications.
      • Support editing environments for different games by plugin mechanisms.
      • Support different job-level algorithms.
    • Develop a Portable AWT/Swing Architecture for Java Game Development. Also see publications.
      • Support faster GUI rendering on different platforms.