Tic Tac Toe in Python – Minimax-Algorithmus erklärt

Was du hier lernst

Spielbaum und Rekursion
Minimax und NegaMax
Bewertungsfunktion
Züge ausprobieren und zurücknehmen
Alpha-Beta-Suche
Klassen für Spiel, Suche und Oberfläche

So denkt der Computer

Tic Tac Toe hat so wenige Möglichkeiten, dass ein Computer jede einzelne Partie im Voraus durchspielen kann. Genau das tut dieses Programm vor jedem seiner Züge: Es probiert alle Züge aus, dann alle Antworten darauf, dann alle Antworten auf die Antworten – bis das Spiel entschieden ist. Aus diesem riesigen Spielbaum wählt es den Zug, der am Ende am besten ausgeht.

1. Das Spielfeld und wer am Zug ist

Das Brett ist eine Liste von drei Zeilen mit je drei Feldern: 0 heißt leer, 1 ist Spieler 1 (der grüne Kreis, du) und 2 ist Spieler 2 (das rote Kreuz, der Computer). Wer am Zug ist, muss sich das Programm nicht merken – es zählt einfach die belegten Felder:

if count % 2 == 0:
    player = 1
else:
    player = 2

Bei einer geraden Anzahl Steine ist Spieler 1 dran, sonst Spieler 2. Diese Funktion getSide() taucht später bei der Suche an einer entscheidenden Stelle wieder auf.

2. Eine Zahl für jede Stellung

Die Suche braucht ein Urteil: Wie gut ist eine Stellung? evaluate() prüft alle Reihen, Spalten und Diagonalen. Hat Spieler 1 drei in einer Reihe, gibt es einen positiven Wert, bei Spieler 2 einen negativen, sonst 0:

if self.field[0][i] == 1:
    return + 10 + moveCount
if self.field[0][i] == 2:
    return - 10 - moveCount

Der Zusatz moveCount zählt die noch freien Felder. Ein Sieg nach fünf Zügen ist damit mehr wert als einer nach neun – der Computer gewinnt so schnell wie möglich und verliert, wenn überhaupt, so spät wie möglich.

Ein Nullsummenspiel

Was der eine gewinnt, verliert der andere. Deshalb genügt eine einzige Zahl: Positiv ist gut für Spieler 1 und im selben Maß schlecht für Spieler 2. Auf dieser Eigenschaft baut der ganze Algorithmus auf.

3. Ausprobieren und zurücknehmen

Um in die Zukunft zu schauen, setzt die Suche einen Stein, bewertet, was passiert – und nimmt ihn wieder weg:

self.gameObject.makeMove(move)
evaluation = self.explore(depth - 1)
self.gameObject.undoMove(move)

Es gibt nur ein einziges Brett, die Suche spielt darauf vor und zurück. Das spart Speicher und ist schneller, als bei jedem Schritt ein neues Brett anzulegen.

4. Minimax: das Beste für mich, das Schlechteste für dich

Die Idee von Minimax: Wenn ich am Zug bin, wähle ich den Zug mit der besten Bewertung für mich (Maximum). Mein Gegner wählt danach den Zug, der für mich am schlechtesten ist (Minimum). Beide Schritte wechseln sich ab, bis das Spiel vorbei ist. So entsteht für jeden Zug eine Bewertung, die davon ausgeht, dass der Gegner perfekt spielt.

5. NegaMax: eine Funktion statt zwei

Das Buch verwendet eine elegante Abwandlung. Statt einer Funktion für Maximum und einer für Minimum gibt es nur explore: Sie bewertet jede Stellung aus Sicht dessen, der am Zug ist. Was für mich +10 ist, ist für den Gegner −10 – also dreht ein Minuszeichen die Sicht bei jeder Ebene um:

for move in moves:
    self.gameObject.makeMove(move)
    value = -self.explore(depth - 1)
    self.gameObject.undoMove(move)
    if value > alpha:
        alpha = value

Am Ende des Baums (keine Züge mehr oder Tiefe erreicht) liefert evaluate() die Zahl aus Sicht von Spieler 1. Ist Spieler 2 am Zug, dreht explore das Vorzeichen – dafür braucht es getSide().

