+ All Categories
Home > Documents > Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und...

Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und...

Date post: 06-Apr-2015
Category:
Upload: hrodulf-westheimer
View: 108 times
Download: 1 times
Share this document with a friend
50
Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27. November 2014
Transcript
Page 1: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Einführung in die Informationsverarbeitung Teil Thaller

Stunde IV: Simulationen von Verhalten und Systemen

Manfred Thaller, Universität zu Köln

Köln 27. November 2014

Page 2: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

I. Grundgedanke

2

(1) Ein Satz von Variablen gibt einen bestimmten Zustand wieder.

(2) Dieser Zustand wird regelbasiert verändert, wobei eine bestimmte Anzahl von Veränderungen einen „Schritt“, also ein Stadium in der Entwicklung eines Systems wiedergibt.

(3) Dieser Zustand kann in regelmäßigen Abständen visualisiert werden.

Page 3: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel: Towers of Hanoi

stack turm1, turm2, turm3;Ausgangszustand: Alle 3 Scheiben auf turm1;Dann: transport(3, turm1, turm2, turm3);

function transport( int n, stack spindel1, stack spindel2, stack spindel3) { if (n >1) transport(n-1,spindel1,spindel3,spindel2); schritt(spindel1,spindel); if (n>1) transport(n-1,spindel3,turm2,spindel1); }

function schritt( stack spindel1, stack spindel2) { spindel2.push(spindel1.pop()); visualisiere(); }

3

Page 4: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Turm1:

Turm2:

Turm3:

Ausgangszustand der Variablen

Scheibe 1 Scheibe 2 Scheibe 3

4

Page 5: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

visualisiere();

5

Page 6: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Turm1:

Turm2:

Turm3:

Ausgangszustand der Variablen

Scheibe 1 Scheibe 2 Scheibe 3

6

Scheibe 4

Page 7: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

visualisiere();

7

Page 8: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Bewegung und Wachstum

Ausgangszustand:Position =2; Durchmesser=1; Schritt:Position=Position+1:Durchmesser=Durchmesser+Durchmesser *0.20;

1 2 3 4 5 6 7 8 9 10 11 12 138

Page 9: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Bewegung und Wachstum

Position =2; Durchmesser=1;

1 2 3 4 5 6 7 8 9 10 11 12 139

Page 10: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Bewegung und Wachstum

Position =3; Durchmesser=1.20;

1 2 3 4 5 6 7 8 9 10 11 12 1310

Page 11: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Bewegung und Wachstum

Position =4; Durchmesser=1.44;

1 2 3 4 5 6 7 8 9 10 11 12 1311

Page 12: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Bewegung und Wachstum

Position =5; Durchmesser=1.728;

1 2 3 4 5 6 7 8 9 10 11 12 1312

Page 13: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel Second Life: Body I

13

Page 14: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel Second Life: Body II

14

Page 15: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel Second Life: II

15

Page 16: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Exkurs: Logik der Computergraphik

Trennung zwischen Graphic Primitives und Graphic Context.

Graphic Primitives: • Draw line.• Draw circle.• Draw text.• Fill area.• [ 3D equivalents. ]

16

Page 17: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Exkurs: Logik der Computergraphik

Trennung zwischen Graphic Primitives und Graphic Context.

Graphic Context: • Set line thickness.• Set line type.• Set line color.• Set fill color.• Set text font.• ………

17

Page 18: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Exkurs: Logik der Computergraphik

Trennung zwischen Graphic Primitives und Graphic Context.

Die Ausführung identischer Zeicheninstruktionen in geändertem Kontext führt zu unterschiedlichem Aussehen.

Aufrufen derselben Primitives mit unterschiedlichen Parametern wie Position und Durchmesser führt zu unterschiedlicher Zeichnung.

18

Page 19: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel Second Life: Nose

19

Page 20: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Abbildung von Inhalten

Vicky A. Walsh: Computer Simulation for Archaeology,In: R.W.Bailey, Computing in the Humanities, North-Holland, 1982, pp. 163-174.

Idee: Simulation des Wachstums eines neolithischen Dorfes.

Fragestellung: Liegen die ausgegrabenen Häuser dort, wo sie vorhergesagt werden?

20

Page 21: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Abbildung von Inhalten

Gelände: Eine Matrix. Feldeigenschaften

Bevölkerung im Haus: n

Gelände

Wasser

Holz

Felsen

