3. Schnelles Iterieren über bestimmte Bitfolge?

Schnelles Iterieren über bestimmte Bitfolge?

  • M

    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.

    0

  • 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.

    0
  • E

    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ß.

    0

  • 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

    0
  • B

    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.

    0
  • E

    Ja, sorry, das war falsch. Ich meine die Boards mit 5 Bits, das reicht.

    0

  • dot schrieb:

    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

    ...oder dir einfach mal anschauen wie sowas wirklich gemacht wird. Es gibt doch sicherlich tausende Paper drüber und mindestens genausoviele Open Source Poker KIs!?

    0
  • E

    Paper habe ich keine gefunden und die Programme, die ich bisher gefunden habe, gingen in die Richtung von dem, was ich bereits tue. Ich habe mir das ja nicht selbst ausgedacht.

    Aber wie gesagt: Ich schaffe 60-100 Mio. Auswertungen pro Sekunde. Ich brauche 1 Mrd. Das ist nur 10-20 Mal schneller. 😞 Daher ja meine starke Vermutung, dass ich so weit vom Ziel nicht mehr entfernt sein kann.

    Ist XOR auf 64 Bit eigentlich langsamer als XOR auf 32 Bit? Also auf einem x64-System? Evtl. kann ich das noch verkürzen.

    0
  • Mod

    Ist es eigentlich nötig, alle Kombinationen durchzugehen? Viele Kombinationen sind doch äquivalent, weil die suit größtenteils egal ist. Da könnte man doch allgemein nur nach suited und unsuited unterscheiden.

    Was ich mich gerade auch frage ist, wie du auf 52*50*49*48*47 / (5!) = 2,3 Millionen kommst. Ich hatte naiv jetzt spontan gesagt, dass es nur 48 über 5 = 1,7 Millionen Möglichkeiten gibt. Was übersehe ich?

    Und bist du sicher, dass die Bitdarstellung das schnellste ist? Ich habe in der Vergangenheit oft die Erfahrung gemacht, dass einfache Ganzzahlen häufig schneller sind, als das ganze Verpacken und Entpacken von Bits durch die Programmlogik.

    Ich schaue mir das Problem heute Abend mal an, wenn ich mehr Zeit habe.

    0
  • E

    Hey,

    48 über 5 passt für alle Boards. Aber jetzt musst Du natürlich noch die Karten der Spieler mit einbeziehen. Du musst für alle (48 über 5) Boards ja die Hand von Spieler 1 hinzufügen, dann für diese resultierenden 7 Karten das Ergebnis berechnen und die Karten wieder abziehen, das gleiche für Spieler 2 und die Ergebnisse dann vergleichen.

    Dann hat man zwar nur (48 über 5) Iterationen, aber das pro Kombination von Hand1 zu Hand2.

    D.h. wenn ich jetzt Spieler 1 ein paar Hände gebe, z.B. AK, AQ, AJ und Spieler 2 auch ein paar kriege wie z.B. TT,99,88, dann muss das Programm alle möglichen Konfrontationen ausrechnen, also AK vs TT, AK vs 99, AK vs 88, AQ vs TT...

    Aaaber: AK entspricht 16 Kombinationen. AQ auch, jede beiden nicht-gepaarten Karten. Wenn ich also schon AK gegen QJ laufen lasse, habe ich 16*16 = 256 Konfrontationen.

    Und diese 256 muss man mit (48 über 5) multiplizieren, um auf die gesamte Durchlaufszahl zu kommen. Das sind 438.349.824 Schleifendurchläufe insgesamt. Pokerstove schafft das in 0,5 Sekunden. Mein Programm braucht dafür zur Zeit ungefähr 10 Sekunden. Das ist ja nicht so weit weg. 🙂

    Und über die Äquivalenz von Boards... das ist auch nicht so einfach. In meiner Evaluationsfunktion baller ich die Bits zusammen mit diamonds ^ hearts ^ clubs ^ spades und für Straßenprüfungen spare ich da natürlich einiges ein. Aber für die Iteration muss ich m.W. schon alles durchgehen. Es gibt ja auch den Str8flush, also kann es sein, dass wir Straße und Flush prüfen müssen.

    Die Bitdarstellung erscheint mir dann schon sehr schnell. Ich brauche ja trotz dessen 52 Bit. Die Vergleiche der Stärken erfolgen ja über ganz normalen Zahlenvergleich.

    0
  • P

    Also einige Argumente hab ich hier schon gelesen, die deinen Ansatz fragwürdig erscheinen lassen:

    1. Das binäre Packen ist sinnfrei, weil Platz nicht dein Problem ist. Performance schon, also lass das Packen weg, das kostet auch.
    2. Du lässt die Poker-Logik völlig außen vor, wie z.B. die Tatsache, dass die Farbe nicht immer eine Rolle spielt. Dein brute-force Algo ist also vermutlich zu grob angesetzt, lass noch ein wenig Pokerlogik mit einfließen. Z.B. kannst du, statt stumpf "karten zu sammeln" und zu schauen, wer gewinnt, umgekehrt relativ einfach bestimmte Kombinationen ausschließen oder ihre Wahrscheinlichkeit berechnen. Das wäre vermutlich mein Ansatz...
    0
  • ?

    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 0000

    So 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

    0
  • B

    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 ...

    0
  • E

    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.

    0
  • J
     

    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?
    0
  • E

    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.

    0
  • ?

    Jetzt habe ich voll daneben gelangt.

    Source Lesen ist einfacher als eine Testaufgabe zu Lösen. 🙂

    Lichtlein

    0
  • P

    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.

    0
  • ?

    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;
}
    0
  • M

    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.

    0
Anmelden zum Antworten