6. Der beste Zug

getEvaluatedMoves bewertet jeden möglichen Zug und sortiert die Liste. Warum nimmt getBestMove dann den kleinsten Wert? Nach dem eigenen Zug ist der Gegner dran, und die Zahl sagt, wie gut es für ihn aussieht. Der kleinste Wert ist also der Zug, der dem Gegner am wenigsten Chancen lässt.

In der Konsole erscheinen alle bewerteten Züge als Tupel: Bewertung, Feld (x, y) und die Zahl der untersuchten Stellungen. Eine 0 bedeutet: Bei perfektem Spiel beider Seiten endet die Partie unentschieden.

7. Die Oberfläche

PlayingField zeichnet das Brett und nimmt Klicks entgegen. Aus der Pixelposition wird mit ganzzahliger Division das Feld:

x, y = (x - self.margin) // self.fieldWidth, (y - self.margin) // self.fieldHeight

Ein Rechtsklick – oder die Taste »Computer zieht« – tauscht die Rollen: Dann macht der Computer den nächsten Zug, auch den ersten einer Partie.

Warum der Computer nicht verliert

Tic Tac Toe ist bei fehlerfreiem Spiel beider Seiten immer unentschieden. Der Computer rechnet alles bis zum Ende durch und macht deshalb nie einen Fehler. Du kannst also höchstens ein Remis erreichen. Unter »Probier mal« lässt sich der Computer kurzsichtig machen – dann hast du eine Chance.

Vom Tic Tac Toe zum Schach

Schachprogramme arbeiten nach derselben Grundidee: Sie durchsuchen den Spielbaum mit Minimax und Alpha-Beta-Suche – nur viel tiefer und mit einer weit feineren Bewertung, denn Schach lässt sich nicht bis zum Ende durchrechnen. Wie sich so ein Gegner anfühlt, kannst du bei BobbyChess ausprobieren: Schach gegen eine KI im Stil von Bobby Fischer.

Probier mal

Jede Variante ändert den Code oben. Ein Klick auf »Ausprobieren« übernimmt die Änderung in den Editor und startet das Programm. »Zurücksetzen« holt das Original zurück.

01Alpha-Beta: derselbe Zug, viel schneller

Drück zuerst im Original auf »Computer zieht«, solange das Brett leer ist: Der Computer braucht mehrere Sekunden, weil er rund eine halbe Million Stellungen durchrechnet. Mit Alpha-Beta-Suche bricht er Zweige ab, sobald klar ist, dass der Gegner sie nie zulassen würde. Das Ergebnis ist exakt dasselbe – nach einem Bruchteil der Arbeit. Die dritte Zahl in der Konsole zeigt die untersuchten Stellungen pro Zug.

-     def explore(self, depth):
-         alpha = -NegaMax.infinity
-         moves = self.gameObject.getMoves()
+     def explore(self, depth, alpha=-infinity, beta=+infinity):
+         moves = self.gameObject.getMoves()
-             value = -self.explore(depth - 1)
-             self.gameObject.undoMove(move)
-             if value > alpha:
+             value = -self.explore(depth - 1, -beta, -alpha)
+             self.gameObject.undoMove(move)
+             if value >= beta:
+                 return beta  # Beta-Schnitt: das lässt der Gegner nie zu
+             if value > alpha:

02Abwechslung bei gleich guten Zügen

Oft sind mehrere Züge gleich gut – der Computer nimmt dann immer den ersten, und jede Partie verläuft gleich. Wie in einer späteren Fassung aus dem Buch wählt er jetzt zufällig unter allen besten Zügen.

- from c4f import Screen, sleep, MOUSEDOWN, KEYDOWN
+ import random
+ from c4f import Screen, sleep, MOUSEDOWN, KEYDOWN
-         bestMove = moves[0][1]
+         bestMoves = [m[1] for m in moves if m[0] == moves[0][0]]
+         bestMove = random.choice(bestMoves)

03Ein kurzsichtiger Gegner

