Gegner Ki und Abfragen beim Schachspiel...

[Multi-Master1988]

Hallo Community!

Also ich plane seit längerem ein Schachspiel allerdings stoße ich hier auf Technische Probleme in der Theorie.

Hier mal ein Bild von einem Schachbrett damit man meine Berechnungen auch verfolgen kann.


http://www.kieler-gelehrtenschule.de/computer-ag/vincent/schachbrett_aufstellung.jpg


Zuerst einmal die groben Grundlagen man versucht mittels der 16 Figuren den Gegenspieler Schachmatt zu setzten d.h. den gegnerischen König bewegungsunfähig zu machen ja und sogar ein unentschieden ist möglich.

Weiß zieht meist zuerst sofern dieser seinen Eröffnungszug nicht den gegnerischen Spieler überlässt aber egal wer anfängt am Anfang gibt es immer 11 Mögliche Eröffnungszug.

Ich hoffe ich konnte zumindest die groben Züge gut erklären und wenn nicht in jeder guten Spiele Sammlung sollte es ein Regel Werk dazu geben.

Zu meinen Theoretischen Problemen:

Mein größtes Problem besteht darin den Gegner eine KI einzubauen ich hab erst gedacht ich könnte sowas evtl. mit Zufalls-Abfragen einbauen nur dann Stoß ich auch das Problem das der Gegner eher Dumm da steht.

Grob:



Figur abfrage (ob diese auch noch da ist)
Abfrage der Möglichen Züge
Und dann per Zufall die Bewegung erstellen


Desweiteren weiß ich nicht genau ob ich bei 64 Feldern x 32 Figuren eine grobe Einsicht in den Abfragen bekomme die wären immerhin 2.048 Abfragen auch nicht grad wenig.

Ich hoffe ihr könnt mir dabei ein wenig helfen.;)

Lg
Multi-Master1988

[R.F.]

Ein Tipp: lass es!
Spätestens wenn es um die KI geht, wirst du merken, wie aufwendig das ganze ist. 2048 Abfragen sind da nur die Spitze des Eisbergs, denn mit jedem Zug ergeben sich jede Menge neue Zugmöglichkeiten und Strategien. Das Problem am ganzen ist nämlich, dass der Gegner nicht nur den aktuellen Zug, sondern auch die darauf folgenden überdenken muss. Ansonsten wär es ja ziemlich einfach, zu gewinnen. Selbst wenn du das außer Acht lässt, wärs, wie du gesagt hast, ein ziemlicher Aufwand.

[R.D.]

Als Anfänger mit einer Schach-KI anzufangen ist auch sehr unglücklich^^

[niR-kun]

Mir würde das auch gar nicht einfallen, wie ich im Maker ein Schach-KI machen würde.

Bei normalen Programmiersprachen würde ich den KI alle möglichen Spielzüge über einen Baum (abstrakter Datentyp) vorher berechnen lassen. Im Spiel selber geht der KI einfach nur die Pointer des Baumes ab, bis er ein Ende (->NULL) findet. :D

[Multi-Master1988]

So hab nochmal ein wenig rumgegoogelt weil mir dies hier selbst zu wenig vorkam:



Weiß zieht meist zuerst sofern dieser seinen Eröffnungszug nicht den gegnerischen Spieler überlässt aber egal wer anfängt am Anfang gibt es immer 11 Mögliche Eröffnungszug.

So nun mal eine Berichtigung:

Für den ersten Zug hat weiss 20 Möglichkeiten (man kann jeden Bauern ein oder zwei Felder nach vorne setzten, zusätzlich kann man die beiden Springer noch bewegen). Schwarz hat dann auch 20 Möglichkeiten zu erwidern.Also ergeben sich für den gesamten ersten Zug 400 theoretische Möglichkeiten.Die Anzahl der weiteren Möglichkeiten ist vom ersten Zug abhängig. Das kann man dann nicht mehr berechnen. (Je nachdem welcher Bauer bewegt wurde, kann man Läufer oder Dame oder König bewegen).

So und das ganze ist nartürlich dann nicht mehr mit dem Maker berrechenbar allein für die ersten vier Züge gibt es ca. 318.979.564.000 verschiedene Möglichkeiten. (Ein zug = schwarz und weiß ziehen)

Generell wäre es aber möglich Schachrätsel mit weniger Figuren einzubauen.;)

Lg
Multi-Master1988

[Wolfskopf]

Es wäre auch im Maker möglich, eine Schach-KI zu entwerfen. Durch verschachtelung von Forks und Variablen kann man sich ja sowas wie nen Array schaffen. Aber ne Schach-KI würde ich nicht mal in ner richtigen und dafür geeigneten Skriptsprache ausführen wollen. Schließlich bedeutet KI in dem Fall nicht nur:

- Standort aller Figuren abfragen
- Alle möglichen Züge abfragen
- den "besten" Zug auswählen und ausführen

sondern auch:
- mehrzügige Strategien des Spielers erkennen und vereiteln
- mehrzügige Strategien selber ausführen.

Ich würde sagen, ein einzelner sitzt da am Ende wahrscheinlich genau so lange dran, wie andere an ihrem Makerspiel... wobei... wohl eher länger ;)

[Multi-Master1988]

@ Wolfskopf

Was die sache auch nicht einfacher macht generell tendier ich eher dazu sachen Vorzugeben so das man den Gegner in einem Zug Matt setzen muss.

[Wolfskopf]

@ Wolfskopf

Was die sache auch nicht einfacher macht generell tendier ich eher dazu sachen Vorzugeben so das man den Gegner in einem Zug Matt setzen muss.
Es soll die Sache nicht einfacher machen, es soll zeigen, dass die Sache generell einfach unmöglich ist. Und für ein "Ein-Zug-Matt"-Rätsel brauch ich keine KI ;)

[Felski]

du könntest einige eröffnungen vorgeben und ab einem gewissen zug die KI nur noch reagieren lassen.

oder du machst es so wie es richtig geht.

du ermittelst alle möglichen züge und bewertest sie nach:
weiteren bewegungsmöglichkeiten der figur
schlagen von gegnern
schützen von eigenen figuren
usw.

anschließend wählst du per zufall einen der höchst bewerteten züge aus.

ganz leicht^^

[Multi-Master1988]

Es soll die Sache nicht einfacher machen, es soll zeigen, dass die Sache generell einfach unmöglich ist. Und für ein "Ein-Zug-Matt"-Rätsel brauch ich keine KI

Unmöglich ist diese sache warschenlich auch wieder nicht nur verdammt schwer momentan.;)

Daher bin ich den Kompromiss ja eingegeangen das ich sachen einfach vorgebe.:D


ganz leicht^^

Das mit sicherheit nicht.;)
Auch bei Vorgegebenen Sachen kann man verschiedene Lösungen finden.

Lg
Multi-Master1988

[Wolfskopf]

Unmöglich ist diese sache warschenlich auch wieder nicht nur verdammt schwer momentan.;)
An Schach-KIs werkeln ganze Teams mehrere Jahre dran und selbst dann sind sie bei weitem nicht perfekt ;)


Daher bin ich den Kompromiss ja eingegeangen das ich sachen einfach vorgebe.:D
Was gibts du vor? Die Züge, die der Computer macht? Da wirst du aber ab Zug 2 ne wahre Freude haben, ob der Anzahl der Züge ;)
Wie du selbst gesagt hast, der Spieler hat am Anfang 20 Möglichkeiten seinen Zug zu machen. Aber alleine bei dem zweiten Zug kommst du zu einem Fall, wo die Fälle ins massig hohe gehen. Ab dem dritten Zug sind die Varianten zu hoch, als dass du sie in den nächsten Monaten eingespeichert kriegst. Das wette ich mit dir :)

Wenn du nen Tipp haben willst: Lass es ;)

[Daos-Mandrak]

Wenn man nur etwas üben will, kann man sich doch an einer simplen KI versuchen. Ich bekomme hier den Eindruck, dass man entweder eine KI auf dem Level eines Schachcomputers entwickeln soll oder es komplett sein lässt.

Ich denke z.B. dass man eine KI scripten könnte, die immer einen einzelnen Zug voraus denkt.

