Abstract: 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.

Muhammad Suleman, Farrukh Hasan Syed, Tahir Q. Syed, Saqib Arfeen, Sadaf I. Behlim and Behroz Mirza, “Generation of Sokoban Stages using Recurrent Neural Networks” International Journal of Advanced Computer Science and Applications(IJACSA), 8(3), 2017. http://dx.doi.org/10.14569/IJACSA.2017.080364

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