TY - JOUR

T1 - QBF encoding of generalized tic-Tac-Toe

AU - Diptarama,

AU - Yoshinaka, Ryo

AU - Shinohara, Ayumi

PY - 2016/1/1

Y1 - 2016/1/1

N2 - Harary's generalized Tic-Tac-Toe is an achievement game for polyominoes, where two players alternately put a stone on a grid board, and the player who first achieves a given polyomino wins the game. It is known whether the first player has a winning strategy in the generalized Tic-Tac-Toe for almost all polyominoes except the one called Snaky. GTTT(p, q) is an extension of the generalized Tic-Tac-Toe, where the first player places q stones in the first move and then the players place q stones in each turn. In this paper, in order to attack GTTT(p, q) by QBF solvers, we propose a QBF encoding for GTTT(p, q). Our encoding is based on Gent and Rowley's encoding for Connect-4. We modify three parts of the encoding: initial condition, move rule and winning condition of the game. The experimental results show that some QBF solvers can be used to solve GTTT(p, q) on 4 × 4 or smaller boards.

AB - Harary's generalized Tic-Tac-Toe is an achievement game for polyominoes, where two players alternately put a stone on a grid board, and the player who first achieves a given polyomino wins the game. It is known whether the first player has a winning strategy in the generalized Tic-Tac-Toe for almost all polyominoes except the one called Snaky. GTTT(p, q) is an extension of the generalized Tic-Tac-Toe, where the first player places q stones in the first move and then the players place q stones in each turn. In this paper, in order to attack GTTT(p, q) by QBF solvers, we propose a QBF encoding for GTTT(p, q). Our encoding is based on Gent and Rowley's encoding for Connect-4. We modify three parts of the encoding: initial condition, move rule and winning condition of the game. The experimental results show that some QBF solvers can be used to solve GTTT(p, q) on 4 × 4 or smaller boards.

UR - http://www.scopus.com/inward/record.url?scp=84996931933&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84996931933&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:84996931933

VL - 1719

SP - 14

EP - 26

JO - CEUR Workshop Proceedings

JF - CEUR Workshop Proceedings

SN - 1613-0073

T2 - 4th International Workshop on Quantified Boolean Formulas, QBF 2016

Y2 - 4 July 2016

ER -