Avaloq IT-Adventure Battle-Day

Dieser Beitrag ist Teil 2 von 2 in der Serie Avaloqix Programmierwettbewerb

    battledaySo, nun ist er also durch, der Avaloq IT Adventure Battle Day. Etwa 40 Anmeldungen verzeichnete Avaloq für den Wettbewerb, die 10 besten Agenten sowie deren Coderz wurden zu diesem Event eingeladen. Das Resultat vorneweg: Mein Agent wurde nach Strich und Faden zerzaust :boxen: und landete auf Platz 8. Nicht den Hauch einer Chance. Ich war schon sehr stolz, in einer solch illusteren Runde überhaupt anwesend sein zu dürfen. Zum Einen war die Veranstaltung Bi-National mit Teams aus Bonn, Köln, Dresden und Berlin, und der Schweiz, zum Anderen bin ich mir schon wie Joe the Plumber vorgekommen :). Mathematikstudenten, Dozenten, passionierte Spieleprogrammierer, die schon während der Präsentation Fachdispute geführt haben :).

    Beim ersten Spieldurchgang haben sich die Programmierer der Agenten vorgestellt und die implementierten Strategien und Taktiken erläutert. Das war wirklich mehr als spannend und lehrreich. Grundsätzlich haben sich zwei Kategorien herausgebildet: Die Bewerter und die Durchspieler (fachlich korrekte Namen aus der Spieletheorie nach Wahl einsetzen).

    Die Bewerter haben verschiedene Faktoren gewichtet miteinander verrechnet: Änderung des Maxflows, Änderung des Current-Flows, eine Kantenwichtigkeit, Quellen- oder Senkenkanten, … Die zweite Gruppe von Agenten hat versucht, möglichst viele Spiele durchzurechnen und so die Züge, bzw. Kanten zu bewerten. Die Durchspieler haben obsiegt (mindestens Rang 1 und 2 gingen an Agenten dieser Kategorie).

    Informatikerkino

    Informatikerkino

    Der Gewinner hat mit einer Vorversion des Agenten schon letztes Jahr gewonnen (obwohl dieser angeblich einen Bug hatte und beim ersten Zug die am schlechtesten bewertete Kante ausgewählt hat 🙂 ). Er war auch der Einzige, der daran gedacht hat, dass die Turnier-Maschinen mehrere Cores haben könnten und diese auch aktiv ausgenutzt hat (an den eigenen Kopf hau! Oft und feste! :kopfklatsch: ). In seinem Handout hat er ein interessantes Paper zur Spieletheorie angegeben.

    Avaloqix hat eine neue Version des Spielfeldes mit erweiterten Debug-Ausgaben gezeigt. Auf einem der Laptops lief ein Matchmaker, der die Agenten automatisch aufeinander los liess; DAS wäre ein gutes Tool gewesen beim Entwickeln :). Sie denken leider eher nicht, dass sie den Wettbewerb noch ein drittes mal durchführen werden. Dafür sind Ideen im Raum, die Spieloberfläche zu opensourcen.

    Der Nachmittag war äusserst spannend und ich habe viel gelernt. Unter Anderem auch, wie hemdsärmelig mein Algorithmus in Tat und Wahrheit war. Etwas mehr Theorie und Optimierung hätten wahrlich nicht geschadet.

    Ich gratuliere allen Gewinnern und danke Avaloq und den Anderen.

    Die Photos sind auf Flickr verfügbar.

    Nachtrag: Juhuu, ich bin doch dabaei in Marrakesch! Das nennt man Lucky Looser :freu: !

    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.

    Weiterlesen

    Profiling des Spielagenten mit Eclipse TPTP

    Die FAQ zu Avaloqix geben ganz klar die Kriterien bekannt:

    Für den Wettbewerb werden Graphen mit 20-60 Knoten genutzt. Pro Knoten gibt es max. 9 Kanten. Zusätzlich gibt es eine Timelimite von 5 sec pro Spielzug.

    Leider fehlen die Angaben über die Leistungsfähigkeit der Wettbewerbsmaschine. Ich gehe mal ganz willkürlich davon aus, dass sie nicht langsamer ist oder weniger Speicher hat als mein Laptop und die Resultate nur besser sein können. Eine Geschwindigkeitsoptimierung dürfte also nicht ganz sinnlos sein. Ausserdem wird mein Agent in den ersten paar Zügen nie fertig mit Rechnen und muss abbrechen. Eine Optimierung die hier mehr Spielzüge erlaubt, würden die Gewinnchancen signifikant steigern.

    Ausserdem gilt wie überall im Leben: Machs schön und richtig und erst danach schnell.

    Benchmarking

    Bei einer Geschwindigkeitsoptimierung sollte man immer benchmarken. Das heisst: Die Geschwindigkeit vor und nach der Optimierung nachmessen, so dass man sicher sein kann, dass man in die richtige Richtung optimiert hat. Ebenfalls empfehlenswert ist gezieltes optimieren: Wenn man eine Funktion nur ein bisschen verschnellert, die sehr oft aufgerufen wird, bringt das unter Umständen mehr wie wenn man eine Funktion mit viel Aufwand drastisch verkürzt die nur wenige Male zum Zuge kommt. Man braucht also Daten.

    Als Benchmark habe ich – mangels anderer Gegner – ein Spiel gegen den OptimalOneAgent gewählt. Für den Benchmark sollten immer die gleichen Einstellungen gelten, die komfortable Avaloqix Oberfläche erlaubt zum Glück das Festlegen des Spielfeldes mit dem Random Seed.

    Es empfiehlt sich auch, Turn Pause zu deaktivieren und End when winner is ovious zu aktivieren.

    Profiling

    Doch woher die Daten nehmen und nicht stehlen? Dafür zuständig sind sogenannte Profiler. Für Eclipse gibt es einen (einer der versteckten Diamanten) im TPTP-Projekt.
    Weiterlesen

    Maximaler Fluss (maxflow) eines Netzwerkes in Java

    Dieser Beitrag ist Teil 1 von 2 in der Serie Avaloqix Programmierwettbewerb

      MaxFlowUm im Avaloqix Wettbewerb einen einigermassen sinnvollen Agenten zustande zu kriegen, braucht es sehr wahrscheinlich eine Funktion, die den maximalen Fluss eines gegebenen Netzwerkes berechnet. Dafür gibt es eine Vielzahl von Algorithmen mit verschiedenen Aufwänden und in verschiedenen Komplexitätsstufen.

      Der erste, älteste und einfachste Algorithmus ist wohl derjenige von Ford und Fulkerson. Er ist aber relativ aufwändig in der Berechnung (O(#Kanten*#Knoten*Grösste-Kapazität)), da der maximale Fluss in den Aufwand hineinspielt. Etwas besser ist der Algorithmus von Tarjan und Goldberg. Er wird von der Uni Karlsruhe anschaulich erklärt und bei Google Code findet man auch eine Implementation davon.

      Für Graphen mit kleiner Kantendichte ist allerdings der Edmonds-Karp-Algorithmus schneller (laut Wikipedia).

      Wenn man die von der Avaloqix-Oberfläche unter Wettbewerbsbedingungen erzeugten Graphen anschaut, ergibt sich folgendes Bild:

      • Bei 20 Knoten werden 40-50 Kanten generiert, das ergibt eine Dichte von ungefähr 0,263
      • Bei 60 Knoten werden 160 Kanten generiert, das ergibt eine Dichte von ungefähr 0,090

      Das darf wohl mit Fug und Recht als undicht, ääh, geringe Dichte bezeichnet werden, also machen wir uns doch an Edmonds Karp!

      Implementation

      Bei der Implementation habe ich mich sehr nahe an die Beispielimplementation von Wikipedia gehalten. Die einzelnen Teile sind etwas aufgeräumter und kommentierter:

      /**
       * Edmonds-Karp algorithm with O(V³E) complexity
       *
       * This implementation is a slightliy modified source from Wikipedia. See
       * http://en.wikipedia.org/wiki/Edmonds_karp
       */

      class MaxFlow {

          public static final int UNVISITED = 0, VISITED = 1;

          private int[][] res_capacity; // Residual capacity
          private int[] parent; // Parent node in Breadth First Search (BFS)
          private int[] mark; // BFS: Already visited?
          private int[] min_capacity; // Minimal flow
          private int size; // Number of nodes
          private int sink;

          public MaxFlow() {
          }

          public int getMaxflow(int[][] graphMatrix, int source, int sink) {
              this.sink = sink;
              this.size = graphMatrix.length;

              int max_flow = 0; // THE max flow for which we are doing this
              // circus

              int[][] flow = new int[size][size]; // Our flow
              res_capacity = new int[size][size]; // Remaining capacity

              parent = new int[size];
              min_capacity = new int[size];
              mark = new int[size];

              // Before we start, all capacities are residual
              // System.arraycopy may be faster: see http://www.javaspecialists.eu/archive/Issue124.html
             
              // The following is wrong, as Feri in the comments has found out.
              // clone() is one-dimensional! *pats-head*
              // res_capacity=graphMatrix.clone();
              //
              //Faster:
              for (int i = 0; i < size; i++) {
                  System.arraycopy(graphMatrix[i], 0, res_capacity[i], 0, size);
              }

              // Search in BFS manner through the graph, Path by Path
              while (BFS(source)) {
                  max_flow += min_capacity[sink];
                  int v = sink, u;
                  while (v != source) {
                      u = parent[v];
                      flow[u][v] += min_capacity[sink];
                      flow[v][u] -= min_capacity[sink];
                      res_capacity[u][v] -= min_capacity[sink];
                      res_capacity[v][u] += min_capacity[sink];
                      v = u;
                  }
              }
              return max_flow;
          }

          /**
           * Breadth First Search in O(V²)
           *
           * @param source
           *            The source node
           */

          private boolean BFS(int source) {
              int first, last; // Queue pointers
              int[] queue; // Queue pointers

              queue = new int[size];
              for (int i = 0; i < size; i++) {
                  mark[i] = UNVISITED;
                  min_capacity[i] = Integer.MAX_VALUE;
              }

              first = last = 0;
              queue[last++] = source;
              mark[source] = VISITED;

              while (first != last) { // While "queue" not empty.
                  int v = queue[first++];
                  for (int u = 0; u < size; u++)
                      if (mark[u] == UNVISITED && res_capacity[v][u] > 0) {
                          min_capacity[u] = Math.min(min_capacity[v],
                                  res_capacity[v][u]);
                          parent[u] = v;
                          mark[u] = VISITED;
                          if (u == sink)
                              return true;
                          queue[last++] = u;
                      }
              }
              return false;
          }
      }

      Resultat

      Als innere Klasse angelegt, arbeitet diese Implementation wunderbar in einem Avaloqix-Agenten. Tests haben gezeigt, dass das Resultat nicht nur stimmt, sondern auch mit den Ausgaben der Spieloberfläche korrespondiert. Auch bei sehr grossen Netzwerken braucht sie auf meinem Schlaftop nur ein paar wenige Millisekunden.

      Avaloqix: Unterhaltsamer Java-Programmierwettbewerb

      Flow im HirnIch liebe Wettbewerbe und ich liebe das Spielen. Meine inneres, urmännliches Ich springt voll auf das kompetitive Element solcher Veranstaltungen an. Zum Erlegen von Höhlenbären oder für Sportwettkämpfe eigne ich mich definitiv nicht, darum bin ich froh, wenn ab und zu ein Kräftemessen auf meinem – eher wetwarelastigen – Gebiet stattfindet.

      Leider hat es jetzt seit längerer Zeit kein Codeduel (ein spassiger, von Microsoft Schweiz gesponserter/organisierter Event in welchem SOAP-Services gegeneinander angetreten sind, für den es aber leider keine offizielle Website mehr gibt) mehr gegeben und für die kommerzielle Version solcher Wettbewerbe habe ich im Moment wirklich keine Zeit.

      Über die Seite des Schweizerischen Jahres der Informatik bin ich auf Avaloqix gestossen und war sofort begeistert. Am Tag der Informatik am 29. August 2008 in Zürich wird es ein Event speziell zu diesem Wettbewerb geben.

      Das Spiel

      Es geht darum, einen Spieler für eine abgewandelte Version des Shannon Switching Games zu programmieren. Kurz erklärt: Es gibt eine Quelle und ein Senke, die über ganz viele Röhren und Sammelpunkte miteinander verbunden sind. Im ersten Durchgang versucht der eine Spieler einen möglichst grossen Durchfluss zu erzielen indem er Röhren freischaltet, während der andere Spieler ebendies durch das Ausbauen von Röhren zu verhindern versucht. In einer zweiten Runde werden die Rollen der Spieler in demselben Röhrengeflecht getauscht. Gewonnen hat, wer als Durchflussmaximierer den grösseren Durchfluss erzielen konnte.
      Weiterlesen