Job-level algorithms for Connect6 opening position analysis

Ting Han Wei*, I-Chen Wu, Chao Chin Liang, Bing Tsung Chiang, Wen Jie Tseng, Shi Jim Yen, Chang Shing Lee

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

This paper investigates job-level (JL) algorithms to analyze opening positions for Connect6. The opening position analysis is intended for opening book construction, which is not covered by this paper. In the past, JL proofnumber search (JL-PNS) was successfully used to solve Connect6 positions. Using JL-PNS, many opening plays that lead to losses can be eliminated from consideration during the opening game. However, it is unclear how the information of unsolved positions can be exploited for opening book construction. For this issue, this paper first proposes four heuristic metrics when using JL-PNS to estimate move quality. This paper then proposes a JL upper confidence tree (JLUCT) algorithm and some heuristic metrics, one of which is the number of nodes in each candidate move’s subtree. In order to compare these metrics objectively, we proposed two kinds of measurement methods to analyze the suitability of these metrics when choosing best moves for a set of benchmark positions. The results show that for both metrics this node count heuristic metric for JL-UCT outperforms all the others, including the four for JL-PNS.

Original languageEnglish
Title of host publicationComputer Games - 3rd Workshop on Computer Games, CGW 2014 Held in Conjunction with the 21st European Conference on Artificial Intelligence, ECAI 2014, Revised Selected Papers
EditorsTristan Cazenave, Yngvi Björnsson, Mark H.M. Winands
PublisherSpringer Verlag
Pages29-44
Number of pages16
ISBN (Electronic)9783319149226
DOIs
StatePublished - 1 Jan 2014
Event3rd Workshop on Computer Games, CGW 2014 held in Conjunction with the 21st European Conference on Artificial Intelligence, ECAI 2014 - Prague, Czech Republic
Duration: 18 Aug 201418 Aug 2014

Publication series

NameCommunications in Computer and Information Science
Volume504
ISSN (Print)1865-0929

Conference

Conference3rd Workshop on Computer Games, CGW 2014 held in Conjunction with the 21st European Conference on Artificial Intelligence, ECAI 2014
CountryCzech Republic
CityPrague
Period18/08/1418/08/14

Keywords

  • Connect6
  • Job-level computing
  • Monte-Carlo tree search
  • Opening book generation
  • Proofnumber search
  • Upper confidence bound

Fingerprint Dive into the research topics of 'Job-level algorithms for Connect6 opening position analysis'. Together they form a unique fingerprint.

  • Cite this

    Wei, T. H., Wu, I-C., Liang, C. C., Chiang, B. T., Tseng, W. J., Yen, S. J., & Lee, C. S. (2014). Job-level algorithms for Connect6 opening position analysis. In T. Cazenave, Y. Björnsson, & M. H. M. Winands (Eds.), Computer Games - 3rd Workshop on Computer Games, CGW 2014 Held in Conjunction with the 21st European Conference on Artificial Intelligence, ECAI 2014, Revised Selected Papers (pp. 29-44). (Communications in Computer and Information Science; Vol. 504). Springer Verlag. https://doi.org/10.1007/978-3-319-14923-3