bitset performant?

Hm, wenn du es sooo portabel haben willst, dann musst du das schon kapseln, zB so:

const unsigned bits_per_uint = sizeof(unsigned)*CHAR_BIT;

template<unsigned N> //number of bits
class my_bitset
{
    unsigned arr[bits_per_uint%N==0 ? bits_per_uint/N : bits_per_uint/N+1] //oder sowas in der Richtung;
};

Dann kommt natürlich noch die Endianess ins Spiel.... Aber dafür gibts dann ja std::bitset<N> / std::vector<bool>...

Eisflamme

Also wenn ich << statt >> nutze, ist das nicht unbedingt portabel oder wie? Bzw. > oder < passt nicht? Also mir ist schon klar, dass little-endian vs. big-endian heißt, dass die Bits anders interpretiert werden, aber hm...

volkard

Eisflamme schrieb:

und irgendwelche maps gebaut

Damit ist hoffentlich nicht std::map gemeint. Das wäre Faktor 100 oder mehr. Falls Du so drauf bist, was ich echt nicht glaube, dann sollten wir uns mal treffen. Ich glaube es nicht; ich lese doch viel von Dir und Du bist nicht so.

Und bring unbedingt die Neunschwänzige mit. Ich werde sie brauchen. Und Du wirst sie auch benötigen.

Eisflamme schrieb:

unsigned long long ist also immer 64 Bit long? Auch auf x86-Systemen und unter verschiedenen Systemen?

Nö.
Mach erstmal static_assert.

Eisflamme

Ne, ich hab sogar ne boost-bimap gebaut. Aber die ist ja wie ne map, nur doppelt. Aber ich bin map-technisch auch nicht so der Experte, weil ich die immer benutze, wenn ich ein key-value-Paar habe und das dann für toll halte. Wenn ich was Hashiges haben will, nutze ich halt die boost::unordered_map, ist das geschickter?

Aua im Voraus.

unsigned long long ist ja schon nicht portabel, weil es nicht im aktuellen Standard drin steht. Die Frage ist, wo du die Grenze mit deiner Portabilität ziehen möchtest:
-Ist es realistisch, dass deine CPU oder wer auch immer mit Mixed-Endianess rechnet?
-Ist es realistisch, dass ein Byte bei dir 17 Bit hat

Also wenn ich << statt >> nutze, ist das nicht unbedingt portabel oder wie?

Wenn du damit bitwise shift meinst - nein, das ist portabel, da es sich um arithmetische shifts handelt. Wenn du das Ergebnis aber binär speicherst und auf einem anderen System mit anderer Endianess einliest, ist es natürlich nicht mehr Portabel. Wie gesagt, zieh die Grenze...

Eisflamme

Achso. Aber innerhalb eines Systems kriege ich keine Probleme? Obige Rechnungen sind zwar datenlastig, aber es zählt nur das Ergebnis. Ergo wird nichts gespeichert und übertragen.

Die zwei Punkte von Dir halte ich für vernachlässigbar. Brauche ich mir dann keine Sorgen machen? Wenn ich beispielsweise 1 << 5 sage, ist das dann immer der Zahl 2^5 entsprechend? Denn wenn die Endianness sich umdreht, laufe ich ja eigentlich in die falsche Richtung.

Hm irgendwie schlagen hier meine Troll Sensoren alarm. Aber trotzdem:
-Der Shift operator verhält sich arithmetisch. "<<" shiftet nicht nach links, sondern nach "höher wertig".
-Wie passt es zusammen, sich Gedanken über die Performance von den elementarsten Bit-Operationen zu machen und auf der anderen Seite etwas von std::maps und hashes zu schreiben? Oo

Eisflamme

Nene, bin kein Troll, das arithmethisch hat mir nur nix gesagt und ich frage immer sehr kleinschrittig.

Und die Performance-Gedanken hatte ich erst, nachdem ich merkte, dass ich ohne nicht klarkam. Ich dachte, ein paar Equity-Berechnungen können ja nicht so aufwendig und zahlreich werden, dass ich da performant rechnen muss. Dann stellte ich fest, dass ich um den Faktor 1000 langsamer war als das Vorlage-Programm... und wenn der Benutzer eine Minute auf ein Ergebnis warten muss, ist das unschön.

Okay, also dann klingt das für mich so, als wäre die Portabilität für meine Zwecke gegeben.

Beschreib doch nochmal genauer, was du da implementieren willst. Ich versteh immernoch nicht, wie die Bitoperationen und map-Implementierungen zusammen passen.

