Grenzen von RandSeed

Für alles, was in den übrigen Lazarusthemen keinen Platz, aber mit Lazarus zutun hat.
Antworten
Scotty
Beiträge: 768
Registriert: Mo 4. Mai 2009, 13:24
OS, Lazarus, FPC: Arch Linux, Lazarus 1.3 r44426M FPC 2.6.4
CPU-Target: x86_64-linux-qt/gtk2
Kontaktdaten:

Grenzen von RandSeed

Beitrag von Scotty »

Wenn mein Spiel über Netzwerk läuft, übermittle ich einen Startwert für den Zufallsgenerator (Longword) und setze den bei allen Mitspielern als Randseed ein. Das funktioniert meistens, auch über OSe hinweg, aber zuweilen zieht eines der Programme falsche Items. Eine Grenze von Randseed ist, wenn ich mich recht erinnere, dass nur 32k Werte zufällig sind. Ich wäre aber davon ausgegangen, dass RandSeed:=xy den Zähler zurücksetzt. Habe ich irgendetwas nicht bedacht?

Scotty
Beiträge: 768
Registriert: Mo 4. Mai 2009, 13:24
OS, Lazarus, FPC: Arch Linux, Lazarus 1.3 r44426M FPC 2.6.4
CPU-Target: x86_64-linux-qt/gtk2
Kontaktdaten:

Re: Grenzen von RandSeed

Beitrag von Scotty »

Nach ein wenig probieren: Mein erster Gedanke war, dass durch die Überladung longint/int64 irgendeine Adressierung nicht stimmt. Deswegen habe ich überall typecasts eingebaut random(longint(<value>)) - allerdings ohne Erfolg. Debugmeldungen belegen, dass der Fehler durch den Zufallsgenerator zustande kommt, einen groben Schnitzer im Code kann ich zu 99% ausschließen. Ich werde als workaround die Zufallswerte nur an einem PC generieren und diese Werte mit den Mitspielern synchronisieren.
Nochmal zum prinzipiellen Vorgehen: Zu Spielbeginn übertrage ich einen Startwert für den Zufallsgenerator (Randseed:=...). Jeder PC würfelt daraufhin gleich mit random(<aList.Count>). Dies funktioniert mit geschätzten 1:1000 korrekt. Stimmt ein random() aber mal nicht, kommt alles durcheinander.

Benutzeravatar
corpsman
Lazarusforum e. V.
Beiträge: 1496
Registriert: Sa 28. Feb 2009, 08:54
OS, Lazarus, FPC: Linux Mint Mate, Lazarus GIT Head, FPC 3.0
CPU-Target: 64Bit
Wohnort: Stuttgart
Kontaktdaten:

Re: Grenzen von RandSeed

Beitrag von corpsman »

Also in speziell deinem Fall wenn du sogar Plattformunabhängig bist würde ich den Zuffalsgenerator einfach selbst machen, das ist einfacher.

ein Zufallssgenerator ist auch nicht so schwer :

Code: Alles auswählen

var seed:Integer = 10;
 
Function Random (value:Integer):integer;
begin
  seed := (seed* seed * 5 + seed ) <Primzahl>
  result := seed mod value;
end;


das ist nun ein sehr einfaches Beispiel mit dem Generatorpolynom a*x^2 +x da gibt es natürlich noch bessere.

Auch solltest du darauf schauen das jedes Programm immer die Selben Zufallszahlen ( also Reihenfolge und Anzahl ) zieht, sonst laufen die werte immer auseinander.
So kannst du Zumindest nachvollziehen was passiert.

Ich würde die Primzahl so wählen das x*x*5 +X immer noch in Integer bleibt, also sehr klein, wenn dir das nicht reicht musst halt int64 nehmen.
--
Just try it

Scotty
Beiträge: 768
Registriert: Mo 4. Mai 2009, 13:24
OS, Lazarus, FPC: Arch Linux, Lazarus 1.3 r44426M FPC 2.6.4
CPU-Target: x86_64-linux-qt/gtk2
Kontaktdaten:

Re: Grenzen von RandSeed

Beitrag von Scotty »

Und ich dachte, das wäre viel komplizierter! Sehr einfach, aber garantiert synchron:

//http://shootout.alioth.debian.org/gp4/benchmark.php?test=fasta&lang=fpascal&id=2

Code: Alles auswählen

unit urandom;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils;
 
function GenRandom(aLimit:integer=-1): integer;
procedure GenRandomize;
 
const Seed : integer = 42;
 
implementation
 
uses LCLIntf;
 
const
  IM = 139968;
  IA = 3877;
  IC = 29573;
 
//http://shootout.alioth.debian.org/gp4/benchmark.php?test=fasta&lang=fpascal&id=2
function GenRandom(aLimit : integer): integer;
begin
  Seed:=(Seed * IA + IC) mod IM;
  if aLimit>0 then
    Result:=Seed mod aLimit else
    Result:=Seed;
end;
 
procedure GenRandomize;
begin
  Seed:=GetTickCount mod IM;
end;
 
end.


Zufälligere Routinen sind in den Numerical Recipies beschrieben.

Benutzeravatar
corpsman
Lazarusforum e. V.
Beiträge: 1496
Registriert: Sa 28. Feb 2009, 08:54
OS, Lazarus, FPC: Linux Mint Mate, Lazarus GIT Head, FPC 3.0
CPU-Target: 64Bit
Wohnort: Stuttgart
Kontaktdaten:

Re: Grenzen von RandSeed

Beitrag von corpsman »

Denk dran, das du mit dem Generator aber nichts verschlüsseln solltest. Denn sonst schreibt dir jeder halb wechs gute Programmierer eine Application, welche den Seed ausliest, kurz nachdem du diesen gesetzt hast.

Code: Alles auswählen

hackseed := GenRandom(-1);

Aber wenn du nur ein "synchrones" random brauchst tuts der bestimmt ;)

Auch Sollte Seed eine Lokale Variable sein ...
--
Just try it

Scotty
Beiträge: 768
Registriert: Mo 4. Mai 2009, 13:24
OS, Lazarus, FPC: Arch Linux, Lazarus 1.3 r44426M FPC 2.6.4
CPU-Target: x86_64-linux-qt/gtk2
Kontaktdaten:

Re: Grenzen von RandSeed

Beitrag von Scotty »

Seed ist mein RandSeed und muss global sein (den Wert für GenRandomize übertrage ich an die Mitspieler). Und da ich nur ein Spiel programmiere, das auch im Netzwerk läuft, langt eine ganz einfache Randomisierung, die aber absolut zuverlässig in der Abfolge ist. Ich frage mich nur, ob es ein Bug ist, wenn FPC's random() nicht 100%-ig funktioniert.

Benutzeravatar
corpsman
Lazarusforum e. V.
Beiträge: 1496
Registriert: Sa 28. Feb 2009, 08:54
OS, Lazarus, FPC: Linux Mint Mate, Lazarus GIT Head, FPC 3.0
CPU-Target: 64Bit
Wohnort: Stuttgart
Kontaktdaten:

Re: Grenzen von RandSeed

Beitrag von corpsman »

Ich bin mir immer noch nicht sicher, ob dein random Problem ein Problem von FPC ist, oder nicht doch irgendwo in deinem Code Problematisch ist.

Aber solltest du es schaffen eine Demo zu bauen die das Problem hervorruft, poste es hier, oder im Bug Report dann wird es sicherlich auch behoben ;)
--
Just try it

carli
Beiträge: 657
Registriert: Sa 9. Jan 2010, 17:32
OS, Lazarus, FPC: Linux 2.6.x, SVN-Lazarus, FPC 2.4.0-2
CPU-Target: 64Bit

Re: Grenzen von RandSeed

Beitrag von carli »

Synchronisation ist da so'ne Sache.

Ich hatte auch mal was synchrones programmiert, da hatten die Clients aber eine fest generierte Zufallszahlenliste (512 Zahlen reichen).
Probier' das auch erstmal so oder setze generell immer nur eine bestimmte Zahl ein und teste, ob es nicht an was anderem liegt.
Soweit ich weiß, führt die Verwendung von Fließkommazahlen sehr oft zu Desynchronisation, vor allem, wenn man auf unterschiedlichen Plattformen (x86_64 arbeitet mit SSE, i386 mit FPU) oder Compilern (die runden anders zwischendurch) arbeitet.

Scotty
Beiträge: 768
Registriert: Mo 4. Mai 2009, 13:24
OS, Lazarus, FPC: Arch Linux, Lazarus 1.3 r44426M FPC 2.6.4
CPU-Target: x86_64-linux-qt/gtk2
Kontaktdaten:

Re: Grenzen von RandSeed

Beitrag von Scotty »

Ich habe ein Testprogramm geschrieben - da kam es zu keinem Fehler (gleicher PC, Linux 64Bit und XP 32Bit in einer VirtualBox). Mein Programm selbst könnte nur durch irgendeine Art "Speicherverschiebung" kompromittiert worden sein, so viele random() stehen da nicht drin. Ich erstelle eine Integer-Liste, die mit der Zeit im Umfang abnimmt (deshalb geht eine vordefinierte Liste von Werten hier nicht so einfach). Aus dieser Liste ziehe ich per random() einen Wert, weise einer anderen Liste diesen Wert zu und lösche das Item. Ich habe die gezogenen Zahlen geloggt. Diese sind in ~0.1% Fällen verschieden. Man konnte auch Spiele á ~100 random()-Aufrufe komplett durchspielen. Aber halt nicht immer. Der Startwert war in jedem Fall identisch. Meine Betatester haben XP und Vista, ich spiele unter Linux.

carli
Beiträge: 657
Registriert: Sa 9. Jan 2010, 17:32
OS, Lazarus, FPC: Linux 2.6.x, SVN-Lazarus, FPC 2.4.0-2
CPU-Target: 64Bit

Re: Grenzen von RandSeed

Beitrag von carli »

~0.1%

das sind 0.001% zu viel!

wenn schon synchron, dann richtig. Eine kleine Nachkommastelle und schon ist die Sync futsch!

RSE
Beiträge: 462
Registriert: Mi 30. Jul 2008, 13:11
OS, Lazarus, FPC: WinXP SP3 (L 0.9.28.2 FPC 2.2.4)
CPU-Target: 32Bit
Kontaktdaten:

Re: Grenzen von RandSeed

Beitrag von RSE »

Du kannst ja dann mal berichten woran es lag, wenn du den Fehler gefunden hast.
Seit er seinen neuen Computer hat, löst er alle Probleme, die er vorher nicht hatte!

Antworten