getBestMove(9) lässt den Computer neun Halbzüge weit denken – also bis zum Spielende. Mit nur zwei Halbzügen sieht er noch, wo er gewinnen oder einen Sieg verhindern kann, aber keine Fallen. Jetzt ist er schlagbar: Baue eine Zwickmühle mit zwei offenen Reihen.
```
- bestMove = self.compObject.getBestMove(9)
+ bestMove = self.compObject.getBestMove(2)
```
04Mitzählen, wie viel gerechnet wird

Nach jedem Zug steht in der Konsole die Summe aller untersuchten Stellungen. Probiere es einmal mit dem Original und einmal zusammen mit der Alpha-Beta-Variante – der Unterschied ist gewaltig.
```
-         print('best move = ', bestMove)
+         print('best move = ', bestMove)
+         print('Stellungen untersucht:', sum(m[2] for m in moves))
```

Vom Buch in den Browser

Im Buch besteht das Spiel aus drei Dateien: ticTacToe.py (Spielregeln), negamax.py (Suche) und playingfield.py (Oberfläche mit pygame). Hier stehen sie in einer Datei. TicTacToe und NegaMax sind unverändert – nur print ist jetzt eine Funktion. Angepasst wurde die Oberfläche:

Im Buch (pygame)	Hier (c4f)
`pygame.draw.rect(self.screen, farbe, rect)`	`self.screen.rect(x, y, b, h, farbe)`
Ring: innere Ellipse in der Farbe von `self.screen.get_at(...)`	innere Ellipse in der Feldfarbe aus `fieldColor(x, y)`
`pygame.font.Font(None, 80).render(...)` + `blit`	`self.screen.text(msg, …, size=56)`
`time.sleep(1)`	`await sleep(1)`
`pygame.event.poll()`	`self.screen.events()`
Rechtsklick lässt den Computer ziehen	Rechtsklick oder Taste »Computer zieht«

Einige Details:

Ganzzahlige Division: In Python 2 lieferte sizeX / self.fieldsX eine ganze Zahl, in Python 3 eine Kommazahl. Als Listenindex wäre die unbrauchbar, deshalb steht dort jetzt //.
Pixel zurücklesen: pygame konnte die Farbe eines Pixels abfragen, um den Kreis innen wieder mit der Feldfarbe zu füllen. c4f zeichnet nur und liest nicht zurück, also berechnet fieldColor die Farbe direkt.
Warten: time.sleep würde Python anhalten, ohne dass der Browser das Brett zeigt. await sleep(...) wartet und zeigt dabei an.
Start: Das Original startete die Spielschleife schon im Konstruktor von PlayingField. Hier läuft sie über await fieldGUI.start().
psyco: Das Buch beschleunigte die Suche mit psyco, einem Just-in-time-Compiler für Python 2. Den gibt es für Python 3 nicht mehr. Die wirksamere Beschleunigung ist ohnehin algorithmisch – siehe die Alpha-Beta-Variante unter »Probier mal«.

Zu den Buch-Quellen gehören auch getunte Fassungen. Die Datei alphbetaprunning.py hätte sich so nicht importieren lassen: Der Standardwert -AlphaBetaPrunning.infinity verweist auf die Klasse, bevor sie existiert, und beim rekursiven Aufruf sind die Grenzen des Suchfensters vertauscht. Eingebunden war in der getunten Fassung NegaScout, eine verwandte Suche, die beides richtig macht. Die Alpha-Beta-Variante auf dieser Seite ist korrigiert.

Original aus dem Buch ansehen ticTacToe.py · Python 2

#coding: latin1

'''
Created on 14.04.2009

@author: Lars Heppert
'''

import psyco
psyco.log()
psyco.profile()

from playingfield import PlayingField
from negamax import NegaMax

class TicTacToe(object):
    def __init__(self):
        self.field = [[0, 0, 0],
                      [0, 0, 0],
                      [0, 0, 0]]
        self.newGame()

    def newGame(self):
        self.player = 1
#       has to be reset this way otherwise
#       it would be a new list which is not
#       referenced by playing field :-) 
        for y in range(3):
            for x in range(3):
                self.field[y][x] = 0
            
    def evaluate(self):
