Logic-based AI for Interpretable Board Game Winner Prediction with Tsetlin Machine

Charul Giri, Ole-Christoffer Granmo, Herke van Hoof, Christian D. Blakely

TL;DR

Researchers have successfully applied Tsetlin Machines (TM) to predict winners in the complex board game Hex, achieving a 92.1% accuracy that outperforms both deep neural networks and gradient-boosted trees. Unlike traditional "black-box" models, this approach uses propositional logic to create human-readable rules, allowing players to see exactly which board patterns the AI uses to make its decisions.

What Problem Does This Paper Address?

In the world of competitive board games, state-of-the-art AIs (like AlphaZero) rely on deep neural networks to evaluate positions. While these models are incredibly accurate, they are "black boxes"—their internal reasoning is hidden behind millions of weights and non-linear transformations.

This lack of transparency is a major hurdle for human-AI collaboration. If an AI suggests a move or predicts a win, a human player cannot easily understand why. Existing "post-hoc" explanation methods (like LIME) are often just approximations and can be misleading. The authors tackle the "interpretability-accuracy trade-off," seeking a model that is both highly accurate and inherently transparent.

Methods

The authors employ the Tsetlin Machine (TM), a relatively new logic-based machine learning algorithm.

  1. Logic-Based Learning: Instead of adjusting weights, the TM uses a team of Tsetlin Automata to learn patterns expressed as conjunctive clauses (AND-rules). For example, a rule might look like: "If there is a Black piece at d2 AND no White piece at f1, then Black is likely to win."
  2. Feature Representation: For a 6×6 Hex board, the input is converted into a 72-bit vector (36 bits for Black piece locations and 36 for White).
  3. Feedback Loops: The model uses two types of feedback:
  4. Type I: Encourages the model to remember and refine patterns it sees frequently.
  5. Type II: Increases the "discrimination power," helping the model avoid false positives by penalizing rules that are too broad.
  6. Interpretability: Because the model is built on propositional logic, the "clauses" can be mapped directly back onto the game board and visualized, providing both global interpretability (what the model knows about the game in general) and local interpretability (why it made a specific prediction for the current board).

Datasets

The study used a dataset of 287,794 game board configurations generated through self-play using a modified version of MoHex2.0 (a top-tier Hex engine using Monte Carlo Tree Search).

  • Board Size: 6×6.
  • Game Stages: Configurations ranged from 2 to 22 moves played, covering early, middle, and end-game states.
  • Distribution: 175,968 Black wins and 111,826 White wins.

Key Insights and Ideas

  • Challenging the Trade-off: The paper disputes the common assumption that you must sacrifice accuracy to get interpretability. By using an adequate problem representation (logic clauses), the TM achieved higher accuracy than complex black-box models.
  • Capturing Strategy: The TM naturally learned fundamental Hex strategies, such as "bridge patterns" and "virtual connections," which are concepts human experts use to secure a win.
  • Stage-Agnostic Performance: Interestingly, the TM's accuracy remained high and stable across all stages of the game. It was nearly as good at predicting the winner after just a few moves as it was in the endgame.
  • Voting Mechanism: The TM doesn't rely on a single rule; it uses a majority vote across thousands of learned clauses, which provides a robust "confidence" measure for its predictions.

Key Results

  • Superior Accuracy: The Tsetlin Machine achieved a testing accuracy of 92.1%.
  • Benchmarks: It outperformed several popular ML algorithms:
  • Neural Networks: 90.7%
    • XGBoost: 88.9%
    • Decision Trees: 87.1%
    • InterpretML (EBC): 74.3%
  • Visual Evidence: The authors demonstrated that by aggregating "True" clauses, they could produce heatmaps (Local Aggregated Interpretation) that highlight the most critical strategic areas of a specific board state.

Limitations and Future Work

  • Board Scaling: This study focused on 6×6 boards. Standard competitive Hex is played on 11×11 or 13×13 boards. Scaling the logic-based approach to these larger state spaces remains a challenge for future research.
  • From Prediction to Action: Currently, the model only predicts the winner. The authors plan to extend this to predicting the winning move, which would turn the TM into a fully functional, interpretable game-playing agent.
  • Hyperparameter Optimization: The authors noted that their results were achieved with limited manual tuning of the 's' (specificity) parameter; automated grid searches might push accuracy even higher.

Summary updated

Abstract

Hex is a turn-based two-player connection game with a high branching factor, making the game arbitrarily complex with increasing board sizes. As such, top-performing algorithms for playing Hex rely on accurate evaluation of board positions using neural networks. However, the limited interpretability of neural networks is problematic when the user wants to understand the reasoning behind the predictions made. In this paper, we propose to use propositional logic expressions to describe winning and losing board game positions, facilitating precise visual interpretation. We employ a Tsetlin Machine (TM) to learn these expressions from previously played games, describing where pieces must be located or not located for a board position to be strong. Extensive experiments on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$6\times 6$</tex> boards compare our TM-based solution with popular machine learning algorithms like XGBoost, InterpretML, decision trees, and neural networks, considering various board configurations with 2 to 22 moves played. On average, the TM testing accuracy is 92.1%, outperforming all the other evaluated algorithms. We further demonstrate the global interpretation of the logical expressions, and map them down to particular board game configurations to investigate local interpretability. We believe the resulting interpretability establishes building blocks for accurate assistive AI and human-AI collaboration, also for more complex prediction tasks.
BibTeX
@inproceedings{giri2022logic,
  author = {Charul Giri and Ole-Christoffer Granmo and Herke van Hoof and Christian D. Blakely},
  title = {{Logic-based AI for Interpretable Board Game Winner Prediction with Tsetlin Machine}},
  booktitle = {IJCNN},
  year = {2022},
  doi = {10.1109/ijcnn55064.2022.9892796},
}
Figure