330_Spielbaum.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Spielbaum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Der MinMax Algorithmus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inf = float('inf')\n",
    "def maximize(state):\n",
    "    '''\n",
    "    state: Spielstellung\n",
    "    returns: (st, k), die Folgestellung st, die die höchste Utlity k hat\n",
    "    '''\n",
    "    if terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, -inf\n",
    "    for st in nextstates(state):\n",
    "        _, k = minimize(st)\n",
    "        if k > best_k:\n",
    "            best_st, best_k = st, k\n",
    "    return best_st, best_k\n",
    "\n",
    "def minimize(state):\n",
    "    '''\n",
    "    state: Spielstellung\n",
    "    returns: (st, k), die Folgestellung st, die die niedrigste Utlity k hat\n",
    "    '''\n",
    "    if terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, inf\n",
    "    for st in nextstates(state):\n",
    "        _, k = maximize(st)\n",
    "        if k < best_k:\n",
    "            best_st, best_k = st, k\n",
    "    return best_st, best_k\n",
    "\n",
    "def nextstates(state):\n",
    "    '''\n",
    "    state: Spielstellung\n",
    "    returns: Liste mit möglichen Folgestellungen\n",
    "    '''\n",
    "    pass\n",
    "\n",
    "\n",
    "def terminal_test(state):\n",
    "    '''\n",
    "    state: Spielstellung\n",
    "    returns: True, wenn Stellung ein Blatt ist\n",
    "    '''\n",
    "    pass\n",
    "\n",
    "def evaluation(state):\n",
    "    '''\n",
    "    state: Spielstellung\n",
    "    returns: Zahl, die den Wert der Stellung wiedergibt\n",
    "    '''\n",
    "    pass\n",
    "\n",
    "# st =  ...                  # Ausgangsstellung\n",
    "# print(maximize(st))        # der nächste Zug nach st für den Maximizer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Der Alpha-Beta Algorithmus mit Bremse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inf = float('inf')\n",
    "def maximize(state, alpha, beta, bremse):\n",
    "    '''\n",
    "    state: Stellung\n",
    "    returns: (st, k), die Folgestellung st, die die höchste\n",
    "    Utlity k hat\n",
    "    '''\n",
    "\n",
    "    if bremse == 0 or terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, -inf\n",
    "\n",
    "    for st in nextstates(state):\n",
    "        _, k = minimize(st, alpha, beta, bremse-1)\n",
    "        if k > best_k:\n",
    "            best_st, best_k = st, k\n",
    "        if best_k >= beta:\n",
    "            break\n",
    "        if best_k > alpha:\n",
    "            alpha = best_k\n",
    "    return best_st, best_k\n",
    "\n",
    "\n",
    "def minimize(state, alpha, beta, bremse):\n",
    "    '''\n",
    "    state: Stellung\n",
    "    returns: (st, k), die Folgestellung st, die die niedrigste\n",
    "    Utlity k hat\n",
    "    '''\n",
    "\n",
    "    if bremse == 0 or terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, inf\n",
    "    for st in nextstates(state):\n",
    "        _, k = maximize(st, alpha, beta, bremse-1)\n",
    "        if k < best_k:\n",
    "            best_st, best_k = st, k\n",
    "        if best_k <= alpha:\n",
    "            break\n",
    "        if best_k < beta:\n",
    "            beta = best_k\n",
    "    return best_st, best_k\n",
    "\n",
    "def nextstates(state):\n",
    "    '''\n",
    "    state: Spielstellung\n",
    "    returns: Liste mit möglichen Folgestellungen\n",
    "    '''\n",
    "    pass\n",
    "\n",
    "\n",
    "def terminal_test(state):\n",
    "    '''\n",
    "    state: Spielstellung\n",
    "    returns: True, wenn Stellung ein Blatt ist\n",
    "    '''\n",
    "    pass\n",
    "\n",
    "def evaluation(state):\n",
    "    '''\n",
    "    state: Spielstellung\n",
    "    returns: Zahl, die den Wert der Stellung wiedergibt\n",
    "    '''\n",
    "    pass\n",
    "\n",
    " \n",
    "# st =  ...                         # Ausgangsstellung\n",
    "# print(maximize(st,-inf,inf,8))    # 8 Stufen bis zur Bremse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tic-Tac-Toe\n",
    "Eine Teil-Implementierung, bei der die Bewertungsfunktion immer 0 zurückgibt. Dadurch wird auch das Spielende nicht erkannt.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "Eine Spielstellung ist eine Liste von Zahlen. Jede Zahl ist die\n",
    "Nummer eines Feldes.\n",
    "\n",
    " x . .       0  1  2\n",
    " . o .       3  4  5\n",
    " . . .       6  7  8\n",
    "\n",
    "ist repräsentiert durch die Liste [0,4]. Der Maximizer (x) beginnt das Spiel\n",
    "\n",
    "'''\n",
    "\n",
    "inf = float('inf')\n",
    "gewinn = [{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 3, 6},\n",
    "          {1, 4, 7}, {2, 5, 8}, {0, 4, 8}, {2, 4, 6}]\n",
    "\n",
    "\n",
    "def maximize(state):\n",
    "    if terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, -inf\n",
    "    for st in nextstates(state):\n",
    "        _, k = minimize(st)\n",
    "        if k > best_k:\n",
    "            best_st, best_k = st, k\n",
    "    return best_st, best_k\n",
    "\n",
    "\n",
    "def minimize(state):\n",
    "    if terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, inf\n",
    "    for st in nextstates(state):\n",
    "        _, k = maximize(st)\n",
    "        if k < best_k:\n",
    "            best_st, best_k = st, k\n",
    "    return best_st, best_k\n",
    "\n",
    "\n",
    "def nextstates(state):\n",
    "    '''\n",
    "    state: Spielstellung\n",
    "    returns: Liste mit möglichen Folgestellungen (also Liste von Listen)\n",
    "    '''\n",
    "    temp = []\n",
    "    for i in range(9):\n",
    "        if i not in state:\n",
    "            temp.append(state+[i])\n",
    "    return temp\n",
    "\n",
    "\n",
    "def terminal_test(state):\n",
    "    '''\n",
    "    state: Stellung\n",
    "    returns: True, wenn Stellung ein Blatt ist\n",
    "    '''\n",
    "    w = evaluation(state)\n",
    "    return w == 1 or w == -1 or len(state) == 9\n",
    "\n",
    "\n",
    "def evaluation(state):\n",
    "    '''\n",
    "    state: Stellung\n",
    "    returns: Zahl, die den Wert der Stellung wiedergibt\n",
    "    '''\n",
    "\n",
    "    maxzuege = set(state[::2])\n",
    "    minzuege = set(state[1::2])\n",
    "    for g in gewinn:\n",
    "        if g <= maxzuege:\n",
    "            return 1\n",
    "        if g <= minzuege:\n",
    "            return -1\n",
    "    return 0\n",
    "\n",
    "\n",
    "def show(state):\n",
    "    '''\n",
    "    state: Spielstellung\n",
    "    returns: None, printed die Stellung\n",
    "    '''\n",
    "    a = ['.'] * 9\n",
    "    for i in range(len(state)):\n",
    "        if (i % 2 == 0):\n",
    "            a[state[i]] = 'x'\n",
    "        else:\n",
    "            a[state[i]] = 'o'\n",
    "\n",
    "    for i in range(9):\n",
    "        if i % 3 == 0:\n",
    "            print()\n",
    "        print(a[i], end=' ')\n",
    "    print()\n",
    "\n",
    "\n",
    "def showMuster():\n",
    "    '''\n",
    "    Hilfsfunktion, die die Nummerierung der Felder zeigt\n",
    "    '''\n",
    "    for i in range(0, 9):\n",
    "        if i % 3 == 0:\n",
    "            print()\n",
    "        print(i, end=' ')\n",
    "    print()\n",
    "\n",
    "\n",
    "def play():\n",
    "    state = []\n",
    "    i = 0\n",
    "    while not terminal_test(state):\n",
    "        \n",
    "        if i % 2==0:\n",
    "            showMuster()\n",
    "            z = int(input(\"Eingabe Spieler x: \"))\n",
    "            state.append(z)\n",
    "        else:\n",
    "            state, _ = minimize(state)\n",
    "        show(state)\n",
    "        i += 1\n",
    "        \n",
    "    if evaluation(state) == 1:\n",
    "        print(\"Spieler x hat gewonnen\")\n",
    "    elif evaluation(state) == -1:\n",
    "        print(\"Computer hat gewonnen\")\n",
    "    else:\n",
    "        print(\"Unentschieden\")\n",
    "\n",
    "play()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgaben:\n",
    "- Ändere das TicTacToe-Spiel so, dass der Computer beginnt.\n",
    "- Erweitere das Spiel auf ein 4x3 Feld. \n",
    "- Erweitere das Spiel auf ein 4x4 Feld, führe ein Eröffnungsbuch ein.\n",
    "- Codingame: [Minimax Exercise](https://www.codingame.com/training/medium/minimax-exercise)\n",
    "- Codingame: [Minimax Simple Example](https://www.codingame.com/training/expert/minimax-simple-example)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Connect4\n",
    "Das Spiel besteht aus 7 Spalten, die jeweils mit bis zu 6 Steinen \n",
    "gefüllt werden können.\n",
    "\n",
    "Eine Stellung wird repräsentiert durch eine Liste von Zahlen\n",
    "von 0 bis 41, die jeweils angeben, in welcher Reihenfolge Steine\n",
    "auf die jeweilige Position gekommen sind.\n",
    "\n",
    "```  \n",
    " 0  1  2  3  4  5  6 \n",
    " 7  8  9 10 11 12 13 \n",
    "14 15 16 17 18 19 20 \n",
    "21 22 23 24 25 26 27 \n",
    "28 29 30 31 32 33 34 \n",
    "35 36 37 38 39 40 41 \n",
    "```\n",
    "\n",
    "Der erste Stein ist 'x'.\n",
    "Die Liste [38,37,30] repräsentiert also die folgende Stellung:\n",
    "\n",
    "```\n",
    ". . . . . . . \n",
    ". . . . . . . \n",
    ". . . . . . . \n",
    ". . . . . . . \n",
    ". . x . . . . \n",
    ". . o x . . . \n",
    "=============\n",
    "0 1 2 3 4 5 6\n",
    "```\n",
    "\n",
    "Im User-Interface gibt man die Nummer der Spalte für den nächsten Stein an.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe: \n",
    "\n",
    "- Versuche zu gewinnen - als Anziehender und als Nachziehender\n",
    "- Gibt es sinnvolle Ergänzungen für das Eröffnungsbuch?\n",
    "- Hast du andere Ideen für die evaluation?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inf = float('inf')\n",
    "gewinn = 10000\n",
    "\n",
    "def maximize(state, alpha=-inf, beta=inf, bremse=6):\n",
    "\n",
    "    if bremse == 0 or terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, -inf\n",
    "\n",
    "    for st in nextstates(state):\n",
    "        _, k = minimize(st, alpha, beta, bremse-1)\n",
    "\n",
    "        if k > best_k:\n",
    "            best_st, best_k = st, k\n",
    "        if best_k >= beta:\n",
    "            break\n",
    "        if best_k > alpha:\n",
    "            alpha = best_k\n",
    "    return best_st, best_k\n",
    "\n",
    "\n",
    "def minimize(state, alpha=-inf, beta=inf, bremse=6):\n",
    "\n",
    "    if bremse == 0 or terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, inf\n",
    "    for st in nextstates(state):\n",
    "        _, k = maximize(st, alpha, beta, bremse-1)\n",
    "        if k < best_k:\n",
    "            best_st, best_k = st, k\n",
    "        if best_k <= alpha:\n",
    "            break\n",
    "        if best_k < beta:\n",
    "            beta = best_k\n",
    "    return best_st, best_k\n",
    "\n",
    "\n",
    "def showNr():\n",
    "    ''' printed die Nummerierung der Felder '''\n",
    "    for i in range(42):\n",
    "        if i % 7 == 0:\n",
    "            print()\n",
    "        print('{:2d}'.format(i), end=' ')\n",
    "    print()\n",
    "\n",
    "\n",
    "def getBoard(state):\n",
    "    ''' wandelt state in ein board um \n",
    "        ein board ist eine Liste mit 42 Zeichen, entweder x, o oder ein Punkt.'''\n",
    "    tmp = list('.'*42)\n",
    "    for i in range(len(state)):\n",
    "        if i % 2 == 0:\n",
    "            tmp[state[i]] = 'x'\n",
    "        else:\n",
    "            tmp[state[i]] = 'o'\n",
    "    return tmp\n",
    "\n",
    "\n",
    "def showBoard(board):\n",
    "    ''' printed board '''\n",
    "    for i in range(42):\n",
    "        if i % 7 == 0:\n",
    "            print()\n",
    "        print('{:1s}'.format(board[i]), end=' ')\n",
    "    print()\n",
    "    print('='*13)\n",
    "    print('0 1 2 3 4 5 6')\n",
    "\n",
    "\n",
    "def muster(board):\n",
    "    tmp = []\n",
    "    for i in range(0, 42, 7):\n",
    "        tmp.append(''.join(board[i:i+7]))  # horizontal\n",
    "    for i in range(7):\n",
    "        tmp.append(''.join(board[i::7]))   # vertikal\n",
    "\n",
    "    # diagonale muster nach links unten\n",
    "    tmp.append(''.join(board[14:39:8]))\n",
    "    tmp.append(''.join(board[7:40:8]))\n",
    "    tmp.append(''.join(board[0:41:8]))\n",
    "    tmp.append(''.join(board[1:42:8]))\n",
    "    tmp.append(''.join(board[2:35:8]))\n",
    "    tmp.append(''.join(board[3:28:8]))\n",
    "\n",
    "    # diagonale muster nach rechts unten\n",
    "    tmp.append(''.join(board[3:22:6]))\n",
    "    tmp.append(''.join(board[4:29:6]))\n",
    "    tmp.append(''.join(board[5:36:6]))\n",
    "    tmp.append(''.join(board[6:37:6]))\n",
    "    tmp.append(''.join(board[13:38:6]))\n",
    "    tmp.append(''.join(board[20:39:6]))\n",
    "    return tmp\n",
    "\n",
    "\n",
    "def nextstates(state):\n",
    "    '''\n",
    "    state: Spielstatus\n",
    "    returns: Liste mit möglichen Folgestellungen\n",
    "    '''\n",
    "    board = getBoard(state)\n",
    "    tmp = []\n",
    "    for i in free(board):     # für jeden verfügbaren Platz\n",
    "        tmp.append(state+[i])\n",
    "    return tmp\n",
    "\n",
    "\n",
    "def evaluation(state):\n",
    "    '''\n",
    "    state: Spielstellung\n",
    "    returns int - Bewertung der Spielstellung\n",
    "    '''\n",
    "    w = 0\n",
    "    board = getBoard(state)\n",
    "    for s in muster(board):\n",
    "        if 'xxxx' in s:\n",
    "            return gewinn\n",
    "        if 'oooo' in s:\n",
    "            return -gewinn\n",
    "        if 'x...' in s:\n",
    "            w += 5\n",
    "        if '.x..' in s:\n",
    "            w += 5\n",
    "        if '..x.' in s:\n",
    "            w += 5\n",
    "        if '...x' in s:\n",
    "            w += 5\n",
    "\n",
    "        if 'xx..' in s:\n",
    "            w += 30\n",
    "        if 'x.x.' in s:\n",
    "            w += 30\n",
    "        if 'x..x' in s:\n",
    "            w += 30\n",
    "        if '.xx.' in s:\n",
    "            w += 30\n",
    "        if '.x.x' in s:\n",
    "            w += 30\n",
    "        if '..xx' in s:\n",
    "            w += 30\n",
    "        if 'xxx.' in s:\n",
    "            w += 500\n",
    "        if 'xx.x' in s:\n",
    "            w += 500\n",
    "        if 'x.xx' in s:\n",
    "            w += 500\n",
    "        if '.xxx' in s:\n",
    "            w += 500\n",
    "\n",
    "        if 'o...' in s:\n",
    "            w += -5\n",
    "        if '.o..' in s:\n",
    "            w += -5\n",
    "        if '..o.' in s:\n",
    "            w += -5\n",
    "        if '...o' in s:\n",
    "            w += -5\n",
    "\n",
    "        if 'oo..' in s:\n",
    "            w += -30\n",
    "        if 'o.o.' in s:\n",
    "            w += -30\n",
    "        if 'o..o' in s:\n",
    "            w += -30\n",
    "        if '.oo.' in s:\n",
    "            w += -30\n",
    "        if '.o.o' in s:\n",
    "            w += -30\n",
    "        if '..oo' in s:\n",
    "            w += -30\n",
    "        if 'ooo.' in s:\n",
    "            w += -500\n",
    "        if 'oo.o' in s:\n",
    "            w += -500\n",
    "        if 'o.oo' in s:\n",
    "            w += -500\n",
    "        if '.ooo' in s:\n",
    "            w += -500\n",
    "    return w\n",
    "\n",
    "\n",
    "def terminal_test(state):\n",
    "    w = evaluation(state)\n",
    "    return w >= gewinn or w <= -gewinn or len(state) == 42\n",
    "\n",
    "\n",
    "def colNrs(i):\n",
    "    '''\n",
    "    i: int,  0 <= i <= 6\n",
    "    returns: Liste der Platznummern für Spalte i, von unten nach oben\n",
    "    '''\n",
    "    return [35+i-7*r for r in range(0, 6)]\n",
    "\n",
    "\n",
    "def freeIn(board, i):\n",
    "    ''' returns: nächster freier Platz in Spalte i '''\n",
    "    for j in colNrs(i):\n",
    "        if board[j] == '.':\n",
    "            return j\n",
    "\n",
    "\n",
    "def free(board):\n",
    "    ''' liste der möglichen nächsten positionen '''\n",
    "    tmp = []\n",
    "    for i in range(7):\n",
    "        for j in colNrs(i):\n",
    "            if board[j] == '.':\n",
    "                tmp.append(j)\n",
    "                break\n",
    "    return tmp\n",
    "\n",
    "\n",
    "def play():\n",
    "    ''' Spieler beginnt und spielt x.\n",
    "    Computer ist Nachziehener und min-Spieler mit o.\n",
    "    '''\n",
    "\n",
    "    BREMSE = 8\n",
    "    state = []\n",
    "    board = getBoard(state)\n",
    "    showBoard(board)\n",
    "\n",
    "    i = 0\n",
    "    while not terminal_test(state):\n",
    "\n",
    "        if i % 2 == 0:\n",
    "            x = int(input(\"Eingabe Spieler x (0-6): \"))\n",
    "            state.append(freeIn(board, x))\n",
    "            board = getBoard(state)\n",
    "            showBoard(board)\n",
    "            print(\"Spieler x hat gezogen\",\n",
    "                  state[-1] % 7, \" - Bewertung:\", evaluation(state))\n",
    "\n",
    "        else:\n",
    "            if tuple(state) in buch:\n",
    "                state = buch[tuple(state)]\n",
    "                k = \"Buchzug\"\n",
    "            else:\n",
    "                state, k = minimize(state, bremse=BREMSE)\n",
    "            board = getBoard(state)\n",
    "            showBoard(board)\n",
    "            print(\"Computer o hat gezogen\",\n",
    "                  state[-1] % 7, \" - Bewertung:\", evaluation(state), \"- min-Wert:\", k)\n",
    "\n",
    "        i = i+1\n",
    "\n",
    "    if evaluation(state) >= gewinn:\n",
    "        print(\"Spieler x hat gewonnen\")\n",
    "    elif evaluation(state) <= -gewinn:\n",
    "        print(\"Computer hat gewonnen\")\n",
    "    else:\n",
    "        print(\"Unentschieden\")\n",
    "\n",
    "\n",
    "def playC():\n",
    "    ''' Computer beginn, ist max-Spieler und setzt x.\n",
    "    Mensch ist Nachziehender und spielt o.\n",
    "    '''\n",
    "    BREMSE = 8\n",
    "    state = []\n",
    "    board = getBoard(state)\n",
    "\n",
    "    i = 0     # Zähler für Spielerwechsel\n",
    "    while not terminal_test(state):\n",
    "\n",
    "        if i % 2 == 1:\n",
    "            x = int(input(\"Eingabe Spieler o (0-6)\"))\n",
    "            state.append(freeIn(board, x))\n",
    "            board = getBoard(state)\n",
    "            showBoard(board)\n",
    "            print(\"Spieler o hat gezogen\",\n",
    "                  state[-1] % 7, \" - Bewertung:\", evaluation(state))\n",
    "\n",
    "        else:\n",
    "            if tuple(state) in buch:\n",
    "                state = buch[tuple(state)]\n",
    "                k = \"Buchzug\"\n",
    "            else:\n",
    "                state, k = maximize(state, bremse=BREMSE)\n",
    "            board = getBoard(state)\n",
    "            showBoard(board)\n",
    "            print(\"Computer x hat gezogen\",\n",
    "                  state[-1] % 7, \" - Bewertung:\", evaluation(state), \"- max-Wert:\", k)\n",
    "\n",
    "        i = i+1\n",
    "\n",
    "    if evaluation(state) <= -gewinn:\n",
    "        print(\"Spieler o hat gewonnen\")\n",
    "    elif evaluation(state) >= gewinn:\n",
    "        print(\"Computer hat gewonnen\")\n",
    "    else:\n",
    "        print(\"Unentschieden\")\n",
    "\n",
    "\n",
    "buch = {tuple(): [38], (38,): [38, 31]}   # Eröffnungsbuch\n",
    "play()     # Spieler beginnt mit x\n",
    "#playC()   # Computer beginnt mit x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Bemerkungen\n",
    "\n",
    "Im folgenden Beispiel ist der Computer der Nachziehende ('o'). Er ist an der Reihe. Wir sehen sofort, dass der Computer den Stein in Spalte 6 plazieren muss. Trotzdem dauert die Berechnung ziemlich lange.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "state = [38,37,31,24,30,17,23,10,3,16,39,32,40]\n",
    "board = getBoard(state)\n",
    "showNr()\n",
    "showBoard(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "minimize(state,bremse=8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die *nextstates* werden in einer ungünstigen Reihenfolge durchlaufen. Wenn wir die Reihenfolge umdrehen, geht die Berechnung schneller."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimize(state, alpha=-inf, beta=inf, bremse=6):\n",
    "\n",
    "    if bremse == 0 or terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, inf\n",
    "    for st in nextstates(state)[::-1]:    # umgedrehte Reihenfolge\n",
    "        _, k = maximize(st, alpha, beta, bremse-1)\n",
    "        if k < best_k:\n",
    "            best_st, best_k = st, k\n",
    "        if best_k <= alpha:\n",
    "            break\n",
    "        if best_k < beta:\n",
    "            beta = best_k\n",
    "    return best_st, best_k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "minimize(state,bremse=8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Was ändert sich durch die umgedrehte Reihenfolge? Wir zählen die Anzahl der pruning-Vorgänge und die Anzahl der besuchten Knoten."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pruneCount = 0\n",
    "visitCount = 0\n",
    "\n",
    "def maximize(state, alpha=-inf, beta=inf, bremse=6):\n",
    "    global pruneCount, visitCount\n",
    "    visitCount +=1\n",
    " \n",
    "    if bremse == 0 or terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, -inf\n",
    "\n",
    "    for st in nextstates(state):\n",
    "        _, k = minimize(st, alpha, beta, bremse-1)\n",
    "       \n",
    "        if k > best_k:\n",
    "            best_st, best_k = st, k\n",
    "        if best_k >= beta:\n",
    "            pruneCount +=1\n",
    "            break\n",
    "        if best_k > alpha:\n",
    "            alpha = best_k\n",
    "    return best_st, best_k\n",
    "\n",
    "\n",
    "def minimize(state, alpha=-inf, beta=inf, bremse=6):\n",
    "    global pruneCount, visitCount\n",
    "    visitCount += 1\n",
    " \n",
    "    if bremse == 0 or terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, inf\n",
    "    for st in nextstates(state): \n",
    "        \n",
    "        _, k = maximize(st, alpha, beta, bremse-1)\n",
    "        if k < best_k:\n",
    "            best_st, best_k = st, k\n",
    "        if best_k <= alpha:\n",
    "            pruneCount +=1\n",
    "            break\n",
    "        if best_k < beta:\n",
    "            beta = best_k\n",
    "    return best_st, best_k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "minimize(state,bremse=8), pruneCount, visitCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das ganze mit der umgedrehten Reihenfolge beim Minimizer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pruneCount = 0\n",
    "visitCount = 0\n",
    "\n",
    "def minimize(state, alpha=-inf, beta=inf, bremse=6):\n",
    "    global pruneCount, visitCount\n",
    "    visitCount += 1\n",
    " \n",
    "    if bremse == 0 or terminal_test(state):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, inf\n",
    "    for st in nextstates(state)[::-1]: \n",
    "        \n",
    "        _, k = maximize(st, alpha, beta, bremse-1)\n",
    "        if k < best_k:\n",
    "            best_st, best_k = st, k\n",
    "        if best_k <= alpha:\n",
    "            pruneCount +=1\n",
    "            break\n",
    "        if best_k < beta:\n",
    "            beta = best_k\n",
    "    return best_st, best_k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "minimize(state,bremse=8), pruneCount, visitCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hier wird weniger häufig gepruned, aber offenbar an höheren Stellen des Baumes, dadurch fallen größere Teile weg und insgesamt müssen nicht mehr so viele Knoten besucht werden.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wie können wir eine günstige Reihenfolge zur Untersuchung der *nextstates* finden? Wir können den maximizer mit einer kleinen bremse auf alle *nextstates* loslassen. Das gibt uns einen Hinweis darauf, welche Knoten für uns (als minimizer) die vielversprechensten sind."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for st in nextstates(state):\n",
    "    print(maximize(st,bremse=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Reihenfolge der nextstates kann auch von anderen Überlegungen abhängig gemacht werden, z.B: Züge in der Mitte versprechen in der Regel mehr Erfolg, also die zuerst untersuchen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Iterative Deepening"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine kleine Bremse findet im Beispiel von oben schon die richtige Antwort:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "minimize(state,bremse=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Beim *iterative deepening* erhöht man schrittweise die Tiefe (bremse). Wenn die Zeit für einen Zug abgelaufen ist, gibt man die beste bisher gefundene Antwort. \n",
    "\n",
    "Bei begrenzter Zeit gibt es einen trade-off zwischen Tiefe und Evaluation. Je komplizierter die Evaluation, desto weniger tief kann in gegebener Zeit nach einer guten Antwort gesucht werden.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Vergleich zweier Evaluationen\n",
    "\n",
    "Wir erweitern *maximize* und *minimize*, so dass wir die Evaluations-Funktion als Parameter übergeben können."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gewinn = 10000\n",
    "def maximize(state, alpha=-inf, beta=inf, bremse=6, evaluation=None):\n",
    "\n",
    "    if bremse == 0 or terminal_test(state, evaluation):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, -inf\n",
    "\n",
    "    for st in nextstates(state):\n",
    "        _, k = minimize(st, alpha, beta, bremse-1, evaluation)\n",
    "        if k > best_k:\n",
    "            best_st, best_k = st, k\n",
    "        if best_k >= beta:\n",
    "            break\n",
    "        if best_k > alpha:\n",
    "            alpha = best_k\n",
    "    return best_st, best_k\n",
    "\n",
    "\n",
    "def minimize(state, alpha=-inf, beta=inf, bremse=6, evaluation=None):\n",
    "\n",
    "    if bremse == 0 or terminal_test(state, evaluation):\n",
    "        return None, evaluation(state)\n",
    "\n",
    "    best_st, best_k = None, inf\n",
    "    for st in nextstates(state):\n",
    "        _, k = maximize(st, alpha, beta, bremse-1, evaluation)\n",
    "        if k < best_k:\n",
    "            best_st, best_k = st, k\n",
    "        if best_k <= alpha:\n",
    "            break\n",
    "        if best_k < beta:\n",
    "            beta = best_k\n",
    "    return best_st, best_k\n",
    "\n",
    "def terminal_test(state, evaluation):\n",
    "    w = evaluation(state)\n",
    "    return w >= gewinn or w <= -gewinn or len(state) == 42\n",
    "\n",
    "def evalB(state):\n",
    "    w = 0\n",
    "    board = getBoard(state)\n",
    "    for s in muster(board):\n",
    "        if 'xxxx' in s:\n",
    "            return gewinn\n",
    "        if 'oooo' in s:\n",
    "            return -gewinn\n",
    "        if 'x...' in s:\n",
    "            w += 5\n",
    "        if '.x..' in s:\n",
    "            w += 5\n",
    "        if '..x.' in s:\n",
    "            w += 5\n",
    "        if '...x' in s:\n",
    "            w += 5\n",
    "\n",
    "        if 'xx..' in s:\n",
    "            w += 10\n",
    "        if 'x.x.' in s:\n",
    "            w += 10\n",
    "        if 'x..x' in s:\n",
    "            w += 10\n",
    "        if '.xx.' in s:\n",
    "            w += 10\n",
    "        if '.x.x' in s:\n",
    "            w += 10\n",
    "        if '..xx' in s:\n",
    "            w += 10\n",
    "            \n",
    "        if 'xxx.' in s:\n",
    "            w += 50\n",
    "        if 'xx.x' in s:\n",
    "            w += 50\n",
    "        if 'x.xx' in s:\n",
    "            w += 50\n",
    "        if '.xxx' in s:\n",
    "            w += 50\n",
    "\n",
    "        if 'o...' in s:\n",
    "            w += -5\n",
    "        if '.o..' in s:\n",
    "            w += -5\n",
    "        if '..o.' in s:\n",
    "            w += -5\n",
    "        if '...o' in s:\n",
    "            w += -5\n",
    "\n",
    "        if 'oo..' in s:\n",
    "            w += -10\n",
    "        if 'o.o.' in s:\n",
    "            w += -10\n",
    "        if 'o..o' in s:\n",
    "            w += -10\n",
    "        if '.oo.' in s:\n",
    "            w += -10\n",
    "        if '.o.o' in s:\n",
    "            w += -10\n",
    "        if '..oo' in s:\n",
    "            w += -10\n",
    "            \n",
    "        if 'ooo.' in s:\n",
    "            w += -50\n",
    "        if 'oo.o' in s:\n",
    "            w += -50\n",
    "        if 'o.oo' in s:\n",
    "            w += -50\n",
    "        if '.ooo' in s:\n",
    "            w += -50\n",
    "    return w\n",
    "\n",
    "def evalA(state):\n",
    "    w = 0\n",
    "    board = getBoard(state)\n",
    "    for s in muster(board):\n",
    "        if 'xxxx' in s:\n",
    "            return gewinn\n",
    "        if 'oooo' in s:\n",
    "            return -gewinn\n",
    "        if 'x...' in s:\n",
    "            w += 5\n",
    "        if '.x..' in s:\n",
    "            w += 5\n",
    "        if '..x.' in s:\n",
    "            w += 5\n",
    "        if '...x' in s:\n",
    "            w += 5\n",
    "\n",
    "        if 'xx..' in s:\n",
    "            w += 30\n",
    "        if 'x.x.' in s:\n",
    "            w += 30\n",
    "        if 'x..x' in s:\n",
    "            w += 30\n",
    "        if '.xx.' in s:\n",
    "            w += 30\n",
    "        if '.x.x' in s:\n",
    "            w += 30\n",
    "        if '..xx' in s:\n",
    "            w += 30\n",
    "        if 'xxx.' in s:\n",
    "            w += 500\n",
    "        if 'xx.x' in s:\n",
    "            w += 500\n",
    "        if 'x.xx' in s:\n",
    "            w += 500\n",
    "        if '.xxx' in s:\n",
    "            w += 500\n",
    "\n",
    "        if 'o...' in s:\n",
    "            w += -5\n",
    "        if '.o..' in s:\n",
    "            w += -5\n",
    "        if '..o.' in s:\n",
    "            w += -5\n",
    "        if '...o' in s:\n",
    "            w += -5\n",
    "\n",
    "        if 'oo..' in s:\n",
    "            w += -30\n",
    "        if 'o.o.' in s:\n",
    "            w += -30\n",
    "        if 'o..o' in s:\n",
    "            w += -30\n",
    "        if '.oo.' in s:\n",
    "            w += -30\n",
    "        if '.o.o' in s:\n",
    "            w += -30\n",
    "        if '..oo' in s:\n",
    "            w += -30\n",
    "        if 'ooo.' in s:\n",
    "            w += -500\n",
    "        if 'oo.o' in s:\n",
    "            w += -500\n",
    "        if 'o.oo' in s:\n",
    "            w += -500\n",
    "        if '.ooo' in s:\n",
    "            w += -500\n",
    "    return w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "EvalA spielt gegen EvalB. Wenn der untere Code beginnen soll, benennen wir die Funktionen um.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def playAB():\n",
    "    ''' evalA startet mit x\n",
    "    evalB ist Nachziehender mit o.\n",
    "    '''\n",
    "    state = []\n",
    "    board = getBoard(state)\n",
    "    showBoard(board)\n",
    "\n",
    "    i = 0\n",
    "    while not terminal_test(state, evaluation=evalA):\n",
    "\n",
    "        if i % 2 == 0:\n",
    "            state, k = maximize(state, bremse=8, evaluation=evalA)\n",
    "            board = getBoard(state)\n",
    "            showBoard(board)\n",
    "            print(\"evalA x hat gezogen\",\n",
    "                  state[-1] % 7, \" - evalA/evalB-Bewertung:\", evalA(state), evalB(state), \"- max-Wert:\", k)\n",
    "\n",
    "        else:\n",
    "            state, k = minimize(state, bremse=8, evaluation=evalB)\n",
    "            board = getBoard(state)\n",
    "            showBoard(board)\n",
    "            print(\"evalB o hat gezogen\",\n",
    "                  state[-1] % 7, \" - evalA/evalB-Bewertung:\", evalA(state), evalB(state), \"- min-Wert:\", k)\n",
    "\n",
    "        i = i+1\n",
    "\n",
    "    if evalA(state) >= gewinn:\n",
    "        print(\"evalA x hat gewonnen\")\n",
    "    elif evalA(state) <= -gewinn:\n",
    "        print(\"evalB o  hat gewonnen\")\n",
    "    else:\n",
    "        print(\"Unentschieden\")\n",
    "\n",
    "playAB()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}