Deep Dive on Checkers Endgame Data

• Author / Creator

  Wang, Jiuqi

• In this thesis, we investigate applying deep learning techniques to learn the win-loss-draw results contained in the databases of the checkers-playing program CHINOOK. Our initial objectives were to (1) compare a deep-learning-based compression scheme versus the custom algorithm used in CHINOOK, and to (2) extract human-understandable
  features from the data. We have implemented the data processing pipeline, the neural network and its training loop, and an experimentation infrastructure. Our experiment results suggest that (1) training the neural network with a small random subset of the target database can achieve a high accuracy; (2) using the learned network with a naïve one-ply minimax search can further improve the robustness of the predictor most of the time; (3) transfer learning from one database to another one is feasible; (4) dynamically switching between the model and the one-ply search can give a better result than using either exclusively. We conclude that the neural network equipped with search does a decent job compressing the endgame databases, but the custom algorithm is hard to beat. Extracting features that are useful not only to the neural network but also to humans is a tricky task that requires more sophisticated and creative techniques. Our work is the first effort in this direction.

• Subjects / Keywords

  • checkers
  • endgame database
  • deep learning
  • search
  • compression
  • board game
  • artificial neural network

• Graduation date

  Fall 2023

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-zd3k-bf10

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.