Ideen zur Schach KI

[Arnulf]

ob das schon irgenwo erwähnt wurde oder nicht weiß ich nicht - ist mir zu viel gewesen alles zu lesen.

aber ich hab ja mehr geschrieben als nur die figuren zu bewerten.

Jede figur hat nunmal gute positionen und schlechte.
Rein von der stelle am schachbrett her.
Auch kann man in weiterer folge kombinationen von figuren bewerten - wie ich auch schon geschreiben hab.
oder eine bestimmte stellung mit einer figurkombination ( --> 2 oder 3 bauern in kombination - oder ein einzelner bauer wird besonder schlecht bewertet oä..)

Eine Schlagabtausch - wie damentausch oder ähnliches wird sowieso gemacht wenn man dadurch seine stellung verbessert - das ist wohl auch der grund warum man sowas normalerweise macht - oder man wird vom gegner gezwungen dann errechnet sich das aber auch.

Man muß sich langsam herantasten würde ich sagen.
Rein tabelarisches spielen ist schon möglich wenn man es gut macht.
Der einzige sonderfall der wirklich beachtet werden muß ist wohl der könig bzw. schach matt.

Schack matt kann man sozusagen in der rechnung mit 1 millon punkten bewerten.
Bei der bewertung des königs muß man besonders aufpassen, weil man leicht den fehler machen könnte den könig viele punkte zu geben - allerdings würde dann der computer nur noch mit dem könig fahren - weil er so gut ist

Natürlich kommts drauf an was man erreichen will.
Ein Schachprogramm das funktioniert und selbstgeschrieben ist, oder will man fritz nachprogrammieren.
im 2. ten fall schreib ich wohl nix mehr dazu, weil ich nicht wirklich weiß wie schachprogramme geschreiben werden .

Arnulf

[Cicaro]

Zitat von Arnulf:

Natürlich kommts drauf an was man erreichen will.
Ein Schachprogramm das funktioniert und selbstgeschrieben ist, oder will man fritz nachprogrammieren.
im 2. ten fall schreib ich wohl nix mehr dazu, weil ich nicht wirklich weiß wie schachprogramme geschreiben werden .

Also um Fritz nachzuprogrammieren, dazu fehlt mir die Zeit, die ich auch für soetwas nicht verschwenden will.

GUI fürn Schachspiel zu programmieren ist wirklich nicht schwer. Die KI hingegen schon, wie ich schon längst festgestellt habe.

Wie KIs programmiert werden, weiß ich auch nicht, ich kann es mir nur erahnen. Deshalb auch der Thread. Meine Vorstellung davon ist eben (s.o.), dass für die Situation auf dem gesamten Feld jeder Seite Plus- und Minuspunkte vergeben werden und der Zug, dessen Folgestellung mehr Punkte bringt, für die KI eben der bessere ist.

Zum Stichwort [i]Figurenvorteil[i]: ich dachte mir, ich zähle für beide Seiten die Figurenwertigkeiten zusammen und nehme diese Punkte für die Entscheidung der KI (neben anderen Punkten natürlich).

[Tonic1024]

Ja, das ist doch schon ein relativ guter Ansatz...

Ich will mal versuchen die (für mich) sinnvoll erscheinenden Anregungen aus diesem Thread in wenigen Sätzen zusammen zu fassen.

Zunächst solltest du einige (möglichst viele) Züge vorausberechnen. Sagen wir ersteinmal Zugtiefe 2 (der Einfachheit halber) - d.h. weißer Bauer geht einen Schritt vor um einen anderen Bauern zu bedrohen (1. Zug), (schwarzer Zug), weißer Bauer schlägt den Bauern. (2. Zug), (schwarzer Zug). Das wäre der erste Zug (mit einer voreingestellten Zugtiefe von 2 Zügen)in deinem Pool. Das machst du für Alle Figuren auf dem Brett.

Das sind unheimlich viele, klar. Du weisst nun folgendes: Der beste Zug, den du mit einer Zugtiefe von 2 bekommen kannst ist in diesem Pool, du musst ihn nur noch finden. Jetzt kommt deine Bewertungsmatrix zum Einsatz und sucht sich genau den Zug raus, der das beste Ergebnis nach den 2 Zügen Zugtiefe liefert. Wie du das machst ist freilich deine Sache. Dein Punktesystem bildet einen guten (vor allem sehr flexiblen) Ansatz. Es sollten natürlich Figur-Grundwert und Position sowie die Machtstellung der Figur eine Rolle spielen. (Machtstellung meint: Es ist nicht sinnvoll einen Läufer abzutauschen, wenn dieser das halbe Brett kontrolliert - sprich viele Felder bedroht, die dein Gegner gut gebrauchen könnte.)

Jetzt merkst du dir diesen Zug, setzt deine Figur und wartest auf den Gegenzug. Bevor du diese ganze Prozedur noch einmal durchläufst prüfst du ob der Zug von eben immernoch gut ist. (Hat der Gegner bemerkt was du vorhattest und vielleicht den Bauern gedeckt?) Wenn der Zug für "immernoch gut" befunden wurde behälst du die Taktik bei. Ansonsten fängst du wieder Oben an und bildest einen neuen Pool.

Das ist schon einmal ein solider Grundstein für deine KI. Eine fertige kleine KI wenn man so will. Hier wurden noch weitere sinnvolle Ergänzungen genannt, die die KI verbessern bzw schneller machen würden. Aber das kann man mal ins Auge fassen, wenn du soweit bist, denke ich.

MfG

Tonic

[Speedmaster]

Also KI würde ich wenn man das so macht wie bisher Vorgeschlagen nicht nennen, es ist eine Linerare Vorgehensweise die dazu führt das der CG dieselben Züge immer wieder ausführt wenn du z.b. die selbe Eröffnung spielst. Um dies zu verhindern sollte man sich noch mal über meinen Vorschlag den ich ein paar Posts zuvor gepostet habe Gedanken machen.
Allerdings muss man dabei bedenken das man Aufpassen muss das die KI nicht zu gut wird. Durch das Unlinieare Handeln das durch die sich immer Vergrößerte Anzahl an Zügen in der DB verursacht wird( Relativ Unliniear ), kann es leicht passieren das der Computer mal besser wird wie man selber!

Ach hier noch ein kleines Bild wie ich gerne Schach spiele: Bild!!!

[Tonic1024]

Zitat von Speedmaster:

Also KI würde ich wenn man das so macht wie bisher Vorgeschlagen nicht nennen, es ist eine Linerare Vorgehensweise die dazu führt das der CG dieselben Züge immer wieder ausführt wenn du z.b. die selbe Eröffnung spielst. Um dies zu verhindern sollte man sich noch mal über meinen Vorschlag den ich ein paar Posts zuvor gepostet habe Gedanken machen.

Stimmt schon, aber letztlich ist das nur Haarspalterei. Lass ihn mal erstmal soweit sein...

[Edit]
Und ob sie immer wieder die gleichen Züge macht wenn die Umstände gleich sind hängt davon ab wie er die Bewertungsmatrix aufpumpt.

Und ob er sich Taktiken und Eröffnungen, die mal sehr erfolgreich waren, irgendwo in einer Datei wegschreibt (oder gleich variablen Code entwickelt/interpreter benutzt) oder erstmal ein Programm schreibt, gegen dass man überhaupt erstmal sinnvoll spielen kann. Da sind ja schon fast Welten dazwischen.
[/Edit]

[Cicaro]

Ich muss mich ersteinmal für 'ne Weile entschuldigen. Da ich zum einen mit dem Ausprobieren einzelner Züge (in der KI) nicht klar komme und zum anderen im Abiturstress stecke, komme ich nicht an die Arbeit an meiner Schach-KI. Hab' es aber nicht vergessen.

Das könnte also noch etwas dauern, bis ich erste Erfolge melden kann.

[himitsu]

@Cicaro: brauchst dich doch nicht für sowas entschuldigen ... keiner hat 'ne bestimmte Dauer festgelegt, bis wann du fertig sein mußt und bei soeinem Thema sollte man sich eh Zeitlassen ... KI's sind ja nunmal nich innerhalb weniger Minuten geschrieben und in Verbindung mit Schach brauchen sogar die größten Profis Jahre/Jahrzehnte

[Cicaro]

Kann mir jemand vielleicht noch hierbei helfen ?
Sagen wir einfach die KI schaut nur einen Zug voraus. Sie prüft, wie es um ihre Seite steht, wenn sie einen zufälligen Zug macht.

Delphi-Quellcode:

TBoard = class
 public
  Move:TMove;
  Turn:Integer;
  Points:Integer;
  // ...
  procedure GetFigureLeading;
  procedure GetBestMove;
  function MoveAllowed:Boolean;
  procedure DoMove;
 end;

procedure TBoard.GetBestMove;
var
 BestMove:TMove;
 MaxPoints,i:Integer;
begin
 Randomize;
 MaxPoints:=64000;

 for i:=1 to 10 do
  // Erstellung eines gedachten Brettes
  with TBoard.Create(Self) do
   begin
    // KI sucht sich zufällig einen Zug aus
    repeat
     repeat
      Move.A.X:=1+Random(8);
      Move.A.Y:=1+Random(8);
     until Field[Move.A.X,Move.A.Y].ID*Turn>0;
     Move.B.X:=1+Random(8);
     Move.B.Y:=1+Random(8);
     Move:=GetMove(Move.A,Move.B);
    until MoveAllowed;
    // KI macht diesen Zug
    DoMove;
    Turn:=-Turn;
    // Berechnung der Punkte (zunächst nur Figurenvorteil)
    // positives Vorzeichen: Weiß   in Führung
    // negatives      "    : Schwarz "   "
    GetFigureLeading;
    // Entscheidung der KI
    if Points*Turn<MaxPoints then
     begin
      BestMove:=Move;
      MaxPoints:=Points*Turn;
     end;
    Free;
   end;

 Move:=BestMove;
 DoMove;
 Turn:=-Turn;
end;

Was ich hierbei wissen will, ob der Gedankengang so in Ordnung ist, wenn man die anderen verwendeten Methoden nicht in Frage stellt.
Habe ich villeicht etwas nicht beachtet oder irgendwo einen Fehler gemacht. Irgendwie funktioniert diese Prozedur bei mir nicht richtig.

[alzaimar]

IMHO: Nein. Dein Gedankengang ist falsch. Die Bezeichnung 'GetBestMove' auch. Sie findet nicht den besten Zug, sondern nur irgend einen.
Was Du machen solltest:

Delphi-Quellcode:

Function GetBestMove (Board : TBoard; Spieler, Gegner : TSpieler; Level : Integer) : TZug;
Begin
// 1. Erzeuge eine Liste aller möglichen Züge, indem Du über jede Figur iterierst und für jede Figur alle möglichen Züge erzeugst.  
  ZugListe := CreateAllMoves (Board);
  For i:=0 To ZugListe.Count - 1 do begin
// 2. Führe jeden Zug aus und bewerte die sich ergebende Stellung. Das wird nur bei Alpha-Beta-Pruning benötigt.
    Board.Play (ZugListe[i]);
    ZugListe[i].Score := Board.Score;
// 3. Nimm den Zug wieder zurück.
    Board.UnDo (ZugListe[i]);
    End;
// 4. Sortiere die Zugliste anhand der Bewertungen der Zielstellung so, das der 'beste' Zug an erster Stelle steht. Das hilft beim Alpha-Beta-Pruning.
  ZugListe.SortByScore;
// 5. Initialisiere 'SCORE' mit -MAXINT
  Result.Score := -MaxInt;
// 6. Für jeden Zug[i] der Zugliste:
  For i:=0 To Zugliste.Count - 1 do Begin
// 6a.   Führe den Zug aus.
      Board.Play (Zugliste[i]);
// Wenn jetzt  z.B. Schachmatt ist, kann man gleich abbrechen. ZugListe[i].Score enthält ja schon die Bewertung des Matts.
     If Board.Mate Then Begin
        Result := ZugListe[i];
        Break;
        End;
     If Level = MaxLevel Then 
       S := ZugListe[i] 
     Else 
       S := GetBestMove (Board, Gegner, Spieler, Level + 1)
     If Result.Score < S.Score Then Result := ZugListe[i] 
// 6b.    Nimm den Zug[i] zurück
     Board.Undo (ZugListe[i])
    End;
//7. In Result ist jetzt der beste Zug, der mit dieser Stellung möglich ist. Allerdings wollen wir das Vorzeichen umdrehen, da der Vorteil des Spielers der Nachteil des Gegners ist.
  Result.Score := -Result.Score;
End;

Mit anderen Worten: Du führst jeden Zug Z[i] aus und schaust durch einen rekursiven Aufruf nach, was der Beste Zug ist, den der Gegner daraufhin ausführen kann. Die Bewertung dieses Zuges ist dann auch die Bewertung von Z[i] (mit umgekehrtem Vorzeichen).

Bespiel: Zug[i] = Bauer A2-A4... Bester Zug des Gegners = Schachmatt (Bewertung = 10000) --> Zug[i].Bewertung = -100000.

Zu beachten gilt hier der sog. Horizonteffekt. Das o.g. Verfahren arbeitet ja mit einer festen Vorschautiefe (Maxlevel), muss also irgendwann die Vorschau abbrechen. Wenn nun ein scheinbarer Vorteil eines Zuges (z.B. Dame geschlagen) im Folgezug ein Schachmatt zur Folge hat, sieht das Programm das nicht. Dieser Folgezug ist sozusagen jenseits des 'Horizonts'. Das Programm wird also diesen scheinbar optimalen Zug wählen.

Du benötigst also eine Heuristik, um diesen Horizonteffekt zu vermeiden. Dann noch eine Heuristik, um Zugwiederholungen zu vermeiden, ausser, der Rechner ist im Hintertreffen und will somit ein Remis provozieren.

Du nimmst Dir verdammt viel vor, gleich mit Schach anzufangen. Wieso nimmst du nicht erstmal 4-Gewinnt, Dame oder Reversi. Diese verfahren, die Du benötigst (MiniMax, Alpha-Beta-Pruning, Horizonteffektvermeidung, Stellungsbewertung, evolutionäre Optimierung etc.) kannst Du an den reilativ einfachen Spielen ausprobieren und Erfahrungen sammeln. Anschließend ist die Programmierung einer Schach-Engine nicht mehr so schwer, und Du kannst Dich auf die wirklich kniffeligen Aspekte konzentrieren (Mustererkennung, Strategien etc.).

Merke Dir: Deine KI wird entscheidend von der Stellungsbewertung und dem Einsatz von heuristischen Strategiealgorithmen abhängen. Vielleicht schaffst Du es auch noch, das Programm selbstlernend zu machen...

Viel Spass.

[turboPASCAL]

Hallöle,

Hey, da habt ihr euch ja was tolles ausgesucht, ein Schachprogramm .!?
So ein Ding ist doch eigentlich das Schwierigste was es gibt oder?

- Schachbrett bauen (einfach)
- Figuren bauen (einfach)
- Figuren die Regeln beibringen, ich meine damit Bauer 1 Schritt/ laufer diagonal usw. (mittel schwer)
damit der User (sagen wir mal mit den Weissen Fig.) nicht etwas falsches setzen kann
- IK für den Computer basteln (sau schwer), er soll ja auf die Züge vom User reagieren oder ?

Ich hatte mal vor langer Zeit ein Prog. habs noch in meinem Archiv gefunden
das war ein komplettes kleines Schachprog (www.bauer-schweitzer.de).

Die Seite im Internet gibt es noch:
www.bauer-schweitzer.de MiniMax (Schach for Delphi)