3. WPC13

WPC13

  • -

    volkard schrieb:

    Ponto schrieb:

    Dann wird der Sieger wohl die beste Wegsuche haben. Hätte ich nicht verratten, dass 341 möglich sind, hätten manche wohl die Suche früher abgebrochen.

    weiß nicht. der weg bis 341 ist doch geradlinig.
    spannender ist, ob 342 oder gar 343 gehen.

    Gilt 341 irgendwie als magische-grenze? hab ich was nicht mitbekommen? irgendne mathematische beweislage? 🙂

    0
  • P

    volkard schrieb:

    Ponto schrieb:

    Dann wird der Sieger wohl die beste Wegsuche haben. Hätte ich nicht verratten, dass 341 möglich sind, hätten manche wohl die Suche früher abgebrochen.

    weiß nicht. der weg bis 341 ist doch geradlinig.
    spannender ist, ob 342 oder gar 343 gehen.

    Ist spannender, aber man kann ja nicht 24 Stunden am Tag an dem Problem hängen 🙂

    0
  • -

    Ich ja, ich hab Ferien 🙂

    0
  • P

    -Foo- schrieb:

    Gilt 341 irgendwie als magische-grenze? hab ich was nicht mitbekommen? irgendne mathematische beweislage? 🙂

    Du kannst wie gesagt alle Instanzen auf dein Programm anwerfen, die es gibt, und einen Erwartungswert ausrechnen. Dieser hängt dann meiner Meinung nach davon ab, wie gut die Wegsuche ist. Du musst ja manchmal entscheiden wohin du als nächstes gehst, und nicht immer ist das Naheliegendste langfristig das Beste.

    Hier mal Code zum Erzeugen aller Instanzen:

    Erst die main:

    int main(int argc, char *argv[])
{
   double total = 0.0;
   for(unsigned i= 0; i < 7372800; ++i )
   {
      Wpc13 agent;
      World world(i);
      agent.solve(&world);
      total += (agent.getScore() * (world.getWeight()/225));
   }
   cout.precision(15);
   cout << "Score: " << total << endl;
}

    World.h bekommt zwei Methoden und einen Datenmember:

    World(unsigned int world);
double getWeight();

double weight;

    World::World(unsigned int world)
   : bumped_(false), monsterDead_(false), monsterDied_(false), weight(1.0)
{
   for(int i=0; i<6; ++i)
   {
      field_[i][0] = field_[i][5] = boundary;
      field_[0][i] = field_[5][i] = boundary;
   }

   for (int i = 1; i != 5; ++i) {
      for(int j = 1; j != 5; ++j) {
         field_[i][j] = FieldState(0);
      }
   }

   int pos = (world % 15) + 1;
   world /= 15;
   int x = (pos%4) + 1;
   int y = (pos/4) + 1;
   field_[x][y] = FieldState(field_[x][y] | monster);

   pos = (world % 15) + 1;
   int xx = (pos%4) + 1;
   int yy = (pos/4) + 1;

   field_[xx][yy] = FieldState(field_[xx][yy] | gold);

   int traps = 0;
   for (int i = 1; i != 5; ++i) {
      for(int j = 1; j != 5; ++j) {
         if ((i == 1 and j == 1)) continue;
         if ((world % 2) == 0) {
            ++traps;
            weight *= 0.2;
            field_[i][j] = FieldState(field_[i][j] | pit);
         } else {
            weight *= 0.8;
         }
         world /= 2;
      }
   }
}

