M
UCI-Schach-Engine, die zweite.
Dass beim ersten Versuch nicht gleich ein Fritz daraus werden konnte, war wohl naheliegend.
Ursprünglich nur elementaren Minimax verwendet -> Für 3 Halbzüge rechnete das Ding rund eine Minute.
Dann auf Alpha_Beta Suche umgestellt -> Immerhin 5 Halbzüge in 8 Sekunden Rechenzeit.
Mehr war beim ersten Versuch nicht drinnen, alle mir bekannten Programmiertricks haben da nicht mehr recht weitergeholfen.
Also das Gleiche von vorne, und etwas gründlicher durchdacht.
Profi-Engines schaffen 13 Halbzüge und mehr in 8 Sekunden, und 'unter der Haube' wird auch dort mit Alpha_Beta Suche und weiterentwickelten Varianten davon (Negascout, Nullzugpruning etc.) gearbeitet, deren Implementierung mir erstmal noch zu schwierig erscheint.
Zielsetzung wären diesmal 7 Halbzüge in 8 Sekunden, was für mich als Hobby-Programmierer schonmal zufriedenstellend wäre.
Bei Schach hat man leider das Problem, dass mit jedem Halbzug Suchtiefe, den man dazunimmt, die Anzahl der zu prüfenden Stellungen überaus geschwind explodiert. (nimmt man an, dass in einer 'durchschnittlichen' Stellung ca. 40 Züge möglich sind, auf die der Gegner dann jeweils widerum mit ca. 40 verschiedenen Zügen antworten kann, heißt das im Klartext, dass bereits
in einer Suchtiefe von 5 ca. 40 x 40 x 40 x 40 x 40 = rd. 100 Millionen mögliche Folgestellungen sich ergeben können.) Zum Glück lassen sich mit Alpha_Beta Algorithmus (und einer entsprechend komplexen Bewertungsfunktion) rund 90% davon wegprunen, aber auch dann müssen immer noch 10 Millionen Mal Zugtabellen generiert und 10 Millionen Stellungen bewertet werden.
Den größten Einfluss auf die Performance haben so gesehen der Zuggenerator sowie die Bewertungsfunktion (die einerseits so komplex wie möglich und andererseits eine so kurze Laufzeit wie möglich haben muss, damit Alpha_Beta erfolgreich prunen kann), bei den beiden Funktionen geb' ich bei meinem zweiten Versuch mein bestes Und wie's aussieht, wird's auch besser. Zuggenerator ist erstmal dreimal so schnell wie der alte. (Hauptsächlich nehm ich QueryPerformanceCounter zur Bestimmung der Laufzeit her? Ist doch in Ordnung?)
thx für Tipps
(und lieber einen schlampig implementierten Bit-Sort- als ein perfekt implementierten Bubble-Sort Algorithmus Das ist jetzt auch klar.
mfg