Muehle_Utilities.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": [
    "# Hilfsfunktionen\n",
    "Im Folgenden sollen Funktionen implementiert werden, die an verschiedenen Stellen in der Entwicklung des Mühlespiels genutzt werden können. Dazu sind sie so einfach wie möglich gehalten."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`count_player_pieces()` zählt die Steine, die ein anzugebender Spieler gerade auf dem Spielfeld hat. Dafür wird über alle möglichen Positionen iteriert und gezählt, bei wie vielen Positionen der Wert der Position mit dem Wert des Spielers übereinstimmt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_player_pieces(board, player):\n",
    "    return [position for ring in board for position in ring].count(player)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`empty_positions()` gibt eine Liste mit Tupeln zurück. Jedes Tupel der Form `(ring, cell)` beschreibt eine Stelle auf dem Spielfeld, auf der kein Spielstein steht, also der Wert 0 ist. So erhält man alle leeren Positionen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def empty_positions(board):\n",
    "    return player_pieces(board, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`neighboring_positions()` liefert für eine gegebene Position auf dem Spielfeld alle benachbarten Felder. Die Position wird dabei in der der Form `(ring, cell)` übergeben. Je nachdem wo sich die übergebene Stelle befindet, hat sie 2, 3 oder 4 Nachbarfelder, die es zu ermitteln gilt. Zunächst werden der linke und der rechte Nachbar ermittelt, den jede Position besitzt. Da die Zellen von 0 bis 7 durchnummeriert sind, muss 1 zu dem Zellenwert dazu addiert oder abgezogen werden. Um von 0 zu 7 und zurück zu gelangen, wird das Ergebnis noch Modulo 8 genommen.\n",
    "Die Zellen 1, 3, 5, 7 liegen in der Mitte und haben deshalb noch einen weiteren Nachbar, falls sie in Ring 0 oder 2 sind. Ansonsten haben sie sogar noch zwei weitere Nachbarpositionen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def neighboring_positions(position):\n",
    "    ring, cell = position\n",
    "    \n",
    "    left_neighbor  = (ring, (cell - 1) % 8)\n",
    "    right_neighbor = (ring, (cell + 1) % 8)\n",
    "        \n",
    "    positions = [left_neighbor, right_neighbor]\n",
    "        \n",
    "    if cell % 2 == 1:\n",
    "        if ring in [0, 2] :\n",
    "            positions.append((1, cell))\n",
    "        else:\n",
    "            positions.append((0, cell))\n",
    "            positions.append((2, cell))\n",
    "    return positions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`empty_neighbors()` berechnet ausgehend von einem gewählten Stein alle benachbarten leeren Felder.\n",
    "Hierfür wird ein Spielbrett, sowie die Position des ausgewählten Steines mit ring und cell übergeben. Zurückgegeben wird eine Liste der Position."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def empty_neighbors(board, ring, cell):\n",
    "    neighboring = set(neighboring_positions((ring, cell)))\n",
    "    empty = set(empty_positions(board))\n",
    "    return neighboring.intersection(empty)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`player_pieces()` gibt eine Liste mit allen Positionen eines zu übergebenden Spielers zurück. Jeder Eintrag der Form `(ring, cell)` beschreibt eine Stelle auf dem Spielfeld, auf der ein Spielstein des Spielers steht, also der Wert gleich dem Wert des Spielers ist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def player_pieces(board, player):\n",
    "    return [(ring, cell) for ring in range(3) for cell in range(8) if board[ring][cell] == player]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`opponent()` gibt den Gegner des übergebenen Spielers zurück. Falls 1 übergeben wird, kommt 2 zurück, ansonsten andersrum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def opponent(player):\n",
    "    return 3 - player"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`get_moved_piece` gibt den Stein eines Spielers zurück, der zwischen zwei zu übergebenden Zuständen bewegt wurde."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_moved_piece(old_board, new_board, player):\n",
    "    for ring in range(3):\n",
    "        for cell in range(8):\n",
    "            if old_board[ring][cell] == 0 and new_board[ring][cell] == player:\n",
    "                return (ring, cell)\n",
    "    return (None, None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Funktion `to_tuple()` wandelt einen übergebenen Spielstatus in Tupelform um."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_tuple(state):\n",
    "    return (tuple(state[0]), tuple(tuple(ring) for ring in state[1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Funktion `to_list()` wandelt einen übergebenen Spielstatus in Listenform um."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_list(state):\n",
    "    return [list(state[0]), [list(ring) for ring in state[1]]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mühlen\n",
    "`find_mills()` gibt alle Mühlen zurück, die ein Spieler auf dem übergebenen Spielbrett hat. Hierzu werden in der ersten Schleife alle Mühlen ermittelt, die sich auf einem einzigen Ringen befinden. Die zweite Schleife erkennt alle Mühlen, die sich über alle drei Ringe erstrecken. Die Eigenschaft einer Mühle ist, dass drei Steine in gerader Linie direkt nebeneinander liegen. Mühlen werden dabei als Tupel der Form `((ring 1, cell 1), (ring 2, cell 2), (ring 3, cell 3))` gespeichert."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_mills(board, player):\n",
    "    mills = set()\n",
    "    for ring in range (0,3):\n",
    "        for cell in [0,2,4,6]:\n",
    "            if(board[ring][cell] == board[ring][cell + 1] == board[ring][(cell + 2) % 8] == player):\n",
    "                mills.add(((ring, cell), (ring, cell + 1), (ring, (cell + 2) % 8)))\n",
    "    for cell in [1,3,5,7]:\n",
    "        if(board[0][cell] == board[1][cell] == board[2][cell] == player):\n",
    "            mills.add(((0, cell), (1, cell), (2, cell)))  \n",
    "    return mills          "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`find_new_mills()` gibt nur die Mühlen zurück, die durch setzen des Steins `piece` auf dem Spielbrett `board` entstanden sind."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_new_mills(board, piece):\n",
    "    new_mills = set()\n",
    "    (ring, cell) = piece\n",
    "    if (ring, cell) != (None, None):\n",
    "        if cell % 2 == 0: # Stein ist in einer Ecke\n",
    "            if board[ring][cell] == board[ring][(cell - 1) % 8] == board[ring][(cell - 2) % 8]: # rechte Ecke\n",
    "                new_mills.add(((ring, (cell - 2) % 8), (ring, (cell - 1) % 8), (ring, cell)))  \n",
    "            if board[ring][cell] == board[ring][(cell + 1) % 8] == board[ring][(cell + 2) % 8]: # linke Ecke\n",
    "                new_mills.add(((ring, cell), (ring, (cell + 1) % 8), (ring, (cell + 2) % 8)))\n",
    "        else: # Stein ist mittig \n",
    "            if board[ring][(cell - 1) % 8] == board[ring][cell] == board[ring][(cell + 1) % 8]: # innerhalb eines Rings\n",
    "                new_mills.add(((ring, (cell - 1) % 8), (ring, cell), (2, (cell + 1) % 8)))\n",
    "            if board[0][cell] == board[1][cell] == board[2][cell]: # über alle Ringe\n",
    "                new_mills.add(((0, cell), (1, cell), (2, cell))) \n",
    "    return new_mills"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`get_opponent_beatable_pieces()` gibt eine Liste mit entfernbaren Steinen des Gegners zurück. Dies ist notwendig, wenn auf Grund des Bildens einer Mühle Steine des Gegners entfernt werden dürfen.\n",
    "Dazu werden alle Steine sowie alle Mühlsteine des Gegners ermittelt. Die schlagbaren Steine sind die Steine des Spielers ohne dessen Mühlsteine. Ist das Ergebnis jedoch leer, werden alle Steine des Gegners zurückgegeben, da laut den offiziellen Regeln in diesem Fall auch Steine aus Mühlen entfernt werden können. Die Arbeit mit Mengen bringt hier keinen Performancevorteil."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_opponent_beatable_pieces(board, current_player):\n",
    "    opponent_player = opponent(current_player)\n",
    "\n",
    "    opponent_mill_pieces = [(ring, cell) for mill in find_mills(board, opponent_player) for (ring, cell) in mill]\n",
    "    opponent_pieces      = player_pieces(board, opponent_player)\n",
    "    beatable_pieces      = [piece for piece in opponent_pieces if piece not in opponent_mill_pieces]\n",
    "    \n",
    "    return beatable_pieces if len(beatable_pieces) != 0 else opponent_pieces"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`beat_pieces()` gibt alle möglichen Spielfelder zurück, nachdem eine bestimmte Anzahl an schlagbaren gegnerischen Steinen (`count`) entfernt, also durch den Wert 0 ersetzt, wurde. Die Eingabeparameter sind dazu ein Spielbrett, also der zweite Teile von `state`, eine natürliche Zahl, die der Anzahl der zu entfernenden Steine entspricht, und ein Spieler, der die Steine entfernt. Die Methode funktioniert rekursiv. Als Rekursionsanker dient `count <= 0`. Ist `count` größer als 1, können Boards mehrmals entstehen, diese werden im Anschluss entfernt. Das Duplikateentfernen wäre schöner, wenn man statt den Listen Mengen verwenden würde. Dazu müsste aber State auf Tupel umgestellt werden, da Lists mutable sind. Wenn noch umgeformt werden muss, bringt das keinen Performancevorteil."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def beat_pieces(board, count, player):\n",
    "    if count <= 0: return [board]\n",
    "    \n",
    "    boards = []\n",
    "    beatable_pieces = get_opponent_beatable_pieces(board, player)\n",
    "    for ring, cell in beatable_pieces:\n",
    "        new_board = copy.deepcopy(board)\n",
    "        new_board[ring][cell] = 0\n",
    "        boards.extend([new_board]) if count == 1 else boards.extend(beat_pieces(new_board, count - 1, player))\n",
    "    \n",
    "    if count >= 1:\n",
    "        # Duplikate entfernen\n",
    "        result = []\n",
    "        for board in boards:\n",
    "            if board not in result:\n",
    "                result.append(board)\n",
    "        return result\n",
    "    return boards"
   ]
  }
 ],
 "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.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}