Mehr Speed für Random?

[Nikolas]

hast du schon mal ausprobiert, wie lange so ein random-aufruf dauert? Am Besten im Vergleich zu einer Multiplikation oder einem einfachen Vergleich mit einem Element aus einem kleinen Array.

[Klaus01]

Zitat von Schlabbermampf:

Zitat von Klaus01:

randomize sollte nur einmal aufgerufen werden, vielleicht beim Start des Programms
und nicht bei jedem Würfeln.

Ich hab das randomize jetzt vor das repeat gesetzt. läuft alles superschnell jetzt, allerdings kommts mir etwas spanisch vor, dass beim Endergebnis, wo angezeigt wird, wer wie oft gewonnen hat und wie oft ein unentschieden erreicht wurde, so nie ein unentschieden auftritt, wenn das das randomize jedoch direkt vor dem random befehl steht kommt es schon ab und zu vor. woran kann sowas liegen?

Hallo Fabian,

randomize soll nur einmal ausgeführt werden. Nicht bei jedem Wurf.
Einmal pro Programmstart reicht. Steht so auch in der Delphi Hilfe.

Grüße
Klaus

[Schlabbermampf]

Zitat von Nikolas:

hast du schon mal ausprobiert, wie lange so ein random-aufruf dauert? Am Besten im Vergleich zu einer Multiplikation oder einem einfachen Vergleich mit einem Element aus einem kleinen Array.

sry da muss grad passen. hatte delphi nur in der schule. wie kann ich denn die dauer messen? und was ist ein "Element aus einem kleinen Array"

Zitat von Klaus01:

randomize soll nur einmal ausgeführt werden. Nicht bei jedem Wurf.
Einmal pro Programmstart reicht. Steht so auch in der Delphi Hilfe.

hab jetzt das randomize mal komplett aus der funktion rausgelassen
es ist jetzt direkt am anfang von dem startknopf, wird also nur einmal ausgeführt.
was jetzt aber immer passiert ist, dass, obwohl beide eingegebene einheiten genau gleich sind, viel öfters gewinnt. das kann ja auch irgendwie nich sein...alles seltsam

[Klaus01]

Hallo Fabian,

welchen Startknopf?

Ich habe es hierhin gepackt:

Delphi-Quellcode:

procedure Tform1.FormCreate(Sender: TObject);
begin
  randomize;
end;

auch hier kann das randomize weg:

Delphi-Quellcode:

repeat
  pas1:=strtofloat(plusangriffscheren1.text);
   //randomize;
   ras1:=random(6)+1;
   if ifs1.checked then a1:=ras1+pas1;

und hier auch:

Delphi-Quellcode:

procedure Tform1.Button1Click(Sender: TObject);
begin
  //randomize;
  x:=random(6)+1;
  w6.text:=floattostr(x);
end;

Ein wenig zur Wahrscheinlichkeitsrechnung:
http://www.faes.de/Basis/Basis-Lexik...inlichke1.html
http://www.henked.de/begriffe/wahrsc...it.htm#wuerfel

Grüße
Klaus

[Nikolas]

Hast du noch nicht mit arrays gearbeitet? Dem einfachsten Listentyp? So was wie Mylist0]?
Schau die einfach mal das Thema in der OH an, das wirst du sofort verstehen.
Meine Idee sah so aus (da ich nicht weiss, wie schnell random eigentlich ist, weiss ich nicht, ob sie schneller ist, als deine Methode): Du berechnest die Wahrscheinlichkeit, dass von deinen n Würfeln genau k treffen.
Die Wahrscheinlichkeit dafür beträgt

Code:

P(k)=(n  k)*p^k*(n-p)^(1-p)

