Schnelles Iterieren über bestimmte Bitfolge?
-
Hi,
also ich habe ja wie bereits gesagt meinen Poker-Equity-Evaluator. Mittlerweile kann ich alles in Bitfolgen darstellen, aber die Performance ist noch nicht besonders gut.
Also erstmal die Voraussetzungen. Zu untersuchen ist ein so genanntes Board, bestehend aus 7 Karten. Dabei besteht das Board erstmal nur aus 5 Karten und jeder Spieler hat 2 Karten. Ich habe eine Funktion evaluateBoard, die für 7 Karten eine Wertigkeitszahl herausgibt, die für die 7 Karten also die beste Hand herausgibt. (natürlich werden nur 5 Karten genutzt und 2 vernachlässigt, weil das bei Poker eben so ist, aber das macht die Funktion alles)
Jetzt kombiniere ich einmal Hand1 mit den 5 Karten und erhalte ein Board1 und Hand2 mit den 5 Karten und erhalte Board2. Beide evaluiere ich und über den Vergleich der Werte kann ich den Gewinner ermitteln.
Ich muss für alle möglichen Boards diese Abfrage machen, da ich ja die Gewinnchance in % erhalten möchte.
Ach und jede Karte entspricht einem einzelnen Bit. Es gibt 52 Karten und das Board ist in einem uint64 angegeben, wobei jedes Bit einer Karte entspricht.
Was ich bisher gemacht hab
Bisher hatte ich 5 Schleifen. In jeder Schleife wurde ein entsprechendes Bit gesetzt und nach dem Schleifendurchlauf wieder gelöscht (mit |= 1 << schleifenZaehler bzw. ^= 1 << schleifenZaehler). Jetzt habe ich aber fest gestellt, dass | und ^ ziemlich langsam sind. Wenn ich die nämlich rauslasse, läuft es schneller, aber darauf kann ich ja nicht verzichten.
Ideen
Also eine Idee war, dass ich ja eine Tabelle mit dem Board vorberechnen kann. Ich würde dann einfach nur über alle Werte gehen. Da ist aber das Problem, dass es zu viele gibt. Wenn ich 5 Karte habe, gibt es 2.598.960 Kombinationen. Wenn ich jetzt Hand1 und Hand2 jeweils dazu nehme, sind es lediglich doppelt so viele. Das wirkliche Performanceproblem ergibt sich aber erst, wenn ich mehrere Hände1 und Hände2 angebe, wo jeder mit jedem rummacht. Das können aber durchaus 32 Kombinationen für Hand1 und 32 Kombinationen für Hand2 sein, also hätte ich 32 x 32 x 2.598.960 Boards, was deutlich zu viel ist. Also lässt sich nicht alles als Tabelle speichern.Eine weitere Idee wäre jetzt alle 5-Karten-Boards zwischenzuspeichern. Denn das Durchiterieren ist auch nicht so einfach und kostet Zeit, da ich bei 52 Karten jeweils 7 besetzt habe und somit auch mit Bits rumhantieren muss.
Das Hauptproblem besteht dann aber: Ich muss in jedem Schleifendurchlauf zu meinem 5-Kartenboard Hand1 (zwei Karten) hinzufügen, Auswertung machen und wieder abziehen und das gleiche dann für Hand2. Also habe ich pro Schleifendurchlauf allein dafür zwei Mal ein oder und zwei mal ein xor und das ist irgendwie zu langsam.
Irgendwelche Ideen? Rückfragen beantworte ich sehr gerne.
-
Verstehe ich das richtig, dass du über bestimmte Bitabschnitte in deinem uint_64 iterieren willst, aber xor ist tatsächlich die Performancebremse? Also wenn deine Zahl z.B. so ist:
1000111011100110011001100100000111100101 ^^^^^Dann möchtest du, dass der markierte Bereich systematisch durchgegangen wird?
Dann zähl doch einfach! In diesem Beispiel fängt der markierte Bereich 9 Stellen von rechts an und ist 5 Stellen breit. Du solltest alle Kombinationen erwischen, indem du 2^(5-1) mal 2^9 addierst.
-
Hi,
ne, ganz so einfach ist das leider nicht. Es geht mir darum, dass ich >alle< Zahlen "abarbeite", in denen genau 7 Bits gesetzt sind und die 52 Bits lang sind.
Und für alle diese Zahlen (was wie gesagt 52*50*49*48*47 / (5!) sind) möchte ich dann jeweils Hand1 hinzufügen (also zwei weitere Bits hinzufügen), eine Evaluation machen und diese Bits wieder löschen. Und das gleiche dann im innersten Schleifendurchlauf auch für die Hand2.
-
Frag doch mal im Matheforum, wie man sowas mit Wahrscheinlichkeitsberechnung hin bekommt und mach nicht immer wieder fast gleiche Threads auf. http://www.c-plusplus.net/forum/288954
-
Es geht nicht besser über Wahrscheinlichkeitsrechnung. Ich muss diesen konkreten Arbeitsschritt so schnell wie möglich hinkriegen. Die Anzahl der Operationen zu verringern oder stattdessen kostengünstigere Operationen zu nutzen ist für mich eher ein Informatik- als ein Matheproblem.
Und nur weil das zu Grunde liegende Programm immer dasselbe ist, heißt das nicht, dass die Fragen immer dieselben sind. Die unterscheiden sich nämlich maßgeblich.
Ach evtl. ist der Shift auch das größere Problem als das XOR. Kann das sein? Ahhhh, << scheint echt saulahm zu sein!
-
Also mir kommt das auch komisch vor diese Vorgehensweise. Wenn ich zwei Pokerhände sehe, kann ich recht flott abschätzen, wer mit welcher Wahrscheinlichkeit gewinnt (wenn ich nur auf Paare gucke auch genau ausrechnen). Und jedes Pokerprogramm kann dir das ohne große Prozessorlast ebenfalls schnell sagen (und zwar exakt). Ich glaube du machst da irgendwas ganz gewaltig falsch, wenn du alle Kombinationen durchprobieren musst.
Das Problem ist, ich kann nichts mit diesen Fernsehfachbegriffen wie Equity usw. anfangen mit denen du um dich wirfst, daher kann ich dir nicht konkret weiterhelfen.
-
Ich habe die entsprechenden Programme ja hier zur Hand. Die nutzen meine Methode, nur besser optimiert. Die Programme gehen definitiv alle Kombinationen durch. Z.B. sagt mir PokerStove, dass es 1 Mrd. "Games/second" berechnet, wobei mit Game halt ein Board (5 Karten) in Kombination mit Hand1 und einmal mit Hand2 gemeint ist.
Mein Procedere ist absolut Standard.
Und Begriffe einfach Fragen. Equity ist Gewinnwahrscheinlichkeit (genauer gesagt Gewinnwahrscheinlichkeit + Wahrscheinlichkeit, dass es einen Split Pot gibt, also die Spieler sich den Pott teilen). Das ist das, was im Fernsehen immer steht. Hand1 hat 78% und Hand2 hat 22%.
Hm, hat jemand denn eine Idee, wie ich über alle 52-Bit-Folgen mit exakt 7 Bits gesetzt laufen kann?
-
(was wie gesagt 52*50*49*48*47 / (5!) sind)
Warum sind es nicht 52 über 7 = 133784560?
-
Eisflamme schrieb:
Ich habe die entsprechenden Programme ja hier zur Hand. Die nutzen meine Methode, nur besser optimiert.
Wenn du den Code dieser Programme hast dann kannst du doch nachschaun wie die das genau machen!?
Eisflamme schrieb:
Hm, hat jemand denn eine Idee, wie ich über alle 52-Bit-Folgen mit exakt 7 Bits gesetzt laufen kann?
Dein Problem ist nicht die Geschwindigkeit der Bitoperationen. AND, OR, XOR, etc. sind so ziemlich die schnellsten Operationen die deine CPU überhaupt kennt. Dein Problem ist die Tatsache dass du über einzelne Bits iterieren willst.
-
So, ich hoffe ich hab Equity im Matheforum richtig erklärt.
http://www.c-plusplus.net/forum/289145
-
dot:
Ich habe den Code nicht, aber die Ausgabe, dass entsprechend viele Operationen gemacht worden sind...Bashar:
Das wäre für 7 Boards, aber zwei der Karten sind ja konstant.Mein Problem liegt jetzt aber wirklich in XOR und AND. Wenn ich die rauslösche, wird's dramatisch schneller.
Vermutlich muss ich wirklich irgendwie anders iterieren. Aber alle Boards zu betrachten ist durchaus ein üblicher Ansatz.
-
Eisflamme schrieb:
dot:
Ich habe den Code nicht, aber die Ausgabe, dass entsprechend viele Operationen gemacht worden sind...Und woher weißt du jetzt dass diese Software es genauso macht wie du? Ich kann auch "1 Million Spiele" mit wahrscheinlichkeitstheoretischen Methoden untersuchen, vermutlich um mehrere Größenordnungen schneller. So eine Zahl sagt absolut rein gar nichts darüber aus was die Software genau tut.
Eisflamme schrieb:
Mein Problem liegt jetzt aber wirklich in XOR und AND. Wenn ich die rauslösche, wird's dramatisch schneller.
Vermutlich muss ich wirklich irgendwie anders iterieren. Aber alle Boards zu betrachten ist durchaus ein üblicher Ansatz.Kanns nicht einfach nur sein dass, wenn du die Operationen rauslöschst, der Compiler den ganzen Code einfach wegoptimiert weil er nichts Sinnvolles mehr tut?
-
Die Bearbeitungszeit steigt linear zu der Anzahl der Spiele. Und wenn ich das, was mir jetzt einfällt, optimiere, ist mein Programm "nur" etwa 10 Mal schneller. Außerdem wird genau angezeigt, wie viele Spiele durchgeführt worden sind, nicht nur die Performance.
Für 16 x 16 Handkombinationen sind es z.B. genau 16*16*48*47*46*45*44 / (5!) Spiele, die durchgeführt worden sind. Und alle Beispielimplementierungen (die natürlich noch nicht soo optimiert worden sind) nutzen ebenfalls meine Binärversionen. Mit volkard hatte ich auch schon kurz diskutiert.
Ich würde mich jetzt wirklich über Anregungen freuen, wie ich hier in meinem System weiter optimieren kann, da ich ziemlich sicher bin, dass es besser nicht geht. Falls jemand konkrete Ideen hat, wie es besser gehen könnte, bin ich dafür natürlich offen, aber nicht nur Schlagworte wie "bedingte Wahrscheinlichkeiten" bitte, das führt uns nicht weiter.
Kanns nicht einfach nur sein dass, wenn du die Operationen rauslöschst, der Compiler den ganzen Code einfach wegoptimiert weil er nichts Sinnvolles mehr tut?
Ich lasse zumindest einen Counter mitzählen, das Ding tut schon was. Aber über den Punkt zu diskutieren hilft mir jetzt auch nicht weiter, also plz back to topic.
-
Eisflamme schrieb:
Aber alle Boards zu betrachten ist durchaus ein üblicher Ansatz.
Bei Schach vielleicht, aber ganz sicher nicht bei Poker.
EDIT: Na bitte
Wikipedia schrieb:
Poker is a game of imperfect information (because some cards in play are concealed) thus making it impossible for anyone (including a computer) to deduce the final outcome of the hand. Because of this lack of information, the computer's programmers have to implement systems based on the Bayes theorem, Nash equilibrium, Monte Carlo simulation or neural networks, all of which are imperfect techniques.
soviel zum Thema "üblicher Ansatz"...
Eisflamme schrieb:
Ich lasse zumindest einen Counter mitzählen, das Ding tut schon was. Aber über den Punkt zu diskutieren hilft mir jetzt auch nicht weiter, also plz back to topic.
lol. Dann wird der Compiler den Schleifenkörper wegoptimieren und deinen Counter auf 1.000.000 setzen. Schau doch mal an was da für Code generiert wird...
-
Im Programm heißt der Radiobutton "Enumerate All". Nach meiner Recherche gibt es keine bessere Methode (Brute Force ist ungenau, ginge aber auch) und die Bezeichnung des Buttons macht es sehr, sehr wahrscheinlich, dass tatsächlich alle Möglichkeiten durchgeprüft werden.
Aber wie gesagt: Die Diskussion führt zu nichts, können wir das jetzt bitte Mal lassen? Oder Du schlägst konkret einen besseren Algorithmus vor. Bis dahin gehe ich davon aus, dass meine Annahmen korrekt sind.
-
Eisflamme schrieb:
Ich habe die entsprechenden Programme ja hier zur Hand. Die nutzen meine Methode, nur besser optimiert. Die Programme gehen definitiv alle Kombinationen durch. Z.B. sagt mir PokerStove, dass es 1 Mrd. "Games/second" berechnet, wobei mit Game halt ein Board (5 Karten) in Kombination mit Hand1 und einmal mit Hand2 gemeint ist.
Das heißt noch nicht, dass das Programm wirklich alle Kombinationen durchprobiert. Wenn nur ein Kern für die Berechnungen zur Verfügung steht, müsste sonst alle zwei bis drei Takte eine Kombination probiert werden.
Edit: Na toll, man sollte Browserfenster nicht zehn Minuten lang offen lassen.
-
Michael E. schrieb:
Eisflamme schrieb:
Ich habe die entsprechenden Programme ja hier zur Hand. Die nutzen meine Methode, nur besser optimiert. Die Programme gehen definitiv alle Kombinationen durch. Z.B. sagt mir PokerStove, dass es 1 Mrd. "Games/second" berechnet, wobei mit Game halt ein Board (5 Karten) in Kombination mit Hand1 und einmal mit Hand2 gemeint ist.
Das heißt noch nicht, dass das Programm wirklich alle Kombinationen durchprobiert. Wenn nur ein Kern für die Berechnungen zur Verfügung steht, müsste sonst alle zwei bis drei Takte eine Kombination probiert werden.
Eben, und das unter der Annahme dass die CPU unter Vollast läuft und nichts andres tut als Pokerspiele zu berechnen, was wohl definitiv nicht der Fall ist. Selbst wenn es nur 1.000.000 Spiele/s wären wäre diese Zahl wohl noch unrealistisch.
-
Hmm... dann könnte es irgendwelche Hilfsstrukturen geben, die Teilergebnisse auswerten oder zusammenfassen oder so. Das ist schon kein schlechter Hinweis.
Aber fallen euch denn andere Möglichkeiten ein, wie ich mein Problem löse?
Ach und 1 Mio. Spiele pro Sekunde kann ich locker auswerten. Ich kann sogar bereits 60 Mio. Spiele pro Sekunde auswerten. Der Schritt zu dem Ziel (1 Mrd.) ist also echt nicht mehr groß.
-
Eisflamme schrieb:
Aber fallen euch denn andere Möglichkeiten ein, wie ich mein Problem löse?
Du könntest z.B. über OpenCL die Grafikkarte verwenden... :p
-
Eisflamme schrieb:
Bashar:
Das wäre für 7 Boards, aber zwei der Karten sind ja konstant.Sorry, ich bin kein Poker-Experte. Du hattest geschrieben:
Es geht mir darum, dass ich >alle< Zahlen "abarbeite", in denen genau 7 Bits gesetzt sind und die 52 Bits lang sind.
