Karten-Verteil-Algorithmus

[yss14]

Guten Mittag
Ich bin gerade dabei, ein kleines Kartenspiel zu programmieren. Dabei sollen je 3 Karten an insgesamt 4 Spieler verteilt werden, also 12 Karten. Das Deck besteht aus 20 Karten. Jede Karte ist nummeriert von 1-20. Nun habe ich mit gedacht, dass ich eine Zufallszahl zwischen 1 und 20 generiere, schaue, ob die in einem Array, welches als Speicher für schon verteile Karten dient, vorhanden ist, wenn ja, dann muss er noch mal eine generieren und schauen, wenn nicht wird sie umgewandelt in den Kartenname und davor noch in das Kartenarray gespeichert. Am Anfang durchgehe ich zwei For-Schleifen, einmal für Spieler 0 bis 3 und dann für Karte 1 bis 3. Allerdings will der Algorithmus noch nicht so richtig, ich bin jetzt seit einer Stunde dran, Fehler zu suchen, aber jedes Mal verteilt er mir die Karten nicht richtig oder läuft in eine Endlosschleife :cry:
Wo ist mein bzw. sind meine Fehler?

Delphi-Quellcode:

procedure TSFrame.Mischen();
var i,j,k,zufall:integer;
    Status:Boolean;
    Karte,Test:String;
begin
  Randomize;
  for i:=0 to Length(VerteilteKarten)-1 do
    VerteilteKarten[i]:=0;
  for i:=0 to 3 do begin
    for j:=1 to 3 do begin
      Status:=false;
      repeat
        Status:=false;
        zufall:=Random(1)+ 20;
        for k:=0 to Length(VerteilteKarten)-1 do begin
          if VerteilteKarten[k] = zufall then begin
            Status:=true;
            break;
          end;
        end;
      until Status = False;
        for k:=0 to Length(VerteilteKarten)-1 do begin
          if VerteilteKarten[k] = 0 then begin
            VerteilteKarten[k] := zufall;
            break;
          end;
        end;
        if zufall = 1 then
          Karte:='K1'
        else if zufall = 2 then
          Karte:='E5'
        else if zufall = 3 then
          Karte:='H4'
        else if zufall = 4 then
          Karte:='H5'
        else if zufall = 5 then
          Karte:='K5'
        else if zufall = 6 then
          Karte:='P3'
        else if zufall = 7 then
          Karte:='P1'
        else if zufall = 8 then
          Karte:='P5'
        else if zufall = 9 then
          Karte:='P4'
        else if zufall = 10 then
          Karte:='E4'
        else if zufall = 11 then
          Karte:='E2'
        else if zufall = 12 then
          Karte:='H2'
        else if zufall = 13 then
          Karte:='K2'
        else if zufall = 14 then
          Karte:='H1'
        else if zufall = 15 then
          Karte:='K4'
        else if zufall = 16 then
          Karte:='P2'
        else if zufall = 17 then
          Karte:='E1'
        else if zufall = 18 then
          Karte:='E3'
        else if zufall = 19 then
          Karte:='H3'
        else if zufall = 20 then
          Karte:='K3';
        Server.Socket.Connections[i].sendText('-gc'+IntToStr(j)+Karte);
        TEdit(SFrame.FindComponent('sp'+IntToStr(i+1)+'_k'+IntToStr(j))).Text:=Karte;
    end;
  end;
end;

[Furtbichler]

Mische die Karten nach Fisher-Yates und verteile die ersten 12 Karten. Genauso, wie Du es in der Realität machen würdest.

[Romiox]

Zitat:

Zitat von Furtbichler (Beitrag 1168402)

Mische die Karten nach Fisher-Yates und verteile die ersten 12 Karten. Genauso, wie Du es in der Realität machen würdest.

Ich hab mich nicht ganz durch deinen Quelltext gequält (Code Tags sind gut, Delphi Tags sind besser ;)), aber erst Mischen und dann 12 Verteilen ist wirklich die einfachste Variante.

Delphi-Quellcode:

for i = 0 to KartenArray.length - 1 do
  begin
  zufall = Random(KartenArray.length - 1);
  dummy = KartenArray[i];
  KartenArray[i] = KartenArray[zufall];
  KartenArray[zufall] = dummy;
  end;

[Gravitar]

Hi,

habe das Thema für mein Poker-Wahrscheinlichkeitsrechner inzwischen sehr performant umgesetzt:

1. Mischen ist nicht notwendig und kostet nur Zeit
2. Lege dir eine Liste vom Typ TCard an (Record Value u. Farbe)
3. Wähle aus der Liste per Zufall eine Karte aus und verteile sie an den Spieler
4. Danach löscht Du diese Karte aus der Liste

Dadurch musst du nicht jedesmal prüfen, ob die Karte bereits verteilt wurde. Durch das zufällige Auswählen einer Karte aus der "Kartenliste" sparst du dir auch noch das mischen.

[Iwo Asnet]

Zitat:

Zitat von Gravitar (Beitrag 1168593)

4. Danach löscht Du diese Karte aus der Liste

