Aber bei Interesse könnte ich ein wenig preisgeben...
Wäre interessant.
Ich weiss jetzt nicht genau, wie und was ich hier jetzt preisgeben soll.
Deswegen fange ich einfach mal vorsichtig an...
Datenstrukturen:
Der Zustand eines Spielbretts wird in einer relativ simplen Struktur gespeichert:
|
Quellcode
|
1
2
3
4
5
6
7
8
9
10
11
12
|
SBOARD struct
{
dword _field[64]; // Alle 64 Felder des Spielbretts (-1 für leer, ansonsten ID der Spielfigur).
dword _player; // Wer ist an der Reihe (0: Weiss; 1: Schwarz).
dword _ply; // Anzahl der bisherigen "Halbzüge".
dword _castleqs[2]; // Status der langen Rochade beider Spieler.
dword _castleks[2]; // Status der kurzen Rochade beider Spieler.
dword _material[2]; // Material der beiden Spieler (Summe der Wertungen aller Spielfiguren).
dword _kingpos[2]; // Position der beiden Könige (ID des Feldes).
dword _enpassant; // Position eines etwaigen En-passant-Bauern.
dword _reserverd; // Zum Hinterlegen von Debug-Informationen.
}
|
Die Positionen der beiden Könige werden aus Performance-Gründen nochmal explizit gespeichert.
Ein Zug wird in einer noch simpleren Struktur gespeichert:
|
Quellcode
|
1
2
3
4
5
6
7
8
9
10
|
SMOVE struct
{
dword _from; // Startfeld des Zuges (ID des Feldes).
dword _to; // Zielfeld des Zuges (ID des Feldes).
dword _chessman; // ID der bewegten Schachfigur.
dword _capture; // ID der etwaigen geschlagenen Figur des Gegners.
dword _type; // Typ des Zuges (normaler Zug, en passant, Rochade etc.).
dword _prom; // ID der neuen Spielfigur bei etwaiger Bauernumwandlung.
dword _reserverd; // Zum Hinterlegen von Debug-Informationen.
}
|
Die Felder erhalten zur Identifizierung eine individuelle ID, wobei das "erste" Feld A1 ("links unten") die ID 0 erhält -- das "letzte" Feld H8 ("rechts oben") die ID 63. Die Spielfiguren sind auch durchnummeriert, sowohl abhängig von der Farbe als auch farbunabhängig: Die farbunabhängigen IDs für Bauer, Läufer, Springer, Turm, Dame und König sind 0, 1, 2, 3, 4 bzw. 5. Dieselben IDs erhalten auch die Figuren für Weiss -- die IDs der schwarzen Figuren werden um 8 erhöht, also 8, 9, 10, 11, 12 und 13.
Algorithmen:
Ich habe -- wie es ja eigentlich üblich ist -- mich an bewehrten Verfahren orientiert. Für genauere Erläuterungen der Algorithmen sollte Google o.ä. angeworfen werden.
Die KI beruht im Großen und Ganzen natürlich auf
Alpha-Beta-Pruning, wie sich das für eine Schach-KI nunmal gehört.
Quiescence Search ist eine feine Sache, weil "gefährliche Captures jenseits des Suchhorizontes" somit vermieden bzw. reduziert werden können. Jedoch denke ich abundzu, dass gerade da noch optimiert werden kann, was ich noch vorhabe, denn die meiste Zeit wird nicht während der "normalen" Suche verbraten, sondern während der "quiescent" Suche.
Iterative Deepening darf bei sowas natürlich auch nicht fehlen, damit alle Züge annähernd ausgewogen die Möglichkeit haben, ihr Potenzial unter Beweis zu stellen.
Der
Transposition Table hat eine einstellbare Größe. Theoretisch kann man seinen kompletten Arbeitsspeicher zur Verfügung stellen. Irgendwann stehen dann so viele Züge im Cache, dass kaum mehr gerechnet werden muss. Naja, ein wenig utopisch, aber theoretisch wäre das denkbar.
Auf Schnickschnack wie
MTD(f) habe ich zunächst verzichtet. Ich befürchte, dass dabei lediglich eine suboptimale Lösung im ohnehin schon suboptimalen Suchraum erzielt würde.
Mit der augenblicklichen Konfiguration lassen sich ca. 800.000 Knoten pro Sekunde generieren, was schon eine erstaunlich gute Rate ist.
Für einen "vorsichtigen Anfang" war das jetzt doch schon eine ganze Menge und ich habe noch nicht einmal was über die Auswertung der Spielbretter erzählt.
Aber bei Bedarf kann ich das ja noch nachholen -- sowie Screenshots, die ich evtl. auch machen könnte, auch wenn die Grafik hinsichtlich der KI eines Schachspiels relativ irrelevant ist.