Puissance 4 avec ia (arbre de jeux)

Soyez le premier à donner votre avis sur cette source.

Vue 22 201 fois - Téléchargée 1 729 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_Mercure
Messages postés
5
Date d'inscription
mardi 13 août 2002
Statut
Membre
Dernière intervention
13 juin 2014
-
L'algorythme est insuffisant pour permettre à l'intelligence artificielle de jouer avec un niveau correct et rapide. Pour l'améliorer, il faut prendre en compte la position tactique et stratégique de celui qui commence le jeu sur les cases paires ou impaires, etc ... Les règles pour gagner ont été publiées sur internet en anglais en 1988 "a knowledge-based approach of Connect-Four"
cs_grandvizir
Messages postés
1237
Date d'inscription
samedi 8 novembre 2003
Statut
Membre
Dernière intervention
3 septembre 2006
10 -
Ma technique repose simplement sur une profondeur de 2 : je ne regarde pas si une situation est gagnante ou pas (dans ce cas, un logiciel d'un Othello jouerait la position qui lui offre le maximum de pions), je prépare les alignements des 4 pions. C'est plus une devinette poussée sur l'instant qu'il faut plutôt qu'un arbre profond qui ne fait que diverger du coup optimal.

Ca m'intéresserai aussi que tu implémentes un compteur de vitesse grâce à GetTickCount (résultat en millisecondes) afin de voir à quelle vitesse va ton prog. J'avais été étonné de mon MD5, et j'aimerais bien voir ce que ça donne sur ton prog : on devrait facilement arriver à plus de 750 000 coups/sec, je pense.
CptPingu
Messages postés
3802
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
9 janvier 2020
93 -
1), 2) et 3) Ok,finalement j'ai compris c'est corrigé.
4) Si tu as une idée pour amélioré l'IA, je suis preneur.

Désoler du double post.
CptPingu
Messages postés
3802
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
9 janvier 2020
93 -
1) et 2) je n'ai pas compris.
3) Ok, tu as raison, ca sera facilement corrigé.
4) J'ai beau essayé de parcourir l'arbre le plus profondemment possible, un humain sera toujours plus fort.
5) Sur ma version (Delphi 7), cela scintillait, libre à l'utilisateur de laisser ou non DoubleBuffered:=True.
cs_grandvizir
Messages postés
1237
Date d'inscription
samedi 8 novembre 2003
Statut
Membre
Dernière intervention
3 septembre 2006
10 -
J'ai testé ton prog... Très surprenant et bien fait ! J'ai des remarques:
1) VARIANTS => destruction
2) Renomme ta variable JPEG qui fait confusion dans le USES
3) Fait un bloc INITIALIZATION et FINALIZATION dans MAIN.PAS dans lequel tu insèreras respectivement tes NEW(Pointeur) et DISPOSE(Pointeur)
4) Concernant l'IA: je savais que ma technique de jeu était bien rodée, mais je n'espérais quand même pas rester imbattable consécutivement pendant mes 10 premières parties. Faudra du coup peut-être envisager une version en réseau (entre humains quoi!) histoire d'affronter le Kasparov du puissance 4.
5) Par défaut, ça ne scintille pas :)

Au final: bravo et félicitations ! 10/10

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.