Turmiten-Simulator

Martok · Verfasst: Di 07.01.14 20:57

Hallo zusammen,

Auch andere haben hier schon was mit Langton's Ameisen oder allgemeiner Turmiten gemacht. Ich aber auch ;-)

Dieses Programm ist etwas schneller und hält sich wörtlicher an die Regeln wie sie in der Wikipedia stehen ("Drehen, Farbe wechseln, Gehen").

Es ist grundsätzlich mehr darauf ausgelegt, systematisch durch die Regeln durchzurennen. Es lassen sich automatisch Regeln einer bestimmten Länge auswürfeln und abspeichern. Die Bedienung ist dabei mit den F-Tasten möglich, so dass man schnell viele durchklicken kann.
Es wird eine History mitgeführt, so dass man zurückspringen kann wenn man sich im Eifer des Gefechts verklickt hat.

Die Darstellung lässt sich zwischen Farbig und Graustufen umschalten - in Monochrom sieht man besser was die Ameise tut, in farbig sieht man Unterschiede besser. "Unscaled" bedeutet, dass die Ansicht nicht verdoppelt wird. Die Brettgröße ist (noch) fix auf 513x513 Felder festgelegt, kann aber im Code angepasst werden.

Achso, und das Programm bezeichnet grundsätzlich die Regeln in HHP-Code:

Mathematiker hat folgendes geschrieben :

An Stelle des Regelstrings könnte man auch die Regeln durchnummerieren. Setzen wir ein nicht(!) auszuführendes R = 1 an den Anfang des Strings, so braucht man auch keine Stringlänge mehr anzugeben.
Aus LRRLLLRR wird dann RLRRLLLRR = Regel 355 und entsprechend die anderen. Ab Regel LL = 4 wären dann jeder natürlichen Zahl genau eine Regel zugeordnet.

Screenshot (png, 93 KB)
Downloads sind hier im Anhang und der aktuelle Code ist bei Github

Viel Spaß beim Spielen

Rev 02: Pause-Funktion, Fehlerbehandlung für zu kurze Regeln, Programmicon
Rev 03: Regeln eingeben nach einer zu kurzen

Einloggen, um Attachments anzusehen!

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Mathematiker · Verfasst: Di 07.01.14 21:08

Hallo,

Martok hat folgendes geschrieben :

Dieses Programm ist etwas schneller und mehr darauf ausgelegt, systematisch durch die Regeln durchzurennen.

Sehr schön und richtig schnell, mehr als doppelt so schnell wie mein Versuch.
Die Idee, automatisch zu stoppen, wenn der Rand erreicht ist, ist ebenfalls sehr gut. Diese Idee werde ich "rauben". :wink:

Martok hat folgendes geschrieben :

Die Darstellung lässt sich zwischen Farbig und Graustufen umschalten - in Monochrom sieht man besser was die Ameise tut, in farbig sieht man Unterschiede besser.

Die Graustufenbilder sind reizvoll, da sonst die vielen Farben etwas ablenken.

Martok hat folgendes geschrieben :

Achso, und das Programm bezeichnet grundsätzlich die Regeln in HHP-Code:

Warte noch ein paar Monate, dann ist der HHP-Code weltweit bekannt. :!:

Vielleicht winkt uns ja ein Preis.
Die Fields-Medaille für Dich (ich bin zu alt). Ich nehme den Abel-Preis (gibt mehr Geld :mrgreen:

). Und für Horst_H findet sich auch noch etwas. :wink:

Beste Grüße
Mathematiker

Nachtrag: Der HHP-Code bei Wikipedia ist Geschichte. :cry:

Ich wusste, dass 2014 nichts Gutes bringt.

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Delphi-Laie · Verfasst: Di 07.01.14 22:14

Bei Enter Rule -> Enter HHP werden ungültige Eingaben nicht abgefangen. Bei kleinen Zahlen erfolgt die Meldungsbox "Division durch 0", ggf. sogar unnählige Male (bei Eingabe 0).

Kann man die Berechnungen nicht abbrechen?

Martok · Verfasst: Mi 08.01.14 18:55

Delphi-Laie hat folgendes geschrieben :

Bei Enter Rule -> Enter HHP werden ungültige Eingaben nicht abgefangen. Bei kleinen Zahlen erfolgt die Meldungsbox "Division durch 0", ggf. sogar unnählige Male (bei Eingabe 0).

Ist behoben.

Delphi-Laie hat folgendes geschrieben :

Kann man die Berechnungen nicht abbrechen?

Jetzt schon

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Horst_H · Verfasst: Mi 08.01.14 18:59

Hallo,

langtons Ant Revision 11 stoppte auch am Rand und erzeugte doch auch automatisch alle Regeln und speicherte diese als gif-Datei.
Haben wir damals die Regeln falsch umgesetzt oder war die Farbwahl unabhängig von der Bewegungsrichtung?
Wenn ich auch 5e5 als Aktualisierungsintervall wähle, komme ich oft auf 40 Mio Berechnungen pro Sekunde.
Aber Rule "LRRR" HPP Code 23 sieht langsamer sehr nett aus, aber bei Martok völlig anders :-(

Gruß Horst
P.S
Ich schaue mir morgen mal die neue Version an..

Martok · Verfasst: Mi 08.01.14 19:12

Horst_H hat folgendes geschrieben :

Haben wir damals die Regeln falsch umgesetzt oder war die Farbwahl unabhängig von der Bewegungsrichtung?

Leider ja

Laut Wikipedia sollte das "Drehen, Farbe wechseln, Gehen" werden, die Ameise machte aber "Farbe wechseln, Drehen, Gehen". Da kommen dann auch nicht die gleichen Bilder raus wie in der WP.

Mathematiker hat folgendes geschrieben :

Die Graustufenbilder sind reizvoll, da sonst die vielen Farben etwas ablenken.

Nicht meine Idee, schreibt Wolfram aber in den Notes zu NKS. Die Argumentation klingt plausibel, deswegen hab ich das mal eingebaut.

Mathematiker hat folgendes geschrieben :

Nachtrag: Der HHP-Code bei Wikipedia ist Geschichte. :cry:

Ich wusste, dass 2014 nichts Gutes bringt.

Och menno, dann wirds ja doch nichts mit den Preisen.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Delphi-Laie · Verfasst: Mi 08.01.14 19:17

Tut mir leid, aber ich kann weder eine Abbrechenbarkeit feststellen noch wird z.B. bei Eingabe des HHP-Parameters 0 die Fehlermeldung unterdrückt.

Martok · Verfasst: Mi 08.01.14 19:32

Delphi-Laie hat folgendes geschrieben :

Tut mir leid, aber ich kann weder eine Abbrechenbarkeit feststellen

Generations->"Pause"

Delphi-Laie hat folgendes geschrieben :

bei Eingabe des HHP-Parameters 0 die Fehlermeldung unterdrückt.

Unterdrückt nicht, aber du bekommst jetzt eine richtige Fehlermeldung. War allerdings noch ein Fehler bei der nächsten Eingabe, der ist in Rev03 behoben.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Mathematiker · Verfasst: Mi 08.01.14 21:02

Hallo Horst_H,

Horst_H hat folgendes geschrieben :

Haben wir damals die Regeln falsch umgesetzt oder war die Farbwahl unabhängig von der Bewegungsrichtung? ... Aber Rule "LRRR" HPP Code 23 sieht langsamer sehr nett aus, aber bei Martok völlig anders :-(

Das ist alles kein Problem. Da wir die Reihenfolge der Abarbeitungsschritte etwas anders haben, müssen wir nur vor der Schleife den hintersten Buchstaben unserer Regel nach vorn kopieren, d.h. aus LRRR wird einfach RLRR.
Dann erhalten wir die gleichen Bilder.

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Horst_H · Verfasst: Mi 15.01.14 10:52

Hallo,

Der Reiz von user profile icon

Martoks Lösung ist ja in der Verwendung eines Palettenimages begründet, sodass man nicht zwei sehr große Felder beackern muss.Wohl auch in der Hoffnung, dass dies wesentliche Geschwindigkeitsvorteile bringt, weil es mehr im Level II Cache zu liegen kommt.Es liegt aber in der Art der Bewegung der Ameise, dass sie sich von Schritt zu Schritt in der "Nähe" aufhält und nur diese vielen IFs es langsamer machen. Eine falsche Vorhersage kostet beim AMD Phenom ja 20 Takte.Wenn man also schnell rechnen will geht es ohne die Beachtung von linker oder rechter Grenze am besten.
Oben und unten muss man beachten, damit man im Bild bleibt.
Also Zylinder statt Torus wäre ein guter Kompromiss für hohe Geschwindigkeit.
Dann kann man statt Zeile,Spalte ( y,x) einen einzelnen Wert zeile*Breite+Spalte nutzen.
Mit Torus und nur einer Ameise erreiche ich unter Delphi7 127 Mio Ber/s ~ 25 CPU-Takte pro Bildpunkt ( Lazarus 1.0.14, 31 CPU-Takte ) mit Ausgabe des Bildes alle 50 Mio Berechnungen. Das ist nicht allzu übel.
Natürlich ist user profile icon

Martoks Programm streng in kleine Häppchen aufgeteilt, aber wenn man viele Bilder betrachten will und alle 60 Sekunden gewechselt werde soll, wäre es doch schön, wenn man in 12 Sekunden damit schon durch wäre. ( HHP-CODE 76 bei Martok , 70 bei Langton )
LangtosAnt

Gruß Horst
Dummerweise habe ich jetzt einen Zugriffsfehler bei Abbruch eingebaut :-(

Einloggen, um Attachments anzusehen!

Martok · Verfasst: Mi 15.01.14 19:44

Horst_H hat folgendes geschrieben :

Der Reiz von user profile icon

Martoks Lösung ist ja in der Verwendung eines Palettenimages begründet, sodass man nicht zwei sehr große Felder beackern muss.

Genau, wenn Windows mir das Umkopieren abnehmen kann, darf es das gerne tun ;-)

Cache-Optimierung war da keine drin (genau genommen war es bis eben komplett unoptimiert). Da hast du natürlich recht, direktes Indizieren ist nochmal einen Zacken schneller als immerhin die Abkürzung durch die Scanlines zu nehmen. Da müsste man dann aber nochmal scharf über TopDown/BottomUp-Bitmaps nachdenken, sonst steht das alles nochmal auf dem Kopf...

Horst_H hat folgendes geschrieben :

Mit Torus und nur einer Ameise erreiche ich unter Delphi7 127 Mio Ber/s ~ 25 CPU-Takte pro Bildpunkt ( Lazarus 1.0.14, 31 CPU-Takte ) mit Ausgabe des Bildes alle 50 Mio Berechnungen. Das ist nicht allzu übel.

"Nicht allzu übel" ist gut. Mit einigen Optimierungen hab ich es jetzt auf um die 20M/s bei Ausgabe alle 50M geschafft (das ist Faktor 4 auf dieser Maschine gewesen). An der Stelle bremsen laut CodeAnalyst fast nur noch Speicherzugriffe in das Bitmap.

Horst_H hat folgendes geschrieben :

Natürlich ist user profile icon

Martoks Programm streng in kleine Häppchen aufgeteilt

Sorry, aber ich versteh grad nicht worauf du dich beziehst...

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Horst_H · Verfasst: Mi 15.01.14 20:43

Hallo,

Zitat:

Horst_H hat folgendes geschrieben :
Natürlich ist Martoks Programm streng in kleine Häppchen aufgeteilt

Sorry, aber ich versteh grad nicht worauf du dich beziehst...

Beim Programm Ameise ist alles in eine einzige Schleife gequetscht.Wenn ich vorher weiß. ich will einen Zylinder ( hätte ich in Rev12 ändern sollen ), kann ich ja die ständige Abfrage in TAnt.Run aWorld.WrapCoords(X,Y); entsprechend eingefügt um die ganzen Abfragen zu sparen.
Sprich ich hätte Ant.run die Anzahl der Schritte und ob ich Torus oder Rechteckfläche haben will übergeben und
als Rückgebewert, die tatsächlich erreichten Schritte.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

function TAnt.Run(const aWorld: TAntWorld;MaxDurchLaeufe: integer;torus:Boolean):integer;
IF Torus then
   result := TAnt.RunTorus(const aWorld: TAntWorld;MaxDurchLaeufe: integer)
else
  result := TAnt.RunRects(const aWorld: TAntWorld;MaxDurchLaeufe: integer)
end;

das

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

 
next:= curr+1;
IF next >= RuleLength
   dec(next, RuleLength);// alternativ next  := 0;
//Habe ich durch einen Feldzugriff ersetzt, denn jede falsche Vorhersage ist enorm teuer, zumal bei diesen kurzen Längen
vorab:
    for i:=0 to Laenge-2 do
      NeuL[i]:=i+1;
    NeuL[Laenge-1] := 0;
in der funktion
 next := NeuL[curr];

aWorld.Field[X,Y]:= next; kostet enorme Zeit, weil auf dynamische Arrays nach einem Call (ein Call 10 CPU Takte weg) zugegriffen wird.
Also Lieber einen Zeiger auf pcurr:= @aWorld.Field[X,Y]; wenn es sowas gibt, dann ist es nur ein Call.
Aber man braucht nur die Adressen der ersten beiden scanline's , dann kann man die anderen aus dem Abstand der Adressen bestimmen.
pCurr := Adresse(scanline0) - Zeile*( Abstand der Adressen scannline(0)..scannline(1))+Spalte;

Aber damit verliert das Programm an Durchsichtigkeit.

Gruß Hrost

Martok · Verfasst: Mi 15.01.14 22:08

Horst_H hat folgendes geschrieben :

Beim Programm Ameise ist alles in eine einzige Schleife gequetscht.Wenn ich vorher weiß. ich will einen Zylinder ( hätte ich in Rev12 ändern sollen ), kann ich ja die ständige Abfrage in TAnt.Run aWorld.WrapCoords(X,Y); entsprechend eingefügt um die ganzen Abfragen zu sparen.

Ah, da hast du Recht.

Horst_H hat folgendes geschrieben :

Habe ich durch einen Feldzugriff ersetzt, denn jede falsche Vorhersage ist enorm teuer, zumal bei diesen kurzen Längen

Bei mir sind das unmessbar wenig Cycles die dort verbracht werden, für die Anzahl müsste ich erstmal in die Doku gucken. Jedenfalls: der Speicherzugriff ist doch extrem viel teurer als ein

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:

uAnt.pas.112: next:= curr+1;
0045EA10 8D4701           lea eax,[edi+$01]
uAnt.pas.113: if next = RuleLength then
0045EA13 3B4314           cmp eax,[ebx+$14]
0045EA16 7502             jnz +$02
uAnt.pas.114: next:= 0;
0045EA18 33C0             xor eax,eax

, schon weil man sich ziemlich sicher sein kann dass die Tabelle nicht in einem Cache liegt?

Zitat:

aWorld.Field[X,Y]:= next; kostet enorme Zeit, weil auf dynamische Arrays nach einem Call (ein Call 10 CPU Takte weg) zugegriffen wird.

Ich würde es ja inlinen, aber D7... ;-)

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Horst_H · Verfasst: Mi 15.01.14 23:08

Hallo,

ich habe Dein Programm etwas modifiziert angehängt.
Du musst auch große "update every" Zahlen nutzen. 10 Mio sollten es sein, sonst kommt da nichts rum, sondern nur knapp 30 Mio/s.
Ich erreiche mit Rule 76 dann um die 68 Mio Berechnungen pro Sekunde.
Ich habe versucht mit Pointern zu arbeiten, aber das funktioniert nicht immer. Ganz merkwürdig, als würden die scanlines verschoben.
Damit erreiche ich bis 91 Mio.
Ich kann dabei aber nicht mit Torus arbeiten, da eine Überlauf des Spaltenwertes X erst noch in der Zeile bleibt, bis die Dword Grenze überschritten ist.
Im Assembler Code stehen wieder diese Dinge Speichere EAX in Mem1 gefolgt von Hole EAX aus Mem1, beim neuen Haswell soll das aber nichts mehr ausmachen ( irgendwo Level0 Cache genannt )

Gruß Horst

Martok · Verfasst: Do 16.01.14 00:15

Dafür funktioniert es nicht mehr, vergleich mal den Output

Und ich hab festgestellt dass das System hier viel langsamer ist. Sind jetzt 25M, also ca 1/4tel mehr. Da muss ich mich nicht über deine Zahlen wundern :lol:

Übrigens warst du etwas früh, mit dem gäbe es eine Stelle wo man an die korrekten Pointer kommt. Bitmaps sind komisch :roll:

Die Lookups die ich mit diesem Commit vor hatte hab ich wieder raus genommen, der Effekt war marginal.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Horst_H · Verfasst: Do 16.01.14 10:17

Hallo,

ich hatte

markieren

Delphi-Quelltext

1:	curr:= aWorld.Field[X,Y];

und nicht

markieren

Delphi-Quelltext

1:	curr := pCurr^;

benutzt. Weil ich die Grenzen falsch abgefragt hatte.Damit war es dann wieder langsam.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

function TAnt.RunTorus(const aWorld: TAntWorld;MaxAnzahlRunden: integer):Integer;
    with deltaJ[Face] do
    begin
      x :=x+dx;
      IF (x<0) OR (X>= col) then // <--- = Vergessen
        break;
      y :=y+dy;
      IF (y<0) OR (y>= row) then // <--- = Vergessen
        break;
      inc(pCurr,dp);
    end;

Ich hänge die neue Version an, die alle 3 Sekunden wechselt und alle 10 Mio ein Refresh macht.
Ein 3.2 Ghz Phenom ist sicher nicht das schnellste.
LangtonsMartokRule355

Gruß Horst
EDIT:
Ich habe den neuen Haswell i3 4330 3.5 Ghz unter Win7 mal das Programm untergejubelt.
Ganz merkwürdiges Verhalten Rule 355 startet mit 35 Mio/s und steigert sich peu a peu auf 117 fällt dann ab auf 40 Mio und beginnt das Spiel von vorn, bleibt aber nach geschätzten 30 Sekunden jetzt bei 105..117 Mio stabil auch bei neuen Werten.
Ist das die Sparoffensive von Intel? Erst mal schauen, ob es länger dauert?.
Unter Win 1.7.9 sind es nur 91 Mio

Einloggen, um Attachments anzusehen!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme