Puissance 4 avec ia (arbre de jeux)

Soyez le premier à donner votre avis sur cette source.

Vue 22 064 fois - Téléchargée 1 724 fois

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.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_bloom1
Messages postés
328
Date d'inscription
jeudi 26 août 2004
Statut
Membre
Dernière intervention
8 mars 2007
-
Aaah, je te gage que tu utilises Delphi 2005 :@ je le haie, on peut même pas faire de réseau dedans :S
Au juste, a quoi sert XPMan dans les uses ???
CptPingu
Messages postés
3834
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
10 juin 2019
85 -
A non pas du tout, je suis sous delphi 7.
XPMan sert à avoir le style XP pour les applications.
DelphiCool
Messages postés
462
Date d'inscription
mardi 24 juillet 2001
Statut
Modérateur
Dernière intervention
10 mars 2009
-
Pour le bug c'est cette ligne qui le créer
DoubleBuffered := True;

Bizarre ???
CptPingu
Messages postés
3834
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
10 juin 2019
85 -
Je te remercie d'avoir trouvé l'erreur. Par contre je doit laisser le "DoubleBuffered := True;" sinon la grille du jeu scintille de temps en temps.
Est-ce normale que cette commande et les TCheckBox ne puissent cohabiter ?

Si tu as une explication, je t'en remercie.
cs_bloom1
Messages postés
328
Date d'inscription
jeudi 26 août 2004
Statut
Membre
Dernière intervention
8 mars 2007
-
Ah ben j'ai compris, moi je suis sous Delphi 6 alors XPMan existe pas... Est-ce que Delphi 7 ressemble beaucoup a Delphi 6 ???
Merci d'avance !


Bloom1 :)

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.