| 

.NET C# Java Javascript Exception

2
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.
News:
14.09.2009
arti 41 1 2
5 Antworten
3
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.
14.09.2009
pjacobi 1,1k 2 7
pjacobi 1,1k 2 7
1
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
14.09.2009
licht_micha 364 1 3
Noch mal so als Anmerkung:

Goggel mal nach KI und Schach:
http://www.google.de/search?q=KI+schach
licht_micha 14.09.2009
1
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
14.09.2009
Scout 1,4k 2 8
[quote]recht schnell zu den künstlichen neuronalen Netzen[/quote]
Nein! Fuer Schach oder andere Spiele halte ich Neuronale Netze fuer ungeeignet. Mich wuerde aber interessieren wo und wie sie erfolgreich in Spielen eingesetzt wurden im Vergleich zu anderen Methoden.
knivil 14.09.2009
Warum sollen KNN dafür ungeeignet sein? Ich könnte mir vorstellen dass ein Hopfield-Netz die aktuelle Position erkennt und aus dem antrainierten Wissen den nächsten Zug generiert. Oder dass ein Feedforward-Netzwerk zur Bewertung der Züge verwendet wird (in Kombination/Ergänzung zu anderen Methoden).

Ich hab zum Spass für Tic-Tac-Toe ein neuronales Netz entwickelt das die möglichen Züge bewertet. Läuft nicht schlecht ;)

Über Spiele generell kann ich nichts sagen da ich mich damit nicht beschäftige.
gfoidl 14.09.2009
Hab zufällig was über KI und Spiele gefunden:
http://onlamp.com/pub/a/onlamp/2004/09/30/AIforGameDev.html
gfoidl 16.09.2009
1
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.


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.
14.09.2009
gfoidl 9,4k 3 5
0
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.
14.09.2009
knivil 209 2

Stelle deine Html-Frage jetzt!