Schnelles Iterieren über bestimmte Bitfolge?
-
Ich werde das mal in einen kleinen Rahmen umsetzen, dann lässt sich das besser denken.
Ich nehme nicht 52 sonder 8 Karten.
Als Board nehme ich 2 Karten.Das ganze in einen Bit abspeichern.
0000 0000
Wenn ich das richtig verstanden habe wanderst Du über jedes Bit mit Set/Unset.
Das ergibt eine Testreihenfolge von.
Step 0: 0000 0011 Step 1: 0000 0101 Step 2: 0000 0110 Step 3: 0000 1001 usw. Step n: 1100 0000So nun hoffe ich das Du das siehst was Du siehst.
Es ist einfach eine Zahl mit Startwert 3 und den Ende 192.Also nur eine Schleife und einen Increment
for(int c = 3; c < 192; ++c) { testWertigkeit(c) }Das dürfte Schneller gehen.
Lichtlein
-
Lichtlein schrieb:
Es ist einfach eine Zahl mit Startwert 3 und den Ende 192.
Also nur eine Schleife und einen Increment
for(int c = 3; c < 192; ++c) { testWertigkeit(c) }Das dürfte Schneller gehen.
Also 190 Kombinationen? Aber nur 8 über 2 = 28 davon haben genau 2 Bits. Bei größeren Zahlen ist die Diskrepanz noch größer. Ne lass das mal lieber ...
-
Ich poste Mal ein wenig Code, vielleicht fällt euch dann ja schon was ein.
Also mein Hauptprogramm hat jetzt etwa so was:
std::vector<BoardType> boards; boards.reserve(2598960); for(unsigned long long c = 0; c < 52; ++c) { board |= unsigned long long(1) << c; for(unsigned long long d = c + unsigned long long(1); d < 52; ++d) { board |= unsigned long long(1) << d; for(unsigned long long e = d + unsigned long long(1); e < 52; ++e) { board |= unsigned long long(1) << e; for(unsigned long long f = e + unsigned long long(1); f < 52; ++f) { board |= unsigned long long(1) << f; for(unsigned long long g = f + unsigned long long(1); g < 52; ++g) { board |= unsigned long long(1) << g; boards.push_back(board); board ^= unsigned long long(1) << g; } board ^= unsigned long long(1) << f; } board ^= unsigned long long(1) << e; } board ^= unsigned long long(1) << d; } board ^= unsigned long long(1) << c; }Damit erstellte ich erstmal alle möglichen Boards und speichere diese in einem vector ab. Das alleine dauert schon 1000ms-1500ms, aber gut, das ließe sich ja am Anfang des Programms einmal machen.
Danach erstelle ich die Karten:
unsigned long long hand1s = unsigned long long(1) << card1 | unsigned long long(1) << card2; unsigned long long hand2s = unsigned long long(1) << card3 | unsigned long long(1) << card4; unsigned long long fourCards = hand1s | hand2s;card1, card2, card3, card4 sind einfach random gesetzt, das sind Werte zwischen 0 und 51, da so entsprechend die Shifts aussehen.
Nun gehe ich eben alle diese Boards durch:
for(std::size_t pos = 0; pos < 2598960; ++pos) { if(containsNoCard(boards[pos], fourCards)) { boards[pos] |= hand1s; t1 = evaluateBoard(boards[pos]); boards[pos] ^= hand1s; boards[pos] ^= fourHands; t2 = evaluateBoard(boards[pos]); boards[pos] ^= hand2s; if(t1 > t2) ++win1; else if(t2 > t1) ++win2; else ++split; } }Es ist übrigens auch zu langsam, wenn ich evaluateBoard komplett auskommentiere.
pumuckl:
Also wenn ich das nichtmal binär mache, dann habe ich ja pro Board 512 oder mehr Bits? Ich weiß nicht, wie mir das weiterhilft, zumal Vergleiche damit ja noch langsamer werden.Ausschlussverfahren bestimmter Boards, hm... Aber von der Wahrscheinlichkeit könnte ich ja noch nicht direkt auf Boards schließen, d.h. ich müsste anhand von bestimmten Bitmustern schon Ausschlüsse machen. Das klingt intelligent, ich überlege Mal ein bisschen.
Das Problem ist aber auch: wenn es nicht Mal ein Paar gibt, zählen alle 5 Highcards dafür, wer gewinnt. Also einfach zu sagen "kein Paar -> Split" ist zu einfach. Jede Karte kann etwas ändern. Und falls man nach der W.keit für einen Flush o.ä. schaut, kann der auch kaputt gehen, wenn jemand einen Str8flush hat.
-
boards[pos] |= hand1s; t1 = evaluateBoard(boards[pos]); boards[pos] ^= hand1s; // Soll das den Wert zurück setzen? // Wenn ja, dann vielleicht besser so t1 = evaluateBoard(boards[pos] | hand1s); ... boards[pos] ^= hand2s; // Hier auch? Passt doch nicht mit boards[pos] ^= fourHands zusammen, oder?
-
Nicht zurücksetzen, sondern die Hand von Spieler 1 dem Board hinzufügen, damit es ein 7-Karteboard ist. Und: boards[pos] ^= fourCards; switcht dann die Hände, d.h. Hand 1 wird abgezogen, Hand 2 hinzugefügt und wieder die Auswertung gemacht.
Sind zwei Kopien (am Anfang und am Ende) schneller als das über ^ umzusetzen? Aber das hilft glaube ich alles nichts, ich muss irgendwie weniger Schleifendurchläufe hinbekommen.
-
Jetzt habe ich voll daneben gelangt.
Source Lesen ist einfacher als eine Testaufgabe zu Lösen.
Lichtlein
-
Eisflamme schrieb:
pumuckl:
Also wenn ich das nichtmal binär mache, dann habe ich ja pro Board 512 oder mehr Bits? Ich weiß nicht, wie mir das weiterhilft, zumal Vergleiche damit ja noch langsamer werden.Die Vergleiche sind nicht der Performanceschlucker. Das bitshiften schon eher. Und wenn du dir garnicht erst alle boards anschauen musst, dann brauchst du sie auch nicht alle zu generieren.
Ich würd vermutlich als ersten Ansatz 5 geschachtelte Schleifen nehmen, quasi in jeder Schleife eine Communitycard "aufdecken" und dann vor der nächsten Karte (Schleife) checken, ob ich bestimmte Abbruchbedingungen erfülle. Damit kann man ne Menge Kombinationen entweder ausschließen bzw. gesammelt abarbeiten.
Zusätzlich zu den Kartenhänden und dem aktuellen Board würde ich noch eine Struktur anlegen, in der steht, welche Gewinnhände mit dem aktuell aufgebauten Board überhaupt noch möglich sind.
Vielleicht find ich am WE mal die Zeit mir da was aus den Fingern zu saugen.
-
Keine Ahnung obs was bringt, aber erstze doch mal
if(t1 > t2) ++win1; else if(t2 > t1) ++win2; else ++split;mit
win1 += t1 > t2; win2 += t2 > t1; split += t1==t2;Oder vielleicht mit einem if
if(t1==t2) ++split; else { win1 += t1 > t2; win2 += t1 < t2; }
-
Erstens verschlechterst du dadurch die Performance, wenn der Compiler nicht sehr schlau ist, denn bei dir werden drei Vergleiche statt vorher zwei gemacht. Zweitens bringen solche Mikroänderungen nichts, wenn man um mindestens eine Größenordnung schneller werden will.
-
pumuckl:
Das klingt nicht so schlecht. Aber das Problem ist, dass ich nicht weiß, was ein Abschlusskriterium ist. Es geht ja immer darum bei bestimmten, bisher bekannten Boardkarten schon sagen zu können, ob Hand1 oder Hand2 gewinnt oder bereits ein sicheres Unentschieden auszusagen ist.Das trifft aber für so gut wie keine Boardkonstellation zu. Selbst wenn ein Spieler bereits einen Flush hat, kann es gut sein, dass er noch den Gegner besiegt.
Oder anders gesagt: Wenn nur der Flop gegeben ist, ist es so gut wie nie der Fall, dass bereits vorhergesagt werden kann, dass jemand mit 100% Wahrscheinlichkeit gewinnt.
-
Eisflamme schrieb:
Oder anders gesagt: Wenn nur der Flop gegeben ist, ist es so gut wie nie der Fall, dass bereits vorhergesagt werden kann, dass jemand mit 100% Wahrscheinlichkeit gewinnt.
Wenn nur der Flop gegeben ist, und einer schon einen flush hat, kannst du mit den Karten des anderen (oder der anderen, wenn du das mal erweitern solltest) direkt berechnen wie viele Kombinationen zu seinem Sieg, seiner Niederlage oder einem Unentschieden führen. Die Berechnung ist deutlich billiger, als die 45*44 restlichen Möglichkeiten durchzunudeln und jedesmal zu sagen "nö, gewinnt auch nicht" oder "okay, ich hab die eine ausnahme gefunden"...
Viele hohe Gewinnhände können bereits nach der zweiten Karte ausgeschlossen bzw. erkannt werden, das reicht, um ziemlich häufig (nicht immer) dort schon die inneren schleifen wegzulassen.
-
Das mit dem Flush könnte gehen...
aber wie willst Du durch das Ausschließen bestimmter Kartenkombinationen die inneren Schleifen rauskicken? Wenn klar ist, dass ein Str8flush nicht möglich ist, ist doch noch lange nicht gesagt, wer gewinnt. Im Gegenteil: umso schwächer die Hände, umso mehr Karten zählen. Wenn du nach der zweiten Karte alles bis auf Highcards ausschließen kannst, kann die letzte Karte noch entscheidend dafür sein ob AK753 oder AK752 gewinnt oder es gar einen Split gibt.
-
Nehmen wir an, Player1 hat nach der zweiten Community-card einen Drilling.
Die noch höheren Gewinnhände sind dann:
- vierling
- full house
- straight
- flush
- straight/royal flushDie Wahrscheinlichkeiten, dass die zustandekommen, sind relativ performant auszurechnen (evtl sogar über LUTs) bzw. oft sogar null. Die Wahrscheinlichkeiten, dass nur der Gegner eine davon hat, auch. Wenn das schnell/einfach zu rechnen ist, brauchst du die immerhin 46*45*44 Kombinationen der inneren drei Schleifen nicht mehr zu rechnen. Du könntest im Gegenteil sogar für die anderen Möglichkeiten, genau diesen Drilling nach der zweiten Karte zu haben, die Wahrscheinlichkeiten mitberechnen und die damit schon vorab berechneten Kombinationen in eine Sperrtabelle eintragen, so dass du auch in einer oder mehreren späteren Iterationen schon früh abbrechen kannst.
-
Das reicht aber doch nicht. Drilling != Drilling.
Wenn ich 333 habe und du 333, dann zählen auch noch die 4. und 5. Karte. 333AK schlägt 333AQ usw. Und in deiner Liste ist natürlich auch noch nicht drin, dass Villain auch einen Drilling trifft.
Aber ich werde mir da Mal ein paar Gedanken machen, die Idee ist auf alle Fälle gut und erscheint mir gerade auch als einzige Lösung.
-
Eisflamme schrieb:
Das reicht aber doch nicht. Drilling != Drilling.
Wenn ich 333 habe und du 333, dann zählen auch noch die 4. und 5. Karte. 333AK schlägt 333AQ usw. Und in deiner Liste ist natürlich auch noch nicht drin, dass Villain auch einen Drilling trifft.
Richtig. Ich kann mit einem Drilling nicht immer sicher sagen, wie es ausgehen kann/wird. Aber ich kann es manchmal sagen und in diesen Fällen kann ich die Abkürzung nehmen.
Zusammengefasst ist es doch so:
Ich kann theoretisch für jede Kombination von Handkarten die Wahrscheinlichkeiten an Hand der Wahrscheinlichkeitstheorie berechnen, ohne die brute-force Methode zu benutzen. Theoretisch kann ich sogar für all diese Kombinationen eine Lookup-Table aufstellen, die mir sagt, wie die chancen stehen. Das Programm ist dann irre schnell, braucht nur ne große Tabelle (auch nur einige MB) und alle sind glücklich. Ist aber irre kompliziert/aufwändig, das ins Programm bzw. in die Tabelle zu hacken.
Das ist das eine Ende.
Das andere Ende ist der absolute brute-force-Ansatz: Ich mach einen auf völlig dumm, hab garkeine Lust auch nur eine Hirnzelle auf Wahrscheinlichkeiten etc. zu verschwenden und teile jedesmal bis zur letzten Karte aus. Ist einfach zu coden, braucht aber viel Laufzeit und rechnet xmal das selbe.Mein Ansatz ist jetzt, irgendwo auf dem Weg zum ganz dummen brute-Force-Ende den Grips einzusetzen, und zwar da, wo es einfach genug ist, den Rest des (langsamen,einfachen) brute-force Ansatzes durch (schnelle, nicht so einfache) Wahrscheinlichkeiten zu ersetzen.
-
Der folgende Abschnitt kann beschleunigt werden, indem der Array nicht verändert wird
stattfor(std::size_t pos = 0; pos < 2598960; ++pos) { if(containsNoCard(boards[pos], fourCards)) { boards[pos] |= hand1s; t1 = evaluateBoard(boards[pos]); boards[pos] ^= hand1s; boards[pos] ^= fourHands; t2 = evaluateBoard(boards[pos]); boards[pos] ^= hand2s;kann es so gemacht werden
for(std::size_t pos = 0; pos < 2598960; ++pos) { unsigned long long board = boards[pos]; if(containsNoCard(board, fourCards)) { t1 = evaluateBoard(board | hand1s); t2 = evaluateBoard(board | hand2s);Es entfällt dadurch das Löschen der Bits, sowie das zurückschreiben des geänderten Array in den Speicher.
Gruss Chris
-
Um mal zu fragen, was das Ziel ist: Ich habe gerade mal ganz naiv einen Brute-Forcer implementiert. Sicherlich noch sehr verbesserungsfähig bei der Handevaluierung und ganz ohne irgendwelche Tricks. Gegeben 4 Karten rechnet dieser die Präflopgewinnwahrscheinlichkeit für beide Spieler in rund 0.5 CPU-Sekunden auf einem i7 exakt aus. Wie viel schneller soll es noch sein und warum sind 0,5 Sekunden zu langsam?
edit: Ach, du willst 32x32 Kombinationen testen. Das wäre wirklich ein bisschen langsam, sofern die Berechnung "live" erfolgen soll. (Was wird das denn dann? Alle möglichen Kombinationen von Starthänden sind doch sicherlich lange schon durchgerechnet tabelliert. Und ich verstehe nicht, wofür man das Ergebnis von 32x32 Händen sofort braucht)
-
Na ja, 32x32 wäre nicht Mal unbedingt nötig. Aber definitiv 16x16. Und 16 ist ja nur eine Hand, nämlich jede nicht-gepaarte wie AK, denn hierfür gibt es 16 Kombinationen.
Das Programm soll Live-Berechnungen machen wie die herkömmlichen Programme. Ich will aber darauf aufbauend noch grafische Geschichten machen und einen Excel-Befehl einbinden usw. usf.
-
Okay, ich habe mir Mal ein paar Tabellen gemacht, welche Hand gg welche andere Hand welche Redraw-Chancen etc. hat.
Fest steht leider so gut wie gar nichts. Str8flush gewinnt immer gegen Quads, das steht fest. Aber Str8flush gewinnt nicht Mal zwangsläufig gegen ein einzelnes Paar, da dieses Redrawchancen auf einen höheren Str8flush haben könnte... mit vielen Bedingungen lassen sich dann ein paar Fälle finden, die man mit einer Vorabfrage ausschließen könnte.
Aber: diese Vorabfragen kosten Zeit und man spart zu selten etwas ein, als dass die gut wären.
Mir ist jetzt aber eine andere Optimierung eingefallen: Wenn ich Spieler1 und 2 jeweils nur eine Kombination gebe, ist mein Programm ja schnell genug (wenn auch bei Weitem nicht so schnell wie Pokerstove oder Konsorten -.-). Mein Problem war ja, dass ich bei AK gegen QJ z.B. 16x16 Kombinationen habe. Aber da gibt es dann tatsächlich viele Äquivalente, also kann ich da schon Mal sehr viel einfach rauskicken.
Ich schaue Mal, wie viel ich damit einsparen kann...
-
Ich hab zwar überhaupt keine Ahnung von Poker aber wenn die Spiele die du durchprobieren willst unabhängig voneinander sind kannst du parallelisieren. Mein Tip mit OpenCL war nicht wirklich als Scherz gemeint. Selbst mit einfachem Multithreading kannst du auf nem Dual Core dann wohl schon annähernd 100% rausholen...
