chess
Főnév
chess (tsz. chesses)
A sakk az egyik legkutatottabb és legismertebb stratégiai játék, amelynek programozási szempontból különösen gazdag struktúrája van. A sakk nem csupán egy játék, hanem egy kombinatorikai probléma, egy játékfa, egy logikai szimuláció, és egy AI-kihívás is – mindez egyben. Ezért ideális alany programozók, algoritmusfejlesztők és mesterséges intelligencia-kutatók számára.
Ebben a bevezetőben a sakk programozási aspektusaira koncentrálunk: táblaábrázolás, lépésszabályok, keresőalgoritmusok, heurisztikák, AI, és sok más fontos elem kerül bemutatásra.
🧱 1. A sakk mint adatmodell
1.1 Tábla reprezentáció
A sakktábla egy 8×8-as rács, azaz 64 mező, amelyeket kétféleképpen lehet reprezentálni:
1D tömb (indexelt):
char board[64];
board[0] = 'r'; // a8: fekete bástya
board[63] = 'R'; // h1: fehér bástya
2D mátrix:
char board[8][8];
board[0][0] = 'r'; // a8
board[7][7] = 'R'; // h1
1.2 Bitenkénti reprezentáció (bitboard)
A bitboard egy 64 bites szám, ahol minden bit egy mezőt jelöl. A gyors bitműveletek miatt sok sakkmotor használja:
uint64_t pawns_white = 0x00FF000000000000; // fehér gyalogok kezdőpozícióban
♞ 2. Lépések generálása (move generation)
2.1 Alapszabályok
Minden bábunak külön lépési szabályai vannak. Egy jó sakkprogram külön modulban definiálja:
- gyalog (egyenes előre, ütés átlósan, en passant)
- huszár (L-alak)
- futó (átlók)
- bástya (sor/oszlop)
- vezér (futó + bástya)
- király (egyel mozdul minden irányban, sáncolás!)
2.2 Példa lépésgenerálásra
std::vector<Move> generate_knight_moves(Position pos, Color color) {
std::vector<Move> moves;
for (auto [dx, dy] : {{2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1}}) {
int x = pos.x + dx;
int y = pos.y + dy;
if (is_valid(x, y) && is_empty_or_enemy(x, y, color))
moves.emplace_back(pos, Position(x, y));
}
return moves;
}
🌲 3. Keresőalgoritmusok – Játékfa bejárása
3.1 Minimax algoritmus
A klasszikus Minimax algoritmus feltételezi, hogy az egyik játékos maximalizálni, a másik minimalizálni akarja az értékfüggvényt.
3.2 Alpha-Beta metszés
Optimalizált változat, amely levágja azokat az ágakat, amelyek garantáltan nem vezetnek jobb eredményhez.
int alphabeta(Node node, int depth, int α, int β, bool maximizing) {
if (depth == 0 || node.is_terminal()) return evaluate(node);
if (maximizing) {
int value = -INF;
for (auto child : node.children())
value = std::max(value, alphabeta(child, depth-1, α, β, false)),
α = std::max(α, value);
if (β <= α) break; // cut-off
return value;
} else {
int value = INF;
for (auto child : node.children())
value = std::min(value, alphabeta(child, depth-1, α, β, true)),
β = std::min(β, value);
if (β <= α) break;
return value;
}
}
📈 4. Heurisztikus értékelőfüggvény
Egy táblaállást értékelni kell pontszámmal. Alapértékek:
| Bábú | Érték |
|---|---|
| Gyalog | 1 |
| Huszár | 3 |
| Futó | 3 |
| Bástya | 5 |
| Vezér | 9 |
| Király | ∞ (nem értékelhető numerikusan) |
Az értékeléshez figyelembe lehet venni:
- bábuk száma és értéke
- támadás / védelem
- mezőkontroll (center, előretolt gyalogok)
- királybiztonság
🧠 5. AI: Gépi tanulás és sakkmotorok
A legerősebb sakk-AI-k már neurális hálózatokat használnak:
- Stockfish – klasszikus motor bitboard és kézzel tervezett heurisztikával
- AlphaZero – reinforcement learning + deep neural net + MCTS
5.1 Monte Carlo Tree Search (MCTS)
A gép véletlenszerű játszmákat szimulál és statisztikák alapján dönt.
🧪 6. Tesztelés és játékok szimulációja
Sakkprogram fejlesztésénél fontos az:
- unit teszt minden bábura és lépésre
- FEN támogatás (táblaállás mentése/szimulációja)
- PGN fájlok beolvasása (játszmaformátum)
- random szimulált játékok AI vs AI
🖥️ 7. GUI / vizualizáció
Fejlett sakkmotorok gyakran külön programot (frontendet) használnak:
- XBoard / WinBoard
- lichess.org bot API
- UCI protokoll (Universal Chess Interface): motorok kommunikálnak GUI-val
🧾 8. Példák és források
- Stockfish – nyílt forráskódú sakkmotor (C++)
- Python Chess – teljes sakkmotor Pythonban
- Lichess Bot API
✅ Összefoglalás
A sakk programozása egy kiváló terep az algoritmusok, mesterséges intelligencia, adatszerkezetek, heurisztika és keresési stratégiák megértésére. Egy egyszerű sakkmotorban is ott rejlik a teljes játékelméleti világ, míg a profi szinten való programozása olyan mély tudást igényel, amely egyesíti a matematikát, a programozást és a gépi tanulást.