Tic Tac Toe Spiel "KI" möglichkeiten

  • Hallo,
    Ich brauche einpar kleine geistigen anregungen für eine "Tic Tac Toe" KI (wenn man es überhuabut KI nennen darf).
    Also eben was für möglichkeiten es giebt dem PC Tic Tac Toe spielen bei zu bringen. :D

    Der gedanke war so das der PC immer gewinnt oder unentschieden spielt, eben den best möglichsten lösungsweg nimmt da giebt es bei tic tac toe ja nicht viele. ;)

    Die einfachste methode wehre mit IF abfragen alle möglichkeiten durch zu gehen das wehre halt sehr zeitaufwendig und nich sehr Elegant. :S

    Jetzt such ich halt nach weiteren wegen die nicht so aufwendig sind oder einen etwas interesanteren lösungsweg bieten. :D

    ich hoffe ihr könnt mir weiter helfen

    mfg Felix

    Bisheriges Spiel ohne "KI".

    Spoiler anzeigen
    [autoit]

    #include <ButtonConstants.au3>
    #include <GUIConstantsEx.au3>
    #include <WindowsConstants.au3>

    [/autoit] [autoit][/autoit] [autoit]

    #Region ### START GUI section ###

    [/autoit] [autoit][/autoit] [autoit]

    $Tic_Tac_Toe_Form = GUICreate("Tic Tac Toe", 400, 400, -1, -1)

    [/autoit] [autoit][/autoit] [autoit]

    Dim $Feld[9]
    $Feld_X = 25
    $Feld_Y = 25

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    For $A=0 to 8

    [/autoit] [autoit][/autoit] [autoit]

    $Feld[$A] = GUICtrlCreateButton("", $Feld_X, $Feld_Y, 100, 100)
    GUICtrlSetFont(-1, 72, 800, 0, "Comic Sans MS")

    [/autoit] [autoit][/autoit] [autoit]

    $Feld_X = $Feld_X+125

    [/autoit] [autoit][/autoit] [autoit]

    If $Feld_X = 400 Then
    $Feld_X = 25
    $Feld_Y = $Feld_Y+125
    EndIf

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Next

    [/autoit] [autoit][/autoit] [autoit]

    GUISetState(@SW_SHOW)

    [/autoit] [autoit][/autoit] [autoit]

    #EndRegion ### END GUI section ###

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Dim $Feld_Aktive [9]

    [/autoit] [autoit][/autoit] [autoit]

    For $B=0 to 8
    $Feld_Aktive[$B]=True
    Next

    [/autoit] [autoit][/autoit] [autoit]

    $Spieler = "X"

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    While 1
    $nMsg = GUIGetMsg()

    [/autoit] [autoit][/autoit] [autoit]

    For $B=0 to 8
    Switch $nMsg

    [/autoit] [autoit][/autoit] [autoit]

    Case $Feld[$B]
    If $Feld_Aktive[$B] Then

    [/autoit] [autoit][/autoit] [autoit]

    GUICtrlSetData($Feld[$B],_X_O())
    $Feld_Aktive[$B] = False
    GUICtrlSetState($Feld[$B],$GUI_DISABLE)

    [/autoit] [autoit][/autoit] [autoit]

    _Sieg_Pruefen("X")
    _Sieg_Pruefen("O")
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    Case $GUI_EVENT_CLOSE
    Exit

    [/autoit] [autoit][/autoit] [autoit]

    EndSwitch
    Next

    [/autoit] [autoit][/autoit] [autoit]

    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    Func _X_O ()

    [/autoit] [autoit][/autoit] [autoit]

    If $Spieler = "X" Then
    $Spieler = "O"
    Return "X"
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    If $Spieler = "O" Then
    $Spieler = "X"
    Return "O"
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    EndFunc

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Func _Sieg_Pruefen($Fuer)

    [/autoit] [autoit][/autoit] [autoit]

    If GUICtrlRead($Feld[0])=$Fuer And GUICtrlRead($Feld[1])=$Fuer And GUICtrlRead($Feld[2])=$Fuer Then
    MsgBox (1,"Sieg für "&$Fuer,$Fuer&" hat gewonnen!!!")
    Exit
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    If GUICtrlRead($Feld[3])=$Fuer And GUICtrlRead($Feld[4])=$Fuer And GUICtrlRead($Feld[5])=$Fuer Then
    MsgBox (1,"Sieg für "&$Fuer,$Fuer&" hat gewonnen!!!")
    Exit
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    If GUICtrlRead($Feld[6])=$Fuer And GUICtrlRead($Feld[7])=$Fuer And GUICtrlRead($Feld[8])=$Fuer Then
    MsgBox (1,"Sieg für "&$Fuer,$Fuer&" hat gewonnen!!!")
    Exit
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    If GUICtrlRead($Feld[0])=$Fuer And GUICtrlRead($Feld[3])=$Fuer And GUICtrlRead($Feld[6])=$Fuer Then
    MsgBox (1,"Sieg für "&$Fuer,$Fuer&" hat gewonnen!!!")
    Exit
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    If GUICtrlRead($Feld[1])=$Fuer And GUICtrlRead($Feld[4])=$Fuer And GUICtrlRead($Feld[5])=$Fuer Then
    MsgBox (1,"Sieg für "&$Fuer,$Fuer&" hat gewonnen!!!")
    Exit
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    If GUICtrlRead($Feld[2])=$Fuer And GUICtrlRead($Feld[5])=$Fuer And GUICtrlRead($Feld[8])=$Fuer Then
    MsgBox (1,"Sieg für "&$Fuer,$Fuer&" hat gewonnen!!!")
    Exit
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    If GUICtrlRead($Feld[0])=$Fuer And GUICtrlRead($Feld[4])=$Fuer And GUICtrlRead($Feld[8])=$Fuer Then
    MsgBox (1,"Sieg für "&$Fuer,$Fuer&" hat gewonnen!!!")
    Exit
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    If GUICtrlRead($Feld[6])=$Fuer And GUICtrlRead($Feld[4])=$Fuer And GUICtrlRead($Feld[2])=$Fuer Then
    MsgBox (1,"Sieg für "&$Fuer,$Fuer&" hat gewonnen!!!")
    Exit
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    EndFunc

    [/autoit]
    • Tic-tac-toe ist ein gelöstes Spiel, d.h. es gibt eine Strategie die immer zum Sieg führt (oder zu einem Unentschieden, wenn beide perfekt spielen). Auf Wikipedia ist diese Strategie sehr schön erklärt.
    • Brute-Force-Methode: Da es für Tic-tac-toe nicht allzu viele Möglichkeiten gibt kann man auch einfach alle möglichen Züge berechnen und dann anhand der daraus resultierenden Gewinne entscheiden, welcher Zug der langfristig beste ist. Das Ergebnis sollte zur perfekten Strategie eigentlich keinen Unterschied machen, es dauert nur um einiges länger. Wenn du den Spieler anfangen lässt ersparst du es dir aus den ersten 9 Möglichkeiten die richtige auszusuchen; bei 8 freien Feldern kann es einige Sekunden dauern. Alle weiteren Züge sollten ohne spürbare Zeitverzögerung funktionieren. Du kannst natürlich auch alles in einer Art Datenbank speichern, das lohnt sich aber denke ich nur für den ersten Zug.
    • Für ein Spiel wie Tic-tac-toe eigentlich vollkommen übertrieben, aber falls du es mit künstlicher Intelligenz machen willst bieten sich künstliche neuronale Netze, genetische Algorithmen oder eine Kombination der beiden an.
  • Das mit der "Brute-Force-Methode" kliengt interesant. Aber wie bekommt man es hin das ein programm alle möglichen züge berechnet?

    wie die Grafik von Wikipedia schon zeigt giebt es bei jedem weiteren zug immer neue möglichkeiten.
    Wie kann man so was in einem Programm realisieren.

    Ich brauch da einen kleinen ansatz sonst komm ich da einfach nicht weiter. ?(

    [Blockierte Grafik: http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Tic-tac-toe-game-tree.svg/545px-Tic-tac-toe-game-tree.svg.png]

  • Ausgerechnet die ineffizienteste Methode von den dreien.

    Du musst dazu nur jede Position auf dem Spielfeld rekursiv bewerten, d.h. jede Position hat einen Punktestand, der bei jedem Gewinn, der von dieser Position aus möglich ist, um 1 erhöht und bei jeder Niederlage um 1 gesenkt wird. Dazu eignet sich am besten eine Funktion die sich für jede freie Position selbst rekursiv aufruft. Ich weiß leider nicht wie ich das einfach genug erklären kann sodass es jemand der nicht ich ist versteht, von daher einfach ein bisschen probieren oder eine der anderen 2 Möglichkeiten versuchen. :D

  • Zitat

    Ich weiß leider nicht wie ich das einfach genug erklären kann sodass es jemand der nicht ich ist versteht.

    Schöner Satz James ^^

    Im Grunde musst du nur jede mögliche Spielsituation nachstellen und auswerten.
    Du hast für gewöhnlich ein Spielfeld[3][3] und die Ausgangssituation. Bei Spielbeginn ist das Feld ja komplett leer. Aber nach einigen Runden könnte das Feld folgendermaßen aussehen:

    * X *
    X O O
    * O X

    Die Frage ist nun, was ist der bestmögliche Zug in dieser Spielsituation? Ein gescheiter Mensch sieht das bestimmt direkt, jedoch geht es ja darum der KI dies klar zu machen. :)

    Dazu müssen erst alle Spielsituationen dargestellt und bewertet werden:

    Die letzte Zeile stellt dabei die Auswertung dar. Dabei wurden alle freien Felder (von der Spielsituation ausgehend) auf Sieg oder Niederlage bewertet. Alle Felder die zu einer Siegesreihe dazu gehören wurde mit + markiert, jedes Feld (in diesen Beispiel nicht dabei) welches zu Niederlagenreihe gehört mit – markiert. Zum Schluss werden alle Felder miteinander ausgewertet. Alle + und – zusammen gezählt und man erhält je nach Spielsituation die „Spielstärke“ des einzelnen Feldes.

    Dazu habe ich ein kleines Skript geschrieben. Die Funktion welche die KI darstellt arbeitet rekursiv (ruft sich selber auf) und stellt so jede Mögliche Spielsituation dar. Jedoch habe ich irgendwo einen Denkfehler eingebaut und die Feldpunkte werden nicht richtig vergeben. Darum kümmere ich mich aber noch. Es demonstriert aber wie solch eine KI in etwa realisierbar ist. Zeile 19 (ist auskommentiert) enthält die „Suchtiefe“. Diese kann man einstellen wenn man die Vorberechnungen der KI begrenzen möchte. Ziemlich praktisch um z.B. die Schwierigkeitsstufe einzustellen.

    Achja, das ganze lässt sich auch noch optimieren. Viele Spielsituationen sind ja einfach nur „gedreht“ oder „gespiegelt“. Aber ich hatte keine Lust das für ein so banales Spiel wie TicTacToe zu beachten. ^^

    Spoiler anzeigen
    [autoit]

    ; Hinweis: X ist immer Spieler, O stetig die KI

    [/autoit] [autoit][/autoit] [autoit]

    #include <Array.au3>
    Global $aPlan[3][3] = _
    [['', 'O', ''], _
    ['O', 'X', 'X'], _
    ['', 'X', 'O']]

    [/autoit] [autoit][/autoit] [autoit]

    _TTT_KI($aPlan)
    _ArrayDisplay($aPlan)

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Func _TTT_KI(ByRef $asField, $bPlayer = False)
    Static $iLevel, $aiPoints[3][3]
    Local $iX, $iY, $bWin, $aiCoord[3], $asCopy = $asField, $i

    [/autoit] [autoit][/autoit] [autoit]

    ; Suchtiefe festlegen
    ;~ If $iLevel = 5 Then Return

    [/autoit] [autoit][/autoit] [autoit]

    ; Prüfen ob Player im nächsten Zug gewinnen kann:
    If Not $iLevel Then
    For $iX = 0 To 2
    For $iY = 0 To 2
    If Not $asField[$iX][$iY] Then
    $asField[$iX][$iY] = 'X'

    [/autoit] [autoit][/autoit] [autoit]

    If _TTT_Win($asField, True) Then
    $asField[$iX][$iY] = 'O'
    Return
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    $asField = $asCopy
    EndIf
    Next
    Next

    [/autoit] [autoit][/autoit] [autoit]

    ; Punkte für kommende Spielbewertung neutralisieren:
    For $iX = 0 To 2
    For $iY = 0 To 2
    $aiPoints[$iX][$iY] = 0
    Next
    Next
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    ; Spielsituation bewerten:
    For $iX = 0 To 2
    For $iY = 0 To 2
    If Not $asField[$iX][$iY] Then
    $asField[$iX][$iY] = ($bPlayer ? 'X' : 'O')

    [/autoit] [autoit][/autoit] [autoit]

    If _TTT_Win($asField, $bPlayer) Then
    $aiPoints[$iX][$iY] += -1 ^ $bPlayer
    Return True
    Else
    $iLevel += 1
    $bWin = _TTT_KI($asField, Not $bPlayer)
    $iLevel -= 1

    [/autoit] [autoit][/autoit] [autoit]

    If $bWin Then $aiPoints[$iX][$iY] += -1 ^ $bPlayer
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    $asField = $asCopy
    EndIf
    Next
    Next

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ; Beste Spieloption auswählen:
    If Not $iLevel Then
    For $iX = 0 To 2
    For $iY = 0 To 2
    If $aiCoord[0] < $aiPoints[$iX][$iY] Then
    $aiCoord[0] = $aiPoints[$iX][$iY]
    $aiCoord[1] = $iX
    $aiCoord[2] = $iY
    EndIf
    Next
    Next
    _ArrayDisplay($aiPoints)
    $asField[$aiCoord[1]][$aiCoord[2]] = 'O'
    EndIf
    EndFunc

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ; Prüfe ob Player oder KI gewonnen hat:
    Func _TTT_Win(ByRef $asField, $bPlayer)
    Local $sPlayer = ($bPlayer ? 'X' : 'O')
    Local $i, $bWin

    [/autoit] [autoit][/autoit] [autoit]

    For $i = 0 To 2
    $bWin = ($bWin Or ($asField[$i][0] = $sPlayer And $asField[$i][1] = $sPlayer And $asField[$i][2] = $sPlayer))
    $bWin = ($bWin Or ($asField[0][$i] = $sPlayer And $asField[1][$i] = $sPlayer And $asField[2][$i] = $sPlayer))
    Next

    [/autoit] [autoit][/autoit] [autoit]

    $bWin = ($bWin Or ($asField[0][0] = $sPlayer And $asField[1][1] = $sPlayer And $asField[2][2] = $sPlayer))
    $bWin = ($bWin Or ($asField[0][2] = $sPlayer And $asField[1][1] = $sPlayer And $asField[2][0] = $sPlayer))

    [/autoit] [autoit][/autoit] [autoit]

    Return $bWin
    EndFunc

    [/autoit]

    2 Mal editiert, zuletzt von Yjuq (19. August 2014 um 01:17)