Dagaz: Ein neuer Anfang

Es läuft nach Süden und kreist nach Norden, kreist, um mit dem Wind zu rennen
Und nach seinen Kreisläufen kehrt der Wind zurück;
Alle Flüsse münden ins Meer - und das Meer fließt nicht über,
Zu dem Ort, wo die Flüsse fließen, - Dort fließen sie weiter;

Das Buch der Prediger

1998 wurde eine für diese Zeit völlig einzigartige Anwendung entwickelt, mit der Sie den Prozess der Entwicklung eines abstrakten Brettspiels (oder Puzzles) auf eine kleine Textbeschreibungssprache reduzieren können, die vage an Lisp erinnert. Dieses Projekt hieß Zillions of Games . Es sorgte bei Fans von Brettspielen für Furore. Derzeit wurden mit dieser Technologie über 2.000 Anwendungen erstellt.

Es wurde schnell klar, dass ZoG viele Nachteile hat. Ich habe bereits in Habr darüber geschrieben und werde mich nicht wiederholen. Lassen Sie mich nur sagen, dass die Entwickler die Funktionen einer großen Anzahl vorhandener Spiele nicht berücksichtigt haben und einige wichtige Optionen fest programmiert wurden, so dass ihre Änderung äußerst problematisch wurde. Greg Schmidt versuchte 2007, die Situation durch die Veröffentlichung des Axiom Development Kit zu korrigieren, aber seine enge Integration in ZoG erlaubt nicht, alle Probleme zu lösen.

Projekt Ludi wies auf neue Grenzen hin und verwendete die universelle Spiel-Engine und genetische Algorithmen, um den Entwicklungsprozess neuer Brettspiele zu automatisieren. Leider wurde dieser Ansatz ursprünglich als bewusste Vereinfachung der Spielmechanik und des Niveaus der eingesetzten KI ins Auge gefasst. Die Diskussion der Ziele dieses Projekts würde den Rahmen dieses Artikels sprengen, aber einige seiner technischen Lösungen dienten zweifellos als Ausgangspunkt für meine eigene Entwicklung.

Mein Ziel ist die Entwicklung einer vielseitigeren und benutzerfreundlicheren "Engine" für die Erstellung abstrakter Brettspiele. Ich habe fast ein Jahr lang die Möglichkeiten von ZoG und Axiom studiert und viel über deren Grenzen gelernt. Ich denke, ich kann ihre Probleme lösen, indem ich eine universellere und plattformübergreifendere Lösung schaffe. Über den Fortgang der Arbeiten an diesem Projekt werde ich berichten.

Offenheit und Modularität

Möglicherweise ist der Hauptnachteil von ZoG seine Schließung. Das Produkt wurde "einmal und für immer" unter einer einzigen Plattform - Windows - zusammengestellt. Wäre es Open-Source-Code, könnte man versuchen, ihn unter Linux, Android, iOS ... zu portieren. Ein weiteres Problem ist seine Monolithizität.

In ZoG gibt es die Anfänge der Modularität, die die Verbindung zur Spiele-DLL ermöglicht, einschließlich benutzerdefinierter Implementierungen der KI. Axiom geht noch einen Schritt weiter und ermöglicht es Ihnen, Anwendungen im Modus Autoplay auszuführen, ohne den ZoG-Kernel zu verwenden. Ungeachtet der schwerwiegenden Einschränkung dieser Lösung (Unterstützung von Anwendungen nur für zwei Spieler) zeigt dieses Beispiel, wie hilfreich Modularität wäre! Die Möglichkeit, ein Spiel mit zwei Bots (mit unterschiedlichen KI-Einstellungen) zu organisieren und Statistiken über eine große Anzahl von Spielen zu sammeln, kann nicht überschätzt werden. Aber wie viel besser wäre es, wenn das Produkt vollständig modular wäre!

• Generierungsmodul verschieben
• Ausführungsmodul verschieben
• Steuermodul
• AI-Modul
• Visualisierungsmodul

Alle Arbeiten, die die Spiele beschreiben, müssen vom Modul zur Erstellung von Zügen ausgeführt werden. Dies ist das „Herz“ des Projekts. Durch die Übertragung aller mit dieser Funktion nicht verbundenen Aufgaben auf andere Module wird dies so einfach wie möglich. Sie können dieses Modul verbessern, ohne auf AI-Probleme und Benutzerinteraktion zu achten. Sie können das Format der Beschreibung von Spielen vollständig ändern oder die Beschreibungen im Format von ZoG, Axiom und Ludi unterstützen. Modularität ist die Basis der Flexibilität der Lösung!

Das Bewegungsausführungsmodul ist der Verwalter des Spielzustands. Informationen zum aktuellen Spielstand werden bei Bedarf an alle anderen Module übertragen. Aus Gründen, die ich im Folgenden erläutern werde, muss der Ausführungsfortschritt das Generierungsmodul durchlaufen, dessen Aufgabe die Bildung eines Befehls im Hinblick auf die Modulausführung ist. Die Aufgabe des Bewegungsgenerierungsmoduls ist auch die primäre Konfiguration des Spielraums basierend auf der Beschreibung des Spiels.

Das Steuermodul ist in der Tat die Anwendung selbst. Es fragt das Zugerzeugungsmodul nach einer Liste möglicher Züge und ändert den Spielstatus, wobei der ausgewählte Zug an das Zugausführungsmodul übergeben wird. Das Steuermodul kann angeschlossen werden, um einen oder mehrere KI-Bots zu spielen. So viele wie Sie brauchen (und möglicherweise anders)! Die Art der Steuerung richtet sich nach der Aufgabenteilung. Dies kann eine automatische Wiedergabe zum Sammeln von Spielstatistiken, ein Spieleserver (der mehrere Statusspeicher steuern kann und eine große Anzahl von Spielsitzungen leitet) oder einzelne Anwendungen zum Offline-Spielen sein.