#       little improvement to chose fastest
#       win just count the open moves 
        moveCount = 0
        for y in range(3):
            for x in range(3):
                if self.field[y][x] == 0:
                    moveCount += 1
                    
        for i in range(3):
            if self.field[0][i] == self.field[1][i] == self.field[2][i]:
                if self.field[0][i] == 1:
                    return + 10 + moveCount
                if self.field[0][i] == 2:
                    return - 10 - moveCount
                
            if self.field[i][0] == self.field[i][1] == self.field[i][2]:
                if self.field[i][0] == 1:
                    return + 10 + moveCount
                if self.field[i][0] == 2:
                    return - 10 - moveCount
                
        if  (self.field[0][0] == self.field[1][1] == self.field[2][2]) or (self.field[0][2] == self.field[1][1] == self.field[2][0]):
            if self.field[1][1] == 1:
                return + 10 + moveCount
            if self.field[1][1] == 2:
                return - 10 - moveCount
            
        return 0
    
    def getSide(self):
        count = 0
        for y in range(3):
            for x in range(3):
                if self.field[y][x] != 0:
                    count += 1
                    
        if count % 2 == 0:
            player = 1
        else:
            player = 2
            
        return player
    
    def getMoves(self):
        moves = []
        if self.evaluate() == 0:
            for y in range(3):
                for x in range(3):
                    if self.field[y][x] == 0:
                        move = (x, y)
                        moves.append(move)
        
        return moves
    
    def makeMove(self, move):
        x, y = move
        self.field[y][x] = self.getSide()
        
    def undoMove(self, move):
        x, y = move
        self.field[y][x] = 0
        
    def checkGameState(self):
        # unbekannte Zustand als Initialwert
        state   = -1
        # aktuelle Postionsbewertung
        eval = self.evaluate()
        # sind noch Züge möglich?
        if not self.getMoves():
            # keine Züge mehr möglich
            state   = 0
        if eval > 0:
            # Spieler Nr. 1 hat gewonnen
            state   = 1
        if eval < 0:
            # Spieler Nr. 2 hat gewonnen
            state   = 2
            
        return state

if __name__ == '__main__':
    size        = 500, 500
    ticTacToe   = TicTacToe()
    negamax     = NegaMax(ticTacToe)
    fieldGUI    = PlayingField(size, ticTacToe, negamax)

Original aus dem Buch ansehen negamax.py · Python 2

'''
Created on 14.04.2009

@author: Lars Heppert
'''

class NegaMax(object):
#   the evaluation function has to be smaller
#   than the defined infinity value
    infinity = 200
    
    def __init__(self, gameObject):
        self.gameObject = gameObject
    
    def getEvaluatedMoves(self, depth):
        possibleMoves   = self.gameObject.getMoves()
        evaluatedMoves  = []
        for move in possibleMoves:
            self.gameObject.makeMove(move)
            self.treeNodeCounter = 0
            evaluation = self.explore(depth-1)
            self.gameObject.undoMove(move)
            evaluatedMoves.append((evaluation, move, self.treeNodeCounter))
        
        evaluatedMoves.sort()
        return evaluatedMoves
        
    def getBestMove(self, depth):
        moves = self.getEvaluatedMoves(depth)
        print '\nEvaluated Moves:'
        for move in moves:
            print move
        print '----------------'
        bestMove = moves[0][1]
        print 'best move = ', bestMove
        return bestMove        
    
    def explore(self, depth):
        alpha = -NegaMax.infinity        
        moves = self.gameObject.getMoves()

        if depth <= 0 or not moves:
            if self.gameObject.getSide() == 1:
                return +self.gameObject.evaluate()
            else:
                return -self.gameObject.evaluate()
        
        self.treeNodeCounter += 1
        for move in moves:
            self.gameObject.makeMove(move)
            value = -self.explore(depth-1)
            self.gameObject.undoMove(move)
            if value > alpha:
                alpha = value
                
        return alpha

Original aus dem Buch ansehen playingfield.py · Python 2

'''
Created on 18.04.2009

@author: Lars Heppert
'''

