Negamax ou Minmax pour jeu d'échecs

Invité · 26/03/2013, 16h33

Bonjour,
J'ai essayer d'implémenter MinMax et NegaMax mais aucun des deux ne fonctionne.
Je viens voir si vous auriez la possibilité de revoir mes codes.
Si vous avez besoin de précision, je reste derrière mon pc.
C'est écrit avec Ada, j'ai suivi le pseudocode de Wikipedia et d'autres.

Un MinMax avec élagage alpha béta non récursif de ma conception.
jovi est le joueur adverse, jova le joueur courant, MINIMAX appelle jovi qui lui appelle jova et lui même jovi jusqu'a la profondeur voulue.

Code ada :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
   function jovi (Game : in Game_Type; 
                  Depth : in Natural;
                  Advers : in Game_Type;
                  Alpha : in Float;
                  Beta  : in float) return Float is      
      V_Min : Float := Beta;
      Hcost : Float := game.Heuristic(Game.Usr, Game.pred);
   begin
 
 
 
      if Game.Depth > Depth then
 
         declare
            V_Fils : Float := Float'Last;
            Successors : Successors_Type := advers.Successors(game.Usr);
            New_Game : Game_Type := Game;
         begin
            New_Game.Pred := Game.Usr;
            if Successors.Successor /= 0 then
               for Succ in 1..Successors.Successor loop                   
                  New_Game.Usr := Successors.Plan(Succ);
                  V_Fils := Float'Min (V_Fils, jova(New_Game, Depth, Advers, Alpha, V_min));
                  if Alpha >= V_Fils Then
                     return V_Fils;
                  else
                     V_Min := Float'Min (V_Min, V_Fils);
                  end if;              
               end loop;
            end if;
         end;
      else       
         V_Min := Hcost;
      end if;
 
      return V_Min;
   end;
 
 
   function jova (Game : in Game_Type;
                       Depth : in Natural;
                       Advers : in Game_Type;
                        Alpha : in Float;
                        Beta  : in float) return Float is
      V_Max : Float := Alpha;
      Hcost : Float := advers.Heuristic(Game.Usr, Game.pred);
   begin        
 
      if game.Depth > Depth then
 
         declare
            V_Fils : float := Float'First;
            Successors : Successors_Type := game.Successors(Game.Usr);
            New_Game : Game_Type := game;           
         begin             
 
            New_Game.Pred := Game.Usr;
            if Successors.Successor /= 0 then
 
               for Succ in 1..Successors.Successor loop     
 
                  New_Game.Usr := Successors.Plan(Succ);
 
                  V_Fils := Float'Max(V_Fils, jovi(New_Game, Depth+1, Advers, V_Max, beta));
 
                  if V_Fils >= Beta then
                     return V_Fils;
                  else
                     V_Max := Float'Max(V_Max,V_Fils);   
                  end if;              
               end loop;
            end if;
         end;
      else
         V_Max := Hcost;
      end if;
 
      return V_Max;
   end;
 
 
   function MINIMAX (player : in Game_Type; Advers : in Game_Type) return Usr_Type is
 
      Maxime : Float := Float'First;
 
      Successors : Successors_Type := Player.Successors(Player.Usr);
      Coup : Usr_Type;
      New_Game : Game_Type := Player;
   begin      
      New_Game.pred := Advers.Usr;
      if Successors.Successor /= 0 then
 
         for Succ in 1..Successors.Successor loop           
 
            New_Game.Usr := Successors.Plan(Succ);
 
            declare
 
               Val_Fils : Float := Jovi(New_Game, 0, Advers, Float'First, Float'last);
            begin
 
               if Val_Fils > Maxime then
                  Put_Line("MINIMAX : " & Float'Image(Val_fils));
                  Maxime := Val_Fils;
                  Coup := Successors.Plan(Succ);
               end if;
            end;
         end loop;
      end if;
      return coup;
   end;

NegaMax, tout bètement l'algo de Wikipedia version english. jovijova appelle NégaMax, peut-être que mon erreur est là.

Code ada :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
function NegaMax (player : in Game_Type; Advers: in Game_Type; Depth : in Natural; A, B : in float) return float is
      Alpha : Float := A;
      Beta  : Float := B;
   begin
      if player.Depth <= Depth then
         return player.Heuristic(Player.Usr, player.pred);
      else
         declare
            V_Fils  : Float := 0.0;
            Best    : Float := Float'First;
            New_Game : Game_Type := Advers;
            Successors : Successors_Type := player.Successors(Player.Usr);
         begin
            New_Game.Pred := Player.Usr;
            for Succ in 1..Successors.Successor loop                      
               New_Game.Usr := Successors.Plan(Succ);             
               V_Fils := -NegaMax(New_Game, Player, Depth+1, -Beta, -alpha);
               if V_Fils >= beta then
                  return V_Fils;
               elsif V_fils >= Alpha then
                  Alpha := V_Fils;
               end if;
            end loop;
            return alpha;           
         end;
      end if;
   end negaMax;
 
 function jovijova(player : in Game_Type; Advers : in Game_Type) return Usr_Type is
      Maxime : Float := Float'First;
 
      Successors : Successors_Type := Player.Successors(Player.Usr);
      Coup : Usr_Type;
      New_Game : Game_Type := Player;
   begin      
      New_Game.pred := Advers.Usr;
      if Successors.Successor /= 0 then
 
         for Succ in 1..Successors.Successor loop           
 
 
            New_Game.usr := Successors.Plan(Succ);
            declare            
               Val_Fils : Float := negamax(New_Game, player, 0, Float'First, Float'last);
            begin
 
               if Val_Fils > Maxime then
                  Put_Line("NegaMax : " & Float'Image(Val_fils));
                  Maxime := Val_Fils;
                  Coup := Successors.Plan(Succ);
               end if;
            end;
         end loop;
      end if;
      return coup;
   end Jovijova;

Pour les deux fonction un type Game_Type fournit les opérations "successeurs" et "heuristic".

Mon problème est un non respect des regles du jeu d'échecs lors d'un echec.

Merci pour votre aide, s'il vous plaît.

Invité · 27/03/2013, 14h45

Bonjour, j'ai fait un paquet pour Gnu/Linux de la mise en oeuvre de ces deux algorithme, alpha béta non récusif pour les blancs et NegaMax pour les noir.
Dans ce paquet, j'ai modifier l'appel à MinMax - alpha-béta, j'appelle désormais jova
Comme ça pour pouvez constater que j'ai chercher à résoudre un problème de coup en échec en détectant l'échec dans l'heuristique.

Depuis les résultat ne sont pas du même ordre. Enfin, je teste encore. Mais l'affaire n'est pas gagné.

Donc, vous pouvez désormais rechercher dans ma signature la version 2.1.0 de MegaChess, tar.gz pour Gnu/linux, la diff, c'est juste un clear à la place d'un cls, et le cadre de l'échiquier. je fais un paquet Windows dans un moment.

Merci pour votre aide.

PArdon, dans le paquet 2.1.0 il faut corriger dans games.adb jovajovi pour qu'il appelle négamax avec depth * 2 et non pas depth * 2 - 1.

Désolé ça va obliger à recompiler celui-ci.

Invité · 30/03/2013, 04h03

Bonjour, bonsoir.

Finalement j'ai implémenté Minimax avec élagage Alpha-Beta en récurcif exactement celui de wikipedia.

Bon, mais ça joue pas très bien à profondeur de 1 c'est à dire que je fait profondeur - 1 dans max.

Par hasard, vous auriez des soluce algorithmique pour améliorer la combativité de mon jeu ?

Parce que là ça tourne en boucle au 40 ou 50 ieme coup alors qu'il reyste plein de pieces sur l'échiquier.

Merci pour vos réponses.

Invité · 02/04/2013, 13h59

Vous êtes ou ?

**Alp** · 08/04/2013, 13h22

Je te suggère de suivre les conseils donnés ici.

Invité · 08/04/2013, 19h32

Envoyé par Alp

Je te suggère de suivre les conseils donnés ici.

Merci Alp, mais je ne pige rien à l'english et Google refuse de traduire.

**Alp** · 09/04/2013, 10h34

En gros: utilise la version negamax, avec le prunage alpha-beta (ça double la profondeur de recherche pour le même temps d'exécution, par rapport à minimax). Et utilise "l'approfondissement itératif" (?? je ne sais pas si ça se dit en FR): http://www.emn.fr/z-info/pdavid/Ense...iterative.html en combinaison avec une table de hachage. Le premier permettra de pouvoir prendre la décision de faire un mouvement au moment que tu veux, puisque ça consiste à améliorer la recherche en allant plus loin à chaque itération dans l'arbre, et la table de hachage te permettra (si t'as une fonction de hachage symmétrique, je suppose?) d'éviter de faire du boulot en trop si tu tombes sur une situation que t'as déjà croisée.

Invité · 09/04/2013, 11h46

A oui, merci si non par rapport à mon code ?

Invité · 09/04/2013, 14h56

Enfin, je veux dire même le code corrigé marche pas.

J'ai oublié de vous dire, j'ai écrit un code qui à l'aire de fonctionner pendant un temps mais qui s'avère inefficace quand viens l'échec et mat, difficile à desceller pour l'homme excuser moi, en jouant en position d'échec.
Là est mon gros problème de puis 1 mois, il joue échec. Aujourd'hui mon algo minmax est corrigé, reste cette histoire d'heuristique. Mais je comprend mas pourquoi il joue échecs ?
Merci pour vos réponses.

**Zosma** · 19/06/2013, 04h41

ça veut dire quoi "il joue échec" ?

Invité · 19/10/2013, 23h40

Ca signifie qu'il joue pour ce placer en position d'échec.

Negamax ou Minmax pour jeu d'échecs

Intelligence artificielle

Discussions similaires

Partager

Partager