Schachspiel

Werbeanzeige

J.M.K.

Alter Hase

Beiträge: 500

Wohnort: BW Karlsruhe Ittersbach

Beruf: Schüler

01.06.2006, 01:00

ich würde dir in dem fall einfach mal empfehlen es mal mit spielen zu probieren die nicht so eine komplexe ki haben z.B. Mühle oder Dame ....

Vegetarier essen meinem Essen das Essen weg.

Zum Seitenanfang

john

Alter Hase

Beiträge: 786

Beruf: Schüler

01.06.2006, 01:10

Es geht mir hier aber um Schach. :lol:
Es war ja wie gesagt nur eine Frage in die Runde, es ist kein tatsächliches Vorhaben im Moment.

mfg
john

Zum Seitenanfang

matthias

Alter Hase

Beiträge: 449

Wohnort: wipperfürth

01.06.2006, 02:28

kannst ja mal eins programmieren bei dem ich gewinnen kann :lol:
Schach für dummies.

"In those days spirits were brave, the stakes were high, men were REAL men, women were REAL women, and small furry creatures from Alpha Centauri were REAL small furry creatures from Aplha Centauri."

Zum Seitenanfang

Anonymous

unregistriert

01.06.2006, 09:04

Oh Man Leute, wie oft soll er denn noch sagen, dass er keins programmieren
will und dass das nur eine Frage war??? Ich hasse solche Andeutungen...

Zum Seitenanfang

Steven77

Alter Hase

Beiträge: 515

Wohnort: Münster - Gievenbeach

Beruf: Wissenschaftlicher Mitarbeiter

01.06.2006, 12:25

Zitat von »"John91"«

Zitat von »"Steven77"«

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

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

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.

Zum Seitenanfang

john

Alter Hase

Beiträge: 786

Beruf: Schüler

01.06.2006, 13:41

Danke!

Einfach mal interessant zu wissen, wie du da rangegangen bist, viel mehr wollte ich auch gar nicht wissen. Ein paar Screenshots kannst du ja auch noch offenbaren wenn du willst, auch wenn es nichts mit der KI zu tun hat, ja.

mfg
john

Zum Seitenanfang

Sicaine

unregistriert

01.06.2006, 20:14

Es gibt ne Schachzeitschrift und mit Google soviele Algos, dass ich bis dato kein Interesse hatte. Vorallem weil da welche dranhocken mit Hochleistungspcs und so otimierten algos, dass ich daran kein Interesse hab, gibt coolere sachen :>

Zum Seitenanfang

Anonymous

unregistriert

02.06.2006, 01:28

Nebenbei:

Ich habe denn Code einer C64 (Commodore) IQ.

Wer Lust hat die 32 Seiten abzutipen darf sich melden. Das ganze Prog hat 128 D4 Seiten (BASIC/DATA). Insgesamt waren 8000 Zeilen angesagt (z+10)

Ich habe damals mit meinem Vater abgetiept. Obwohl wir beide eigentlich gut waren brauchte der C64 nicht mehr als 48 Züge. Aufgabe wäre also die IQ umzuschreiben und die DATA zu "inclueden"(1200 evektive Data Zeilen).

cu :oops:

Zum Seitenanfang

DarkRage

Treue Seele

Beiträge: 226

02.06.2006, 21:31

Krass @ Abrexxes.

Ich staune echt immer wieder darüber was man damals am C64 schon alles machen konnte und was geleistet wurde... einfach nur "cool". Ich hab nur leider gar keine Ahnung mehr davon und es lohnt sich sicherlich auch nicht mehr sich da rein zu lesen. Schade das ich nicht schon zu der Zeit alt genug für sowas war...