Fehler in einer AI finden

Mortal-Shadow · Beiträge: 110

Hi,

ich wollte ein 4 gewinnt Spiel programmieren.
Um gegen den PC zu spielen braucht es natürlich noch eine AI.
Ich habe mich entschlossen rekursiv alle Züge zu berechnen.
Das sieht vereinfacht so aus:
Wenn der PC dran ist, ruft er eine Funktion SearchPCTurn auf.
Diese ruft SearchHumanTurn (für jeden möglichen Zug einmal, mit angepasstem Spielfeld) auf, die wiederum SearchPCTurn aufruft.
Dabei wird immer übergeben, der wievielte Aufruf dies ist.
Wenn Aufruf = MaxAufrufe gibt die Funktion zurück, ob es im Moment unentschieden, oder wer gewonnen hat.
Andernfalls schaut SaerchPCTurn, was die Rückgabewerte der Funktionen waren.
Mindestens einmal PCgewinnt: result -> Pcgewinnt, Min einmal unentschieden: result -> unentschieden, ansonsten result -> Mensch.

SearchHumanTurn funktioniert fast genau so, nur dass sie zuerst schaut ob min einmal Menschgewinnt.

Der Computer versucht natürlich den Zug zu machen, bei dem Rauskam er gewinnt, danach unentschieden und zum Schluss die wow er verlieren wird.

Allerdings muss ich irgendwo einen Fehler gemacht haben, denn der PC spielt sche****.
Aber ich habe keine Ahnung wie ich vernünftig testen kann wo das Problem liegt.

Hat einer von euch eine Idee?

crncpz · Beiträge: 59 WIN 2000, WIN XP Pro Delphi 6

wenn ich das jetzt richtig verstanden habe nimmt der computer den ersten zug der ihm erfolg verspricht?
so ist aber kein "intelligentes" spiel möglich. versuch doch mal für einen bestimmten zug für den computer alle weiteren möglichkeiten zu ermitteln die nach dem zug möglich wären. dann könntest du eine prozentuale auswertung machn die ergibt x% gewinnt computer, y%unentschieden, z% mensch gewinnt.
das müsstest du für 7 mögliche nächste zuüge machen und den zug wählen der die hööchste erfolgs prozentzahl vorraus sagt.

das ist zwar noch immer keine wirkliche intelligenz aber so könnte die ai schon deutlich besser spielen.

edit:

Mortal-Shadow hat folgendes geschrieben :

Wenn Aufruf = MaxAufrufe gibt die Funktion zurück, ob es im Moment unentschieden, oder wer gewonnen hat.

du darfst die rekursion auch nicht so lange laufen lassen bis alle steine gesetzt wurden und dann kucken wer gewonnen hat, sondern musst nach jedem rekursion schritt prüfen.

ffgorcky · Beiträge: 573 WIN XP/2000 & 7Prof (Familie:Win95,Win98)

Das wäre wesentlich einfacher, wenn Du uns Deinen bisherigen Quelltext offenbaren könntest.
Oder zumindest schon mal Dein (soweit fertiges, jetziges) Programm, so dass wir das ausprobieren und anführen können, wo noch Verbesserungsvorschläge verarbeitet werden müssten.
Ich würde das ganze mit einem 2-dimensionalen, int-Array machen, wo ich dann 0(=Null) für unbesetzt, 1 für den einen und 2 für den anderen Spieler eintragen würde.

Mortal-Shadow · Beiträge: 110

@crncpz: momentan berechnet er 5 züge vorraus - wenn er in einem sicher gewinnt, macht er das.
Wenn er bei einem sicher verliert macht er ihn nur, wenn kein anderer möglich ist.
Zumindest hab ich mir das so vorgestellt.
Deine Variante wäre eine Verfeinerung für die Züge ohne eindeutigen Gewinner. Atm missachtet er aber, wenn er direkt verliert.
Wenn er direkt gewinnt, nutzt er es.

@ffgorcky: kann ich machen - ist halt viel Text, da ich keine Ahnung habe, wo der Fehler liegt.
TSpielfeld ist eigentlich nur ein zweidimmensionaler Array mit den Ausmaßen der Konstanten HOEHE (=6) und BREITE(=7)
Wenn beim Create nil übergeben wird erschafft es ein leeres Spielfeld, ansonstenkopiert es ein übergebenes

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:

function TForm1.ComputerTurn : Integer;  //wird aufgerufen wenn der PC am Zug ist
var count1 : Integer;
begin
label1.Caption := '';
For count1 := 1 to BREITE do
    begin
    Case SearchWinningTurn(Spielfeld, count1, Suchtiefe)of  //gibt zurück wer Gewinner bei dem Zug sein wird: Funktion weiter unten  //Suchtiefe ist ne Konstante (=5)
    Winner_Computer: WinList.Add(count1);  //Die Listen sind n dynamischer Array, der Integer Werte speichert
    Winner_None: PossibleList.Add(count1);
    Winner_Mensch: LooseList.Add(count1);
    end;
    end;
If Winlist.Count > 0 then
    begin
    result := Winlist.GetRandom;
    label1.Caption := 'Juhu, ich glaube ich werde gewinnen'; //zum Fehler finden eingefügt: Dieser Text kommt nur im Zug in dem er gewinnt
    end
else If PossibleList.Count > 0 then
    begin
    result := PossibleList.GetRandom;
    label1.Caption := 'Momentan weis ich nicht wer gewinnen wird. ' + inttostr(possiblelist.Count);
    end