Die Möglichkeit, verschiedene AI-Implementierungen miteinander zu verbinden, verbessert die Qualität des Spiels. Es versteht sich, dass die Module für das Schach- und Go-Spiel unterschiedliche Ansätze verwenden sollten. Spiele mit unvollständigen Informationen und Spiele mit zufälligen Daten erfordern ebenfalls eine individuelle Herangehensweise. Die universelle Implementierung von KI wird in allen Spielen gleich schlecht sein! Die modulare Verbindungs-KI ermöglicht den Vergleich der „Stärke“ der Algorithmen, einschließlich eines Spielemodus „miteinander“. Da die KI-Architektur vom Speicherstatus des Spiels getrennt ist, kann eine Instanz des Spielebots eine unbegrenzte Anzahl unterstützen von Spielsitzungen gleichzeitig.

Die Visualisierung des Spielprozesses kann ebenfalls variiert werden. Das erste, was mir in den Sinn kommt, sind 2D- und 3D-Implementierungen. Die Plattform, für die die Anwendung entwickelt wird, ist ebenfalls wichtig. Weniger offensichtlich ist, dass Visualisierung ein wichtiger Teil des Spiels sein kann! Zum Beispiel ist es im Spiel Surakarta völlig unübersehbar, Teile zu nehmen, wenn die Bewegungen nicht richtig animiert sind.


Im Allgemeinen scheint Modularität eine gute Idee für ein solches Projekt zu sein, und Open Source Code ermöglicht es jedem, der sich an dem Projekt beteiligen möchte. Gegenwärtig setze ich mich nicht zu kommerziellen Zwecken, denke aber, dass ich auf Wunsch einen Weg finden werde, Geld zu verdienen, ohne den Quellcode zu schließen.

Der Spielraum

Bevor Sie mit der Show beginnen, müssen Sie die Bühne einrichten. Das Brett ist nicht nur ein Ort, an dem die Teile angeordnet sind. Daneben kann die Bewegungsrichtung der Spielsteine ​​bestimmt werden (in der Tat die Verbindungen zwischen den Brettpositionen), Spielfelder (z. B. Bereiche zur Umwandlung von Spielsteinen), verbotene Felder usw. So sieht die Definition des Schachbretts in der ZoG-Implementierung aus:


Möglicherweise stellen Sie fest, dass neben den Spieleinstellungen auch die mit der Visualisierung verbundenen Einstellungen vorhanden sind. Ich bin fest davon überzeugt, dass diese Einstellungen nicht hierher gehören. Bei der Implementierung eines Visualisierungsmoduls können mehrere Einstellungen verwendet werden, und möglicherweise sind unterschiedliche Einstellungen erforderlich. Darüber hinaus können Simulationsspiele ohne Visualisierungsmodul ausgeführt werden (wie Autoplay in Axiom). Da Axiom zur Visualisierung von ZoG verwendet wird, enthält die Definition nichts Überflüssiges:


Leider hat Axiom auch keine Möglichkeit, Spielzonen zu bestimmen (die Position der Spielzonen muss manuell im Code festgelegt werden). Dies ist nicht die einzige Vereinfachung von Axiom. Die Definition der Platine in diesem Projekt darf nicht mehr als ein Raster enthalten, und dieses Raster muss zweidimensional sein. Die so definierte Karte ist ein eindimensionales Array, aber zur Vereinfachung des Programmierers werden Synonyme für jeden der Räume wie folgt definiert:


Verglichen mit dem flexibleren Schema der Rasterdefinition in ZoG sind diese Einschränkungen ziemlich unangenehm (insbesondere angesichts der Tatsache, dass das auferlegte Benennungsschema diese Felder zum Zwecke der Visualisierung verwendet hat). Glücklicherweise ist es möglich, eine Tafel beliebiger Form zu definieren. Sowohl Axiom als auch ZoG bieten die Möglichkeit, jede Position auf dem Board elementweise zu identifizieren und die Verknüpfungen zwischen beliebigen Positionspaaren zu bestimmen. Mit diesem Ansatz können wir eine Karte mit einer beliebigen Topologie definieren. Der einzige Nachteil ist die extreme Ausführlichkeit und Komplexität der Beschreibung.

Zusätzlich zur Position der Spielsteine ​​auf der Tafel und in der Reserve sollte das System die Möglichkeit haben, Attribute für einzelne Spielsteine ​​und für die Felder auf der Tafel zu speichern. Ein gutes Beispiel für die Notwendigkeit, die Attribute einer Regel des „ Rochierens “ im Schach zu verwenden . Dies ist ein schwieriger Zug, der die gleichzeitige Bewegung von König und Turm beinhaltet, vorausgesetzt, dass sich keine dieser Figuren bewegt hat, bevor dieser Zug ausgeführt wurde. Ein Attribut könnte verwendet werden, um ein Boolesches Tag zu speichern, das anzeigt, ob sich das Teil jemals bewegt hat. Feldattribute können auch einige interessante Anwendungen finden.

Es sollte beachtet werden, dass Attribute nicht nur Variablen sind, sondern Teil des Spielstatus. Ein Attributwert kann durch die Ausführung einer Runde (einschließlich des AI-Moduls) geändert werden und sollte für alle nachfolgenden Runden verfügbar sein, jedoch nicht für Runden, die in einem anderen Zweig des Spiels ausgeführt werden. Derzeit unterstützt ZoG das Speichern von Booleschen Attributen von Teilen. Axiom-Speicherattribute werden nicht unterstützt, aber Sie können der Definition der Karte eine Beschreibung der Variablen und Arrays hinzufügen. Diese Variablen können verwendet werden, z. B. Zähler für die Anzahl der erfassten Teile:

 {board 5 18 {grid} {variable} WhitePieces {variable} BlackPieces board} 