Eisflamme

Achso, der Zusammenhang besteht so gar nicht. Ich hatte vorher maps, um enum-Werte von Karten (ACE, KING) auf die entsprechenden chars 'A', 'K' abzubilden. Das war purer Luxus und erschien zweckdienlich. Aber jetzt habe ich gemerkt, dass ich auf jeden Fitzel Performance achten muss und daher hab ich das alles weggeschmissen und benutze einfach chars, die per se schon vergleichbar sind und so Zeug.

Bitoperationen nutze ich jetzt insofern, als dass ich nicht nur einzelne Karten nicht mehr als Objekte darstelle, sondern sogar ganze Boards bzw. Kombinationen aus Boards und Holecards (7 Karten) in einer einzigen Bitfolge darstelle. Also weg von Objekten für dies und jenes und hin zu super-kompakter Darstellung ohne jeglichen Overhead.

volkard

asdfasd schrieb:

Beschreib doch nochmal genauer, was du da implementieren willst.

Derzeit haut ihn die kombinatorische Explosion beim Poker-Spiel kaputt. Faktor 100 oder sowas wird er gewinnen durch supi native Datenstrukturen. Aber nur Faktor 100 oder sowas. Mathebuch macht kluch. Das wird er aber nicht anschauen, solange nicht der letzte Fitzel Bitgefummle ausgeschöpft ist. Also lasst uns doch noch ein wenig bitfummeln. Mit Mathe wird er Faktor 1e40 und mehr schaffen je nach Aufgabe. Aber das lernt man erst in der 13. oder 12. Klasse und auch da nur runimentär, nicht genug für sein Prog. Er wird trotz Abi-Kentnissen noch was lesen müssen oder saugeil selber überlegen.

Eisflamme

Ich habe ein Referenz-Programm in C# gesehen, das ganz gescheite Sachen macht. Es geht nicht nur darum, dass da Boards in Bits dargestellt werden, aber man kann für jede Farbe Masken drüberlegen und mit denen weiterrechnen. Und man kann dann wie gesagt Tabellen vorberechnen, die anhand der Bitsets dann auf ein paar Informationen (wie viele Karten doppelt etc.) abbilden, mit welchen man wiederum recht schnell zu weiteren Infos kommt.

Nur nutzen die in C# natürlich andere Typen, um 52 Bits abzubilden, daher wollte ich mich hier erkundigen, was in C++ angebracht ist.

Hast du noch ein Stichwort, wonach ich im Mathebuch suchen könnte?

volkard

Eisflamme schrieb:

Hast du noch ein Stichwort, wonach ich im Mathebuch suchen könnte?

Uih, sauviele Begriffe.
Du lernst sie als guter Informatiker auch so. Normalerweise schneller als in der Schule. Im konkreten Fall kauf Dir ein Buch, würde ich meinen. Abi-Wissen gibt es nicht im Netz. Nur das kleinere Wissen für Realschulabschluss, wofür es viel Nachhilfe gibt, und die Nachhilfegeber werben damit.
Und die Studies, die sich helfen.
Dazwischen ist ein Loch, fürchte ich. Miete Die einen MIND-Studenten für drei Stunden für den Einstieg. Das bläst. Das Loch ist echt doof. Was soll ich sagen? Google "Wahrscheinlichkeitsrechnung" und viel Geduld? Nee. Ausnahmsweise lernt man das in der Schule besser. Mach Dich gefaßt auf ein Thema, das auf Papier nicht gut zugänglich ist. Aber tu es.

Eisflamme

Ich bin ja lernbereit, aber ich weiß nicht genau, was mir so wirklich fehlt.

Bzgl. der Wahrscheinlichkeitsrechnung fehlt mir hier nämlich nichts, soweit ich das sehe. Man muss in meinem speziellen Fall alle Möglichkeiten durchgehen und sehen, welcher Spieler vorne liegt, das zählen und darüber auf die Equity kommen, da gibt es leider keine Abkürzungen. Die restliche Wahrscheinlichkeitsrechnung bzgl. Poker habe ich drauf, aber die hilft hier ja nicht.

volkard

Höhere Begriffe fehlen.

Eisflamme

Werd doch Mal konkret. Wenn ich nach "Wahrscheinlichkeitsrechnung höhere Begriffe" google, bringt mir das nichts. Mir fehlen sicherlich irgendwelche ausgefallenen Wahrscheinlichkeitsmatrizen oder komplexere Muster, mit denen man gescheite Dinge anstellt. Aber etwas zielgerichteter wüsste ich schon gern, was Du meinst.

