MiniMax Algorithmus

F34r0fTh3D4rk · Verfasst: Di 25.04.06 21:40

Hi, ich quäle mich jetzt seit ewigkeiten mit meinem Minimax Algorithmus, ich möchte, dass er für das spiel TicTacToe, den nächsten bestmöglichen zug berechnet, soweit so fein, jetzt habe ich eine Bewertungsfunktion geschrieben, die wirklich für bessere spielsituationen bessere werte ausgibt. der minimax funktioniert jedoch nicht so ganz, da er entscheidungen trifft die überhaupt nicht sinnvoll sind, zb:

x = pc
o = mensch

markieren

Quelltext

1:
2:
3:

---
-X-
---

markieren

Quelltext

1:
2:
3:

---
-X-
O--

markieren

Quelltext

1:
2:
3:

X--
-X-
O--

markieren

Quelltext

1:
2:
3:

X--
-X-
OO-

soweit so verständlich, aber jetzt:

markieren

Quelltext

1:
2:
3:

XX-
-X-
OO-

markieren

Quelltext

1:
2:
3:

XX-
-X-
OOO

Mensch gewinnt, die frage ist, warum nimmt er nicht das feld unten rechts ? Oo

hier mein algo:

markieren

Delphi-Quelltext

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:

{
hier findet die berechnung des nächstbesten zuges statt.
verwendet wird der minimax algorithmus
am anfang versucht die ki jedoch erst einmal einen stein
in die mitte zusetzten, andernfalls setzt sie ihn links oben
}
procedure TForm1.ki;
var
  nextone: integer;
  function maxwert: integer; forward;
  function minwert: integer;
  var
    ermittelt, zugwert, i, c: integer;
    voll: boolean;
  begin
    zugwert := 0;
    ermittelt := maxint;
    voll := true;
    for i := 1 to 9 do
      if felder[i] = nix then
      begin
        felder[i] := blau;
        for c := 1 to 9 do
          if felder[c] = nix then
          begin
            voll := false;
            break;
          end;
        if voll then
          zugwert := bewertung else
            zugwert := maxwert;
        felder[i] := nix;
        if zugwert < ermittelt then
        begin
          nextone := i;
          ermittelt := zugwert;
        end;
        if voll then
          break;
      end;
    result := ermittelt;
  end;
  function maxwert: integer;
  var
    ermittelt, zugwert, i, c: integer;
    voll: boolean;
  begin
    zugwert := 0;
    ermittelt := - maxint;
    voll := true;
    for i := 1 to 9 do
      if felder[i] = nix then
      begin
        felder[i] := rot;
        for c := 1 to 9 do
          if felder[c] = nix then
          begin
            voll := false;
            break;
          end;
        if voll then
          zugwert := bewertung else
            zugwert := minwert;
        felder[i] := nix;    
        if zugwert > ermittelt then
          ermittelt := zugwert;
        if voll then
          break;
      end;
    result := ermittelt;
  end;
begin
  nextone := 5;
  if not spielende then
  begin
    if (runden = 1) and (felder[5] = rot) then
      nextone := 1;
    if runden > 1 then
      minwert;
    if felder[nextone] = nix then
    begin
      felder[nextone] := blau;
      tshape(findcomponent('shape' + inttostr(nextone))).brush.color := clblue;
      if gwinner = maschine then
      begin
        spielende := true;
        showmessage('Du hast verloren');
      end else
        if gwinner = unentschieden then
          showmessage('Unentschieden');
      spieler := mensch;
      inc(runden);
      label1.caption := 'Du bist dran';
    end;
  end;
end;

das spielfeld ist ein array [1..9] of TFeld tfeld kann rot, blau oder auch nix sein.

ich habe den rest mal angehängt

vielen dank schonmal

Einloggen, um Attachments anzusehen!

alzaimar · Verfasst: Di 25.04.06 21:51

Es ist immer schwer, sich in die Gedanken Anderer hineinzuversetzen. Umso schwerer bei Algorithmen. ich kenne den minimax-Algorithmus ganz Anders:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

Function FindeBestenZug (Level : Integer; Spieler, Gegner : TSpieler: Brett : TSpielfeld) : Integer;
Begin
  L := ErzeugeListeAllerZüge;
  MaxS := -999999;
  Foreach Z in L Do Begin
    MakeTheMove (Brett, Spieler, Gegner, Z);                                           // Zug ausführen
    If Level = MaxZugTiefe Then
      S := BewerteStellung (Brett, Spieler, Gegner)              // Je höher der Wert, desto besser ist
    Else                                                              // die Stellung für den 'Spieler'
      S := -FindeBestenZug (Level + 1, Gegner, Spieler, Brett);     // Und dann besten Gegnerzug finden
// Hier wird der beste Gegnerzug geliefert. Wir wollen aber den Zug, der S minimiert! Deshalb das MINUS
    UndoMove  (Brett, Spieler, Gegner, Z);                                     // Zug rückgängig machen
    If S > MaxS Then Begin                 // Ist der Zug besser als alle bisherigen in diesem Versuch?
      MaxS := S;                                                                             // Merken!
      MaxZ := Z;                                               // MaxZ in Stufe 0 ist der gesuchte Zug!
    End;
  End;
