16-Loesung.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mastermind\n",
    "### - Lösung - "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mastermind - Das Spiel"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Spiel Mastermind (auch SuperHirn genannt) ist ein Logikspiel für zwei Spieler aus den 1970er Jahren. Dabei gibt einer der Spieler einen Code, bestehend aus vier farbigen Stiften, vor und der andere Spieler versucht diesen, durch geschicktes logisches Schlussfolgern, zu erraten.\n",
    "\n",
    "Das Spielprinzip ist das Folgende:\n",
    "\n",
    "- Spieler 1 steckt verdeckt einen Code aus vier farbigen Stiften. Es gibt 6 verschiedene Farben aus denen der Spieler wählen kann. Farben dürfen auch mehrfach vorkommen.\n",
    "\n",
    "- Eine Runde läuft dann folgendermaßen ab:\n",
    "    - Spieler 2 gibt eine Vermutung ab, in dem er/sie einen Code aus vier farbigen Stiften steckt.\n",
    "    - Spieler 1 gibt Feedback indem er/sie eine gewisse Anzahl an schwarzen (oder im Bild unten roten) und weißen Stiften neben die geratene Kombination steckt. \n",
    "        - Die Anzahl der schwarzen Stifte gibt an, wie viele farbige Stifte im geratenen Code die richtige Farbe haben und gleichzeitig an der richtigen Position stecken.\n",
    "        - Die Anzahl der weißen Stifte gibt an, wie viele farbige Stifte im geratenen Code zwar die richtige Farbe haben, aber an der falschen Position stecken.\n",
    "\n",
    "    **Beispiel**: Im Bild unten in der zweiten Reihe (von oben) ist das Feedback ein weißer und ein schwarzer (bzw. roter) Stift. Der schwarze Stift ist dort, da im geratenen Code ein roter Stift an der richtigen Position (nämlich der zweiten von rechts) steckt. Den weißen Stift gibt es, da im geheimen Code zwar ein lilaner Stift vorkommt, dieser aber an der falschen Position steckt.\n",
    "    \n",
    "- Das geht solange so weiter bis Spieler 2 entweder den Code erraten hat oder die vorher festgelegte maximale Rundenanzahl erreicht ist. Im ersten Fall gewinnt Spieler 2 und im letzteren gewinnt Spieler 1.\n",
    "\n",
    "\n",
    "Wenn dir noch etwas unklar ist wie das Spiel gespielt wird oder du noch mehr wissen möchtest, dann schau dir folgende Links an:\n",
    "\n",
    "https://de.wikipedia.org/wiki/Mastermind\n",
    "\n",
    "https://www.spielregeln-spielanleitungen.de/spiel/mastermind-superhirn/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In dieser Aufgabe geht es darum, erst das Mastermind-Spiel zu implementieren und dann wollen wir eine KI programmieren, die den Code in möglichst wenig Versuchen erraten kann.\n",
    "\n",
    "Je nach Mastermind-Spiel hat man ca. 8-12 Versuche, um den Code zu erraten. Die maximale Anzahl der Versuche wollen wir aber erstmal nicht als Bedingung in unser Spiel aufnehmen sondern stattdessen zählen wie viele Versuche ein Spieler braucht, um den Code zu erraten. Das heißt, je weniger Versuche der Spieler braucht, desto besser ist das Ergebnis."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div>\n",
    "<img src=\"https://upload.wikimedia.org/wikipedia/commons/2/2d/Mastermind.jpg\" width=\"400\"/>\n",
    "</div>\n",
    "\n",
    "(Quelle: https://upload.wikimedia.org/wikipedia/commons/2/2d/Mastermind.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Spiel implementieren"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In unserer Implementierung von Mastermind wird es so sein, dass die Rolle von Spieler 1 (in der Beschreibung oben) von unserem Programm übernommen wird. Das heißt der geheime Farbcode wird immer zufällig durch den Computer festgelegt (welcher auch das Feedback gibt) und der/die Spieler/in (oder KI) muss den Code erraten.\n",
    "\n",
    "Die Methode \"spiele_mastermind()\", in der der Ablauf eines Mastermindspiels implementiert ist, ist schon vorgegeben. Die Methoden, die dort aufgerufen werden, müssen größtenteils aber noch implementiert werden.\n",
    "Außerdem wird der spiele_mastermind() Methode ein Spieler-Objekt übergeben. Deswegen werden wir, nachdem wir das eigentliche Spiel implementiert haben, noch jeweils Klassen für menschliche und KI-Spieler erstellen.\n",
    "\n",
    "An den Stellen, an denen drei Punkte (...) sind, musst du Code ergänzen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "import copy\n",
    "import itertools\n",
    "from statistics import mean"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Die Farbzuordnung brauchen wir für die Eingabe eines menschlichen Spielers, damit er/sie nicht alle Farben \n",
    "# ausschreiben muss sondern einfach die jeweiligen Buchstaben eingeben kann.\n",
    "farbzuordnung = {'y':'Gelb', 'r':'Rot', 'b':'Blau', 'g':'Grün',  'o':'Orange', 'p':'Lila'}\n",
    "farben = list(farbzuordnung.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Lege zufällig einen verdeckten vierstelligen Farbcode fest z. B. ['Grün','Orange','Grün','Lila'].\n",
    "# Verwende dazu die Variable \"farben\", die eine Liste mit den Farben enthält.\n",
    "def farbcode_festlegen():\n",
    "    \"\"\" Legt zufällig einen verdeckten vierstelligen Farbcode fest\n",
    "    \n",
    "    Returns:\n",
    "        geheimer_code (list): Liste mit vier Farben z. B. ['Grün','Orange','Grün','Lila']\n",
    "    \"\"\"\n",
    "    \n",
    "    # BEGINN LÖSUNG\n",
    "    geheimer_code = random.choices(farben, k=4)\n",
    "    # ENDE LÖSUNG\n",
    "    return geheimer_code\n",
    "\n",
    "\n",
    "def farbcode_raten(farbcode,code):\n",
    "    \"\"\" Überprüft vermuteten Code und erstellt Feedback\n",
    "    \n",
    "    In dieser Methode wird überprüft wie viele farbige Stifte im geratenen Code mit dem verdeckten Code\n",
    "    übereinstimmen und entsprechendes Feedback gegeben.\n",
    "    \n",
    "    Args:\n",
    "        farbcode (list): geheimer Farbcode als Liste mit 4 Strings\n",
    "        code (list): Vermutung für den Code, die überprüft werden soll; auch eine Liste mit 4 Strings\n",
    "        \n",
    "    Returns:\n",
    "        anzahl_richtige_position (int): Anzahl der Stifte mit der richtigen Farbe und der richtigen Position\n",
    "        anzahl_richtige_farbe (int): Anzahl der Stifte mit der richtigen Farbe aber der falschen Position\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "    # Kopie erstellen damit übergebene Variablen nicht verändert werden\n",
    "    farbcode = farbcode.copy()\n",
    "    code = code.copy()\n",
    "    \n",
    "    # BEGINN LÖSUNG\n",
    "    anzahl_richtige_position = 0\n",
    "    anzahl_richtige_farbe_alle = 0\n",
    "    \n",
    "    for i in range(len(farbcode)):\n",
    "        if farbcode[i]==code[i]:\n",
    "            anzahl_richtige_position += 1\n",
    "    \n",
    "    for element in farbcode:\n",
    "        if element in code:\n",
    "            anzahl_richtige_farbe_alle += 1 \n",
    "            code.remove(element)\n",
    "    \n",
    "    # Alternative Möglichkeit:\n",
    "    #anzahl_richtige_farbe_alle = sum([min(farbcode.count(farbe),code.count(farbe)) for farbe in farben])\n",
    "    \n",
    "    # Da wir alle farbigen Stifte gezählt haben, die in beiden Codes vorkommen (egal an welcher Position),\n",
    "    # müssen wir die abziehen, die gleichzeitig auch an der richtigen Position sind, damit wir sie nicht doppelt zählen\n",
    "    anzahl_richtige_farbe = anzahl_richtige_farbe_alle - anzahl_richtige_position\n",
    "    # ENDE LÖSUNG\n",
    "            \n",
    "    return anzahl_richtige_position,anzahl_richtige_farbe\n",
    "             \n",
    "def code_erraten(anzahl_richtige_position):\n",
    "    \"\"\" Diese Methode testet, ob der Farbcode erraten wurde\n",
    "    \n",
    "    Args:\n",
    "        # BEGINN LÖSUNG\n",
    "        anzahl_richtige_position (int): Anzahl der Stifte mit der richtigen Farbe und der richtigen Position\n",
    "        # ENDE LÖSUNG\n",
    "        \n",
    "    Returns:\n",
    "        erraten (bool): Boolscher Wert, der angibt, ob der Code erraten wurde (True) oder nicht (False)\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    # BEGINN LÖSUNG\n",
    "    erraten = (anzahl_richtige_position == 4)\n",
    "    # ENDE LÖSUNG\n",
    "    return erraten"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Im Folgenden findet ihr noch ein paar Hilfsfunktionen, die schon vorimplementiert sind. Sie sind dafür verantwortlich, dass je nach Spieler (Mensch oder KI) die richtigen Methoden für die Eingabe einer Code-Vermutung und für die Verarbeitung des Feedbacks aufgerufen werden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Diese Methode ist für die Code-Eingabe verantwortlich\n",
    "def code_eingabe(spieler):\n",
    "    eingabe_methode = waehle_eingabe_methode(spieler)\n",
    "    return eingabe_methode()\n",
    "\n",
    "# Diese Methode wählt die passende Eingabemethode aus je nachdem ob der/die Spieler/in ein Mensch oder eine KI ist.\n",
    "# Die jeweiligen Methoden werden weiter unten als Teil der entsprechenen Klasse (Mensch/KI) definiert.\n",
    "def waehle_eingabe_methode(spieler):\n",
    "    if spieler.typ == \"Mensch\":\n",
    "        return spieler.code_eingabe_mensch\n",
    "    elif spieler.typ == 'KI':\n",
    "        return spieler.tippe_code\n",
    "    else:\n",
    "        raise ValueError(spieler.typ)\n",
    "\n",
    "# Diese Methode ist dafür verantworlich wie der Spieler das erhaltende Feedback verarbeitet\n",
    "def feedback_verarbeiten(spieler, anzahl_richtige_position, anzahl_richtige_farbe):\n",
    "    feedback_methode = waehle_feedback_methode(spieler)\n",
    "    return feedback_methode(anzahl_richtige_position, anzahl_richtige_farbe)\n",
    "\n",
    "# Diese Methode wählt die passende Feedbackmethode aus je nachdem ob der/die Spieler/in ein Mensch oder eine KI ist\n",
    "# Die jeweiligen Methoden werden weiter unten als Teil der entsprechenen Klasse (Mensch/KI) definiert.\n",
    "def waehle_feedback_methode(spieler):\n",
    "    if spieler.typ == \"Mensch\":\n",
    "        return spieler.feedback_mensch\n",
    "    elif spieler.typ == 'KI':\n",
    "        return spieler.feedback_ki\n",
    "    else:\n",
    "        raise ValueError(spieler.typ)\n",
    "        \n",
    "# Diese Methode gibt das Feedback einer Runde aus\n",
    "def zeige_feedback(anzahl_richtige_position, anzahl_richtige_farbe):\n",
    "    print('\\n'+'Feedback:')\n",
    "    print('Richtige Farbe und richtige Position: {}'.format(anzahl_richtige_position))\n",
    "    print('Richtige Farbe aber falsche Position: {}'.format(anzahl_richtige_farbe))\n",
    "    print('\\n')\n",
    "\n",
    "# Diese Methode wird am Anfang eines Spiels aufgerufen und zeigt an, welche Farben möglich sind\n",
    "def zeige_beschreibung(name):\n",
    "    print('\\nLass uns Mastermind spielen, {}!\\n'.format(name))\n",
    "    print('Du kannst eine Vermutung äußern, indem du einen Code bestehend aus bis zu vier der folgenden Farben eingibst:')\n",
    "    print('Farben: Gelb(y), Rot(r), Blau(b), Grün(g), Orange(o), Lila(p)')\n",
    "    print('Beispiel: rrgb'+'\\n')\n",
    "    print('Um das Spiel zu beenden, tippe \"ende\"!\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Im Folgenden Codeblock findet ihr die Methode, in der der Ablauf eines Mastermindspiels implementiert ist und die die Funktionen aufruft, die ihr oben implementiert habt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def spiele_mastermind(spieler):\n",
    "    gewonnen = False\n",
    "\n",
    "    # hier wird der geheime Farbcode festgelegt\n",
    "    farbcode = farbcode_festlegen()\n",
    "    \n",
    "    # falls der Spieler ein Mensch ist wird ihm eine kurze Beschreibung zum Spiel angezeigt\n",
    "    if spieler.typ == \"Mensch\":\n",
    "        name = spieler.name\n",
    "        zeige_beschreibung(name)\n",
    "    \n",
    "    runde = 1\n",
    "\n",
    "    while gewonnen != True:\n",
    "        \n",
    "        if spieler.typ == \"Mensch\":\n",
    "            print('Runde {}:'.format(runde))\n",
    "\n",
    "        # hier wird eine Vermutung für den geheimen Code vom Spieler gefordert\n",
    "        code = code_eingabe(spieler)\n",
    "\n",
    "        if len(code) == 0:\n",
    "            print('Das Spiel wurde abgebrochen.')\n",
    "            break\n",
    "            \n",
    "        # Die farbcode_raten() Method wertet den vermuteten Code aus und gibt Feedback\n",
    "        anzahl_richtige_position, anzahl_richtige_farbe = farbcode_raten(farbcode,code)\n",
    "        \n",
    "        # Die feedback_verarbeiten() Methode bestimmt wie der/die Spieler/in mit dem Feedback umgeht\n",
    "        feedback_verarbeiten(spieler,anzahl_richtige_position, anzahl_richtige_farbe)\n",
    "\n",
    "        # hier wird getestet, ob der Code bereits erraten wurde, ansonsten beginnt die nächste Runde\n",
    "        if code_erraten(anzahl_richtige_position):\n",
    "            if spieler.typ == \"Mensch\":\n",
    "                print('Bravo, {}! Du hast den Code in {} Versuchen erraten!'.format(spieler.name, runde))\n",
    "            gewonnen = True\n",
    "\n",
    "        else:\n",
    "            runde += 1\n",
    "            \n",
    "    return runde"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Um Mastermind spielen zu können, brauchen wir einen Spieler, entweder einen menschlichen Spieler oder eine KI. Wie wir oben gesehen haben bestimmt das Typ-Attribut dieses Spielers, welche Methoden für die Codeeingabe und die Feedbackverarbeitung aufgerufen werden.\n",
    "\n",
    "Zunächst erstellen wir eine Spielerklasse \"Mensch\". Die Klasse hat die zwei Attribute Typ und Name und je eine Methode , um einen Code einzugeben und um Feedback zu \"verarbeiten\" (bzw. anzuzeigen)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Mensch:\n",
    "    \n",
    "    def __init__(self, name):\n",
    "        self.typ = 'Mensch'\n",
    "        self.name = name\n",
    "        \n",
    "    # In dieser Methode ist die Eingabe einer Farbkombination für eine/n menschlichen Spieler/in implementiert\n",
    "    def code_eingabe_mensch(self):\n",
    "        farben_eingabe = []\n",
    "\n",
    "        while len(farben_eingabe) != 4:\n",
    "            code = input('Deine Vermutung:')\n",
    "\n",
    "            if code.lower() == 'ende':\n",
    "                break\n",
    "\n",
    "            farben_eingabe = [farbzuordnung[buchstabe] for buchstabe in code if buchstabe in farbzuordnung]\n",
    "            \n",
    "            if len(farben_eingabe) == 4:\n",
    "                print(farben_eingabe)\n",
    "            else:\n",
    "                print(\"\\033[31m Kein valider Farbcode! \\033[0m\")\n",
    "                print(\" Bitte gib eine vierstellige Vermutung bestehend aus den oben genannten Farben ein!\"+\"\\n\")\n",
    "\n",
    "        return farben_eingabe\n",
    "    \n",
    "    # Für einen Menschen wird das Feedback nur auf dem Bildschirm ausgegeben\n",
    "    def feedback_mensch(self, anzahl_richtige_position, anzahl_richtige_farbe):\n",
    "        zeige_feedback(anzahl_richtige_position, anzahl_richtige_farbe)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Super, jetzt sind wir startklar, um unser Mastermind-Spiel zu testen. Erstelle dir einen Spieler der Klasse Mensch mit deinem Namen und los geht's!\n",
    "\n",
    "**Hinweis**: Um das Spiel vorzeitig zu beenden, gib statt einer Farbkombination das Wort \"ende\" ein."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "name = input(\"Wie heißt du? \")\n",
    "mein_spieler = Mensch(name)\n",
    "anzahl_versuche = spiele_mastermind(mein_spieler)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## KI implementieren"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jetzt können wir unser Mastermind-Spiel schon selbst spielen. Als nächstes wollen wir eine KI programmieren, die Mastermind spielen kann.\n",
    "\n",
    "Wir wollen mit einer sehr simplen KI beginnen. \n",
    "Diese KI erstellt eine Liste mit allen möglichen Codes und geht diese nacheinander durch, bis sie die richtige Lösung gefunden hat.\n",
    "Bei 4 farbigen Stiften gewählt aus 6 möglichen Farben (mit Zurücklegen und Beachten der Reihenfolge) gibt es $6^4 = 1296$ mögliche Kombinationen.\n",
    "\n",
    "Wir definieren unsere KI als eigene Klasse. Wenn du dich mit Klassen (und Vererbung) in Python noch nicht so gut auskennst oder noch etwas dazulernen möchtest, dann schaue dir gerne die folgenden Links an:\n",
    "\n",
    "https://www.python-kurs.eu/python3_klassen_instanzattribute.php\n",
    "\n",
    "https://www.python-kurs.eu/python3_vererbung.php\n",
    "\n",
    "In der \\__ init\\__() Methode (die auch Konstruktor genannt wird) unserer KI Klasse können wir die Attribute, d. h. die Eigenschaften definieren, die unsere Klasse haben soll. Wir können dann innerhalb der Klasse mit self.eigenschaft auf die jeweilige Eigenschaft zugreifen. Zum Beispiel gibt uns self.typ den Typ unserer Klasse, d. h in unserem Fall 'KI'.\n",
    "\n",
    "Die ki_zuruecksetzen() Methode brauchen wir, da wir später viele Durchläufe des Spiels simulieren wollen, um zu testen wie viele Versuche die KI durchschnittlich braucht. Das heißt, falls du z. B. einen Index definierst, um durch alle möglichen Kombinationen durchzugehen, dann solltest du diesen in der ki_zuruecksetzen() Methode wieder auf den Anfangszustand zurücksetzen.\n",
    "\n",
    "Die tippe_code() Methode wird im Spiel immer dann aufgerufen, wenn eine Vermutung für den Code abgegeben werden soll und der Spieler vom Typ KI ist. Das heißt, diese Methode soll eine Liste mit vier Strings zurückgeben, die den Farben aus der oben definierten Farbliste entsprechen. Ein Beispiel wäre: ['Rot','Gelb','Gelb','Grün'].\n",
    "\n",
    "Da unsere simple KI das Feedback des Spiels nicht benutzt passiert nichts, wenn man die feedback_ki() Methode aufruft. Wir wollen diese Methode aber schon definieren, da die KI(s), die wir später erstellen wollen, von der simplen KI erben soll(en) und wir die Methode dann \"überschreiben\" also so anpassen, dass die KI das Feedback nutzen kann."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Mastermind_KI:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.typ = 'KI'\n",
    "        self.ki_zuruecksetzen()\n",
    "        \n",
    "    def ki_zuruecksetzen(self):\n",
    "        # BEGINN LÖSUNG\n",
    "        self.index = 0\n",
    "        self.kombinationen = [list(kombination) for kombination in itertools.product(farben,repeat=4)]\n",
    "        # ENDE LÖSUNG\n",
    "        \n",
    "    def tippe_code(self):\n",
    "        # BEGINN LÖSUNG\n",
    "        tipp = self.kombinationen[self.index].copy()\n",
    "        self.index += 1\n",
    "        # ENDE LÖSUNG\n",
    "        return tipp\n",
    "    \n",
    "    def feedback_ki(self,anzahl_richtige_position, anzahl_richtige_farbe):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bis jetzt haben wir das Feedback des anderen Spielers gänzlich ignoriert. Als nächstes wollen wir unsere KI so erweitern, dass sie das Feedback nutzen kann, um den Suchraum zu verkleinern und so den Code in weniger Versuchen zu erraten.\n",
    "\n",
    "Dafür gibt es natürlich verschiedene Strategien. Wir wollen die Folgende implementieren:\n",
    "Anstatt blind alle möglichen Kombinationen durchzugehen, soll die KI versuchen, erst einmal herauszufinden, welche Farben (nicht) im verdeckten Code vorkommen. Das verkleinert den Suchraum, da ja nur maximal vier der sechs Farben im Code vorkommen können.\n",
    "Dazu soll die KI erst alle einfarbigen Kombinationen, also z. B. ['Gelb','Gelb','Gelb','Gelb'] durchgehen und das Feedback nutzen, um die Kombinationen aus der Liste zu entfernen, die eine Farbe enthalten, die nicht vorkommt.\n",
    "\n",
    "**Tipp**: Mit super().methodenname kann man die Methoden der Elternklasse aufrufen. Um z. B. den Konstruktor der Elternklasse aufzurufen benutzt man folgende Codezeile: super().\\__init__()."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Mastermind_KI_version_2(Mastermind_KI):\n",
    "    \n",
    "    def __init__(self):\n",
    "        # BEGINN LÖSUNG\n",
    "        super().__init__()\n",
    "        self.farben_test = [[farbe]*4 for farbe in farben]\n",
    "        # ENDE LÖSUNG\n",
    "        \n",
    "    def ki_zuruecksetzen(self):\n",
    "        # BEGINN LÖSUNG\n",
    "        super().ki_zuruecksetzen()\n",
    "        self.teste_farben = True\n",
    "        # ENDE LÖSUNG\n",
    "    \n",
    "    def tippe_code(self):\n",
    "        # BEGINN LÖSUNG\n",
    "        if self.teste_farben:\n",
    "            tipp = self.farben_test[self.index].copy()\n",
    "            self.index += 1\n",
    "            \n",
    "            if self.index == len(self.farben_test):\n",
    "                self.teste_farben = False\n",
    "                self.index = 0\n",
    "                \n",
    "        else:\n",
    "            tipp = super().tippe_code()\n",
    "        # ENDE LÖSUNG\n",
    "            \n",
    "        return tipp\n",
    "    \n",
    "    def feedback_ki(self,anzahl_richtige_position, anzahl_richtige_farbe):\n",
    "        # BEGINN LÖSUNG\n",
    "        if self.teste_farben:\n",
    "            if (anzahl_richtige_position == 0) and (anzahl_richtige_farbe == 0):\n",
    "                self.kombinationen = [kombination for kombination in self.kombinationen if not farben[self.index-1] in kombination]\n",
    "        # ENDE LÖSUNG"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Anhand von einem Durchgang eines Mastermind-Spiels lassen sich verschiedene Spieler nicht besonders gut vergleichen. \n",
    "Deswegen wollen wir viele Spiele (z. B. 1000) simulieren und die Anzahl der benötigten Versuche mitteln, um ein verlässlicheres Ergebnis zu bekommen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def evaluiere_spieler(spieler, anzahl_durchlaeufe = 1000):\n",
    "    anzahl_versuche = []\n",
    "    \n",
    "    for durchlauf in range(anzahl_durchlaeufe):\n",
    "        spieler.ki_zuruecksetzen()\n",
    "        ergebnis = spiele_mastermind(spieler)\n",
    "        anzahl_versuche.append(ergebnis)\n",
    "        \n",
    "    mittel_anzahl_versuche = mean(anzahl_versuche)\n",
    "        \n",
    "    return mittel_anzahl_versuche"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Erstelle jeweils eine Instanz unserer KI-Klassen\n",
    "ki_1 = Mastermind_KI()\n",
    "ki_2 = Mastermind_KI_version_2()\n",
    "\n",
    "# Simuliere viele Spieldurchgänge (z. B. 1000) und berechne den Mittelwert der benötigten Versuche\n",
    "mittel_anzahl_versuche_ki1 = evaluiere_spieler(ki_1)\n",
    "mittel_anzahl_versuche_ki2 = evaluiere_spieler(ki_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als nächstes wollen wir unsere Spielerevaluation für unsere beiden KIs in einer Graphik visualisieren.\n",
    "\n",
    "Auf der X-Achse werden die Spieler/innen (KIs) dargestellt, die wir vergleichen wollen und auf der Y-Achse, die durchschnittliche Anzahl an Versuchen, die sie gebraucht haben, um den Code zu erraten (gemittelt wurde über 1000 Spiele).\n",
    "\n",
    "Die gestrichelte Linie markiert die maximale Anzahl an Versuchen, die man brauchen kann, wenn man keine Kombination doppelt rät. Wie wir oben schon festgestellt haben, gibt es  $6^4 = 1296$ Kombinationen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "# mit dieser Methode kann man ein Balkendiagramm erstellen, um die durchschnittlichen Ergebnisse der KIs zu vergleichen\n",
    "def evaluations_plot(spieler_namen, durchschnitt_anzahl_versuche):\n",
    "    \n",
    "    if len(spieler_namen) != len(durchschnitt_anzahl_versuche):\n",
    "        raise ValueError(\"Die Liste mit den Spielernamen und die Liste mit der durchschnittlichen Anzahl an Versuchen haben nicht die gleiche Länge!\")\n",
    "    \n",
    "    plt.figure(figsize=(8, 8), dpi=80)\n",
    "    plt.bar(range(len(durchschnitt_anzahl_versuche)),durchschnitt_anzahl_versuche, tick_label = spieler_namen, width=0.8)\n",
    "    plt.axhline(1296, linestyle=':', label='Maximal mögliche Anzahl')\n",
    "    plt.ylabel('Durchschnittliche Anzahl an Versuchen', fontsize=12)\n",
    "    plt.title(\"Evaluation der Mastermind-KIs\", fontsize=14)\n",
    "    plt.legend()\n",
    "\n",
    "    # Mittelwerte als Zahlen anzeigen\n",
    "    for index, value in enumerate(durchschnitt_anzahl_versuche):\n",
    "        plt.text(index, value+20, str(round(value,2)), horizontalalignment='center')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "spieler_namen = ['Mastermind_KI','Mastermind_KI_version_2']\n",
    "durchschnitt_anzahl_versuche = [mittel_anzahl_versuche_ki1,mittel_anzahl_versuche_ki2]\n",
    "\n",
    "evaluations_plot(spieler_namen, durchschnitt_anzahl_versuche)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zusatzaufgabe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Geht das nicht besser?\n",
    "\n",
    "Wir haben gesehen, dass wir die Anzahl an Versuchen, die die KI braucht um den Code zu erraten, um ein Vielfaches reduzieren können, wenn wir uns eine Strategie überlegen und das Feedback miteinbeziehen.\n",
    "Trotzdem würde die KI das Spiel selten gewinnen, da man im Spiel normalerweise nur 8-12 Versuche hat, um den Code zu erraten. Ansonsten gewinnt der/die Spieler/in, der/die sich den geheimen Code überlegt hat.\n",
    "\n",
    "Hast du eine Idee, wie man die KI noch verbessern kann, so dass sie vielleicht durchschnittlich nur 50 oder sogar nur 20 Versuche benötigt?\n",
    "\n",
    "Schreibe eine Klasse, die von einer der schon vorgegebenen KIs erbt und erweitere ihre Fähigkeiten, indem du die tippe_code() und/oder die feedback_ki() Methoden überschreibst oder neue Methoden hinzufügst.\n",
    "\n",
    "Evaluiere die neue KI mit der evaluiere_spieler-Methode und erstelle eine neue Graphik mit der evaluations_plot() Methode mit allen drei KIs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Mastermind_KI_version_3(...):\n",
    "    \n",
    "    def __init__(self):\n",
    "        ...\n",
    "        \n",
    "    def ki_zuruecksetzen(self):\n",
    "        ...\n",
    "        \n",
    "    def tippe_code(self):\n",
    "        ...\n",
    "        return tipp\n",
    "    \n",
    "    def feedback_ki(self,anzahl_richtige_position, anzahl_richtige_farbe):\n",
    "        ...\n",
    "        \n",
    "    \n",
    "    ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mögliche Lösung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine weitere Möglichkeit um unsere KI zu verbessern ist, das Feedback (das wir jede Runde bekommen) zu nutzen, um Kombinationen auszuschließen die damit nicht kompatibel sind.\n",
    "\n",
    "\n",
    "Das heißt, jedes mal, wenn wir Feedback zu unserer Vermutung bekommen haben, gehen wir alle Kombinationen durch, die noch in unserer Liste mit möglichen Kandidaten für den geheimen Code sind.\n",
    "Für jede Kombination aus dieser Liste überprüfen wir, welches Feedback wir bekommen würden, wenn diese Kombination der geheime Code wäre und unsere Vermutung die ist, die wir tatsächlich eingegeben haben. Ist dieses hypothetische Feedback nicht das gleiche wie das, welches wir tatsächlich bekommen haben, dann können wir die entsprechende Kombination ausschließen, weil sie nicht als geheimer Code in Frage kommt.\n",
    "\n",
    "\n",
    "**Beispiel**: <br /> \n",
    "Stell dir vor, du hast die Vermutung [\"Blau\", \"Blau\", \"Grün\", \"Grün\"] geäußert und bekommst als Feedback, dass 1 Stift an der richtigen Position ist und die richtige Farbe hat und das 2 Stifte zwar die richtige Farbe haben, aber an der falschen Position sind.\n",
    "\n",
    "Jetzt gehst du alle Kombinationen durch, die noch in der Liste der möglichen Kombinationen sind und testest, ob sie mit dem Feedback kompatibel ist. Stell dir z. B. vor, dass die Kombination [\"Blau\", \"Blau\", \"Orange\", \"Gelb\"] noch in deiner Liste von Kombinationen ist. Jetzt überprüfst du, welches Feedback du bekommen würdest, wenn diese Kombination der geheime Code wäre und du die obige Vermutung [\"Blau\", \"Blau\", \"Grün\", \"Grün\"] äußerst.\n",
    "\n",
    "Das Feedback wäre, dass 2 Stifte an der richtigen Position sind und die richtige Farbe haben. Das ist nicht das gleiche Feedback, wie das, was du tatsächlich bekommen hast. Daraus kannst du schließen, dass die Kombination [\"Blau\", \"Blau\", \"Orange\", \"Gelb\"] nicht der geheime Code sein kann und sie aus deiner Liste mit möglichen Kombinationen entfernen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Mastermind_KI_version_3(Mastermind_KI):\n",
    "    \n",
    "    def __init__(self):\n",
    "        super().__init__()\n",
    "        \n",
    "    def ki_zuruecksetzen(self):\n",
    "        super().ki_zuruecksetzen()\n",
    "    \n",
    "    # Diese Methode geht alle verbleibenden Kombinationen durch und testet, ob sie mit dem Feedback kompatibel sind\n",
    "    def feedback_testen(self):\n",
    "        for kombination in self.kombinationen:\n",
    "            if farbcode_raten(farbcode=kombination,code=self.tipp) != self.feedback:\n",
    "                self.kombinationen.remove(kombination)\n",
    "        \n",
    "    def tippe_code(self):\n",
    "        # Einfachheitshalber wird die nächste Vermutung zufällig aus der Liste der verbleibenden Kombinationen ausgewählt\n",
    "        self.tipp = random.choice(self.kombinationen)\n",
    "        self.kombinationen.remove(self.tipp)\n",
    "        \n",
    "        return self.tipp\n",
    "    \n",
    "    def feedback_ki(self,anzahl_richtige_position, anzahl_richtige_farbe):\n",
    "        self.feedback = anzahl_richtige_position,anzahl_richtige_farbe\n",
    "        self.feedback_testen()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ki_3 = Mastermind_KI_version_3()\n",
    "spiele_mastermind(ki_3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "mittel_anzahl_versuche_ki3 = evaluiere_spieler(ki_3)\n",
    "\n",
    "if 'Mastermind_KI_version_3' not in spieler_namen:\n",
    "    spieler_namen.append('Mastermind_KI_version_3')\n",
    "    durchschnitt_anzahl_versuche.append(mittel_anzahl_versuche_ki3)\n",
    "\n",
    "evaluations_plot(spieler_namen, durchschnitt_anzahl_versuche)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fragen & Feedback:\n",
    "\n",
    "**Wenn ihr Fragen oder Anregungen zu der Aufgabe (oder Lösung) habt, dann tauscht euch gerne im [Chat](https://spectrum.chat/bwki/aufgabenarchiv/) darüber aus oder schreibt uns eine E-Mail (an info@bw-ki.de). **\n",
    "\n",
    "Wir freuen uns auch immer über **Feedback** (auch unter info@bw-ki.de):\n",
    "\n",
    "- War diese Aufgabe zu leicht, zu schwer oder genau richtig?\n",
    "- Wie lang hast du für diese Aufgabe ungefähr gebraucht?\n",
    "- Welche Art von Aufgaben wünschst du dir in Zukunft?"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:bwki_env]",
   "language": "python",
   "name": "conda-env-bwki_env-py"
  },
  "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}