What is it about?

This study introduces a blazingly fast, no-loss expert system for tic-tac-toe using decision trees called T3DT, which tries to emulate human gameplay as closely as possible. It does not make use of any brute force, minimax, or evolutionary techniques, but is still always unbeatable. To make the gameplay more human-like, randomisation is prioritised and T3DT randomly chooses one of the multiple optimal moves at each step. Since it does not need to analyse the complete game tree at any point, T3DT is exceptionally faster than any brute force or minimax algorithm, this has been shown theoretically as well as empirically from clock-time analyses in this study. T3DT also does not need the data sets or the time to train an evolutionary model, making it a practical no-loss approach to play tic-tac-toe.

Featured Image

Why is it important?

Many minimax based strategies can play the game without losing, but that is useless for playing with a human, as they will be easily bored when the computer makes the same optimal starting moves or the same move sequences to the human player's opening. We also study the massive improvements compared to minimax based approaches in terms of speed and promise a highly randomized sequence of perfect moves.

Perspectives

Making decisions is an important part of game theory. Traditionally various approaches have been used like starting books etc. But those were hardcoded, often non-randomized moves. In recent times, machine learning has gained massive popularity for solving problems so complex that rules cannot be written for playing them effectively, but are often black-box. We show that rather then going to either of these extremes, trying to develop meaningful herusitics, which can then be used to play the games, provides an explainable, fast and effective strategy that can also be used to test games being played by other automated systems.

Aditya Jyoti Paul
Cognitive Applications Research Lab

Read the Original

This page is a summary of: Randomised fast no-loss expert system to play tic-tac-toe like a human, Cognitive Computation and Systems, September 2020, the Institution of Engineering and Technology (the IET),
DOI: 10.1049/ccs.2020.0018.
You can read the full text:

Read

Resources

Contributors

The following have contributed to this page