Leistungsoptimierung für den Minimax-Algorithmus in Tic-Tac-Toe mit variablen Boardgrößen und Gewinnbedingungen
Posted: 25 Jan 2025, 16:06
Ich implementieren ein Tic-Tac-Toe-Spiel mit einer KI, die den Minimax-Algorithmus (mit Alpha-Beta-Pruning) verwendet, um optimale Bewegungen auszuwählen. Ich erlebe jedoch Leistungsprobleme, wenn die Spielfeldgröße zunimmt oder die Anzahl der aufeinanderfolgenden Punkte, die zum Gewinnen erforderlich sind (k), zunimmt. Die aktuelle Implementierung funktioniert gut für kleinere Boardgrößen (z. B. 3x3), aber wenn ich die Boardgröße auf größere Raster (z. B. 8x12) skaliere, sinkt die Leistung erheblich, insbesondere mit der Tiefe der Suche.Der Algorithmus läuft auf größeren Boards (z. B. 6x6 oder 8x12) mit komplexeren Gewinnbedingungen (z. B. 4 in einer Reihe, 5 in einer Reihe) zu langsam Zeile).
Code: Select all
import random
import time
# Check if a player has won
def check_win(board, player, k):
rows = len(board)
cols = len(board[0])
# Check horizontally, vertically, and diagonally
for r in range(rows):
for c in range(cols):
if c