Tic-Tac-Rustle - A Tic-Tac-Toe Game with MENACE

This project develops a Tic-Tac-Toe game in Rust with MENACE AI. It offers a server-client setup where users can play against a cloud-hosted MENACE AI or deploy their own locally.

Builds

	Stable	Beta	Nightly	MSRV (1.72.0)
Linux
Windows
macos

MENACE

Machine Educable Noughts and Crosses Engine (MENACE) is one of the first implementations of a machine learning system. Donald Michie developed it in 1961 while working at University of Edinburgh. The original system used a stack of matchboxes labeled with possible game states, along with a reinforcement learning algorithm, to learn the optimal strategy over a certain number of games. Michie called this system Matchbox Educable Noughts and Crosses Engine (MENACE).

This was one of the first systems to use reinforcement learning to learn how to play a game and the first to prove that a machine could learn how to play a game without being explicitly programmed to do so.

The classical MENACE system consisted of 304 matchboxes. Each matchbox represented a possible state of the game. Each matchbox had up to nine colored beads inside, with the number and color of beads representing the next move on the 3 X 3 board. The player would make the first move, and then draw a random bead from the matchbox matching the state of the game. This represents the move that MENACE has chosen to make. The process continues until the player or MENACE wins the game. If MENACE wins, the player returns the beads to the matchbox, along with extra beads for the winning move. If the player wins, the player does not return the beads to the matchbox. This process repeats until MENACE achieves the optimal strategy.

More information on MENACE is available here.

Project Structure

This project has three parts:

• lib_tictacrustle: This is the library crate that contains the core logic of the game. This crate manages the game logic, the game state, and the game rules. This crate is also responsible for the MENACE system.
• ttrustle: This is a binary crate tasked with actually running the game. This crate hosts the player interactions with the GUI[^1] and TUI[^2], as it progresses.
• ttserver: This is a binary crate that hosts the MENACE AI. This crate handles running the MENACE system and providing an API for the ttrustle binary to interact with.

MENACE Implementation

Since MENACE predates both the internet and consumer computers, the original implementation was purely matchbox-based. In translating that system to a modern incarnation, we adhere to the following principles:

• A database replaces the matchboxes used in the original implementation.
• The game runs as a client-server system that has independent clients and servers.
• The server along with the database and API is usable both locally and in the cloud.

The original MENACE implementation used a manually curated list of possible game states that treated the rotationally symmetrical board states as the same. Since this implementation is not constrained by the number of virtual matchboxes, we build the MENACE system in two flavors:

1. MENACE-C: This is the classic MENACE system that treats the rotationally symmetrical board states as the same.
2. MENACE-S: This is the MENACE system that treats the rotationally symmetrical board states as distinct.

Roadmap

The project is in its initial stages of development. The following list includes features that we plan to add in the future:

• Add the base game logic.
• Add the human player.
• Add the MENACE-C system.
• Add the MENACE-S system.
• Add the Command-line Interface (CLI).
• Add a Terminal User Interface (TUI).
• Add a Graphical User Interface (GUI).

Contributing

Contributions to the project are welcome. Please see the Contributing Guidelines for more information.

This project is Gitpod-enabled. You can use Gitpod to contribute to the project without having to install any dependencies on your local machine. You can click the button below to start a Gitpod workspace with a complete development environment.

License

This project is dual-licensed under the MIT License and the Apache License (Version 2.0). You may choose to use this project under either license, at your discretion. Other, insignificant files are under the CC0 License. Please see the LICENSES directory for more information.

This project is REUSE compliant. You can find more information about REUSE here.

Code of Conduct

This project adheres to the Contributor Covenant Code of Conduct. By participating, You are expected to uphold this code.

Acknowledgements

This project would not be possible without the efforts of the Rust Community for outreach and training.

Specific people and projects worth mentioning:

• Chris Krycho and the New Rustacean Podcast.
• Bogdan Pshonyak and the Let's Get Rusty YouTube Channel.
• Tris Oaten (NAMTAO) and the No Boilerplate YouTube Channel.
• My loving family for their support and encouragement.

[^1]: Graphical User Interface [^2]: Terminal User Interface