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 2 von 2     12
Gravitar

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

AW: Karten-Verteil-Algorithmus

  Alt 30. Mai 2012, 16:45
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, 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
  Mit Zitat antworten Zitat
shmia

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

AW: Karten-Verteil-Algorithmus

  Alt 30. Mai 2012, 19:36
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.
Andreas

Geändert von shmia (30. Mai 2012 um 19:46 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#13

AW: Karten-Verteil-Algorithmus

  Alt 30. Mai 2012, 21:04
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.

Geändert von BUG (30. Mai 2012 um 22:43 Uhr)
  Mit Zitat antworten Zitat
Gravitar

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

AW: Karten-Verteil-Algorithmus

  Alt 31. Mai 2012, 08:41
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.
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#15

AW: Karten-Verteil-Algorithmus

  Alt 31. Mai 2012, 09:03
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.
  Mit Zitat antworten Zitat
Gravitar

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

AW: Karten-Verteil-Algorithmus

  Alt 31. Mai 2012, 11:06
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.
  Mit Zitat antworten Zitat
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 07:58 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