double World::getWeight()
{
   return weight;
}

    \\EDIT: Code berichtigt

    0
  • V

    Ponto schrieb:

    Ist spannender, aber man kann ja nicht 24 Stunden am Tag an dem Problem hängen 🙂

    ja, man muß auch ebay machen, chatten und spielen, damit es nicht einseitig wird.

    0
  • V

    mein code hat nur noch eine schleife drin.

    0
  • -

    Klasse, und ich hab gut 900unübersichtliche zeilen, 20 funktionen und keine lust mehr, was drann zu ändern... 🙂

    0
  • V

    -Foo- schrieb:

    Klasse, und ich hab gut 900unübersichtliche zeilen, 20 funktionen und keine lust mehr, was drann zu ändern... 🙂

    316 zeilen
    23 funktionen, davon 6 mit mehr als einem statement.
    aber das ändert sich noch. bin froh, daß es nach dem redesign noch läuft.
    aber noch habe ich nix, was mich über 341 bringt. morgend wird sich auszahlen, daß ich meinen neuen code ändern kann.

    0
  • P

    volkard schrieb:

    mein code hat nur noch eine schleife drin.

    Macht das das Ergebnis besser?

    0
  • P

    Hab 709+105 zeilen und 29 schleifen.

    0
  • V

    Ponto schrieb:

    volkard schrieb:

    mein code hat nur noch eine schleife drin.

    Macht das das Ergebnis besser?

    nee, überhaupt nicht.
    ich hoffe nur, daß ich dadurch die möglichkeit hätte, ihn besser zu machen, wenn mir ein toller trick einfiele.

    aber ist wohl nicht so. 341 bleibt 341. ok, vielleicht habe ich nachkommastellen verbessert. ich werfe jetzt Pontos messprogramm an und schau morgen früh nach.

    0
  • V

    Ponto schrieb:

    Da mein Algorithmus keine Harakirientscheidungen, a la rand() macht, kann ich den Erwartungswert genau ausrechnen. Dieser liegt bei 341.362786787123

    auch mit dem korrigierten messprog?
    ich bin jetzt leicht über 342.

    0
  • P

    Könnte dann die Aufgabenstellung aktualisiert werden, oder bleibt sie so wie sie ist ???

    Devil

    0
  • P

    devil81 schrieb:

    Könnte dann die Aufgabenstellung aktualisiert werden, oder bleibt sie so wie sie ist ???

    Devil

    Was sollte aktualisiert werden?

    0
  • P

    Ponto schrieb:

    devil81 schrieb:

    Könnte dann die Aufgabenstellung aktualisiert werden, oder bleibt sie so wie sie ist ???

    Devil

    Was sollte aktualisiert werden?

    Dinge die hier im Thread stehen, sind nicht mit dem wpc Forum deckungsgleich.
    So z.b. die Form wie was jetzt eingesandt werden soll etc.

    0
  • P

    devil81 schrieb:

    Ponto schrieb:

    Was sollte aktualisiert werden?

    Dinge die hier im Thread stehen, sind nicht mit dem wpc Forum deckungsgleich.
    So z.b. die Form wie was jetzt eingesandt werden soll etc.

    Ich denke mal, das wpc Forum ist die Referenz

    0
  • J

    Jo, kann ich machen 🙂

    aber ist das wirklich sooo wichtig?

    0
  • P

    Jester schrieb:

    Jo, kann ich machen 🙂

    aber ist das wirklich sooo wichtig?

    wollte nur damit wissen, welches nun die Anforderungen sind,
    und ob sich was dran geändert hat.

    Devil

    0
  • P

    Da die Zeit abgelaufen ist, hier mal der Bot, den ich geschrieben habe:

    http://www.pontohonk.de/wpc13/PontoAgent.tgz

    Die Arbeitsweise ist einfach:

    1. Wenn ein neues Feld betreten wurde, sammle alle verfügbaren Informationen zusammen

    2. Analysiere die Situation
    2a) Falls es ein definitiv freies Feld gibt, gehe dort hin.
    2b) Falls es kein freies Feld gibt, aber ein Feld, das frei wird, wenn man das Monster tötet. gehe zum ersten solchen Feld.
    2c) Falls keiner der beiden oberen Fälle zutrifft, checke ob das Feld eine der gespeicherten Formen hat, gehe dann das Risiko ein auf eine Falle zu treten. Die gespeicherten Fälle sind alle Situationen, in denen es auf lange Sicht besser ist ein Risiko einzugehen.
    2d) Falls nichts zutrifft, gebe auf.

    3. Wird ein Weg gesucht, so läuft ein einfacher Dijkstra, der die kürzeste Zugfolge sucht, bis ein Prädikat erfüllt ist. Für die Fälle 2a) 2b) und 2c) gibt es jeweils ein eigenes Prädikat.

    4. Führe die Zugfolge aus, bis das Zielfeld erreicht wurde.

    Die wesentlichen Methoden sind:

    update_info() für 1.
    analyse() für 2.
    search_path() für 3.
    move() für 4.

    Die riskanten Fälle sind in der riskmap kodiert. Dabei sind die Felder wie folgt benannt:

    DHLP
    CGKO
    BFJN
    AEIM

    Nach jedem Feld steht die Information, wie oft für das Feld eine Falle in einem benachbarten Feld gemeldet wurde. Eine G2 bedeutet also, auf zwei Nachbarfeldern von G wurde ein Luftzug gespürt. Zu jeder Situation gibt es die Information, auf welches Feld man treten kann.

    Insgesamt hat der Bot einen Erwartungswert von 348.791945988877 Punkten pro Runde.

    0
  • V

    Ponto schrieb:

    2c) Falls keiner der beiden oberen Fälle zutrifft, checke ob das Feld eine der gespeicherten Formen hat, gehe dann das Risiko ein auf eine Falle zu treten. Die gespeicherten Fälle sind alle Situationen, in denen es auf lange Sicht besser ist ein Risiko einzugehen.
    Insgesamt hat der Bot einen Erwartungswert von 348.791945988877 Punkten pro Runde.

    damit haste mich um längen geschlagen.
    342,280

    0
Anmelden zum Antworten