{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Projet IA Grundy R1.13 Python \n",
"### Grégoire MAROUSE 1C1 & Floriant LE JONCOUR 1C2 \n",
"\n",
"***"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1 - Présentation jeu de Grundy :\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Le jeu de Grundy consiste à opposer deux joueurs qui devront partager, chacun leur tour, un tas d'allumettes en deux tas inégaux. Le gagnant est le dernier joueur à avoir joué.\n",
"\n",
"### Mise en place\n",
"\n",
"\n",
"Le jeu de Grundy se joue à 2 joueurs selon les règles suivantes : \n",
"- On commence la partie avec un tas de $n$ allumettes\n",
"- Les deux joueurs jouent alternativement\n",
"- On sépare un tas en deux tas contenant un nombre d'allumettes différent. (donc impossible de choisir des tas de 1 ou 2 allumettes)\n",
"- La personne qui réalise le dernier coup possible gagne la partie. (présence uqiquement de tas contenant une ou deux allumettes à la fin de la partie)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Sommaire\n",
"\n",
"2 - PRÉREQUIS\n",
"\n",
"3 - CODE JEU DE GRUNDY (JOUEUR)\n",
"- a - Affichage du message de bienvenu\n",
"- b - Affichage du plateau\n",
"- c - Condition de victoire\n",
"- d - Vérifier la validité d'un coup\n",
"- e - Jouer un coup (joueur)\n",
"- f - Jeu joueur contre joueur\n",
"- g - Stockage de la stratégie de l'IA\n",
"- h - Jeu joueur contre IA\n",
"\n",
"4 - IA DU JEU DE GRUNDY\n",
"- a - Stockage de la stratégie\n",
"- b - Jouer un coup (IA)\n",
"- c - Joueur contre IA\n",
"- d - Jeu IA contre IA\n",
"- e - Règles d'apprentissage\n",
"- f - Entrainement IA contre aléatoire\n",
"- g - Entrainement odri contre lui même\n",
"- h - Entrainement ordi contre ordi"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"***\n",
"## 2 - Prérequis"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"import matplotlib.pyplot as plt\n",
"%matplotlib inline\n",
"plt.rcParams['figure.figsize'] = (12, 12)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"***\n",
"## 3 - Code jeu de Grundy (Joueur)\n",
"#### a - Affichage du message de bienvenu"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"----------------------------------------------------------------------------\n",
" Règles du jeu de Grundy\n",
"----------------------------------------------------------------------------\n",
"Règles : 1 - Les joueur jouent à tour de rôle.\n",
" 2 - Choisir un tas à séparer en 2 tas de tailles différentes\n",
" 3 - Celui qui ne peux plus séparer de tas en 2 perd.\n",
"----------------------------------------------------------------------------\n",
"\n"
]
}
],
"source": [
"def welcome_message_joueur():\n",
" \"\"\"\n",
" Fonction d'affichage du message au début du jeu\n",
" \"\"\"\n",
" print(\"\"\"\n",
"----------------------------------------------------------------------------\n",
" Règles du jeu de Grundy\n",
"----------------------------------------------------------------------------\n",
"Règles : 1 - Les joueur jouent à tour de rôle.\n",
" 2 - Choisir un tas à séparer en 2 tas de tailles différentes\n",
" 3 - Celui qui ne peux plus séparer de tas en 2 perd.\n",
"----------------------------------------------------------------------------\n",
"\"\"\")\n",
" \n",
"# Example usage:\n",
"welcome_message_joueur()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### b - Affichage du plateau"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" . oo . ooo . o . o .\n"
]
}
],
"source": [
"def display_board_with_x(plateau):\n",
" \"\"\"\n",
" Fonction d'affichage du platea de jeu au format : . oo . o .\n",
" Prend en argument le tableau représentatif du plateau de jeu\n",
" ne renvoi rien\n",
" \"\"\"\n",
" #Affichage des \".\"\n",
" for i in range (len(plateau)) :\n",
" print(\" . \",end=\"\")\n",
" indice=0 \n",
" valeurL=plateau[i]\n",
" #Affichage des \"o\"\n",
" while(indice2 )\n",
" coupValid=False\n",
" if tasValid :\n",
" coupValid= ( 1<=coup[1]<=(plateau[coup[0]]-1) and coup[1]!=(plateau[coup[0]]-coup[1]) )\n",
"\n",
" return (tasValid and coupValid)\n",
"\n",
"# Example usage:\n",
"l=[2,3,1,1]\n",
"t1 = testCoup(l,[1,2]) #true\n",
"t2 = testCoup(l,[0,1]) #false"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### e - Jouer un coup (Joueur)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On enregistre le tas et la séparation que le joueur souhaite réaliser puis on appele la fonction testCoup() tant que le coup n'est pas jouable. On réalise ensuite les modifications sur le plateau"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" . oo . oooo . o . o .\n"
]
},
{
"data": {
"text/plain": [
"[2, 3, 1, 1, 1]"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def joueur(tab) :\n",
" \"\"\"\n",
" Fonction qui permet au joueur de jouer un coup\n",
" Prends en parametre le tableau représentatif du plateau de jeu\n",
" Ne renvoi rien, modifi directement le tableau\n",
" \"\"\"\n",
" coup = []\n",
" coup.append(int(input(\"Quel tas souhaitez-vous séparer ? \")))\n",
" coup.append(int(input(\"Quel taille pour le premier sous-tas ? \")))\n",
"\n",
" while (not(testCoup(tab,coup))) :\n",
" print(\"Veuiller saisir un coup valide !\")\n",
" coup[0]=int(input(\"Quel tas souhaitez-vous séparer ? \"))\n",
" coup[1] = int(input(\"Quel taille pour le premier sous-tas ? \"))\n",
" \n",
" tab[coup[0]]-=coup[1]\n",
" tab.append(coup[1])\n",
"\n",
"# Example usage:\n",
"l=[2,4,1,1]\n",
"display_board_with_x(l)\n",
"joueur(l)\n",
"l"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### f - Jeu joueur contre joueur"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Fonction qui permet de jouer au jeu. On initialise un tableau de taille n, une variable tour qui va nous permettre de savoir à qui est-ce le tour de jouer et une variable v qui va nous permettre de vérifier si la partie est terminée ou non."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"----------------------------------------------------------------------------\n",
" Règles du jeu de Grundy\n",
"----------------------------------------------------------------------------\n",
"Règles : 1 - Les joueur jouent à tour de rôle.\n",
" 2 - Choisir un tas à séparer en 2 tas de tailles différentes\n",
" 3 - Celui qui ne peux plus séparer de tas en 2 perd.\n",
"----------------------------------------------------------------------------\n",
"\n",
" au tour du premierjoueur ... \n",
"la taille des tas est : [5]\n",
" . ooooo .\n",
" au tour du deuxiemejoueur ... \n",
"la taille des tas est : [4, 1]\n",
" . oooo . o .\n",
" au tour du premierjoueur ... \n",
"la taille des tas est : [3, 1, 1]\n",
" . ooo . o . o .\n",
" . oo . o . o . o .\n",
"Fin! le premier joueur à gagné !\n"
]
}
],
"source": [
"def JvJ(n) :\n",
" \"\"\"\n",
" Fonction qui permet de jouer une partie joueur contre joueur\n",
" Prends en parametre la taille du tas de départ\n",
" ne renvoi rien\n",
" \"\"\"\n",
" welcome_message_joueur()\n",
"\n",
"\n",
" tab = [n]\n",
" tour = -1\n",
" v= False\n",
" while not v :\n",
" tour +=1\n",
" print(\" au tour du \"+(\"premier\" if tour%2==0 else \"deuxieme\")+\"joueur ... \\nla taille des tas est :\",tab)\n",
" display_board_with_x(tab)\n",
" joueur(tab)\n",
" v = victoire(tab)\n",
" display_board_with_x(tab)\n",
" print(\"Fin! le \"+(\"premier\" if tour%2==0 else \"deuxieme\")+ \" joueur à gagné !\")\n",
"\n",
"# Example usage:\n",
"JvJ(5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"***\n",
"## 4 - IA du jeu de Grundy"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### a - Stockage de la stratégie"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour initialiser le dictionnaire contenant la stratégie, on utilise une fonction récursive qui effectue un parcours de tous les chemins possibles depuis la situation donnée. Le dictionnaire ressence pour chaque situation un autre dictionnaires des coups possibles dans cette situation précise. on associe a chacun de ces coups une vleur initiale $n$."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'5': {'0,1': 1, '0,2': 1}, '4': {'0,1': 1}, '3': {'0,1': 1}}"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def stratInit(plat,strat,n) :\n",
" \"\"\"\n",
" Fonction récursive qui gère l'initialisation du dictionnaire de stratégie de l'IA par un parcours de chemin depuis un plateau de jeu.\n",
" Prends en paramettre plat le plateau de jeu, strat la variable qui contiendra le dictionnaire de stratégie et n la valeurs initiale des cases du dicitionnaire\n",
" \"\"\"\n",
"\n",
" string = \",\".join(str(x) for x in plat)\n",
" strat[string]={}\n",
" for x in range(len(plat)) :\n",
" for y in range(1,(plat[x]//2 if plat[x]%2==0 else (plat[x]//2)+1)) :\n",
" coup=str(x)+\",\"+str(y)\n",
" strat[string][coup]=n\n",
"\n",
" for i in range(len(plat)) :\n",
" for j in range(1,(plat[i]//2 if plat[i]%2==0 else (plat[i]//2)+1)):\n",
" test = plat.copy()\n",
" test[i]-=j\n",
" test.append(j)\n",
" while 1 in test or 2 in test :\n",
" if 1 in test :\n",
" test.remove(1)\n",
" if 2 in test :\n",
" test.remove(2)\n",
" test.sort()\n",
" stratInit(test,strat,n)\n",
" return\n",
"\n",
"# Example usage :\n",
"strat = {}\n",
"stratInit([5],strat,1)\n",
"strat.pop('')\n",
"strat"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### b - Jouer un coup (IA)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La fonction coup IA Permet à l'IA de jouer un coup. Pour cela on commence par retrouver la situation dans la stratégie en normalisant le plateau. Puis on choisie un coup aléatoire dans le dictionnaire en fonction des pondérations associés à chauqe coup. Enfin on modifie le plateau de jeu en fonction du coup choisi et on renvoi le coup en String qui est la clef du dictionnaire choisie dans cette situation."
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" L'IA à séparer le tas 2 en 1 et 4\n"
]
},
{
"data": {
"text/plain": [
"[1, 1, 4, 1]"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def coupIA(tab,strat,verb=False) :\n",
" \"\"\"\n",
" fonction qui permet à l'IA de jouer un coup sur le plateau : tab à partir d'une stratégie donnée : strat\n",
" Prend en paramètre tab le plateau de jeu, strat le dictionnaire de stratégie de l'IA et l'option verb un booléen qui gère l'affichage\n",
" renvoi le coup jouer en String\n",
" \"\"\"\n",
" \n",
" jeu = tab.copy()\n",
" while 1 in jeu or 2 in jeu :\n",
" if 1 in jeu :\n",
" jeu.remove(1)\n",
" if 2 in jeu :\n",
" jeu.remove(2)\n",
" string = \",\".join(str(x) for x in jeu)\n",
" coupStr = random.choice([key for key, value in strat[string].items() for x in range(value)])\n",
" coup = [int(x) for x in coupStr.split(\",\")]\n",
" if verb : print(\" L'IA à séparer le tas \",((len(tab)-len(jeu))+coup[0]),\"en\",coup[1],\"et\",tab[(len(tab)-len(jeu))+coup[0]]-coup[1])\n",
" tab[(len(tab)-len(jeu))+coup[0]]-=coup[1]\n",
" tab.append(coup[1])\n",
" return coupStr\n",
"\n",
"# Example usage:\n",
"tab=[1,1,5]\n",
"coupIA(tab,strat,True)\n",
"tab"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### c - Jeu joueaur contre IA"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Fonction qui encadre le cycle de jeu entre un joueur et une IA, pour un jeu de taille n et la stratégie strat pour l'IA. A la fin on renvoi un booléen : True si l'IA à gagnée et un dictionnaire qui stock la partie dont on pourra se servir pour permettre à l'IA d'apprendre."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Au tour de l'IA ... \n",
" La taille des tas est : [3]\n",
" . ooo .\n",
" L'IA à séparer le tas 0 en 1 et 2\n",
" . o . oo .\n",
"Fin! L'IA a gagné !\n"
]
},
{
"data": {
"text/plain": [
"({'3': '0,1'}, True)"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def JvAI(n,strat) :\n",
" \"\"\"\n",
" Fonction qui permet de jouer une partie joueur contre une IA\n",
" Prends en parametre la taille du tas de départ et la stratégie de l'IA\n",
" \"\"\"\n",
"\n",
" tab = [n]\n",
" partie = {} \n",
" tour = 0\n",
" v= False\n",
" while not v :\n",
" situation = tab.copy()\n",
" while 1 in situation or 2 in situation :\n",
" if 1 in situation :\n",
" situation.remove(1)\n",
" if 2 in situation :\n",
" situation.remove(2)\n",
" string = \",\".join(str(x) for x in situation)\n",
"\n",
" tour +=1\n",
" print(\"Au tour \"+(\"du joueur \" if tour%2==0 else \"de l'IA \")+\"... \\n La taille des tas est :\",tab)\n",
" display_board_with_x(tab)\n",
"\n",
" if tour%2==0 :\n",
" joueur(tab) \n",
" else :\n",
" coup=coupIA(tab,strat,True)\n",
" partie[string]=coup\n",
"\n",
" tab.sort()\n",
" v = victoire(tab)\n",
"\n",
" display_board_with_x(tab)\n",
" print(\"Fin! \"+(\"Le joueur\" if tour%2==0 else \"L'IA\")+ \" a gagné !\")\n",
" return partie,True if tour%2==1 else False\n",
"\n",
"# Example usage:\n",
"# strat aléatoire\n",
"aleatoire = {}\n",
"stratInit(tab,aleatoire,1)\n",
"aleatoire.pop('')\n",
"JvAI(3,aleatoire)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### d - Jeu IA contre IA"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Fonction qui encadre le cycle de jeu entre 2 IA dans le but de réaliser un entrainement en boucle soit contre l'aléatoire si on entraine qu'une des deux stratégie l'autre est seulempent initialisée, sinon contre une stratégie précise ou une autre IA qui apprends séparement."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"({'7': '0,2', '3': '0,1'}, True, {'5': '0,2'})"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def IAvIA(n,strat1,strat2,verb=False) :\n",
" \"\"\"\n",
" Fonction qui permet de jouer une partie joueur contre IA\n",
" Prends en parametre la taille du tas de départ n, strat1 et strat2 les stratégie des IA et l'option verb pour gérer l'affichage.\n",
" renvoi true si l'IA 1 a gagné ainsi que les enregistrements des parties de chaque IA en dictionnaire\n",
" \"\"\"\n",
" tab = [n]\n",
" partie1 = {} \n",
" partie2 = {} \n",
" tour = -1\n",
" v= False\n",
" while not v :\n",
" situation = tab.copy()\n",
" while 1 in situation or 2 in situation :\n",
" if 1 in situation :\n",
" situation.remove(1)\n",
" if 2 in situation :\n",
" situation.remove(2)\n",
" string = \",\".join(str(x) for x in situation)\n",
"\n",
" tour +=1\n",
" if verb :\n",
" print(\"Au tour \"+(\"de l'IA 1 \" if tour%2==0 else \"de l'IA 2 \")+\"... \\n La taille des tas est :\",tab)\n",
" display_board_with_x(tab)\n",
"\n",
" if tour%2==0 :\n",
" coup=coupIA(tab,strat1)\n",
" partie1[string]=coup\n",
" else :\n",
" coup=coupIA(tab,strat2)\n",
" partie2[string]=coup\n",
"\n",
" tab.sort()\n",
" v = victoire(tab)\n",
" if verb :\n",
" display_board_with_x(tab)\n",
" print(\"Fin! \"+(\"L'IA 1\" if tour%2==0 else \"L'IA 2\")+ \" a gagné !\")\n",
" return partie1,True if tour%2==0 else False,partie2\n",
"\n",
"# Example usage:\n",
"# strat contre aleatoire\n",
"tab = [7]\n",
"strat = {}\n",
"stratInit(tab,strat,5)\n",
"strat.pop('')\n",
"aleatoire=strat.copy()\n",
"IAvIA(7,strat,strat)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### e - Règles d'aprentissage "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour l'apprentissage nous avons choisi des règles simples : si l'IA gagne on ajoute 1 au coéfficients des coups qu'elle a jouer si elle perds on enlève 1. De plus, le coéfficiant minimum est 1 pour ne jamais faire disparaitre completement un coup \"par malchance\"."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Au tour de l'IA ... \n",
" La taille des tas est : [7]\n",
" . ooooooo .\n",
" L'IA à séparer le tas 0 en 1 et 6\n",
"Au tour du joueur ... \n",
" La taille des tas est : [1, 6]\n",
" . o . oooooo .\n",
"Au tour de l'IA ... \n",
" La taille des tas est : [1, 2, 4]\n",
" . o . oo . oooo .\n",
" L'IA à séparer le tas 2 en 1 et 3\n",
"Au tour du joueur ... \n",
" La taille des tas est : [1, 1, 2, 3]\n",
" . o . o . oo . ooo .\n",
" . o . o . o . oo . oo .\n",
"Fin! Le joueur a gagné !\n"
]
},
{
"data": {
"text/plain": [
"{'7': {'0,1': 4, '0,2': 5, '0,3': 5},\n",
" '6': {'0,1': 5, '0,2': 5},\n",
" '5': {'0,1': 5, '0,2': 5},\n",
" '4': {'0,1': 4},\n",
" '3': {'0,1': 5},\n",
" '3,4': {'0,1': 5, '1,1': 5},\n",
" '3,3': {'0,1': 5, '1,1': 5}}"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def apprend(rec,strat) :\n",
" \"\"\"\n",
" Fonction qui modifie la stratégie de l'IA en fonction de la partie et de la victoire\n",
" Prends en paramettre rec le tupple contenant le dictionnaire ou est stocké la partie et un booléen de victoire sur cette partie\n",
" Prend aussi en paramettre la stratégie à modifier\n",
" \"\"\"\n",
" partie=rec[0]\n",
" victoire=rec[1]\n",
"\n",
" for situation in partie :\n",
" coup = partie[situation]\n",
" if victoire :\n",
" strat[situation][coup]+=1\n",
" elif strat[situation][coup]>1 :\n",
" strat[situation][coup]-=1\n",
"\n",
"# Example usage:\n",
"strat = {}\n",
"stratInit([7],strat,5)\n",
"strat.pop('')\n",
"apprend(JvAI(7,strat),strat)\n",
"strat"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### f - entrainement IA contre aléatoire"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avec les fonctions précédentes, on peut créer une stratégie initiale et une stratégie aléatoire puis les faire jouer ensembles un nombre de parties choisi sur un jeu de taille n pour entrainer l'IA sur un grand nombre de parties très rapidement et donc dévelloper une stratégie gagnante probabiliste à cause de la partie aléatoire des coups jouer par l'IA (cf jouer un coup IA plus haut) mais qui peut s'avérer très efficace et de plus en plus efficace avec le nombre de parties jouées.\n",
"La fonction calcule également le taux de victoire après chaque partie et renvoi le tableaux de ces taux à la fin.\n",
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"y=entrainementIAvAleatoire(50_000, 12)\n",
"x=[x for x in range(1,50_001)]\n",
"\n",
"print(\"Après entrainement contre un environement jouant aléatoirement sur un jeu de taille initiale 12, l'ordinateur gagne \\n-------------- \", y[-1] ,\" % du temps\")\n",
"\n",
"plt.figure()\n",
"plt.plot(x, y, color='orange', marker='+', markeredgewidth=2)\n",
"plt.xlabel(\"Nombre de parties jouées\")\n",
"plt.ylabel(\"Tau de victoire (%)\")\n",
"plt.grid()\n",
"plt.title(\"Entrainement contre l'aléatoire\")\n",
"plt.show()\n"
]
}
],
"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.11.9"
}
},
"nbformat": 4,
"nbformat_minor": 2
}