Reinforcement Learning For Constraint Satisfaction Game Agents (15-Puzzle, Minesweeper, 2048, and Sudoku)

In recent years, reinforcement learning has seen interest because of deep\nQ-Learning, where the model is a convolutional neural network. Deep Q-Learning\nhas shown promising results in games such as Atari and AlphaGo. Instead of\nlearning the entire Q-table, it learns an estimate of the Q function that\ndetermines a state's policy action. We use Q-Learning and deep Q-learning, to\nlearn control policies of four constraint satisfaction games (15-Puzzle,\nMinesweeper, 2048, and Sudoku). 15-Puzzle is a sliding permutation puzzle and\nprovides a challenge in addressing its large state space. Minesweeper and\nSudoku involve partially observable states and guessing. 2048 is also a sliding\npuzzle but allows for easier state representation (compared to 15-Puzzle) and\nuses interesting reward shaping to solve the game. These games offer unique\ninsights into the potential and limits of reinforcement learning. The Q agent\nis trained with no rules of the game, with only the reward corresponding to\neach state's action. Our unique contribution is in choosing the reward\nstructure, state representation, and formulation of the deep neural network.\nFor low shuffle, 15-Puzzle, achieves a 100% win rate, the medium and high\nshuffle achieve about 43% and 22% win rates respectively. On a standard 16x16\nMinesweeper board, both low and high-density boards achieve close to 45% win\nrate, whereas medium density boards have a low win rate of 15%. For 2048, the\n1024 win rate was achieved with significant ease (100%) with high win rates for\n2048, 4096, 8192 and 16384 as 40%, 0.05%, 0.01% and 0.004% , respectively. The\neasy Sudoku games had a win rate of 7%, while medium and hard games had 2.1%\nand 1.2% win rates, respectively. This paper explores the environment\ncomplexity and behavior of a subset of constraint games using reward structures\nwhich can get us closer to understanding how humans learn.\n