Ein kleines Matheproblem (Details unten)

[Kokujou]

(P(A) + P(B)) * P(C) = P(B) * P(C) + P(A) * P(C) =|= P(A) * P(B) + P(B) * P(C) + P(A) * P(C)

Ja eben. Aber es wäre einfacher den ersten Term auszurechnen weil er weniger mathematische Operationen drin hat und damit wäre es ein Laufzeiterfolg und darum mache ich das aktuell auch so.

https://github.com/Kokujou/Hanafuda/blob/master/Assets/External/Scripts/KI/Omniscient/Omniscient.cs
Vielleicht hilft dir das.

Verlinke lieber die OmniscientYakus.cs, die hier ist nur für die Koordination und das Auswerten der Ergebnisse zuständig. Der Code um den es geht ist in der OmniscientYakus.

 

[Kokujou]

Ich spiele ehrlich gesagt auch mit der Idee folgende Näherung zu nehmen:
(P(1) * P(2) * ... * P(k))^(1/n)

Ich meinte natürlich (P(1) * P(2) * ... * P(n))^(1/k)

 

[BeBur]

Die Wurzel ist traditionell von den Rechenoperationen, die einem so spontan einfallen, die mit Abstand langsamste und gerne mal die, die man tatsächlich in einem Algorithmus mit 'Tricks' entfernt.
Hängt aber natürlich daran, wie oft die Wurzel dann am Ende berechnet werden müsste.

 

[0-8-15 User]

aus P(A) * P(B) + P(B) * P(C) + P(A) * P(C) könnte man auch (P(A) + P(B)) * P(C) machen

Das ist hoffentlich ein Scherz.

 

[Kokujou]

Das ist es ja. Einmal XD Darum ist die Wurzel garantiert tausend mal besser als dieses schreckliche Additionskonstrukt aufzubauen.

Und... ja ich glaub wenn ich sage das war ein Scherz komm ich am besten weg... Das war ja wirklich extrem dämlich.

 

[0-8-15 User]

Kannst du nicht alle Karten, die noch für einen bestimmten Yaku fehlen, über einen Kamm scheren? Dann könntest du versuchen abzuschätzen, wie wahrscheinlich es ist, die fehlenden Karten in den verbleibenden Spielzügen einzusammeln. Was wesentlich weniger rechenintensiv wäre.

Der 10er Yaku ist doch außerdem eh nur dann möglich, wenn du zu Spielbeginn schon mindestens zwei passende Karten hast, oder hab ich die Regeln nicht verstanden?

Stellt euch mal vor dass 8/10 meiner Karten ne Zugwahrscheinlichkeit von 1 haben

Warum betrachtest du die Karten dann überhaupt? Die spielen für die eigentliche Rechnung doch überhaupt keine Rolle mehr. Entscheidend sind doch nur die Karten, die noch fehlen, um ein Yaku zu erreichen. Nicht die, die du sowieso schon hast ...

Ich versteh nur Bahnhof bei deiner aktuellen Logik. Und ich bekomm auch nicht auf die Reihe, dass als angehender M.Sc es in 6 Seiten noch nicht geschafft hast uns gedanklich abzuholen. Vielleicht einfach mal eine Woche was anderes machen und das Problem mit ein wenig Abstand neu betrachten.

 

[Kokujou]

Grundsätzlich tu ich das. Natürlich schmeiße ich bei den Berechnungen alle Karten raus die bereits eingesammelt worden... glaube ich zumindest XD zumindest ist das der Plan.

Der 10er-Yaku ist in jeder hinsicht mglich. Bedenke dass du bei jedem Spielzug im BESTFALL 4 Karten einsammeln kannst. und du nicht nur mit deiner Hand sondern auch mit dem Deck spielst. Du hast am Anfang 8 Karten auf der Hand und eine Karte vom Deck ziehst du am ende deines Zuges mit der du wieder einsammeln kannst. Also hast du 16 möglichkeiten Karten des betreffenden Typs einzusammeln. Und mit jedem einsammeln sammelst du nicht eine sondern entweder keine, 2 oder 4 Karten ein.