Eine weitere Einschränkung von ZoG und Axiom ist die Regel, dass jede Position der Tafel nicht mehr als ein Stück enthalten darf. Wenn ein Teil einen Zug zu einer Position vollendet, die von einem anderen Teil besetzt ist, wird das Teil, das zuvor die Position besetzt hatte, automatisch als "gegessen" betrachtet. Diese Regel passt gut zum Schachprinzip und dient der Vereinfachung der Beschreibung dieses Spiels, erschwert jedoch die Implementierung von Spielen wie " bashni checkers " und " tavreli ".



In diesen Spielen können Stücke in "Spalten" angeordnet werden. Eine solche „Säule“ kann zusammen als ein Stück bewegt werden. Nach einiger Überlegung entschied ich, dass es besser ist, die automatische Implementierung der Schach-Erfassung nicht aufzugeben, sondern die Mechanismen zum Verschieben von Gruppen von Stücken zu verbessern. In der Tat können Sie für die Implementierung der „Säulen“ immer eine andere Dimension hinzufügen (dies ist besonders einfach, solange das Visualisierungsmodul vom Bewegungserzeugungsmodul und von der KI getrennt ist und Sie eine beliebige Logik verwenden können zum Rendern der dreidimensionalen Tafel in ihre zweidimensionale Visualisierung). Ein weiteres Argument für diese Entscheidung war, dass die „hoch gestapelte“ Bewegung von Teilen nicht die einzige Art der Gruppenreise ist. Beispielsweise können in „ Pentago “ Brettfragmente zusammen mit den darauf montierten Stücken gedreht werden.


Zusammenfassend kann ich sagen, dass ich für mein Spiel-Framework alles Gute aus ZoG, Axiom und Ludi herausgesucht habe und alles hinzufüge, was meiner Meinung nach fehlt.

Generation bewegen

Die Generierung von Verschiebungen ähnelt der nicht deterministischen Programmierung . Die Aufgabe des Bewegungsgenerators besteht darin, auf Anfrage eine Liste aller möglichen Bewegungen von der aktuellen Position aus bereitzustellen. Welcher Zug aus dieser Liste von einem Spieler oder einer KI ausgewählt wird, ist nicht ihre Funktion. Mal sehen, wie die Erzeugung von Zügen in ZoG erfolgt. Als Beispiel nehmen wir das Makro zur Erzeugung von Zügen für ein Stück mit großer Reichweite (eine Königin oder ein Bischof). So wird es bei der Bestimmung der Züge für diese Teile verwendet:

 (piece (name Bishop) (image White "images\Chess\SHaag\wbishop.bmp" "images\Chess\wbishop.bmp" Black "images\Chess\SHaag\bbishop.bmp" "images\Chess\bbishop.bmp") (moves (slide ne) (slide nw) (slide se) (slide sw) ) ) 

Als Parameter wird einem Makro die Bewegungsrichtung auf der Platine übergeben. Wenn Sie nicht die Möglichkeit in Betracht ziehen, neue Figuren auf dem Brett zu installieren, sieht die Erzeugung eines Zuges einfach aus. Für jede Figur auf dem Brett werden alle möglichen Züge nach den Regeln berechnet. Dann beginnt die Magie ...

Jede der Definitionen kann der Liste eine Reihe von möglichen Zügen hinzufügen! Das Hinzufügen eines Zuges zur Liste erfolgt mit dem Befehl add (wobei gleichzeitig jedes bewegliche Teil auf dem Brett positioniert wird). Ich habe bereits darüber geschrieben, wie schlecht diese architektonische Lösung ist. Der Befehl zur Bildung des Zuges sollte von den Befehlen zur Manipulation von Stücken (wie in Axiom) getrennt werden. Mal sehen, wie das Makro funktioniert:

 (define slide ( $1 (while empty? add $1 ) (verify not-friend?) add )) 

Zuerst wird die Verschiebung von einer Zelle in der gegebenen Richtung ausgeführt, dann wird in einem Zyklus der erreichte Raum auf das Fehlen der darauf befindlichen Teile überprüft, eine Bewegung wird gebildet und die Anordnung schreitet in der gleichen Richtung zu einer anderen Zelle fort. Wenn Sie hier anhalten, kann das Teil durch leere Zellen "gleiten", aber wie können Sie feindliche Teile nehmen?

Sehr einfach! Nachdem wir den Befehl verify ausgeführt haben und überprüft haben, dass das Feld nicht von einem befreundeten Teil belegt ist, bilden wir einen weiteren Befehl add, der den Verschiebevorgang abschließt. Wenn sich in dieser Zelle eine gegnerische Figur befunden hat, wird sie automatisch genommen (wie auf einem Feld des Spielbretts kann man zu einem Zeitpunkt nicht mehr als eine Figur haben). Wenn das Teil befreundet war, wird die Berechnung des Zuges mit dem Befehl verify abgebrochen (ein Verstoß gegen die in diesem Befehl angegebenen Bedingungen beendet sofort die Berechnung des aktuellen Zuges).

Sowohl in ZoG als auch in Axiom kann man nur die eigenen Figuren bewegen (oder besser gesagt, es ist möglich, die gegnerischen Figuren zu bewegen, aber nur, wenn dies in der Berechnungsmethode für einen Zug einer eigenen Figur angegeben ist). Ich finde dies eine äußerst unbequeme Einschränkung, da es viele Spiele gibt, in denen Sie die gegnerische Figur direkt bewegen können (zum Beispiel in „ Stavropol Checkers “). Es wäre konsistenter, die Bewegungsberechnung für alle Teile durchzuführen, unabhängig von ihrer Zugehörigkeit. In dem Makro, das den Zug bestimmt, müsste nur ein Häkchen hinzugefügt werden, damit nur die eigenen Figuren bewegt werden können:

 (define slide ( (verify friend?) $1 (while empty? add $1 ) (verify not-friend?) add )) 

Wichtig ist die Fähigkeit, einen Zug auszuführen, der aus mehreren „Teilzügen“ besteht. Bei der Implementierung von Entwürfen wird diese Fähigkeit verwendet, um "Ketten" -Erfassungen durchzuführen:

 (define checker-jump ($1 (verify enemy?) capture $1 (verify empty?) (if (not-in-zone? promotion-zone) (add-partial jumptype) else (add-partial King jumptype) ) ) ) 

