Automatic Generation of Alternative Starting Positions for Simple
  Traditional Board Games
  Simple board games, like Tic-Tac-Toe and CONNECT-4, play an important role
not only in the development of mathematical and logical skills, but also in the
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. We present an approach that 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. The presence of such states for standard game variants like $4
\times 4$ Tic-Tac-Toe opens up new games to be played that have never been
played as the default start state is heavily biased.