Ich betrachte keine Karten von Whkt = 1... hoffentlich... Ist auf jeden Fall der Plan. Aber ich will euch halt sagen dass es MÖGLICH ist. und damit eine gesamtwahrscheinlichkeit > 1 entsteht. Karten schließen sich nicht gegenseitig aus, was bei eurem Modell wohl aus irgendeinem Grund der Fall ist. Nur weil ich eine Karte einsammle, selbstw enn wir nur einen Zug betrachten, kann ich trotzdem noch andere einsammeln. Also summieren sich die Wahrscheinlichkeiten der Karten auch nicht zu 1.

Ich kann euch deswegen nicht abholen weil ich keine Ahnung von mathe oder Statistik oder sonstewas habe. Ich hatte gehofft dass das hier ein kleines Problem wird und es wirft mich total aus der Bahn dass das jetzt doch so komplex ist. Ich hab bestenfalls Grundlagenwissen in Statistik und eigentlich auch nicht vorgehabt das zu intensivieren darum frage ich ja euch.

Es ist auch völlig unnötig mein Modell oder das Spiel zu verstehen. darum sage ich jetzt gefühlt zum 100. mal:
"Wie hoch ist die Wahrscheinlichkeit mindestens x von y Ereignissen zu erreichen"?
Unter der Voraussetzung dass diese Ereignisse unabhängig sind und sich nicht zu 1 aufsummieren.

Das Problem ist wirklich keine Wissenschaft. Diese Frage zu verstehen auch nicht. Aber je mehr ich erkläre desto mehr kommt ihr mit Worten die da drin gar nichts zutun haben. Wieviele Züge? Was für Züge von Zügen hab ich doch gar nichts gesagt. Es gibt keine Anzahl von Ziehungen. Ich habs am Anfang doch extra so formuliert dass meine Problemstellung abgespeckt und vom eigentlichen Thema unabhängig ist.

Aber die Frage ist ja jetzt beantwortet. Additionssatz. Google-Recherche und praktische anwendung ergibt dass das schlicht und einfach nicht möglich ist und Kosten und Nutzen vermutlich auch total vermüllt sind. Besonders wenn man die ganzen Abzüge der Schnittwahrscheinlichkeiten noch einbringt die man nun vieleicht oder auch nicht braucht.

Darum ändere ich mein Problem und ziehe jetzt einfach die x.te Wurzel aus den größten k Ereignissen oder so. das ist dann quasi der statistische Oberwert und die Wurzel dient. Oder ich streich die Wurzel raus und nehme nur die Multiplikation der größten k Ergebnisse. Das ist ja quasi der Basiswert. Danach kommen noch andere und vor allem kleinere Werte hinzu.

Vielleicht könnt ihr mir ja helfen und mir ne Art obere Schranke dieses n-stelligen Additionssatzes verraten. Falls es sowas gibt. Wenn man mit dem größten Wert beginnt werden ja immer kleinere und kleinere werte aufaddiert also wird es wohl gegen irgendeinen Wert konvergieren, besonders wenn die Anzahl der Faktoren dann auch noch wächst. Das würde ja dann als wahrscheinlichkeit reichen.

 

[0-8-15 User]

"Wie hoch ist die Wahrscheinlichkeit mindestens x von y Ereignissen zu erreichen"?
Unter der Voraussetzung dass diese Ereignisse unabhängig sind und sich nicht zu 1 aufsummieren.

Letzter Vorschlag: Wie wäre es, wenn du die Wahrscheinlichkeit einfach empirisch ermittelst? Du würfelst das Ganze ein paar tausendmal aus und zählst, wie oft das gewünschte Ereignis eingetreten ist. Dann hast du die empirische Wahrscheinlichkeit und die konvergiert gegen den wahren Wert.

Dann musst du nur noch abschätzen, wie oft du würfeln musst, damit das Ergebnis hinreichend genau ist.

 

[BeBur]

"Wie hoch ist die Wahrscheinlichkeit mindestens x von y Ereignissen zu erreichen"?
Unter der Voraussetzung dass diese Ereignisse unabhängig sind und sich nicht zu 1 aufsummieren.

Das kann dir vermutlich keiner beantworten. Wenn vier Karten auf dem Tisch liegen die du nehmen kannst und denen du damit eine Wahrscheinlichkeit von jeweils Eins zuordnen willst und also in der Summe Vier ausrechnest - dann würde das bedeuten, dass die Wahrscheinlichkeit so wie du es aufsummieren willst 400% ergibt.
Das ganze lässt sich von daher schon rein intuitiv nicht beantworten.