, das p steht für die Wahrscheinlichkeit, dass ein Würfel trifft; im Fall, dass du mindestens eine 4 Würfeln musst, beträgt p dann 4/6=2/3. Das (n k) soll ein Binomialkoffezient sein, das Ganze ist eine Binomialverteilung. (einfach in die Wikipedia schauen).
Jetzt legst du dir eine Liste an. Die zu berechnen dürfte nicht allzu lange dauern, dass kannst du einmal beim Programmstart machen. Jetzt wird es etwas fies, da du gleich eine nette Arraykonstruktion hast, obwohl du damit noch nicht gearbeitet hast. Also eine kurze Einführung: ein array ist eine geordnete Anordnung von Variablen des gleichen Typs. Anstatt also 5 integer, int0, int1, ..., int4 zu definieren, kannst du auch eine Liste mit so vielen Integern anlegen, wobei du die einzelnen Werte dann mit MyIntegerList[0]:=1; könntest du dann einfach einen Wert an die erste (!) Stelle des arrays legen und auch genauso auslesen. Für mehr Info gibts die OH.
So eine Liste kannst du auch mehrdimensional anlegen.
Hier wäre eine dreidimensionale Liste angebracht. Eine Dimension wäre die Anzahl der Würfel im Spiel (n), eine andere Dimension wäre die Anzahl der Augen auf deinem Würfel. (Das kannst du dir einfach wie ein Koordinatensystem vorstellen) Wenn du in diesem System auf eine Stelle schaust, hast du da die Kombination aus der Anzahl der Würfel, die in diesem Zug gespielt werden, als auch die Wahrscheinlichkeit, dass einer dieser Würfel trifft (aus der zweiten Koordinate, die dann die Augenzahl angibt, die erreicht werden muss). An dieser Stelle hast du jetzt noch eine Liste mit n Einträgen, nämlich den Wahrscheinlichkeiten, dass keiner, einer,..., alle Würfel treffen. Wie du vielleicht aus der Schule mal gehört hast, müssen sich diese Wahrscheinlichkeitn zu 1 aufaddieren. (die Wahrscheinlichkeit, dass eine irgendeine Anzahl an Würfeln gewinnt, ist sicher gleich 1). Diese Liste kannst du dir jetzt wie eine Art Glücksrad vorstellen, das in n Gebiete unterteilt ist, die unterschiedlich groß sind. (Wenn du 100 Würfel hast und mindestens eine vier Würfeln musst, ist die Wahrscheinlichkeit, dass 50 Würfel treffen deutlich höher, als die Wahrscheinlichkeit, dass nur 10 Würfel treffen). Jetzt musst du nur noch einen Ball in dieses Glücksrad werfen und schauen, wo er liegen bliebt. Du machst also einen einzelnen randomAufruf und bekommst eine Zahl x.
Du hast schon eine Liste p(k), in der steht, wie Wahrscheinlich es ist, dass k Würfel treffen. Jetzt schaust du dir die p(k) der Reihe nach an und suchst das erste k', so dass p(k')>x. Dieses k' gibst du dann aus. Nach dem Berechnen der Liste, hast du also nur noch ein paar ( recht genau log_2(n) bei Binärsuche) if-Abfragen, die schneller sein sollten, als ein paar RandomAufrufe. Schön, dass du bis hier noch gelesen hast. Wenn du das Projekt wirklich durchziehen willst, und dir dabei noch etwas Stochastik anlesen willst, (Niveau 10. Klasse Gymnasium, wenn du es noch nicht hast), kann ichs nochmal schöner aufschreiben und vielleicht etwas Code liefern. Ich hoffe du erkennst die Idee wenigstens in den Grundzügen, wenn nicht, bitte fragen , ich finde das Problem selbst recht interessant.
Wikipedia:Binomialkoeffizient, Bimomialverteilung, (Binarysearch, wenn du noch Lust hast, klappt auch ohne)
OH: statische Arrays (in mehreren Dimensionen), setzen der Länge solcher

[Schlabbermampf]

alsoooo
schon heftig...
stochastik hatten wir leider noch nich. kommt jetzt in der 13ten... (mein bruder hat mich aber schon davor gewarnt )
ich komm zwar von der logik ganz gut mit in der ganzen sache, aber für mich ist das ganze auf wiki und in der oh (sofern das die code library ist) eher fachchinesisch...

war halt jetzt eher darauf bedacht den gesamten prozess möglichst realitätsnah ablaufen zu lassen, also damit man sich zB auch einen kampf einfach berechnen lassen kann ohne die würfel selbst in die hand nehmen zu müssen.

ansich funktioniert das ganze mit dem randomize. hab jetzt mal das mit der randomize prozedur mit formcreate gemacht und klappt super.
vorallem, ich muss noch was einbauen, dass die sechsen zählt um diverse ausrüstungen darzustellen. denke mal das kompliziert das ganze mit den arrays nochmal.
ach verdammt, bin aber jetzt auch etwas heiß drauf geworden mich etwas zu vertiefen in deine sache da, weil programmieren macht übelst laune find ich und stochastik wird denk ich mal auch abiturthema sein.
also wenns dir wirklich nix ausmacht, dann könntest du noch n bissel dazuerzählen und n paar codes liefern wie man son array aufstellt.

ach du gott, wirklich üüüübelst nett wie ihr euch hier für einen einsetzt. vielen dank leute!
wenn das programm fertig ist werd ichs auf jedenfall hier reinstellen.

mfg Fabian

[Nikolas]

