# Automatic Generation of Alternative Starting Positions for Traditional Board Games

Ahmed, Umair Z and Chatterjee, Krishnendu and Gulwani, Sumit (2013) Automatic Generation of Alternative Starting Positions for Traditional Board Games. Technical Report. IST Austria.

## Abstract

Board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in development of mathematical and logical skills, but also in emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. Our approach generates starting states of varying hardness levels for player~$1$ in a two-player board game, given rules of the board game, the desired number of steps required for player~$1$ to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. Also, the presence of such states for standard game variants like Tic-Tac-Toe on board size $4 \times 4$ opens up new games to be played that have not been played for ages since the default start state is heavily biased.

Item Type: Monograph (Technical Report) A short version of this technical report is available at https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9523 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data Chatterjee Group Prof Krishnendu Chatterjee 03 Dec 2013 14:49 19 Jul 2019 04:50 https://repository.ist.ac.at/id/eprint/146