1D Array: Zyklen / Perioden erkennen

Christian J. schrieb:
> die CRC32 Perioden erkennt.

"CRC32" und "Periode" ist mir ein Begriff.
Ich hab aber keinen Schimmer wonach du suchst. Kannst du das anhand 
eines Beispiels erklären?

@ TO

Machst du irgendwas mit Glücksspielautomaten?

Hmm.... hilft mir jetzt nicht weiter. Und der Beitrag wo nur Gegenfragen 
drinstehen (Wie sieht ein Array aus? Es ist egal wie eine Periode 
aussieht, die wiederholt sich nur eben :-) auch nicht. Es geht nur um 
die Strategie Perioden zu erkennen. Das mit dem Timing mache ich schon, 
zwei Ints koppeln durch Puffer ist mir nicht neu.

Welche Suchstrategie braucht man, das ist die Frage?

Weber schrieb:
> Machst du irgendwas mit Glücksspielautomaten?

Nein, Periodenerkennung bei "Game of Life"..... ich brauche kein 
Glücksspiel, ich bin Ingenieur.

Christian J. schrieb:
> Wie sieht ein Array aus? Es ist egal wie eine Periode
> aussieht, die wiederholt sich nur eben :-) auch nicht.

Na, dann halt nicht!
Wirst schon selber rausfinden. Irgendwie.
Und wenn dir 20 ms als "muss schnell gehen", dann ist dir sowieso nicht 
zu helfen.

Ben B. schrieb:
> Game of Life ist doch aber eine 2D-Oberfläche...

Der Bitstrom in die Displays ist allerdings 1D. Die 2D Matrix wird ja 
umgerechnet in diesen Bitstrom der MAX7219 füttert und die sind alle in 
Reihe verkettet.

Nick M. schrieb:

> Na, dann halt nicht!
> Wirst schon selber rausfinden. Irgendwie.

Mimimimii.... wer wird denn gleich weinen?

Eine Periode ist eine Reihe von Zahlen, die sich periodisch wiederholt. 
Sowohl die Länge als auch der Inhalt sind undefiniert. Sie lassen sich 
aber hier auf 2 bis 5 eingrenzen und die Inhalte liegen zwischen 0 und 
2^32.

Vielleicht gibt es ja mathematische Verfahren sowas zu lösen ohne 
1000Mal durch den Array zu kurven. Triviale Lösung wäre sich 2,3,4,5 
aufeinander folgende Zahlen zu schnappen und diese dann per Maske 
schrittweise gegen alle weiteren Elemente zu vergleichen. Kostet irre 
Rechenzeit.

Irgendjemand hat sowas sicher schon gemacht.  Sogar nur digitale Werte 
ohne "Rauschen".

Ben B. schrieb:
> Noch eine Möglichkeit wenn alle wichtigen möglichen Perioden bekannt und
> nicht so viele sind wäre, das Array gezielt nach diesen abzusuchen.
> Quasi einen String in dem Array finden.

Der eigentliche Bitstream hat keinen logischen Zusammenhang. Es sind 
sture Bitmuster mit Steuercodes vorne, die erst die Adresse des MAX7219 
angeben, daher 8x8 Bytes als Muster. Aber auch diese sind vergleichbar, 
jedes 2D Muster hat genau einen Bitstream. Dieser Bitstream ist in 32Bit 
Vars organisiert, da ich die interne CRC32 benutze im Int, der das 
Display bedient. Während des Raushämmerns über die SPI wird gleich die 
CRC32 gebildet.

Jedes Muster auf dem 24x32 Feld entspricht genau einem 32 Bit Wert. 
Diese werden in einem Array abgelegt. 15 Stück, da ich denke, dass man 
die braucht.

Ich spiele schon länger damit herum und habe festgestellt, dass es nach 
zig Tagen Laufen immer wieder Muster gibt, die ich nicht erkenne als 
"endgültig", zb große pulsierende Sterne. Dazu habe ich das ohne Display 
mit maximaler Speed laufen lassen im debugger. Locker 1000 
Generationen/Sekunden sind drin. Nur auf dem STm32 Board ohne was drum 
herum.

Mein Zufall ist echt, ich nutze einen LDR mit um den Seed zu setzen, 
zusätzlich zur RTC 32 Bit. Gleiter und Raumschiffe werden nicht erkannt 
aber dafür habe ich schon was anderes gefunden, die haben nämlich nahezu 
konstante Anzahl Zellen.

Ben B. schrieb:
> 1000 Generationen/s sind aber deutlich mehr als 50, für Deine 20ms.

