sakkalgoritmus
P (gyalog), R (bástya), N (ló), B (futó), Q (vezér), K (király), kis- és nagybetűkkel jelezve a fekete/fehér színeket.
Ez az algoritmus rekurzívan kiértékeli a lehetséges állapotokat: 1. A játékos célja a maximális nyereség elérése (Maximizing player). 2. Az ellenfél célja a minimális veszteség elérése (Minimizing player).
Pseudocode:
function MinMax(state, depth, maximizingPlayer):
if depth == 0 or is_terminal(state):
return evaluate(state)
if maximizingPlayer:
maxEval = -infinity
for each child in generate_moves(state):
eval = MinMax(child, depth - 1, false)
maxEval = max(maxEval, eval)
return maxEval
else:
minEval = infinity
for each child in generate_moves(state):
eval = MinMax(child, depth - 1, true)
minEval = min(minEval, eval)
return minEval
Az Alpha-Beta metszés optimalizálja a Min-Max algoritmust azáltal, hogy bizonyos alágakat kizár, amelyek már nem befolyásolják az eredményt.
Pseudocode:
function AlphaBeta(state, depth, alpha, beta, maximizingPlayer):
if depth == 0 or is_terminal(state):
return evaluate(state)
if maximizingPlayer:
maxEval = -infinity
for each child in generate_moves(state):
eval = AlphaBeta(child, depth - 1, alpha, beta, false)
maxEval = max(maxEval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break # Beta cut-off
return maxEval
else:
minEval = infinity
for each child in generate_moves(state):
eval = AlphaBeta(child, depth - 1, alpha, beta, true)
minEval = min(minEval, eval)
beta = min(beta, eval)
if beta <= alpha:
break # Alpha cut-off
return minEval
Az evaluate(state) függvény számítja ki az adott állapot értékét. Példák heurisztikákra: 1. Bábok értéke: - Király: végtelen - Vezér: 9 - Bástya: 5 - Futó: 3 - Ló: 3 - Gyalog: 1 2. Pozíció: - Központi mezők (pl. d4, e4) értékesebbek. - Király biztonsága (pl. sáncolás). 3. Játékhelyzet: - Léptetések száma, támadott bábok.
Példa Pythonban:
def evaluate(state):
piece_values = {'K': 1000, 'Q': 9, 'R': 5, 'B': 3, 'N': 3, 'P': 1}
score = 0
for row in state:
for piece in row:
if piece.isupper(): # Fehér bábu
score += piece_values.get(piece.upper(), 0)
elif piece.islower(): # Fekete bábu
score -= piece_values.get(piece.upper(), 0)
return score
Az alábbi egyszerű példában sakklépéseket generálunk és Min-Max algoritmust alkalmazunk:
class Chess:
def __init__(self):
self.board = [
,
,
,
,
,
,
,
]
def generate_moves(self, player):
# Egyszerű lépésgenerálás (csak gyalogok példája)
moves =
for i in range(8):
for j in range(8):
if player == 'white' and self.board == 'P':
if i > 0 and self.board == '.':
moves.append(((i, j), (i - 1, j)))
return moves
def make_move(self, move):
# Lépés végrehajtása
start, end = move
piece = self.board]]
self.board]] = '.'
self.board]] = piece
def evaluate(self):
# Egyszerű értékelés (bábok értéke)
piece_values = {'K': 1000, 'Q': 9, 'R': 5, 'B': 3, 'N': 3, 'P': 1}
score = 0
for row in self.board:
for piece in row:
if piece.isupper():
score += piece_values.get(piece.upper(), 0)
elif piece.islower():
score -= piece_values.get(piece.upper(), 0)
return score
def minmax(self, depth, maximizingPlayer):
if depth == 0:
return self.evaluate()
if maximizingPlayer:
max_eval = -float('inf')
for move in self.generate_moves('white'):
self.make_move(move)
eval = self.minmax(depth - 1, False)
self.undo_move(move)
max_eval = max(max_eval, eval)
return max_eval
else:
min_eval = float('inf')
for move in self.generate_moves('black'):
self.make_move(move)
eval = self.minmax(depth - 1, True)
self.undo_move(move)
min_eval = min(min_eval, eval)
return min_eval
C++-ban hasonló módon hozhatjuk létre:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Chess {
public:
int evaluate(const vector<vector<char>>& board) {
int piece_values = {};
piece_values = 1; piece_values = -1;
piece_values = 5; piece_values = -5;
piece_values = 3; piece_values = -3;
piece_values = 3; piece_values = -3;
piece_values = 9; piece_values = -9;
piece_values = 1000; piece_values = -1000;
int score = 0;
for (const auto& row : board) {
for (char piece : row) {
score += piece_values;
}
}
return score;
}
};
int main() {
vector<vector<char>> board = {
{'r', 'n', 'b', 'q', 'k', 'b', 'n', 'r'},
{'p', 'p', 'p', 'p', 'p', 'p', 'p', 'p'},
{'.', '.', '.', '.', '.', '.', '.', '.'},
{'.', '.', '.', '.', '.', '.', '.', '.'},
{'.', '.', '.', '.', '.', '.', '.', '.'},
{'.', '.', '.', '.', '.', '.', '.', '.'},
{'P', 'P', 'P', 'P', 'P', 'P', 'P', 'P'},
{'R', 'N', 'B', 'Q', 'K', 'B', 'N', 'R'}
};
Chess chess;
cout << "Board evaluation: " << chess.evaluate(board) << endl;
return 0;
}
Ezek az alapok könnyen bővíthetők és optimalizálhatók különböző heurisztikákkal, például sakk-matt ellenőrzéssel, pozíciók súlyozásával és további szabályok figyelembevételével.