Der Avaloqix Spielagent

Juhuu! Mein Spieler hat sich anscheinend gut geschlagen und ich wurde an den Battleday von Avaloq eingeladen! An diesem Datum werden die programmierten Spieler in einem spassigen Turniermodus gegeneinander antreten. Noch mehr freue ich mich auf die Präsentationen der anderen Mannschaften und auf die Leute. Ich kann mir da sehr spannende Begegnungen, Gespräche und Kontakte vorstellen. Ich werde mit Photoapparat bewaffnet davon berichten.

Nun kann ich auch kurz die Taktik meines Spielagenten vorstellen, da er sich ja anscheinend nicht ganz überschlecht angestellt hat. Wenn für Sie als Leser bis hier alles nur nach Bahnhof geklungen hat, dann möchte ich Sie ermuntern, die restlichen Beiträge dieser Serie durchzulesen.

Grundsätzlicher Ablauf

Struktogramm meines Spielers

Struktogramm meines Spielers

Nach der Initialisierung und der Aktualisierung verschiedener Attribute wird zuerst der maximale Fluss nach Edmonds-Karp (Ford-Fulkerson mit BFS) berechnet.
Danach werden möglichst viele „minimale Schnitte“ gesucht. Minimale Schnitte in diesem Kontext sind Kombi­natio­nen von Kanten, die alle bei einer maximalen Flusskonstellation durchflossen sind – in der Summe mit den maxi­ma­len Fluss – und die den Graphen teilen.

Diese Schnitte werden folgendermassen gesucht:

  • Der Schnitt aus der Berechnung des maximalen Flusses.
  • Alle Kanten die von der Quelle oder Senke ausgehen.
  • In Brute-Force Manier bis ans Zeit/Speicherlimit.

Jede gefundene Kante, die in einem solchen Fluss teilnimmt, wird bewertet und mit einer Priorität versehen:

  • Wenn es die einzige Kante des Schnittes ist: ∞
  • Wenn die anderen Kanten des Schnittes voll gefüllt sind: ∞
  • Ansonsten: Anteil des Flusses in der Kante zur freien Kapazität der anderen Kanten des minimalen Schnittes (in Prozent)

Im Folgenden wird eine unselektierte Kante gesucht:

  1. Eine Kante aus den Schnitten, absteigend nach Priorität
  2. Eine Kante die beim maximalen Fluss beteiligt ist, absteigend nach Fluss
  3. Eine zufällige Kante (Frigidor-Algorithmus)

Schwächen

Bei gewissen Konfigurationen versagt der Algorithmus. Darstellung zu Beginn mit Auslastung bei maximalem Fluss (dem als erstes gefundenen). Oncode ist MIN:

Problematische Konstellation

Problematische Konstellation

Der maximale Fluss ist 7.
MAX wählt intelligenterweise E.
Minimale Schnitte (mit Maximalfluss): (A/B), (D/E)

Da A am wenigsten in den restlichen Kanten (B) „versorgt“ werden kann, wird A statt dem eigentlich richtigen B gewählt. Dieser Zug ermöglicht ein 5:1 Gewinn für jeden halbwegs intelligenten Gegenspieler.
Für den Wettbewerb sind nur grosse Netze angekündigt, darum habe ich diese Schwäche unberücksichtigt gelassen.

Optimierungen

Viele Optimierungen erschweren die Lesbarkeit des Codes. So werden Arrays wiederverwendet und Zelle für Zelle kopiert. Zusätzlich werden eigene Edge-Klassen verwendet, welche die Priorisierung vornehmen können.

Verbesserungsmöglichkeiten

  • Verschiedene, maximale Flüsse berücksichtigen
  • Aufgezeigte Schwäche eliminieren

Was habe ich gelernt

  • Collections sind langsam
  • Collections brauchen viel Speicher
  • Profiling bringts
  • Arrays erzeugen ist teuer
  • DFS braucht ebenfalls viel Speicher
  • Windows ist case-insensitive. Kopiert man die Classdateien von Linux, und hat man mal was an der Gross-/Kleinschreibung der Klassen verändert gibt es eine java.lang.NoClassDefFoundError (wrong name). Ein Clean Rebuild hilft…
  • Denken schadet nicht 🙂 …
  • Wenn ich den Leuten sage, dass ich vielleicht Offroader fahren werde, kriegen sie Angst.

Ein Gedanke zu “Der Avaloqix Spielagent

  1. Erstmal: Jaja, der Frigidor-Algorithmus 😉 Bei der Auswahl der unselektierten Kanten wird er hier beinahe verachtend dargestellt, da (insbesondere bei grossen Netzen) er wohl kaum einmal zum Zug kommt. Dennoch ist der (zugegebenermassen sehr einfache) Zufalls-„Algorithmus“ nicht zu verachten. Insbesondere gegen Spieler die versuchen die Taktik und Strategie des Gegners an Hand seiner Züge herauszufinden können gehörig verwirrt werden, wenn man ab und zu mal den Zufalls spielen lässt. Natürlich ist dann der Zug nicht optimal aber je nach dem (Codeduel I) kann das reichen! Ich bin natürlich auch ein Fan von „Killer“-Algorithmen, die den Gegner, egal ob er einen liest oder oder nicht, schlagen. Aber auch diese Algorithmen sind je nach Aufgabe und Turniermodus bezwingbar (Codeduel III). Fazit: Ich würde die Punkte 2 und 3 bei der Auswahl der unselektierten Kanten tauschen.

    Übrigens: Mir kommen da ein paar grössere Netzwerk-Konfiguration in den Sinn, bei denen es gewisse Schwächen geben könnte (z.B. es führen nur Kanten mit niedriger Kapazität zu Quelle und Senke).

    Und: Tolle Serie! Thx, Grats & viel Glück am Freitag!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.