import pygame
import time
pygame.init()

class PlayingField(object):
    def __init__(self, size, gameObject, compObject):
        self.gameObject     = gameObject
        self.compObject     = compObject
        self.computerSide   = 2
        sizeX, sizeY        = size
        self.field          = self.gameObject.field
        self.fieldsY        = len(self.field)
        self.fieldsX        = len(self.field[0])
        self.fieldWidth     = sizeX / self.fieldsX
        self.fieldHeight    = sizeY / self.fieldsY
        self.margin         = 50
        self.padding        = 30
        self.seperator      = 5
        self.size           = sizeX+self.margin*2, sizeY+self.margin*2
        self.screen         = pygame.display.set_mode(self.size)
        self.running        = True
        self.start()
        
    def drawRect(self, position, color, size=(10, 10)):
        x, y            = position
        width, height   = size
        rect            = (x, y, width, height)
        pygame.draw.rect(self.screen, color, rect)
        
    def drawField(self):
        for y in range(self.fieldsY):
            for x in range(self.fieldsX):
                position    = (self.margin+x*self.fieldWidth,
                               self.margin+y*self.fieldHeight)
                size        = (self.fieldWidth-self.seperator,
                               self.fieldHeight-self.seperator)
                if (y*3+x) % 2 == 0:
                    color = 0, 0, 140
                else:
                    color = 0, 0, 220
                self.drawRect(position, color, size)
                if (self.field[y][x] != 0):
                    self.drawPlayerSign(position, self.field[y][x])
                    
    def drawPlayerSign(self, startPosition, player):
        startX, startY  =   startPosition
        startPosition   =  (startX+self.padding,
                            startY+self.padding)
        endPosition     =  (startX+self.fieldWidth-self.padding,
                            startY+self.fieldHeight-self.padding)
        if player == 1:
            self.drawPlayerOne(startPosition, endPosition)
        else:
            self.drawPlayerTwo(startPosition, endPosition)
            
    def drawPlayerOne(self, startPosition, endPosition):
        x1, y1      = startPosition
        x2, y2      = endPosition
        x2, y2      = x2-x1, y2-y1
        rect        = x1, y1, x2, y2
        innerRect   = x1+15, y1+15, x2-30, y2-30
        color       = 0, 180, 0
        backColor   = self.screen.get_at(startPosition)
        pygame.draw.ellipse(self.screen, color, rect, 0)
        pygame.draw.ellipse(self.screen, backColor, innerRect, 0)    
            
    def drawPlayerTwo(self, startPosition, endPosition):
        color       = 180, 0, 0
        width       = 20
        adjustion   = 10
        startX, startY  = startPosition
        endX, endY      = endPosition
        startPosition   = startX+adjustion, startY+adjustion
        endPosition     = endX-adjustion, endY-adjustion
        pygame.draw.line(self.screen, color, startPosition, endPosition, width)
        startX, startY  = startPosition
        startX, startY  = (startX-self.padding-adjustion,
                           startY-self.padding-adjustion)
        startPosition   = (startX+self.padding+adjustion,
                           startY+self.fieldHeight-self.padding-adjustion)
        endPosition     = (startX+self.fieldWidth-self.padding-adjustion,
                           startY+self.padding+adjustion)
        pygame.draw.line(self.screen, color, startPosition, endPosition, width)
        
    def makeHumanMove(self, position, button):
        x, y    = position
        if x > self.margin and y > self.margin:
            x, y    = (x-self.margin)/self.fieldWidth, (y-self.margin)/self.fieldHeight
            if len(self.field) > y and len(self.field[0]) > x:
                move = x, y
                if button == 3:
#                   switch sides and let the computer move 
                    self.computerSide = self.gameObject.getSide()
                    self.makeCompMove()
                elif move in self.gameObject.getMoves():
#                   the human makes his move alone
#                   so we first check if its a possible move ;-) 
                    self.gameObject.makeMove(move)
                    self.checkForResult()
                        
    def makeCompMove(self):
        bestMove = self.compObject.getBestMove(9)
        self.gameObject.makeMove(bestMove)
        self.checkForResult()
         
    def checkForResult(self):
        state = self.gameObject.checkGameState()
        if state != -1:
