Muehle_Introduction.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%HTML\n",
    "<style>\n",
    ".container { width:100% }\n",
    "</style>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Einleitung\n",
    "Mühle ist ein Brettspiel für zwei Spieler, deren  Ziel es ist, durch das Positionieren von jeweils neun Spielsteinen eine sogenannte \"Mühle\" zu bilden. Dabei befinden sich drei Steine eines Spielers in einer Reihe, um so die Steine des Gegners entfernen zu dürfen. Gewonnen hat, wer alle gegnerischen Steine bis auf zwei geschlagen hat, oder den Gegner so zubaut, dass dieser nicht mehr ziehen kann. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aufgabenstellung\n",
    "\n",
    "Das Ziel dieser Arbeit ist die Implementierung eines Mühle-Spiels mit Hilfe der Programmiersprache Python. Dabei soll es möglich sein, in einem Jupyter Notebook mit Hilfe einer Künstlichen Intelligenz (KI) gegen einen Computer zu spielen. Die KI verwendet dabei die Algorithmen Minimax und Alpha-Beta-Pruning und nutzt Transpositions-Tabellen. Die grafische Oberfläche soll mit Hilfe von ipywidgets und ipycanvas gestaltet werden.\n",
    "Die Künstliche Intelligenz sollte sinnvolle Spielzüge wählen, und es so dem menschlichen Spieler möglichst schwer machen, zu gewinnen. Die Implementierung ist an das [Skript](https://github.com/karlstroetmann/Artificial-Intelligence/blob/master/Lecture-Notes/artificial-intelligence.pdf) von Professor Dr. Stroetmann angelehnt."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Struktur\n",
    "Das Mühle-Spiel kann über das Notebook `Muehle_Game.ipynb` gestartet werden.\n",
    "\n",
    "Zum Lesen und Verstehen der Anwendung ist folgende Reihenfolge zu empfehlen:\n",
    "\n",
    "1. **Einführung**\n",
    "2. **Mühle** - In diesem Kapitel werden die Spielregeln und Eigenschaften des Brettspiels erläutert.\n",
    "3. **`Muehle_GUI.ipynb`** - Hier befindet sich die Implementierung der Graphischen Nutzeroberfläche, die dem menschlichen Spieler die Kommunikation und Interaktion erleichtert, sowie die Steuerung des Spielablaufs.\n",
    "4. **`Muehle_Utilities.ipynb`** - Die in diesem Abschnitt enthaltenen Hilfsfunktionen werden an unterschiedlichen Stellen verwendet und erleichtern die Implementierung der restlichen Komponenten.\n",
    "5. **`Muehle_Logic.ipynb`** - In diesem Kapitel wird die Logik des Mühlespiels abgebildet. Dazu gehört die Ermittlung aller möglichen nächsten Zustände, die ausgehend von einem Zustand in einem Zug zu erreichen sind.\n",
    "6. **`Muehle_Heuristic.ipynb`** - Eine Heuristik, wie sie in diesem Kapitel beschrieben ist, bewertet einen Zustand aus der Sicht eines Spielers und ermittelt so seine Gewinnwahrscheinlichkeit.\n",
    "7. **`Muehle_Algo.ipynb`** - In diesem Kapitel werden die beiden Algorithmen implementiert, die die Künstliche Intelligenz darstellen.\n",
    "8. **`Muehle_Conclusion.ipynb`** - Abschließend werden die Ergebnisse bewertet und die Algorithmen Minimax und Alpha-Beta-Pruning hinsichtlich ihrer Spielstärke verglichen. Außerdem sollen mögliche Weiterentwicklungen diskutiert werden."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Einrichten der Entwicklungsumgebung\n",
    "### erstes Mal\n",
    "Zunächst sollte das Projekt geklont werden. Das GitHub Repository ist unter https://github.com/luisafuss/muehle-studienarbeit zu finden. Darin enthalten ist die Datei `environment.yml`, die genutzt werden kann, um eine virtuelle Umgebung inklusive aller benötigen Libraries zu erhalten.\n",
    "\n",
    "Um das Environment zu erstellen, muss im Projektordner über die Anaconda Prompt folgender Befehl aufgerufen werden:\n",
    "\n",
    "```\n",
    "conda env create -f environment.yml\n",
    "```\n",
    "\n",
    "Alternativ steht auch die Datei `requirements.txt` zur Verfügung.\n",
    "### jedes Mal\n",
    "Die eingerichtete Umgebung kann mit Hilfe des folgenden Befehls aktiviert werden:\n",
    "```\n",
    "conda activate muehle\n",
    "```\n",
    "\n",
    "Als Nächstes kann Jupyter notebook mit folgendem Befehl gestartet werden:\n",
    "```\n",
    "jupyter notebook\n",
    "```\n",
    "\n",
    "### Beenden\n",
    "Um den Kernel herunterzufahren, kann der Shortcut `Crtl + c` in der Anaconda Prompt genutzt werden.\n",
    "\n",
    "Zum Verlassen des Environments dient der Befehl\n",
    "\n",
    "```\n",
    "conda deactivate\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mühle\n",
    "Mühle ist ein sogenanntes Nullsummenspiel mit perfekter Information. Unter Nullsummenspiel versteht man in der Spieltheorie ein Spiel, bei dem der Gewinn des einen Spielers, den Verlust des anderen bedeutet (vgl. Holler, S.55). Formal bedeutet dies:\n",
    "\n",
    "$$\\forall state \\in Terminalstates : utility(state, playerOne) + utility(state, playerTwo) = 0$$\n",
    "\n",
    "wobei gilt:\n",
    "$$\n",
    "utility(state, player) = \\begin{cases}\n",
    "-1 & \\texttt{falls player verliert bei Zustand state}\\\\\n",
    " 0 & \\texttt{falls Unentschieden}\\\\\n",
    " 1 & \\texttt{falls player gewinnt bei Zustand state.}\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "Ein Spiel mit perfekter Information ist laut Walter Schlee ein Spiel, bei dem jedem Spieler die getroffenen Entscheidungen des Gegners bekannt sind. Dies ist bei Mühle der Fall, da ersichtlich ist, welcher Stein von wo nach wo bewegt oder wohin er gesetzt wurde.\n",
    "Quellen: \n",
    "* Manfred J. Holler, Gerhard Illing: Einführung in die Spieltheorie. 7. Auflage. Springer, Berlin u. a., 2009, ISBN 978-3-540-69372-7\n",
    "* Walter Schlee: Einführung in die Spieltheorie: mit Beispielen und Aufgaben, Vieweg+Teubner Verlag, 2004, ISBN 978-3-528-03214-6, S. 95"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Anzahl möglicher Zustände\n",
    "Zunächst soll die Anzahl möglicher Zustände $N$ berechnet werden, um die Größenordnung des Spiels besser einschätzen zu können. Ein Mühlebrett besitzt 24 Positionen, auf denen Steine platziert werden können. Jede Position kann drei Zustände annehmen:\n",
    "$$\n",
    "ZustandPosition = \\begin{cases}\n",
    " 0 & \\texttt{falls kein Stein auf der Position ist}\\\\\n",
    " 1 & \\texttt{falls ein Stein des Spielers 1 auf der Position ist}\\\\\n",
    " 2 & \\texttt{falls ein Stein des Spielers 2 auf der Position ist.}\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "Damit ergibt sich\n",
    "$$ N = 3^{24} = 282.429.536.481$$\n",
    "\n",
    "als obere Schranke für die Anzahl der zu betrachtenden Zustände.\n",
    "\n",
    "Beachtet man jedoch, dass sich höchstens neun Steine eines Spielers auf dem Spielfeld befinden, lässt sich die Anzahl der Zustände $N$ weiter einschränken.\n",
    "\n",
    "Es gilt:\n",
    "\n",
    "* 0 bis 9 weiße Steine auf dem Feld\n",
    "* 0 bis 9 schwarze Steine auf dem Feld\n",
    "* (24 - Anzahl Weiß - Anzahl Schwarz) leere Felder\n",
    "\n",
    "Daraus folgt:\n",
    "<center>\n",
    "    Möglichkeiten \"Weiß\" zu platzieren = $\\binom{24}{weiß}$\n",
    "</center>\n",
    "\n",
    "<center>\n",
    "    Möglichkeiten \"Schwarz\" zu platzieren = $\\binom{24-weiß}{schwarz}$\n",
    "</center>\n",
    "\n",
    "Um die Anzahl der Zustände zu erhalten müssen diese Werte multipliziert werden. Die Gesamtanzahl aller Zustände ergibt sich aus der Summe aller Zustände bei $weiß \\in \\{0, 1, ..., 9\\}$ und $schwarz \\in \\{0, 1, ..., 9\\}$ Markierungen.\n",
    "Das bedeutet:\n",
    "<center>\n",
    "    \\[ Anzahl Zustände = \\sum_{weiß=0}^9 \\sum_{schwarz=0}^9\\binom{24}{weiß} * \\binom{24-weiß}{schwarz}\\]\n",
    "</center>\n",
    "\n",
    "Noch weiter lässt sich die Anzahl der Zustände $N$ einschränken, wenn man beachtet, dass eine Drehung des Spielfelds um 90°, 180° oder 270° im Grunde den gleichen Spielzustand darstellt. Auch die Spiegelungen an der waagrechten und senkrechten Achse sowie an den beiden Diagonalen stellen Symmetrien dar, die die Anzahl der zu betrachtenden Zustände $N$ verringert. Auch die Inversion des Spielfeldes von innen nach außen und andersherum, kann bei korrekter Bearbeitung zu einer niedrigeren Anzahl der Zustände $N$ führen. Diese Symmetrien werden im Rahmen der Implementierung jedoch nicht beachtet, weshalb an dieser Stelle die exakte Berechnung der Anzahl der Zustände $N$ für diese Fälle nicht erläutert werden soll."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import scipy.special\n",
    "anzahl_zustaende = 0\n",
    "for weiß in range(10):\n",
    "    for schwarz in range(10):\n",
    "        anzahl_zustaende += scipy.special.binom(24, weiß) * scipy.special.binom(24-weiß, schwarz)\n",
    "print(\"Die Anzahl der Zustände beträgt \" + \"{:,}\".format(int(anzahl_zustaende))+\".\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Spielbrett und Spielsteine\n",
    "<img src=\"images/spielbrett_beispiel.JPG\" alt=\"Beispiel eines Spielbrettes\" width=\"300\"/>\n",
    "Ein typisches Mühlebrett besteht aus drei Quadraten, die durch vier Linien verbunden sind. Die Quadrate werden als Innenring, Mittelring und Außenring bezeichnet. Jeder Spieler hat neun Spielsteine, meist runde Holzscheiben, in weiß und schwarz/braun. Diese können auf eine von 24 Positionen gesetzt werde. Die Positionen ergeben sich aus Kreuzungen von zwei Linien. So entstehen 12 Eckpunkte an den Ecken der Quadrate, vier Kreuzpunkte im Mittelring, und acht T-Punkte im Innen- bzw. Außenring.\n",
    "Zu Beginn des Spiels befinden sich keine Spielsteine auf dem Spielbrett."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Spielablauf\n",
    "Basierend auf den Regeln des Welt-Mühle-Dachverbands (WMD) besteht das Spiel aus drei aufeinanderfolgenden Spielphasen:\n",
    "* Setzphase: Die Spieler setzen einen ihrer Steine auf eine beliebige leere Position.\n",
    "* Zugphase: Die Spieler ziehen einen ihrer Spielsteine von einer Position auf eine benachbarte leere Position\n",
    "* Sprungphase: Die Spieler springen mit einem ihrer Spielsteine von einer Position auf eine beliebige leere Position"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Spielregeln\n",
    "Die Spieler sind abwechselnd an der Reihe und befinden sich zunächst in der Setzphase, bis alle neun Steine platziert sind. Anschließend sind sie solange in der Zugphase, bis sie nur noch drei Steine besitzen und damit in die Sprungphase wechseln. \n",
    "\n",
    "Wer eine Mühle schließt (drei Steine waagrecht oder senkrecht nebeneinander), darf einen beliebigen Stein des Gegners entfernen, solange sich dieser nicht in einer Mühle befindet. Hat der Gegner ausschließlich in einer Mühle befindliche Steine, so dürfen auch diese entfernt werden. Werden mit einem Zug zwei Mühlen geschlossen, dürfen auch zwei gegnerische Steine entfernt werden.\n",
    "\n",
    "Kann ein Spieler in der Zugphase keinen seiner Steine bewegen, da alle benachbarten Felder belegt sind, so hat er verloren.\n",
    "Hat ein Spieler weniger als drei Steine, hat er ebenfalls verloren.\n",
    "Wurde 30 Runden lang keine Mühle geschlossen, endet das Spiel mit einem Unentschieden."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die offiziellen Turnierregeln des WMD sind hier zu finden: http://www.muehlespiel.eu/images/pdf/WMD_Turnierreglement.pdf."
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}