Java | Technik, Gothic und Anderes

Profiling des Spielagenten mit Eclipse TPTP

Geschrieben von skaldrom am 22. October 2008

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

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 »

Maximaler Fluss (maxflow) eines Netzwerkes in Java

Geschrieben von skaldrom am 14. October 2008

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

MaxFlow 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 »

Avaloqix: Unterhaltsamer Java-Programmierwettbewerb

Geschrieben von skaldrom am 23. August 2008

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

Flow im Hirn 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 »

Automatisches und mehrfaches submitten von Formularen

Geschrieben von skaldrom am 30. July 2008

Wirre Gedanken

Formular Dieser Beitrag ist dem Titz gewidmet. Dem Titz, der sich aufgeregt hat , obwohl es gar nicht nötig gewesen wäre und der sich nun mit einer gewissen Teilnehmerredundanz anfreunden muss. Hauptsache ist doch, das PHP fliesst und die Variablen bleiben sauber… Und ein Bierchen würde ich auch noch springen lassen …

Eine wichtige Frage zu Beginn: Wieso sollten wir denn automatisch und mehrfach Formulare submitten wollen? Hmm, um den Titz zu ärgern? Weil wir es können? Weil man manchmal tun muss, was man tun muss? Weil man seine 84 Kinder an einem elektronischen Fussballturnier anmelden will (hat eigentlich schon jemand bemerkt, dass ich neue Smilies und unglaublich Freude daran habe?)? Oder weil man über einen Wettbewerb gestolpert ist, der ebendies nicht verbietet (also das Mehrfachsubmitten, nicht das Kinderanmelden oder die neuen Smilies) und der kein Captcha hat (~~vielleicht, weil es der Titz vergessen hat~~)?

Nachtrag 31.07.2008: Schenken mir doch so unglaublich nette Mitarbeiter einer Versicherung heute morgen am Bahnhof einen Müsliriegel. Und auf diesem eher gesunden Teil hat es, ja rate, oh wissbegieriges Volk, einen Wettbewerb. Ob der Titz wohl am Abend für eine andere Firma weitercoded? Ich werde mich auf jeden Fall während der Zugfahrt mal damit befassen .

Vorgehen

Erster Schritt: Selenium IDE

Man könnte nun wie wild losprogrammieren, oder aber einen einfacheren Weg wählen. Ein guter Startpunkt für automatisiertes Browsen generell ist die Selenium IDE. Dieses geniale Teil für den Firefox zeichnet wie ein Macrorecorder alles auf, was im Browser gemacht wird. Hat man die Teilnahme beim Wettbewerb einmal so aufgezeichnet, so müssen nur noch die click’s, die das Form absenden, durch clickAndWait’s ersetzt werden, damit vor dem Weiterausfüllen (bei mehrseitigen Formularen) auf die neue Seite gewartet wird. Es empfiehlt sich, eine Abschlussüberprüfung als letzten Schritt hinzuzufügen, um um kontrollieren zu können, ob die Kinder erfolgreich angemeldet wurden (markieren des “Dankeblabla”, dann rechte Maustaste und assertTextPresent).

Ein Wettbewerb über 2 Seiten. Aufgezeichnet und bearbeitet mit der Selenium IDE.

Diesen Testcase kann man nun abspeichern und eigentlich immer wieder ausführen. Ein Klick reicht und Firefox rasselt alles schön durch. Den Namen leicht verändern kann man durch Editieren des Skripts…

Für den zweiten Schritt sollte man das Testscript als PHP exportieren.

Zweiter Schritt: Selenium RC

Die Selenium RC Komponente kann den Browser fernsteuern und so ferngesteuert am Wettbewerb teilnehmen. Um sie unter Linux Debian zum Laufen zu kriegen, war ein Bisschen Gemurkse notwendig.

Lesen Sie den Rest dieses Beitrages »

Eingeordnet in Theorie und Schnipsel, Web | 2 Komentare »

