python/mastermind/mastermind.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f888c508",
   "metadata": {},
   "source": [
    "# [Mastermind](https://fr.wikipedia.org/wiki/Mastermind)\n",
    "## Objet du problème\n",
    "On se propose de faire jouer à l'ordinateur le rôle du décodeur dans le jeu Mastermind. L'algorithme utilisé, dû à [Donald Knuth](https://fr.wikipedia.org/wiki/Donald_Knuth), est nommé *five-guess* car il permet de trouver le code caché en au plus cinq propositions (cinq motifs proposés).\n",
    "\n",
    "On donne ensuite un autre algorithme (D. L. Greenwell), pour le mastermind classique ($p=4$ positions et $n=6$ couleurs), qui consiste à faire 6 propositions d'un coup, avec toujours les 6 mêmes motifs, pour ensuite déduire le code caché des indications associées à ces 6 propositions.\n",
    "\n",
    "## Mise en place des données du jeu\n",
    "Les couleurs étant numérotées de $0$ à $n-1$, un code ou un un motif est un élément de $\\{0,\\ldots,n-1\\}^p$ ; une indication est un couple (nombre de bien placés, nombre de mal placés).  \n",
    "Dans le but d'afficher les codes, motifs et indications, on les représente par des jolies chaines de caractères colorées en utilisant l'unicode.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "ce8def25",
   "metadata": {},
   "outputs": [],
   "source": [
    "p, n = 4, 6\n",
    "\n",
    "colors = '🔴🟢🔵🟡⚫⚪🟣🟠' # n supposé <= 8\n",
    "\n",
    "def repr(t):\n",
    "    if len(t) == p:\n",
    "        s = ''\n",
    "        for i in t: s += colors[i]\n",
    "        return s\n",
    "    else:\n",
    "        return '● ' * t[0] + '⚬ ' * t[1] + '  ' * (p - t[0] - t[1]) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "083a01e0",
   "metadata": {},
   "source": [
    "`totalCodes` $=\\{0,\\ldots,n-1\\}^p$ est l'ensemble de tous le codes (ou motifs) possibles.   \n",
    "`hints` est la liste des indications possibles.  \n",
    "`getHint`$(c,m)$ calcule l'indication $h$ associée à un motif $m$, le code $c$ étant connu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "9d660c86",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "totalCodes = set(product(*(range(n) for _ in range(p))))\n",
    "hints = [(w, b) for w in range(p + 1) for b in range(p + 1 - w) if (w,b) != (p - 1, 1)]\n",
    "\n",
    "def getHint(code, pattern):\n",
    "    well = len([i for i in range(p) if code[i] == pattern[i]])\n",
    "    def N(t, j):\n",
    "        return len([i for i in range(p) if t[i] == j])\n",
    "    bad = sum([min(N(code,j), N(pattern,j)) for j in range(n)]) - well\n",
    "    return well, bad"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5843ef1c",
   "metadata": {},
   "source": [
    "On calcule tous les `getHint`$(c,m)$ et on les stocke dans un dictionnaire `totalHints`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "db5e9aa9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1296^2 = 1679616 calculs\n"
     ]
    }
   ],
   "source": [
    "# 1/2 mn pour p, n = 4, 6\n",
    "totalHints = dict()\n",
    "for code in totalCodes:\n",
    "    for pattern in totalCodes:\n",
    "        totalHints[(code, pattern)] = getHint(code, pattern)\n",
    "print(f'{n**p}^2 = {n**(2*p)} calculs')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8242103f",
   "metadata": {},
   "source": [
    "La fonction `decreaseCodes` prend en entrée\n",
    "- un ensemble $C$ de codes (une partie de `totalCodes`) qui contient le code caché ;\n",
    "- un motif $m$ et son indication associée $h$.\n",
    "\n",
    "Elle renvoie la partie $C'$ de $C$ formée des codes de $C$ qui, face au motif $m$, fournirait la même indication $h$.  \n",
    "Ainsi, $C'$ contient encore le code caché et possède moins d'éléments que $C$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "4e245d94",
   "metadata": {},
   "outputs": [],
   "source": [
    "def decreaseCodes(codes, pattern, hint):\n",
    "\n",
    "    return {code for code in codes if totalHints[(code, pattern)] == hint}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f951b793",
   "metadata": {},
   "source": [
    "## L'algorithme five-guess\n",
    "La fonction `nextPattern`$(C)$ est la fonction principale de l'algorithme. Elle prend en entrée un ensemble $C$ de codes qui contient le code caché et renvoie le motif $m$ qui, en un certain sens, fera le plus décroitre $C$. Remarque pas très maline : si on connaissait à l'avance l'indication $h$, on choisirait le motif pour lequel le cardinal de `decreaseCodes`$(C,m,h)$ soit minimum. En fait, on choisit $m$ pour que max $\\{$ card $($`decreaseCodes`$(C,m,h)), h\\in$ `hints`$\\}$ soit minimum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "5d194ad8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nextPattern(codes):\n",
    "\n",
    "    if len(codes) == 1: return codes.pop()\n",
    "    wMin = len(codes)\n",
    "    for pattern in totalCodes:\n",
    "        W = 0\n",
    "        for hint in hints:\n",
    "            w = len(decreaseCodes(codes, pattern, hint))\n",
    "            W = max(W, w)\n",
    "        if W < wMin:\n",
    "            wMin = W\n",
    "            patternMin = pattern\n",
    "    return patternMin"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b764590b",
   "metadata": {},
   "source": [
    "Comme le calcul est un peu long (15 s pour $p,n=4,6$), on calcule une fois pour toutes le premier motif à proposer "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "b42826d0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'⚪🔴🔴⚪'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "initPattern = nextPattern(totalCodes)\n",
    "repr(initPattern)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82c87bba",
   "metadata": {},
   "source": [
    "La fonction suivante simule l'exécution de l'algorithme pour un code \"caché\" donné"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "d508cd37",
   "metadata": {},
   "outputs": [],
   "source": [
    "def simulateKnuth(secretCode, verbose = True):\n",
    "    \n",
    "    if verbose:\n",
    "        print(f'secret : {repr(secretCode)}')\n",
    "    codes = totalCodes\n",
    "    k = 1\n",
    "    pattern = initPattern\n",
    "    hint = totalHints[(secretCode, pattern)]\n",
    "    while True:\n",
    "        codes = decreaseCodes(codes, pattern, hint)\n",
    "        if verbose:\n",
    "            print(f'{repr(pattern)} -> {repr(hint)} => {len(codes)} possibilites')\n",
    "        if len(codes) == 1:\n",
    "            guessCode = codes.pop()\n",
    "            if secretCode != guessCode:\n",
    "                raise Exception(f'ERREUR : {repr(secretCode)} => {repr(guessCode)} ??') # jamais exécuté\n",
    "            if verbose:\n",
    "                print(f'resultat en {k} propositions : {repr(guessCode)}')\n",
    "            break\n",
    "        k += 1\n",
    "        pattern = nextPattern(codes)\n",
    "        hint = totalHints[(secretCode, pattern)]\n",
    "    return k"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eee83fdf",
   "metadata": {},
   "source": [
    "Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "ab64eff7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "secret : 🔴🟢🔵🟡\n",
      "⚪🔴🔴⚪ -> ⚬        => 256 possibilites\n",
      "🔵🟢🟢🔴 -> ● ⚬ ⚬    => 21 possibilites\n",
      "🔴🟢🟡🔵 -> ● ● ⚬ ⚬  => 2 possibilites\n",
      "🔵🟡🟢⚫ -> ⚬ ⚬ ⚬    => 1 possibilites\n",
      "resultat en 4 propositions : 🔴🟢🔵🟡\n"
     ]
    }
   ],
   "source": [
    "_ = simulateKnuth((0,1,2,3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11d07695",
   "metadata": {},
   "source": [
    "L'exécution (longue : plus d'1/4 d'heure) de la cellule suivante calcule le maximum, pour tout code, du nombre de propositions nécessaire au calcul de ce code. Le résultat 4 (donc 5 si on compte la dernière étape de vérification) montre la validité de l'algorithme."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "6cf4f32e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Algorithme de Knuth prouvé\n"
     ]
    }
   ],
   "source": [
    "# Vérification de la validité (15 mns pour (p, n) == (4, 6), 9 jours pour (p, n) = (4, 8))\n",
    "from IPython.display import clear_output\n",
    "maxk = 0\n",
    "total = p ** n\n",
    "for i, c in enumerate(totalCodes):\n",
    "    clear_output()\n",
    "    print(f'maximum actuel du nombre de propositions : {maxk}')\n",
    "    maxk = max(simulateKnuth(c), maxk)\n",
    "clear_output()\n",
    "if (p, n) == (4, 6):\n",
    "    if maxk == 4:\n",
    "        print('Algorithme de Knuth prouvé')\n",
    "else:\n",
    "    print(f'Pour (p,n) = {(p, n)}, le maximum du nombre de propositions nécessaires est {maxk}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "062262a3",
   "metadata": {},
   "source": [
    "Les fonctions suivantes permettent à l'ordinateur décodeur de jouer contre un humain codeur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "2f14b52c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def initKnuth():\n",
    "\n",
    "    global initPattern, currentCodes, currentPattern\n",
    "\n",
    "    currentCodes = totalCodes\n",
    "    currentPattern = initPattern\n",
    "    print(f' motif proposé : {repr(initPattern)}')\n",
    "\n",
    "def playKnuth(hint, verbose = True):\n",
    "\n",
    "    global currentCodes, currentPattern\n",
    "    \n",
    "    currentCodes = decreaseCodes(currentCodes, currentPattern, hint)\n",
    "    if verbose:\n",
    "        print((f'{repr(currentPattern)} -> {repr(hint)} => {len(currentCodes)} possibilités'))\n",
    "    if len(currentCodes) == 1:\n",
    "        print(f'solution : {repr(currentCodes.pop())}')\n",
    "    else:\n",
    "        currentPattern = nextPattern(currentCodes)\n",
    "        print(f' nouveau motif proposé : {repr(currentPattern)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4bcf7d9f",
   "metadata": {},
   "source": [
    "Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "6452b51b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " motif proposé : ⚪🔴🔴⚪\n"
     ]
    }
   ],
   "source": [
    "initKnuth()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "662cb2cf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "⚪🔴🔴⚪ -> ⚬        => 256 possibilités\n",
      " nouveau motif proposé : 🔵🟢🟢🔴\n"
     ]
    }
   ],
   "source": [
    "playKnuth((0,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "7d2c8b63",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "🔵🟢🟢🔴 -> ● ⚬ ⚬    => 21 possibilités\n",
      " nouveau motif proposé : 🔴🟢🟡🔵\n"
     ]
    }
   ],
   "source": [
    "playKnuth((1,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "89a3c3e4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "🔴🟢🟡🔵 -> ● ● ⚬ ⚬  => 2 possibilités\n",
      " nouveau motif proposé : 🔵🟡🟢⚫\n"
     ]
    }
   ],
   "source": [
    "playKnuth((2,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "25dc61f7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "🔵🟡🟢⚫ -> ⚬ ⚬ ⚬    => 1 possibilités\n",
      "solution : 🔴🟢🔵🟡\n"
     ]
    }
   ],
   "source": [
    "playKnuth((0,3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4821f4f9",
   "metadata": {},
   "source": [
    "## L'algorithme de Greenwell\n",
    "Greenwell propose les 6 motifs suivants"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "18834dc4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "🔴🟢🟢🔴\n",
      "🟢🔵⚫🟡\n",
      "🔵🔵🔴🔴\n",
      "🟡⚫🟢🟡\n",
      "⚫⚪⚫⚪\n",
      "⚪⚪🟡🔵\n"
     ]
    }
   ],
   "source": [
    "greenwell = (0,1,1,0), (1,2,4,3), (2,2,0,0), (3,4,1,3), (4,5,4,5), (5,5,3,2)\n",
    "for pattern in greenwell: print(repr(pattern))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "927a565f",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def playGreenwell(hints, verbose = True):\n",
    "    codes = totalCodes\n",
    "    for k, hint in enumerate(hints):\n",
    "        pattern = greenwell[k]\n",
    "        codes = decreaseCodes(codes, pattern, hint)\n",
    "        if verbose:\n",
    "            print(f'{repr(pattern)} -> {repr(hint)} => {len(codes)} possibilites')\n",
    "        if len(codes) == 1:\n",
    "            guessCode = codes.pop()\n",
    "            if verbose:\n",
    "                print(f'Résultat : {repr(guessCode)}')\n",
    "            return guessCode\n",
    "    print('INFORMATION INSUFFISANTE') # jamais exécuté\n",
    "\n",
    "def simulateGreenwell(secretCode, verbose = True):\n",
    "    if verbose:\n",
    "        print(f'secret : {repr(secretCode)}')\n",
    "    guessCode = playGreenwell([totalHints[(secretCode, greenwell[k])] for k in range(6)], verbose=verbose)\n",
    "    if guessCode is None:\n",
    "        return False\n",
    "    if secretCode != guessCode:\n",
    "        raise Exception(f'ERREUR : {secretCode} => {guessCode} ??')\n",
    "    return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "3efec671",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "secret : 🔴🟢🔵🟡\n",
      "🔴🟢🟢🔴 -> ● ●      => 114 possibilites\n",
      "🟢🔵⚫🟡 -> ● ⚬ ⚬    => 10 possibilites\n",
      "🔵🔵🔴🔴 -> ⚬ ⚬      => 2 possibilites\n",
      "🟡⚫🟢🟡 -> ● ⚬      => 1 possibilites\n",
      "Résultat : 🔴🟢🔵🟡\n"
     ]
    }
   ],
   "source": [
    "_ = simulateGreenwell((0,1,2,3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "4027d97b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Algorithme de Greenwell prouvé\n"
     ]
    }
   ],
   "source": [
    "# Vérification de la validité\n",
    "for c in totalCodes:\n",
    "    if not simulateGreenwell(c, verbose = False):\n",
    "        raise Exception(f\"Le code {repr(c)} n'a pas été trouvé\") # jamais exécuté\n",
    "print('Algorithme de Greenwell prouvé')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33724370",
   "metadata": {},
   "source": [
    "Pour faire jouer le programme en lui donnant les  6 indications associées aux 6 motifs de `greenwell`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "07b7d74d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "🔴🟢🟢🔴 -> ● ●      => 114 possibilites\n",
      "🟢🔵⚫🟡 -> ● ⚬ ⚬    => 10 possibilites\n",
      "🔵🔵🔴🔴 -> ⚬ ⚬      => 2 possibilites\n",
      "🟡⚫🟢🟡 -> ● ⚬      => 1 possibilites\n",
      "Résultat : 🔴🟢🔵🟡\n"
     ]
    }
   ],
   "source": [
    "_ = playGreenwell([(2, 0), (1, 2), (0, 2), (1, 1), (0, 0), (0, 2)])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}