Wikiszótár

dámajáték

Magyar

Kiejtés

  • IPA: [ ˈdaːmɒjaːteːk]

Főnév

dámajáték

  1. (matematika)

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.


1. Dámajáték szabályai

  1. Tábla és bábuk:
    • Egy 8x8-as sakktáblát használnak, de csak a sötét mezőkön játszanak.
    • Minden játékos 12 bábút kap, amelyek a tábla sötét mezőire kerülnek az első három sorba.
  2. Mozgás:
    • A bábuk előre átlós irányban mozognak egy mezőt.
    • Ha egy ellenfél bábuja mögött üres mező van, akkor át lehet ugrani rajta, így leütve azt. Az ugrás kötelező, ha lehetséges.
  3. Dáma:
    • Ha egy bábu eléri az ellenfél hátsó sorát, „dáma” lesz, és ezután előre és hátra is léphet átlós irányban.
  4. Játék vége:
    • Egy játékos veszít, ha az összes bábuját elveszíti, vagy ha nincs érvényes lépése.


2. Adatstruktúra

Táblázatos reprezentáció:

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: 

[[ 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]]

Bábuk pozíciójának tárolása:

Alternatív megközelítésként egy lista használható a bábuk pozícióinak tárolására: 

player1_pieces = [(5, 0), (5, 2), (5, 4), (5, 6), ...]  # Első játékos bábui
player2_pieces = [(2, 1), (2, 3), (2, 5), (2, 7), ...]  # Második játékos bábui

3. Algoritmus

Lépések generálása:

  1. Egyszerű lépés: Minden bábu számára vizsgáljuk az átlós irányokat (előre és hátra dámák esetében).
  2. Ugrások: Vizsgáljuk, hogy van-e ellenfél bábuja mögött üres mező. Az ugrások kötelezőek.

Értékelési függvény:

  • Bábuk száma: Több bábu = jobb pozíció.
  • Pozíció: A középső mezők értékesebbek.
  • Dámák száma: A dáma bábuk értékesebbek.

Lépés kiválasztása:

  • Min-Max algoritmus Alpha-Beta metszéssel:
    • Rekurzív keresés a lehetséges lépéseken.
    • Az ellenfél legrosszabb helyzete és a saját legjobb helyzet kiválasztása.


4. Dámajáték implementáció

Python kód

class Checkers:
    def __init__(self):
        # 8x8 tábla
        self.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],
        ]

    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[i][j] == player:
                    # Vizsgáljuk az átlós irányokat
                    directions = [(-1, -1), (-1, 1)] if player == 1 else [(1, -1), (1, 1)]
                    for dx, dy in directions:
                        x, y = i + dx, j + dy
                        if 0 <= x < 8 and 0 <= y < 8 and self.board[x][y] == 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))

C++ kód

#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[i][j] == 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 [dx, dy] : directions) {
                        int x = i + dx, y = j + dy;
                        if (x >= 0 && x < 8 && y >= 0 && y < 8 && board[x][y] == 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.


Dámajáték solver Pythonban

Teljes kód: Min-Max alapú solver Alpha-Beta metszéssel

import copy

class Checkers:
    def __init__(self):
        self.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],
        ]

    def print_board(self):
        for row in self.board:
            print(row)
        print()

    def generate_moves(self, player):
        moves = []
        directions = [(-1, -1), (-1, 1)] if player == 1 else [(1, -1), (1, 1)]
        for i in range(8):
            for j in range(8):
                if self.board[i][j] == player:
                    for dx, dy in directions:
                        x, y = i + dx, j + dy
                        if 0 <= x < 8 and 0 <= y < 8 and self.board[x][y] == 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[start[0]][start[1]] = 0
        self.board[end[0]][end[1]] = player

    def undo_move(self, move, player):
        """Visszavon egy lépést."""
        start, end = move
        self.board[start[0]][start[1]] = player
        self.board[end[0]][end[1]] = 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()

Kódmagyarázat

  1. Táblastruktúra:
    • A tábla 8x8-as mátrixként van tárolva, ahol a pozitív számok az első játékos, a negatív számok a második játékos bábuit jelölik.
  2. Lépések generálása:
    • Az 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).
  3. Értékelési függvény (evaluate):
    • Egy egyszerű pontozási függvény, amely a bábuk számát hasonlítja össze.
  4. Min-Max algoritmus Alpha-Beta metszéssel:
    • Optimalizálja a keresést azáltal, hogy bizonyos ágazatokat kizár.
    • Rekurzívan keres a lehetséges lépések között, és a legjobb pontszámot választja.
  5. Legjobb lépés kiválasztása (best_move):
    • Meghatározza a legjobb lépést a megadott mélység alapján.


Példa futtatás eredménye

  1. Az alap táblaállapot:

    [0, -1, 0, -1, 0, -1, 0, -1]
[-1, 0, -1, 0, -1, 0, -1, 0]
...
[1, 0, 1, 0, 1, 0, 1, 0]
[0, 1, 0, 1, 0, 1, 0, 1]

  2. Legjobb lépés például:

    Az első játékos legjobb lépése: ((5, 0), (4, 1))

  3. 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.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=dámajáték&oldid=3480212”