Actualités
Articles
Mark Overmars Glog: Un autre vieux jeu: Gobang
Un autre vieux jeu: Gobang


Super Breakout, décrit dans le post précedent(NDT: L'article "Mes jeux sur Atari" ), n'était pas l'unique jeu que j'ai crée pour l'Atari ST. J'ai également programmé un jeu de type "Snake"(également avec des fonctionnalités supplémentaires), et j'ai crée une version du jeu Gobang ou le but était d'aligner 5 pierres de sa couleur sur un tableau..
J'ai récemment retrouvé le vieux code source de ce jeu, et j'ai décidé de le recréer avec Game Maker. Vous pouvez trouver le resultat : ici.

La partie difficile et interessante lorsqu'on recrée un jeu comme Gobang, c'est la programmation de l'ordinateur adverse.
La méthode "standard" pour créer des ordinateurs adverses comme ceci, c'est l'utilisation d'un algorithme minimax ou encore mieux, d'utiliser de l'alpha-beta pruning. Expliquée trés simplement, la methode fonctionne comme ceci. Disons que nous voulons calculer le meilleur mouvement pour les pierres blanches. Nous considérons tous les mouvements possibles(tout en restant dans le raisonnable) pour les pierres blanches. Si l'un d'eux mène à la victoire(ou à une situation trés favorable), nous pouvons faire ce mouvement. Sinon, pour tous les mouvements possibles des pierres blanches nous calculons le meilleur mouvement des pierres noires et nous évaluons le résultat de ce mouvement. Maintenant, nous prenons le mouvement de pierres blanches pour lequel le meilleur mouvement des pierres noires mène à la pire situation pour les pierres noires(ou la meilleure pour les pierres blanches). Pour calculer le meilleur mouvement des pierres noires nous réutilisons le même algorithme, et uniquement celui-ci. Evidemment nous devons arrêter à un degré particulier du calcul, c'est-à-dire, nous ne vérifions qu'un nombre d'emplacements limités. Sinon le calcul deviendrait trop gourmand en ressources. Pour plus d'information, vous pouvez chercher sur Wikipédia avec des mots-clés tels que minimax et alpha-beta pruning.


Gobang, version refaite avec Game Maker

Le challenge dans la re-création du jeu Gobang, c'est que le nombre de mouvements possibles est trés large. Même si nous ne placons que de nouvelles pierres près de pierres existantes, trés vite dans le jeu il y a environ 100 mouvements différents possibles. Egalement, il est difficile de les écarter du calcul, car ils récidiveront vite en réappelant l'ordinateur répetitivement et donc, ceci nous donnera une IA assez lente. Bien sur, dans des jeux comme les èchecs, on peut trouver acceptable le fait que l'IA réflechisse pendant une ou deux minutes, mais dans un jeu comme Gobang, ceci n'est pas du tout apprécié par les joueurs.

La solution était en faite, le fait que le jeu ne faisait attention qu'à des modèles trés simples. Il y a 12 règles du genre:
1) Si il y a un mouvement ou l'ordinateur peut gagner, ce mouvement est joué.
2) Si il y a un mouvement ou le joueur peut gagner, c'est ce mouvement que l'IA va jouer.
3)Si un mouvement comme le n°2 existe, apres lui, si il y a une ou deux positions supplémentaires ou l'ordinateur peut gagner, cette position est jouée, etc.

Dans le mode facile, seulement quelques unes de ces règles sont appliquées. En mode normal, 10 d'entre elles sont appliquées, et en mode difficile, les 12 règles sont appliquées. Il est assez surprenant de voir comment un adversaire peut être fort en appliquant juste quelques règles simples.

En mode difficile, un peu de recherche répetitive a étée également ajoutée. Si il y a différents mouvements qui peuvent forcer l'adversaire à jouer une certaine pierre, sur ces mouvements nous utilisons un algorithme minimax, mais uniquement pour considérer les mouvements forcés. Comme il y en a trés peu, ceci est assez rapide(Même si sur l'ancienne Atari ceci pouvait toujours ramener à des performances lentes.)

Au faite, l'IA du jeu n'a pas étée ecrite en GML mais en Delphi, et le système d'extensions de Game Maker a été utilisé pour l'inclure. Si vous voulez observer le code ou bien améliorer le jeu, vous pouvez télecharger la source du jeu ici, avec la version éditable du jeu et le pack d'extension(NDT: Le gex en faite :p ).
Utilisez-le comme vous le voulez mais s'il vous plaît, remerciez moi quand vous l'utilisez avec un lien vers le jeu original.

Article écrit par Mark Overmars.
Traduit par Death_Egg pour Le CBNA.
23/12/2007 par Difègue
6 Commentaires

par Death Egg @ 23/12/2007 05:31 pm
pfouuuu...
Il était dur à traduire celui-là gniah

par Master47 @ 23/12/2007 05:57 pm
Si tu veux je peux toujours t'aider pour ce genre de traductions :D
Si ca te chante contacte moi ici : olivier-k@hotmail.com

par Topaze22 @ 24/12/2007 12:37 pm
Joli boulo! super
J'ai tout lu, et c'est sympa de savoir comment ils font leur IA. même si à mon avis, une IA d'échec m'est hors de porté gnii

par Kev2442 @ 25/12/2007 10:01 pm
moi aussi rouge
pour death egg bonne orthographe mais il y a quand même une ou deux fautes...continue! super

par manon @ 05/07/2011 08:10 pm
j'ai rien compris a se jeux vous pouvez mexpliquer en resumé?


merci

par manon @ 05/07/2011 08:14 pm
svp question snif heheh clin^

Nom:
Mail: (optionel)
Êtes vous Humain? (Entrez oui si c'est le cas)

smile's:

fleche_dfleche_gbehgniihappy1questionrirerire2rougesupertristeangeclincoeurcoleredodofierghagniahhaphehehhontenonnon3ouhouisnif

| M'oublier

Actualités Générales
2016, l'année de sortie du nouveau CBNA
GP2X Wiz - La console portable du programmeur
Mark Overmars Glog: Mon Nouvel Ordinateur Vista
La programmation
Mark Overmars Glog: Mes jeux sur Atari
Key To Key
CBNA Pix'Art : Concours de Pixel Art!
A.I.M.E - Aide Informatique contre la Mucoviscidose des Enfants
LCEN
A quand le nouveau forum ?
Ablationage > Webcomic
20 Mars! Journée de la Francophonie!
Un demi-siècle de disque dur! L'anniversaire!
Grâce à un trombone il gagne une maison
Les Mac s'ouvrent à Windows!

Actualités GameMaker
GameMaker9PC compatible PSP ???
GameMaker8, dernière chance de l'upgrader gratuitement
Yoyogames engage un nouveau "chef technique"
Firefox 3.6 pas encore compatible avec Yoyogames
GM pour Mac... le travail a repri
Le moteur de physique de vos rêves
Compétition n°5 lancée sur Yoyogames
Résumé des dernières news du Blog de Yoyogames
Une compilation de 100 jeux réalisés en 2009
Yoyogames instant play pas encore compatible GM8
GameMaker 8 est sorti
Résumé des dernières news du Blog de Yoyogames
Traduction française d'ajout sur GM8 :
GM8 version "release candidate"
Beaucoup d'info sur GM7mac, GM8 et l'avenir
Version béta test de GameMaker 8.0 disponible
GameMaker 8.0, une bonne partie des nouveautés annoncées
Compétition N°7: Titres Spéciaux
5 Jeux de la Compétition N°7
Mise à jour de l'éditeur d'image de GameMakerV8 disponible
Date de Sortie de GameMaker 8
GameMakerV8 l'éditeur d'image disponible en téléchargement ici
Game Maker 4 Mac: Bêta recue
Traduction Française de la documentation d'Ultimate 3D
GameMaker version Mac version béta
La Compétition N°7 est lancée!
Mark Overmars Glog: Astuce: Support du PNG dans GM
Mark Overmars Glog:Game Design: Aligner Des X
Astuce pour Game Maker: Support de l'écriture Cyrillique
Enigma : 3ème release publique
Firefox 3 compatible avec le nouveau plug in Instant Play de Yoyogames
Mark Overmars Glog:une expérience sur l'animation
Prebeta de GMPhysiqueV5
Mark Overmars Glog:Etre Original
Premère sortie d'ENIGMA
Compétition N°6 : Les Prix et les lettres!!
Mark Overmars Glog: GDCSE'08 (Game Development in Computer Science Education)
Game Maker sur MAC
Mark Overmars Glog: Les Codes de triche
Mark Overmars Glog: Le losange du genre d'un jeu
Mark Overmars Glog: Un autre vieux jeu: Gobang
Mark Overmars Glog: Les Ressources pour Game Maker
Mark Overmars Glog: L'effet des récompenses (bonus) & Parlons un peu plus des récompenses
Mark Overmars Glog: Le Score
Le Blog de Mark Overmars
Interview des organisateurs de la Game Maker Exposition
GME: Game Maker Exposition
Interview de Bast et de Daminetreg
Game Maker 7.0 Disponible!
Les Prix de la Compétition N°5 sont arrivés!
Le GMC réouvert!
Le GMC cracké, GameMaker est triste...