Haus

21

Page 22: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Generationen

Errechne pro Generation für jedes Haus Bevölkerungszuwachs „zufällig“ in vorgegebenem Grenzbereich.

Wenn Bevölkerung eines Hauses größer als m wird, baue neues Haus.

So, dass:-Abstand zu Wasser gering,-Abstand zu Holz gering,-Abstand zu ursprünglichem Haus nahe an „zufälligem“ Zielwert. 22

Page 23: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Abbildung von Inhalten

Gelände: Eine Matrix. Feldeigenschaften

Bevölkerung im Haus: n

Gelände

Wasser

Holz

Felsen

Haus

23

Page 24: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Sinn

Wenn Befund im Gelände dem Ergebnis der Simulation entspricht, wurde der Prozess, der zur Wahl der Siedlungsplätze führte, richtig verstanden.

24

Page 25: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

… 20 Jahre später

25

Page 26: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Zufall

Algorithmen sind deterministisch.

Das macht Spiele vorhersehbar und langweilig; Simulationen zu mechanistisch.

Lösung: „Zufallsgenerator“.

26

Page 27: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Zufall

Definition: Ein mathematisches Verfahren, dass bei n hintereinander erfolgenden Aufrufen n Zahlen in einem Bereich (Min, Max) so errechnet, dass sie zwischen Max und Min mit der Häufigkeit einer bestimmten statistischen Verteilung auftreten.

Oft:Minimum = 0; Maximum = 232 - 1 Verteilung: Gleichverteilung

27

Page 28: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Zufall

Paradoxon: Der die „Zufalls“zahlen generierende Algorithmus ist selbst deterministisch.

Lösung: Variabler Startwert, der von einer mit dem Zweck des Programms unabhängigen und nicht vorhersehbaren Umweltbedingung abhängt.

28

Page 29: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel

Ein Bogenschütze soll mit 33 % seiner Schüsse treffen.

Vor jedem Schuss wird eine Zufallszahl von 1 bis 100 gewählt.

Ist sie 33 oder kleiner, trifft der Bogenschütze; sonst geht der Schuss vorbei.

29

Page 30: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Zweck von Simulationen

Simulationen müssen nicht unmittelbar mit Visualisierungen verbunden werden.

Sie können auch dazu dienen, die Performanz von Systemen mit bestimmten Eigenschaften zu testen.

30

Page 31: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Simulationen Emulationen

Simulationen von Rechnersystemen auf Rechnersystemen: „Emulationen“.

• Smartphone Programmierung• Langzeitarchivierung

31

Page 32: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel: Aufzucht von Trollen

Annahme: Ein Troll lebt in einer n x n Welt.

32

Page 33: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel: Aufzucht von Trollen

Diese enthält:

Schafe.

Schmackhaft und für das Überleben des Trolls notwendig.

33

Page 34: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel: Aufzucht von Trollen

Diese enthält:

Ritter.

Aggressiv, gefährlich, aber sterblich.

34

Page 35: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel: Aufzucht von Trollen

Diese enthält:

Türme.

Stationär, gefährlich, nicht bekämpfbar.

35

Page 36: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel: Aufzucht von Trollen

Diese enthält:

Refugien.

Sicherer Aufenthalt. Trolle „heilen“.

36

Page 37: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Beispiel: Aufzucht von Trollen

Diese enthält:

Fallen.

•Sehen aus wie Refugien.•„Fesseln“ den Troll für eine gewisse Zeit.•Machen ihn verwundbarer. 37

Page 38: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Test eines Trolls:

•Einzelner Troll wird in Welt „geboren“.•Er muss 500 „Züge“ überleben.•Bei jedem Zug wird seine Reaktion durch seine „Gene“ gesteuert.•Am Ende wird der Erfolg seines Lebens bewertet:

double Troll::GetEvaluation() { double score = 8.0 * KnightsKilled + 10.0 * SheepEaten + 1.5 * TurnsSurvived – 1.0 * TurnsCaptive – 2.5 * DamageTaken; return score; } 38

Page 39: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Test eines Trolls: „Gene“.

Beispiel: Ein Troll steht genau zwischen einem Ritter, einem Schaf und einem Refugium.

Er habe drei Gene:{Sicherheitsstreben, Hunger, Aggressivität}

Der Troll { 1.0, 0.5, 0.5} läuft ins Refugium.

Der Troll { 0.5, 1.0, 0.5 } frisst das Schaf.

