Ein kleines Matheproblem (Details unten)

[Kokujou]

Ja... es ist sehr empfehlenswert...
Koi Koi hat maximal 8 Spielzüge. Dazu kommen pro Spielzug maximal 2 weitere Entscheidungsmöglichkeiten. Wir reden hier also bei Spielbäumen über beide Spieler von 16!*4^16 Zuständen.
Da reicht ja nichtmal ein Quantencomputer um das in sinnvoller Laufzeit auszurechnen. Ich kriege maximal 7 Zustände hin, mehr ist nicht drin. Selbst wenn ich Alpha/Beta mäßig auf 99% aller zustände verzichte ist die Laufzeit so groß dass die Rechenzeit pro Spielzug mehrere Minuten bedarf.

Wenn das gesamte Spielfeld bekannt ist ist es aber, wie bei meiner früheren Schach Ki nicht nur möglich sondern auch effizient eine Bewertungsfunktion zu bauen, was ich ja gerade tue...

Aber was ich eigentlich sagen wollte: Ich konnte die Laufzeit erneut drastisch reduzieren indem ich die Eingabe also im code die cardProberties in ein double-Array konvertiert habe bevor die eigentlichen Berechnungen beginnen. Die Zugriffszeiten sind deutlich besser und ich bin jetzt pro Spielzug bei 200-300ms.

Und ja die KI bestimmt gute Züge. Sie hat eine statische Funktion die eigenschaften in einem Spielzug kombiniert und am ende einen Wert ausgibt.

Bei den Wahrscheinlichkeiten reden wir eindeutig aneinander vorbei aber wenn mir jemand bei der Performanceoptimierung der Mathematik meiner bisherigen Formel und der des Algorithmus helfen könnte wäre das wirklich riesig
solche Tipps wie "Verwende statt Listen Array" oder "double rechnet schneller als float" wären wirklich enorm hilfreich gewesen

 

[BeBur]

Es ist empfehlenswert, dass du dir einen Profiler besorgst der dir anzeigt, wo dein Programm am meisten Zeit aufwendet. Damit wirst du dir sehr häufig vermutlich selber helfen können.
double ist nicht schneller als float btw.

 

[Kokujou]

sag das meinen Ergebnissen XD double ist um 100ms schneller als float. was keinen Sinnmacht da double einen größeren Wertebereich hat. aber ich hab auch in google gefunden dass double bei simplen operationen wohl iwie schneller sein soll...

Aber egal. so ist es halt. Ich hab nochn bisl rumoptimiert und mit Multithreading komm ich jetzt pro ganzem Spielzug auf 2 Sekunden. Das ist vertretbar... bei Android wären es dann vermutlich 10 sekunden weil ich nen ziemlich leistungsstarken Prozessor habe also wenn noch jemand optimierungen an meinem algorithmus kennt dann immer her damit.

Ja ein profiler wäre super. Visual Studio hatte mal sowas wo ich sehen kann wo der code lange braucht aber das ist mit meiner Entwicklungsengine inkompatibel. Aktuell geht es aber auch um die Komprimierung mathematischer formeln...


Z.B. wo kann ich die terme zusammenfassen dass irgendwo halt z.B. nicht steht x*y*z sondern x^5+y^5 oder was weiß ich. Weniger Mathe = perfekt. Aber auch was meinen Code angeht. Vielleicht mache ich ja überflüssige schleifen, habe zu viele leere abfragen oder weiß der Geier, vielleicht ist mein Algorithmus zum Aufbau der Kombinationen total schwach und unperformant.

Oder gibts ne Datenstruktur die noch schneller ist als Arrays? Oder gibts möglichkeiten auf Bitebene bedeutende Zeitvorsprünge zu machen. Ich meine mathematische Operationen sind sicher viel schneller wenn du die größe der Zahlen auf 2 Stellen nach dem Komma beschränkst oder?

Gibts irgendne Bibliothek bestenfalls im System namespace die speziell für prozentuale Werte ist?

 

