| Programmez par plaisir! |
30-07-2010 03:37 |
Introduction
Description
Screenshots
Documentation
Téléchargements
Le but de ce projet est d'implémenter un algorithme Alpha/Béta et de l'appliquer au jeu de chomp. C'est un jeu de plateau contenant m * n (colonnes * lignes) jetons. Deux adversaires jouent à tour de rôle. Celui qui prend le dernier jeton a perdu. Jouer c'est prendre tous les jetons au-dessus et à droite de celui qu'on choisit. Le système sera capable de jouer une partie contre un joueur humain via cet algorithme paramétré par la profondeur de l'arbre de recherche et une fonction d'estimation.
1. Algorithme Alpha/Béta
Fonction : estimation3
Arguments :
noeud (* celui que l'on évalue *)
mp (* borne inférieure de l'intervalle d'utilité et valeur courante de noeud *)
b (* borne supérieure de l'intervalle d'utilité de noeud *)
Variables globales :
n (* le nombre de fils du noeud à traiter *)
i (* un compteur de boucle *)
vloc (* pour sauvegarder des résultats *)
Valeur retournée :
La valeur négamax du noeud argument
Algorithme :
début
si noeud est terminal
alors estimation3 <- estimation initiale de cette feuille
sinon
début
développer noeud; (* soit n le nombre de ses fils *)
i <- 1
tant_que i <= n et mp < b faire
début
vloc <- -estimation3(fi(noeud), -b, -mp);
si vloc > mp
alors mp <- vloc;
i <- i + 1
fin
estimation3 <- mp
fin
fin
Le calcul de la valeur négamax d'un noeud n s'obtient en appelant estimation3(n, -inf, +inf).
2. Les règles du jeu de chomp
a) Le jeu se joue sur un tapis comportant un repère orthonormé. Sur ce tapis sont
disposés tous les jetons de coordonnées (u, v) avec 1 <= u <= m et 1 <= v <= n
où m et n sont supérieurs ou égaux à 1 et le produit m * n est
strictement supérieur à 1.
Un jeu est donc caractérisé par le couple (m, n). En conséquence, on parlera
d'un jeu de type m * n.
b) Les adversaires seront dénotés respectivement par A et B. Ils jouent à tour
de rôle, A joue le premier.
c) Jouer c'est choisir un jeton de coordonnées (x, y) sur le tapis et prélever tous
les jetons de coordonnées (x', y') situés sur le tapis tels que x' >= x et y' >= y.
d) C'est le joueur qui par son coup prélève le jeton de coordonnées (1, 1) qui
perd.
3. Définition d'une heuristique
On peut démontrer qu'il existe une stratégie gagnante pour le premier qui joue dans
le cas de tout jeu de type m * n (avec m * n > 1).
Cette stratégie gagnante est aisée à décrire dans les cas suivants :
jeu de type 1*n (ou m*1), de type 2*n (ou m*2), de type m*m.
Sujet. (pdf) [ 349 Ko ]
Le code source (tar.gz) [13 Ko]
Le code source (zip) [18 Ko]
Contenu de l'archive : (cliquable)
ReadMe.txt,
AlphaBeta1.ml,
AlphaBeta2.ml,
AlphaBeta3.ml,
AlphaBeta4.ml,
AlphaBetaTest.ml,
ChompGraphic.ml,
ChompGraphicTest.ml,
Chomp.ml,
ChompTest.ml,
JeuDeCartes.ml
