Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Problem bei der Rekursion des MiniMax Algorithmus

Werbeanzeige

Zuko347

Frischling

  • »Zuko347« ist der Autor dieses Themas

Beiträge: 5

  • Private Nachricht senden

1

07.01.2015, 18:56

Problem bei der Rekursion des MiniMax Algorithmus

Hallo!

Ich bin leider noch Anfänger beim Programmieren. Um zu üben habe ich versucht mit Code::Blocks (c++) das Spiel "5 Gewinnt" zu programmieren. Es klappt schon ganz gut :)! Nur habe ich Probleme bei der KI. Ich habe mir eine Struct Field zur vereinfachung gemacht:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8

static int X_Size=9;
static int Y_Size=9;

struct Field
{
    int Array[9][9];
    int Bewertung;
};


In der main Methode darf abwechselnd der Spieler und dann der Computer einen Zug machen. Ich habe mit im Internet den "vergleichsweise" einfachen MiniMax-Algorithmus zum umsetzen der KI angeschaut. ( http://de.wikipedia.org/wiki/Minimax-Algorithmus ). So Sieht der code der KI-Funktion jetzt aus :) :

C-/C++-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

Field ComputerZug(Field SField, int Player, int Zuege)
{
    int EnemyPlayer = -Player +3;
    Field newField;
    SField.Bewertung=0;

    int finalBewertung=-9999999;
    int finalX_Pos;
    int finalY_Pos;

    if(Zuege>0)
    {
        for(int count_i=0;count_i<X_Size;count_i++)
        {
            for(int count_j=0;count_j<Y_Size;count_j++)
            {
                if(SField.Array[count_i][count_j]==0)
                {
                    int currentBewertung=0;
                    Field tempField=insertValue(SField, count_i,count_j,Player);

                    if(PlayerWin(tempField)==Player)
                    {
                        currentBewertung+=1000000;
                    }



                    newField=ComputerZug(tempField, EnemyPlayer, Zuege-1);
                    if(PlayerWin(newField)==EnemyPlayer)
                    {
                        currentBewertung-=newField.Bewertung/100;
                    }

                    if(currentBewertung>finalBewertung)
                    {
                        finalBewertung=currentBewertung;
                        finalX_Pos=count_i;
                        finalY_Pos=count_j;

                    }
                }
            }
        }
    }
    else
    {
        return SField;
    }


    SField.Bewertung=finalBewertung;
    return insertValue(SField, finalX_Pos,finalY_Pos,Player);

}


Die Parameter: SField gibt das Feld an, für den ein neuer Zug ausgedacht werden soll, Spieler den Spieler für den der Computer spielen soll(1 oder 2) und Zuege die Anzahl der Zuege die er vorberechnen soll. Leider kann der KI aber nur maximal 1 Zug voraussehen, auch wenn man mehr angibt. Ich vermute das Problem liegt entweder bei der Rekursion selbst oder bei der Bewertung der SpielfeldSituation. Die Bewertung sieht im moment nur so aus, als dass geschaut wird, ob der Computer in einer bestimmten anzahl an Zuegen gewinnen kann. (die Funktion Playerwin(Field SField)). Leider komme ich nicht weiter was genau mein Denkfehler ist ): , vielleicht hat jemand ja eine Idee! Meine Restlichen Funktionen sind:

C-/C++-Quelltext

 
1
2
3
4

void DrawField(Field SField);
Field NewField();
Field insertValue(Field SField,int x_pos, int y_pos, int Value);
int PlayerWin(Field SField);


Viele Grüße

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

2

07.01.2015, 19:04

Bau doch mal Funktionen ein, mit denen du den Ablauf deines Programms nachvollziehen kann. Du koenntest z.b. immer ausgeben, welchen Zug der Computer gerade testet, wie er ihn bewertet und wie das Spielfeld dazu aussieht.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Ähnliche Themen