[0-8-15 User]

Ja... es ist sehr empfehlenswert...

Ist es: http://www.pokercruncher.com/monte_carlo_simulation.htm, aber querdenken ist ja scheinbar unerwünscht:

vielleicht ist mein Algorithmus zum Aufbau der Kombinationen total schwach und unperformant.

Vergleich ihn doch einfach mit dem, was eine Suche nach "C# Generate Subset of k elements" liefert.

Oder gibts ne Datenstruktur die noch schneller ist als Arrays?

Kurze Antwort: Nein

Ich meine mathematische Operationen sind sicher viel schneller wenn du die größe der Zahlen auf 2 Stellen nach dem Komma beschränkst oder?

Kurze Antwort: Nein

 

[BeBur]

Gibt evtl. mehr Rücklauf wenn du den Algo von der Implementierung trennst und es einmal in Pseudo-Code hinschreibst. Da ist dann schneller zu sehen was dein Algo macht.
Zusätzlich / Alternativ die Variablen ausdrucksstärker benennen.

 

[0-8-15 User]

Ein Link zum Projekt wäre vielleicht auch kein Schaden gewesen: https://github.com/Kokujou/Hanafuda

 

[Kokujou]

Naja ich dachte mir wenn ich euch mein ganzes Projekt um die Ohren haue steigt ihr komplett aus XD Die Funktion ist ja quasi losgelöst.
Gut an ausdrucksstarken Variablen arbeite ich schon aber mir fehlen sehr oft einfach die Worte...

Das Problem ist Hanafuda ist ein sehr einzigartiges Spiel. Es hat gemeinsamkeiten mit Poker, ja. Aber die Karten sind viel individueller, die Kombinationen genauso, die ganze Spielweise unterscheidet sich. Also im Prinzip ist es einfach kein Vergleich. Ich wüsste auch nicht wie ich es mit einem bekannteren Spiel vergleichen sollte. Vielleicht ne Mischung aus Poker und Memory aber das bringt den Kern glaube ich auch nicht gut rüber.

Was mein Algo macht ist eigentlich ganz einfach. Er zählt von rechts angefangen jede Zahl in nem Array der Größe k solange hoch bis das Maximum erreicht ist. Stellt es euch vor wie beim normalen Zählen, nur dass nicht auf 0 zurückgesetzt wird sondern immer auf den Vorgänger +1 also bei maximum = 4
0 1 2 -> 0 1 3 -> 0 1 4 -> 0 2 3 -> 0 2 4 -> 0 3 4 -> 1 2 3 -> 1 2 4 -> 1 3 4 -> 2 3 4

Und immer wenn so ein Array fertig erstellt ist mappe ich die Zahlen darin als Indizes auf die Wahrscheinlichkeiten. Also eigentlich ganz einfach. Ich glaub auch nicht dass man am Algo noch viel optimieren kann aber vielleicht ja doch. oder vielleicht kann man in C# optimierungen ausführen...

 

[simpsonsfan]

Laufzeitoptimierung ohne Laufzeitanalye/Profiling ist in meinen Augen nichts als Stochern im Nebel. Such dir einen Profiler und guck, wo die Zeit draufgeht, dann kann man da gezielt was machen.
Solltest du bspw. feststellen, dass die Zeit beim Generieren deiner Kombinationsmöglichkeiten (0 1 2 -> 0 1 3 -> 0 1 4 etc.) draufgeht, könntest du diese auch schlicht abspeichern. Bei maximal einigen zig-Millionen Kombinationen und dem Abspeichern jeder Kombination in 48 bit beschränkt sich das auch auf einige zig-Megabyte. Bzw. kannst du es einmal zum Start des Spiels aufstellen und im RAM behalten. Bringt aber gar nichts, wenn die Zeit nicht dafür draufgeht.

Die Formel muss schon P(Yaku) = P(1) * P(2) + P(2) * P(3) + P(1) * P(3) lauten, sonst ist sie falsch.

