dámajáték
A dámajáték egy klasszikus kétszemélyes stratégiai játék, amelyet egy 8x8-as táblán játszanak. A cél az, hogy az ellenfél összes bábuját leüssük, vagy mozgásképtelenné tegyük. Az alábbiakban bemutatom a játék szabályait, adatstruktúráját, algoritmusát, valamint egy egyszerű Python és C++ implementációt.
A tábla 8x8-as mátrixként tárolható: - 0: üres mező. - 1: az első játékos bábuja. - 2: az első játékos dámája. - -1: a második játékos bábuja. - -2: a második játékos dámája.
Példa egy táblaállapotra:
, , , , , , , ]
Alternatív megközelítésként egy lista használható a bábuk pozícióinak tárolására:
player1_pieces = # Első játékos bábui
player2_pieces = # Második játékos bábui
class Checkers:
def __init__(self):
# 8x8 tábla
self.board = [
,
,
,
,
,
,
,
,
]
def print_board(self):
for row in self.board:
print(row)
def generate_moves(self, player):
"""Lépések generálása egy játékos számára."""
moves =
for i in range(8):
for j in range(8):
if self.board == player:
# Vizsgáljuk az átlós irányokat
directions = if player == 1 else
for dx, dy in directions:
x, y = i + dx, j + dy
if 0 <= x < 8 and 0 <= y < 8 and self.board == 0:
moves.append(((i, j), (x, y))) # Egyszerű lépés
return moves
# Használat
game = Checkers()
game.print_board()
print("Lépések az első játékosnak:", game.generate_moves(1))
#include <iostream>
#include <vector>
using namespace std;
class Checkers {
private:
vector<vector<int>> board;
public:
Checkers() {
board = {
{ 0, -1, 0, -1, 0, -1, 0, -1},
{-1, 0, -1, 0, -1, 0, -1, 0},
{ 0, -1, 0, -1, 0, -1, 0, -1},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 1, 0, 1, 0, 1, 0, 1, 0},
{ 0, 1, 0, 1, 0, 1, 0, 1},
{ 1, 0, 1, 0, 1, 0, 1, 0},
};
}
void printBoard() {
for (const auto& row : board) {
for (int cell : row) {
cout << cell << " ";
}
cout << endl;
}
}
vector<pair<pair<int, int>, pair<int, int>>> generateMoves(int player) {
vector<pair<pair<int, int>, pair<int, int>>> moves;
for (int i = 0; i < 8; ++i) {
for (int j = 0; j < 8; ++j) {
if (board == player) {
vector<pair<int, int>> directions = player == 1 ? vector<pair<int, int>>{{-1, -1}, {-1, 1}} : vector<pair<int, int>>{{1, -1}, {1, 1}};
for (auto : directions) {
int x = i + dx, y = j + dy;
if (x >= 0 && x < 8 && y >= 0 && y < 8 && board == 0) {
moves.push_back({{i, j}, {x, y}});
}
}
}
}
}
return moves;
}
};
int main() {
Checkers game;
game.printBoard();
auto moves = game.generateMoves(1);
cout << "Lépések az első játékosnak:" << endl;
for (const auto& move : moves) {
cout << "(" << move.first.first << "," << move.first.second << ") -> (" << move.second.first << "," << move.second.second << ")" << endl;
}
return 0;
}
Ezek az implementációk az alapokhoz szükségesek. Egy teljes solver implementációjához Min-Max algoritmust Alpha-Beta metszéssel, illetve heurisztikákat kell alkalmazni. Egy dámajáték solver Pythonban a Min-Max algoritmus és az Alpha-Beta metszés segítségével implementálható. Az alábbiakban bemutatom, hogyan lehet létrehozni egy egyszerű, de működőképes solver-t.
import copy
class Checkers:
def __init__(self):
self.board = [
,
,
,
,
,
,
,
,
]
def print_board(self):
for row in self.board:
print(row)
print()
def generate_moves(self, player):
moves =
directions = if player == 1 else
for i in range(8):
for j in range(8):
if self.board == player:
for dx, dy in directions:
x, y = i + dx, j + dy
if 0 <= x < 8 and 0 <= y < 8 and self.board == 0:
moves.append(((i, j), (x, y)))
return moves
def make_move(self, move, player):
"""Végrehajt egy lépést."""
start, end = move
self.board]] = 0
self.board]] = player
def undo_move(self, move, player):
"""Visszavon egy lépést."""
start, end = move
self.board]] = player
self.board]] = 0
def evaluate(self):
"""Egyszerű értékelési függvény."""
score = 0
for row in self.board:
for piece in row:
if piece == 1:
score += 1
elif piece == -1:
score -= 1
return score
def minmax(self, depth, maximizing_player, alpha, beta):
"""Min-Max algoritmus Alpha-Beta metszéssel."""
if depth == 0 or not self.has_moves(maximizing_player):
return self.evaluate()
if maximizing_player:
max_eval = float('-inf')
moves = self.generate_moves(1)
for move in moves:
self.make_move(move, 1)
eval = self.minmax(depth - 1, False, alpha, beta)
self.undo_move(move, 1)
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break # Beta metszés
return max_eval
else:
min_eval = float('inf')
moves = self.generate_moves(-1)
for move in moves:
self.make_move(move, -1)
eval = self.minmax(depth - 1, True, alpha, beta)
self.undo_move(move, -1)
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break # Alpha metszés
return min_eval
def has_moves(self, player):
"""Ellenőrzi, hogy a játékosnak van-e érvényes lépése."""
return len(self.generate_moves(player)) > 0
def best_move(self, depth, player):
"""Legjobb lépés kiválasztása."""
best_eval = float('-inf') if player == 1 else float('inf')
best_move = None
moves = self.generate_moves(player)
for move in moves:
self.make_move(move, player)
eval = self.minmax(depth - 1, player == -1, float('-inf'), float('inf'))
self.undo_move(move, player)
if (player == 1 and eval > best_eval) or (player == -1 and eval < best_eval):
best_eval = eval
best_move = move
return best_move
# Dámajáték használat
game = Checkers()
game.print_board()
# Első játékos legjobb lépése
best = game.best_move(depth=3, player=1)
print("Az első játékos legjobb lépése:", best)
if best:
game.make_move(best, player=1)
game.print_board()
generate_moves függvény visszaadja az összes lehetséges lépést a megadott játékos számára (egyszerű lépésekkel).evaluate):
best_move):
Az alap táblaállapot:
...
Legjobb lépés például:
Az első játékos legjobb lépése: ((5, 0), (4, 1))
Tábla frissítése a lépés után.
Ez a kód működőképes alapot ad egy dámajáték solverhez. Az optimalizáció és a további szabályok (pl. ugrás, dáma) bővíthetők a kódhoz.