volkard

Mir fehlt das Pokerwissen.
Equilator, Equity, Holecards, Community-Cards, Board?
Wenn Du nur pro Spieler herausfinden willst, welches das bestmögliche Blatt ist, das er noch kriegen kann, mußt Du gar keine Wahrscheinlichkeitsrechnung betreiben, sondern nur die paar möglichen Blattbewertungsregeln durchgehen und versuchen, das Ergebnis zu konstruieren. Mit Wahrscheinlichkeitsrechnung war ich auf der falschen Fährte. Ich dachte, Du wolltest berechnen, mit welcher Wahrscheinlichkeit welcher Spieler gewinnt. Das ist dann ein wenig schlimmer. Aber mir will scheinen, daß man das auch konstruieren sollte, statt alles duchzuprobieren.

Ich versuche mal:
Ausgespielt sind bei 5 Spielern bisher 5*3=15 Karten und 2 in der Mitte. Insgesamt gibt es 104 Karten, also 8 Asse, davon zwei von der selben Farbe.
Ich habe ein As und zwei Schrott.
In der Mitte liegt ein As.

Und dann rufe ich nacheinander auf:
Wie groß ist meine Wahrscheinlichkeit für 4 Asse?
Ich darf annehmen, daß ich jetzt dran bin und noch 2 Karten auf einmal ziehe und dann erst die anderen ihre. Würden die anderen erst ziehen, gäbe es weniger Asse, aber auch weniger Karten überhaupt und irgendwie würde sich der Effekt wieder wegrechnen.
Ich brauche noch 2 Asse.
Erste Ziehung: 6 Asse von 87 noch übrigen Katzen
Zweite Ziehung: 5 Asse von 86 noch übrigen Katzen
6/87*5/86=0.0040096231

Die Berechnung wird natürlich noch doofer, wenn man verschiedene Karten braucht, um sein Wunschblatt zu bekommen. Da braucht man viel Fleiß, um alle bewertungsrelevanten Kombinationen zu proggern.

Eisflamme

Okay, also Equity ist das, was in den Pokersendungen immer da steht. Z.B. hat ein Spieler 99 und der andere 76 in Kreuz oder so. Und dann geht es um die Gewinnchance, also die Wahrscheinlichkeit, dass die Hand, wenn die fünf Karten in die Mitte wandern, gewinnt. 99 hätte hier jetzt 80% oder so und 76 halt 20%. Natürlich verändert die sich mit jeder Karte, die noch in die Mitte kommt.

Wenn man nicht blöd durchprobiert, könnte man z.B. sagen: 99 liegen erstmal ggü. 76 vorne, haben ja ein Paar. Damit 76 gewinnt könnten drei Karten in der Farbe ankommen. Aber dann könnten die 99 wiederum ein Fullhouse treffen, aber dann könnte 76 wiederum einen Straightflush machen...

Also das wird ziemlich schnell recht kompliziert, wenn man für alle Hände alle Wahrscheinlichkeitsbäume aufbaut, wer wann gewinnen kann. Meine Google-Recherche kam auch immer nur zu Brute Force-Ansätzen oder eben dem kompletten Durchprobieren. Es gibt halt so viele Möglichkeiten, dass die schwächere Hand doch noch gewinnt. Und es kann auch sein, dass es nen Splitpot gibt, wenn auf dem Board ein Royal-Flush erscheint, sodass keiner von beiden besser ist.

volkard

Ach, 2 Asse mit König drunter, 2 Asse mit Dame drunter, ... sind ja alles verschiedene Gewinnklassen.
Es gibt doch ein wenig mehr Gewinnklassen, als ich angenommen hatte. Daher das Bruteforcen. Wieviele Gewinnklassen gibt es denn?

inter2k3

Eisflamme schrieb:

Okay, also Equity ist das, was in den Pokersendungen immer da steht. Z.B. hat ein Spieler 99 und der andere 76 in Kreuz oder so. Und dann geht es um die Gewinnchance, also die Wahrscheinlichkeit, dass die Hand, wenn die fünf Karten in die Mitte wandern, gewinnt.

Nö, das wäre einfach nur die Gewinnwahrscheinlichkeit.
Equity bezieht auch noch den zu erwartenden Gewinn und den ggf. dafür einzusetzenden Betrag ein.