Ich kann euch deswegen nicht abholen weil ich keine Ahnung von mathe oder Statistik oder sonstewas habe. Ich hatte gehofft dass das hier ein kleines Problem wird und es wirft mich total aus der Bahn dass das jetzt doch so komplex ist. Ich hab bestenfalls Grundlagenwissen in Statistik und eigentlich auch nicht vorgehabt das zu intensivieren darum frage ich ja euch.

Du fragst zwar, aber ignorierst die Antworten. Du sagst du hast keine Ahnung, sagst aber die ganze Zeit, wir verstehen nicht.

 

[Kokujou]

Man muss keine Ahnung von Statistik zu haben um zu verstehen dass die Antworten hier widersprüchlich sind und von falschen Grundannahmen ausgehen.

Aber dann gehen wir es doch mal so an. Bei der Problematik "Mindestens k von n":
1. wenn k Ereignisse die Whkt 1 haben muss das Ergebnis der Funktion 1 sein.
2. Wenn weniger als k Ereignisse eine Wahrscheinlichkeit > 0 haben ist das Ergebnis 0
3. Wenn weniger als n-k Ereignisse die Wahrscheinlichkeit = 0 haben muss das Ergebnis trotzdem > 0 sein.
4. Der Werteberech der Funktion liegt zwischen 0 und 1, darf also nicht > 1 werden.

Die Formel des Additionssatz könnte theoretisch auf über 1 kommen, fliegt also raus.
Das stumpfe aufsummieren aller n Wahrscheinlichkeiten geht nicht, denn dann hätte 0 zu viel einfluss.
Durchschnitt geht nicht, denn dann wäre das Ergebnis >0, selbst wenn nicht genug Ereignisse da sind.

Die beste Lösung die ich mit diesen Kriterien finde ist das produkt aus der k größten Wahrscheinlichkeiten.
Dieser Wert sagt zunächst mal sinnvoll aus, dass diese Werte durch ein & verknüpft werden. Sie also gleichzeitig auftreten. Außerdem nimmt der Wert 0 an wenn eine der k größten Whkt 0 ist, also nicht genug >0 vorhanden sind.
Weiterhin ist er 1 wenn die k größten 1 sind. Erfüllt also alle Kriterien.

Natürlich räume ich ein, dass das nicht die beste Lösung überhaupt ist. Das war jetzt quasi die Manuelle Anwendung des Candidate Elminiation Algorithmus vielleicht wird dadurch ja deutlich was ich will.

PS: Wer wissen will wie ich die Einzelwahrscheinlichkeiten approximiere sehe hier nach:
https://github.com/Kokujou/Hanafuda/tree/master/Assets/External/Scripts
Stichwort Funktion CalcProbs

 

[BeBur]

1. wenn k Ereignisse die Whkt 1 haben

Das geht schon nicht. Wenn ein Ereignis zu 100% eintritt, dann treten alle anderen (unabhängigen) Ereignisse auf keinen Fall ein. Dein Denkfehler ist vermutlich, dass wenn Bube und König offen auf den Tisch liegen und du beide nehmen kannst, dann ist es keine Frage von Wahrscheinlichkeit mehr, welche der Karten du erhältst. Wahrscheinlichkeitsrechnung modelliert Unwissenheit.

 

[Kokujou]

Leute wenn die Wahrscheinlichkeit ne Münze zu werfen 50% ist und die Wahrscheinlichkeit dass es irgendwo auf der Welt regnet 75% summiert sich das auch nicht zu eins aber man kann berechnen wie hoch die Wahrscheinlichkeit ist dass beides gleichzeitig eintritt.

und nein... zum gefühlt 300. Mal: Es schließt sich nicht aus!!!!!!!!!!!!!!!!!!!!!!!

Du kannst in einem Zug bis zu 8 Karten gleichzeitig einsammeln. Und du kannst in einem gesamten Spiel ... puuh... 32 Karten einsammeln. +- ein paar die ich jetzt nicht konkret berechnen möchte. Und es gibt nur 48.

Erstmal kannst du in einem Zug deine Karte von der Hand aufs Feldlegen und so 0 2 oder 4 Karten einsammeln.
Dann machst du dasselbe nochmal mit der Karte vom Deck.

Darum summieren sich meine Wahrscheinlichkeiten nicht zu 1. Ich abstrahiere meinen Zug sogar soweit dass es möglich wäre in einem Zug alle 48 Karten einzusammeln. Ausgeschlossen derer mit Whkt 0. Und dass das Spiel nach einem Zug auch direkt beendest. Ich plätte also quasi die 8 möglichen Züge auf einen herunter, um mir die Berechnung zu vereinfachen.

Ich weiß nicht wie ich es noch einfacher erklären kann.

 

[0-8-15 User]

Die Lösung in #108 gefällt dir nicht? Mit 10000 Würfen bist du extrem nah am korrekten Ergebnis dran und das zu berechnen dauert selbst in Python keine 10 ms.

Außerdem hat @simpsonsfan dir doch die allgemeingültige Formel (Siebformel) präsentiert, nur gefällt sie dir nicht. Und weiter vereinfachen kann man die nicht, ohne das Ergebnis zu verfälschen.

 

[Kokujou]

Oh die hab ich wohl überscrollt.
Auswürfeln...
Also du versuchst quasi jede der x<48 Karten mit Whkt >0 zu ziehen mit nem Random-Generator?
das ist... wirklich interessant Das könnte ich als Richtwert benutzen. Klingt zwar sehr nach bruteforce aber wennich den Additionssatz als alternative sehe ist das wirklich ne klevere Idee

Ja sie gefällt mir nicht das ist das Problem vor dem ich gerade stehe ^^ mich deem Ergebnis dieser formel anzunähern ohne mehrere Minuten ans Rechnen zu verschwenden ^_^

 

[BeBur]

Leute wenn die Wahrscheinlichkeit ne Münze zu werfen 50% ist und die Wahrscheinlichkeit dass es irgendwo auf der Welt regnet 75%

Wenn du P(A oder B oder C) = P(A) + P(B) + P(C) rechnest, dann hast du die Schnittmenge dreifach drin.
Siehe dieses Bild hier

Die Mitte addierst du fälschlich dreimal dazu statt nur einmal und die anderen Schnittmengen doppelt statt einmal.
Deswegen muss man sie wieder subtrahieren und das ist genau das Prinzip beim Additionssatz.

Oh die hab ich wohl überscrollt.

Wurde dir hier schon mehrmals vorgeschlagen und ist vom Prinzip her bekannt unter dem Namen Monte-Carlo-Simulation.

 

[new Account()]

Dann musst du nur noch abschätzen, wie oft du würfeln musst, damit das Ergebnis hinreichend genau ist.

Oder man sucht sich ein epsilon als Konvergenzkriterium:
Falls sich die Wahrscheinlichkeit durch die letzten x Züge weniger als epsilon geändert hat, wird abgebrochen.

Echt nette Idee - sollte ich mir merken.

 

[Kokujou]

Ich bin auch total begeistert! Ich versuch ja immer unkonventionell zu denken aber es einfach auszuprobieren darauf wär ich nicht gekommen XD

Also diese Additionssatz-Siebformel bei der man noch die Schnittmengen rausrechnen muss können wir auf jeden Fall in jede Form von Tonne kloppen. Laufzeitineffizient ist da noch milde ausgedrückt. Da dauert eine Iteration meines worst case yaku ja schon 15 sekunden XD

ob man das ergebnis dieser bruteforce-methode auch gleich mathematisch ermitteln kann statt es tatsächlich auszuprobieren?

 

[0-8-15 User]

Also du versuchst quasi jede der x<48 Karten mit Whkt >0 zu ziehen mit nem Random-Generator?

Ja, und zwar 10000 Mal, und jedes Mal wenn du genügend Karten für einen deiner Yaku erwischt, zählst du den Zähler für diesen Yaku hoch. Am Ende teilst du alle Zähler durch 10000 und erhälst dadurch die empirischen Wahrscheinlichkeiten für das Eintreten der jeweiligen Yaku.

Damit hast du die gesuchten Wahrscheinlichkeiten auf schätzungsweise ~2 Stellen nach dem Komma angenähert.

 

[Kokujou]

na dann machen wir das doch~ mal gucken vielleicht fällt uns ja noch ne Formel dazu ein die die annäherung bringt und nicht 17 Minuten berechnung erfordert. Bis dahin: Thumbs up!

 

[0-8-15 User]

Also ein paar Würfel schmeißen geht auch auf einem Handy in Nullkommanix.