Ich habe gestern gegen Fritz Schach gespielt... unglaublich. Ich habe mir sogar mehr Figuren per Editor eingefügt und trotzdem sofort verloren. Ich will jetzt auch eine Schach-KI machen... natürlich nicht so gut wie Fritz aber sie soll einen Menschen halt besiegen. Wie geht man am besten an sowas ran? Man kann ja nicht alle in der Zukunft möglichen Züge testen weil zu viele.

Oh Gott, ein weites Feld, da darfst Du hier keine erschöpfende Behandlung erwarten. Natürlich haben meine Vorredner recht, erst einmal Wikipedia und Google zu befragen. Trotzdem ein paar konkrete Hinweise:

(1) Schachprogramme die z.B. acht Halbzüge vorausrechnen, schauen nicht alle möglichen Zugfolgen an, um zu einer Bewertung zu kommen, sondern nur die dazu nötigen. Viele Zugfolgen kann man vorher abbrechen, ohne dass hier Heuristik oder KI ins Spiel kommt. Der Kerngedanke ist, dass man nicht nach weiteren Widerlegungen eines Zugs suchen muss, wenn man schon eine gefunden hat, die zu einem schlechteren Resultat führt als die bisher beste Wahl des Ausgangszug. Diese äußerst wichtige Erkenntnis wird konkret z.B. in der Alpha-Beta-Suche umgesetzt. Du solltest so etwas mal übungshalber selbst implementieren, vielleicht für ein einfacheres Spiel wie Mühle oder Othello.

(2) Les Dir mal ein existierendes Schachprogramm durch. Zum Beispiel Toga II, nicht sehr groß, nicht sehr kompliziert und in lesbarem C++ geschrieben: www.superchessengine.com/toga_ii.htm.

(3) Wenn Du ein selbstgeschriebenes oder übernommenes Grundgerüst hast, gibt es drei naheliegende "Schrauben" an denen Du drehen kannst:
(a) Die Bewertungsfunktion: Wie soll eine Position auf dem Brett statisch bewertet werden? Wieviel Schachwissen willst Du hier reinstecken? Oder vielleicht doch etwas ganz simples, um Rechenzeit zu sparen und zwei Halbzüge tiefer rechnen zu können?
(b) Die "quiescence analysis", die Kriterien wann das Berechnen von weiteren Zügen abgebrochen werden soll und die Stellung guten Gewissens der Bewertungsfunktion übergeben werden kann. Offensichtlich ist eine feste Berechnungstiefe ganz schlecht, zumindest das Schlagen hängender Figuren und Schachgebote sollten weiter verfolgt werden als ruhige Züge.
(c) Die Vorsortierung für die Alpha-Beta-Suche. Je wahrscheinlicher die besten Züge als erstes betrachtet werden, um so mehr unnötige Berechnungen kann die Alpha-Beta-Suche abschneiden.

Meines wissens geht Fritz genau so vor. Dabei ist es nicht wirklich intelleligent. Es probiert einfach unglaublich viele Züge aus (je nach Schwierigkeitsstufe) und macht dann den Zug der die größte Wahrscheinlichkeit auf einen Sieg hat.

Was interessantes zu KI-Methoden bei Wiki

Man kann ja nicht alle in der Zukunft möglichen Züge testen weil zu viele.

Aber genau das macht ja eine KI ;-) Der PC kann nunmal in ein paar Sekunden um die Millionen Züge probieren. Dabei wägt er Anzahl der Züge bis zum Sieg und die dabei verlorenen Figuren ab.

Alternativ dazu kann man auch ein Programm aufbauen, dass dazu lernen kann. Dann wirst du wahrscheinlich recht schnell zu den künstlichen neuronalen Netzen (Wikipedia) kommen.
Allerdings wird dann die Datenbasis immer größer. Eine Datenbank mit 10-20 Mio. Datensätzen kann ich mir da gut vorstellen.

Grüßle

Im Wiki-Artikel über Schachprogramme ist relativ gut zusammengefasst was für ein solches Programm notwendig. Für die Eigenentwicklung kannst du dich an OpenSource-Projekten orientieren.

• µ-Max: ein minimalistisches Schachprogramm
  
• GNU Chess
  
• Crafty
  
• Rybka: der aktuelle "Großmeister"
  

Man kann ja nicht alle in der Zukunft möglichen Züge testen weil zu viele.

Ohne Brute-Force kommt kein Schachprogramm aus. Eine ausgeklügelte künstliche Intelligenz (KI, bzw AI: artificial intelligence) kann dies jedoch unterstützen bzw. zur Bewertung der Züge verwendet werden.

Wenn du nicht selbst gleich alles programmieren willst kannst du auch "fertige" Zuggeneratoren verwenden und nur die UI selber bauen.

Probiere dich erst an einem einfacheren Spiel aus, z.B. tic tac toe, 4 gewinnt oder Muehle. Zu 4 gewinnt gibt es gute Links zur konkreten KI. Und du solltest nicht zu euphorisch an die Sache herangehen ... es ist ein schwieriges Gebiet.