CONNECT 4 / PUISSANCE 4 / TOP 4 AVEC ALGORITHME ALPHA-BETA
romagny13
Messages postés
687
Date d'inscription
lundi 10 janvier 2005
Statut
Membre
Dernière intervention
27 août 2014
-
2 févr. 2007 à 18:51
cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 - 24 oct. 2009 à 13:06
cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 - 24 oct. 2009 à 13:06
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/41345-connect-4-puissance-4-top-4-avec-algorithme-alpha-beta
https://codes-sources.commentcamarche.net/source/41345-connect-4-puissance-4-top-4-avec-algorithme-alpha-beta
24 oct. 2009 à 13:06
Cette remarque est tout à fait correcte. Je ne me rappelle plus exactement du code que j'ai fait (il est pas récent), mais la fonction d'heuristique choisie n'est effectivement pas adaptée (ou suffisante) pour ce jeu.
En jetant un coup d'oeil rapide dans la source, je dirais qu'il faut probablement, dans la property IsLeaf de la classe Game, mettre une valeur plus adaptée pour la variable _gameValue afin de donner +/- d'importance à certaines situations/positions.
Avec .NET 4 il y a aussi certainement pas mal d'améliorations qui pourraient être faites en utilisant Parallel Framework...
24 oct. 2009 à 12:36
Bravo. Le code est très clair et bien construit.
Vous émettez une remarque sur les performances de l'IA, voici mon humble avis.
Votre code est basé sur la recherche d'un coup gagnant au tic-tac-toe où l'on peut se permettre de chercher toutes les combinaisons.
Donc, on ne note que les feuilles de l'arbre de recherche (Partie nulle : 0 ou coup gagnant : 1 ou -1).
Pour le puissance 4, quand la profondeur de recherche est atteinte sans coup gagnant, il faut noter autre chose que Game.Value=0. L'IA ne cherchera jamais à gagner car tout autre grille non gagnante vaut zero.
Il faut donc savoir évaluer la grille à tout moment et lui donner un score.
Un exemple trivial : une grille contenant 3 pions alignés avec un trou adjacent est bien notée, alors que 3 pions alignés et encerclés par par les pions adverses vaut un score nul.
Il faut savoir aussi que les pions ne sont pas toujours alignés. Il faut vérifier d'autres combinaisons. (pion=1 et trou=0) 1110 , 1011, 1101, 0111.
Il faut aussi vérifier pour 2 pions (0011, 0101, 1001, 1010, 1100, 0110)
Il faut aussi noter 1 pion (0001, 0010, 0100, 1000)
Bref, il faut fortement noter 3 pions potentiellement gagnants, moyennement noter 2 pions potentiellement gagnants et faiblement noter 1 pion.
La note finale est la note donnée aux pions de l'ordinateur ôtée de la note des pions du joueur.
A partir de là, il faut changer le score pour une grille gagnante en 1000000 et -1000000 pour faire la différence avec l'évaluation courante d'une grille.
Conclusion : L'algorithme de recherche aide à la performance alors que la fonction d'évaluation est primordiale pour que l'ordinateur soit un adversaire correct.
Cordialement.
Luis.
2 févr. 2007 à 21:06
Ce qui est pas mal, c'est de découvrir les algorithmes qui tournent la derrière!
2 févr. 2007 à 18:51
non seulement cela donne envie de jouer à puissance 4
mais vu le code qu'il y a derriere en plus ...
je vais finir par me mettre moi aussi a developper des jeux avec toutes les excellentes sources de Bidou :p