MiniMax Algorithmus (Spiele KI)
Zum Code
Der MiniMax-Algorithmus ist eine künstliche Intelligenz, die in der Simulation von Brettspielen oder ähnlichem sehr viel Verwendung findet. Das Arbeitsprinzip des Algorithmus sieht folgendermaßen aus:

Von einer Ausgangsposition simuliert der Computer abwechselnd eigene und gegnerische Züge (alle, die es gibt) bis zu einer bestimmten Tiefe, bei der er dann die Stellung bewertet. Diese Bewertung sieht so aus, dass eine günstige Stellung für ihn einen positiven (großen) Wert erhält, eine günstige Stellung für den Gegner erhält einen negativen (niedrigen) Wert.

Hierdurch entsteht nun ein Spielbaum. Ganz oben befindet sich die Ausgangsposition. Von dieser zweigen ab alle Stellungen, die der Computer durch einen Zug erreichen kann. Von jenen Stellungen wiederum zweigen jeweils wieder alle Stellungen ab, die durch einen erneuten Zug des Spielers (der Computer simuliert ja diesen gegnerischen Zug) erreicht werden können. Etc. etc. bis irgendwann Schluss ist, und der Baum entweder eine vorgeschriebene Tiefe erreicht hat oder - wie in diesem Beispiel - ein Endzustand (Sieg, Niederlage oder Brett ist voll) erreicht ist.

Nun versucht der Rechner einen Weg zurückzuverfolgen, auf dem er auf eine für ihn möglichst günstige Stellung auf der letzten Eben des Baumes gelangt. Zu diesem Zweck sucht er sich aus allen Stellungswerten, die er durch einen eigenen Zug erreichen kann, das Maximum heraus und gibt dieses weiter an den Elternknoten. Aus allen Stellungswerten, die durch einen simulierten gegnerischen Zug entstanden sind, wählt er denjenigen, der am kleinsten ist. Der Computer geht nämlich davon aus, dass der Spieler den seinerseits besten Zug nimmt und dadurch die schlechteste Stellung für den PC erreicht.

Durch dieses Weitergeben von abwechselnd maximierten und minimierten Knoten erhält der Computer nun für jede ihm zur Verfügung stehende Auswahl einen bestimmten Wert, der ihm angibt, welche der Auswahl er am günstigsten treffen sollte.

Dies hört sich wahrscheinlich alles sehr schwer verständlich an, ist es aber wirklich nicht. Am besten einfach mal in Google "MiniMax" eintippen oder ähnliches. Unter den Suchergebnissen wird man sicher viele lustige Bildchen mit beschriebenen Spielbäumen finden. Visuell dargestellt lässt sich das ganze dann sehr viel einfacher begreifen =)

History
09.07.2003 Hinzugefügt

Autor: Benjamin Schröder <immoertael_auf_gmx.de> 

Code aus frmTicTacToe.frm
Option Explicit
Dim SpielerZug As Boolean
'Ist der Spieler am Zug?
Dim Spielfeld(2, 2) As String
'Virtuelles Spielfeld
Dim TOTALSTONES As Integer
'Anzahl der Steine auf dem Feld

Private Sub Command1_Click()
'PC beginnt mit Zufallszug um Rechenzeit zu sparen
    ResetGame
    'Alles zurücksetzen
    Randomize
  Dim i%, j%
    i = Int(Rnd * 2 + 0.5)
    'Zufällige Koordinaten
    j = Int(Rnd * 2 + 0.5)
    Feld.TextMatrix(i, j) = "O"
    'Setzen auf dem sichtbaren wie auch auf dem
    Spielfeld(i, j) = "O"
    'unsichtbaren Feld, wie gehabt
    TOTALSTONES = TOTALSTONES + 1
    'Mittlerweile klar..
    SpielerZug = True
    'Nun ist der Spieler dran
    Label1.Caption = "Spieler am Zug.."
