{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f8805037",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Q6C(a-b): Set up the Tic-Tac-Toe environment and game rules.\n",
    "from collections import defaultdict\n",
    "import numpy as np\n",
    "WIN_LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8),\n",
    "             (0, 3, 6), (1, 4, 7), (2, 5, 8),\n",
    "             (0, 4, 8), (2, 4, 6)]\n",
    "def winner(board):\n",
    "    for a, b, c in WIN_LINES:\n",
    "        if board[a] != 0 and board[a] == board[b] == board[c]:\n",
    "            return board[a]\n",
    "    return 0\n",
    "def available(board):\n",
    "    return [i for i, value in enumerate(board) if value == 0]\n",
    "def show(board):\n",
    "    symbols = {1: \"X\", -1: \"O\", 0: \".\"}\n",
    "    print(\"\\n\".join(\" \".join(symbols[v] for v in board[i:i + 3])\n",
    "                    for i in (0, 3, 6)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "071fca24",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Q6C(c): Q-learning agent X plays against a random opponent O.\n",
    "# The state is the board immediately before X's turn.\n",
    "q = defaultdict(lambda: np.zeros(9))\n",
    "rng = np.random.default_rng(42)\n",
    "alpha, gamma = 0.25, 0.95\n",
    "def choose_action(board, epsilon):\n",
    "    legal = available(board)\n",
    "    if rng.random() < epsilon:\n",
    "        return int(rng.choice(legal))\n",
    "    values = q[tuple(board)][legal]\n",
    "    best = [a for a, value in zip(legal, values) if value == max(values)]\n",
    "    return int(rng.choice(best))\n",
    "def play_episode(epsilon, learn=True):\n",
    "    board = [0] * 9\n",
    "    while True:\n",
    "        state = tuple(board)\n",
    "        action = choose_action(board, epsilon)\n",
    "        board[action] = 1\n",
    "        if winner(board) == 1:\n",
    "            reward, result = 1.0, \"win\"\n",
    "            break\n",
    "        if not available(board):\n",
    "            reward, result = 0.2, \"draw\"\n",
    "            break\n",
    "        board[int(rng.choice(available(board)))] = -1\n",
    "        if winner(board) == -1:\n",
    "            reward, result = -1.0, \"loss\"\n",
    "            break\n",
    "        if not available(board):\n",
    "            reward, result = 0.2, \"draw\"\n",
    "            break\n",
    "        if learn:\n",
    "            next_state = tuple(board)\n",
    "            target = gamma * max(q[next_state][available(board)])\n",
    "            q[state][action] += alpha * (target - q[state][action])\n",
    "    if learn:\n",
    "        q[state][action] += alpha * (reward - q[state][action])\n",
    "    return result, board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "d9f29a78",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Training results: {'win': 25201, 'draw': 1774, 'loss': 3025}\n",
      "Learned board states: 2415\n"
     ]
    }
   ],
   "source": [
    "# Q6C(d): Train through repeated games, gradually reducing exploration.\n",
    "training_results = {\"win\": 0, \"draw\": 0, \"loss\": 0}\n",
    "for episode in range(30000):\n",
    "    epsilon = max(0.05, 1 - episode / 24000)\n",
    "    result, _ = play_episode(epsilon)\n",
    "    training_results[result] += 1\n",
    "print(\"Training results:\", training_results)\n",
    "print(\"Learned board states:\", len(q))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "b6568b59",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test results (1000 games): {'win': 989, 'draw': 11, 'loss': 0}\n",
      "Win rate: 0.989\n",
      "Example game (X=agent, O=random opponent):\n",
      "O . X\n",
      ". X .\n",
      "X O .\n",
      "Result: win\n"
     ]
    }
   ],
   "source": [
    "# Q6C(e): Test the learned greedy policy against new random games.\n",
    "test_results = {\"win\": 0, \"draw\": 0, \"loss\": 0}\n",
    "for _ in range(1000):\n",
    "    result, _ = play_episode(epsilon=0, learn=False)\n",
    "    test_results[result] += 1\n",
    "print(\"Test results (1000 games):\", test_results)\n",
    "print(\"Win rate:\", round(test_results[\"win\"] / 1000, 3))\n",
    "print(\"Example game (X=agent, O=random opponent):\")\n",
    "result, final_board = play_episode(epsilon=0, learn=False)\n",
    "show(final_board)\n",
    "print(\"Result:\", result)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}