Muehle_Algo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "%%HTML\r\n",
    "<style>\r\n",
    ".container { width:100% }\r\n",
    "</style>"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Algorithmen"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "%run ./Muehle_Logic.ipynb\r\n",
    "%run ./Muehle_Heuristic.ipynb"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "Cache_Memoize = {}"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Memoisierung\n",
    "Die nachfolgende Memoisierungsfunktion `memoize(f)` wird im Rahmen des Minimax-Algorithmus verwendet, um zu `value_minimax(state, player, depth)` einen Cache hinzuzufügen. Als Schlüssel zur Zwischenspeicherung der berechneten Werte wird ein Tupel aus Status, Spieler und Suchtiefe verwendet (Argumente von `value_minimax()`)."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "def memoize(f):\r\n",
    "    global Cache_Memoize\r\n",
    "    \r\n",
    "    def f_memoized(*args):\r\n",
    "        if args in Cache_Memoize:\r\n",
    "            return Cache_Memoize[args]\r\n",
    "        result = f(*args)\r\n",
    "        Cache_Memoize[args] = result\r\n",
    "        return result\r\n",
    "    return f_memoized"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Minimax-Algorithmus\r\n",
    "\r\n",
    "Der Minimax-Algorithmus wird im Rahmen dieser Studienarbeit für die Ermittlung der optimalen Strategie für das Nullsummenspiel Mühle verwendet. Bei einem Nullsummenspiel wie Mühle ist der Gewinn eines Spielers gleichzeitig der Verlust des anderen Spielers. Die Summe ist somit null. Der Minimax-Algorithmus ist hierbei ein relativ einfacher Algorithmus für Nullsummenspiele, der durch die spätere Verwendung von Alpha-Beta-Pruning deutlich verbessert werden kann.\r\n",
    "\r\n",
    "Der Minimax-Algorithmus beruht auf einer Bewertungsfunktion, der Heuristik und systematischer Suche. Grundlegend werden bei Minimax alle auf den aktuellen Spielstatus folgenden Zustände berechnet und bewertet. Dies ist vergleichbar mit einer Baumstruktur, bei der bis zu den Blättern alle Zustände ausgewertet werden. Da dies aus Gründen der Rechenzeit und des Speichers nicht möglich ist, werden die Folgezustände nur bis zu einer gewissen Tiefe berechnet und ausgewertet. Um nur bis zu einer geringen Baumtiefe suchen zu müssen wird allerdings eine geeignete Heuristik benötigt, da wir mit der übergebenen Suchtiefe nicht immer einen Endzustand erreichen und den Zustand somit nicht eindeutig bewerten können. Mit der Nutzung dieser Heuristik verlieren wir also die Sicherheit den optimalen Zug zu wählen, erhalten aber immerhin eine gute Einschätzung und eine akzeptable Rechenzeit. Ohne eine Heuristik müssten wir alle Spielverläufe im Vorfeld ausrechnen, was bei nicht trivialen Nullsummenspielen äußerst aufwendig, beziehungsweise nicht möglich ist.\r\n",
    "\r\n",
    "Minimax-Baumstruktur-Beispiel:\r\n",
    "Die Werte innerhalb der Knoten/Blätter entsprechen der Bewertung des jeweiligen Zustandes\r\n",
    "\r\n",
    "<img src=\"images/minimax.png\" width=\"800\"/>\r\n",
    "\r\n",
    "Quelle: (https://stackabuse.com/minimax-and-alpha-beta-pruning-in-python/) [Mina Krivokuća, 2019]\r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Die Funktion `value_minimax(state, player, depth)` erhält drei Argumente. Einen Spielzustand, einen Spieler und die Suchtiefe. Die Funktion gibt dabei den Wert zurück, den der übergebene Spielzustand für den übergeben Spieler hat.\n",
    "Dieser Wert wird, für den Fall, dass das Spiel mit dem übergebenen Zustand beendet ist, von der Funktion `utility()` berechnet. Wenn die maximale Suchtiefe erreicht wurde wird der Wert allerdings von der Funktion `heuristic()` berechnet.\n",
    "Ist die maximale Suchtiefe noch nicht erreicht wird rekursiv nach dem besten Folgezustand gesucht.\n",
    "Um Werte für Zustände nicht mehrfach berechnen zu müssen werden diese durch Memoisation `@memoize` zwischengespeichert.\n"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "@memoize\r\n",
    "def value_minimax(state, player, depth):\r\n",
    "    if finished(to_list(state), player):\r\n",
    "        return utility(to_list(state), player)\r\n",
    "    if depth == 0:\r\n",
    "        return heuristic(state, player)\r\n",
    "    o = opponent(player)\r\n",
    "    depth -= 1\r\n",
    "    return max([ -value_minimax(to_tuple(ns), o, depth) for ns in next_states(to_list(state), player) ])"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Die Funktion `best_move_minimax(state, player, depth)` erhält drei Argumente. Einen Spielzustand, einen Spieler und die Suchtiefe. Die Rückgabewerte sind, der von der Funktion ermittelte, beste Folgezustand und dessen Bewertung. Gibt es mehrere beste Folgezustände wird der Folgezustand zufällig ausgewählt.\n",
    "\n",
    "Die besten Züge werden von der Funktion durch das wiederholte negierte Aufrufen der Funktion `value_minimax()` bestimmt, da für den Folgezustand mit dem Gegner als Spieler gesucht werden muss. Genauer gesagt müssen wir, da wir uns in einem Nullsummenspiel befinden, die Bewertungen für alle berechneten Züge negieren, um für den, der Funktion `best_move_minimax()`, übergebenen Spieler den besten Zug zu wählen."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "def best_move_minimax(state, player, depth):\r\n",
    "    ns          = next_states(state, player)\r\n",
    "    best_value  = value_minimax(to_tuple(state), player, depth)\r\n",
    "    best_moves  = [s for s in ns if -value_minimax(to_tuple(s), opponent(player), depth - 1 ) == best_value]\r\n",
    "    best_state  = random.choice(best_moves)\r\n",
    "    return best_value, best_state"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Die Funktion `minimax(state, player, depth)` wurde erstellt, um die Funktion `best_move_minimax()` nach außen hin eindeutiger von `best_move_ab()` abzugrenzen. Die übergebenen Argumente und Rückgabewerte entsprechen somit denen der Funktion `best_move_minimax()`."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "def minimax(state, player, depth = 5):\r\n",
    "    return(best_move_minimax(state, player, depth))"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Alpha-Beta-Pruning\n",
    "Das Alpha-Beta-Pruning ist, wie im Rahmen des Minimax-Algorithmus schon erwähnt eine Verbesserung von Minimax. Beim Alpha-Beta-Pruning wird die Auswertung von Teilbäumen abgebrochen, sobald klar ist, dass keine Verbesserung erwartbar ist. Durch diese Technik wird die Rechenzeit bei steigender Suchtiefe gegenüber Minimax erheblich reduziert. \n",
    "Das Hauptkonzept von Alpha-Beta-Pruning besteht darin, die Werte Alpha und Beta über die gesamte Suche hinweg mitzunehmen. Alpha enthält dabei den bestmöglichen Wert der erkundeten Optionen für den maximierenden Spieler und Beta das gleiche für den minimierenden Spieler, wobei Alpha und Beta initial auf dem für Alpha und Beta schlechtesten Wert starten. (Alpha = -1, Beta = 1)"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "Cache_AB = {}"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Der Funktion `value_ab(state, player, alpha=-1, beta=1)` werden vier Argumente übergeben. Einen Spielzustand, einen Spieler, Alpha, Beta und die Suchtiefe. Dabei gibt value_ab wie value_minimax, den ermittelten Wert für den übergebenen Spielzustand und den übergebenen Spieler zurück."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "def value_ab(state, player, alpha=-1, beta=1, depth=6):\r\n",
    "    global Cache_AB\r\n",
    "    state = to_tuple(state)\r\n",
    "    if (state, player, depth) in Cache_AB:\r\n",
    "        value, a, b = Cache_AB[(state, player, depth)]\r\n",
    "        if a <= alpha and beta <= b:\r\n",
    "            return value\r\n",
    "        else:\r\n",
    "            alpha = min(alpha, a)\r\n",
    "            beta  = max(beta , b)\r\n",
    "            value   = alpha_beta(state, player, alpha, beta, depth)\r\n",
    "            Cache_AB[(state, player, depth)] = value, alpha, beta\r\n",
    "            return value\r\n",
    "    else:\r\n",
    "        value = alpha_beta(state, player, alpha, beta, depth)\r\n",
    "        Cache_AB[(state, player, depth)] = value, alpha, beta\r\n",
    "        return value"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Die Funktion `get_order_value(state, player, depth)` erhält den Spielzustand, einen Spieler und die Suchtiefe, und gibt den von der Heuristik ermittelten Wert für diesen Zustand aus der vorherigen Iteration zurück. Verwendet wird diese Funktion für das Sortieren der Zustände in der Funktion `alpha_beta(state, player, alpha, beta, depth)`."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "def get_order_value(state, player, depth):\r\n",
    "    state = to_tuple(state)\r\n",
    "    val, _, _ = Cache_AB.get((state, player, depth-3), (0, -1, 1))\r\n",
    "    return val"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Die Funktion `alpha_beta(state, player, alpha, beta, depth)` erhält die gleichen Werte wie die Funktion `value_ab()` und gibt den Wert für den übergebenen Zustand zurück. Dabei arbeitet `alpha_beta()` nach den im Skript vorgestellten Regeln:\r\n",
    "* $\\alpha \\leq \\texttt{value}(state, player) \\leq \\beta \\;\\rightarrow\\;\\texttt{alpha_beta}(state, player, \\alpha, \\beta) = \\texttt{value}(state,player)$\r\n",
    "* $\\texttt{value}(state, player) < \\alpha \\;\\rightarrow\\; \\texttt{alpha_beta}(state, player, \\alpha, \\beta) \\leq \\alpha$\r\n",
    "* $\\beta < \\texttt{value}(state, player) \\;\\rightarrow\\; \\beta \\leq \\texttt{alpha_beta}(state, player, \\alpha, \\beta)$\r\n",
    "\r\n",
    "### Move-Ordering\r\n",
    "Das Sortieren der Folgezustände zur Verbesserung der Performance des Algorithmus wird innerhalb der Funktion durch eine Liste realisiert. Diese enthält Paare, die aus einem Folgezustand und dem Wert dieses Zustandes aus der vorherigen Iteration des Iterative-Deepening bestehen. Diese Liste wird anhand der Bewertung der Zustände absteigend sortiert. Somit steht der bestmögliche Folgezustand an erster Stelle und wird zuerst bewertet."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "def alpha_beta(state, player, alpha, beta, depth):\r\n",
    "    state = to_list(state)\r\n",
    "    if finished(state, player):\r\n",
    "        return utility(state, player)\r\n",
    "    if depth == 0:\r\n",
    "        return heuristic(state, player)\r\n",
    "    value = alpha\r\n",
    "\r\n",
    "    #move-ordering\r\n",
    "    ns = []\r\n",
    "    for s in next_states(state, player):\r\n",
    "        ns = ns + [[s, get_order_value(s, player, depth)]]\r\n",
    "    ns = sorted(ns, key=itemgetter(1) ,reverse=True)\r\n",
    "\r\n",
    "    for s in ns:\r\n",
    "        value = max(value, -value_ab(s[0], opponent(player), -beta, -alpha, depth-1))\r\n",
    "        if value >= beta:\r\n",
    "            return value\r\n",
    "        alpha = max(value, alpha)\r\n",
    "    return value"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Die Funktion `best_move_ab()` erhält drei Argumente. Einen Spielzustand, einen Spieler und die Suchtiefe. Die Rückgabewerte sind, der von der Funktion ermittelte, beste Folgezustand und dessen Bewertung. Ermittelt wird diese Zustand durch die Bewertung aller Folgezustände durch die Funktion `value_ab()` und die darauf folgende Auswahl des besten Wertes.\r\n",
    "Verbessert wird die Effizienz von Alpha-Beta-Pruning an dieser Stelle durch den Einsatz von iterative deepening. Dabei wird die Suchtiefe `distance` immer weiter, bis zum Erreichen des Werts von `depth`, gesteigert. Passend zum \"Move-Ordering\" aus der Funktion `aplha_beta()` werden die Folgezustände für den aktuellen Zustand nach jedem Iterative-Deepening-Durchlauf geordnet."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "from operator import itemgetter\r\n",
    "\r\n",
    "def best_move_ab(state, player, depth):\r\n",
    "    ns     = next_states(state, player)\r\n",
    "    next_states_and_values = []\r\n",
    "    for s in ns:\r\n",
    "        next_states_and_values = next_states_and_values + [[s, 0.0]]\r\n",
    "        distance = 1\r\n",
    "        while distance <= (depth - 1):\r\n",
    "            for idx_s, s in enumerate(next_states_and_values):\r\n",
    "                value = -value_ab(s[0], opponent(player), depth = distance)\r\n",
    "                next_states_and_values[idx_s][1] = value\r\n",
    "            next_states_and_values = sorted(next_states_and_values, key=itemgetter(1), reverse=True)\r\n",
    "            distance += 1\r\n",
    "    best_value = next_states_and_values[0][1]\r\n",
    "    best_state = next_states_and_values[0][0]\r\n",
    "    return best_value, best_state"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Die Funktion `alpha_beta_pruning(state, player, depth)` wurde erstellt, um die Funktion `best_move_ab(state, player, depth)` nach außen hin eindeutiger von `best_move_minimax (state, player, depth)` abzugrenzen."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "def alpha_beta_pruning(state, player, depth = 6):\r\n",
    "    return(best_move_ab(state, player, depth))"
   ],
   "outputs": [],
   "metadata": {}
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "b7a881999586eaef06c9c58c0c9ebbfb5dcaedf70b93463d94cc91aab857d3f6"
  },
  "kernelspec": {
   "display_name": "Python 3.7.9 64-bit ('ai': conda)",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}