Der Troll { 0.5, 0.5, 1.0 } attackiert den Ritter.39

Page 40: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Tatsächliche Gene

1. "Hunger“ oder: Zuneigung zu Schafen.

2. "Aggressivität“ oder: Abneigung gegen Ritter.

3. "Gesundheit“ oder: Geschwindigkeit der Heilung.

4. "Fluchtbereitschaft“ oder: Misstrauen gegen potentielle Gefahren.

5. "Neugier“ oder: Bereitschaft, in neue Teile des Spielfeldes zu ziehen, auch wenn kein unmittelbarer Anreiz in unmittelbarer Umgebung ist. 40

Page 41: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Testanordnung

1. Am Anfang werden 100 Trolle, anfänglich mit vorgegebenen „Genen“, in 100 unterschiedlichen Welten ausgesetzt.

2. Diese Welten repräsentieren unterschiedliche Umwelttypen: „schafreich“, „ritterreich“, „bevölkerungsarm“.

3. Am Ende wird der „Lebenserfolg“ jedes Trolls gemessen.

4. Und die überlebenden Trolle zeugen eine neue Generation von 100 weiteren Trollen …

5. … die bei Schritt 1 fortsetzen.41

Page 42: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Die Partnerwahl des Trolls

•Top 20 Clonen. (= 20 junge Trolle) •Das erfolgreichste Drittel paart sich. Je erfolgreicher ein Troll, desto öfter paart er sich. (= 70 junge Trolle) •Einige wenige neu (mit Zufallsgenen) erzeugen. (= 10 junge Trolle)

42

Page 43: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Wie paaren sich Trolle?

Troll-Elter 1: { 1.0, 0.8, 0.8, 0.2, 1.0 }

Troll-Elter 2: { 0.8, 0.6, 0.8, 0.4, 0.9 }

Troll- Kind: { 0.9, 0.7, 0.8, 0.3, 0.95 }

43

Page 44: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

… oder auch so …:

Troll-Elter 1: { 1.0, 0.8, 0.8, 0.2, 1.0 }

Troll-Elter 2: { 0.8, 0.6, 0.8, 0.4, 0.9 }

Troll- Kind: { 1.0, 0.6, 0.8, 0.4, 1.0 }

44

Page 45: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Wozu macht man sowas?

Es ist auf andere Weise kaum feststellbar, welche Eigenschaften einen Troll in einem Spiel zu einem Gegner mit wechselnden, aber in etwa vorhersehbaren Eigenschaften machen. (Spielgrad für einen Ritter „leicht“, „mittel“, „schwierig“).

Das Prinzip hat zahlreiche Anwendungen außerhalb der Spieleentwicklung.

45

Page 46: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Wozu macht man sowas?

Ingenieurwissenschaften: Testen des Verhaltens von komplexen technischen Komponenten.

Biowissenschaften: Testen von Annahmen über genetische Gesetzmäßigkeiten / Interaktionen zwischen vererbten Eigenschaften und der Umwelt / Reaktion auf Umweltveränderungen.

Geistes- / Kulturwissenschaften: Sind wir in der Lage Entwicklungsprozesse zu modellieren, haben wir sie verstanden.

46

Page 47: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Wozu macht man sowas?

Interaktive Medien: Schaffung künstlicher Umwelten mit „künstlichen Individuen“ vorhersagbarer Eigenschaften.

47

Page 48: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Back to reality

„Genetische Algorithmen“ haben gezeigt dass die Rolle von Mutationen in der Evolution erheblich überschätzt wurde; „crossover“, i.e., die Neukombination von Genen, wahrscheinlich wesentlich einflussreicher.

48

Page 49: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Literatur

Francois Dominic Laramee: "Genetic Algorithms: Evolving the Perfect Troll", in: Steve Rabin (Ed.): AI Game Programming Wisdom,Charles River Media: 2002, p. 629 - 639.

Eberhard Schöneburg et al: Genetische Algorithmen und Evolutionsstrategien, Addison Wesley, 1993.

Randy L. Haupt und Sue E. Haupt: Practical Genetic Algorithms, Wiley & Sons, 2004.

49

Page 50: Einführung in die Informationsverarbeitung Teil Thaller Stunde IV: Simulationen von Verhalten und Systemen Manfred Thaller, Universität zu Köln Köln 27.

Danke für heute!

50


Recommended