Entschuldige bitte, DAS hälst Du für performant? Fisher-Yates geht einmal durch die Liste und führt Nx3 Zuweisungen durch, die vermutlich durch Verwendung von Registern noch optimiert werden. Demnach ist Fisher-Yates vom Aufwand O(n).

Dein Ansatz löscht ein Element aus der Liste. Falls Du nicht gerade eine verkettete Liste verwendest (wobei dann das Auffinden eines Elementes O(n) wäre, also alles andere als performant), wird dein Verfahren bei O(n*n) landen, denn jedes 'Löschen' ist vom Aufwand O(n).

Bei meinem bescheidenen Wissen ist O(n) im allgemeinen performanter als O(n*n), zumindest bei vergleichbarem Overhead.

Falls ich mich irre, und Du eine Kartenstapel-Klasse/Struktur hast, die dies alles sehr schnell bewerkstelligt, lass es mich wissen. Ich lerne immer wieder gerne dazu.

[shmia]

Für die Datenhaltung der Karten gibt es ja zwei Ansätze
* Arrays
* Listen
Listen sind dabei der abstraktere und bessere Ansatz, denn man braucht nicht darum kümmern, dass beim Löschen einer Karte ein Loch entsteht oder dass beim Einfügen evtl. neuer Platz geschaffen werden müsste.

Ein Kartenspiel mit 32 Karten aus dem dann Karten an die Spielerhände verteilt werden lässt sich viel leichter mit Listen als mit Arrays implementieren.
Der kleine Overhead, den Listen gegenüber Arrays haben liegt deutlich unter einer Millisekunde - der Spieler bemerkt davon überhaupt nichts.

Man benötigt folgende Listen:
* Kartengeber (zu Beginn gefüllt mit 32 Karten)
* Spieler 1 ... Spieler N
* Tisch = Karten die auf dem Tisch liegen

Je nach Kartenspiel braucht jeder Spieler noch eine weitere Liste in der er seine gewonnenen Stiche ablegt.
Es kann für den Tisch auch zwei Listen geben (verdeckte Karten / offene Karten).

Auf jeden Fall sind Listen die Vorraussetzung dafür, dass der Code gut les- und verstehbar wird.
Wenn z.B. ein Spieler gewonnen hat und die Karten einsacken will, dann sieht das so aus:

Delphi-Quellcode:

TischList.MoveTo(Sieger.WinList); // alle Karten auf dem Tisch in die "Gewinnliste" verschieben

Da ja ständig Karten zwischen den Listen verschoben werden, sollte die Klasse für die Listen dies speziell berücksichtigen, damit man später mit einem Methodenaufruf auskommt:

Delphi-Quellcode:

AktiverSpieler.HandList.MoveCard(IndexDerKarte, TischList); // gewählte Karte auf den Tisch legen

[idefix2]

Bei so einem Code schaudert es mich:

Delphi-Quellcode:

if zufall = 1 then
          Karte:='K1'
        else if zufall = 2 then
          Karte:='E5'
        else if zufall = 3 then
          Karte:='H4'
        ....
        else if zufall = 19 then
          Karte:='H3'
        else if zufall = 20 then
          Karte:='K3';

Wie wäre es mit

Delphi-Quellcode:

const kartennamen: array[1..20] of string = ('K1','E5','H4',...,'H3','K3');
....

karte:=Kartennamen[zufall]

[Iwo Asnet]

Zitat:

Zitat von shmia (Beitrag 1168601)

Für die Datenhaltung der Karten gibt es ja zwei Ansätze
* Arrays
* Listen
Listen sind dabei der abstraktere und bessere Ansatz, denn man braucht nicht darum kümmern, dass beim Löschen einer Karte ein Loch entsteht oder dass beim Einfügen evtl. neuer Platz geschaffen werden müsste.

Das stimmt, aber wenn man über (theoretische) Performance redet, also über Algorithmik, dann ist dieses Argument fehl am Platze.

Das der Spieler davon nix merkt, ist auch klar, aber wenn ich z.B. eine Pokersimulation schreibe, dann macht es sehr wohl einen Unterschied, ob ich pro Sekunde 100000 oder 1000000 Spiele simulieren kann.

[gammatester]

Zitat:

Zitat von idefix2 (Beitrag 1168705)

Bei so einem Code schaudert es mich:
...

Mich macht etwas ganz anderes schaudern:

Delphi-Quellcode:

Status:=false;
repeat
  Status:=false;
  zufall:=Random(1)+ 20;
  ...
until Status = False;
...
//Orgie mit if Zufall=...

Abgesehen davon, daß das erste

Delphi-Quellcode:

Status:=false;

völlig überflüssig ist, nimmt Zufall immer nur den Wert 20 an! Selbst Dein verbesserter Code wird da nichts bringen.

[idefix2]

Naja, das ist natürlich falsch, aber im gegensatz zur IF-Sequenz keine böse Absicht, sondern nur ein Vertipper - richtig wäre und ist wohl auch gemeint

Delphi-Quellcode:

random(20)+1

[Gravitar]

Zitat:

Zitat von Iwo Asnet (Beitrag 1168599)

