Introduction to Connect6 Programs Developed at CGI Lab

This page introduces the history of Connect6 programs, mainly for NCTU6, 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 won ALL the Computer Connect6 tournaments that we participated, and most human-machine competitions. This page also wants to acknowledge all the contributors involved in the development.

Early design of Connect6 program (2004-2005)

Dei-Yen Huang (黃德彥) decided to write a Connect6 program for his M.S. Thesis on 2004. Actually, this is also the first computer game project of our CGI lab. His program was used to prove a loss for an initial breakaway move and play against human players (with a win rate of about 60%) in a game site in 2005.

Authors

Dei-Yen Huang (黃德彥) 2004-2005 Wrote a Connect6 program with threat space search (TSS) based on double threats (or so-called Live 4).
I-Chen Wu (吳毅成) 2004-2005 Supervised the whole project.

Features

Publications

  1. I-Chen Wu, Dei-Yen Huang and Hsiu-Chen Chang, "Connect6", ICGA Journal (SCI), Vol. 28, No. 4, pp. 235-242, December 2005.
  2. I-Chen Wu, and Dei-Yen Huang, "A New Family of k-in-a-row Games", the 11th Advances in Computer Games Conference (ACG'11), Taipei, Taiwan, September 2005.


The core design of NCTU6 (2006-2010)

I-Chen Wu (吳毅成) rewrote the whole code and named it "NCTU6" in 2006-2008. Hsiu-Chen Chang (張修逞) assisted on it during this period. Then, Ping-Hung Lin (林秉宏) took over the code and added some more heuristics and relevance zones for TSS starting from 2008.

Authors

I-Chen Wu (吳毅成) 2006-2010 Rewrote the whole code, NCTU6, including alpha-beta search for move selection and double-threat TSS and single-threat TSS for solving positions. Also supervised the whole project.
Hsiu-Chen Chang (張修逞) 2006-2007 Assisted on the TSS design of NCTU6.
Ping-Hung Lin (林秉宏) 2008-2010 Added several useful heuristics and relevance zones.

Features

Publications

  1. I-Chen Wu and Ping-Hung Lin, "Relevance-Zone-Oriented Proof Search for Connect6", the IEEE Transactions on Computational Intelligence and AI in Games (SCI), Vol. 2, No. 3, pp. 191-207, September 2010.
  2. Ping-Hung Lin and I-Chen Wu, "NCTU6 Wins in the Man-Machine Connect6 Championship 2009", ICGA Journal (SCI), vol. 32(4), 2009.
  3. I-Chen Wu and Ping-Hung, Lin, "NCTU6-Lite Wins Connect6 Tournament", ICGA Journal (SCI), Vol.31, No.4, December 2008.
  4. I-Chen Wu and Shi-Jim, Yen, "NCTU6 Wins Connect6 Tournament", ICGA Journal (SCI), Vol.29, No.3, September 2006.


Strength Improvements (2010-)

Even though we won almost all competitions (human or computers), we still kept improving NCTU6's strength. The first significant improvement is to use TD learning to train better feature weights by Hsin-Ti Tsai (蔡心迪) and Hung-Hsuan Lin (林宏軒). The second is to use dependency-based search to improve TSS performance by Hao-Hua Kang (康皓華) and Ting-Han Wei (魏廷翰). The third is to parallelize NCTU6 by Chieh-Min Chang (張傑閔). We also built a job-level proof-number search algorithm using NCTU6 as jobs by Hung-Hsuan Lin (林宏軒) and Ting-Han Wei (魏廷翰), and built a mobile Connect6 program, named mobile6, by modifying it from NCTU6 by Ji-Hong Zheng (鄭吉閎), Chia-Yun Hu (胡嘉芸) and Hung-Hsuan Lin (林宏軒).

Authors

Hung-Hsuan Lin (林宏軒) 2010-2013 Assisted TD learning, built job-level proof-number search algorithm, and designed the algorithm used in the mobile6 design.
Hsin-Ti Tsai (蔡心迪) 2010-2011 Designed and implemented TD learning (the key person).
Hao-Hua Kang (康皓華) 2011-2012 Designed and implemented dependency-based search(the key person).
Chieh-Min Chang (張傑閔) 2011-2013 Designed and implemented parallelization of NCTU6 (the key person).
Chia-Yun Hu (胡嘉芸) 2011-2012 Designed and implemented mobile6 on iOS.
Ji-Hong Zheng (鄭吉閎) 2011-2012 Designed and implemented mobile6 on Android.
Ting-Han Wei (魏廷翰) 2013-current Assisted on job-level proof-number search algorithm, and dependency-based search.
I-Chen Wu (吳毅成) 2011-current Supervised the whole project.

Features

Publications

  1. Ting-Han Wei, I-Chen Wu, Chao-Chin Liang, Bing-Tsung Chiang, Wen-Jie Tseng, Shi-Jim Yen, and Chang-Shing Lee, "Job-Level Algorithms for Connect6 Opening Position Analysis", ECAI Computer Games Workshop 2014, Prague, Czech Republic, August 2014.
  2. I-Chen Wu, Hao-Hua Kang, Hung-Hsuan Lin, Ping-Hung Lin, Ting-Han Wei, Chieh-Min Chang, Ting-Fu Liao, "Dependency-Based Search for Connect6", The International Conference on Computers and Games (CG 2013), Yokohama, Japan, August 2013. (Best Paper Award)
  3. Ji-Hong Zheng, Chia-Yun Hu, I-Chen Wu, Wen-Jie Tseng, Ching-Hsuan Wei, Hung-Hsuan Lin, Chieh-Min Chang, Hao-Hua Kang, Hsiu-Chuan Lin, "Connect6 Programs on Mobile Devices", the 2012 Conference on Technologies and Applications of Artificial Intelligence (TAAI 2012), Tainan, Taiwan, November 2012. (Excellent Demo Award)
  4. I-Chen Wu, Yi-Shan Lin, Hsin-Ti Tsai and Ping-Hung Lin, "The Man-Machine Connect6 Championship 2011", ICGA Journal (SCI), vol. 34, no. 2, June 2011.
  5. I-Chen Wu, Hsin-Ti Tsai, Hung-Hsuan Lin, Yi-Shan Lin, Chieh-Min Chang, Ping-Hung Lin, "Temporal Difference Learning for Connect6", The 13th Advances in Computer Games Conference (ACG 13), Tilburg, The Netherlands, 20-22 November 2011.
  6. I-Chen Wu, H.-H. Lin, P.-H. Lin, D.-J. Sun, Y.-C. Chan and B.-T. Chen, "Job-Level Proof-Number Search for Connect6", The International Conference on Computers and Games (CG 2010), Kanazawa, Japan, September 2010.

Competition Summary

Computer Competitions

Year Competitions Place
2013 Computer Olympiad 1st place (Gold)
2010 Computer Olympiad 1st place (Gold)
2008 Computer Olympiad 1st place (Gold)
2010-2014 TAAI computer game tournaments All 1st place (Gold)
2011-2015 TCGA computer game tournaments All 1st place (Gold)

Human Competitions

Year Competitions Human Result
2011 The third annual Man-Machine Connect6 Contest Top human players in Taiwan Won 5 and lost 3
2008 The first annual Man-Machine Connect6 Contest Top human players in Taiwan Won 11 and lost 1
2009 The second annual Man-Machine Connect6 Contest Top human players in Taiwan Won 8 and lost nothing
2009-2015(now) Littlegolem Connect6 Championships Top online human players all over the world Won 9 champions out of 13 championships (from #7-#19) with names, "lomaben" and "Happy6".