Jetzt habt ihr mich soweit getrieben, eine wunderbar ästhetische Paint-Zeichnung anzufertigen.

Unter der gegebenen Voraussetzung ("Die Wahrscheinlichkeit für das Eintreten des Ereignisses "Karte 1 wird gezogen" ist P(1) etc. und P(i) und P(j) sind stochastisch unabhängig) ergibt sich die Wahrscheinlichkeit für das Eintreten von mindestens einer gesuchten Kombination aus der Vereinigung all dieser Kombinationen.

Bei 2 von 3 möglichen Karten haben wir entsprechend (3 über 2)=3 mögliche Kombinationen und wie man oben sieht, wird bei einer simplen Addition der Wahrscheinlichkeiten der drei Kombinationen die Mitte dreimal gezählt. Sie ist aber nur einmal zu zählen. Die Formel sagt hierzu konkret:
P(A ∪ B ∪ C)=P(A) + P(B) + P(C) − P(A∩B) − P(A∩C) − P(B∩C) + P(A∩B∩C)
=P(1∩2) + P(1∩3) + P(2∩3) - P(1∩2∩1∩3) - P(1∩2∩2∩3) - P(1∩3∩2∩3) + P(1∩2∩1∩3∩2∩3)
=P(1∩2) + P(1∩3) + P(2∩3) - P(1∩2∩3) - P(1∩2∩3) - P(1∩2∩3) + P(1∩2∩3)
= P(1)*P(2) + P(1)*P(3) + P(2)*P(3) - 2*P(1)*P(2)*P(3)

Das wird aber bei mehr Kombinationsmöglichkeiten schnell unübersichtlich und rettet bei der Unsicherheit in der Grundlage sowieso nichts mehr.

Grundsätzlich ist die Wahrscheinlichkeit für die Vereinigung von beliebigen Ereignismengen immer kleiner gleich der Summer deren Einzelwahrscheinlichkeiten. Es kann also nichts dazukommen, sondern unterm Strich nur weg.

 

[Kokujou]

Ein Profiler ist in dem Fall nicht hilfreich, ich könnte jetzt lange ausführen warum, aber ich belasse es bei der kurzen Antwort: Würde ich externe Funktionen benutzen, aufwändige Datenstrukturen oder dergleichen wäre das eine gute und sinnvolle Lösung. Mein Algorithmus benutzt aber C# Basiskram. Dass der dauert wie lange er halt dauert ist nunmal so^^

Es gibt also bei mir 3 Optimierungsmöglichkeiten:
1. die Formel, die durch Klammern, komplexere aber vielleicht weniger rechenintensive Funktionen wie Potenzen oder weiß der Geier optimiert werden kann. Vielleicht auch iwas mit Matrizen oder ... ach was weiß ich XD

2. Der Algorithmus der vielleicht irgendwelche Leerläufe zu viel drin hat wo nichts produktives passiert. Das Vorberechnen der Kombinationen wäre ein Beispiel ist aber hier nicht zielführend. Denn ein paar Megabyte würde die größe der APK schon beträchtlich erhöhen ohne dabei einen sinnvollen mehrwert zu bringen. Ihr sagt ja selbst das Modell ist bestenfalls annehmbar. Das lohnt dann einfach nicht

3. Mikrooptimierung der Operationen. Wenn ihr z.B. sagt wir komprimieren die Wahrscheinlichkeiten runter auf einen Byte, und rechnen damit. Oder wenn ich den Multiplikationsoperator neudefiniere oder weiß der Geier. Irgendwas dass im EInzelfall ein paar nanosekunden spaart aber bei 100Mio Iterationen halt den Kohl fett macht.

 

[new Account()]

4. Code zu C++ auslagern.

 

[Kokujou]

Warum eigentlich nicht überlege ich gerade... Ich könnte ne simple Konsolenanwendung mit Rückgabewert programmieren und sie in meiner Unity-Anwendung ansprechen...

Zu dem Thema eine Frage: was wäre der leichteste weg? Mein Unity3D unterstützt nur C# Skripte soweit ich weiß, wie baut man am einfachsten und vor allem am schnellsten eine Schnittstelle zu einer C#-Anwendung?

Und vor allem: Ist P(A&B&C) = P(A&B) * P(A&C) * P(B&C) zumindest eine gute Näherungslösung? Denn wenn ich jetzt noch die Subtraktion reinpacke kannich alles direkt wegschmeißen. Dann nimmt die Laufzeit wieder auf das 5fache zu.

 

[kuddlmuddl]

wie baut man am einfachsten und vor allem am schnellsten eine Schnittstelle zu einer C#-Anwendung?

Habe ich neulich gerade gemacht - hiermit war ich sehr schnell am Ziel
https://ericeastwood.com/blog/17/unity-and-dlls-c-managed-and-c-unmanaged
Das Tutorial verät nicht nur, wie du eine C++ Funktion aufrufst und ihr Parameter gibst sondern auch schon, wie man das Ergebnis wieder zurückkopiert.

Ich garantiere dir jetzt schon, dass du keinen Spaß haben wirst, weil printf und debuggen beides nicht geht.
Ich hab mir dafür printf-to-file gebaut und zusätzlich im C++-Teil nen state (int) den C++-Modulen hinzugefügt, den ich jederzeit von C# heraus auslesen konnte.
Sobald du parallelisierst müssen diese states threadsicher sein.
Da du wahrscheinlich keine Lust auf komplizierte Callbacks hast, die dir mitteilen, wann C++ fertig gerechnet hat (timeouthandling...) wirst du wahrscheinlich am einfachsten im Unity-Teil innerhalb der Update() Funktion die C++DLL pollen wollen, ob sie fertig mit der Berechnung ist.

Bevor du diesen Weg gehst denk auch dran: Um C++ zu optimieren muss man natürlich auch profilen. Dh du brauchst einen C++ Wrapper um deine C# Anwendung herum, welche die DLL benutzt um mit C++-Profilern arbeiten zu können. Außerdem solltest du vorher klären, ob C++ Libs auf deinen Zielgeräten überhaupt funktionieren und du Compiler hast.

Dann immer schön -O3 und -march native und vektorisierten Code. Dann mit Cachegrind ne hohe L1/L2 Ausnutzung anstreben. Stichwort 'dataoriented design' statt oop.
Das sind dann aber fast schon mikro-optimierungen.. meist erreicht man in kurzer Zeit viel mehr, wenn man unnötige und doppelte Arbeit vermeidet dh 'den Algo' optimiert und nicht lowlevel 'den code'.

Performance auf embedded Zielhardware (Tablet/Smartphone stand irgendwo?) kann auch ganz anders ausfallen als auf nem Intel/AMD wgn hardfloat/softfloat support - also früh Testen, ob überhaupt Hoffnung besteht

 

[Kokujou]

tja wie gesagt bei diesem code muss ich nicht profilen den kann ich größtenteils... eigentlich sogar alles würde ich behaupten 1:1 kopieren. Denn es sind ja nur Basistypen. Da ist nichtmal mehr ne generische Liste drinne.

Was die Ausgabe angeht ich lasse sie mir einfach in ne Datei umleiten. Bei C# zumindest konnte ich ganz einfach nen prozess starten und dessen inputbuffer beschreiben das ist super wenn man Multithreading debuggen will und ne ausgabe braucht. Denn Unity friert ja immer ein wenn was aufm mainthread wartet. Also nix Debug.Log.

Mal gucken wie ich das mit C++ mache. Notfalls schreib ich ne Exe... ach ne... geht ja auch nicht...

ach du scheiße ist das überhaupt cross-plattform-kompatibel?! ich mach mir sorgen über den build auf android systemen.

Außerdem immer schön -O3 und march native und vektorisierten Code. Dann mit Cachegrind ne hohe L1/L2 Ausnutzung anstreben.

Gesundheit.

 

[BeBur]

Ich bin ja fast versucht nicht zu versuchen, dich davon abzuhalten.

 

[Kokujou]

Na mal gucken wies wird aber aus den fehlenden Reaktionen darauf nehme ich an dass man da nicht einfach mit klammern die Faktorenanzahl halbieren kann hm? ^^
ich meine aus P(A) * P(B) + P(B) * P(C) + P(A) * P(C) könnte man auch (P(A) + P(B) * P(C) machen und das hab ich ja auch schon drinne aber man bräuchte halt einen Tick mehr

Ergänzung (10. April 2019)

Ich glaube ich werd den Algorithmus so erstmal fertig konstruieren, die Wahrscheinlichkeiten der Karten berechnen, die Gewichte schön ausbalancieren und dann gucken obs nen großatigen Unterschied bei der Zugqualität gibt wenn ich die korrekte Formel mit krankhafter Laufzeit verwende und wenn ich einfach nur summiere und n dynamisches Gewicht anhänge oder so.

Vielleicht kann man das alles auch noch viel einfacher regeln.

 

[0-8-15 User]

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

Und wo ist dann bitte P(A) * P(B) abgeblieben?

Ich glaube ich werd den Algorithmus so erstmal fertig konstruieren ... und dann gucken obs nen großatigen Unterschied bei der Zugqualität gibt

Das wäre auch mein Vorschlag gewesen. Sonst verschwendest du nur unnötig Zeit für etwas, das eh nichts bringt.

 

[NightSun]

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

 

[0-8-15 User]

Ist P(A&B&C) = P(A&B) * P(A&C) * P(B&C) zumindest eine gute Näherungslösung?

Ich glaube nicht, dass du das Richtige meinst, wenn du die Formel so aufschreibst. Ich kann die richtige Formel ehrlich gesagt in dem Codebeispiel von oben auch nicht wiederfinden.

P(1) * P(2) + P(1) * P(3) + P(2) * P(3) ist jedenfalls eine sehr gute Näherungslösung, denn die Terme P(1) * P(2) * P(3) werden in der Praxis sehr kleine Werte annehmen. Weshalb das Weglassen dieser das Ergebnis nur geringfügig verfälscht.

 

[Kokujou]

Ja aber das ist das Minimalbeispiel normalerweise nähert man sich mit allen Kombinationen an die man erst abzieht dann dazuaddiert dass ist ein klopper von Formel ich hab sie mal unter dem Stichwort "Additionssatz" in dynamischer ausführung in google gesehen.

Tut mir leid ich muss die Klammern irgendwie versaubeutelt haben was ich meinte ist:
aus P(A) * P(B) + P(B) * P(C) + P(A) * P(C) könnte man auch (P(A) + P(B)) * P(C) machen

Die Reihenfolge ist bei Multiplikation egal. Also hast du wenn du die Klammern durch Multiplikation auflöst dasselbe Ergebnis.

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

Wobei ich die P(1) bis P(k) aus dem Maximum auslösen würde. wie ihr ja gesagt habt sind alles weitere vernachlässigbar kleine Werte. Der Hintergedanke ist, dass es so quasi ne Art durchschnittsbildung ist. Indem man die nte Wurzel aus k Termen zieht berücksichtigt man gleichzeitig dass es noch mehr Zahlen in der Reihe sind. Und vor allem hat man nicht die Gefahr über 1 zu kommen.

Stellt euch mal vor dass 8/10 meiner Karten ne Zugwahrscheinlichkeit von 1 haben. und das ist tatsächlich möglich und sinnvoll. Würde man die einzelterme aufaddieren käme man schnell auf nen Wert weit über 1. das wäre etwas unsinnig. Da ich dort nur multipliziere besteht diese Gefahr nicht.

Gibt es ein statistisches Modell in dem Wurzelziehen irgendeine bedeutung hat?

 

[new Account()]

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

(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)