Giz | senomo a écrit :
c'est un jeu qui s'appelle chocobar, qui consiste en une tablette de chocolat (donc matrice) où chaque joueur mange un carré quand c'est son tour de jouer, quand tu mange un carré tu prends avec tous ceux qui sont à sa droite et en dessous. donc si tu as une latrice de 3x3 et que tu mange le 1,1, tu prends avec le 1,2 le 2,1 et le 2,2. le but est de ne pas manger le carré 0,0 sinon il peut t'arriver de graves problèmes de santé. pour cela il faut forczer l'adversaire à manger le carré 0,0.
l'heuristique sert à estimer plus qu'autre chose, tu n'es jamais certain de gagner avec. sinon une stratégie gagante calcule un chemin UNIQUE du sommet à une feuille ou l'adversaire s'empoisonne
le programme consiste donc à faire une construction de l'arbre en profondeur, c'est à dire de créer le sommet, et d'appeler la fonction create récursivement.
create(Sommet s) {
bla bla bla
créer le fils t;
create(t);
}
|
Bon, écoute, ton problème est hyper connu : c'est le principe du jeu des allumettes qui est :
Tu as un tas de X allumettes, chacun (toi et l'adversaire) a tour de role doit retirer entre une ou trois allumettes. Celui qui retire la dernière a perdu.
Un problème comme celui la met en avant direct l'application du "minimax". En gros dans ton prog tu fixes une bonne constante : il s'agira de la profondeur d'exploration maximale de ton arbre. Ainsi tu crees tout l'arbre de solution jusqu'à la profondeur X (X=constante). Ensuite tu evalues TOUTES les feuilles de la profondeur X. Dans ton exo, evaluer signifie juste dire "j'ai perdu" (I) ou bien "j'ai pas perdu" (II) ou bien "j'ai gagné" (III). A partir de la, tu fais remonter l'information dans l'arbre intelligemment. C'est a dire qu'a la profondeur 0, c'est le plateau a partir duquel tu es exposé (vient du coup joué de l'adversaire), ensuite les noeuds se trouvant en profondeur 1 sont les coups que tu peux jouer, ensuite en profondeur 2 sont les coups que ton adversaire peux jouer ... et ainsi de suite jusqu'a la profondeur X.
deux cas à distinguer :
- Les noeuds de profondeur X sont les coups joués par l'adversaire : donc trois etats possibles : ou bien des noeuds valent l'état (I) dans ce cas le noeud parent est satisfaisant pour toi (a garder). Si etat (II), on ne peut rien dire. Si etat (III), tu oublies le noeud parent (en gros il ne faudra pas prendre les chemins d'arbre qui passent par ce noeud !.
- Les noeuds de profondeur X sont les coups joués par toi, dans ce cas le raisonnement a faire est l'inverse du 1er cas.
Une fois que tu as fais remonter l'information, les noeuds de profondeur 1 (les coups que tu peux jouer) tu pourra voir les coups "banni" qui te font perdre ! donc ce seront des noeuds a ne pas prendre...et tu prendra alors les noeuds qui ne te font pas perdre (ou bien qui te feront gagné ou bien qui t'amenent a un etat "j'ai pas perdu".
Bon voila c'est pas plus complique. Il existe plein d'algo sur le "minimax". Sache que c l'algo utilisé a la base de tous jeu avec un adversaire (comme le jeu d'echec Deep Blue qui a battu kasparov) ... normal c'est un algo qui calcul les coups a l'avance en fait pour voir les meilleurs coups a jouer et les pires coups a ne pas jouer. Bon ensuite il y a toujours moyen de l'ameliorer avec notamment l'algo "elagage alpha beta" qui te coupe des branches dans ton arbre (comme par exemple si le fils d'un noeud est perdant, ca ne sert a rien d'aller parcourir les autres fils de ce noeud), tu gagneras en rapidité. Message édité par Giz le 23-12-2004 à 01:43:46
|