AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Karten-Verteil-Algorithmus

Ein Thema von yss14 · begonnen am 28. Mai 2012 · letzter Beitrag vom 31. Mai 2012
Antwort Antwort
Seite 1 von 2  1 2   
yss14

Registriert seit: 27. Mai 2012
9 Beiträge
 
#1

Karten-Verteil-Algorithmus

  Alt 28. Mai 2012, 17:05
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
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;

Geändert von TBx (29. Mai 2012 um 14:04 Uhr) Grund: CODE-Tags durch DELPHI-Tags ersetzt
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#2

AW: Karten-Verteil-Algorithmus

  Alt 28. Mai 2012, 17:34
Mische die Karten nach Hier im Forum suchenFisher-Yates und verteile die ersten 12 Karten. Genauso, wie Du es in der Realität machen würdest.
  Mit Zitat antworten Zitat
Romiox

Registriert seit: 14. Okt 2010
Ort: Ruhrpott
57 Beiträge
 
#3

AW: Karten-Verteil-Algorithmus

  Alt 28. Mai 2012, 21:13
Mische die Karten nach Hier im Forum suchenFisher-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;
Janis F.
  Mit Zitat antworten Zitat
Gravitar

Registriert seit: 8. Okt 2006
94 Beiträge
 
Delphi 7 Enterprise
 
#4

AW: Karten-Verteil-Algorithmus

  Alt 29. Mai 2012, 16:19
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.
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#5

AW: Karten-Verteil-Algorithmus

  Alt 29. Mai 2012, 17:00
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.

Geändert von Iwo Asnet (29. Mai 2012 um 17:09 Uhr)
  Mit Zitat antworten Zitat
shmia

Registriert seit: 2. Mär 2004
5.508 Beiträge
 
Delphi 5 Professional
 
#6

AW: Karten-Verteil-Algorithmus

  Alt 29. Mai 2012, 17:35
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:
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:
AktiverSpieler.HandList.MoveCard(IndexDerKarte, TischList); // gewählte Karte auf den Tisch legen
Andreas

Geändert von shmia (29. Mai 2012 um 17:45 Uhr)
  Mit Zitat antworten Zitat
idefix2

Registriert seit: 17. Mär 2010
Ort: Wien
1.027 Beiträge
 
RAD-Studio 2009 Pro
 
#7

AW: Karten-Verteil-Algorithmus

  Alt 30. Mai 2012, 12:13
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]
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#8

AW: Karten-Verteil-Algorithmus

  Alt 30. Mai 2012, 12:33
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.
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
999 Beiträge
 
#9

AW: Karten-Verteil-Algorithmus

  Alt 30. Mai 2012, 12:33
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 Status:=false; völlig überflüssig ist, nimmt Zufall immer nur den Wert 20 an! Selbst Dein verbesserter Code wird da nichts bringen.
  Mit Zitat antworten Zitat
idefix2

Registriert seit: 17. Mär 2010
Ort: Wien
1.027 Beiträge
 
RAD-Studio 2009 Pro
 
#10

AW: Karten-Verteil-Algorithmus

  Alt 30. Mai 2012, 13:01
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
random(20)+1
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 08:05 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf