WPC13

-Foo-

TGGC schrieb:

Wir wollen ja nicht, das volkard Minderwertigkeitskomplexe bekommt.

Bye, TGGC (Keine Macht den Dummen)

*hrhr*

volkard

-Foo- schrieb:

In was für Punkte-Bahnen bewegt ihr euch gerade so? *neugierieg sei*

hab gerade auch die 341 erreicht. bei 100000 messungen und srand(0) am anfang.

Ponto

volkard schrieb:

-Foo- schrieb:

In was für Punkte-Bahnen bewegt ihr euch gerade so? *neugierieg sei*

hab gerade auch die 341 erreicht. bei 100000 messungen und srand(0) am anfang.

Dann hatte ich wenigstens keinen Mist gebaut.

-Foo-

Hm... bei srand(0) und 1.000.000 Durchläufen komm ich bei mir nur auf 329.7 Punkten/Runde

Wie lange braucht dein Agent dafür?

volkard

Ponto schrieb:

Bei weniger als 10000 ist die Streuung noch zu groß. Deshalb schlage ich Jester ja vor mindestens 100 Mio zu nehmen

es gibt 15 felder, die ein loch haben können.
macht 2^15 für alle lochmöglichkeiten.
es gibt 15 felder, wo das monster sehen kann, macht 15 für alle monstermöglichkeiten.
es gibt 15 felder, wo das gold liegen kann, macht 15 für alle goldmöglichkeiten.

macht 2^15*15*15 mögliche welten.
also nur 7372800 stück.
viel besser, also 100 mio zufällige welten zu testen, ist es, einfach alle 7.3 mio welten zu testen.

Ponto

-Foo- schrieb:

Hm... bei srand(0) und 1.000.000 Durchläufen komm ich bei mir nur auf 329.7 Punkten/Runde

Wie lange braucht dein Agent dafür?

329,7 kann ja noch innerhalb der Schwankungen liegen, glaube ich. Für 1.000.000 Durchgänge braucht er hier auf einem P4 2.4GHz 160 Sekunden. Ich aber nicht bis zum Ende durchoptimiert.

-Foo-

Schwanken tuts bei mir nur zwischen $\frac{+}{}$5 Punkten.
(Wie macht man das +- ohne Latex? )

Auf meinem 1.4GHZ brauch ich etwa 45Sekunden...

Ponto

volkard schrieb:

Ponto schrieb:

Bei weniger als 10000 ist die Streuung noch zu groß. Deshalb schlage ich Jester ja vor mindestens 100 Mio zu nehmen

es gibt 15 felder, die ein loch haben können.
macht 2^15 für alle lochmöglichkeiten.
es gibt 15 felder, wo das monster sehen kann, macht 15 für alle monstermöglichkeiten.
es gibt 15 felder, wo das gold liegen kann, macht 15 für alle goldmöglichkeiten.

macht 2^15*15*15 mögliche welten.
also nur 7372800 stück.
viel besser, also 100 mio zufällige welten zu testen, ist es, einfach alle 7.3 mio welten zu testen.

100 Mio war auch recht hoch gegriffen. Je nach Optimierungen, die man hier so anstellt können 7.3 Mio schon zu viel für Jester werden. Er hat uns ja nur gebeten weniger als 1 Sekunde pro Zug zu machen. Meine erste Implementierung war zwar nicht im 1 Sekunde Bereich, aber hätte für 7.3 Mio 32 Stunden benötigt.

volkard

-Foo- schrieb:

Hm... bei srand(0) und 1.000.000 Durchläufen komm ich bei mir nur auf 329.7 Punkten/Runde

ballerst du auch fein das monster tot? immerhin könnte es den schatz als kopfkissen benutzen.

Wie lange braucht dein Agent dafür?

sinnlos lange eigentlich.
100 sekunden.

aber die funktionen müßte ich für mehr speed so schlimm verkomplizieren, daß ich gar keinen spielraum mehr hätte, einen neuen trick einzubasteln.

in der annahme, daß ich eine der langsamsten implemetierungen habe, brüchte man um alle 7.3 mio welten zu testen also ca 7372 sekunden, was zwei stunden sind.

auf meinem celeron mit 400 MHz.

-Foo-

volkard schrieb:

-Foo- schrieb:

Hm... bei srand(0) und 1.000.000 Durchläufen komm ich bei mir nur auf 329.7 Punkten/Runde

ballerst du auch fein das monster tot? immerhin könnte es den schatz als kopfkissen benutzen.

Logisch

Ponto

Einfach alle 7.3 Mio möglichen Instanzen auszuwählen und die Algorithmen darauf laufen zu lassen ist nach den Regeln verboten. Betrachtet man alle Instanzen nur einmal, so ist die Instanz mit 15 Fallen und dem Gold auf (2,1) genauso wahrscheinlich wie keine Falle und Gold auf (2,1). Nach den Regeln befindet sich zu 20% eine Falle auf einem Feld und nicht zu 50%, wie in der Rechnung. Deshalb ist die Instanz mit 15 Fallen wesentlich unwahrscheinlicher als die Instanz mit keiner Falle.

Ich hab zwar wenig Ahnung von Kombinatorik und Wahrscheinlichkeitsrechnung, aber für mich sieht das so aus: Für jedes Feld gibt es 5 mögliche Zustände.

1 bedeutet: Falle
2-5 bedeuten: keine Falle

Die Anzahl aller Instanzen entsprechend den Regeln ist damit:
5^15*15*15 = 6.866.455.078.125

So wird Jester nicht alle möglichen Instanzen ausprobieren können.

Eine Möglichkeit, dies zu umgehen, ist es alle 7.3 Instanzen im 50% Fall berechnen zu lassen und jede Instanz dann mit der Wahrscheinlichkeit ihres Auftretens zu gewichten.

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"?