WPC13

volkard

volkard schrieb:

sinnlos lange eigentlich.
100 sekunden.

auch wenn hume das nicht hören mag.
einfaches ersetzen von std::queue und std::map durch problemangepaßte queue und map brachten speedup um faktor 6.
jetzt 15 sekunden.

volkard

Ponto schrieb:

srechnung, aber für mich sieht das so aus: Für jedes Feld gibt es 5 mögliche Zustände.

ich habe auch keine ahnung von dem, was in der schule kombonatorik und stochastk genannt wird. meistens nur formeln ohne jede einsicht. zuerst wird bis ins bodenlose abstrahiert, und das problem wird in "urnenmodell", "bedingte wahrscheinlichkeiten" und weiß der teufel was klassifiziert. und dann schlägt man in der formelsammlung was nach, was dazu paßt und rechnet es aus.

aber ich denke, daß man beim generieren der welt einfach nur nen doublke mitlaufen lassen muss, der *=.8 bei keine-falle und *=.2 bei falle macht. und dann hat man am ende einer jeden welt auch die wahrscheinlichkeit, wie oft sie anzutreffen wäre. also doch 7.3 mio fälle.

Ponto

volkard schrieb:

aber ich denke, daß man beim generieren der welt einfach nur nen doublke mitlaufen lassen muss, der *=.8 bei keine-falle und *=.2 bei falle macht. und dann hat man am ende einer jeden welt auch die wahrscheinlichkeit, wie oft sie anzutreffen wäre. also doch 7.3 mio fälle.

Da hast du Recht. Es gibt nur 7.3 mio verschiedene Instanzen und jede hat eine Wahrscheinlichkeit des Auftretens. Es ist nur wichtig, dass dieser Faktor als Gewichtung mitberücksichtigt wird

volkard

Es gibt sogar viel weniger als 7.3 mio nenneswerte instanzen.

wenn ich folgende fallen hab:

....
pp..
..pp
....

dann sind die folgenden felder betretbar:

....
....
bb..
bbbb

und die folgenden felder sind mit kurzem sensor erfallsbar

....
ss..
ssss
ssss

bezüglich meiner sensorischen möglichkeiten sind alle kombinationen der fallen in den nicht-s-felder gleich. das sind 2^6 und alle möglichkeiten des goldes in den nicht-b-feldern sind gleich, das sind 10. und alle möglichkeiten des monsters in den nicht-s-feldern, das sind 6.

das wären 3840 bezüglich meiner sensorik gleichwertige instanzen.

Ponto

Noch schlimmer sieht es bei folgendem aus:

....
....
P...
.P..

Dennoch hat jede der nicht nennenswerten Instanzen eine eigene Gewichtung, die man ausrechnen müsste. Die Summe ist dann das Gesamtgewicht aller solchen Instanzen.

Aber da stellt sich folgende Frage: Ist es fair einmal so eine Instanz zu rechnen und dann mit dem Gesamtgewicht zu bewerten? Ein Bot könnte rand() benutzen um auf Risiko zu gehen. Er könnte sich sagen: Ich geh mit einer Wahrscheinlichkeit von 40% doch auf ein Feld, wo eine Falle sein könnte.

So ein Bot würde beim obigen Beispiel in 40% der Fälle sterben und in 60% aufgeben. Misst man jedoch nur eine Instanz, dann ist das Ergebnis mit 60% Wahrscheinlichkeit, dass er immer aufgibt, und mit 40% Wahrscheinlichkeit, dass er immer stirbt.

Genau die gleichen Überlegungen gelten auch wenn man alle 7.3 Mio Instanzen ausprobiert.

Ich bleibe dabei: Die einzige faire Möglichkeit, alle zu vergleichen, ist sehr viele Instanzen zu generieren und alle Agenten darauf laufen zu lassen. Die Instanzen müssen nach den Spezifikationen der Aufgabe generiert werden.

HumeSikkins

volkard schrieb:

volkard schrieb:

sinnlos lange eigentlich.
100 sekunden.

auch wenn hume das nicht hören mag.
einfaches ersetzen von std::queue und std::map durch problemangepaßte queue und map brachten speedup um faktor 6.

Netter Seitenhieb nur schlägst du den Falschen. Ich sage sowas wie "wenn vorhanden benutze eine passende Datenstruktur aus der Standardlib und bring das Programm zum Laufen. Wenn's funktioniert, du aber bessere Performance brauchst, bau dir problem-spezifische Datenstrukturen für die sinnvollen Stellen".
Ich baue nur ungern gleich die problem-spezifischen Datenstrukturen, weil ich dann zwei Dinge gleichzeitig testen muss und ich im Zweifelsfall auch noch zuviel arbeit mache.
Aber schön zu wissen, dass du mich nicht nur für nen BWLer sondern gleich auch noch für einen verblendeten Starrkopf hälst

-Foo-

Jetzt hab ich bei srand(0) und 1000000 auch die 341 erreicht :p

Ponto

-Foo- schrieb:

Jetzt hab ich bei srand(0) und 1000000 auch die 341 erreicht :p

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.

volkard

Ponto schrieb:

Dann wird der Sieger wohl die beste Wegsuche haben.

wie verbessert ihr die wegsuche? genetische algorithmen? neuronale netze? oder heuristiken wie "immer in die mitte"?

-Foo-

Ponto schrieb:

-Foo- schrieb:

Jetzt hab ich bei srand(0) und 1000000 auch die 341 erreicht :p

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.

Ja, ich hätte bei 200 aufgegeben

volkard

Ponto schrieb:

Dann wird der Sieger wohl die beste Wegsuche haben.

ja. mit abstand von +-10 auf die punktesumme bei 1 mio runden.

volkard

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.

Ponto

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

-Foo-

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?

Ponto

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

-Foo-

Ich ja, ich hab Ferien

Ponto

-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

volkard

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.

volkard

mein code hat nur noch eine schleife drin.

-Foo-

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