Result := MaxS;
End;

Ich habe das nicht getestet, aber es sollte hinkommen.

_________________
Na denn, dann. Bis dann, denn.

F34r0fTh3D4rk · Verfasst: Mi 26.04.06 15:40

das ist die NegaMax Variante

die liste aller züge erzeugen, das ist doch die liste mit allen in der runde möglichen zügen oder ?

bei mir:

markieren

Delphi-Quelltext

1:
2:

  for i := 1 to 9 do
    if felder[i] = nix then

für alle züge die möglich sind wird das folgende ausgeführt

und

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

  procedure nextbest;
  var
    i, curr, mini: integer;
  begin
    mini := maxint;
    for i := 1 to 9 do
      if felder[i] = nix then
      begin
        felder[i] := blau;
        curr := bewertung;
        if curr < mini then
        begin
          mini := curr;
          nextone := i;
        end;
        felder[i] := nix;
      end;
  end;

ist die unintelligente variante,

den negamax hab ich mal so eingebaut, aber da tut sich nichts:

markieren

Delphi-Quelltext

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:

Function NegaMax (Level: Integer; spieler: TSpieler) : Integer;
var
  MaxS, S, i: integer;
begin
  MaxS := -maxint;
  for i := 1 to 9 do
    if felder[i] = nix then
    begin
      case spieler of
        mensch: felder[i] := rot;
        maschine: felder[i] := blau;
      end;
      if level = maxdepth then
      begin
        case spieler of
          mensch: S := BewerteFarbe(rot);
          maschine: S := BewerteFarbe(blau);
        end;
      end else
      S := -NegaMax(Level + 1, Spieler);
      felder[i] := nix;
    if S > MaxS then
    begin
      MaxS := S;
    end;
  end;
  result := MaxS;
end;

die bewertungsfunktion bewertet jetzt auch für beide spieler positiv, aber so recht klappt das net, ist im grunde auch das gleiche, nur das funzt garnet, eigentlich braucht man die bewertung überhaupt nicht, weil die maximale tiefe bei mir ohnehin maximal ist, weil es nicht so viele schritte zu berechnen gibt.

das hier funktioniert auch nicht:

markieren

Delphi-Quelltext

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:

  function maxwert: integer; forward;
  function minwert: integer;
  var
    ermittelt, zugwert, i: integer;
  begin
    zugwert := 0;
    ermittelt := maxint;
    for i := 1 to 9 do
      if felder[i] = nix then
      begin
        felder[i] := blau;
        if gwinner = maschine then
          zugwert := -1;
        if gwinner = mensch then
          zugwert := 1;
        if gwinner = unentschieden then
          zugwert := 0;
        if gwinner = keiner then
          zugwert := maxwert;
        felder[i] := nix;
        if zugwert < ermittelt then
        begin
          nextone := i;
          ermittelt := zugwert;
        end;
      end;
    result := ermittelt;
  end;
  function maxwert: integer;
  var
    ermittelt, zugwert, i: integer;
  begin
    zugwert := 0;
    ermittelt := - maxint;
    for i := 1 to 9 do
      if felder[i] = nix then
      begin
        felder[i] := rot;
        if gwinner = maschine then
          zugwert := -1;
        if gwinner = mensch then
          zugwert := 1;
        if gwinner = unentschieden then
          zugwert := 0;
        if gwinner = keiner then
          zugwert := minwert;
        felder[i] := nix;
        if zugwert > ermittelt then
          ermittelt := zugwert;
      end;
    result := ermittelt;
  end;

alzaimar · Verfasst: Do 27.04.06 19:39

Leider bin ich voll im Stress, aber soviel vorab: Deine Routine solltest Du einfach mit zwei Parametern aufrufen (neben 'Brett' und 'Leve'), nämlich 'Spieler' und 'Gegner'. Beim rekursiven Abstieg vertauscht Du Spieler und Gegner. Dann kannst Du Dir deine Fallunterscheidung sparen.

Ich versuche heute mal, TTT zu programmieren und schicke Dir, falls ich nicht auf die Fresse falle, die Version zu, bzw. poste sie hier.

Deine Annahmen ('Liste der möglichen Züge') ist richtig. Bei komplexeren Spielen erzeugt man erst diese Liste, macht eine Vorabbewertung, um z.B. ein Schach-Matt sofort zu erkennen, oder Züge, die einen vor dem Verlieren bewahren. Das ist bei der Verfeinerung, dem Alpha-Beta-Pruning von entscheidender Bedeutung...

_________________
Na denn, dann. Bis dann, denn.

F34r0fTh3D4rk · Verfasst: Do 27.04.06 19:43

jo danke schonmal, hab schon 5 versionen mit auskommentierten zeilen, dabei ist das eigentliche programm recht klein, ich kann dir ja mal mein ttt schicken es muss nur die ki gefüllt werden, und den wert nextone, für das nächst zu füllende feld setzen, sonst ist alles fertig

F34r0fTh3D4rk · Verfasst: Do 04.05.06 17:24

und wie sieht es aus ? evtl kannst du dich ja mal per pm oder icq an mich wenden

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme