DEV5.2/TP01/Nim.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implémentation du jeu de Nim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "etat_jeu = [3, 4, 5] # Trois tas contenant respectivement 3, 4 et 5 objets.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 4, 5]\n",
      "[0, 0, 0]\n",
      "[1, 0, 2]\n"
     ]
    }
   ],
   "source": [
    "# A.\n",
    "def afficher_etat(etat_jeu) :\n",
    "    print(etat_jeu)\n",
    "\n",
    "\n",
    "# B.\n",
    "test1 = [3, 4, 5]\n",
    "test2 = [0, 0, 0]\n",
    "test3 = [1, 0, 2]\n",
    "\n",
    "afficher_etat(test1)\n",
    "afficher_etat(test2)\n",
    "afficher_etat(test3)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 2 : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5)]\n",
      "[]\n",
      "[(0, 1), (2, 1), (2, 2)]\n"
     ]
    }
   ],
   "source": [
    "# A.\n",
    "\n",
    "def generer_mouvement(etat_jeu) : \n",
    "    mouvements = []\n",
    "    for i in range(len(etat_jeu)) : # On parcourt les tas\n",
    "        for j in range(etat_jeu[i]) : # On tire le nombre d'objets dans le tas\n",
    "            if etat_jeu[i] > 0 :\n",
    "                mouvements.append((i, j+1)) # On ajoute le mouvement à la liste\n",
    "    return mouvements\n",
    "\n",
    "# B.\n",
    "print(generer_mouvement(test1))\n",
    "print(generer_mouvement(test2))\n",
    "print(generer_mouvement(test3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 3 : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A et B\n",
    "def appliquer_mouvement(etat_jeu, tas_index, nombre_objets) :\n",
    "    if nombre_objets > etat_jeu[tas_index] :\n",
    "        print(\"Erreur : nombre d'objets à retirer supérieur au nombre d'objets dans le tas.\")\n",
    "        return etat_jeu\n",
    "    else : \n",
    "        etat_jeu[tas_index] -= nombre_objets\n",
    "        return etat_jeu\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 4 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\" étant donné que  heuristique est égale à la somme des objets dans les tas, \\nc'est donc un calcul simple qui ne dépend pas de l'ordre des tas. \""
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# A.\n",
    "'''\n",
    "def heuristique(etat_jeu) :\n",
    "    return sum(etat_jeu)\n",
    "\n",
    "print(heuristique(test1))\n",
    "print(heuristique(test2))\n",
    "print(heuristique(test3))'''\n",
    "\n",
    "# B.\n",
    "''' étant donné que  heuristique est égale à la somme des objets dans les tas, \n",
    "c'est donc un calcul simple qui ne dépend pas de l'ordre des tas. '''\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 5 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "# A.\n",
    "def est_etat_final(etat_jeu) :\n",
    "    return sum(etat_jeu) == 0\n",
    "\n",
    "# B.\n",
    "def cout_transition(etat_courant, etat_suivant):\n",
    "    return 1\n",
    "\n",
    "# Exemple d'utilisation\n",
    "etat_courant = [3, 4, 5]\n",
    "etat_suivant = appliquer_mouvement(etat_courant, 0, 1)  # Devrait retourner [2, 4, 5]\n",
    "print(cout_transition(etat_courant, etat_suivant))  # Devrait retourner 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 6 : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[4, 8, 5], [4, 0, 5], [0, 0, 5], [0, 0, 0]]\n"
     ]
    }
   ],
   "source": [
    "import heapq\n",
    "\n",
    "class Noeud:\n",
    "    def __init__(self, etat, parent, cout, heuristique):\n",
    "        self.etat = etat\n",
    "        self.parent = parent\n",
    "        self.cout = cout\n",
    "        self.heuristique = heuristique\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.cout + self.heuristique < other.cout + other.heuristique\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self.etat == other.etat\n",
    "\n",
    "    def __hash__(self):\n",
    "        return hash(tuple(self.etat))\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.etat)\n",
    "    \n",
    "def xor_etat(etat_jeu):\n",
    "    xor_total = 0\n",
    "    for nb_objets in etat_jeu:\n",
    "        xor_total ^= nb_objets\n",
    "    return xor_total\n",
    "\n",
    "def heuristique(etat_jeu):\n",
    "    xor_valeur = xor_etat(etat_jeu)\n",
    "    if xor_valeur == 0:\n",
    "        # Position désavantageuse (perdante)\n",
    "        return 100 + sum(etat_jeu)  # Pénalité\n",
    "    else:\n",
    "        # Position avantageuse (gagnante)\n",
    "        return sum(etat_jeu)  # Heuristique standard\n",
    "\n",
    "def est_etat_final(etat):\n",
    "    return all(pile == 0 for pile in etat)\n",
    "\n",
    "def generer_successeurs(etat):\n",
    "    successeurs = []\n",
    "    for i in range(len(etat)):\n",
    "        if etat[i] > 0:\n",
    "            for j in range(1, etat[i] + 1):\n",
    "                nouvel_etat = etat[:]\n",
    "                nouvel_etat[i] -= j\n",
    "                successeurs.append(nouvel_etat)\n",
    "    return successeurs\n",
    "\n",
    "def algorithme_a_star(etat_initial):\n",
    "    noeud_initial = Noeud(etat_initial, None, 0, heuristique(etat_initial))\n",
    "    frontiere = []\n",
    "    heapq.heappush(frontiere, noeud_initial)\n",
    "    visites = set()\n",
    "\n",
    "    while frontiere:\n",
    "        noeud_courant = heapq.heappop(frontiere)\n",
    "\n",
    "        if est_etat_final(noeud_courant.etat):\n",
    "            chemin = []\n",
    "            while noeud_courant:\n",
    "                chemin.append(noeud_courant.etat)\n",
    "                noeud_courant = noeud_courant.parent\n",
    "            return chemin[::-1]\n",
    "\n",
    "        visites.add(tuple(noeud_courant.etat))\n",
    "\n",
    "        for successeur in generer_successeurs(noeud_courant.etat):\n",
    "            if tuple(successeur) not in visites:\n",
    "                cout = noeud_courant.cout + cout_transition(noeud_courant.etat, successeur)\n",
    "                heur = heuristique(successeur)\n",
    "                noeud_successeur = Noeud(successeur, noeud_courant, cout, heur)\n",
    "                heapq.heappush(frontiere, noeud_successeur)\n",
    "\n",
    "    return None\n",
    "\n",
    "# Exemple d'utilisation\n",
    "etat_initial = [4, 8, 5]\n",
    "chemin_optimal = algorithme_a_star(etat_initial)\n",
    "print(chemin_optimal)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 7 :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(voir cellule précédante)\n",
    "\n",
    "A. \n",
    "- Initialisation:\n",
    "    - Crée un nœud initial avec l'état initial du jeu.\n",
    "    - Utilise une file de priorité (heap) pour gérer les nœuds à explorer.\n",
    "    - Utilise un ensemble (set) pour stocker les états déjà visités.\n",
    "- Boucle principale:\n",
    "    - Tant que la file de priorité n'est pas vide, extraire le nœud avec le coût total (coût + heuristique) le plus bas.\n",
    "    - Si l'état du nœud courant est un état final, reconstruire et retourner le chemin depuis l'état initial jusqu'à l'état final.\n",
    "    - Ajouter l'état courant à l'ensemble des états visités.\n",
    "    - Générer les états successeurs et les ajouter à la file de priorité s'ils n'ont pas été visités.\n",
    "- Retour: Si aucun chemin n'est trouvé, retourner None.\n",
    "\n",
    "B.\n",
    "- Vérification des états visités, avant d'ajouter un successeur à la file de priorité, on vérifie si ils ont été visité.\n",
    "- Une fois qu'un successeur est ajouté, il est ajouté à la file de priorité et marqué comme visité.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 8 : "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A. \n",
    "Une représentation de son parent est crée dans la classe noeud. Lorsque qu'un successeur est crée, le noeud courant est défini comme parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[3, 4, 5], [3, 4, 4], [3, 4, 0]]\n"
     ]
    }
   ],
   "source": [
    "# B.\n",
    "\n",
    "def reconstruire_chemin(noeud_final):\n",
    "    \"\"\"\n",
    "    Reconstruit la séquence de mouvements depuis l’état initial jusqu’à l’état final.\n",
    "    \n",
    "    :param noeud_final: Le nœud final de l'algorithme A*.\n",
    "    :return: Une liste des états représentant le chemin de l'état initial à l'état final.\n",
    "    \"\"\"\n",
    "    chemin = []\n",
    "    noeud_courant = noeud_final\n",
    "    while noeud_courant:\n",
    "        chemin.append(noeud_courant.etat)\n",
    "        noeud_courant = noeud_courant.parent\n",
    "    return chemin[::-1]\n",
    "\n",
    "# Création d'un chemin d'exemple pour tester la fonction\n",
    "etat_initial = [3, 4, 5]\n",
    "etat_intermediaire = [3, 4, 4]\n",
    "etat_final = [3, 4, 0]\n",
    "\n",
    "noeud_final = Noeud(etat_final, Noeud(etat_intermediaire, Noeud(etat_initial, None, 0, 0), 1, 0), 2, 0)\n",
    "chemin = reconstruire_chemin(noeud_final)\n",
    "print(chemin)  # Devrait retourner [[3, 4, 5], [3, 4, 4], [3, 4, 0]]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 9 : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 4, 5]\n",
      "[3, 4, 5]\n",
      "\n",
      "L'IA joue...\n",
      "[3, 4, 0]\n",
      "[0, 4, 0]\n",
      "\n",
      "L'IA joue...\n",
      "\n",
      " L'IA a gagné !\n"
     ]
    }
   ],
   "source": [
    "def jeu_nim(etat_initial):\n",
    "    etat = etat_initial[:]\n",
    "    while not est_etat_final(etat):\n",
    "        afficher_etat(etat)\n",
    "        try:\n",
    "            pile = int(input(\"Entrez le numéro de la pile (1, 2, 3, ...): \")) - 1\n",
    "            nb_objets = int(input(\"Entrez le nombre d'objets à retirer: \"))\n",
    "            appliquer_mouvement(etat, pile, nb_objets)\n",
    "            afficher_etat(etat)\n",
    "        except ValueError:\n",
    "            print(\"Entrée invalide. Veuillez entrer des nombres entiers.\")\n",
    "            continue\n",
    "\n",
    "        if est_etat_final(etat):\n",
    "            print(\"\\nFélicitations ! Vous avez gagné !\")\n",
    "            break\n",
    "\n",
    "        # Tour de l'IA\n",
    "        chemin_optimal = algorithme_a_star(etat)\n",
    "        if chemin_optimal and len(chemin_optimal) > 1:\n",
    "            etat_ia = chemin_optimal[1]\n",
    "            print(\"\\nL'IA joue...\")\n",
    "            etat = etat_ia\n",
    "\n",
    "        if est_etat_final(etat):\n",
    "            print(\"\\n L'IA a gagné !\")\n",
    "            break\n",
    "\n",
    "# Exemple d'utilisation\n",
    "etat_initial = [3, 4, 5]\n",
    "jeu_nim(etat_initial)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 10 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def xor_etat(etat_jeu):\n",
    "    xor_total = 0\n",
    "    for nb_objets in etat_jeu:\n",
    "        xor_total ^= nb_objets\n",
    "    return xor_total\n",
    "\n",
    "def heuristique_amelioree(etat_jeu):\n",
    "    xor_valeur = xor_etat(etat_jeu)\n",
    "    if xor_valeur == 0:\n",
    "        # Position désavantageuse (perdante)\n",
    "        return 100 + sum(etat_jeu)  # Pénalité\n",
    "    else:\n",
    "        # Position avantageuse (gagnante)\n",
    "        return sum(etat_jeu)  # Heuristique standard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bonus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# création d'un système de sauvegarde des parties jouées\n",
    "\n",
    "def sauvegarder_partie(historique):\n",
    "    \"\"\"\n",
    "    Sauvegarde l'historique de la partie dans un fichier.\n",
    "    \n",
    "    :param historique: Liste des coups effectués pendant la partie.\n",
    "    :param fichier: Nom du fichier où sauvegarder l'historique.\n",
    "    \"\"\"\n",
    "    fichier = \"historique.txt\"\n",
    "    with open(fichier, \"a\") as f:\n",
    "        f.write(\"Nouvelle partie :\")\n",
    "        for coup in historique:\n",
    "            f.write(f\"{coup} \")\n",
    "        f.write(\"\\n\")\n",
    "\n",
    "\n",
    "# modification de la fonction jeu_nim pour sauvegarder l'historique des coups\n",
    "def jeu_nim(etat_initial):\n",
    "    etat = etat_initial[:]\n",
    "    historique = []\n",
    "    while not est_etat_final(etat):\n",
    "        afficher_etat(etat)\n",
    "        try:\n",
    "            pile = int(input(\"Entrez le numéro de la pile (1, 2, 3, ...): \")) - 1\n",
    "            nb_objets = int(input(\"Entrez le nombre d'objets à retirer: \"))\n",
    "            historique.append(f\"Joueur: Pile {pile + 1}, Objets retirés: {nb_objets}\")\n",
    "            appliquer_mouvement(etat, pile, nb_objets)\n",
    "            historique.append(f\"Player: {etat}\")\n",
    "            afficher_etat(etat)\n",
    "        except ValueError:\n",
    "            print(\"Entrée invalide. Veuillez entrer des nombres entiers.\")\n",
    "            continue\n",
    "\n",
    "        if est_etat_final(etat):\n",
    "            print(\"\\nFélicitations ! Vous avez gagné !\")\n",
    "            break\n",
    "\n",
    "        # Tour de l'IA\n",
    "        chemin_optimal = algorithme_a_star(etat)\n",
    "        if chemin_optimal and len(chemin_optimal) > 1:\n",
    "            etat_ia = chemin_optimal[1]\n",
    "            historique.append(f\"IA: Pile {pile + 1}, Objets retirés: {nb_objets}\")\n",
    "            print(\"\\nL'IA joue...\")\n",
    "            etat = etat_ia\n",
    "            historique.append(f\"AI: {etat}\")\n",
    "\n",
    "        if est_etat_final(etat):\n",
    "            print(\"\\n L'IA a gagné !\")\n",
    "            break\n",
    "    sauvegarder_partie(historique)"
   ]
  }
 ],
 "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.10.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}