Minimax, Alpha-Beta und NegaScout: Spielbaumsuche im Vergleich

# Spielbaumsuche – Minimax, NegaMax, Alpha-Beta und NegaScout im Vergleich
# zu Kapitel 6 »Tic Tac Toe« aus »Coding for Fun mit Python«, portiert auf Python 3.
# MiniMax und NegaScout stehen so im Buch, NegaMax und Alpha-Beta
# stammen von der Buch-CD. Jede Klasse zählt in self.nodes die besuchten Stellungen.
import time
from c4f import Screen


class TicTacToe(object):
    def __init__(self, position="........."):
        self.field = [[0, 0, 0],
                      [0, 0, 0],
                      [0, 0, 0]]
        # »O« = Spieler 1 (Kreis), »X« = Spieler 2 (Kreuz), ».« = frei
        for i, sign in enumerate(position):
            self.field[i // 3][i % 3] = ".OX".index(sign)

    def evaluate(self):
        # kleine Verbesserung, um den schnellsten
        # Siegweg zu wählen, werden die Züge gezählt
        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:
            return 1
        return 2

    @property
    def sideToPlay(self):
        return self.getSide()

    def getMoves(self):
        moves = []
        if self.evaluate() == 0:
            for y in range(3):
                for x in range(3):
                    if self.field[y][x] == 0:
                        moves.append((x, y))

        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


class MiniMax(object):
    infinity = 200

    def __init__(self, gameObject):
        self.gameObject = gameObject
        self.nodes = 0

    def getEvaluatedMoves(self, depth):
        possibleMoves  = self.gameObject.getMoves()
        evaluatedMoves = []
        for move in possibleMoves:
            self.gameObject.makeMove(move)
            evaluation = self.explore(depth)
            self.gameObject.undoMove(move)
            evaluatedMoves.append((evaluation, move))

        evaluatedMoves.sort()
        return evaluatedMoves

    def explore(self, depth):
        if self.gameObject.getSide() == 1:
            return self.max(depth)
        else:
            return self.min(depth)

    def max(self, depth):
        self.nodes += 1
        alpha = -MiniMax.infinity
        moves = self.gameObject.getMoves()

        if depth <= 0 or not moves:
            return self.gameObject.evaluate()

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

        return alpha

    def min(self, depth):
        self.nodes += 1
        alpha = MiniMax.infinity
        moves = self.gameObject.getMoves()

        if depth <= 0 or not moves:
            return self.gameObject.evaluate()

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

        return alpha


class NegaMax(object):
    # die Bewertung darf nie größer als
    # der Vorgabewert für Unendlich werden
    infinity = 200

    def __init__(self, gameObject):
        self.gameObject = gameObject
        self.nodes = 0

    def getEvaluatedMoves(self, depth):
        possibleMoves  = self.gameObject.getMoves()
        evaluatedMoves = []
        for move in possibleMoves:
            self.gameObject.makeMove(move)
            evaluation = self.explore(depth - 1)
            self.gameObject.undoMove(move)
            evaluatedMoves.append((evaluation, move))

        evaluatedMoves.sort()
        return evaluatedMoves

    def explore(self, depth):
        self.nodes += 1
        alpha = -NegaMax.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()

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

        return alpha


class AlphaBetaPruning(NegaMax):
    # getEvaluatedMoves erbt die Klasse von NegaMax

    def explore(self, depth, alpha=-NegaMax.infinity, beta=+NegaMax.infinity):
        self.nodes += 1
        moves = self.gameObject.getMoves()

        if depth <= 0 or not moves:
            if self.gameObject.sideToPlay == 1:
                return +self.gameObject.evaluate()
            else:
                return -self.gameObject.evaluate()

        for move in moves:
            self.gameObject.makeMove(move)
            # aus Sicht des Gegners: aus (alpha, beta) wird (-beta, -alpha)
            value = -self.explore(depth - 1, -beta, -alpha)
            self.gameObject.undoMove(move)
            if value >= beta:
                # beta-»cut off«
                return beta
            if value > alpha:
                alpha = value

        return alpha


class NegaScout(NegaMax):
    # getEvaluatedMoves erbt die Klasse von NegaMax

    def explore(self, depth, alpha=-NegaMax.infinity, beta=+NegaMax.infinity):
        self.nodes += 1
        moves = self.gameObject.getMoves()

        if depth <= 0 or not moves:
            if self.gameObject.sideToPlay == 1:
                return +self.gameObject.evaluate()
            else:
                return -self.gameObject.evaluate()

        pvFound = False
        for move in moves:
            self.gameObject.makeMove(move)
            if pvFound:
                # suche mit kleinem Fenster starten
                value = -self.explore(depth - 1, -alpha - 1, -alpha)
                if value > alpha and value < beta:
                    # neue Hauptvariante gefunden,
                    # Suchlauf ist deshalb zu wiederholen
                    value = -self.explore(depth - 1, -beta, -alpha)
            else:
                value = -self.explore(depth - 1, -beta, -alpha)
            self.gameObject.undoMove(move)

            if value >= beta:
                # beta-»cut off«
                return beta
            if value > alpha:
                alpha = value
                pvFound = True

        return alpha


# --- der Vergleich ------------------------------------------------------------
algorithms = [("Minimax", MiniMax), ("NegaMax", NegaMax),
              ("Alpha-Beta", AlphaBetaPruning), ("NegaScout", NegaScout)]
positions  = [("Leeres Brett", "........."),
              ("Kreis in der Ecke", "O........"),
              ("Kreis droht", "O.X.O....")]


def compare(name, position, searchClass):
    game  = TicTacToe(position)
    side  = game.getSide()
    start = time.perf_counter()
    search = searchClass(game)
    evaluatedMoves = search.getEvaluatedMoves(9)
    duration = time.perf_counter() - start

    # alle Bewertungen aus Sicht dessen, der in der Stellung am Zug ist
    results = []
    for entry in evaluatedMoves:
        value, move = entry[0], entry[1]
        if searchClass is MiniMax:
            value = value if side == 1 else -value   # MiniMax: Sicht von Spieler 1
        else:
            value = -value                           # Nega…: Sicht des Gegners
        results.append((value, move))
    best = max(value for value, move in results)
    bestMoves = sorted(move for value, move in results if value == best)
    return {"name": name, "nodes": search.nodes, "seconds": duration,
            "best": best, "bestMoves": bestMoves, "all": sorted(results)}


def number(n):
    return f"{n:,}".replace(",", ".")


def seconds(s):
    return f"{s:.2f} s".replace(".", ",")


# --- Darstellung ----------------------------------------------------------------
W, H       = 640, 480
BACKGROUND = (16, 18, 24)
GRID       = (48, 53, 66)
TEXT       = (228, 231, 238)
MUTED      = (150, 157, 172)
COLORS     = [(239, 98, 108), (255, 159, 67), (72, 199, 116), (86, 156, 255)]
LEFT, RIGHT = 150, 545

screen = Screen(W, H, background=BACKGROUND, title="Spielbaumsuche")


def drawBoard(position, x, y, size):
    cell = size / 3
    for i in range(1, 3):
        screen.line((x + i * cell, y), (x + i * cell, y + size), GRID, 2)
        screen.line((x, y + i * cell), (x + size, y + i * cell), GRID, 2)
    for i, sign in enumerate(position):
        cx, cy = x + (i % 3 + 0.5) * cell, y + (i // 3 + 0.5) * cell
        r = cell * 0.3
        if sign == "O":
            screen.circle((cx, cy), r, (72, 199, 116), 3)
        elif sign == "X":
            screen.line((cx - r, cy - r), (cx + r, cy + r), (239, 98, 108), 3)
            screen.line((cx - r, cy + r), (cx + r, cy - r), (239, 98, 108), 3)


def drawChart(table, status):
    screen.clear()
    screen.text("Besuchte Stellungen bis zum Spielende", (20, 16), TEXT, size=20, bold=True)
    for i, (name, cls) in enumerate(algorithms):
        x = 20 + i * 150
        screen.rect(x, 50, 14, 14, COLORS[i])
        screen.text(name, (x + 20, 57), MUTED, size=15, baseline="middle")

    groupHeight = (H - 120) / len(positions)
    barHeight   = min(18, (groupHeight - 24) / len(algorithms))
    for p, (title, position) in enumerate(positions):
        top = 84 + p * groupHeight
        drawBoard(position, 20, top + 4, min(90, groupHeight - 30))
        screen.text(title, (LEFT, top), MUTED, size=14)
        rows = table.get(title, [])
        longest = max([row["nodes"] for row in rows] + [1])
        for i, row in enumerate(rows):
            y = top + 20 + i * (barHeight + 4)
            length = max(2, (RIGHT - LEFT) * row["nodes"] / longest)
            screen.rect(LEFT, y, length, barHeight, COLORS[i])
            label = f"{number(row['nodes'])} · {seconds(row['seconds'])}"
            screen.text(label, (LEFT + length + 6, y + barHeight / 2), TEXT, size=13, baseline="middle")

    screen.text(status, (20, H - 22), MUTED, size=15, baseline="middle")


table = {}
agree = True
for title, position in positions:
    table[title] = []
    print(f"\n{title} – {'Kreis' if TicTacToe(position).getSide() == 1 else 'Kreuz'} ist am Zug")
    print(f"{'Verfahren':<12}{'Stellungen':>12}{'Zeit':>10}  Bewertung  beste Züge")
    for name, searchClass in algorithms:
        drawChart(table, f"{title}: {name} rechnet …")
        await screen.frame()
        row = compare(name, position, searchClass)
        table[title].append(row)
        bestMoves = "alle gleich gut" if len(row["bestMoves"]) == len(row["all"]) else row["bestMoves"]
        print(f"{name:<12}{number(row['nodes']):>12}{seconds(row['seconds']):>10}  {row['best']:>9}  {bestMoves}")
        if row["all"] != table[title][0]["all"]:
            agree = False

print("\nAlle vier Verfahren kommen zu denselben Bewertungen:", "ja" if agree else "NEIN")
drawChart(table, "Fertig – alle vier Verfahren sind sich einig." if agree
          else "Achtung: Die Verfahren bewerten die Züge unterschiedlich!")
await screen.frame()