Discussion :

[Sylvain255]

bonjour
si ma fonction minimax est définie comme cela :

Code :

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
type
 
tcoup = record
  ligne:byte;
  colonne:byte;
  end;
 
tcoups = record
   coups :array [0..64] of tcoup;
   nb_coups:integer;
  end;
 
function ValeurMinMax(tableau: ttab;prof: integer; est_max: boolean): integer;
var
  x: integer;
  s,score:integer;
  cp:tcoups;
  a_joue:boolean;
begin
  s:=evalueCPU(tableau);
  if s=10000 then // ordinateur gagne
    result := +10000
  else if s=-10000 then // humain gagne
    result := -10000
  else if prof = 0 then
    result := s
  else
  begin
    if est_max then
    begin
      result := -10001;
      cp:=coupsPossibles(tableau,couleur_cpu);
      if cp.nb_coups=0 then
      begin
        result:=s;
        exit;
      end;
      for x := 0 to cp.nb_coups-1 do
      begin
          score := ValeurMinMax(jouer(tableau, couleur_cpu, a_joue,cp.coups[x]), prof - 1, FALSE);
          if score > result then
            result := score;
      end
    end
    else
    begin
      result := 10001;
      cp:=coupsPossibles(tableau,couleur_humain);
      if cp.nb_coups=0 then
      begin
        result:=s;
        exit;
      end;
      for x := 0 to cp.nb_coups-1 do
      begin
          score := ValeurMinMax(jouer(tableau, couleur_humain, a_joue,cp.coups[x]), prof - 1, TRUE);
          if score < result then
            result := score;
      end;
    end;
  end;
end;

comment se coderait l'élagage alpha bêta SVP ?

merci

cordialement

[Charly910]

Bonjour Sylvain,
Paul Toth t'a déjà donné des pistes. Regarde ici tu as du pseudo code que tu peux traduire en Pascal.
Essaye, et poste le résultat si tu as des difficultés.

A+
Charly

[Sylvain255]

c'est bon comme cela ?

Code :

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
type
 
tcoup = record
  ligne:byte;
  colonne:byte;
  end;
 
tcoups = record
   coups :array [0..64] of tcoup;
   nb_coups:integer;
  end;
 
const
couleur_cpu=1;
couleur_humain=2;
 
uses math;
 
function DecisionAlphaBeta (tableau:ttab) 
// Décide du meilleur coup à jouer par le joueur J dans la situation e 
var val:real;
cp:tcoups;
x:integer;
begin
  cp:=coupsPossibles(tableau,couleur_cpu);
  for x := 0 to cp.nb_coups-1 do
    val = ValeurAlphaBeta(jouer(tableau, couleur_cpu, a_joue,cp.coups[x]),couleur_cpu,-infinity,+infinity,false,4);//pmax=4
    if val>alpha then
    begin
      result= coup;
      alpha  = val;
   end;
  end;
end;
 
function ValeurAlphaBeta (tableau:ttab;joueur:integer;alpha:real;beta:real;EstUnEtatMax:boolean;pmax:integer):real ;
{ Calcule la valeur de e pour le joueur J selon que e EstUnEtatMax ou pas
  et pmax la profondeur maximale }
var
x:integer;
cp:tcoups;
begin
  if gagne(tableau) =joueur then result:=+infinity
  else if gagne(tableau)=3-joueur then  result:=-infinity
        else if PartieNulle(tableau) then result:=0
              else 
                 if pmax=0 then result:=evalue(tableau,joueur)
		 else
                   if EstUnEtatMax then // noeud MAX
                   begin
                     cp:=coupsPossibles(tableau,joueur);
                     for x := 0 to cp.nb_coups-1 do
                     begin
                        alpha := max(alpha,ValeurAlphaBeta(jouer(tableau, couleur_cpu, a_joue,cp.coups[x]),couleur_cpu,alpha,beta,not(EstUnEtatMax),pmax-1));
                        if alpha >= beta then
                        begin
                          result:=alpha;  // coupe beta 
                          exit;
                        end;
                     end;
                     result:=alpha;
                   end
                   else
                   begin //noeud MIN
                     cp:=coupsPossibles(tableau,joueur);
                     for x := 0 to cp.nb_coups-1 do
                     begin
                        beta := min(beta,ValeurAlphaBeta(jouer(tableau, couleur_humain, a_joue,cp.coups[x]),couleur_humain,alpha,beta,not(EstUnEtatMax),pmax-1));
                        if beta <= alpha then
                        begin
                          result:=beta; // coupe alpha 
                          exit;
                        end;
                     end;
                     result:=beta;
                   end;
end;

;

[Sylvain255]

je vois plusieurs erreurs dans l'algo de https://fabien-torre.fr/Enseignement...ielle/jeux.php :
le joueur n'est jamais changé dans les appels à ValeurAlphaBeta
dans DecisionAlphaBeta une fois c'est ValMax une fois c'est MaxVal
dans Si pmax=0 Alors retourner h(s,J) ça devrait être e et pas s car s n'est pas défini contrairement à e

[anapurna]

salut

je vois aussi plusieurs erreur dans ton algo alphabeta
je crois que tu n'as pas bien saisie la logique de l'algorithme

Code :

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
 
// Version complete
function alphabeta(nœud, alpha, Beta) : Valeur;
(* α est toujours inférieur à β *)
  If IsFeuille(nœud) Then 
  begin 
    Result := ValeurNoeud(nœud);
  end
  else   
  If TypeNoeud(nœud) = _Min alors  // ici c'est ton changement de joeur 
  begin 
    v := ValeurMax;
    ForEach fils in nœud do 
    Begin 
      v := min(v, alphabeta(fils, alpha, Beta))                
      if alpha >= v Then   (* coupure alpha *)
      Begin 
         Result := v;
	 Exit;
	 end;	
      End;  
     Beta = min(Beta, v)           
  end 			   
  else 
  begin 
    v = ValeurMax*-1;
    ForEach fils in nœud do 
    Begin 
      v := max(v, alphabeta(fils, alpha, Beta))                
      If v >= Beta Then (* coupure beta *)
      begin  
          Result :=  v
          Exit;
      end;
      alpha := max(alpha, v)
  end;		   
  Result := v;
end;

[Sylvain255]

ta version utilise des arbres mais la mienne et celle du site Internet non je préfère ne pas utiliser d'arbres