Technik, Gothic und Anderes

Technik ist Spiel, Gothic ist ernst und Zeit hat man zuviel

  • Kategorien

  • Tags

  • Archiv

  • Links

    zu Bee5

    blog.oncode.info läuft bei Cyon und ich bin sehr glücklich damit.

Mehr Glück als Verstand: Der Linux-Magazin Wettbewerb ist ausgefochten

Geschrieben von skaldrom am 14. Dezember 2010


Warning: Cannot use a scalar value as an array in /home/oncodein/public_html/blogoncodeinfo/wp-content/plugins/organize-series/orgSeries-template-tags.php on line 46

Warning: Invalid argument supplied for foreach() in /home/oncodein/public_html/blogoncodeinfo/wp-content/plugins/organize-series/orgSeries-template-tags.php on line 55
Dieser Beitrag ist Teil 3 von 3 in der Serie Linux-Magazin Wettbewerb

    Viele haben nicht mehr daran geglaubt, aber der Wettbewerb des Linuxmagazins ist durchgeführt worden: Im neusten Heft (01/11) sind die Gewinner abgedruckt. Siehe da, ich habs als einziger PHP-Frickler in die Top-20 geschafft:

    Das gute an Programmierwettbewerben ist, dass man mit einer solchen Rangierung für die Zukunft ausgesorgt hat: Reichtum, Jugend, Schönheit, Wein, willige Weiber und einen offiziellen Schutz vor Alterskurzsichtigkeit sind das Minimum das es zu gewinnen gab. Ähhm, nein, sorry, ich hab da was verwechselt.

    Auf jeden Fall: Heeeeeeeeeeerzliche Gratulation den Gewinnern! Gut gemacht! Die Turnierergebnisse und Bots sollen laut Heft alsbald downgeloaded werden können. Ganz im Sinne der Durchführung ist aber bis Dato noch nichts sichtbar. Ich werde sicher analysieren, warum der Frigidor nicht weheheit vor mir liegt. Unter uns gesagt, ist er nämlich viel der bessere Programmierer (der liebe Gott hat mir dafür eine grosse Klappe geschenkt).

    Mein Wettbewerbseintrag

    Vorgehen

    Zu Beginn habe viel experimentiert. Mit einem selbst geschriebenen Simulator habe ich mit einfacher Parametrisierung und naiver Taktik versucht, die Anzahl Transaktionen pro Spiel zu minimieren. Später habe ich verschiedene Generationen meiner Bots auf dem offiziellen Trainingsserver in den Kampf geschickt. Von sehr umfangreichen, komplexen Taktiken habe ich wieder auf sehr einfache gewechselt, nur um dann wieder zurück ins Komplexe zu wechseln. Ganz Grundsätzlich habe ich versucht, die Theorie mit der Praxis (Messungen und Statistiken) und dem Bauchgefühl zu verbinden.

    Die Implementation

    Leider bin ich kurz vor Schluss auf die Webseite gestossen, die das Problem sowohl akademisch als auch praktisch für das Spiel “Pig Dice” gelöst hat. Diese Lösung habe ich auf die Regeln des Wettbewerbs angepasst, in Java vorberechnet und in meinem Wettbewerbsbot implementiert.

    Der Spieler verwendet die vor-berechneten Spielzüge dieses Java-Programms:

    public class PigSolver {

        int goal;
        double epsilon;
        double[][][] p;
        boolean[][][] roll;

        PigSolver(int goal, double epsilon) {
            this.goal = goal;
            this.epsilon = epsilon;
            p = new double[goal][goal][goal];
            roll = new boolean[goal][goal][goal];

            valueIterate();
        }

        void valueIterate() {
            double maxChange;
            do {
                maxChange = 0.0;
                for (int i = 0; i < goal; i++) // for all i
                {
                    for (int j = 0; j < goal; j++) // for all j
                    {
                        for (int k = 0; k < goal - i; k++) { // for all k
                            double oldProb = p[i][j][k];
                            double pRoll = ((1.0 - pWin(j, i, 0)) + pWin(i, j, k + 1) + pWin(i, j, k + 2) + pWin(i, j, k + 3) + pWin(i, j, k + 4) + pWin(i, j, k + 5)) / 6;
                            double pHold = 1.0 - pWin(j, i + k, 0);
                            p[i][j][k] = Math.max(pRoll, pHold);
                            roll[i][j][k] = pRoll > pHold;
                            double change = Math.abs(p[i][j][k] - oldProb);
                            maxChange = Math.max(maxChange, change);
                        }
                    }
                }
            } while (maxChange >= epsilon);
        }

        public double pWin(int i, int j, int k) {
            if (i + k >= goal) {
                return 1.0;
            } else if (j >= goal) {
                return 0.0;
            } else {
                return p[i][j][k];
            }
        }

        public void outputHoldValues() {
            for (int i = 0; i < goal; i++) {
                for (int j = 0; j < goal; j++) {
                    int k = 0;
                    while (k < goal - i && roll[i][j][k]) {
                        k++;
                    }
                    System.out.print(k + " ");
                }
                System.out.println();
            }
        }

        public void summarize() {
            System.out.println("p[0][0][0] = " + p[0][0][0]);
            System.out.println();
            System.out.println("i\tj\tPolicy changes at k =");
            for (int i = 0; i < goal; i++) // for all i
            {
                for (int j = 0; j < goal; j++) { // for all j
                    int k = 0;
                    System.out.print(i + "\t" + j + "\t" + (roll[i][j][k] ? "roll " : "save "));
                    for (k = 1; i + k < goal; k++) // for all valid k
                    {
                        if (roll[i][j][k] != roll[i][j][k - 1]) {
                            System.out.print(k + " " + (roll[i][j][k] ? "roll " : "save "));
                        }
                    }
                    System.out.println();
                }
            }
        }

        public void summarizePHP() {
            System.out.println("$optimalWin = array();");
            for (int i = 0; i < goal; i++) // for all i
            {
                for (int j = 0; j < goal; j++) { // for all j
                    int k = 0;
                    System.out.println("$optimalWin["+i+"][" + j + "][0]='" + (roll[i][j][k] ? "roll" : "save") + "';");
                    for (k = 1; i + k < goal; k++) // for all valid k
                    {
                        if (roll[i][j][k] != roll[i][j][k - 1]) {
                            System.out.println("  $optimalWin["+i+"][" + j + "]["+k+"]='" + (roll[i][j][k] ? "roll" : "save") + "';");
                        }
                    }
                }
            }
        }

        public static void main(String[] args) {
            //new PigSolver(100, 1e-9).outputHoldValues();
            //new PigSolver(50, 1e-10).summarizePHP();
            new PigSolver(50, 1e-15).summarize();
        }
    }


    Lassen Sie eine Antwort hier...

    XHTML: Sie können folgende Tags verwenden: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


    × 7 = zwanzig acht