Generation of Sokoban Stages using Recurrent Neural Networks

Puzzles and board games represent several important classes of AI problems, but also represent difficult complexity classes. In this paper, we propose a deep learning based alternative to train a neural network model to find solution states of the popular puzzle game Sokoban. The network trains against a classical solver that uses theorem proving as the oracle of valid and invalid games states, in a setup that is similar to the popular adversarial training framework. Using our approach, we have been able to verify the validity of a Sokoban puzzle up to an accuracy of 99% on the test set. We have also been able to train our network to generate the next possible state of the puzzle board up to an accuracy of 99% on the validation set. We hope that through this approach, a trained neural network will be able to replace human experts and classical rule-based AI in generating new instances and solutions for such games.

@article{Suleman2017,
  title     = {Generation of Sokoban Stages using Recurrent
Neural Networks},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {8},
  number    = {3},
  year      = {2017},
  publisher = {The Science and Information Organization},
  author    = {Muhammad Suleman and Farrukh Hasan Syed and Tahir Q. Syed and Saqib Arfeen and Sadaf I. Behlim and Behroz Mirza},
  doi       = {10.14569/IJACSA.2017.080364},
  url       = {https://doi.org/10.14569/IJACSA.2017.080364}
}