Schnelles Iterieren über bestimmte Bitfolge?

Eisflamme

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

dot

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!?

Eisflamme

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.

SeppJ

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.

Eisflamme

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.

pumuckl

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

Das binäre Packen ist sinnfrei, weil Platz nicht dein Problem ist. Performance schon, also lass das Packen weg, das kostet auch.
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...

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

Bashar

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

Eisflamme

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.

Jockelx

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?

Eisflamme

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

pumuckl

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;
}

Michael E.

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.

Eisflamme

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.

pumuckl

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.

Eisflamme

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.

pumuckl

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 flush

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

Eisflamme

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.