AI_LAB10.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "source": [
        "print(\"Ajay N M\\n1BM22CS026\\n\")\n",
        "class Node:\n",
        "    def __init__(self, value=None, children=None):\n",
        "        self.value = value\n",
        "        self.children = children if children else []\n",
        "\n",
        "\n",
        "def alpha_beta_pruning(node, depth, alpha, beta, maximizing_player):\n",
        "    \"\"\"\n",
        "    Perform Alpha-Beta pruning and return the best value for the MAX node.\n",
        "    Also logs the pruning and final values.\n",
        "    \"\"\"\n",
        "    if not node.children or depth == 0:\n",
        "        return node.value\n",
        "\n",
        "    if maximizing_player:\n",
        "        max_eval = float('-inf')\n",
        "        for child in node.children:\n",
        "            eval = alpha_beta_pruning(child, depth - 1, alpha, beta, False)\n",
        "            max_eval = max(max_eval, eval)\n",
        "            alpha = max(alpha, eval)\n",
        "            if beta <= alpha:\n",
        "                print(f\"Pruned at MAX node with alpha={alpha}, beta={beta}\")\n",
        "                break\n",
        "        node.value = max_eval\n",
        "        return max_eval\n",
        "    else:\n",
        "        min_eval = float('inf')\n",
        "        for child in node.children:\n",
        "            eval = alpha_beta_pruning(child, depth - 1, alpha, beta, True)\n",
        "            min_eval = min(min_eval, eval)\n",
        "            beta = min(beta, eval)\n",
        "            if beta <= alpha:\n",
        "                print(f\"Pruned at MIN node with alpha={alpha}, beta={beta}\")\n",
        "                break\n",
        "        node.value = min_eval\n",
        "        return min_eval\n",
        "\n",
        "\n",
        "def print_tree(node, level=0):\n",
        "    \"\"\"Print the game tree with the node values.\"\"\"\n",
        "    print(\"  \" * level + f\"Node Value: {node.value}\")\n",
        "    for child in node.children:\n",
        "        print_tree(child, level + 1)\n",
        "\n",
        "\n",
        "if __name__ == \"__main__\":\n",
        "    # Build the game tree from the question\n",
        "    tree = Node(None, [\n",
        "        Node(None, [\n",
        "            Node(None,[Node(10),Node(9)]),\n",
        "            Node(None, [\n",
        "                Node(14),\n",
        "                Node(18)\n",
        "            ])\n",
        "        ]),\n",
        "        Node(None, [\n",
        "            Node(None, [\n",
        "                Node(5),\n",
        "                Node(4)\n",
        "            ]),\n",
        "            Node(None, [\n",
        "                Node(50),\n",
        "                Node(3)\n",
        "            ])\n",
        "        ])\n",
        "    ])\n",
        "\n",
        "    print(\"Game Tree Before Alpha-Beta Pruning:\")\n",
        "    print_tree(tree)\n",
        "\n",
        "    final_value = alpha_beta_pruning(tree, depth=3, alpha=float('-inf'), beta=float('inf'), maximizing_player=True)\n",
        "\n",
        "    print(\"\\nGame Tree After Alpha-Beta Pruning:\")\n",
        "    print_tree(tree)\n",
        "\n",
        "    print(\"\\nFinal Value at MAX node:\", final_value)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "OwvXvbrmxf0i",
        "outputId": "92dfdae8-f255-44cf-c2d4-9b3d98116b2d"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Ajay N M\n",
            "1BM22CS026\n",
            "\n",
            "Game Tree Before Alpha-Beta Pruning:\n",
            "Node Value: None\n",
            "  Node Value: None\n",
            "    Node Value: None\n",
            "      Node Value: 10\n",
            "      Node Value: 9\n",
            "    Node Value: None\n",
            "      Node Value: 14\n",
            "      Node Value: 18\n",
            "  Node Value: None\n",
            "    Node Value: None\n",
            "      Node Value: 5\n",
            "      Node Value: 4\n",
            "    Node Value: None\n",
            "      Node Value: 50\n",
            "      Node Value: 3\n",
            "Pruned at MAX node with alpha=14, beta=10\n",
            "Pruned at MIN node with alpha=10, beta=5\n",
            "\n",
            "Game Tree After Alpha-Beta Pruning:\n",
            "Node Value: 10\n",
            "  Node Value: 10\n",
            "    Node Value: 10\n",
            "      Node Value: 10\n",
            "      Node Value: 9\n",
            "    Node Value: 14\n",
            "      Node Value: 14\n",
            "      Node Value: 18\n",
            "  Node Value: 5\n",
            "    Node Value: 5\n",
            "      Node Value: 5\n",
            "      Node Value: 4\n",
            "    Node Value: None\n",
            "      Node Value: 50\n",
            "      Node Value: 3\n",
            "\n",
            "Final Value at MAX node: 10\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "5iXDYc1rxuUZ"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}