Chopsticks AI: Q-Learning Agent

This project implements an AI agent that learns to play the traditional game of Chopsticks using the Q-learning reinforcement learning algorithm. The AI (Player 0) trains against a random opponent (Player 1) to learn optimal strategies for winning the game.

Game Rules (Chopsticks)

Chopsticks is a simple two-player game played with hands.

• Each player starts with one finger extended on each hand (e.g., 1-1).
• Turns: Players take turns.
• Moves:
  1. Attack: A player uses one of their hands to tap an opponent's hand. The number of fingers on the tapping hand is added to the tapped hand. If the total reaches 5 or more, the tapped hand becomes 0 (it's "out"). The tapping hand (the one that initiated the attack) also becomes 0.
  2. Split (or Transfer): A player can redistribute fingers between their own two hands. For example, if a player has 4-0, they can split to 2-2. The total number of fingers must remain the same, and neither hand can exceed 4 fingers (if it does, it becomes 0). This move can only be done if both hands are active (not 0).
• Winning: A player wins when their opponent has no active hands (both hands are 0).
• Losing: A player loses when they have no active hands.

Mathematical & Algorithmic Steps

The core of this AI is Q-learning, a model-free reinforcement learning algorithm.

1. Markov Decision Process (MDP) Formulation

The game of Chopsticks can be modeled as a finite MDP:

• States ($S$): A state is defined by the number of fingers on each of the four hands: (player_0_left_hand, player_0_right_hand, player_1_left_hand, player_1_right_hand). Each hand can have 0, 1, 2, 3, or 4 fingers. States where both hands of a player are 0 represent a terminal (win/loss) state.
  • Example: (1, 1, 1, 1) is the initial state. (0, 0, 2, 1) means Player 0 has lost, and Player 1 has 2 fingers on their left hand and 1 on their right.
• Actions ($A$): An action is a specific move defined by:
  • [sender_player, target_player, sender_hand_LR, target_hand_LR, amount]
  • sender_player: 0 (AI) or 1 (Opponent)
  • target_player: 0 (AI) or 1 (Opponent)
  • sender_hand_LR: 0 (Left Hand) or 1 (Right Hand) of the sender.
  • target_hand_LR: 0 (Left Hand) or 1 (Right Hand) of the target.
  • amount: Only relevant for 'split' moves (sender == target). For 'attack' moves, the amount is implicitly the number of fingers on the sender_hand.