#           show current position for 1 seconds 
            self.refresh()
            time.sleep(1)
#           the computer should not start
            self.computerSide = 2
            self.gameObject.newGame()
#           show the winner of the game 
            self.screen.fill((0, 0, 0))
            if state == 1:
                msg = 'Player 1 won!'
            elif state == 2:
                msg = 'Player 2 won!'
            elif state == 0:
                msg = 'The Game is drawn'
                
            font = pygame.font.Font(None, 80)
            # Render the text
            text = font.render(msg, True, (255, 255, 255), (159, 182, 205))
            # Create a rectangle
            textRect = text.get_rect()
            # Center the rectangle
            textRect.centerx = self.screen.get_rect().centerx
            textRect.centery = self.screen.get_rect().centery
            # Blit the text
            self.screen.blit(text, textRect)                
            pygame.display.flip()    
            time.sleep(2)
                
    def refresh(self):
        self.screen.fill((0, 0, 0))
        self.drawField()                
        pygame.display.flip()
        
    def start(self):
        while self.running:
#           draw current playing field 
            self.refresh()
#           does the computer has to play? 
            if self.gameObject.getSide() == self.computerSide:
                self.makeCompMove()
            else:
#               the human has to play! 
                event = pygame.event.poll()
                if event.type == pygame.QUIT:
                    self.running = False
                elif event.type == pygame.MOUSEBUTTONDOWN:
                    self.makeHumanMove(event.pos, event.button)
                    
    def stop(self):
        self.running = False

Original aus dem Buch ansehen alphbetaprunning.py · Python 2

'''
Created on 19.04.2009

@author: Lars Heppert
'''

class AlphaBetaPrunning(object):
#   the evaluation function has to be smaller
#   than the defined infinity value
    infinity = 200
    
    def __init__(self, gameObject):
        self.gameObject = gameObject
    
    def getEvaluatedMoves(self, depth):
        possibleMoves   = self.gameObject.getMoves()
        evaluatedMoves  = []
        for move in possibleMoves:
            self.gameObject.makeMove(move)
            self.treeNodeCounter = 0
            evaluation = self.explore(depth-1)
            self.gameObject.undoMove(move)
            evaluatedMoves.append((evaluation, move, self.treeNodeCounter))
        
        evaluatedMoves.sort()
        return evaluatedMoves
        
    def getBestMove(self, depth):
        moves = self.getEvaluatedMoves(depth)
        print '\nEvaluated Moves:'
        for move in moves:
            print move
        print '----------------'
        bestMove = moves[0][1]
        print 'best move = ', bestMove
        return bestMove        
    
    def explore(self, depth,
                alpha   =   -AlphaBetaPrunning.infinity,
                beta    =   +AlphaBetaPrunning.infinity):
        
        moves = self.gameObject.getMoves()
        if depth <= 0 or not moves:
            if self.gameObject.sideToPlay == 1:
                return +self.gameObject.evaluate()
            else:
                return -self.gameObject.evaluate()
        
        self.treeNodeCounter += 1
        for move in moves:
            self.gameObject.makeMove(move)
            value = -self.explore(depth-1, -alpha, -beta)
            self.gameObject.undoMove(move)
            if value >= beta:
#               beta cut off 
                return beta
            if value > alpha:
                alpha = value
                
        return alpha

Was du hier lernst

So denkt der Computer

1. Das Spielfeld und wer am Zug ist

2. Eine Zahl für jede Stellung

3. Ausprobieren und zurücknehmen

4. Minimax: das Beste für mich, das Schlechteste für dich

5. NegaMax: eine Funktion statt zwei

6. Der beste Zug

7. Die Oberfläche

Probier mal

01Alpha-Beta: derselbe Zug, viel schneller

02Abwechslung bei gleich guten Zügen

03Ein kurzsichtiger Gegner

04Mitzählen, wie viel gerechnet wird

Vom Buch in den Browser

Passt dazu

Genetischer Algorithmus

Snake

Ziegenproblem