Logic-based AI for Interpretable Board Game Winner Prediction with
Tsetlin Machine
- URL: http://arxiv.org/abs/2203.04378v1
- Date: Tue, 8 Mar 2022 20:10:25 GMT
- Title: Logic-based AI for Interpretable Board Game Winner Prediction with
Tsetlin Machine
- Authors: Charul Giri, Ole-Christoffer Granmo, Herke van Hoof, Christian D.
Blakely
- Abstract summary: We propose to use propositional logic expressions to describe winning and losing board game positions.
We employ a Tsetlin Machine (TM) to learn these expressions from previously played games.
On average, the TM testing accuracy is $92.1%$, outperforming all the other evaluated algorithms.
- Score: 23.83480738752374
- License: http://creativecommons.org/licenses/by/4.0/
- 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 $6\times6$ 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.
Related papers
- Denoising Opponents Position in Partial Observation Environment [0.4660328753262075]
Soccer Simulation 2D (SS2D) match involves two teams, including 11 players and a coach for each team, competing against each other.
We will explain our position prediction idea powered by Long Short-Term Memory models (LSTM) and Deep Neural Networks (DNN)
arXiv Detail & Related papers (2023-10-23T04:16:52Z) - Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
We study multi-agent general-sum Markov games with nonlinear function approximation.
We focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure on top of an unknown non-linear representation.
arXiv Detail & Related papers (2022-10-30T22:58:22Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
We develop the concepts of Mean-Field correlated and coarse-correlated equilibria.
We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
arXiv Detail & Related papers (2022-08-22T08:31:46Z) - Dual Lottery Ticket Hypothesis [71.95937879869334]
Lottery Ticket Hypothesis (LTH) provides a novel view to investigate sparse network training and maintain its capacity.
In this work, we regard the winning ticket from LTH as the subnetwork which is in trainable condition and its performance as our benchmark.
We propose a simple sparse network training strategy, Random Sparse Network Transformation (RST), to substantiate our DLTH.
arXiv Detail & Related papers (2022-03-08T18:06:26Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
We present the first line of algorithms that require only $widetildemathcalO((XA+YB)/varepsilon2)$ episodes of play to find an $varepsilon$-approximate Nash equilibrium in two-player zero-sum games.
This improves upon the best known sample complexity of $widetildemathcalO((X2A+Y2B)/varepsilon2)$ by a factor of $widetildemathcalO(maxX,
arXiv Detail & Related papers (2022-02-03T18:18:28Z) - Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents.
We focus on the solution concept of Nash equilibria (NE)
We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
arXiv Detail & Related papers (2021-11-07T21:15:35Z) - Discovering Multi-Agent Auto-Curricula in Two-Player Zero-Sum Games [31.97631243571394]
We introduce a framework, LMAC, that automates the discovery of the update rule without explicit human design.
Surprisingly, even without human design, the discovered MARL algorithms achieve competitive or even better performance.
We show that LMAC is able to generalise from small games to large games, for example training on Kuhn Poker and outperforming PSRO.
arXiv Detail & Related papers (2021-06-04T22:30:25Z) - Evolving Evaluation Functions for Collectible Card Game AI [1.370633147306388]
We presented a study regarding two important aspects of evolving feature-based game evaluation functions.
The choice of genome representation and the choice of opponent used to test the model were studied.
We encoded our experiments in a programming game, Legends of Code and Magic, used in Strategy Card Game AI Competition.
arXiv Detail & Related papers (2021-05-03T18:39:06Z) - Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
We consider a repeated sequential game between a learner, who plays first, and an opponent who responds to the chosen action.
We propose a novel algorithm for the learner when playing against an adversarial sequence of opponents.
Our results include algorithm's regret guarantees that depend on the regularity of the opponent's response.
arXiv Detail & Related papers (2020-07-10T09:33:05Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
We consider the problem of $K$-armed dueling bandit in the contextual setting.
We present two algorithms for the setup with respective regret guarantees.
arXiv Detail & Related papers (2020-02-20T06:36:19Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games.
In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap.
In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
arXiv Detail & Related papers (2020-02-17T17:04:16Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.