05850678

a

05850678 Wu, I-Chen Lin, Hung-Hsuan Lin, Ping-Hung Sun, Der-Johng Chan, Yi-Chih Chen, Bo-Ting Job-level proof-number search for Connect6. van den Herik, H. Jaap (ed.) et al., Computers and games. 7th international conference, CG 2010, Kanazawa, Japan, September 24--26, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-17927-3/pbk). Lecture Notes in Computer Science 6515, 11-22 (2011). 2011 Berlin: Springer EN

doi:10.1007/978-3-642-17928-0_2

Summary: This paper proposes a new approach for proof number (PN) search, named job-level PN (JL-PN) search, where each search tree node is evaluated or expanded by a heavy-weight job, which takes normally over tens of seconds. Such JL-PN search is well suited for parallel processing, since these jobs are allowed to be performed by remote processors independently. This paper applies JL-PN search to solving automatically several Connect6 positions including openings on desktop grids. For some of these openings, so far no human expert had been able to find a winning strategy. Our experiments also show that the speedups for solving the test positions are roughly linear, fluctuating from sublinear to superlinear. Hence, JL-PN search appears to be a quite promising approach to solving games.