Topologisch gleichwertige Stellungen zu erkennen ist ein wichtiger Bestandteil der Computerspielers, und wird auch in der Benutzer - Zugauswahl eingesetzt.

Ohne das Erkennen topologsich äquivalenter Spielstellungen wäre die Anzahl der möglichen verschiedenen Stellung sehr viel grösser als mit Erkennen.
Vielleicht etwa das Quadrat der Anzahl mit Erkennen.Daher ist dieser Teil für den Computerspieler unbedingt erforderlich.

Ausserdem soll eine Stellung immer schnell mit vielen anderen Stellungen (die bereits berechnet wurden) auf topologische Gleichheit getestet werden.
Daher brauchen wir einen normalisierungs Algorithmus: Er soll eine Stellung ein eine normalisierte Darstellung überführen, so dass alle topologisch gleichen Stellugen auf die selbe Normaldarstellung abgebildet werden, und topologisch verschiedene Stellung werden auf unterschiedliche Normaldarstellungen abgebildet.
Dann brauchen wir jede Stellung nur einmal zu normalisieren und suchen diese in der Transpositionstabelle, die die normalisierten Darstellungen der bereits berechneten Stellungen enthält.


Wann sind zwei Stellungen topologisch äquivalent?
    Die Stellungen in Bild 2 und 3 sind ebene-verschieden , aber kugel-äquivalent.
In der Grafikdarstellung sind zwei Graphen äquivalent, wenn sie sich durch Begwegen der Punkten und Linien, ohne Überschneidung, ineinander überführen lassen; wie aber erkennen wir die Äquivalenz in der internen Darstellung?.

Die Stellung im linken Bild kann intern auf verschieden Weise dargestellt sein:
Es ergibt sich ein zyklischer Pfad, A usw. sin die Namen der Punkte.
ACBC,
Weitere topologisch äquivalente Darstellugen ergeben sich durch Verändern der Wahl der Startkante oder durch Vertauschen von Punktnamen:
CBCA;  BCAB;       CABC;       EFGF;
Alle diese so beschriebenen Stellungen sind äquvalent.

Übertragen wir die Äquivalenzdefinition aus der Anschauung in die interne Darstellung kommt etwa so etwas heraus:
Zwei Graphen äquivalent, wenn sie sich durch Permutation der Punkt/Flächennamen und der aufzählreihenfolge der Pfade ineinander überführen lassen.

Alle diese Pemutationen durchzuprobieren dauert natürlich zu lange.. Bei 10 Punkten sind allein 10! =  3628800 Permutationen für die Punkte möglich

Hier der Algrithmus, schematisch (für die einfache interne Darstellung, kugel-äquivalenz)

Der Algorithmus arbeitet sich von der Aussenfläche nach innen durch. Für die Kugeläquivalenz werden alle Flächen als Aussenfläche ausprobiert die der kleinste Ergebnisswert zurückgeliefert. Dort wo verschiedene Varianten durchprobiert werden müssen, lässt sich die Verabeitungsgeschwindig keit erhöhen, wenn bei offensichtlich verschiedenen Varianten nach einem willkürlichen Verfahren eine ausgewählt wird. Z.B beim durchtesten aller potentiellen "Aussenflächen" brauchen nur diejenigen berücklsichtigt zu werden, die die meisten und längsten Pfade enthalten.
Der Computerspieler verbringt etwa (nur) 50% seiner Rechenzeit im Normalisierungsalgorithmus

Das Ergebinss der Normalisierung ist ein string.
 normalisiere_graph(g):
   fuer alle flaechen a in g:
     normalisiere_flaeche_ohne_pfad(a,kein pfad)
   ergebinss = kleinster wert.
 
 normalisiere_flaeche_ohne_pfad(a,oph):
   fuer alle pfade ph an a, ausser oph:
     normalisiere_netz_von_pfad_aus(ph)
   ergebniss = sortierte folge der ergebnisse, getrennt durch ';'.
 
 normalisiere_netz_von_pfad_aus(ph)
   fuer alle kanten c in ph:
     normalisiere_netz_von_kante_aus(c)
   ergebniss = kleinster wert.
 
 normalisiere_netz_von_kante_aus(stc)
   merke kante stc vor.
   fuer alle (jetzt oder spaeter) vorgemerkten kanten c
     ph ist der pfad von c.
     wenn ph noch nicht bearbeitet:
       laufe den pfad entlang, beginnend mit c; 
          liste alle punktnamen auf, merke am punkt die vom pfad
          links abzweigende kante vor.
       wenn c nicht stc ist, und an der flaeche von c noch weitere pfade liegen:
         fuege in '[' ']' eingeschlossen hizu:
           normalisiere_flaeche_ohne_pfad(ph).
   ergebnisse getrennt durch ','. 
   im ergebniss nummeriere die punktnamen ausserhalb [] so um,
   dass der zuerst genannte punkt A heisst, der als zweites genannte B , usw.

Für ebene-äquivalenz wird in normalisiere_graph nur die aussenfläche verwendent.
In der reduzierten Darstellung können noch die einzelnen Teilsysteme getrennt normalisiert werden, das Ergebniss ist dann die sortierte Folge davon, getrennt durch '|'.
normalisiere_flaeche_ohne_pfad wird innerhalb von normalisier_graph (indirekt) möglicherweise mehrmals mit den selben parametern aufgerufen. Einmal berechnete Werte können dann zwischengespeichert und beim nächsten aufruf direkt zurückgegeben werden.

Der Algorithmus funktioniert auch mit Graphen, wo ein Punkt mehr als 3 Kanten haben darf.
Die Zeitkompexität habe ich nicht genau ermittelt, nur am Test mit 3Graph, wo die Graphen eher klein sind.
Bie vielen Zufallsspielen mit 8 Startpunkten: Kanten:8,16,24, ... _us:4,8,12,18,27,36,44. Könnte etwa propotional K^1,25 sein, K=anzahl der Kanten.

Beispiele für Stellungen und Normal-strings sind hier