Geschrieben von skaldrom am 23. August 2008
Ich 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.
Lesen Sie den Rest dieses Beitrages »
Eingeordnet in Desktop, Theorie und Schnipsel | 5 Komentare »
Geschrieben von skaldrom am 14. October 2008
Um 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
res_capacity=graphMatrix.
clone();
// 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.
Eingeordnet in Theorie und Schnipsel | Keine Kommentare »
Geschrieben von skaldrom am 22. October 2008
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.
Lesen Sie den Rest dieses Beitrages »
Eingeordnet in Coding | Keine Kommentare »
