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.

[img] Text
main.pdf - Published Version
Available under License All rights reserved.
[IST-2013-146-v1+1]
Download (667Kb)

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)
Additional Information: A short version of this technical report is available at https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9523
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data
Research Group: Chatterjee Group
Depositing User: Prof Krishnendu Chatterjee
Date Deposited: 03 Dec 2013 14:49
Last Modified: 19 Jul 2019 04:50
URI: https://repository.ist.ac.at/id/eprint/146

Actions (login required)

View Item View Item