Man trainiert dadurch sein eigenes logisches Denken und sitzt im Gegensatz zu einem richtigen Projekt nur wenige Wochen dran.

[Multi-Master1988]

Wenn man nur etwas üben will, kann man sich doch an einer simplen KI versuchen. Ich bekomme hier den Eindruck, dass man entweder eine KI auf dem Level eines Schachcomputers entwickeln soll oder es komplett sein lässt.

Nein ich möchte hier keine KI eines Schachcomputers mit einbauen sondern
lediglich das hintergrundwisse dazu befragen.;)

Sollt ich sowas einbauen so würde ich spezielle Rätsel dafür planen wo man selber wirklich nur 1-2 Züge hat um den Gegener Matt zu setzten.:)

Selbiges hat Daos-Mandrak auch beschrieben.

Lg
Multi-Master1988

[Corti]

Vom Macher von "Ich und Zitate, die ich nicht verstehe" (http://www.multimediaxis.de/showthread.php?t=128847)
und "Warum macht ihr euch keinen Arbeitsaufwand, den ich nicht einschätzen kann" (http://www.multimediaxis.de/showthread.php?t=128882)
kommt nach langer Wartezeit nun endlich das neuste Werk
"KI ausserhalb meiner Kragenweite" (http://www.multimediaxis.de/showthread.php?t=128915).
If you only see one movie this year that revolves around thematische
Fehleinschätzung des eigenen Könnens, make it this one.

De de, dede dede ...~ (Imagine Requiem for a Dream Maintheme here)

Diesen Herbst, nur im Kino und auf Kino.to(lle Viren zerbumsen Ihren PC)

[Dhan]

Generell mal als Frage, kannst du überhaupt selbst einigermaßen professionel Schach spielen? Der übliche Ansatz für eine komplexere KI ist es, ihr die eigenen Taktiken beizubringen - und da eine KI oft holzig ist, muss man ihr meist verdammt gute Taktiken füttern.



Bei normalen Programmiersprachen würde ich den KI alle möglichen Spielzüge über einen Baum (abstrakter Datentyp) vorher berechnen lassen. Im Spiel selber geht der KI einfach nur die Pointer des Baumes ab, bis er ein Ende (->NULL) findet. :D
Üblicherweise erzeugen Spiele exponentiell viele Züge. Die Methode funktioniert bei sehr einfachen Spielen, schon bei wesentlich simpleren Spielen als Schach versagt sie jedoch.


So und das ganze ist nartürlich dann nicht mehr mit dem Maker berrechenbar allein für die ersten vier Züge gibt es ca. 318.979.564.000 verschiedene Möglichkeiten. (Ein zug = schwarz und weiß ziehen)
Jepp. Brute Force nennt man nicht umsonst "brute"

Es wäre auch im Maker möglich, eine Schach-KI zu entwerfen. Durch verschachtelung von Forks und Variablen kann man sich ja sowas wie nen Array schaffen. Aber ne Schach-KI würde ich nicht mal in ner richtigen und dafür geeigneten Skriptsprache ausführen wollen. Schließlich bedeutet KI in dem Fall nicht nur:

- Standort aller Figuren abfragen
- Alle möglichen Züge abfragen
- den "besten" Zug auswählen und ausführen

Wenn das nur einen oder zwei Züge berechnet, besiegt ein Anfänger die KI locker - aber für Schach als sowas wie ein Minispiel tauglich.

Frage ist nur generell, ob man sich den großen Aufwand machen will, statt ein situierteres Spiel zu integrieren, Tactic-KS wie in Bahamut Lagoon bzw auf dem Maker First Fantasy

@Corti: Nee, nicht mal im Ansatz witzig.

[Wolfskopf]

Wenn das nur einen oder zwei Züge berechnet, besiegt ein Anfänger die KI locker - aber für Schach als sowas wie ein Minispiel tauglich.

Wie ich es schon mal oben schrieb:
An komplexen Schach-KIs sitzen ganze Teams Monate mit dafür deutlich besser geeigneten Programmen. Mehr als so eine simple KI wirst du mit dem Maker nur schwerlich hinbekommen, zu Mal du irgendwann das Problem kriegen wirst, dass er nicht nur ewig rechnen wird, sondern er im Maker das Event selbst kaum noch öffnen können wird.
Mit den neueren Makern kriegst du es dann vllt noch besser hin, indem du es "extern" berechnen lässt und nur den Zug als Variablen zurück gibst. Aber auch da wirst du kaum über einfache KIs hinauskommen.

Wenn man Spiele machen will, dann eher eingeschränkte Spiele wie Mühle, Dame oder sowas. Da hat man dann ne gute Chance, durch so einfache KI gute Ergebnisse zu erzielen, da die Möglichkeiten einfach begrenzt sind. Aber dadurch, dass Schach halt einfach derart komplex ist (ich denke nur an Strategien, wie eine Figur zu opfern, um damit irgendwo einen Freiraum für andere zu schaffen), wächst die Komplexität der KI eben exponentiell mit. Mehr als eine grundlegende Situationsbezogende KI wirst du da im Maker nicht hinbekommen. Und selbst dann gilt wie die letzten Male:

Aufwand >>>>>>>>>>> Ergebnis --> Sein lassen und Alternativen suchen.

[Multi-Master1988]

Generell mal als Frage, kannst du überhaupt selbst einigermaßen professionel Schach spielen?

Jawohl ich spiel auch bei unserem Ortsansässigen Schachklub bei kleineren Turnieren mit.;)

[Cherry]

Mit einem Patch, wo man eine Skriptsprache verwenden kann, wird das ganze natürlich viel einfacher. Konkret rede ich vom Power Patch, weil der DestinyPatch ja afaik noch keine Kontrollstrukturen in Skripten unterstützt.

Und wenn der Power Patch an sich zu langsam ist, kannst du immernoch in C++ eine DLL schreiben und die vom Power Patch aus aufrufen.

[Dhan]

Mit den neueren Makern kriegst du es dann vllt noch besser hin, indem du es "extern" berechnen lässt und nur den Zug als Variablen zurück gibst. Aber auch da wirst du kaum über einfache KIs hinauskommen.
Also ich muss sagen, dass ich den XP bisher kaum benutzt hab und Ruby nicht kenne aber gerade weil Ruby-Syntax ja tatsächlich als Hochsprache benutzt wird, müsste das doch aufs gleiche rauslaufen ob ichs extern hab oder intern? (Das is tatsächlich von meiner Seite eine Frage)


Wenn man Spiele machen will, dann eher eingeschränkte Spiele wie Mühle, Dame oder sowas.
Hast du da generell Erfahrung? Ich selbst hab mich nie groß mit beschäftigt, Mühle seh ich machbar aber auch für Dame bräuchte es doch schon so einiges um die KI auch nur einigermaßen wettbewerbstauglich zu machen, oder? (gehen wir davon aus, dass wir uns nicht in einem Maker befinden sondern in einer aktuellen Hochsprache)



Jawohl ich spiel auch bei unserem Ortsansässigen Schachklub bei kleineren Turnieren mit.;)
Ah, das is keine verkehrte Basis. Da fallen dann auch die 3 Milliarden Möglichkeiten weg - ich spiel zwar wie gesagt selber kein Schach aber in Schulzeiten hab ich zwei Profis beim Spiel zugesehen und so wie ich das sehe, hats ja nur ne handvoll sinnvoller Eröffnungen oder man ist tot.
Du wirst auch diese Bewertungen kennen, Bauer = 1, Turm = 5, Dame = 9 usw, die für einen Profi zwar nur Anhaltspunkte sind, aber gerade für einen Computer ideal sein dürften.
Wie schon genug Leute gesagt haben, du wirst keine Schach-KI hinbekommen aber ich finds trotzdem sinnvoll für dich, dich damit zu beschäftigen, das verbessert deinen Umgang mit Algorithmen.
Dementsprechend hab ich auch die Bewertungen gebracht - ein Algorithmus für sowas wie Schach würde die Situation wahrscheinlich tatsächlich recht momentan betrachten, wobei er niemals alle Möglichkeiten berechnen würde - er würde genau wie ein Mensch kurzfristige Ziele setzen. Opfere ich jetzt diese und jene Figur um dort eine Schneise zu schlagen, die meinem Turm erlaubt, direkt ins Feindesland zu ziehen und alles mögliche zu bedrohen?
Er würde nur eine geringe Zahl solcher Taktiken nehmen und einige essentielle Züge berechnen. Bewertungen sind da dann das A und O, mit dem Array wurds ja weiter oben schon angesprochen, der Computer würde die wahrscheinlichste Stellung nach den kurzfristigen Taktiken analysieren und der Gesamtsituation einen Wert zuweisen, eben eine Bewertung anstellen.

So stell ich mir das jedenfalls vor, das wär mein intuitiver Ansatz. Denk ein bisserl drüber nach, dann merkst du, wie ungeheuerlich schon bei diesem Ansatz das wäre, was der KI gefüttert werden müsste - du müsstest ganze Bücher "Wie spiele ich Schach" in Code umsetzen mit dieser und jener Extraklausel, selbst wenn das Ding nur mit Leuten, die von Schach grad mal die Regeln kennen, mithalten können soll



Und wenn der Power Patch an sich zu langsam ist, kannst du immernoch in C++ eine DLL schreiben und die vom Power Patch aus aufrufen.
Das interessiert mich an der Stelle dann doch - wie ist so eine DLL aufgebaut? Einfach im Prinzip eine .c-Datei? Wie werden die Variablen ausgetauscht? Schnappt sich das Programm einfach Variablen, die die RPG_RT in den Kurzspeicher geschrieben hat oder wie?

[elvissteinjr]

Das interessiert mich an der Stelle dann doch - wie ist so eine DLL aufgebaut? Einfach im Prinzip eine .c-Datei? Wie werden die Variablen ausgetauscht? Schnappt sich das Programm einfach Variablen, die die RPG_RT in den Kurzspeicher geschrieben hat oder wie?
Generell gilt für eine DLL dass man Funktionen hat, die bestimmte Rückgabewerte haben. Die Funktionen werden also vom Programm in der DLL ausgerufen und von ihr ausgeführt, die DLL gibt dann einen Wert zurück, falls die Funktion kein void ist.


bool __stdcall HarmonyPlaySoundEx(char* filename, int volume, int speed, int pan)
{
return 1;
}

So würde beispielsweise in einer Harmony DLL der Befehl PlaySound aussehen, wenn es der RPG_RT einfach nur sagt dass es geklappt hat(return 1(true)), aber nichts gemacht hat.

Wie man jetzt die Funktionen einer DLL aufruft hängt ganz von der Programmiersprache des Programms ab.

Das war jetzt ein ganz simples Beispiel. Das Teil lässt sich so natürlich nicht als DLL kompilieren, erklärt aber das wesentliche Prinzip.
Über Google findet man noch viele weitere nützliche Infos.;)

[Cherry]

Das interessiert mich an der Stelle dann doch - wie ist so eine DLL aufgebaut? Einfach im Prinzip eine .c-Datei? Wie werden die Variablen ausgetauscht? Schnappt sich das Programm einfach Variablen, die die RPG_RT in den Kurzspeicher geschrieben hat oder wie?

Du schreibst ein Power-Patch-Plugin in irgendeiner Sprache, wie etwa C++. Eine Anleitung ist beim Power Patch dabei. Da stellst du dann Funktionen bereit, die durch den Power Patch aufgerufen werden können. Dabei kannst du beliebig viele Werte als Parameter entgegennehmen und auch beliebig viele zurückgeben (im Gegensatz zu den meisten Sprachen erlaubt Lua - die Skriptsprache die im PP verwendet wird - mehr als einen Rückgabewert). Außerdem kannst du aus deiner Funktion heraus die Powerpatch-Funktionen GetVar und SetVar aufrufen, mit denen du Variablen und Switches lesen und ändern kannst.

Zeph macht auf dieser Basis ein AKS, weil die KI dadurch einfacher einzubauen ist als wenn alles mit Eventcode wäre, außerdem wird kompilierter Code natürlich schneller ausgeführt als interpretierter Eventcode.

mfG Cherry