Das zählen der sechser ist auch kein Problem, das kann mit dem gleichen Code sauber gelöst werden.
Das mit den Arrays musst du dir selber mal anschauen, da gibts so viele Quellen zu, das sollte wirklich kein Problem darstellen.
Die Idee ist eigentlich recht einfach. Sagen wir mal, du hast 3 Würfel und musst eine Drei Würfeln. p(0) gibt dann an, wie wahrscheinlich es ist, nur einser und zweier zu würfeln, also 0 Treffer zu machen. Die Wahrscheinlichkeit liegt dafür bei p(0)=(2/6)^3.
Die andeneren Wahrscheinlichkeiten p(1) bis p(3) kannst du über die oben beschriebene Gleichung für die Binomialverteilung berechnen. (Im weiteren gehe ich mal von nur drei Würfeln aus)
also p(0)=8/27, p(1)=(2/6)^2*(4/6)*3=4/36*2=8/36 (die drei kommt aus dem Binomialkoeffizienten), usw.
Während du dir diese Werte ausrechnest, legst du eine Liste an:
Der erste Eintrag ist p(0), der zweite ist p(0)+p(1), der dritte p(0)+p(1)+p(2), der dritte dann p(0)+p(1)+p(2)+p(3), wobei du den nicht ausrechnen musst, da er 1 ist. (gute Kontrollmöglichkeit, ob du vorher richtig gerechnet hast).
Das ist jetzt sozusagen deine Einteilung für dein Glücksrad. Wenn alle Wahrscheinlichkeiten bei 1/3 gelegen hätten, lägen deine Einträge bei 1/3, 2/3, 3/3=1. Die Abstände zwischen zwei benachbarten Zahlen ist dann ein Maß dafür, wie wahrscheinlich es ist, dieses Ergebniss zu erhalten.
Bei unserem Beispiel oben sind die ersten beiden Felder grob gleich groß, das nächste wird deutlich größer, da zwei Treffer hier der wahrscheinlichste Ausgang sind.
Jetzt machst du einen Randomaufruf und erhällst eine Zahl zwischen Null und eins. Jetzt musst du nur noch herrausfinden, in welchem Abschnitt diese Zahl ist. Dafür gehst du die p-Liste Schritt für Schritt durch und schaust, ob der jeweilige Wert größer ist, als die gezogene Zahl. Sobald das der Fall ist, bist du fertig. Wenn z.B. die Zahl 6/27 aus dem Generator gekommen ist, bist du sofort fertig, da p(0)>6/27, und du gibst als Ergebniss die 0 Treffer zurück, gibt der Generator aber 9/27 raus, fliegst du erst bei der zweiten Überprüfung raus, gibst also 1 Treffer zurück. Damit hast du pro Wurf (egal, wie viele Würfel zu benutzt, es können auch gerne 50 sein), nur einen einzigen Randomaufruf und ein paar Vergleiche.

Bis jetzt bin ich von einer bestimmten Anzahl an Würfeln und einer bestimmten Zahl die überboten werden muss, ausgegangen und habe dafür die Liste der Wahrscheinlichkeiten angelegt. Dieses zweidimensionale Array, von dem ich im letzten Post erzählt habe, ist also eigentlich nichts anderes als eine Art Buch, in dem die Wahrscheinlichkeitslisten abgedruckt sind. Wenn also eine Anfrage für 23 Würfel kommt, die die 5 Überbieten müssen, suchst du dir einfach die passende Tabelle raus und machst dann wie oben weiter.