Der Teilbewegungsbefehl wird mit add-partial gebildet (für diesen Befehl sowie für den Befehl add gibt es eine Variation der Bewegung mit „Transformation“ der Teile). Ein solcher Zug ist immer Teil eines größeren, zusammengesetzten Zuges. In der Regel wird für nachfolgende Züge ein "Modus" eingestellt, den die Fortsetzung implementieren soll. In Checkern kann eine Erfassung nur mit den folgenden Erfassungen fortgesetzt werden, jedoch nicht mit einer „weichen“ (nicht erfassenden) Bewegung.


Ein solches System zur Beschreibung der Regeln ist sehr flexibel, aber manchmal ist eine komplexere Logik erforderlich. Wenn das Teil beispielsweise während des "teilweisen" Fortschritts nicht erneut durch ein zuvor durchquertes Feld laufen soll, ist es logisch, die mit Positionen auf der Tafel verbundenen Flags zu verwenden. Nachdem wir einen Raum besucht haben, setzen wir eine Flagge, um anschließend nicht wieder in diesen Raum zu gehen:

 (verify (not-position-flag? my-flag)) (set-position-flag my-flag true) 

Zusätzlich zu Positionsflags können Sie in ZoG globale Flags verwenden. Diese Funktionen dürfen nicht mit den Attributen von Teilen verwechselt werden. Im Gegensatz zu letzteren sind diese nicht Teil des Spielstatus. Leider können sowohl Attribute von Teilen als auch Flags in ZoG nur boolesch sein (in Axiom werden Attribute nicht einmal unterstützt). Diese Einschränkung erschwert die Durchführung von Operationen, die mit den verschiedenen Zählarten verbunden sind. Zum Beispiel musste ich in diesem kleinen Puzzle ein Paar boolescher Flaggen (die genaue Zahl, die ich nicht brauchte, solange die Teile mehr als eine waren) verwenden, um Teile zu zählen, die in einer Gabel gefangen waren.

Eine andere Sache, die behoben werden muss, ist das Fehlen eines klaren „Lebenszyklus“ bei der Ausführung des Umzugs. Alle Flags werden automatisch zurückgesetzt, bevor der Umzug gestartet wird. Es ist jedoch einfacher, die Initialisierungsphase eindeutig zu identifizieren. Meiner Meinung nach sollten bei der Berechnung des Umzugs die folgenden Phasen auftreten:

1. Initialisierung von Variablen und Überprüfung der Voraussetzungen für den Composite Move
2. Initialisierung von Variablen und Überprüfung der Voraussetzungen für die Teilverschiebung
3. Erzeugung des Teilzugs
4. Überprüfung der Nachbedingungen des Teilzuges
5. Generieren, Abschließen und Überprüfen der Nachbedingungen des zusammengesetzten Verschiebens
6. Überprüfung der Abbruchbedingungen des Spiels

Die Gruppe von Schritten vom zweiten bis zum vierten Schritt in der vollständigen zusammengesetzten Bewegung kann viele Male wiederholt werden. Die Idee der Vor- und Nachbedingungen, die ich Invarianten nenne, habe ich aus dem Projekt Ludi übernommen. Ich erzähle Ihnen später mehr über die Verwendung von Invarianten.

Über die Bedeutung der Notation

Die Generierung aller möglichen Bewegungen von der Position aus ist nur die halbe Wahrheit. Um den Spielstatus zu steuern, ist eine kompakte Darstellung der generierten Moves erforderlich. In ZoG wird zu diesem Zweck die ZSG-Notation verwendet. Hier ist ein Bericht über einen möglichen Beginn eines Schachspiels in dieser Form:

 1. Pawn e2 - e4 1. Pawn e7 - e5 2. Knight g1 - f3 2. Knight b8 - c6 3. Bishop f1 - c4 3. Knight g8 - f6 4. King e1 - g1 Rook h1 - f1 @ f1 0 0 @ g1 0 0 4. Pawn d7 - d5 5. Pawn e4 x d5 5. Knight f6 x d5 

Dieses Skript entspricht in etwa der üblichen Schachnotation und ist allgemein benutzerfreundlich. Nur der vierte Zug von Weiß kann Verwirrung stiften. In der ZSG sieht es also nach Rochade aus . Der Teil der Beschreibung der Bewegung vor dem Zeichen '@' ist ziemlich klar. es ist die gleichzeitige Bewegung von Turm und König, aber was folgt? In ZSG scheint daher ein Zurücksetzen der Attribute der Stücke erforderlich zu sein, um die Möglichkeit einer wiederholten Rochade zu verhindern.


Die Aufzeichnung eines Zuges in ZSG-Notation sollte vollständige Informationen enthalten, die ausreichen, um den Spielstatus korrekt zu ändern. Wenn Informationen über eine Änderung von Attributen verloren gehen, könnte in einem Spiel gemäß einer solchen Aufzeichnung ein Zug fälschlicherweise wiederholt werden (zum Beispiel hätte der Spieler die Möglichkeit, die Rochade erneut auszuführen). Leider können in DLL-Erweiterungen (wie Axiom) erweiterte Informationen nicht übertragen werden.

Bei der Arbeit mit DLL-Erweiterungen ist ZoG gezwungen, beim Positionieren auf eine ausgewählte Bewegung (z. B. beim Zurücksetzen einer Bewegung) eine recht raffinierte Manipulation vorzunehmen. Aus [jeder] vorherigen Position [ab Spielbeginn] werden alle möglichen Züge generiert, und dann muss in dieser Liste mit der [entsprechenden] ZSG-Darstellung nach einem Zug gesucht werden. Die [Nebenwirkungen von jedem] generierten Zug werden auf [jeden nachfolgenden] Spielzustand angewendet, da es möglich ist, Nebenwirkungen auszuführen, die sich nicht in der ZSG-Darstellung des Zugs widerspiegeln.

Die Situation wird durch die Tatsache erschwert, dass der einzige Weg, zum Zeitpunkt eines Spielzugs in der Vergangenheit in den Spielzustand zu gelangen, die konsequente Anwendung aller Spielzüge vom Beginn des Spiels bis zum Anfangszustand des Spielbretts ist. In wirklich komplexen Fällen erfolgt diese Art der Navigation nicht schnell. Ein weiterer Nachteil der ZSG-Notation ist die Aufzeichnung des folgenden Zuges im Go- Spiel:

 1. White Stone G19 x A19 x B19 x C19 x D19 x E19 x F19 

Hier wird in der Position G19 ein weißer Stein platziert, der eine Gruppe schwarzer Steine ​​erfasst. Da alle an der Durchführung der Platzierung beteiligten Teile in der ZSG-Aufführung erwähnt werden müssen, kann die Aufzeichnung der Runde sehr lang erscheinen (in Go kann ein Tropfen bis zu 360 Steine ​​einfangen). Zu was das führen mag, habe ich früher geschrieben . Die für die Aufzeichnung der ZoG-Bewegung zugewiesene Puffergröße reicht möglicherweise nicht aus. Wenn sich aus irgendeinem Grund die Reihenfolge der Entfernung von Steinen ändert (im Verlauf der Entwicklung des Spiels geschieht dies), schlägt der Versuch, einen Zug aus einer alten Reihenfolge von Eroberungen anzuwenden, fehl.

Glücklicherweise gibt es eine einfache Möglichkeit, mit all diesen Problemen umzugehen. Schauen wir uns an, wie Bewegungen von Teilen in ZRF definiert werden:

 (piece (name Pawn) (image White "images\Chess\SHaag\wpawn.bmp" "images\Chess\wpawn.bmp" Black "images\Chess\SHaag\bpawn.bmp" "images\Chess\bpawn.bmp") (moves (Pawn-capture nw) (Pawn-capture ne) (Pawn-move) (En-Passant e) (En-Passant w) ) ) 

In ZoG-Makros definierte Zugnamen sind als Generatoren von Zügen nicht zugänglich. Aber was hindert uns daran, Makros aufzugeben und die Bewegungen mit ihren Namen zu beschreiben? So würde die Platte für ein Schachspiel aussehen:

 1. e2 - e4 Pawn-move 1. e7 - e5 Pawn-move 2. g1 - f3 leap2 n nw 2. b8 - c6 leap2 n ne 3. f1 - c4 slide nw 3. g8 - f6 leap2 n nw 4. e1 - g1 OO 4. d7 - d5 Pawn-move 5. e4 x d5 Pawn-capture nw 5. f6 x d5 leap2 w nw 

Die Vorteile einer solchen Aufzeichnung liegen nicht auf der Hand, haben jedoch einen wichtigen Vorteil. Alle Züge sind einheitlich beschrieben, und diese Beschreibungen enthalten keine zusätzlichen Informationen (die Namen der Zugbeschreibungen könnten natürlich „beschreibender“ sein). In der Beschreibung der Rochade ist es gelungen, sowohl die Änderungen der Attribute als auch die Beschreibung des Turmzugs zu beseitigen (diese Beschreibung hängt nicht mehr von den Implementierungsdetails des Zugs ab). Eine noch klarere Nützlichkeit solcher Aufzeichnungen besteht im Fall des Spiels Go:

 1. G19 drop-to-empty White Stone 

Und das war's auch schon! Wenn die Steine ​​des Gegners gemäß den Spielregeln genommen werden, müssen sie nicht alle in der Zugbeschreibung aufgeführt werden. Es reicht aus, den Anfangs- und Endbereich der Verschiebung (möglicherweise mit einem Vorzeichen), den Namen der ausgeführten Verschiebung und die ihm übergebene Parameterzeile anzugeben. Um einen Zug gemäß dieser Beschreibung auszuführen, ist es natürlich erforderlich, zum Decodieren auf das Bewegungserzeugungsmodul zuzugreifen, aber ZoG tut dies!

Eine andere Möglichkeit, die man unterstützen sollte, taucht in der Funktionalität von "Teilzügen" auf. Hier ist ein Beispiel von " russischen Dame ":

 1. Checker g3 - f4 1. Checker f6 - g5 2. Checker e3 - d4 2. partial 2 Checker g5 - e3 = XChecker on f4 2. Checker e3 - c5 = XChecker on d4 x d4 x f4 

Hier nehmen die Schwarzen im zweiten Zug zwei Figuren auf d4 und f4. Eine vorläufige „Transformation“ dieser Teile zu XChecker ist ein Merkmal dieser Implementierung und dient dazu, die Wiederaufnahme von „besiegten“ Teilen im selben Zug zu verhindern. Der Ausdruck "Teil 2" beschreibt den Beginn des "Composite" -Kurses, der aus zwei "Teilzügen" besteht. Diese Form der Beschreibung ist unpraktisch, da zum Zeitpunkt der Erzeugung des ersten Zuges die Länge der Folge von "Teilzügen" möglicherweise nicht bekannt ist. So sieht diese Beschreibung in einem neuen Format aus:

 1. g3 - f4 checker-shift nw 1. f6 - g5 checker-shift ne 2. e3 - d4 checker-shift nw 2. + g5 - e3 checker-jump nw 2. + e3 - c5 checker-jump sw 2. + 

Implementierungsdetails im Zusammenhang mit der „Transformation“ von Stücken sind irrelevant. Die Erfassung von Stücken ist ebenfalls nicht festgelegt, da die Erfassung bei Dame als „Nebeneffekt“ des Spielzugs und nicht nach dem „Schachprinzip“ erfolgt. Der Teilfortschritt wird am Anfang mit dem Symbol „+“ codiert der Linie. Ein einsames "+" zeigt den Abschluss eines "zusammengesetzten Zuges" an (in der Tat ist dies der übliche "partielle" Zug, der einen fehlenden Zug und eine leere Zeichenfolge enthält).

Auf diese Weise ist es gelungen, unter Verwendung von benannten Regeln für die Implementierung von Zügen eine universelle Notation zu erstellen, die unsere Anforderungen vollständig erfüllt. Natürlich hat es weder mit dem Standardschach noch mit irgendeiner anderen Notation zu tun, aber es kommt auch vor, dass die konventionelle Notation für Schach, Dame und andere Spiele nichts miteinander zu tun hat. Das Visualisierungsmodul kann den Bewegungsdatensatz immer in eine vertraute Form konvertieren, die für ein bestimmtes Spiel akzeptiert wird. Die Konvertierung kann auch in eine universelle Form erfolgen, z. B. in SGF (Smart Game Format) .

Der Lebenszyklus des Spiels

Zusätzlich zu den Informationen zum Platzieren von Steinen auf dem Brett ist die Abfolge der Runden ein wesentlicher Bestandteil des Spielzustands, eine Variable im Spielprozess. Im einfachsten (und gebräuchlichsten) Fall reicht ein Bit aus, um diese Informationen zu speichern, ZoG bietet jedoch einige weitere Möglichkeiten, komplexere Fälle zu implementieren. So könnte eine Beschreibung einer Abfolge von Zügen für das Spiel Splut aussehen! :

 (players South West North East) (turn-order South West West repeat North North North East East East South South South West West West ) 

In diesem Spiel macht jeder Spieler drei Züge gleichzeitig, aber wenn Sie dem ersten Spieler die Möglichkeit geben, drei Züge von der Anfangsposition aus zu machen, kann er eine der gegnerischen Figuren zerstören, wodurch er eine erhält wesentlicher Vorteil. Aus diesem Grund sollte der erste Spieler nur einen Zug machen (dies gibt die Gelegenheit, sich darauf vorzubereiten, einen gegnerischen Spieler anzugreifen, ihn aber nicht anzugreifen), der zweite - zwei Züge (dies reicht auch nicht aus, um einen gegnerischen Spieler anzugreifen) was jeder Spieler immer drei Züge macht.


Die Etikettenwiederholung zeigt den Beginn einer sich zyklisch wiederholenden Folge von Zügen an. Wenn es nicht erscheint, wird die gesamte Beschreibung zyklisch wiederholt. ZoG erlaubt es nicht, das Etikett mehrmals zu verwenden. Ein weiteres wichtiges Merkmal ist die Angabe der Turnreihenfolge. So könnte eine Beschreibung der Abfolge der Züge für ein Spiel aussehen, in dem jeder Spieler zwei Züge ausführt (der erste Zug - Spielsteine ​​bewegen, der zweite - Spielsteine ​​des Gegners erfassen):

 (players White Black) (turn-order (White normal-move) (White capture-move) (Black normal-move) (Black capture-move) ) 

Mit der Beschreibung des Verschiebens von Teilen anderer Personen ist eine weitere Funktion verbunden, deren Verwendung jedoch sehr unbequem ist. Das Problem ist, dass eine solche Beschreibung keine Alternative hat. Wenn die Beschreibung besagt, dass der Zug von einer gegnerischen Figur ausgeführt werden soll, muss der Spieler diesen Zug ausführen! In ZoG ist es unmöglich zu beschreiben, ob man sein eigenes Stück oder das eines anderen bewegt. Wenn eine solche Fähigkeit in einem Spiel benötigt wird (wie in " Stavropol Checkers "), ist es notwendig, alle Teile neutral zu machen (zu diesem Zweck einen Spieler zu schaffen, der nicht am Spiel teilnimmt) und für alle Spieler die Möglichkeit zu bestimmen ein neutrales Stück bewegen. Ich habe oben erwähnt, dass es standardmäßig viel einfacher ist, allen Spielern die Möglichkeit zu geben, beliebige Figuren (sowohl ihre eigenen als auch die des Gegners) zu bewegen, indem die notwendigen Checks in den Algorithmen zur Generierung von Zügen hinzugefügt werden.

Wie Sie sehen, ist die Auswahl an Optionen, die ZoG für die Beschreibung der Abfolge von Abbiegungen bietet, äußerst begrenzt. Axiom kann auch keine neuen Funktionen hinzufügen, da es (normalerweise) über ZoG läuft. Ludi ist in dieser Hinsicht noch ärmer. Um die Vereinheitlichung der Spielregeln (die für die Verwendung generischer Algorithmen erforderlich sind) zu maximieren, wurden in diesem Projekt alle Beschreibungsfunktionen bewusst vereinfacht, wodurch ganze Spielebenen eliminiert wurden.


" Bao Swahili " ist ein gutes Beispiel für ein Spiel mit einem komplexen Lebenszyklus. In diesem Spiel gibt es zwei Phasen mit Regeln für die Bewegungsausführung, die sich erheblich unterscheiden. Zu Beginn des Spiels befindet sich ein Teil der Steine ​​"in der Hand" "Von jedem Spieler. Während noch Steine" in der Hand "sind, werden Steine ​​Stein für Stein in die Vertiefungen gelegt. Wenn die Steine" in der Hand "ausgehen, beginnt die zweite Phase des Spiels mit der Verteilung der eingeworfenen Steine Man kann nicht sagen, dass dieses Spiel nicht in ZRF (der Beschreibungssprache von ZoG) beschrieben werden kann, aber aufgrund der Einschränkungen von ZoG wäre diese Implementierung äußerst verwirrend (was sicherlich nicht für die Qualität der KI-Arbeit am besten ist). Mal sehen, wie die Beschreibung eines solchen Spiels in einer „idealen Welt“ aussehen würde:

 (players South North) (turn-order (turn-order (South pi-move) (North pi-move) ) (label phase-ii) (turn-order (South p-ii-move) (North p-ii-move) ) ) 

Hier bestimmt jede Zugreihenfolge ihre sich wiederholende Zugfolge (die sich durch die Art der Zugausführung unterscheidet). Das Schlüsselwort label definiert ein Label, zu dem während der Generierung des letzten Schrittes ein Übergang erfolgen kann. Sie werden vielleicht bemerken, dass wir hier von der impliziten Annahme ausgehen, dass ein solcher Übergang immer nach dem Zug des zweiten Spielers erfolgt (andernfalls würde er die Zugfolge verletzen). Wie kann der Übergang zur nächsten Phase zu einem beliebigen Zeitpunkt erfolgen?

 (players South North) (turn-order (turn-order (South pi-move) (North pi-move) ) (turn-order (labels - phase-ii) (South p-ii-move) (labels phase-ii -) (North p-ii-move) ) ) 

Hier werden Etiketten im Schleifenkörper getragen und bestehen aus zwei Namen. Markennamen in den Etikettenlisten werden in der Reihenfolge der Übertragung von Spielern in der Liste der Spieler angezeigt. Der für den Übergang verwendete Name wird von dem Spieler bestimmt, der den letzten Zug gemacht hat. Wenn dies der Norden war, wird zum ersten Etikett übergegangen, andernfalls zum zweiten. Wenn einer der Namen in den Beschriftungen nicht verwendet wird, kann die entsprechende Position mit einem Bindestrich gefüllt werden.


Ein wichtiger Aspekt bei der Verwaltung abwechselnder Züge ist die Fähigkeit, einen wiederholten Zug auszuführen. In Spielen der Tischfamilie , wie beispielsweise Nard , Backgammon oder Ur , ist die Fähigkeit, wiederholte Züge auszuführen, ein wichtiges Element der Spieltaktik. In ZoG kann man eine Spielrunde verwenden, um diese Funktion zu emulieren, aber dieser Ansatz erschwert die Beschreibung des Spiels erheblich (insbesondere bei mehr Spielern). Es wäre viel logischer, ein Etikett für die Wiederholung einer Runde zu verwenden:

 (players South North) (turn-order (label repeat) South (label repeat) North ) 

Nachdem das Spiel zur Wiederholung des Etiketts gesprungen ist, spielt der Spieler erneut seinen Zug (der der aktuellen Position in der Liste der Züge am nächsten liegende Zug wird wirksam). Mir gefällt der Ansatz von Perl in seinen impliziten Definitionen. Die implizite Erzeugung von Kontrollstrukturen kann die Spielbeschreibung erheblich vereinfachen. Da wiederholte Züge in vielen Spielen verwendet werden können, wiederholen sich die Bezeichnungen, und das Vorwegnehmen einer möglichen Wiederholung jeder Runde kann implizit sein:

 (players South North) (turn-order South North ) 

Da außerdem die Reihenfolge der Züge vollständig mit der schriftlichen Reihenfolge der Spieler im Spielerkonstrukt übereinstimmt, können Sie die gesamte Reihenfolge der Züge automatisch generieren:

 (players South North) 

Je einfacher die Beschreibung zu schreiben ist, desto besser.

Zerbrechliche Invariante

Die Hauptsache, die ich in ZoG nicht mag, kann mit einem Wort ausgedrückt werden - schachmatt. Auf den ersten Blick ist es nur eine Bedingung (sehr häufig in Spielen der Schachfamilie ), die das Ende des Spiels mit der Situation des Verbündeten verbindet. Leider zeigt sich bei näherer Betrachtung die Einfachheit als trügerisch. Die Verwendung dieses Schlüsselworts bedeutet nicht nur, dass nach jedem Zug eine Prüfung auf den Abschluss des Spiels durchgeführt wird, sondern dass dem Spieler auch ein bestimmtes „Verhalten“ auferlegt wird.


Dieses Spiel unterscheidet sich vom üblichen Shogi nur in der Anzahl der Spieler. Leider reicht dieser Unterschied aus, um die Aufgabe, Schachmatt (und alles, was mit diesem „magischen“ Wort zusammenhängt) zu bestimmen, falsch zu machen. Die Überprüfung der Kontrolle wird nur in Bezug auf einen der Spieler durchgeführt. Infolgedessen kann der König angegriffen werden und gefressen werden [durch eine Kombination von gegnerischen Spielzügen, auch wenn nicht "checken" gelassen wird]! Dass dies nicht optimal ist, spiegelt sich in der Arbeit der KI wider.

Wenn dieses Problem unbedeutend erscheint, sollten Sie nicht vergessen, dass Koalitionen normalerweise in Viererspielen „Paar gegen Paar“ gebildet werden. Bei der Bildung von Koalitionen müssen wir berücksichtigen, dass königswillige Figuren ihn nicht bedrohen! So können sich beispielsweise zwei befreundete Könige auf benachbarten Feldern der Tafel aufhalten.


Es wird komplizierter als je zuvor, wenn ein Spieler mehrere Könige hat. Im „ Tamerlane-Schach “ verwandelt sich der königliche Bauer in einen Prinzen (eigentlich einen zweiten König). In diesem Fall können Sie nur gewinnen, indem Sie den ersten König (einen der beiden) erobern und den zweiten verbinden. In diesem Spiel können Sie sogar einen dritten König gewinnen, der doppelt so viel Geld für die Umwandlung des „Bauern der Bauern“ ausgibt! Die Ausdrucksfähigkeit von „checkmated“ reicht nicht aus, um diese Situation angemessen zu beschreiben.

Eine andere Schwierigkeit kann der Prozess des Gebens des Gefährten sein. Im mongolischen Schach ( Shatar ) hängt das Ergebnis des versuchten Partners von der Reihenfolge ab, in der die Figuren nacheinander „checken“. Das Ergebnis kann entweder ein Sieg oder ein Unentschieden sein (z. B. ein Mitspieler) oder sogar eine Niederlage (ein Mitspieler ist verboten, aber Sie können einen Scheck abgeben). Etwas weniger exotisch ist in dieser Hinsicht der japanische Shogi. In diesem Spiel ist es verboten, einen Partner mit einem fallengelassenen Bauern zu geben, aber Sie können einen Scheck mit einem fallengelassenen Bauern und einen Scheckpartner mit einem bewegten Bauern geben.


Offensichtlich muss man die Logik der Überprüfung des Spielendes von der Prüfung für den in Schach geratenen König trennen. Dies ist eine unveränderliche Regel , die nach jeder Runde überprüft wird. Ein Verstoß gegen die Regel macht es unmöglich, den Zug auszuführen (der Zug wird aus der Liste der verfügbaren Züge entfernt). So könnte ein (vereinfachter) Test für die Kontrolle eines Königs für "Tamerlane-Schach" aussehen:

 (verify (or (> (count (pieces my? (is-piece? King))) 1) (= (count (pieces my? (is-piece? King) is-attacked?)) 0) ) ) 

Es ist wichtig zu verstehen, dass dieser Test nur für die eigenen Könige durchgeführt werden sollte (ich habe das Prädikat my verwendet, weil der Prädikat friend mit Unterstützung für Koalitionen nicht nur für die eigenen Stücke zufrieden sein wird, sondern auch für die Stücke aller befreundeten Spieler). Akzeptabel (und wünschenswert, wenn es mehrere befreundete Könige gibt) ist die Situation, in der der feindliche König nach einem Zug, aber durch den eigenen König, unter Kontrolle gerät. Diese Situation sollte unmöglich sein [es sei denn, es gibt mehrere befreundete Könige]! Die Überprüfung solcher Regeln auf den Abschluss des Spiels durch Schachmatt wird zu einer trivialen Angelegenheit. Wenn es keine möglichen Züge gibt und der [einzige] König in Schach ist, ist das Spiel vorbei [wenn dieser König dem letzten überlebenden Spieler der vorletzten überlebenden Koalition gehört]:

 (loss-condition (and (= (count moves) 0) (= (count (pieces my? (is-piece? King)) 1) (> (count (pieces my? (is-piece? King) is-attacked?)) 0) ) ) 

Die Fähigkeit, Invarianten zu bestimmen, ist in anderen Spielen nützlich, z. B. in Dame . Die größte Schwierigkeit bei der Umsetzung von Spielen dieser Familie hängt mit der Umsetzung der „Mehrheitsregel“ zusammen. In fast allen Entwurfsspielen ist das Erfassen obligatorisch. Außerdem gibt es in den meisten Spielen dieser Familie eine charakteristische Vollendung von "Ketteneroberungen" in einer einzigen Runde. Wenn möglich, nimmt der Kontrolleur, nachdem er gefangen genommen hat, weiterhin andere Teile. In den meisten Spielen muss der Spieler Kettenerfassungen bis zum Ende durchführen, es gibt jedoch Ausnahmen von dieser Regel, z. B. Fanorona .


Mit dem Mechanismus der Teilbewegungen ist die Implementierung einer "Kettenerfassung" recht einfach. Schwierigkeiten ergeben sich, wenn man zusätzlich eine Bedingung auferlegt, unter der man von allen möglichen Optionen eine Kette auswählen muss, in der eine maximale Anzahl von Stücken erfasst wird. In ZoG muss diese Logik auf der Ebene der „Hardcodierung“ von Grund auf implementiert werden:

 (option "maximal captures" true) 

Diese Einstellung eignet sich für „ Internationale Prüfer “, bei den „ Italienischen Prüfern “ ist die Mehrheitsregel jedoch anders formuliert. Wenn es in dieser Version des Spiels mehrere Optionen für die gleiche Anzahl von Eroberungen gibt, müssen Sie eine Option auswählen, die die größere Anzahl transformierter Steine ​​(Könige) erfasst. Die Entwickler von ZoG haben dies zur Verfügung gestellt. You enter the following setting:

 (option "maximal captures" 2) 

In this setting, one counts not only the number of pieces captured, but also their type. Unfortunately, not everything can be foreseen. Here's how the “majority rule” is formulated in “old French checkers”:

If by a series of captures it is possible to capture the same number of checkers with a simple man or with a king, the player must use the king. However, if the number of checkers is the same in both cases, but in one there is an enemy king (or there are more), the player must choose this option, even if the capturing is then done using the simple checker, and not using the king.

Of course, at the present time, almost no one plays this version of checkers, but its very existence clearly demonstrates the shortcomings of “hardcoded” implementation. Using the mechanism of invariants allows for all possible options for the “majority rule” in a universal manner. For the “ old French checkers ” implementation would be as follows:

 (verify (>= capturing-count max-capturing-count) ) (if (> capturing-count max-capturing-count) (let max-capturing-count capturing-count) (let max-capturing-sum capturing-sum) (let max-attacking-value attacking-value) ) (verify (>= capturing-sum max-capturing-sum) ) (if (> capturing-sum max-capturing-sum) (let max-capturing-sum capturing-sum) (let max-attacking-value attacking-value) ) (verify (>= attacking-value max-attacking-value) ) (let max-attacking-value attacking-value) 

Here, we assume that the rules for capture generation correctly fill [the following] local variables:

• capturing-count — total pieces captured
• capturing-sum — number of kings captured
• attacking-value — value of piece capturing

Associated with each of these variables is a value-accumulator, stored in a variable with the prefix max. The three checks are executed serially. Violation of any of the verify conditions immediately interrupts the generation of the next turn option (the capture is not stored in the list of possible turns). Since the checks performed are associated with variable values, it is not sufficient [to test only the current new capture option]. Each test generates a “bendable rule” associated with the generated capture [which may revise the accumulated maximum value]. After each change in any accumulator, all associated rules must be checked again [for every option in the list]. If any of the conditions are breached for a previously generated option, that option must be removed from the list of possible turn options.

Fazit

This is translation of my article of 2014 year. Since then, I have rethought a lot and the Dagaz project has become a reality, but I did not change almost anything in the text. This article was translated by my friend Howard McCay and I am grateful to him for the work done.