End Sub
Private Sub Feld_Click()
    If SpielerZug Then
      'Wenn der Spieler am Zuge ist, ansonsten wird das Klicken _
          einfach nicht beachtet
      If Feld.TextMatrix(Feld.RowSel, Feld.ColSel) = "" Then
        'Wenn das selektierte Feld auch frei ist
        Feld.TextMatrix(Feld.RowSel, Feld.ColSel) = "X"
        'Setzt einen Stein für den Spieler auf dem sichtbaren Feld
        Spielfeld(Feld.RowSel, Feld.ColSel) = "X"
        'Tut das gleiche auf dem virtuellen Feld, welches die KI _
            zur Berechnung ihres Zuges nutzt
        TOTALSTONES = TOTALSTONES + 1
        'Ist wohl klar
        
        If GameOver = "X" Then
          'Wenn der Spieler mit dem Zug gewonnen hat
          If MsgBox("Gewonnen! (Sollte eigentlich unmöglich sein?) " & _
              "Nochmal spielen?", vbYesNo, "Sieg") = vbYes Then
            ResetGame
            'Nochmal von vorne
          Else
            Exit Sub
            'Schluss
          End If
        ElseIf GameOver = "Unentschieden" Then
          'Spiel ist unentschiede
          If MsgBox("Unentschieden. Nochmal?", vbYesNo, _
              "Unentschieden") = vbYes Then
            ResetGame
            'Nochmal von vorne
          Else
            Exit Sub
            'Schluss
          End If
        End If
        
        SpielerZug = False
        'Ab jetzt darf der Spieler erstmal nicht mehr setzen, er _
            muss nun auf den Zug der KI warten
        
        Label1.Caption = "KI rechnet.."
        'Zeigt besonders bei den ersten Zügen, dass das Programm
        Form1.MousePointer = 11
        'etwas tut und nicht abgeschmiert ist
        DoEvents
        
  Dim i, j As Integer
  Dim Bewertung(2, 2) As Integer
        For i = 0 To 2
          For j = 0 To 2
            Bewertung(i, j) = -50
            'Bewertung für jedes Feld initialisieren mit niedrigem _
                Wert So kann man später erkennen, auf welches Feld _
                gesetzt werden kann und auf welches nicht. Nicht _
                besetzbare Felder behalten nach der Kalkulierung _
                des Zuges immer noch den niedrigen Wert und kommen _
                daher automatisch nicht für den Zug in Frage.
          Next j
        Next i
        For i = 0 To 2
          'Gehe das komplette Spielfeld durch
          For j = 0 To 2
            If Feld.TextMatrix(i, j) = "" Then
              'Wenn auf das aktuelle Feld gesetzt werden kann
              Spielfeld(i, j) = "O"
              'Simuliere einen Zug
              TOTALSTONES = TOTALSTONES + 1
              Bewertung(i, j) = KI(1, -10000, 10000, "X")
              'Hole die Bewertung für diesen Zug
              Spielfeld(i, j) = ""
              'Nimm den Zug wieder zurück
              TOTALSTONES = TOTALSTONES - 1
            End If
          Next j
        Next i
        
  Dim MaxWert%, MaxPos(1) As Integer
        MaxWert = -30
        
        For i = 0 To 2
          'Hier wird nun aus den gesammelten Bewertungen die
          For j = 0 To 2
            'höchste rausgesucht
            If Bewertung(i, j) > MaxWert Then
              'Wenn Wert im Array größer
              MaxWert = Bewertung(i, j)
              'Dann merk den neuen Maxwert
              MaxPos(0) = i
              '.. und die Position
              MaxPos(1) = j
            End If
          Next j
        Next i
        
        'Wenn mehrere gleich gute Züge existieren so wird der _
            erste im Array vorkommende
        'genommen
        
        Feld.TextMatrix(MaxPos(0), MaxPos(1)) = "O"
        'Führt dann tatsächlich den Zug
        Spielfeld(MaxPos(0), MaxPos(1)) = "O"
        'mit der höchsten Bewertung aus
        TOTALSTONES = TOTALSTONES + 1
        
        Label1.Caption = "Spieler am Zug.."
        'Nun ist der Spieler wieder dran
        Form1.MousePointer = 0
'Doch zunächst noch die Gewinnüberprüfung:
        If GameOver = "O" Then
          'Wenn dieser Zug die KI zum Sieger macht
          If MsgBox("Die KI hat gewonnen! Nochmal spielen?", _
              vbYesNo, "Sieg") = vbYes Then
            ResetGame
            'Nochmal
          Else
            Exit Sub
            'Schluss
          End If
        ElseIf GameOver = "Unentschieden" Then
          'Spiel ist unentschieden
          If MsgBox("Unentschieden. Nochmal?", vbYesNo, _
              "Unentschieden") = vbYes Then
            ResetGame
            'Nochmal
          Else
            Exit Sub
            'Schluss
          End If
        End If
        
        SpielerZug = True
        'Der Spieler darf jetzt wieder ziehen
        
      End If
    End If
