This is a toy project to create a Tic Tac Toe game that can be played by any two players. The ultimate intention here is to create the game in such a way that it can be played by a human and a computer. The computer will be using the MENACE algorithm to learn how to play the game.
| Platform | Rust Version |Status |
| -------- | ------ | ------ |
| Linux | stable
beta
nightly
MSRV (1.64.0) | 
beta
nightly
MSRV (1.64.0) | 
beta
nightly
MSRV (1.64.0) | 
Machine Educable Noughts and Crosses Engine (MENACE) is one of the first implementations of a mchine learning system. It was developed by Donald Michie in 1961. The original system was developed using a stack of matchboxes over a period of time and was called 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 a number of beads inside, with the number and color of beads representing the next move to be made. The system would play a game of Tic Tac Toe and keep track of the moves made throughout the game. Afterwards, depending on the result of the game (win, lose, draw), the system would either be "rewarded" or "punished" by adding or removing beads from the matchboxes. The system would then play another game and repeat the process.
More information on MENACE can be found here.
This project uses Cargo's workspace feature to organize the project into multiple crates. The following is a brief description of each crate:
tttm: This is a binary crate tasked with actually running the game. This crate is planned to host the player interactions with the GUI or TUI, as it progresses.lib_ttt: This is a library crate that contains the core logic of the game. This crate is responsible for the game logic, the game state, and the game rules.lib_player: This is a library crate that serves two purposes. First, it provides a common interface for the different types of players that can be plugged into the game. Second, it provides a basic implementation for a human player.lib_menace_c: This is a library crate that implements the MENACE-C system. The implementation of this system is based on the interface defined in lib_player.lib_menace_s: This is a library crate that implements the MENACE-S system. The implementation of this system is based on the interface defined in lib_player.Since MENACE was originally designed to not require a computer, we have to make certain adjustments in adapting the Matchbox-based system to a computer-based system. We will follow the following principles in our implementation:
u8 values. Each value will represent the number of beads in the matchbox.Additionally, the original MENACE implementation used a manually curated list of possible game states that treated the rotationally symmetrical board states as equivalent. Since we are not constrained by the number of virtual matchboxes, we will be implementing the MENACE system in two flavors:
The project is currently in the early stages of development. The following is a list of features that will be implemented in the future:
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. Simply click on the button below to start a Gitpod workspace.
This project is dual-licensed under the MIT License and the Apache License (Version 2.0).
This project adheres to the Contributor Covenant Code of Conduct. By participating, you are expected to uphold this code.
This project would not be possible without the efforts of the Rust Community for outreach and training.
I would specifically mention the following people and projects: