Ein Algorithmus zur Auswertung von Diplomacy

(Peter Jacobi für Interzine '92.04', 1992-04-12
neu in HTML gesetzt 1999-06-29)

Dieser Artikel skizziert einen Algorithmus zur Auswertung von Diplomacy (und gewisser Varianten), wie er in dem Programm DIP_EVAL implementiert ist.
Ich betrachte hier nur die Auswertung nach den neuen (1983er) Regeln von Avalon Hill.

1. Grundsätzliches
2. Auswertung eines einzelnen Konflikts
3. Abhängigkeiten verschiedener Konflikte
   1. Auswertung von Konflikten auf die Wirksamkeit von Unterstützungen
   2. Auswertung von Konflikten auf die Wirksamkeit von Bewegungsbefehlen
   3. Gegenseitige Abhängigkeit von Konflikten
4. Auswertungsreihenfolge
   1. K1: Auswertung von Konflikten um Felder, in denen convoyende Flotten stehen
   2. K2: Auswertung von Konflikten, von denen die Wirksamkeit von Unterstützungen abhängt
   3. K3: Auswertung von gegenläufigen Angriffen
   4. K4: Auswertung aller anderen Angriffe

I. Grundsätzliches

Der Algorithmus transformiert einen korrekten Befehlssatz für ein Diplomacy-artiges Spiel in einen anderen korrekten Befehlssatz für dieses Spiel, dessen sämtliche Befehle ausgeführt werden können. Mit anderen Worten, es wird entschieden, welche Unterstützungen, Convoys und insbesondere Bewegungen gelingen, woraus auch folgt, welche Einheiten vertrieben werden.

Für die Auswertung einer pbm-Partie muß natürlich der erforderliche korrekte Eingabebefehlssatz vom GM oder von einem Computerprogramm aus den Zügen der Spieler erstellt werden. Diese Aufgabe wird zum Beispiel vom Programm DIP_WORK / DIP_READ / DIP_WRIT von Torsten Will erfüllt.

Die Syntax der Eingabe- und Ausgabebefehlssätze des Auswertungsalgorithmus unterscheidet sich in zwei Punkten von den üblicherweise notierten:

1. Es wird explizit zwischen normalen Bewegungen und per-Convoy-Bewegungen unterschieden.
   In den neuen Avalon-Hill-Regeln wird ja bestimmt, daß ein Zug eines Spielers immer entweder als normaler oder als per Convoy-Zug betrachtet werden muß, auch wenn beide Alternativen möglich sind.
2. Als zusätzlicher Befehl wird der nicht-gelingende-aber-wirksame Bewegungsbefehl eingeführt, der nur im Ausgabebefehlssatz vorkommen kann.

Weder um welche Einheiten es sich handelt, noch (bis auf eine Ausnahme) die Geografie des Spielplans muß für diesen Auswertungsschritt bekannt sein.

II. Auswertung eines einzelnen Konfliktes

Ein Konflikt im Sinne dieses Algorithmus liegt vor, wenn

• mehr als eine Einheit in das gleiche Feld ziehen will oder
• mindestens eine Einheit in ein Feld ziehen will, in dem bereits eine Einheit steht.

Gehen wir vorgreifend davon aus, daß wir schon wissen, welche Unterstützungen wirksam sind und welche nicht.

• Die A-Stärke eines Angriffs errechnet sich aus der Summe der Stärke des Angreifers und der Stärken aller wirksamen Unterstützungen dieses Zugs - bei Standard-Dippy sind natürlich alle einzelnen Stärken gleich eins.
• Die Verteidigungsstärke eines leeren Feldes und eines Feldes, das von einer Einheit erfolgreich verlassen wird, ist -1. (Nicht 0, damit auch Einheiten der Stärke 0 korrekt behandelt werden können). Andernfalls ist die Verteidigungsstärke gleich der Summe der Stärke der Einheit in diesem Feld und der Stärken der Einheiten, die diese Einheit erfolgreich im Halten unterstützen. (Letztere gibt es natürlich nicht, wenn die erstere Einheit einen Bewegungsbefehl hat).

In diesem Fall müssen die Angriffsstärken auch noch einmal anders berechnet werden, um dem Verbot, sich selbst zu vertreiben, Rechnung zu tragen. Sei X die Nation der Einheit im Zielfeld.

• Die B-Stärke eines Angriffs einer Einheit der Nation X ist null.
  Die B-Stärke eines anderen Angriffs errechnet sich aus der Summe der Stärke des Angreifers und der Stärken aller wirksamen Unterstützungen dieses Zugs, die nicht von der Nation X kommen.

Sehen wir jetzt einmal vom Problem eines gegenläufigen Angriffs ab, so ist

• ein Angriff auf ein leeres oder erfolgreich verlassenes Feld dann erfolgreich, wenn seine A-Stärke größer als die A-Stärke jedes anderen Angriffs auf dieses Feld ist.
• Ist im anderen Fall
  • der Angreifer von der gleichen Nation wie die Einheit im Zielfeld, so gelingt der Angriff nicht.
  • Andernfalls ist ein Angriff erfolgreich, wenn seine A-Stärke größer als die A-Stärke jedes anderen Angriffs auf dieses Feld ist und größer als die Verteidigungsstärke des Zielfelds und wenn zusätzlich (je nach Regelinterpretation) eine der folgenden Bedingungen erfüllt ist:
    1. Die B-Stärke dieses Angriffs ist größer als die Verteidigungsstärke des Zielfelds.
    2. Die B-Stärke dieses Angriffs ist größer als die Verteidigungsstärke des Zielfelds und größer als die B-Stärken aller anderen Angriffe.
    3. Die B-Stärke dieses Angriffs ist größer als die Verteidigungsstärke des Zielfelds und größer als die A-Stärken aller anderen Angriffe.
    4. Die B-Stärke eines Angriffs auf dieses Feld ist größer als die Verteidigungsstärke des Zielfelds und größer als die B-Stärken aller anderen Angriffe.

III. Abhängigkeit verschiedener Konflikte

1. Auswirkung von Konflikten auf die Wirksamkeit von Unterstützungen

1. Die Wirksamkeit von Unterstützungsbefehlen (für Konflikte um Felder, die keine convoyenden Flotten enthalten) aus Feldern heraus, die per Convoy angegriffen werden, hängt davon ab, ob eine gültige Convoyroute existiert.
2. Eine Unterstützung in das Feld hinein, aus dem die unterstützende Einheit angegriffen wird, ist unwirksam, wenn die unterstützende Einheit vertrieben wird.

2. Auswirkung von Konflikten auf die Wirksamkeit von Bewegungsbefehlen

1. Bei gegenläufigen Angriffen muß eine Einheit nicht nur den Konflikt um ihr Zielfeld gewinnen, sondern auch stärker unterstützt sein, als die sich entgegengesetzt bewegen wollende Einheit.
2. Sind beide Voraussetzungen erfüllt, so wird der entgegengesetzte Angriff unwirksam.

3. Gegenseitige Abhängigkeit von Konflikten

1. Gibt es einen Konflikt um ein Feld, in dem eine Einheit steht, die selber einen Bewegungsbefehl hat und dadurch an einem anderen Konflikt beteiligt ist, so ist der Ausgang des ersten Konflikts möglicherweise vom Ausgang des zweiten Konflikts abhängig.

IV. Auswertungsreihenfolge

K1: Auswertung von Konflikten um Felder, in denen convoyende Flotten stehen

Der Ausgang dieser Konflikte ist nicht vom Ausgang anderer Konflikte abhängig.

• Unterstützungen für diese Konflikte sind genau dann wirksam, wenn sie nicht aus dem Zielfeld eines normalen Bewegungsbefehls kommen. Deshalb können diese Konflikte jetzt nach II. ausgewertet werden.
• Alle per-Convoy-Bewegungen, die jetzt nicht mehr über eine gültige Convoyroute verfügen (dies ist die einzige Stelle, wo die Geografie einfließt), werden aus der Befehlsliste gestrichen.
• Die nicht gelingenden Bewegungsbefehle werden in nicht-gelingende-Bewegungsbefehle umgewandelt. (Nicht-gelingende-Bewegungsbefehle verteidigen im Gegensatz zu anderen Bewegungsbefehlen ihr Ausgangsfeld.)

K2: Auswertung von Konflikten, von denen die Wirksamkeit von Unterstützungen abhängt

Nachdem die Frage der Wirksamkeit von Unterstützungen gemäß III.1.a geklärt ist, werden in der nächsten Stufe die Konflikte behandelt, die die Wirksamkeit von Unterstützungen nach III.1.b beeinflussen, d. ,h. in Situationen wie:

X: A Bbb-Aaa; Y: A Ccc-Bbb; A Aaa S A Ccc-Bbb

der Konflikt um Aaa.

Da die Einheit im Zielfeld keinen Bewegungsbefehl hat, können keine Abhängigkeiten nach III.2 und III.3 auftreten, aber auch keine nach III.1.b, da auch in diesem Fall nur Konflikte um Felder, in denen eine Einheit mit einem Bewegungsbefehl steht, beeinflußt werden (im obigen Beispiel Bbb).

Diese Konflikte können jetzt einzeln nach II. behandelt werden, wobei alle Unterstützungen wirksam sind, die nicht aus den Zielfeldern von Bewegungsbefehlen kommen.

Danach kann endgültig über die Wirksamkeit aller Unterstützungsbefehle für die noch zu behandelnden Konflikte entschieden werden:

• Ein Unterstützungsbefehl ist unwirksam, wenn eben festgestellt wurde, daß die Einheit aus dem Zielfeld des Unterstützungsbefehls heraus vertrieben wurde.
• In allen anderen Fällen, wo eine unterstützende Einheit nur aus dem Zielfeld ihrer Unterstützung angegriffen wird, ist die Unterstützung wirksam.
• In den verbleibenden Fällen, wo die unterstützende Einheit (auch) aus anderen Feldern angegriffen wird, ist die Unterstützung unwirksam.

Die nicht gelingenden Bewegungsbefehle werden in nicht-gelingende-Bewegungsbefehle umgewandelt.

K3: Auswertung von gegenläufigen Angriffen

• Zuerst wird (falls vorhanden) der stärkere Angriff behandelt. Gewinnt er den Konflikt im Zielfeld, so wird der andere Angriff gestrichen.
• Dann wird der Konflikt im Zielfeld des schwächeren Angriffs (bzw. beide Konflikte bei gleichstarken Angriffen) ausgewertet. Würde bei normaler Auswertung der Angriff, der einem gegenläufigen Angriff ausgesetzt ist, gelingen, so wird die Konfliktauswertung so geändert, daß kein Angriff gelingt.
  (Für diese Konfliktklasse gibt es eine Minderheitenmeinung, wie sie ausgewertet werden sollte; dies läßt sich im Programm einstellen).

Die nicht gelingenden Bewegungsbefehle werden in nicht-gelingende-Bewegungsbefehle umgewandelt.

K4: Auswertung aller anderen Angriffe

Die noch auszuwertenden Konflikte können noch durch III.3.a voneinander abhängen.
Dies zu berücksichtigen ist überraschend einfach - folgende beiden Schritte werden solange wiederholt, bis keine Änderung der Auswertung mehr eintritt:

1. Die verbliebenen Konflikte werden nach II. ausgewertet (wobei angenommen wird, daß eine Einheit mit einem normalen oder per-Convoy-Bewegungsbefehl ihr Feld verlassen kann).
2. Die nicht gelingenden Bewegungsbefehle werden in nicht-gelingende-Bewegungsbefehle umgewandelt.

Warum dieses Verfahren funktioniert, kann der geneigte Leser als Übung selber herausfinden.

Peter Jacobi