End Sub
Private Function GameOver() As String
'Beurteilt die Stellung danach wer gewonnen hat
  Dim i%
    
    For i = 0 To 2
      'Die Waagerechte wird durchsucht, Reihe um Reihe
      If Spielfeld(i, 0) <> "" And Spielfeld(i, 0) = Spielfeld(i, _
          1) And Spielfeld(i, 1) = Spielfeld(i, 2) Then
        'Wenn eine Reihe gleicher Steine vorhanden ist
        GameOver = Spielfeld(i, 0)
        'Die Funktion gibt zurück, wer mit jener Reihe gewinnt
        Exit Function
      End If
    Next i
    
    For i = 0 To 2
      'Die Senkrechte wird durchsucht, Spalte um Spalte
      If Spielfeld(0, i) <> "" And Spielfeld(0, i) = Spielfeld(1, _
          i) And Spielfeld(1, i) = Spielfeld(2, i) Then
        'Wenn eine Spalte gleicher Steine vorhanden ist
        GameOver = Spielfeld(0, i)
        'Die Funktion gibt zurück, wer mit jener Spalte gewinnt
        Exit Function
      End If
    Next i
    
    If Spielfeld(2, 0) <> "" And Spielfeld(2, 0) = Spielfeld(1, 1) _
        And Spielfeld(1, 1) = Spielfeld(0, 2) Then
      'Wenn die Diagonale (links unten nach rechts oben) nur _
          gleiche Steine enthält
      GameOver = Spielfeld(2, 0)
      'Mittlerweile dürfte es klar sein :)
      Exit Function
    End If
    
    If Spielfeld(0, 0) <> "" And Spielfeld(0, 0) = Spielfeld(1, 1) _
        And Spielfeld(1, 1) = Spielfeld(2, 2) Then
      'Diagonale (links oben nach rechts unten
      GameOver = Spielfeld(0, 0)
      Exit Function
    End If
    
    'Wenn vorher niemand gewonnen hat wird noch getestet, ob das _
        Brett voll ist
    If TOTALSTONES = 9 Then
      GameOver = "Unentschieden"
    End If
End Function
Private Function KI(Tiefe, a, b As Integer, Spieler As String) As _
    Integer
'Die Minimax-Funktion. Tiefe repräsentiert die Zugtiefe, Spieler _
    den Spieler, dessen Zug
'simuliert werden soll. a und b sind Hilfsvariablen zur _
    Feststellung von Maximum (a) bzw.
'Minimum (b) an den entsprechenden Knoten
  Dim w, i, j As Integer
    If GameOver = "X" Then
      'Baum ist zu Ende, wenn der Spieler eine gewinnende Stellung _
          erhält
      KI = -1 * (10 - Tiefe)
      'Es wird dann eine negative Bewertung zurückgegeben,
      'je weiter oben im Baum diese Stellung ist, desto akuter die
      'Gefahr und darum auch desto kleiner der Wert
    ElseIf GameOver = "O" Then
      'Baum ist auch zu Ende, wenn die KI eine gewinnende Stellung _
          erhält
      KI = 10 - Tiefe
      'Analog zur Bewertung für eine Siegesposition des Spielers, _
          nur hier
      'Positiv für einen eigenen Sieg und je weiter oben desto höher
    ElseIf GameOver = "Unentschieden" Then
      'Wenn das Brett voll ist aber keiner gewinnt
      KI = 0
      'Schlechter als ein Sieg aber immer noch besser als eine _
          Niederlage
    Else
      For i = 0 To 2
        'Gehe jedes einzelne Feld auf dem Spielbrett durch
        For j = 0 To 2
          If Spielfeld(i, j) = "" Then
            'Wenn das Feld leer ist
            Spielfeld(i, j) = Spieler
            'Simuliere einen Zug
            TOTALSTONES = TOTALSTONES + 1
            
            If Spieler = "X" Then
              w = KI(Tiefe + 1, -10000, 10000, "O")
              'Hole die Wertung für den simulierten Zug
            Else
              w = KI(Tiefe + 1, -10000, 10000, "X")
            End If
            
            If Tiefe Mod 2 = 0 Then
              'Wenn dies ein Maxknoten ist
              If w > a Then
                a = w
                'Such den größten Wert der Folgeknoten
              End If
            Else
              'Wenn dies ein Minknoten ist
              If w < b Then
                b = w
                'Such den kleinsten Wert der Folgeknoten
              End If
            End If
            
            Spielfeld(i, j) = ""
            'Nimm den simulierten Zug zurück
            TOTALSTONES = TOTALSTONES - 1
            
          End If
        Next j
      Next i
      
      If Tiefe Mod 2 = 0 Then
        'Wenn dies ein Maxknoten ist
        KI = a
        'Gib das Maximum der Folgeknoten zurück
      Else
        'Wenn dies ein Minknoten ist
        KI = b
        'Gib das Minimum der Folgeknoten zurück
      End If
      
    End If
End Function
Private Sub ResetGame()
'Sichtbares und virtuelles Spielfeld werden entleert
  Dim i%, j%
    TOTALSTONES = 0
    For i = 0 To 2
      For j = 0 To 2
        Spielfeld(i, j) = ""
        Feld.TextMatrix(i, j) = ""
      Next j
    Next i
    Feld.Refresh
End Sub
Private Sub Form_Load()
'Hier wird nur das sichtbare Spielfeld initialisiert
  Dim i%
    For i = 0 To 2
      Feld.ColWidth(i) = 640
      Feld.RowHeight(i) = 640
    Next i
    SpielerZug = True
End Sub