Connect 4 / puissance 4 / top 4 avec algorithme alpha-beta

Télécharger le projet
Commenter

Description

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 / Exemple : 


/// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/// <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!
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (cs_Bidou)