5 Wege für ProgrammiererInnen die Zeit intelligent zu verdödeln

Geschrieben von skaldrom am 8. August 2007

1. Corewars

Oldie but Goldie! Corewars ist ein Programmierspiel in welchem sich Programme in einem zyklischen Speicher bekämpfen. Diese kleinen Kämpfer sind in einer Assemblerartigen Programmiersprache geschrieben und beherrschen sogar eine Art Multithreading. Bei jedem der Kampfprogramme wird abwechslungsweise ein Befehl ausgeführt. Das Programm das am Schluss noch ausführbar ist hat gewonnen.

Einfachstes Beispiel: der Imp. Er gewinnt zwar nie, aber verliert auch nicht. Alles was er tut ist den Code aus Speicherstelle 0, also sich selber (in Corewars sind alle Speicherangaben relativ zur eigenen Position) eine Speicherstelle weiterkopieren. Als nächstes wird diese kopierte Version ausgeführt und er rast geschwind durch den ganzen Speicher und überschreibt viele, sehr ausgeklügelte aber träge Giganten.

; The imp: Er kopiert sich selbst immer einen Schritt weiter

mov 0, 1

Etwas vielfältiger ist der Dwarf. Er schiesst Steine (unausführbare DAT-Anweisungen) durch den Speicher:

add #4, 3 ; Addiere 4 zur DAT-Anweisung

mov 2, @2 ; Kopiere die DAT-Anweisung an die Speicherstelle auf die sie zeigt

jmp -2    ; Von vorne

dat #0

Grundsätzlich gibt es drei Strategien die sich grundsätzlich zyklisch gegenseitig schlagen:

Papers:: Papers sind Replikatoren. Sie kopieren sich selbst über das Spielfeld und führen ihre Kopien dann aus.
Stone:: Stones schmeissen unausführbare dat Anweisungen über das Spielfeld.
Scissors:: Scannen das Spielfeld und versuchen andere Warriors zu finden und mit sinnlosem Code zu beschäftigen.

Ganz wilde Naturen wenden genetische Algorithmen an um sich Krieger zu züchten! Ganz verrückte Sache!

Die Idee ist schon über 10 Jahre alt und die “Arenen” sind relativ ausgereift, inklusive Debuggingfunktionen. Es gibt sie online als Applet und einige Implementationen wie ARES, Corewin oder den Klassiker pMars (inklusive Quellcode) den es auch für Linux gibt (wenn man nicht selber kompilieren will). Die Sprache (redcode) ist genormt und es gibt Turniere (sogenannte Hills) auf denen ständig Kampfprogramme gegeneinander antreten. Sogar ein Benchmark gibt es.

Eine gute Deutsche Einführung gibt W. Zimmer. Auf Englisch gibt es ganz viele verschiedene (einfach mal googeln oder wikipedien).

2. NetLogo

Kennt Ihr noch Logo? Die Sprache mit der Schildkröte (turtle) die man hemmungslos herumkommandieren konnte? NetLogo ist Logo auf Speed, denn mit ihm kann man fast beliebig viele Schildkröten kommandieren. Das ermöglicht sehr interessante Simulationen für verschiedene Fänomene wie Gerüchteausbreitung, Jäger/Beuteverhältnis, Seggregation, Partikelverhalten und besoffene Seemänner . Über NetHub ist NetLogo Client/Server fähig. Eine spassige und äusserst fesselnde Sache.

3. Robocode

Bei Robocode geht es darum in Java einen Roboter zu entwickeln. Dabei leitet man von einer Grundklasse ab und lässt die Roboter in einer grafisch schön gestalteten Arena gegeneinander antreten. Ursprünglich wurde das Spiel von IBM entwickelt, baer heute macht eine deutsche und eine englische Community weiter. Robocode ist eine geniale Möglichkeit, Java und objektorientiertes Design zu lernen.

package msc;

import robocode.*;

//import java.awt.Color;

/**

 * StupidZonk - a robot by (your name here)

 */

public class StupidZonk extends Robot

{

        /**

         * run: StupidZonk's default behavior

         */

        public void run() {

                // After trying out your robot, try uncommenting the import at the top,

                // and the next line:

                //setColors(Color.red,Color.blue,Color.green);

                while(true) {

                        // Replace the next 4 lines with any behavior you would like

                        ahead(100);

                        turnGunRight(360);

                        back(100);

                        turnGunRight(360);

                }

        }

        /**

         * onScannedRobot: What to do when you see another robot

         */

        public void onScannedRobot(ScannedRobotEvent e) {

                fire(1);

        }

        /**

         * onHitByBullet: What to do when you're hit by a bullet

         */

        public void onHitByBullet(HitByBulletEvent e) {

                turnLeft(90 - e.getBearing());

        }

}

4. CodeRuler

CodeRuler ist ein weiteres IBM Glanzstück: Sie, beziehungsweise Ihr Programm, ist eine Königin oder König und Herrscht über Land, Burgen, Ritter und Untertanen. Sie kämpfen gegen eine oder mehrere böse Königinnen und Könige in feindlichen Schlössern. Ritter können Bauern metzeln und Schlösser einnehmen, Bauern bestellen das Land und bringen Punkte um neue Bauern oder Ritter zu machen und im Schloss werden diese dann produziert.

Technisch bedeutet dies, dass man wieder eine Javaklasse ableitet und bestimmte Methoden überschreibt. Es macht unglaublich Spass und ganz nebenbei lernt man viel über Java.

Hier ein Beispiel eines etwas dementen Rulers:

import com.ibm.ruler.*;

import java.util.Random;

public class MyRuler extends Ruler {

    public String getRulerName() {

        return "Simple Ruler";

    }

    public String getSchoolName() {

        return "IBM developerWorks";

    }

    public void initialize() {

    }

    protected Random rand = new Random();

    public void orderSubjects(int lastMoveTime) {

    IPeasant[] peasants = getPeasants();

    for (int i = 0; i < peasants.length; i++) {

                move(peasants[i], rand.nextInt(8) + 1);

        }

    }   

}

5. Kara

Kara wurde von Swisseduc entwickelt und sieht schnufflig aus. Der “jööö”-Effekt soll aber nicht täuschen, denn beim Marienkäfer handelt es sich um eine ausgewachsene Zustandsmaschine. Mit dieser lassen sich einfachere und Komplexere Aufgaben lösen die im Programm vorgegeben sind. Das GUI ist sehr anwenderfreundlich und ermöglicht schnelle trial-error-Zyklen. Bis zum Schluss kann man die Grenzen von Zustandsmaschinen erfassen und bekommt ein gutes “Gefühl” für die Dinge.

Kara hat viele weitere Projekte: Multikara ermöglicht mehrere Zustandsmaschinen kooperativ zu betreiben, mit LegoKara kann ein richtiger Roboter Kara übernehmen und des Weiteren sind Anbindungen an viele Programmiersprachen vorhanden. Diese ermöglichen dann die Verbindung von der Zustandsmaschine zum Coden.

Zu Kara gibt es auch gute Unterrichtsmaterialien für eine Einführung in die Programmierung.

Buchempfehlung

Ein sehr beeinflussendes und eindrückliches Werk sind: A.K. Dewdney. Computer-Kurzweil und Computer-Kurzweil 2. Diese Bücher sprühen vor Ideen..! Leider gibt es keine Neuauflage und sie sind nur noch gebraucht zu erwerben…

Eingeordnet in Coding, Desktop | 4 Komentare »

Eclipse und die Umlaute

Geschrieben von skaldrom am 3. April 2007

Ganz einfach, schlicht und ergreifend, und kann einem Stunden sparen: Eclipse unter Linux importiert keine Projekte die einen Umlaut im Pfadnamen haben. GNARRRGH!

Eingeordnet in Coding, Linux | Keine Kommentare »

