Tic-Tac-Toe AI: Reinforcement Learning in Standard ML

Machine Learning | Functional Programming | Game Theory

This project implements a reinforcement learning agent for Tic-Tac-Toe, completely written in Standard ML (SML). It demonstrates how functional programming paradigms can be applied to state-based learning algorithms, featuring an agent that improves its strategy through self-play.

Overview

The AI improves over time through repeated self-play and maintains a memory of game states using a dictionary-based system. The game supports human vs. AI play, with the AI acting as Player O.

Features

• Human vs. AI gameplay: The user plays as Player X against an AI opponent (Player O).
• Game rules enforcement: Ensures valid moves, detects wins, and handles draws.
• AI reinforcement learning: Uses self-play and Q-learning to improve decision-making.
• Dictionary-based AI memory: Stores learned state evaluations for optimal moves.
• Command-line interface: Simple text-based interaction.

Project Structure

• TicTacToe.sml: Core game mechanics and state validation.
• Controller.sml: Game loop managing user interaction and turn cycles.
• Train.sml: The training engine that updates the agent's policy using value iteration.
• Dict.sml: A custom dictionary implementation for storing state-value pairs (the agent's memory).
• Player.sml: Type definitions for human vs. AI players.

AI Learning Process

The agent uses a tabular method where every unique board state is assigned a value.

1. Self-Play: The agent plays thousands of games against itself.
2. Value Update: After each move, the value of the previous state is updated based on the current state's estimated winning probability (Temporal Difference learning).
3. Strategy: In inference mode, the agent selects the move that transitions to the state with the highest stored value.

Installation

Requires an SML compiler (e.g., SML/NJ).

sml
- use "TicTacToe.sml";
- use "Train.sml";