Kurze Zusammenfassung wie ein Schachbot funktioniert: Der gezeigte Bot verwendet den Minimax-Algorithmus (Implementierung in JavaScript).
1. Bewertungsfunktion: Der Bot bewertet den Zustand des Schachbretts anhand einer numerischen Bewertung. Positive Werte signalisieren Vorteile für den Bot, negative Werte einen Vorteil des Gegners.
2. Suchbaumgenerierung: Der Bot erstellt einen Suchbaum mit allen möglichen Zügen bis zu einer bestimmten Tiefe. Jeder Knoten repräsentiert einen Zug, die Blätter sind Endpositionen nach einer bestimmten Zuganzahl.
3. Minimax-Algorithmus: Der Bot wendet den Minimax-Algorithmus auf den Suchbaum an, indem er zwischen den Rollen des Maximizer (Bot) und Minimizer (Gegner) wechselt. Der Maximizer strebt den höchsten Bewertungswert an, der Minimizer den niedrigsten.
4. Rekursive Bewertung: Der Bot bewertet die Blatt-Positionen im Suchbaum mithilfe der Bewertungsfunktion. Die Bewertungen werden entlang des Baums zurückverfolgt, wobei der Maximizer den höchsten Wert und der Minimizer den niedrigsten Wert auswählt.
5. Entscheidungsfindung: Der Bot wählt den Zug, der zur am besten bewerteten Position führt, als besten Zug aus und führt ihn aus.

Damit ein Schachbot funktionieren kann, muss man ihm als erstes ein paar Daten zur Verfügung stellen: Wert der Figuren und Wert der Position der Figur.
Die Werte der einzelnen Figuren habe ich wie folgt definiert:
var pieceValues = { 1: 100, // Bauer 3: 280, // Springer 4: 320, // Läufer 2: 479, // Turm 5: 929, // Dame 6: 60000 // König (eine hohe Bewertung, um die Sicherheit des Königs zu betonen) };

Zum Verständnis ist hier das Schachbrett am Start einer Partie. Jede positive Zahl repräsentiert eine andere weiße Figur (die negativen Zahlen repräsentieren die schwarzen Figuren). Die 0 repräsentiert ein leeres Feld:
var testboard = [ [-2, -3, -4, -5, -6, -4, -3, -2], [-1, -1, -1, -1, -1, -1, -1, -1], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1], [2, 3, 4, 5, 6, 4, 3, 2] ];
Weiter braucht jede Figur die Bewertung der aktuellen Position. Für den König gibt es zwei Tabellen. Die zweite ist für das Endspiel und noch nicht implementiert in den weiteren Code. Hierbei soll der König versuchen, in der Mitte des Spielbretts zu bleiben, um nicht Schachmatt gesetzt zu werden:
var pst_w = { 1:[ [ 100, 100, 100, 100, 105, 100, 100, 100], [ 78, 83, 86, 73, 102, 82, 85, 90], [ 7, 29, 21, 44, 40, 31, 44, 7], [ -17, 16, -2, 15, 14, 0, 15, -13], [ -26, 3, 10, 9, 6, 1, 0, -23], [ -22, 9, 5, -11, -10, -2, 3, -19], [ -31, 8, -7, -37, -36, -14, 3, -31], [ 0, 0, 0, 0, 0, 0, 0, 0] ], 3: [ [-66, -53, -75, -75, -10, -55, -58, -70], [ -3, -6, 100, -36, 4, 62, -4, -14], [ 10, 67, 1, 74, 73, 27, 62, -2], [ 24, 24, 45, 37, 33, 41, 25, 17], [ -1, 5, 31, 21, 22, 35, 2, 0], [-18, 10, 13, 22, 18, 15, 11, -14], [-23, -15, 2, 0, 2, 0, -23, -20], [-74, -23, -26, -24, -19, -35, -22, -69] ], 4: [ [-59, -78, -82, -76, -23,-107, -37, -50], [-11, 20, 35, -42, -39, 31, 2, -22], [ -9, 39, -32, 41, 52, -10, 28, -14], [ 25, 17, 20, 34, 26, 25, 15, 10], [ 13, 10, 17, 23, 17, 16, 0, 7], [ 14, 25, 24, 15, 8, 25, 20, 15], [ 19, 20, 11, 6, 7, 6, 20, 16], [ -7, 2, -15, -12, -14, -15, -10, -10] ], 2: [ [ 35, 29, 33, 4, 37, 33, 56, 50], [ 55, 29, 56, 67, 55, 62, 34, 60], [ 19, 35, 28, 33, 45, 27, 25, 15], [ 0, 5, 16, 13, 18, -4, -9, -6], [-28, -35, -16, -21, -13, -29, -46, -30], [-42, -28, -42, -25, -25, -35, -26, -46], [-53, -38, -31, -26, -29, -43, -44, -53], [-30, -24, -18, 5, -2, -18, -31, -32] ], 5: [ [ 6, 1, -8,-104, 69, 24, 88, 26], [ 14, 32, 60, -10, 20, 76, 57, 24], [ -2, 43, 32, 60, 72, 63, 43, 2], [ 1, -16, 22, 17, 25, 20, -13, -6], [-14, -15, -2, -5, -1, -10, -20, -22], [-30, -6, -13, -11, -16, -11, -16, -27], [-36, -18, 0, -19, -15, -15, -21, -38], [-39, -30, -31, -13, -31, -36, -34, -42] ], 6: [ [ 4, 54, 47, -99, -99, 60, 83, -62], [-32, 10, 55, 56, 56, 55, 10, 3], [-62, 12, -57, 44, -67, 28, 37, -31], [-55, 50, 11, -4, -19, 13, 0, -49], [-55, -43, -52, -28, -51, -47, -8, -50], [-47, -42, -43, -79, -64, -32, -29, -32], [ -4, 3, -14, -50, -57, -18, 13, 4], [ 17, 30, -3, -14, 6, -1, 40, 18] ], // Endgame Königtabelle noch nicht integriert 7: [ [-50, -40, -30, -20, -20, -30, -40, -50], [-30, -20, -10, 0, 0, -10, -20, -30], [-30, -10, 20, 30, 30, 20, -10, -30], [-30, -10, 30, 40, 40, 30, -10, -30], [-30, -10, 30, 40, 40, 30, -10, -30], [-30, -10, 20, 30, 30, 20, -10, -30], [-30, -30, 0, 0, 0, 0, -30, -30], [-50, -30, -30, -30, -30, -30, -30, -50] ] };
Bei genauerer Betrachtung werden einem die Werte klar. Ein Pferd sollte sich möglichst in der Mitte des Spielfeldes befinden, um möglichst viele Felder zu bedrohen. Ein Bauer sollte möglichst weit nach vorne gelangen, damit er sich umwandeln kann.
Nun drehen wir die Bewertung um, da der schwarze Bauer in die andere Richtung laufen muss:
var pst_b = { 1: pst_w[1].slice().reverse(), 3: pst_w[3].slice().reverse(), 4: pst_w[4].slice().reverse(), 2: pst_w[2].slice().reverse(), 5: pst_w[5].slice().reverse(), 6: pst_w[6].slice().reverse(), 7: pst_w[7].slice().reverse() }
Da wir nun alle Daten für die Bewertung des Spielbretts haben, können wir die Bewertungsfunktion evaluateBoard(board) schreiben. Hierbei gehen wir alle Felder durch und bewerten die Figur auf dem Feld. Diese Werte werden dann für Schwarz und Weiß jeweils addiert und am Ende subtrahiert, um den Endwert des Spielbretts darzustellen:
function evaluateBoard(board) { let white = 0; let black = 0; for(let i=0; i<8; i++) { for(let j=0; j<8; j++) { let figure = board[i][j]; if(figure !== 0) { if(figure > 0) { white = white + pieceValues[figure] + pst_w[figure][i][j]; } else { black = black + pieceValues[figure*(-1)] + pst_b[figure*(-1)][i][j]; } } } } return white-black; }
Da wir nun ein Spielbrett bewerten können, müssen wir nun alle Züge generieren, diese bewerten und den besten Zug finden. Bevor wir zu dem schwierigen Teil kommen, schreiben wir die Zuggenerierung generateEveryMove(board, player).
Bei dieser Funktion gehen wir ähnlich wie bei der Spielbrettbewertung vor. Wir gehen jedes Feld durch und generieren für die darauf stehende Figur die möglichen Züge:
function generateEveryMove(board, player) { let moves = []; // Iteriere über das gesamte Spielbrett for (let row = 0; row < 8; row++) { for (let col = 0; col < 8; col++) { // Überprüfe, ob das Feld vom aktuellen Spieler besetzt ist if (board[row][col] * player > 0) { let piece = Math.abs(board[row][col]); let pieceMoves = []; // Generiere Züge basierend auf dem Spielstein switch (piece) { case 1: // Pawn pieceMoves = generatePawnMoves(board, row, col, player); break; case 3: // Knight pieceMoves = generateKnightMoves(board, row, col, player); break; case 4: // Bishop pieceMoves = generateBishopMoves(board, row, col, player); break; case 2: // Rook pieceMoves = generateRookMoves(board, row, col, player); break; case 5: // Queen pieceMoves = generateQueenMoves(board, row, col, player); break; case 6: // King pieceMoves = generateKingMoves(board, row, col, player); break; } // Füge die generierten Züge der Gesamtliste hinzu moves.push(...pieceMoves); } } } return moves; }
Jetzt kommen wir zu einem interessantem Part. Wir definieren die Funktionen generatePawnMoves(), generateKnightMoves(), generateBishopMoves(), generateRookMoves(), generateQueenMoves() und generateKingMoves().
Hierfür benötigen wir noch eine kleine Extrafunktion, die überprüft, ob man auf das Feld ziehen darf oder nicht:
function isValidSquare(row, col) { return row >= 0 && row < 8 && col >= 0 && col < 8; }
Nun starten wir mit der Funktion generatePawnMoves(). Ein kleiner Hinweis zum Output. Es wird ein Array zurückgegeben, der wie folgt aussieht:
[Art des Zuges, aktuelle Reihe, aktuelle Spalte, neue Reihe, neue Spalte]
Bei dieser Funktion fehlt noch die Implementierung von en Passant und die Umwandlung von Bauer in eine andere Figur beim Erreichen der letzten Reihe:
function generatePawnMoves(board, row, col, player) { const moves = []; const direction = player > 0 ? -1 : 1; // Richtung abhängig vom Spieler // Einzelner Schritt vorwärts const newRow = row + direction; if (isValidSquare(newRow, col) && board[newRow][col] === 0) { moves.push(['move',row, col, newRow, col]); } // Doppeltes Schritt vorwärts von der Startposition const startRow = player > 0 ? 6 : 1; // Startreihe abhängig vom Spieler if (row === startRow && board[startRow + direction][col] === 0 && board[startRow + 2*direction][col] === 0) { moves.push(['move', row, col, startRow + 2 * direction, col]); } // Schläge auf diagonale Felder const captureMoves = [[row + direction, col - 1], [row + direction, col + 1]]; for (const [captureRow, captureCol] of captureMoves) { if (isValidSquare(captureRow, captureCol) && board[captureRow][captureCol] * player < 0) { moves.push(['move', row, col, captureRow, captureCol]); } } // TODO: Implementierung für en passant und Bauernumwandlung return moves; }
Hier ist der Code der Funktion generateKnightMoves():
function generateKnightMoves(board, row, col, player) { const moves = []; const offsets = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]]; for (const [offsetRow, offsetCol] of offsets) { const targetRow = row + offsetRow; const targetCol = col + offsetCol; if (isValidSquare(targetRow, targetCol) && board[targetRow][targetCol] * player <= 0) { moves.push(['move', row, col, targetRow, targetCol]); } } return moves; }
Bevor wir zu den Funktionen generateBishopMoves(), generateRookMoves() und generateQueenMoves kommen, wenden wir uns der Funktion generateKingMoves() zu, da die drei Funktionen in einer Funktion vereinfacht werden können:
function generateKingMoves(board, row, col, player) { const moves = []; const offsets = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]; for (const [offsetRow, offsetCol] of offsets) { const targetRow = row + offsetRow; const targetCol = col + offsetCol; if (isValidSquare(targetRow, targetCol) && board[targetRow][targetCol] * player <= 0) { moves.push(['move', row, col, targetRow, targetCol]); } } // Generiere Rochade-Züge if (Math.abs(board[row][4]) === 6) { //König auf position if (Math.abs(board[row][7]) === 2) { if (board[row][5] === 0 && board[row][6] === 0) { moves.push(['castle', row, col, row, col + 2]); // Kurze Rochade } } if (Math.abs(board[row][0]) === 2) { if (board[row][1] === 0 && board[row][2] === 0 && board[row][3] === 0) { moves.push(['castle', row, col, row, col - 2]); // Lange Rochade } } } return moves; }
Hier sind die drei Funktionen generateBishopMoves(), generateRookMoves() und generateQueenMoves. Wie ihr seht beziehen sich die drei Funktionen auf die Funktion generateSlidingMoves(). Als Parameter wird der Funktion das Bewegungsmuster übergeben:
function generateBishopMoves(board, row, col, player) { return generateSlidingMoves(board, row, col, player, [[-1, -1], [-1, 1], [1, -1], [1, 1]]); } function generateRookMoves(board, row, col, player) { return generateSlidingMoves(board, row, col, player, [[-1, 0], [1, 0], [0, -1], [0, 1]]); } function generateQueenMoves(board, row, col, player) { return generateSlidingMoves(board, row, col, player, [[-1, -1], [-1, 1], [1, -1], [1, 1], [-1, 0], [1, 0], [0, -1], [0, 1]]); }
Das Bewegungsmuster sagt aus, wie sich die Figur um einen Wert bewegen. Ein Beispiel für den Turm:
Es verändert sich immer nur um einen Wert, wobei der zweite Wert 0 bleibt, d.h. der Turm bewegt sich entweder nach vorne, hinten, links oder rechts und nie diagonal. So kann einfach mit den einzelnen Arrays multipliziert werden. Wie ihr im Code sehen werdet:
function generateSlidingMoves(board, row, col, player, directions) { const moves = []; for (const [offsetRow, offsetCol] of directions) { let targetRow = row + offsetRow; let targetCol = col + offsetCol; while (isValidSquare(targetRow, targetCol)) { if (board[targetRow][targetCol] * player <= 0) { moves.push(['move', row, col, targetRow, targetCol]); if (board[targetRow][targetCol] * player < 0) { break; } } else { break; } targetRow += offsetRow; targetCol += offsetCol; } } return moves; }
Nun können wir jeden Zug generieren und jedes Spielbrett bewerten. Bevor wir zu dem Minimax-Algorithmus kommen, schreiben wir zwei kleine letzte Funktionen. Einmal eine Funktion isGameOver(board), die überprüft, ob das Spiel vorbei ist, und eine Funktion, die einen Zug macht namens makeMove(board, move). Ihr genauer Verwendungszweck wird im Laufe der Erklärung des Minimax-Algorithmus deutlich.

Die Funktion isGameOver(board):
function isGameOver(board) { // Überprüfe auf spezifische Bedingungen, die auf ein Spielende hinweisen // Beispiel: Wenn keine Könige mehr auf dem Brett sind, ist das Spiel beendet let whiteKingExists = false; let blackKingExists = false; for (let row = 0; row < 8; row++) { for (let col = 0; col < 8; col++) { let piece = board[row][col]; if (piece === 6) { whiteKingExists = true; } else if (piece === -6) { blackKingExists = true; } } } return !whiteKingExists || !blackKingExists; }und die Funktion makeMove(board, move):
function makeMove(board, move) { const [ability, startRow, startCol, endRow, endCol] = move; // Kopie des Schachbretts erstellen const newBoard = JSON.parse(JSON.stringify(board)); // Figur vom Startplatz zum Endplatz bewegen if(ability === "move") { const piece = newBoard[startRow][startCol]; newBoard[startRow][startCol] = 0; newBoard[endRow][endCol] = piece; } else if(ability === "castle") { newBoard[endRow][endCol] = newBoard[startRow][startCol]; newBoard[startRow][startCol] = 0; if(endCol === 6) { newBoard[startRow][5] = newBoard[startRow][7]; newBoard[startRow][7] = 0; } else { newBoard[startRow][3] = newBoard[startRow][0]; newBoard[startRow][0] = 0; } } return newBoard; }
Der Minimax-Algorithmus:
Der Minimax-Algorithmus ist ein Entscheidungsverfahren, das in Spielen mit gegnerischen Parteien eingesetzt wird, wie zum Beispiel Schach. Das Ziel des Minimax-Algorithmus ist es, die bestmögliche Entscheidung für den Spieler zu treffen, indem er die möglichen Züge in einem Spielbaum analysiert.

Der Algorithmus basiert auf der Annahme, dass der Gegner immer den für den Spieler ungünstigsten Zug wählt, während der Spieler selbst versucht, den für ihn vorteilhaftesten Zug auszuwählen. Das bedeutet, dass der Algorithmus abwechselnd die Rolle des Maximizers und des Minimizers einnimmt.

Der Maximierer (der Spieler) bewertet alle möglichen Züge und wählt den Zug mit der höchsten Bewertung aus. Der Minimierer (der Gegner) bewertet wiederum alle möglichen Gegenzüge und wählt den Zug mit der niedrigsten Bewertung aus. Dieser Prozess wird rekursiv fortgesetzt, indem der Algorithmus den Spielbaum in der Tiefe durchsucht.

Der Minimax-Algorithmus nimmt an, dass beide Spieler perfekt spielen und immer die besten Züge wählen. Das bedeutet, dass der Algorithmus alle möglichen Spielverläufe betrachtet und die beste Entscheidung basierend auf den Bewertungen der Endpositionen trifft.

Am Ende liefert der Minimax-Algorithmus den besten Zug für den Spieler unter der Annahme, dass der Gegner optimal spielt. Es ist jedoch wichtig zu beachten, dass der Minimax-Algorithmus im Schach aufgrund der enormen Anzahl von möglichen Zügen und Positionen nicht praktikabel ist. Daher wenden wir die Optimierung Alpha-Beta-Pruning an, um die Anzahl der zu bewertenden Positionen zu reduzieren.

Um diese Erklärung zu veranschaulichen, ist hier ein Beispiel.

Beispiel:
Hierbei folgende Situation:


Nun stellen wir ein Spielbaum mit der Tiefe 2 auf:


Hier lässt sich schnell erkennen, welcher Zug der Beste für Weiß ist. Weiter werden auf der zweiten Ebene die Züge für Schwarz dargestellt. Hier würde der Algorithmus den schlechtesten für den Spieler bzw. den besten Zug für Schwarz erwarten. Falls man nun einen tieferen Baum haben möchte, muss man aus jedem Zug jeden weiteren Zug generieren. Somit brauchen wir mehr Rechenleistung und die Berechnung dauert länger. Hierbei kommt der Alpha-Beta-Pruning-Algorithmus zum Einsatz.

Der Alpha-Beta-Pruning-Algorithmus:
Der Algorithmus verändert das Ergebnis nicht, sondern ermöglicht es, unnötige Berechnungen zu vermeiden und die Anzahl der zu betrachtenden Spielzustände zu reduzieren.

Der Algorithmus verwendet zwei Parameter: Den Alpha-Wert und den Beta-Wert. Der Alpha-Wert repräsentiert den besten Wert, den der Maximizer bisher gefunden hat, während der Beta-Wert den besten Wert darstellt, den der Minimizer bisher gefunden hat.

Der Algorithmus durchläuft den Suchbaum rekursiv und wendet dabei eine Technik des Abschneidens an. Wenn der Maximizer einen Zug findet, der zu einem besseren Alpha-Wert führt, wird dieser Wert aktualisiert. Wenn der Minimizer einen Zug findet, der zu einem besseren Beta-Wert führt, wird dieser Wert aktualisiert.

Während der Suche werden bestimmte Zweige des Suchbaums abgeschnitten, wenn festgestellt wird, dass sie keinen Einfluss auf das Endergebnis haben. Das bedeutet, dass bestimmte Spielzustände nicht weiter untersucht werden müssen, da bereits bekannt ist, dass sie zu einem schlechteren Ergebnis führen.

Bei unserem Beispiel würde das wie folgt aussehen. Der Algorithmus hat folgende Züge abgeschnitten. Sie müssen nicht weiter erkundet werden, da sie ein schlechteres Ergebnis liefern würden:


Nun betrachten wir die Implementierung.

Der Code:
Als erstes schauen wir uns die Minimax-Funktion ohne Alpha-Beta-Pruning an namens minimaxOHNE():
function minimaxOHNE(board, depth, maximizingPlayer) { // Überprüfe, ob das Spiel beendet ist oder die maximale Tiefe erreicht wurde if (depth == 0 || isGameOver(board)) { return [evaluateBoard(board), null]; } // Hole alle möglichen Züge für den aktuellen Spieler let moves = generateEveryMove(board, maximizingPlayer ? 1 : -1); // Initialisiere den besten Wert und den besten Zug let bestValue = maximizingPlayer ? -Infinity : Infinity; let bestMove = null; // Iteriere über alle möglichen Züge for (let move of moves) { // Führe den Zug auf einer Kopie des Spielbretts aus let newBoard = makeMove(board, move); // Rekursiver Aufruf der Minimax-Funktion für den nächsten Zug let [value, _] = minimax(newBoard, depth - 1, !maximizingPlayer); // Aktualisiere den besten Wert und den besten Zug basierend auf dem aktuellen Spieler if (maximizingPlayer) { if (value > bestValue) { bestValue = value; bestMove = move; } } else { if (value < bestValue) { bestValue = value; bestMove = move; } } } return [bestValue, bestMove]; }
Durch die Kommentare sollte der obere Code relativ verständlich sein. Somit wenden wir uns den Zusatz von Alpha-Beta-Pruning zu. Hierbei werden wir die Parameter der Funktion um die Werte alpha und beta erweitern und folgende fünf Zeilen hinzufügen:
alpha = Math.max(alpha, bestValue); ... beta = Math.min(beta, bestValue); ... if (beta <= alpha) { break; }
Somit sieht der Code aus wie folgt:
function minimax(board, depth, alpha, beta, maximizingPlayer) { // Überprüfe, ob das Spiel beendet ist oder die maximale Tiefe erreicht wurde if (depth == 0 || isGameOver(board)) { return [evaluateBoard(board), null]; // Rückgabe von Wert und null-Zug } // Hole alle möglichen Züge für den aktuellen Spieler let moves = generateEveryMove(board, maximizingPlayer ? 1 : -1); // Initialisiere den besten Wert und den besten Zug let bestValue = maximizingPlayer ? -Infinity : Infinity; let bestMove = null; // Iteriere über alle möglichen Züge for (let move of moves) { // Führe den Zug auf einer Kopie des Spielbretts aus let newBoard = makeMove(board, move); // Rekursiver Aufruf der Minimax-Funktion für den nächsten Zug let [value, _] = minimax(newBoard, depth - 1, alpha, beta, !maximizingPlayer); // Aktualisiere den besten Wert und den besten Zug basierend auf dem aktuellen Spieler if (maximizingPlayer) { if (value > bestValue) { bestValue = value; bestMove = move; } alpha = Math.max(alpha, bestValue); } else { if (value < bestValue) { bestValue = value; bestMove = move; } beta = Math.min(beta, bestValue); } // Alpha-Beta-Pruning: Abbruchbedingungen if (beta <= alpha) { break; } } return [bestValue, bestMove]; // Rückgabe von bestem Wert und bestem Zug }
Um nun den besten Zug eines Spielers zu berechnen, müssen wir nur noch die Minimax-Funktion aufrufen.

Beispiel:
let [bestValue, bestMove] = minimax(testboard, 4, -Infinity, Infinity, true);*Aufruf für Weiß (True) mit der Tiefe 4

Die Ausgabe für den Startzustand einer Partie:
['move', 7, 6, 5, 5]
Hier soll das Pferd von G8 auf F6 gezogen werden.

Da wir wissen, wie der Bot funktioniert, kommen wir noch zu ein paar Vertiefungen.

Analyse:
Nun sammeln wir ein paar Daten, um den Algorithmus und seine Effizienz zu testen. Je tiefer der Spielbaum ist, desto besser werden die Züge. Jetzt schauen wir mal, wie schnell der Bot den besten Zug berechnen kann. Als weiteren Vergleich betrachten wir die Berechnungsdauer und die berechneten Züge ohne Alpha-Beta-Pruning, damit wir ein Verständnis für den Einfluss dieses Algorithmus bekommen. Hierbei lass ich die Funktion fünf Mal mit jeweils einer Tiefe von 1-7 den besten Zug berechnen (Zeiten weichen bei verschiedenen Rechenkapazitäten voneinander ab):

Bei dem Ergebnis sieht man deutlich, dass sich der Alpha-Beta-Pruning Algorithmus lohnt. Durch diesen sparen wir viel Rechenaufwand und Zeit. Bei einer Tiefe von 7 habe ich den Algorithmus nicht durchlaufen lassen, da dies sehr lange gedauert hat. Um uns jetzt den vorliegenden exponentiellen Wachstum anzuschauen, bilden wir mithilfe der uns zur Verfügung stehenden Daten insgesamt vier Graphen.
Auf der linken Seite plotten wir den Graphen, der die Zeit in Abhängigkeit von der Tiefe angibt und auf der rechten Seite den Graphen, der die Anzahl der Züge in Abhängigkeit der Tiefe beschreibt. Dies geschieht jeweils für die Minimax-Funktion mit und ohne Alpha-Beta-Pruning:


Die Funktionen sind folgende:
Zeit ohne AB-Pruning: \( f(x)=0,0000341020046*e^{2,653861935763x} \)
Zeit mit AB-Pruning: \( f(x)=0,0000391980904*e^{2,0334884151653x} \)
Züge ohne AB-Pruning: \( f(x)=0,8127650778346*e^{3,1313396807574x} \)
Züge mit AB-Pruning: \( f(x)=1,686213835827*e^{2,3587784400947x} \)

Nun können wir mithilfe der Funktionen unsere beiden fehlenden Felder bestimmen. Hierzu setzen wir die Tiefe 7 in die Funktionen ohne AB-Pruning ein und bekommen einen ungefähren Wert für die Zeit und die berechneten Züge.
Das Ergebnis für eine Tiefe von 7 ohne AB-Pruning ist, dass ca. 2688003594 Züge in ca. 3987,3381 Sekunden (ca. 1 Stunde) berechnet werden. Diese Stunde wollte ich nicht abwarten, da wir genug Daten für Funktionen haben, die uns einen Näherungswert liefern.

Somit haben wir einen Schachbot in JavaScript geschrieben, der uns einen sehr guten Zug liefert. Perfekt ist der Zug natürlich nicht, da man sonst ein ganzes Schachspiel simulieren müsste. Das wäre mit normalen Computern in absehbarer Zeit nicht möglich. Nun stellt sich folgende Frage:

Wie beschleunige ich die Berechnungen?
Das naheliegendste wäre bessere Hardware. Das würde zwar etwas bringen, aber nicht genug. Somit kommen wir auf einen "einfacheren" Ansatz. Wir bringen die Berechnungen auf die kleinste Ebene. Die Bit-Ebene (Siehe Binärsystem und Logikgatter und Schalttabellen). Um am schnellsten den besten Zug zu berechnen, sollten wir Bit-Operationen anwenden, da sie die schnellsten Operationen sind. Hier ein kleiner Einblick:

Als erstes müssen wir unser Spielbrett in Bits darstellen. Da wir nur zwei Zahlen (0 und 1) zur Verfügung haben, lagern wir das Spielbrett in acht verschiedene Bitboards aus:
Bauern, Springer, Läufer, Türme, Damen, Könige, weiße Figuren und schwarze Figuren.

Hier eine kleine Veranschaulichung des Bauern-Bitboards:
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
Um nun die weißen Bauern zu bekommen, wenden wir eine &-Operation mit dem Bitboard der weißen Figuren an und erhalten nur die weißen Bauern. Auf diesem Bitboard kann man eine Verschiebung um acht nach links ("<<": left shift) anwenden, um die Bewegung der Bauern darzustellen. Somit wäre die Reihe der weißen Bauern um eine Reihe nach oben verschoben. Nun müssen wir nur noch prüfen, welche Positionen davon möglich sind, indem wir die Bitboards der weißen Figuren und der schwarzen Figuren addieren, dies dann invertieren und eine &-Operation zwischen diesem Bitboard und dem der bewegten weißen Bauern durchführen. So bleiben die Einsen über, auf die ein Bauer ziehen kann.
Das Gleiche kann man für das Schlagmuster (Verschiebung um 7 und 9) der Bauern machen. Der Einzige Unterschied ist, dass man natürlich seine eigenen Figuren nicht schlagen kann und nur auf besetzten Feldern von schwarzen Figuren ziehen kann (&-Operation mit schwarzen Figuren).

So können wir die Züge jeder Figur schneller generieren und sparen Rechenkapazität bzw. Zeit.