Job-level algorithms for Connect6 opening book construction

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

Research output: Contribution to journalArticlepeer-review

Abstract

This article investigates the use of job-level (JL) algorithms for Connect6 opening book construction. In the past, JL proof-number 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, the current article first proposes four heuristic metrics when using JL-PNS to estimate move quality. The article then proposes a JL upper confidence tree (JL-UCT) algorithm and three heuristic metrics that work with JL-UCT. Of the three, the best way to estimate move quality for JLUCT is the number of nodes in each candidate move's subtree. In order to compare the heuristic metrics among the two algorithms 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. Experimental results show that the node count heuristic metric for JL-UCT outperforms all other heuristic metrics, including the four for JL-PNS. We then verify the results by constructing three separate opening books using the top three performing heuristic metrics. Competitive play also shows that the node count heuristic metric for JL-UCT is most suitable among the currently proposed heuristic metrics for Connect6 opening book construction.

Original languageEnglish
Pages (from-to)165-179
Number of pages15
JournalICGA Journal
Volume38
Issue number3
DOIs
StatePublished - 1 Jan 2015

Cite this