begin process at 2012 02 11 11:24:09
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Jeux

 > CONNECT 4 / PUISSANCE 4 / TOP 4 AVEC ALGORITHME ALPHA-BETA

CONNECT 4 / PUISSANCE 4 / TOP 4 AVEC ALGORITHME ALPHA-BETA


 Information sur la source

Note :
10 / 10 - par 1 personne
10,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Jeux Source .NET ( DotNet ) Classé sous :puissance4, connect4, alphabeta, jeu, top4 Niveau :Initié Date de création :02/02/2007 Date de mise à jour :23/11/2008 22:41:40 Vu / téléchargé :15 094 / 891
Auteur : Bidou

Ecrire un message privé
Site perso
Ce membre participe au partage de revenus publicitaires
Commentaire sur cette source (4)
Ajouter un commentaire et/ou une note

 Description

Cliquez pour voir la capture en taille normale
Connect 4 / Puissance 4 en C#

C'est le jeu très connu qui se nomme Puissance4, Top4 ou encore Connect4.
L'interface graphique n'est pas très soignée comme vous allez pouvoir vous en rendre compte, mais je ne suis pas designer :D

Il y a un menu d'options très basique pour paramétrer quelque peu le jeu.

L'intérêt de la source se trouve au niveau de l'implémentation de l'algorithme Alpha-Beta. Dans le Tic-Tac-Toe (ou Morpion) que j'avais posté ici (http://www.csharpfr.com/codes/JEU-MORPION-TIC-TAC -TOE-AVEC-ALGORITHME-MINIMAX_35814.aspx) j'avais utilisé un algorithme de type Minimax car le jeu ne contient que 9 cases, ce qui nous permet de vérifier toutes les possibilités (toutes les feuilles de l'arbres).
Pour un Puissance 4, le nombre de possibilité est immense et il faut donc utiliser un algorithme moins gourmand, commme Alpha-Beta, qui n'évalue pas toutes les branches de l'arbre mais fait des simplifications.
De plus, il faut spécifier une profondeur maximale de recherche dans l'arbre pour éviter d'une part des temps de calculs immenses, et d'autres part de faire sauter le stack (récursivité oblige).

L'algorithme peut (doit!) être encore amélioré, car pour l'instant j'ai des temps de réponses relativement longs (avec une recherche de profondeur 8 dans l'arbre) et il est possible de gagner contre l'IA en mode difficile. De plus, l'algo ne semble pas plus performant (ou alors très légèrement) avec des profondeurs de recherches plus grandes. Du coup, on a un temps de calcul beaucoup plus grand pour une IA pas plus intelligente...

Source

  • /// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  • /// <summary>
  • /// Return the best column.
  • /// </summary>
  • /// <param name="game"> The current game. </param>
  • /// <param name="maxDepth"> The maximum depth (in tree). </param>
  • /// <returns> The best column. </returns>
  • /// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  • public int AlphaBeta(Game game, int maxDepth)
  • {
  • List<Game> gResult = new List<Game>(); // The best points
  • int max = Int32.MinValue;
  • foreach (Game curGame in game.GetSuccessors(PlayerType.Computer))
  • {
  • int sonValue = AlphaBetaInternal(curGame, Int32.MinValue, Int32.MaxValue, maxDepth);
  • if (sonValue > max) // We have a new best point
  • {
  • gResult.Clear();
  • max = sonValue;
  • }
  • if (sonValue == max) gResult.Add(curGame);
  • }
  • return gResult[Tools.ChooseColumn(gResult.Count)].BestColumn; // Choose one between the bests
  • } 
/// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/// <summary>
/// Return the best column.
/// </summary>
/// <param name="game"> The current game. </param>
/// <param name="maxDepth"> The maximum depth (in tree). </param>
/// <returns> The best column. </returns>
/// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
public int AlphaBeta(Game game, int maxDepth)
{
      List<Game> gResult = new List<Game>(); // The best points
      int max = Int32.MinValue;
      foreach (Game curGame in game.GetSuccessors(PlayerType.Computer))
      {
            int sonValue = AlphaBetaInternal(curGame, Int32.MinValue, Int32.MaxValue, maxDepth);
            if (sonValue > max) // We have a new best point
            {
                  gResult.Clear();
                  max = sonValue;
            }
            if (sonValue == max) gResult.Add(curGame);
      }
      return gResult[Tools.ChooseColumn(gResult.Count)].BestColumn; // Choose one between the bests
}

 Conclusion

Tous commentaires et/ou notes sont bien entendu les biens venus!

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Historique

02 février 2007 22:47:16 :
Mise en page du code, GUI, petites corrections diverses
04 février 2007 12:00:58 :
Légère amélioration de l'IA et corrections de quelques petits bugs...
07 novembre 2008 09:38:38 :
Ortho
23 novembre 2008 22:41:41 :
^^

 Sources du même auteur

Source avec Zip Source .NET (Dotnet) CHESS GAME CORE - LIBRAIRIE JEU D'ÉCHEC EN C#
Source avec Zip Source avec une capture Source .NET (Dotnet) CUBE-IT: PETIT JEU EN WPF
Source avec Zip Source avec une capture Source .NET (Dotnet) YOUTUBE VIEWER
Source avec Zip Source avec une capture Source .NET (Dotnet) COLOR WHEEL
Source avec Zip Source avec une capture Source .NET (Dotnet) PETIT EXEMPLE UTILISANT XAML ET WPF
Toutes les sources de Bidou

 Sources de la même categorie

Source avec Zip Source avec une capture GÉNÉRATEUR DE PARTIES DE SUDOKU par MisterEpic
Source avec Zip GENERATEUR DE GRILLES DE SUDOKU RESOLUES par robx2391
Source avec Zip Source avec une capture Source .NET (Dotnet) JEU DE LA VIE par epineurien
Source avec Zip Source avec une capture MYCARDZINO par thebigboss
Source avec Zip Source .NET (Dotnet) [XNA] CULTURE ASTEROIDS par Chiheb2010
Toutes les sources de la catégorie Jeux

 Sources en rapport avec celle ci

Source avec Zip Source avec une capture GÉNÉRATEUR DE PARTIES DE SUDOKU par MisterEpic
Source avec Zip Source avec une capture Source .NET (Dotnet) [SILVERLIGHT] UN JEU D'ÉCHECS UTILISANT L'ALGORITHME ALPHA/B... par loudadyassine
Source avec Zip Source avec une capture Source .NET (Dotnet) JEU D'ÉCHECS EN C# par orioljimenez
Source avec Zip Source .NET (Dotnet) SERVERTIMER: AUTOMATISER LES TÂCHES DE REDÉMARRAGE D'UN SERV... par codergamer
Source avec Zip Source .NET (Dotnet) CHESS GAME CORE - LIBRAIRIE JEU D'ÉCHEC EN C# par Bidou

Commentaires et avis

Commentaire de romagny13 le 02/02/2007 18:51:58

Génial !!
non seulement cela donne envie de jouer à puissance 4
mais vu le code qu'il y a derriere en plus ...
je vais finir par me mettre moi aussi a developper des jeux avec toutes les excellentes sources de Bidou :p

Commentaire de Bidou le 02/02/2007 21:06:40 administrateur CS

Bah c'est léger ;-)
Ce qui est pas mal, c'est de découvrir les algorithmes qui tournent la derrière!

Commentaire de LuisL le 24/10/2009 12:36:21

Bonjour,

Bravo. Le code est très clair et bien construit.

Vous émettez une remarque sur les performances de l'IA, voici mon humble avis.

Votre code est basé sur la recherche d'un coup gagnant au tic-tac-toe où l'on peut se permettre de chercher toutes les combinaisons.
Donc, on ne note que les feuilles de l'arbre de recherche (Partie nulle : 0 ou coup gagnant : 1 ou -1).

Pour le puissance 4, quand la profondeur de recherche est atteinte sans coup gagnant, il faut noter autre chose que Game.Value=0. L'IA ne cherchera jamais à gagner car tout autre grille non gagnante vaut zero.

Il faut donc savoir évaluer la grille à tout moment et lui donner un score.
Un exemple trivial : une grille contenant 3 pions alignés avec un trou adjacent  est bien notée, alors que 3 pions alignés et encerclés par par les pions adverses vaut un score nul.
Il faut savoir aussi que les pions ne sont pas toujours alignés. Il faut vérifier d'autres combinaisons. (pion=1 et trou=0) 1110 , 1011, 1101, 0111.
Il faut aussi vérifier pour 2 pions (0011, 0101, 1001, 1010, 1100, 0110)
Il faut aussi noter 1 pion (0001, 0010, 0100, 1000)
Bref, il faut fortement noter 3 pions potentiellement gagnants, moyennement noter 2 pions potentiellement gagnants et faiblement noter 1 pion.
La note finale est la note donnée aux pions de l'ordinateur ôtée de la note des pions du joueur.
A partir de là, il faut changer le score pour une grille gagnante en 1000000 et -1000000 pour faire la différence avec l'évaluation courante d'une grille.

Conclusion : L'algorithme de recherche aide à  la performance alors que la fonction d'évaluation est primordiale pour que l'ordinateur soit un adversaire correct.

Cordialement.
Luis.

Commentaire de Bidou le 24/10/2009 13:06:34 administrateur CS

Bonjour,
Cette remarque est tout à fait correcte. Je ne me rappelle plus exactement du code que j'ai fait (il est pas récent), mais la fonction d'heuristique choisie n'est effectivement pas adaptée (ou suffisante) pour ce jeu.

En jetant un coup d'oeil rapide dans la source, je dirais qu'il faut probablement, dans la property IsLeaf de la classe Game, mettre une valeur plus adaptée pour la variable _gameValue afin de donner +/- d'importance à certaines situations/positions.

Avec .NET 4 il y a aussi certainement pas mal d'améliorations qui pourraient être faites en utilisant Parallel Framework...

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

lancement d'une appli [ par rintchu ] salut a tous,voila, je voudrais mettre dans mon programme un jeu secret comme ceux que l'on trouve dans Word ou Excel. Comment dois je faire pour reli Changer l'image d'un label ... [ par Baelorn ] Bonjour,je suis actuellement en train de réaliser un jeu en C# mode graphique et je rencontre un problème au niveau du changement de l'image d'un labe jeu vache taureau language c [ par cafou ] est ce que quelqu'un pourrait me donner la solution du jeu vache taureau en language cmerci d'avanceCAFOU Jeu de cartes en reseau [ par PeterG ] J'ai créer un jeu de Black Jack (2 joueur et +) avec visual studio dans mon cours de programmation 1, et j'aimerai pouvoir y jouer contre un ami chacu Jeu en réseau local [ par CMatt ] Bonjour à tous!J'ai développé un petit jeu en C# qui possède une "base de données" plutôt complexe, par ex. : - une classe Systeme contient un tabl Remoting et "sécurité" [ par CMatt ] Bonjour tout le monde!J'ai commenc&#233; &#224; d&#233;velopper un jeu en temps r&#233;el&nbsp;et j'essaie d'impl&#233;menter un mode multijoueurs (pa Problème sous DIRECTX [ par Lord_ZanTe ] Bonjour,nous sommes &#233;tudiant et nous d&#233;veloppons un jeu 3D sous DirectX, en C# dans le cadre d'un projet tuteur&#233;.Nous arrivons &#224; a Comment gerer input pour jeu en opengl ? [ par gimli123 ] Salut tout le monde ! J'aurai voulu savoir, comment me conseillez-vous de g&#233;rer les inputs (clavier/souri), si je veux faire un petit jeu en c#/c conditions [ par Kbitnik ] salut, je fais un jeu en c# ou je g&#233;n&#233;re des nombre &#224; chaque foi que j'appuie sur un bonton.et ainsi, un label ajoute a chaque fois son Poker client-serveur [ par malara ] Salut tout le monde,&nbsp;&nbsp;&nbsp;J'ai un petit probl&#232;me, c'est pourquoi j'ai besoin de l'expertise des membres de ce forum ... J'ai d&#233;v


Nos sponsors


Sondage...

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 1,794 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)