else If LooseList.Count > 0 then
    begin
    result := Looselist.GetRandom;
    label1.Caption := 'Mist, ich bin am verlieren';  //kommt nie
    end
else
    begin
    result := 0;
    end;
Winlist.Clear;
Looselist.Clear;
possiblelist.Clear;
end;

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:

function TForm1.SearchWinningTurn(Prefeld : TSpielfeld; PutLoc, Tiefe : Integer): TWinner;
var OnFeld : TSpielfeld;
count1 : Integer;
begin
OnFeld := TSpielfeld.Create(PreFeld);
Case OnFeld.Put(PutLoc, Owner_Computer) of  //manipuliert das Spielfeld indem ein Stein in die entsprechende Reihe geworfen wird. Überprüft dann ob die neue Situation gewonnen/verloren ist
PS_NotPossible: result := Winner_Impossible;  //Wird zurückgegeben wenn in diese Reihe nicht gesetzt werden kann
PS_Won:         result := Winner_Computer;    //Wird zurückgegeben wenn derjenige der den Stein geworfen hat dadurch gewinnt
PS_Putted :     begin  //Der Zug ist möglich, aber keiner gewinnt
                If Tiefe = 0 then    //Rekursion zu Ende - kein eindeutiger Gewinner
                    result := Winner_None 
                else   //Weitersuchen mit der neuen Spielfeldsituation
                    begin
                    result := Winner_Mensch;
                    For count1 := 1 to BREITE do
                        begin
                        Case SearchEnemyTurn(OnFeld,count1,Tiefe-1) of  //nimmt eine perfekte menschliche Spielweise an
                        Winner_Computer: result := Winner_Computer;  
                        Winner_None: begin
                                     If result <> Winner_Computer then
                                         result := Winner_None;
                                     end;
                        end;
                        end;
                    end;

                end;
end;
OnFeld.Destroy;
end;

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:

function TForm1.SearchEnemyTurn(Prefeld : TSpielfeld; PutLoc, Tiefe : Integer): TWinner;
var OnFeld : TSpielfeld;
count1 : Integer;
begin               //Fast das gleiche wie die vorherige Funktion - nur Mensch und PC vertauscht
OnFeld := TSpielfeld.Create(PreFeld);
Case OnFeld.Put(PutLoc, Owner_Mensch) of
PS_NotPossible: result := Winner_Impossible;
PS_Won:         result := Winner_Mensch;
PS_Putted :     begin
                If Tiefe = 0 then
                    result := Winner_None
                else
                    begin
                    result := Winner_Computer;
                    For count1 := 1 to BREITE do
                        begin
                        Case SearchWinningTurn(OnFeld,count1,Tiefe-1) of
                        Winner_Mensch: result := Winner_Mensch;
                        Winner_None: begin
                                     If result <> Winner_Mensch then
                                         result := Winner_None;
                                     end;
                        end;
                        end;
                    end;

                end;
end;
OnFeld.Destroy;
end;

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:

function TSpielfeld.Put(PutLoc : Integer; ForPlayer : TFeldOwner) : TPutState;
var count1 : Integer;
Abbruch : boolean;
begin  //legt Spielsteine
count1 := 1;
Abbruch := false;
Repeat  //sucht den tiefstmöglichen Punkt in der übergebenen Reihe
If IsValidPoint(PutLoc, Count1) then
    begin
    If Felder[PutLoc, Count1] = Owner_None then
        begin
        Felder[PutLoc, Count1] := ForPlayer;
        If TestWin(PutLoc, Count1) then
            result := PS_Won
        else
            result := PS_Putted;
        Abbruch := true;
        end
    else
        begin
        inc(count1);
        end;
    end
else
    begin
    result := PS_NotPossible;
    Abbruch := true;
    end;
Until Abbruch;
end;

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:

function TSpielfeld.TestWin(x,y : integer): boolean;
var streak, count1, count2 : integer;
begin  //Testet ob um den geworfenen Stein mindestens vier anliegen
streak := 0;
result := false;
For count1 := (x-3) to (x + 3) do  //waagrecht
    begin
    If IsValidPoint(count1, y) then
    If Felder[count1, y] = Felder[x,y] then
        begin
        inc(streak);
        If streak = 4 then
            result := true;
        end
        else
            begin
            streak := 0;
            end;
    end;
streak := 0;
If not result then
For count1 := (y-3) to (y + 3) do  //senkrecht
    begin
    If IsValidPoint(x, count1) then
    If Felder[x, count1] = Felder[x,y] then
        begin
        inc(streak);
        If streak = 4 then
            result := true;
        end
        else
            begin
            streak := 0;
            end;
    end;
streak := 0;
If not result then
For count1 := (x-3) to (x + 3) do  //diagonal1
    begin
    count2 := count1;
    If IsValidPoint(count1, count2) then
    If Felder[count1, count2] = Felder[x,y] then
        begin
        inc(streak);
        If streak = 4 then
            result := true;
        end
        else
            begin
            streak := 0;
            end;
    end;
streak := 0;
If not result then    
For count1 := (x-3) to (x + 3) do    //diagonal2
    begin
    count2 := 2*y - count1;
    If IsValidPoint(count1, count2) then
    If Felder[count1, count2] = Felder[x,y] then
        begin
        inc(streak);
        If streak = 4 then
            result := true;
        end
        else
            begin
            streak := 0;
            end;
    end;
end;

So das wars.
Falls noch was fehlt -> sagen.

Mfg.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme