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