In der Simulation, nicht im Demo-Mode an der Wand. In der Simu läuft nur 
der reine Zell Automat, damit ich möglichst schnell sehen kann wohin der 
Hase läuft. Dazu brauche ich keine spi bedienen, maximale Geschwindgkeit 
ohne jedes Delay fahren. Das geht fix bei einem stm32 mit 72 Mhz Clock.

Yalu X. schrieb:
> Das sind 4·n-14 Vergleiche (n ist die Länge des Arrays).

Ja.... ok, dachte vielleicht es gibt da kluge Verfahren für sowas. 
Stures Vergleichen ist nicht gerade das Ei des Kolumbus und etwas 
größere Zahlen und Arrays und schon potenziert sich das.

Ich kann mir also die 2,3,4,5 ersten Elemente einfach rausholen und per 
memcmp vergleichen mit dem Rest, der schrittweise durchlaufen wird, 
immer ein Byte vorsetzen auf den Ringpuffer angewendet.  Dazu einen 
eigenen Zeiger definieren, der unabhängig vom Writze Zeiger des INTs 
ist.

Kriegen wir hin....

ben eater hat doch vor urzeiten mal diese hübsche CRC berechnung in 
hardware ausgeführt (youtube)

n paar XOR gates und ne Hand voll flipflops und fertig.

wenn sich die Muster nun ausreichend vordefinieren lassen,
kannst Du vollständig Analog zu Bens CRC

die hardware die Muster erkenenn lassen,
noch ein detection pin und schwupp sended dein detector ein binäres 
signal an den µC bei Fund eines Musters.

sid schrieb:
> n paar XOR gates und ne Hand voll flipflops und fertig.

Der STM32 hat eine CRC Hardware intern, die das in 2-3 Zyklen
erledigt.... dauert keine paar Mikrosekunden bei mir für das ganze Feld.
Das Polynom ist allerdings fix, mir aber auch egal. XOR taete es auch.

Christian J. schrieb:
> Der STM32 hat eine CRC Einheit intern, die das in 2-3 Zyklen
> erledigt....

jo, aber er braucht ja keinen CRC sondern eine Mustererkennung ;)

Yalu X. schrieb:
> Was potenziert sich da? Der Aufwand ist O(n) (n = Länge des Arrays).
> Besser als O(n) ist auch kein anderes Verfahren, da jedes Arrayelement
> mindestens einmal gelesen werden muss.

Ich widerspreche nicht, da ich weiss, dass Du ziemlich was auf dem 
Kasten hast in Sachen Software :-) Ok, ich baue es so ein......

Ist jetzt noch nicht ganz fertig aber geht das auch noch pfiffiger?
Habe versucht das alles in Schleifen zu erschlagen. 2er bis 5er 
Perioden.
compVal als HilfsVar zunächst mal, kann man auch weglassen.

Habe es im Debug Mode mit "Life View" mehrmals durchlaufen lassen, auf 
2er Perioden reagiert er jedenfalls sofort. Eine 2er wird allerdings 
durch den Vergleich auf 3er auch abgedeckt. D.h auf 2 bräuchte man gar 
nicht zu prüfen, 1,2,1,2,1,2,... wird auch mit Vergleich auf 1,2,1 
abgedeckt.

 Die Switch Case kann man sicherlich noch etwas eleganter formulieren 
aber das später. Da ich lokale Vars auf dem Stack nicht debuggen kann 
sind die erstmal global.

1

/* 15 x 32 Bit Checksummen als aufeinander folgende Abbilder der Matrix */

2

#define CRC32_MAX  15

3

volatile int WP_CRC32Stream = 0;    /* Write Pointer, rolierend, INT gesteuert */

4

volatile uint32_t CRC32Stream[CRC32_MAX+1];

5

6

#define MAX_COMP   5

7

uint32_t compVal[MAX_COMP];

8

9

static

10

int CheckForPeriod()

11

{

12

    int round = 2;

13

    int ptr = 0;

14

15

    while (round <= MAX_COMP) {

16

        /* Erste Werte als Vergleich speichern */

17

        for (int i = 0; i < round; i++)

18

            compVal[i] = CRC32Stream[i];

19

20

        ptr = round + 1;

21

22

        /* Vergleiche die n 32 Bit Werte schrittweise mit dem Rest des Arrays */

23

        _Bool treffer = false;

24

        while (ptr < CRC32_MAX) {

25

26

            switch (round)

27

            {

28

                case 2: if ((compVal[0] == CRC32Stream[ptr]) &&  \

29

                            (compVal[1] == CRC32Stream[ptr + 1]))

30

                            treffer = true;

31

                        break;

32

                case 3: if ((compVal[0] == CRC32Stream[ptr]) &&  \

33

                            (compVal[1] == CRC32Stream[ptr + 1]) && \

34

                            (compVal[2] == CRC32Stream[ptr + 2]))

35

                            treffer = true;

36

                        break;

37

                case 4: if ((compVal[0] == CRC32Stream[ptr]) &&  \

38

                            (compVal[1] == CRC32Stream[ptr + 1]) && \

39

                            (compVal[2] == CRC32Stream[ptr + 2]) && \

40

                            (compVal[3] == CRC32Stream[ptr + 3]))

41

                            treffer = true;

42

                        break;

43

                case 5: if ((compVal[0] == CRC32Stream[ptr]) &&  \

44

                            (compVal[1] == CRC32Stream[ptr + 1]) && \

45

                            (compVal[2] == CRC32Stream[ptr + 2]) && \

46

                            (compVal[3] == CRC32Stream[ptr + 3]) && \

47

                            (compVal[4] == CRC32Stream[ptr + 4]))

48

                            treffer = true;

49

                        break;

50

                default:

51

                        break;

52

            }

53

54

            /* Pointer n Bytes weiter setzen */

55

            ptr = ptr + round;

56

        }

57

58

        round++;

59

    }

60

61

    return 0;

62

}

Yalu X. schrieb:
> Sollte das Verfahren statt bei Index 0 nicht bei Index WP_CRC32Stream,
> d.h. nicht am Anfang des Array, sondern am Anfang des Ringpuffers
> starten?

Ja, so ist das wenn man etwas postet und nachher noch weiter macht. 
Fehler ist korrigiert. Außerdem muss das Feld erst voll sein.

1

 /* Eintragen in BitStream */

2

    CRC32Stream[WP_CRC32Stream] = CRC32Bitstream;

3

    /* Zeiger rolieren */

4

    WP_CRC32Stream = (WP_CRC32Stream + 1) % CRC32_MAX;

5

6

    /* Feld muss voll sein für Auswertung */

7

    if (WP_CRC32Stream == 0)

8

        f_IsFull = true;

9

10

    if (!f_IsFull)

11

        return 0;

Aber wo man anfängt.... es ist egal ob das sofort oder erst später 
erkannt wird, Periode ist Periode und die bleibt so. Nur sind 2er 
Treffer auch zufällig möglich. 3er unwahrscheinlicher und ein 3er deckt 
den 2er mit ab.

Nur mal als Hinweis: Game of Life ist deterministisch - auf einen 
bestimmten State X folgt immer der gleiche State X+1.   D.h., wenn ich 
zwei States gefunden habe, die gleich sind, brauch ich nicht mehr weiter 
zu vergleichen, da sie eh immer die gleichen Folgestates generieren. 
Das Finden eines Zyklus' reduziert sich also auf die Suche, ob der neue 
State schon einmal vorgekommen ist.

foobar schrieb:
> Das Finden eines Zyklus' reduziert sich also auf die Suche, ob der neue
> State schon einmal vorgekommen ist.

Innerhalb welchen Zeitraumes? Bzw Periodenraumes hier... d.h. ich muss 
nur schauen, ob ich bei N States schon einmal meinen gemerkten State 
hatte? Eben weil sich aus einem Muster immer die gleichen Folgemuster 
entwickeln. Ein Muster wird durch eine einzige 32 Bit CRC32 eindeutig 
beschrieben.

Christian J. schrieb:
> Für meine ST32 Bastelei muss ich eine Funktion schreiben, die CRC32
> Perioden erkennt.

CRC32 ? Woher auch immer, Perioden sind Zahlenfolgen.

Der ZIP ZLW Ziv Lemoel Welsh  Algorithmus erkennt, ob eine Bytefolge 
früher schon mal vorlag, man kann einstellen wie viel früher und wie 
lang.

Compress von http://ftp.ntu.edu.tw/pub/cpatch/h/helpdeco/helpdc21.zip 
ist eine kurze Version.

MaWin schrieb:
> RC32 ? Woher auch immer, Perioden sind Zahlenfolgen.

Jedes grafische 24x32 Muster wird bei mir durch einen CRC32 abgelegt, da 
ich nur so feststellen kann, ob es ein Muster schon mal gab.

Dieser Algorithmus funktioniert auch für Binärzahlen? Sieht eher nach 
Text Zippen aus.

>> Das Finden eines Zyklus' reduziert sich also auf die Suche, ob der neue
>> State schon einmal vorgekommen ist.
>
> Innerhalb welchen Zeitraumes? Bzw Periodenraumes hier... d.h. ich muss
> nur schauen, ob ich bei N States schon einmal meinen gemerkten State
> hatte?

Wenn du die letzten N States merkst, kannst du Zyklen bis Länge N 
erkennen.

Christian J. schrieb:
> [...]

> Ein Muster wird durch eine einzige 32 Bit CRC32 eindeutig
> beschrieben.

Soweit ich den Sachverhalt CRC verstanden habe, gilt das nur und hängt 
auch von dem Polynom ab, falls die Menge der Eingangsdaten (bei CRC32) 
kleiner oder gleich 32 Bit sind.

Anders herum. Für 33 Bit Eingangsdatenlänge wird ein CRC32 verschiedene 
Eingangsdaten auf die gleich CRC-Summe abbilden.

Ich hoffe, ich habe nichts übersehen, was meinen Einwand überflüssig 
macht.

Christian J. schrieb:
> Sieht eher nach Text Zippen aus

Text zippen besteht aus der Aufgabe, früher schon mal auftretende 
Bytefolgen schnell erkennen zu können.

Beim GoL sind aber sehr lange Perioden denkbar, über tausende von 
States, eine sichere Erkennung ab wann das Muster wiederholt wird (und 
ab dann das Spiel in eine Periodd läuft) ist also nicht möglich.

MaWin schrieb:
> Beim GoL sind aber sehr lange Perioden denkbar, über tausende von
> States,

Sind sie nicht. Oder nur bei konstruierten Welten. Jede Zufallswelt 
bleibt früher oder später einfach stehen. Blinker und Stilleben. Ich 
habe es nur ganz selten gehabt, dass komplexe Blinker entstehen, die aus 
mehr als 5 Zyklen bestehen. Das Ding läuft Tag und Nacht bei mir, ca 1 x 
Woche entstehen Zustände, die noch nicht erfasst habe.

foobar schrieb:
> Nur mal als Hinweis: Game of Life ist deterministisch - auf einen
> bestimmten State X folgt immer der gleiche State X+1.

Wollte nochmal Danke sagen für diesen Hinweis! Man muss wirklich keine 
Perioden durchsuchen, da eine einzige Wiederholung schon ausreicht um zu 
erkennen, dass es eine Periode mit ? Zyklen ist. Es kann keine 2 
gleichen Muster beginnend ab Start geben bis Ende. Ich hatte öfter mal 
einen Zustand mit zwei parallel fliegenden Gleitern, der unendlich war 
aber auch die kriege ich mit einer 100er Histrory erfasst, da das Feld 
ja "rund" ist, was obenr raus fliegt, fliegt unten wieder rein.

Schaue mir das heute abend mal an, nach ner Weile wird man eh etwas 
"gaga" vom Zuschauen ;-)

1

static

2

int CheckForPeriod()

3

{

4

    static int WP_CRC32 = 0;    /* Write Pointer, rolierend, INT gesteuert */

5

  static _Bool f_IsFull = false;

6

7

    /* Aktuelles Muster eintragen in BitStream */

8

    CRC32Stream[WP_CRC32] = CRC32Bitstream;

9

  uint32_t CRC32Now = CRC32Bitstream;

10

11

    /* Zeiger rolieren */

12

    WP_CRC32 = (WP_CRC32 + 1) % CRC32_MAX;

13

14

    /* Feld muss voll sein für Auswertung */

15

    if (WP_CRC32 == 0)

16

        f_IsFull = true;

17

18

    if (!f_IsFull)

19

        return 0;

20

21

  /* Werte vor Write Pointer bis direkt hinter ihm durchsuchen */

22

  int ReadPtr = WP_CRC32;

23

  do {

24

    /* Read Pointer auf nächstes Element */

25

    ReadPtr = (ReadPtr + 1) % CRC32_MAX;

26

    if (CRC32Now == CRC32Stream[ReadPtr])

27

      /* Muster schon vorgekommen! */

28

      return 1;

29

  } while (ReadPtr != WP_CRC32); /* RP holt WP ein */

30

31

    return 0;

32

}

Christian J. schrieb:
> Sind sie nicht

Doch.

Allerdings muss ich einschränken: nur in Toruswelten, wo also links und 
rechts, oben und unten verbunden sind. Aber das halte ich für die 
normale GoL Welt.

Es gibt Gleiter, die fliegen endlos wenn sie mit nicht mit was anderem 
kollidieren, Periodenlänge abhängig von Brettgrösse. Davon mehrere 
unterschiedlich fliegende nicht kollidierende, und der Zyklus ist das 
KGV davon.

MaWin schrieb:
> Allerdings muss ich einschränken: nur in Toruswelten, wo also links und
> rechts, oben und unten verbunden sind. Aber das halte ich für die
> normale GoL Welt.

Ist bei mir auch so und ja, wenn ich 2 davon habe fliegen die auch 
endlos über das 32x24 Feld. Bzw bei STM32409 Disco Board mit seinen 
640px noch weiter, da kann es ewig dauernd bis 3 zusammen stossen. Somit 
wäre das richtig. Aber den Zustand erkenne ich schnell über die 
Zellzahl, da diese sich dann innerhalb fester Differenzen bewegt.

PS: Habe hier grad ein recht komplexes Muster, was sich aber laufend in 
mehr als 50 Zyklen wiederholt.... faszinierend :-)

Christian J. schrieb:

> Sind sie nicht. Oder nur bei konstruierten Welten. Jede Zufallswelt
> bleibt früher oder später einfach stehen.

Der Witz am Zufall ist ja gerade, dass er auch so extrem 
Unwahrscheinliches wie eine "konstruierte" Welt erschaffen kann. Er muss 
nur oft genug die Chance haben, wirksam zu werden.

Ich persönlich finde übrigens diese konstruierten Welten mit ihren 
Zyklen einigermaßen langweilig.

Wenn ich nach irgendwas suchen würde, wären das zufallsgenerierte 
Welten, die eine möglichst lange Phase "Chaos" haben, bevor sie in 
Statik oder einem Zyklus enden. Das sind für mich die spannendsten 
Welten. Vermutlich hat auch der TO genau dieses Ziel.

Er wird aber wahrscheinlich daran scheitern. Ein statistische Analyse 
zeigt, warum. Am besten fängt man mit sehr kleinen Toroiden an, da die 
Sache dann noch einfach beherschbar ist und der volle Suchraum 
durchexerziert werden kann. Bei schrittweiser Vergrößerung des Toroiden 
und Auswertung der jeweiligen Ergebnisse erkennt man dann schnell, wohin 
der Hase läuft...

OK, die dabei empirisch ermittelte "Gesetzmäßigkeit" ist mathematisch 
gesehen natürlich noch kein Beweis dafür, dass das bis zur unendlichen 
Ausdehnung der Toroide so weitergeht...

> static int CheckForPeriod()
> ...

Ich denke, deine Routine ist .. verbesserungswürdig ;-)  Findet wohl 
immer den gerade neu eingetragenen State; das isFull erscheint mir 
unnötig (bei Programmstart wird ne CRC von 0 als Zyklus erkannt - who 
cares); den neuen State muß man nur eintragen, wenn er noch nicht drin 
ist; globale Variable als versteckter Funktionsparameter; ...

Btw, ich bin kein Fan von vielen Großbuchstaben in Identifiern, erst 
recht bei lokalen Variablen.  Insb sind komplett großgeschriebene 
immer defines.

1

#define MAX_CYCLE_LEN    16

2

3

/*

4

 * Add new state to history.  Returns true if 'state' really is new.

5

 */

6

7

static int

8

new_state(uint32_t state)

9

{

10

    static uint32_t history[MAX_CYCLE_LEN];

11

    static unsigned wp;

12

13

    for (unsigned i = 0; i < MAX_CYCLE_LEN; ++i)

14

        if (history[i] == state)

15

            return 0;  // not new - start of a cycle

16

17

    history[wp++] = state;

18

    wp %= MAX_CYCLE_LEN;

19

    return 1;

20

}

foobar schrieb:
> Ich denke, deine Routine ist .. verbesserungswürdig ;-)

Yupp! Deswegen habe ich mir das auch grad nochmal vorgenommen, eh 
besch.. Wetter draussen. Leider ist es so, dass sich CRC32 wiederholen. 
Nicht oft aber eben doch. Erst wenn man 3 Treffer als erfüllte Bed. 
einstuft passt es.

c-hater schrieb:
> Wenn ich nach irgendwas suchen würde, wären das zufallsgenerierte
> Welten, die eine möglichst lange Phase "Chaos" haben, bevor sie in
> Statik oder einem Zyklus enden.

Das geht leider nur mit dem STm32F4xxx, da dieser einen Zufall hat, der 
von einer Rauschdiode erzeugt wird und zudem auch für Sicherheitssysteme 
geeignet ist. Was ich mache ist immer die gleiche Chose, die exakt so 
abläuft wie der Startwert es vorgibt.

Andere lösen Kreuzworträtsel oder gehen auf FFF Demos, mir ist das hier 
lieber...