Einfache Objektpersistenz mit Netminds Persistence for Java

Geschrieben von skaldrom am 8. March 2007

Um einen weiteren komplexen und fehleranfälligen Teil unter meine Applikationen zu schieben, wollte ich Objektpersistenz mal ausprobieren. Es gibt da verschiedene Möglichkeiten:

Objektorientierte DB
Persistenzframework bzw Mapper auf eine relationale DB

Für Java gibts da die Schwergewichte Hybernate und JDO (bspw. mittels JPOX), die mir aber für ein kurzes Schnuppern zu schwergewichtig waren. Ich habe mich für Netminds “Persistence for Java” entschieden. Nachtrag: Das Projekt wurde umbenannt und heisst nun Beankeeper.

Bestehende Unterlagen:

BeanKeeper Tutorial: Wichtige Teile des Codes sind aber nicht abgedruckt, imports, etc…
BeanKeeper Dokumentation: Hier habe ich leider mehr über Ant gelernt als über Persistence
IBM Tutorial: Hier kann der Quellcode nicht runtergeladen werden? 404? Bei IBM????

Erstellen eines Projekts

Ich habe zum Ausprobieren Eclipse verwendet.

Neues Java Projekt erstellen
“lib/” Verzeichnis anlegen
Die Libraries netmind, log4j und java-cup-11-runtime sind im Download von Net Persistence dabei. Diese ins “lib/” Verzeichnis kopieren.
Den JDBC-Treiber (ev. den für MySQL) auch in dieses Verzeichnis.
Rechtsklick auf das Projekt -> Properties -> Java Build Path -> Libraries -> Add JARs und alle Libs hinzufügen.
Eine Datenbank und einen DB-Benutzer erstellen. Schema braucht es keines.

Quirks:

Beim Start gabs bei mir folgende Meldung:

Exception in thread "main" hu.netmind.persistence.StoreException: there are multiple network interfaces, but no recognizable preferred subnetwork ip

Ein Blick auf den Quellcode ergab, dass er in /java/hu/netmind/persistence/node/NodeServer.java, Zeile 151 irgendwie alle Interfaces durchgeht und nur eines auswählt wenn es mit “10.” oder “192.” beginnt. Meines beginnt mit 172. und so musste ich das in dieser Quelldatei ergänzen. Ant und Maven treiben mir den Angstschweiss auf die Stirn, aber ein simples “ant” im Basisverzeichnis des Downloads hat mir eine neue Lib gemacht. Super!

Code

Hier der Code… Als Resultat sollte er komplett und verständlich sein….

AddressStarter.java:

package ch.baden.Modul223.LA1002;

import hu.netmind.persistence.Store;

import java.util.*;

public class AdressStarter {

    public static void main(String[] args) {

        Store store = new Store("com.mysql.jdbc.Driver",

                "jdbc:mysql://localhost/persistence?user=persistence&amp;password=persistence");

        Address myAddress = new Address("Sarg", "Skaldrom Y.", "000-000");

        store.save(myAddress);

        List addresses = store.find("find Address");

        System.out.println("Total results: " + addresses.size());

        for (Object object : addresses) {

            Address bean = (Address) object;

            System.out.println(bean.toString());

        }

    }

}

Address.java:

package ch.baden.Modul223.LA1002;

public class Address {

    private String name;

    private String vorname;

    private String nummer;

    public Address(String name, String vorname, String nummer) {

        super();

        this.name = name;

        this.vorname = vorname;

        this.nummer = nummer;

    }

    public Address() {

    }

    public String getName() {

        return name;

    }

    public void setName(String name) {

        this.name = name;

    }

    public String getNummer() {

        return nummer;

    }

    public void setNummer(String nummer) {

        this.nummer = nummer;

    }

    public String getVorname() {

        return vorname;

    }

    public void setVorname(String vorname) {

        this.vorname = vorname;

    }

    public String toString() {

        return this.name + " " + this.vorname + "/" + this.nummer;

    }

}