Entschuldige bitte, DAS hälst Du für performant? Fisher-Yates geht einmal durch die Liste und führt Nx3 Zuweisungen durch, die vermutlich durch Verwendung von Registern noch optimiert werden. Demnach ist Fisher-Yates vom Aufwand O(n).

Mhm,:gruebel: stimmt. Die Funktion TList.Delete scheint wirklich das Element zu löschen und die anderen Elemente aufrücken zu lassen. Ich dachte immer, dass das Löschen über eine verkettete Liste und "umbiegen" von 2 Pointern realisiert würde.

Ich probiere mal Fisher-Yates aus (einmal eine TList von 52 Elementen durcheinandermischen und danach dann stumpf die ersten n Karten nach dieser TList ziehen).

Mal sehen, wie groß der Laufzeitunterschied dann ist (bei 50.000.000 simulierten Karten).

Melde mich, wenn ich mehr habe. Danke für den Tipp:thumb:

[shmia]

Zitat:

Zitat von Donald Knuth

Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

Grob auf Deutsch:
Programmierer verschwenden jede Menge Zeit oder sorgen sich um die Geschwindigkeit von unkritischen Teilen ihrer Programme.
Dies hat gwöhnlich starke negative Auswirkungen auf das Debuggen und die Wartbarkeit.
Den Rest schenk' ich mir; ihr könnt wahrscheinlich besser Englisch als ich.

Auf jeden Fall ist die Entscheidung gegen Listen und für Arrays eine Optimierung an der falschen Stelle!
Viel wichtiger ist doch der Spielalgorithmus; hier kann man durch kleine Änderungen z.B. Alpha-Beta-Suche statt MinMax-Suche, grosse Verbesserungen erreichen.

[BUG]

Aber gerade das Mischen von Karten (also Erstellen eines neuen gemischten Kartenstapels) kann man doch gut wegkapseln, so das es von außen egal ist, wie intern gemischt wird; und heraus kommt eine nette randomisierte Liste, da es für einen Pokeralgorithmus wirklich Sinn machen würde, problemlos Karten in der Mitte entfernen zu können.

Und wenn es wirklich ans Eingemachte geht, kann man dann immer noch über einen Array mit Freispeicherverwaltung für die Karten nachdenken.

EDIT: Warum eigentlich Freispeicherverwaltung: die Anzahl der Karten in einem Stapel/Spiel bleibt ja immer gleich.

[Gravitar]

So,

nachdem ich nun Fisher-Yates als Randomisierung der Karten genutzt habe und nicht mehr Karten aus meiner TList über TList.Delete rauslösche, komme ich zu folgenden Laufzeiten:

50.000.000 Handsimulationen für Texas-Hold'em

Ansatz 1: TList der Karten mit Zufallsziehung einer Karte und TList.Delete = 142,601 sek.

Ansatz 2: Randomisieren einer Liste mit 52 Nummern und Ziehung
der 1..n Karten lt. randomisierter Liste = 103,881 sek.

Zeitersparnis = 38,72 sek. = 27%

Immerhin, aber der vorherige Ansatz war anscheinend auch schon ganz gut optimiert.

[Furtbichler]

Wenn Du nun noch "Texas Hold'em" aus der Simulation nimmst?
Wenn ich die beiden Verfahren vergleichen will, dann habe ich das Problem, das ich im Falle von Fisher-Yates auf das ständige Erzeugen eines Kartenstapels verzichten kann, denn ich kann den Kartenstapel mischen, und die verteilten Karten einfach dadurch 'aus dem Stapel entfernen', indem ich einen Stapelzähler beginnend von 52 dekrementiere.

Beim Austeilen durch Entfernen zerstöre ich den Kartenstapel und muss ihn in der Folge bei jedem neuen Start auch neu erstellen.

Wenn Fisher-Yates ein perfektes Mischen darstellt, ist die Entropie (also die Unordnung) eines gemischten Kartenstapels immer die gleiche, egal ob der Ursprungsstapel geordnet war oder nicht. Hier kenne ich aber die Fallstricke und würde mich eines Besseren belehren lassen.

Ich kann mir sehr gut vorstellen, das deine Pokersimulation noch viel schneller wird, wenn Du FY nimmst und den Stapel nicht jedes mal neu erstellst.

[Gravitar]

Zitat:

Zitat von Furtbichler (Beitrag 1168868)

Ich kann mir sehr gut vorstellen, das deine Pokersimulation noch viel schneller wird, wenn Du FY nimmst und den Stapel nicht jedes mal neu erstellst.

Hey, da kennt ja jemand meine Umsetzung für Ansatz 1 sehr genau! Ja stimmt, tatsächlich muss ich den Kartenstapel in Ansatz 1 immer wieder neu aufbauen (über TList.Assign).

In Ansatz 2 (Fisher-Yates) verzichte ich darauf. Schließlich zerstöre ich die Kartenliste ja nicht, sondern greife lediglich über die randomisierte Liste auf die Karten zu.

Die dargestellten Zeiten berücksichtigen diesen Effekt bereits.

Aber, wie gesagt, auch der Ansatz 1 scheint über die TList-Implementierung schon ziemlich effizient zu sein.