• Reward Function ($R(s, a, s')$): The reward signal guides the AI's learning.
  • If the AI (Player 0) wins (opponent's hands become 0-0): $R = +100$
  • If the AI (Player 0) loses (its own hands become 0-0): $R = -100$
  • For any non-terminal state transition: $R = -1$ (This encourages the AI to win quickly and avoid prolonged losing games).
• Policy ($\pi(a|s)$): A strategy that the agent learns, mapping states to actions.

2. Q-Learning Algorithm

Q-learning is an off-policy temporal difference control algorithm that learns an action-value function, denoted as $Q(s, a)$. This function estimates the expected total future reward for taking action $a$ in state $s$, and then following an optimal policy thereafter.

The update rule for $Q(s, a)$ is:

$Q(s, a) \leftarrow Q(s, a) + \alpha [R + \gamma \max_{a'} Q(s', a') - Q(s, a)]$

Where:

• $Q(s, a)$: The current Q-value for state $s$ and action $a$.
• $\alpha$ (Learning Rate): self.alpha = 0.1. Determines how much new information overrides old information. A value of 0 makes the agent learn nothing, while a value of 1 makes the agent consider only the most recent information.
• $R$: The immediate reward received after taking action $a$ from state $s$ and transitioning to state $s'$.
• $\gamma$ (Discount Factor): self.gamma = 0.9. Determines the importance of future rewards. A value of 0 makes the agent "myopic" (only consider immediate rewards), while a value close to 1 makes it strive for long-term high rewards.
• $\max_{a'} Q(s', a')$: The maximum Q-value for the next state $s'$ (the state after both the AI's move and the opponent's move), across all possible actions $a'$ that the agent could take from $s'$. This represents the estimated optimal future value.
• $s'$: The next state after the agent takes action $a$ and the opponent takes their turn.

3. Exploration-Exploitation Strategy (Epsilon-Greedy)

During training, the AI balances exploration (trying new actions to discover better strategies) and exploitation (choosing the best-known action based on current Q-values). This is achieved using an $\epsilon$-greedy policy:

• With probability $\epsilon$ (exploration rate): The agent chooses a random action from the set of possible actions.
• With probability $1 - \epsilon$ (exploitation rate): The agent chooses the action with the highest Q-value for the current state.

The $\epsilon$ value decreases over time (self.epsilon_decay) to transition from more exploration in early stages to more exploitation in later stages.

• self.epsilon = 1.0 (starts with pure exploration).
• self.epsilon_decay = 0.9999 (epsilon is multiplied by this factor after each episode, causing it to decrease slowly).
• self.epsilon_min = 0.05 (epsilon will not fall below this value, ensuring some minimal exploration throughout training).

4. Training Process

The training process involves running multiple episodes (games) where the AI learns from its interactions:

1. Initialize: The Q-table is initialized with zeros for all state-action pairs.
2. Episode Loop: For each episode:
   • The game starts from the initial state (1, 1, 1, 1).
   • Turn Loop (until terminal state):
     • AI's Turn:
       • The AI chooses an action using the $\epsilon$-greedy strategy.
       • The game state transitions to s_prime_agent.
       • If s_prime_agent is a terminal state, the episode ends for the AI's perspective, and the Q-table is updated with the final reward.
     • Opponent's Turn:
       • If s_prime_agent is not terminal, the opponent (which uses a purely random policy) makes a move.
       • The game state transitions to s_prime_full_turn.
       • Q-Table Update: The Q-table for the AI's previous action (s, a) is updated using the reward obtained in s_prime_full_turn and the maximum Q-value from s_prime_full_turn. This is crucial as the AI's learning accounts for the opponent's immediate response.
       • current_state for the next iteration becomes s_prime_full_turn.
       • If s_prime_full_turn is a terminal state, the episode ends.
   • Epsilon Decay: After each episode, $\epsilon$ is decayed (epsilon = max(epsilon_min, epsilon * epsilon_decay)).
3. Save Q-table: After training, the learned Q-table is saved to a JSON file (q_table.json) for later use.

Setup and Getting Started

Prerequisites

• Python 3.x

Installation

1. Clone the repository (or save the code):

   # If this were a Git repository
   # git clone <repository_url>
   # cd chopsticks-ai

   For now, simply save the provided Python code as solve.py and the interface.py (if you have one) in the same directory.

Training the AI

To train the Q-learning agent and generate the q_table.json file:

1. Open your terminal or command prompt.
2. Navigate to the directory where you saved solve.py.
3. Run the training script:

   python3 solve.py

   This process can take a significant amount of time (e.g., several hours for 1,000,000 episodes) depending on your system specifications. You will see progress updates printed to the console.

Playing Against the AI

Once the q_table.json file has been generated by the training script, you can play against the trained AI.

1. Ensure you have an interface.py file that loads the q_table.json and implements the human-AI interaction. (If you don't have this, you'll need to create it based on your previous examples).
2. Run the interface script:

   python3 interface.py

   Follow the on-screen prompts to make your moves. The AI will then make its move based on its learned Q-table.

Project Structure

• solve.py: Contains the State, Action, and Solve classes, implementing the Q-learning algorithm and the training loop.
• q_table.json: (Generated after training) Stores the learned Q-values.
• interface.py: (Assumed) Script for human players to interact with the trained AI.

Future Improvements

• Smarter Opponent during Training: Implement a more sophisticated opponent policy (e.g., a simple heuristic AI, or another learning agent in a self-play setup) to train the AI against a more challenging adversary.
• Deep Q-Networks (DQN): For larger state spaces or more complex games, replacing the explicit Q-table with a neural network (DQN) can generalize better.
• Experience Replay: Store past experiences in a replay buffer and sample from them to train the network, improving learning stability.
• Policy Gradient Methods: Explore alternative reinforcement learning algorithms that directly learn a policy.

---