// Ab jetzt wirds noch etwas Spielerei, das brauchst du eigentlich noch nicht.
Die Anzahl der Vergleiche ist hier offensichtlich der Schritt der die meiste Zeit während der eigentlichen Berechnung benötigt, nachdem die Liste zu Programmstart aufgestellt wurde. Die Frage ist jetzt, wie viele dieser Vergleiche benötigt werden. (Ich gehe jetzt mal von 10 Würfeln aus)
Wenn du die Liste einfach so vom Anfang an durchgehst, wirst du zu viele Vergleiche mit den Wahrscheinlichkeiten von p(0) p(1) usw vergeuden, da diese nur recht selten wirklich auftreten. Die Frage ist jetzt also, wo du am Besten mit der Suche anfängst, und in welcher Reihenfolge du die Werte anschaust. Meine Idee sieht so aus: (nicht ganz perfekt durchdacht, sollte aber recht gut sein)
Du beginnst beim Erwartungswert. (Der Erwartungswert ist die Anzahl an treffenden Würfeln, die auf lange Sicht am Häufigsten auftauchen. Bei 10 Würfeln und einem Minimum von 4 werden das sicherlich 5 sein, bei einem Minimum von 1 auf jeden Fall 10. Mit etwas denken oder Wikipedia, kommt man drauf, dass der Erwartungswert bei N*p liegt, wobei N die Anzahl der Würfel (z.B. 10) und p die Wahrscheinlichkeit, dass ein bestimmter einzelner Würfel trifft. (wenn du eine sechs würfeln musst, liegt p dann bei 1/6 und der Erwartungswert für 6 Würfel bei 1, d.h. wenn du sechs Würfel wirfst, wirst du meistens eine sechs sehen, was intuitiv auch klar sein wird)
Du vergleichst also deine Zufallszahl aus dem Generator (x) mit p(EW). Für x>EW vergleichst du sie mit p(EW+1) und dann nach oben, für x<p(EW) mit den darunterliegenden.
Das dürfte in den meisten Fällen sehr schnell zum Ergebniss führen.
{Wenn hier noch ein paar InfoStudenten mitlesen: Kennt ihr da einen SuchAlgo, der auf die Binomialverteilung oder andere Verteilungen optimiert wurde? Vll so eine Mischung aus meiner Startwertbestimmung mit einer binären Suche? Zu zeigen, dass ein Suchalgo minimale laufzeit für diese Binomialwerte hat, wäre doch sicher eine schöne Zettelaufgabe

Die OH ist nicht die CodeLibrary. In zweiteres kommen Codestücke, die so schön oder hilfreich sind, dass sie hier anderen Schreibern zur Verfügung gestellt werden. Die OH ist die in Delphi integrierte Hilfe, einfach mal F1 drücken und los gehts.

[Schlabbermampf]

also ich hab mich jetzt, mit hilfe meines bruders, allgemein etwas mit stochastik auseinandergesetzt.
die hilfe von dem delphi 5 das ich aus der schule hab kann mir die sache mit den arrays leider nicht ganz so gut erklären, aber ich kam zu dem schluss lieber so weitersumachen wie ich angefangen hatte, klappt mitlerweile superschnell und fast problemlos.

trotzdem danke für deine mühen, ich werd vieleicht nochmal drauf zurückkommen, aber momentan will ich lieber noch meine zeit für warhammer selbst, statt so nem programm dafür einsetzen ;D

wenn das programm fertig ist werd ichs auf jedenfall hier reinstellen!

mfg Fabian

[Blink]

Hallo

Wieso rufst du randomize immer so oft auf? Du solltes dir es angewöhnen das randomize nur einmal auf rufen zb. so

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, ExtCtrls, ComCtrls, Tabnotbk, Grids, Outline;

type
  Tform1 = class(TForm)

var
  form1: Tform1;
  x:real;

implementation

{$R *.DFM}

function wurf (a,w:real):real;

function svsw (sa,wv:real):real;

function kgvskg (kga,kgv:real):real;

procedure Tform1.Button1Click(Sender: TObject);

procedure Tform1.AuswertenClick(Sender: TObject);

// Ale anderen randomize entfernen und nur das lassen
initialization
  randomize;
end.

Dan sollte random auch richtig funktionieren.

[Nikolas]

Ich habe mal meine Idee grob umgesetzt. Ein paar Feinheiten fehlen noch und man muss an ein paar Stellen noch mal etwas denken. Da ich gerade Java lernen muss, habe ich es mal in der Sprache geschrieben, was es macht, sollte klar sein. (i++; ist identisch mit i:=i+1

Code:

public class WarHammer {

   
   int n=20; // maximale Anzahl an Würfeln in einem Wurf
   int augenMax=6; // maximale Augenzahl auf einem Würfel
   float[] fac = new float[n];
   float[][][] pList = new float[n][augenMax][augenMax+1];
   

   public static void main(String[] args) {

   }
   
   int WURF(int wurfel, int ziel) {
      
      float p = 1-(ziel-1)/augenMax;
      
      int EW = Math.round(wurfel*p);
      
      float x = (float) Math.random();
      
      if (pList[wurfel][ziel][EW] > x ) {
         int i = EW-1;
         while (pList[wurfel][ziel][i] > x) {
            i--;
         }
         return i; // oder i+-1 ??
      } else {
         int i = EW+1;
         while (pList[wurfel][ziel][i] <= x) {
            i++;
         }
         return i; // oder i+-1 ??
      }
   
   }
   
   void InipList() {
      for (int wurfel=0; wurfel<=n;wurfel++) { // Anzahl benutze Würfel
         for (int ziel=1;ziel<=augenMax;ziel++){ // zu erreichende Augenzahl
            for (int treffer=0; treffer<=augenMax; treffer++){ // anzahl treffende Würfe
               // hier werden die eigentlichen Wahrscheinlichkeiten ausgerechnet:
               int binom = binKoeff(wurfel, treffer);           // (wurfel  über erg
               float p = 1-(ziel-1)/augenMax; // wahrscheinlichkeit zu treffen
               // Binomialverteilung
               pList[wurfel][ziel][treffer] = (float) (binom*Math.pow(p, treffer)*Math.pow(n-p,1-p));
            }
         }
            
      }
      
   }
   
   int binKoeff(int n, int k) {
      // hier fehlen noch ein paar Sonderfälle
      return (int) (fac[n]/(fac[n-k]*fac[k]));
   }
   
   void IniFac() {
      fac[0]=fac[1]=1;
      for (int i=2;i<=n;i++) fac[i]=i*fac[i-1];
   }

}