Ideen zur Schach KI

[Binärbaum]

Zitat:

Zitat von atreju2oo0

Zitat:

Zitat von Binärbaum

Das ist unterschiedlich und kommt auch auf die jemweilige Figur an.
Also ein Bauer ist zum Beispiel am wertvollsten, wenn er in der 7. (weiß) bzw. 2. Reihe (schwarz) steht, da man diesen beim nächsten Zug verwandeln kann.
Für König ist es hingegen sinnvoll, wenn man die Rochade ausführt, da er so besser geschützt ist.
Für Springer ist es gut, wenn aich sich im (erweiterten) Zentrum befinden,...
...

Wenn dein Programm nach diesen Gesichtspunkten entscheidet schickt es alle Bauern auf die Reise zum Gegner führt ne Rochade aus und lässt den König in der Ecke stehen!
Das interessante an Schach ist ja gerade, das jeder mögliche Zug der beste sein kann.

Ich habe ja auch gesagt, dass diese Kriterien noch lange nicht vollständig sind.
Aber IMHO arbeiten manche Schahprogramme (z.B. GNUchess) nach dem von mir beschriebenen Prinzip/ Ansatz, und fahren damit auch nicht schlecht und es schickt nicht alle Bauern zur Grundlinie, so wie du es behauptest. Sinnvoll sind diese Ansätze mit dem bewerten der Züge ja auch erst dann, wenn man mehrere Züge vorrausberechnet.

MfG
Binärbaum

[Cicaro]

Zitat:

Zitat von Binärbaum

Mit Entwicklung meint er sicher, dass man mehrere Züge hintereinander auf ein bestimmtes Ziel (z.B. Angriff auf dem Königsflügel) hinarbeitet. Das wird aber schon schwieriger (für die KI).

Eben. Es soll die erste Schach-KI von mir werden.

Zitat:

Zitat von Binärbaum

Und zur "mathematischen Logik":
Ein ehemaliger Schach-Weltmeister hat mal gesagt (nicht wörtlich, aber vom Inhalt her):
"Ein Spiel, indem alles so klar wäre wie 2 mal 2 gleich 4, würde schnell an Reiz verlieren."
Soll heißen, dass es nicht so einfach ist, eine gewisse Logik herauszuarbeiten, um das Schachspiel zu beschreiben.

Ist schon klar. Aber um die Logik ins Spiel zu bringen ist genau der Reiz des Spiels, oder nicht ?

Zitat:

Zitat von Binärbaum

Und wie man diese "Logik" dann in dein Programm implementiert, hängt stark davon ab, wie du die gegenwärtige Stellung auf dem Brett darstellst (d.h. Datentypen, ...).

kurz skizziert:

Delphi-Quellcode:

type 
TFigure = record
Pos:Tpoint;
Info:Integer;
end;

TFields = array[1..8,1..8] of TFigure;

TBoard = class
 Fields:TFields;
parent:TBoard;
Children:array of TBoard;
//... 
end;

// zur Darstellung
TChessBoard = class
Image:Timage;
Board:TBoard;
//...
end;

da wir gerade dabei sind, was hältst du davon ?

[bigg]

Spontan fallen mir da noch Figur-Wertigkeit, Schlagrichtung und Sprungrichtung ein.

[Cicaro]

Zitat:

Zitat von atreju2oo0

Wenn dein Programm nach diesen Gesichtspunkten entscheidet schickt es alle Bauern auf die Reise zum Gegner führt ne Rochade aus und lässt den König in der Ecke stehen!
Das interessante an Schach ist ja gerade, das jeder mögliche Zug der beste sein kann.
Es gibt genug Partien die gewonnen wurden, weil der spätere Gewinner 4 Züge vorher seine Dame geopfert hat!
Deshalb ist der Ansatz nach generell-günstigen Positionen zu spielen IMHO falsch.

Allein schon, doch - ich dachte dies wär' klar - ich will viele gute Methoden der Zugbepunktung einbringen und so eine gute KI kreieren.

[Binärbaum]

Zitat:

Zitat von Cicaro

kurz skizziert:

Delphi-Quellcode:

type 
TFigure = record
Pos:Tpoint;
Info:Integer;
end;

TFields = array[1..8,1..8] of TFigure;

TBoard = class
 Fields:TFields;
parent:TBoard;
Children:array of TBoard;
//... 
end;

// zur Darstellung
TChessBoard = class
Image:Timage;
Board:TBoard;
//...
end;

da wir gerade dabei sind, was hältst du davon ?

Naja, ...
Wozu speicherst du in TFigure die Position in pos, wenn diese doch schon aus den Indices von TFields hervorgeht?

[Cicaro]

Ganz nebenbei glaub ich bei MiniMax ein gewisses Bepunktungssystem gesehen zu haben. Ich hab' nämlich mal eine Source in die Finger bekommen, die aber nich' kompilierbar ist, da dort Units wie 'Diag*.dcu' nicht vorhanden sind.

Weiß da noch jemand was dazu ('ne komplette Source vielleicht) ?

[Cicaro]

Zitat:

Zitat von Binärbaum

Zitat:

Zitat von Cicaro

kurz skizziert:

Delphi-Quellcode:

type 
TFigure = record
Pos:Tpoint;
Info:Integer;
end;

TFields = array[1..8,1..8] of TFigure;

TBoard = class
 Fields:TFields;
parent:TBoard;
Children:array of TBoard;
//... 
end;

// zur Darstellung
TChessBoard = class
Image:Timage;
Board:TBoard;
//...
end;

da wir gerade dabei sind, was hältst du davon ?

Naja, ...
Wozu speicherst du in TFigure die Position in pos, wenn diese doch schon aus den Indices von TFields hervorgeht?

Eigentlich ist dieser kleiner Zusatz ja egal, aber:

Delphi-Quellcode:

procedure TBoard.IrgendNeProc(F:TFigure);
begin
// ...
end;

hier kannst du die Pos auch ermitteln ohne lange zu suchen.

Worauf ich aber meine Frage bezog, war, ob diese Children-Verschachtelung Sinn macht (unter anderem).
Ich wollte nämlich noch 'ne Methode einbauen, die die Punkte einer bestimmten Stellung 'misst' und das Parent-Board prüft wie gut der Zug, der zu dieser Stellung geführt hat, war. usw.

Gibt es vielleicht noch andere sinnvolle Vorgehensweisen, die dieses 'Vorausdenken' sorgen ?

[glkgereon]

bepunktungssystem? die figuren?

Bauer: 1
Läufer: 3
Springer: 3
Turm: 5
Dame: 8 (oder 9 ?)
König: ~ (unendlich, ohne könig hat man verloren ;) )

bevor du mit ner ki anfängst, schreib erstmal eine "grafik"-engine, die folgende anforderungen erfüllt:

- darstellung der akuellen stellung
- entgegennahme von user-inputs (maus, tastatur)
- entgegennahme von programm-inputs (functions/ procedures)
- einfach ansteuerung (zb. TrackFigure(x1,y1,x2,y2); )

dann erweiterst du diese engine mit einem reinen bewertungssystem, das einfach sagt, wie es seiner meinung nach grade steht.

dieses testest du dann ausführlich

wenn es gut ist, dann baust du ein das er züge selber ausprobiert.

und dann, ist es nur noch ein kleiner schritt bis zur "richtigen" ki

[Binärbaum]

Zitat:

Zitat von glkgereon

bevor du mit ner ki anfängst, schreib erstmal eine "grafik"-engine, die folgende anforderungen erfüllt:

- darstellung der akuellen stellung
- entgegennahme von user-inputs (maus, tastatur)
- entgegennahme von programm-inputs (functions/ procedures)
- einfach ansteuerung (zb. TrackFigure(x1,y1,x2,y2); )

dann erweiterst du diese engine mit einem reinen bewertungssystem, das einfach sagt, wie es seiner meinung nach grade steht.

dieses testest du dann ausführlich

wenn es gut ist, dann baust du ein das er züge selber ausprobiert.

und dann, ist es nur noch ein kleiner schritt bis zur "richtigen" ki

Ich würde davon abraten, zuerst die Grafik-Engine zu schreiben.
Solange man die KI bzw. das

Zitat:

Zitat von glkgereon

reinen bewertungssystem

noch nicht hat, braucht man IMHO auch noch keine Grafik. Ich hatte in meinem Programm am Anfang auch keine Grafik-Engine, sondern nur einen "Konsolenmodus", d.h. man konnte das Prog. über die Konsole ansprechen und seine Züge machen.
Das reicht auch erstmal, bis man die KI (nahezu) fertig hat. (Bis zu dem Punkt bin ich leider bis heute nicht gekommen :( )
Erst dann sollte man sich um die Grafik kümmern.

MfG
Binärbaum

[dizzy]

Zitat:

Zitat von Cicaro

Ganz nebenbei glaub ich bei MiniMax ein gewisses Bepunktungssystem gesehen zu haben. Ich hab' nämlich mal eine Source in die Finger bekommen, die aber nich' kompilierbar ist, da dort Units wie 'Diag*.dcu' nicht vorhanden sind.

Weiß da noch jemand was dazu ('ne komplette Source vielleicht) ?

Einen Source nicht, aber die Theorie:

Minimax liegt ein sog. Spielbaum zu Grunde, der folgendermaßen aufgebaut ist:
Wurzel ist das Schachbrett im Ausgangszustand. Davon ab gehen n Unterknoten, in denen jeweils ein möglicher Zug des nächsten Spielers (weiss hier) abgebildet wird. Von dieses aus gehen jeweils Kinder ab die alle Zugmöglichkeiten vom Gegenspieler (schwarz hier) darstellen, usw...
Ganz am Ende in den Blättern gibt es dann 3 Möglichkeiten die es zu erkennen gilt: Matt(weiss), Matt(schwarz), Remis. Nun vergibt man an diese Blätter eine Wertung, z.B. 1 für Matt(weiss), 0 für Remis und -1 für Matt(schwarz). Diese Wertung muss nun rekursiv bis in die Wurzel hochgezogen werden, und bildet die Grundlage der KI. Ziel von schwarz ist es ein Matt(weiss) zu erreichen - folglich spielt er immer zum Teilbaum mit der höchsten Bewertung hin, da es dort wahrscheinlicher ist zu gewinnen. Er ist somit hier der Maximierer, und weiss der Minimierer (da er auf -1 = Matt(schwarz) spielt).
Möchte man seiner KI jetzt auch noch beibringen möglichst schnell einen Sieg zu verbuchen, so empfiehlt sich eine Portion A*: Man zählt also den Baum hinab in welchem Teilbaum man den kürzesten Weg bis zu einer positiven trivialen Situation hat (Sieg), und entscheidet sich für diesen. (Das wäre aber nur nen Bonbon ;))

Man braucht für obiges System aber alle möglichen Spielstände! Was fällt einem auf? Genau: Das werden allein schon nach nur 2-3 Spielerwechseln irre viele Knoten! Einen kompletten Schachbaum aufzubauen sollte heutzutage nicht in vernünftiger Zeit schaffbar sein.

Lösung 1) Teilbäume aus der aktuellen Stellung mit vorgegebener Tiefe berechnen. So wird es imho auch gemacht. Das Problem hierbei: In den Blättern sind eher selten echte Endsituationen zu finden. Also kommt man nun an die Stelle die den ganzen Thread lang schon diskutiert wurde (und nur einen Teilaspekt einer KI darstellt ;)) - man muss ein unfertiges Spiel bewerten und das also Grundlage für eine Zahl von -1 bis 1 hernehmen mit der entschieden wird. (Diese Stelle ist vital für die Intelligenz der KI.)
Da kann ich allerdings kein geeignetes Verfahren anbieten, und würde ähnlich vorgehen wie es hier ja schon passiert. (Ideen sammeln + Try&Error)

Lösung 2) Das sog. Alpha-Beta-Pruning. Dies ist eine Verbesserung des Minimax-Algos (hinsichtlich der Laufzeit), da man auf Grund günstiger Konstellationen von vorne herein ganze Teilbäume einfach weglassen kann; also erst garnicht aufstellen muss. Das Verfahren ist jedoch nicht ganz so einfach nachvollziehbar (für Details sei auf Onkel Googel / WiKiPedia / etc. verwiesen) und es wäre wohl auch nicht ausreichend um einen kompletten Spielbaum aufzubauen, da es trotzdem noch zu viele Knoten würden.
Somit böte sich das also eher an um Lösung 1 zu verschnellern bzw. zu verbessern, da man ggf. tiefere Bäume aufbauen kann als ohne A-B-Pruning.


Der goldene Weg wäre also ein partieller Spielbaum mit A-B-Pruning aufgebaut für eine KI die einfach nur gewinnen will, und ohne A-B-Pruning aber mit einer Priese A* für eine KI die schnell gewinnen soll (heisst nach mögl. wenigen Zügen, das Programm ist sicherlich langsamer ;)). Warum nicht A-B-Pruning und A* zusammen? Weil durch das Wegschneiden der Teilbäume ohnehin schon auch schnellere Wege gekillt würden, so dass auch A* nur mittelmäßige Wege finden könnte. A-B-Pruning ist NICHT auf schnellen Sieg ausgelegt, nur auf "überhaupt gewinnen" :).


Versteift euch nicht zu sehr auf die reine Bewertungsfunktion unfertiger Bretter. Die ist zwar sehr wichtig, aber auch nur ein Teilaspekt. Und sie muss schließlich zum eigentlichen Wegfindungsalgo passen ;).



Schönen Gruß,
Fabian
:hi: