---
_id: '1481'
abstract:
- lang: eng
  text: '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×4 Tic-Tac-Toe opens up new games to be played that have never been played
    as the default start state is heavily biased. '
acknowledgement: "A Technical Report of this paper is available at: \r\nhttps://repository.ist.ac.at/id/eprint/146.\r\n"
article_processing_charge: No
arxiv: 1
author:
- first_name: Umair
  full_name: Ahmed, Umair
  last_name: Ahmed
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Sumit
  full_name: Gulwani, Sumit
  last_name: Gulwani
citation:
  ama: 'Ahmed U, Chatterjee K, Gulwani S. Automatic generation of alternative starting
    positions for simple traditional board games. In: <i>Proceedings of the Twenty-Ninth
    AAAI Conference on Artificial Intelligence</i>. Vol 2. AAAI Press; 2015:745-752.'
  apa: 'Ahmed, U., Chatterjee, K., &#38; Gulwani, S. (2015). Automatic generation
    of alternative starting positions for simple traditional board games. In <i>Proceedings
    of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i> (Vol. 2, pp.
    745–752). Austin, TX, USA: AAAI Press.'
  chicago: Ahmed, Umair, Krishnendu Chatterjee, and Sumit Gulwani. “Automatic Generation
    of Alternative Starting Positions for Simple Traditional Board Games.” In <i>Proceedings
    of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i>, 2:745–52.
    AAAI Press, 2015.
  ieee: U. Ahmed, K. Chatterjee, and S. Gulwani, “Automatic generation of alternative
    starting positions for simple traditional board games,” in <i>Proceedings of the
    Twenty-Ninth AAAI Conference on Artificial Intelligence</i>, Austin, TX, USA,
    2015, vol. 2, pp. 745–752.
  ista: 'Ahmed U, Chatterjee K, Gulwani S. 2015. Automatic generation of alternative
    starting positions for simple traditional board games. Proceedings of the Twenty-Ninth
    AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence
    vol. 2, 745–752.'
  mla: Ahmed, Umair, et al. “Automatic Generation of Alternative Starting Positions
    for Simple Traditional Board Games.” <i>Proceedings of the Twenty-Ninth AAAI Conference
    on Artificial Intelligence</i>, vol. 2, AAAI Press, 2015, pp. 745–52.
  short: U. Ahmed, K. Chatterjee, S. Gulwani, in:, Proceedings of the Twenty-Ninth
    AAAI Conference on Artificial Intelligence, AAAI Press, 2015, pp. 745–752.
conference:
  end_date: 2015-01-30
  location: Austin, TX, USA
  name: 'AAAI: Conference on Artificial Intelligence'
  start_date: 2015-01-25
date_created: 2018-12-11T11:52:16Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2025-05-19T11:10:17Z
day: '01'
department:
- _id: KrCh
ec_funded: 1
external_id:
  arxiv:
  - '1411.4023'
intvolume: '         2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/download/9523/9300
month: '01'
oa: 1
oa_version: None
page: 745 - 752
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
  name: Microsoft Research Faculty Fellowship
publication: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence
publication_status: published
publisher: AAAI Press
publist_id: '5713'
quality_controlled: '1'
related_material:
  record:
  - id: '5410'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Automatic generation of alternative starting positions for simple traditional
  board games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2
year: '2015'
...