Accueil > > > PUISSANCE 4 AVEC IA (ARBRE DE JEUX)
PUISSANCE 4 AVEC IA (ARBRE DE JEUX)
Information sur la source
Description
Une IA est intégrée. Elle se defend pas mal. On a la possibilité d'exporter l'image de la partie en bitmap ou jpeg. L'éxécutable est autonome, les images étant contenu dans celui-ci. Je sais qu'il existait déjà des "Puissance 4" sur ce site. Mais, je n'en ai pas vu beaucoup qui utilisait une IA. De plus, pour ceux que ca interesse, j'ai implémenté un algo d'arbre de jeux.
Conclusion
La théorie de l'algorithme Min-Max.
- On crée un arbre dont chaques branches représentent un coup joué. - Ensuite si à la suite de ce coup, il ne se passe rien, je donne une note de 0 au noeud. Si celui-ci me fait gagner la partie je donne une note de 10000. Enfin si celui-ci me fait perdre je donne une note de -10000. - Je parcours alors l'arbre (en fait je le remonte puisque l'algo est récursif) en gardant la branche la mieux notée. - Théoriquement, l'IA jouerait de facon optimal, et serait IMBATTABLE.
Malheureusement, le nombre de combinaison possible augmente exponentiellement. Construire un arbre de jeu entier est pour l'instant impossible. C'est pourquoi on est obligé de stopper l'algo à une certaine profondeur. De plus, on peux simplifier l'algo à l'aide de la méthode Alpha-Beta. Celle-ci consiste à ne pas parcourir toutes les branches de l'arbre. En effet, si un score est trop élevé ou trop faible, certaines branches ne valent pas le coup d'être explorées. J'ai ajouté quelques optimisations propre à mon application. Par exemple, je donne aussi un score lorsque je trouve des formations incompletes: - 4 pions : 10000 points - 3 pions : 100 points - 2 pions : 1 points Ainsi, j'ai plus de précision lors du choix de la branche de l'arbre. Enfin, je ne parcours une branche que si c'est nécessaire. Je m'explique, si je n'ai pas le droit de poser dans une colonne (en vérifiant le "tableau d'interdit" que j'expliquerai après), alors le noeud et tout ses fils ne seront pas parcourus.
L'implementation de mon IA.
L'IA fonctionne comme ceci: - Tout d'abord on verifi si on peux jouer un coup qui nous fait immédiatement gagner. - Ensuite on verifi si on peux jouer un coup qui nous empêcherait de perdre sur le champ. - Si on est dans aucun des cas ci-dessus, alors on inspecte le tableau des colonnes interdites. Ce tableau est crée en même temps que les deux verifications précédentes. C'est simple, si lors de ma vérification je détecte que la position d'un pion entrainerait obligatoirement la défaite au coup suivant (deux coup apres en fait), je l'indique dans ce tableau. L'IA n'a alors plus le droit de poser un pion dans cette colonne, jusqu'à ce qu'un changement soit fait. De même, j'interdit de placer un pion dans une colonne, si le placement détruit une formation (par exemple trois de mes pions alignés). Ce tableau contient alors un état par colonne. Les 3 états sont: * AUCUN : on peut poser dans cette colonne. * PLACER : poser dans cette colonne détruit une de nos formation. * EMPECHER : poser dans cette colonne ferait gagner l'adversaire.
Pour en revenir à la méthode, j'inspecte le tableau d'interdit de la facon suivante: - Si il reste des colonnes ou je peux placer, je lance l'aglorithme Min-Max (arbre des jeux expliqué ci-dessus). - Si il ne reste plus de place, alors je sacrifie une de mes formations (c'est ca ou donner la victoire à l'adversaire), et je place un de mes pions dans une colonne (marqué PLACER) - Si il ne reste plus de colonne à placer, et aucune de ses formations à sacrifier, alors la partie est perdu. On place (à contre coeur) le pions qui fera gagner l'adversaire.
Si vous voyez des améliorations à apporter, n'hésitez pas à me contacter.
Historique
- 10 juillet 2005 18:27:20 :
- Les fautes d'orthographes...
- 10 juillet 2005 18:41:37 :
- J'avais laisser le .exe ...
Je suis bête des fois.
- 11 juillet 2005 00:41:09 :
- Mes anciennes mises à jour n'ont pas été pris en compte...
- 14 juillet 2005 23:49:46 :
- Amélioration de l'IA.
Ajout d'un algorithme d'arbre des jeux.
(Algorithme Min-Max simplifié par la méthode Alpha-Beta)
- 16 juillet 2005 13:40:55 :
- Petites améliorations.
- 25 juillet 2005 00:12:47 :
- Petites optimisations + Conseil de GrandVizir
Sources du même auteur
Sources de la même categorie
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
help!!!!!svp les best en delphi :) [ par eedy31 ]
j'ai un gro pblém : je debute en delphi et il me fo du temps pour apprendre!!!ET le pblém c'est que mon père monopolise le PC avec son jeu(atlantis3..
Jeu avec le source [ par Synthox ]
Si ca vous dis de faire un jeu de carte, je vous met mes sources en telechargement sur mon site, il contiens aussi un fichier RES avec les cartes de t
Comment faire les menus d'un jeu en Delphi ?! Vite ça presse ! [ par Gropoli ]
Je suis entrain de faire un jeu de type wargame en delphi et je me demande comment je dois faire les menus du jeu : menu principal (nouveau jeu, optio
Comment faire les menus d'un jeu en Delphi ?! Vite ça presse ! [ par Gropoli ]
Je suis entrain de faire un jeu de type wargame en delphi et je me demande comment je dois faire les menus du jeu : menu principal (nouveau jeu, optio
Recherche de code pour jeu d'enregistrement [ par clemot ]
Salut je recherche un exemple ou des exemples de code pourun jeu d'enregistrement à partir de TDBCtrlGrid et de stringgrid pouyr enregistrer des donn
Direct Connect en Delphi [ par aroslide ]
Recherche personnes ayant travaillé sur le protocol Direct Connect afin de réaliser en collaboration un serveur Direct Connect plus leger et plus sta
Jeu de strategie avec directdraw [ par sebrs1 ]
Tout d'abord, je vais vous expliquer ce que je veux fairec'est tout simple (enfin, simple a comprendre mais pas a faire)je voudrais faire un truc genr
Cherche dessinateur [ par sebrs1 ]
Bonjourje cherche un dessinateur qui pourrait m'aider dans les graphisme et animations de mon jeuc'est un jeu en directdraw en isometrique genre jeux
programmation jeu de dames sur delphi4.0 en pascal [ par Laurie ]
Comment programmer un jeu de dames avec un stringgrid pour que les pionts ne puissent pas reculer? Comment faire apparaître une dame et controler ses
DelphiX: ralentissements!! [ par costello ]
AAAARGGHH (cri de détresse) ! je développe 1 jeu depuis quelques jours, sous DelphiX / Delphi 7 perso (tout tourne très bien jusqu'à maintenant, ya ja
|
Derniers Blogs
[MIX10] KEYNOTE DEUXIèME JOURNéE - INTERNET EXPLORER 9, HTML5, VISUAL STUDIO 2010, ODATA[MIX10] KEYNOTE DEUXIèME JOURNéE - INTERNET EXPLORER 9, HTML5, VISUAL STUDIO 2010, ODATA par cyril
Le deuxième keynote du mix fut très riche en contenu. Internet Explorer 9 Juste un après le lancement de Internet Explorer 8, Microsoft a dévoilé les nouveautés de Internet Explorer 9. Désormais, IE supportera HTML5, SVG et CSS3. L'élément ...
Cliquez pour lire la suite de l'article par cyril CERTIFICATIONS BETA .NET 4CERTIFICATIONS BETA .NET 4 par KooKiz
Les inscriptions pour les certifications beta .NET 4 ont commencé. L'inscription est offerte pour les examens suivants : - 71-511, TS: Windows Applications Development with Microsoft .NET Framework 4 - 71-515, TS: Web Applications Development with...
Cliquez pour lire la suite de l'article par KooKiz [MIX 2010] - MICROSOFT TRANSLATOR TECHNOLOGY PREVIEW V2[MIX 2010] - MICROSOFT TRANSLATOR TECHNOLOGY PREVIEW V2 par redo
J'imagine que la plupart d'entre vous connaissent bien et utilisent le service de traduction de Google, mais connaissez-vous celui de Microsoft . Microsoft Translator ? Effectivement, Microsoft nous annoncé le lancement version 2 de la Technologie Preview...
Cliquez pour lire la suite de l'article par redo LANCEMENT EN PREVIEW DE CYCLONE LORS DES TECHDAYS 2010!LANCEMENT EN PREVIEW DE CYCLONE LORS DES TECHDAYS 2010! par MPOWARE
Toutes les vidéos de ce lancement sont en ligne!
Partie I - Intro
http://www.youtube.com/watch?v=LkQzTQ8T6CA
Partie II - Démo 1
http://www.youtube.com/watch?v=drAhYQ7lqvo
Partie III - Démo 2
http://www.youtube.com/watch?v=c8KM_1Gqybc...
Cliquez pour lire la suite de l'article par MPOWARE
Logiciels
Academy System (10.9.4.0)ACADEMY SYSTEM (10.9.4.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Xilisoft Convertisseur Vidéo Ultimate (5.1.39.0305)XILISOFT CONVERTISSEUR VIDéO ULTIMATE (5.1.39.0305)Xilisoft Convertisseur Vidéo Ultimate est un outil puissant de conversion vidéo, facile à utilise... Cliquez pour télécharger Xilisoft Convertisseur Vidéo Ultimate Xilisoft DVD Ripper Ultimate (5.0.64.0304)XILISOFT DVD RIPPER ULTIMATE (5.0.64.0304)Xilisoft DVD Ripper Ultimate est un logiciel excellent pour copier et convertir DVD vers presque ... Cliquez pour télécharger Xilisoft DVD Ripper Ultimate Rigs of Rods (63.3)RIGS OF RODS (63.3)c'est un jeu de multi-simulation camions,autobus voitures, avions, bateaux, hélicoptère avec défo... Cliquez pour télécharger Rigs of Rods
|