View
221
Download
0
Category
Preview:
Citation preview
Universität zu Köln. Historisch-Kulturwissenschaftliche InformationsverarbeitungJan G. Wieners // jan.wieners@uni-koeln.de
Basisinformationstechnologie IISommersemester 2013
26. Juni 2013 – Digitale Spiele und künstliche Intelligenz (ein kleiner Überblick)
…
Spiel
„Der Form nach betrachtet, kann man das Spiel also zusammenfassend eine freie Handlung nennen, die als „nicht so gemeint“ und außerhalb des gewöhnlichen Lebens stehend empfunden wird und trotzdem den Spieler völlig in Beschlag nehmen kann, an die kein materielles Interesse geknüpft ist und mit der kein Nutzen erworben wird, die sich innerhalb einer eigens bestimmten Zeit und eines eigens bestimmten Raums vollzieht, die nach bestimmten Regeln ordnungsgemäß verläuft und Gemeinschaftsverbände ins Leben ruft, die ihrerseits sich gern mit einem Geheimnis umgeben oder durch Verkleidung als anders von der gewöhnlichen Welt abheben.“
Huizinga: „Homo Ludens“ (1938)
„Der Form nach betrachtet, kann man das Spiel also zusammenfassend eine freie Handlung nennen, die als „nicht so gemeint“ und außerhalb des gewöhnlichen Lebens stehend empfunden wird und trotzdem den Spieler völlig in Beschlag nehmen kann, an die kein materielles Interesse geknüpft ist und mit der kein Nutzen erworben wird, die sich innerhalb einer eigens bestimmten Zeit und eines eigens bestimmten Raums vollzieht, die nach bestimmten Regeln ordnungsgemäß verläuft und Gemeinschaftsverbände ins Leben ruft, die ihrerseits sich gern mit einem Geheimnis umgeben oder durch Verkleidung als anders von der gewöhnlichen Welt abheben.“
Huizinga: „Homo Ludens“ (1938)
Freie Handlung, nicht so gemeint, außerhalb des gewöhnlichen Lebens,kein materielles Interesse, kein Nutzen, eigens bestimmte Zeit und Raum („Magischer
Zirkel“),Gemeinschaftsverbände, Verkleidung
Kongruiert diese Definition mit unserem intuitiv verwendeten
Spielbegriff?
Auf dem Weg zu einer Arbeitsdefinition: Huizinga Caillois Suits Avedon und Sutton-Smith Crawford Kelley Salen und Zimmerman
Juul: „Classic Game Model“ (2005)
„A game is a rule-based system with a variable and quantifiable outcome, where different outcomes are assigned different values, the player exerts effort in order to influence the outcome, the player feels emotionally attached to the outcome, and the consequences of the activity are negotiable.“
Juul: Sechs Eigenschaften von Spiel bzw. Spielen
1. Regeln [Rules]: Spiele verfügen über Regeln.
2. Veränderliches, quantitativ bestimmbares Ergebnis [Variable, Quantifiable Outcome]: Die Spielregeln müssen unterschiedliche Spielresultate / -
Ergebnisse vorsehen. Als „game activity“: Das Spiel muss auf die Spielfertigkeiten der
Spieler eingehen können.
3. Differierende Qualität der Spielergebnisse [Valorization of Outcome]: Manche der möglichen Spielergebnisse sind besser, manche schlechter als andere, d.h. das Spielergebnis ist charakterisiert durch eine Wertigkeit (i.e. die Auszahlung des Spieles).
Juul: „Classic Game Model“
Juul: Sechs Eigenschaften von Spiel bzw. Spielen
4. Spieler / Spielerinnen bemühen sich um das Spielergebnis [Player effort; „Games are challenging“]: Spiele stellen eine Anforderung an Spielerinnen und Spieler.
5. Der Spieler / die Spielerin steht in einem emotionalen Verhältnis zum Spielergebnis [Player attached to outcome]: Gewinner => glücklich, Verlier => unglücklich
6. Das Spiel hat keine unmittelbaren Konsequenzen auf das Leben des Spielers / der Spielerin [negotiable consequences]; die Verknüpfung des Spiels mit Konsequenzen ist optional: Das Spiel ist sich zunächst Selbstzweck.
+ Systemischer Aspekt [Salen und Zimmerman 2004]: „A game is a system in which players engage in an artificial conflict, defined by rules, that result in a quantifiable outcome.“
Juul: „Classic Game Model“
Fokussierungsweisen
Das Spiel als formales System: Regeln, Spielergebnis, Spielziele und -ergebnisse,
Das Verhältnis der Spielerinnen und Spieler zum Spiel: Spieler bemühen sich um das Spielergebnis, emotionales Verhältnis zum Spiel, keine unmittelbaren Konsequenzen auf das Leben der Spieler
Juul: „Classic Game Model“
„Theory of Games and Economic Behavior“ (1944) Spiel („game“): Gesamtheit der Regeln, die das
Spiel beschreiben Spielpartie („play“): Vorgang, in dem das Spiel
gespielt wird Spielzug („move“) Zugwahl („choice“)
Spielregeln determinieren, welche Spielsymbole zu welchem Spielzeitpunkt auf welche Art und Weise bewegt werden dürfen
Spieltheorie nach von Neumann und Morgenstern
Formale Definition: Ein Spiel (Gamma) in Normalform ist vollständig beschrieben durch das Tripel
die finite Anzahl der Spielerinnen und Spieler aus der Spielermenge .
den Strategieraum. Der Strategieraum gibt die Menge aller möglichen Strategiekombinationen aus den Strategien der einzelnen Spieler an, d.h. . Der Strategieraum S ist definiert als kartesisches Produkt der Strategiemengen , wobei eine endliche Menge von Entscheidungen und Aktionen für jeden Spieler in bezeichnet.
die Nutzenfunktionen, wobei die Auszahlungs- oder Nutzenfunktion des Spielers bezeichnet. Wird die Strategiekombination gespielt, so lässt sich mit der Nutzen für Spieler bestimmen.
Spieltheorie nach von Neumann und Morgenstern
Grundfragen: Handeln und Agieren Anzahl der Spielerinnen und Spieler Kommunikation Rationalität Wiederholung
Spieltheorie nach von Neumann und Morgenstern
KIals Entscheidungsfindung
Koch
Bewertet die Köchin positiv () Bewertet die Köchin negativ ()
Köchin
Bewertet den Koch positiv ()Köchin: 50 Euro
Koch: 50 Euro
Köchin: 0 Euro
Koch: 100 Euro
Bewertet den Koch negativ ()Köchin: 100 Euro
Koch: 0 Euro
Köchin: 20 Euro
Koch: 20 Euro
Auszahlungsmatrix des Spieles
Wie würden Sie sich am Ende des Wettbewerbes entscheiden?
Das Gefangenendilemma
Spieler 2
Nicht-Gestehen () Gestehen ()
Spieler 1Nicht-Gestehen () 3,3 7,0
Gestehen () 0,7 5,5
Übung: Spielen Sie das Gefangenendilemma mit Ihrem Sitznachbarn / Ihrer –Nachbarin. Wer gewinnt das Spiel? Und warum?Worin bestünde eine sinnvolle Handlung? Worin besteht das namensgebende Dilemma des Spieles?
Das iterierte Gefangenendilemma
Spieler 2
Nicht-Gestehen () Gestehen ()
Spieler 1Nicht-Gestehen () 3,3 7,0
Gestehen () 0,7 5,5
Würden die Spieler anders entscheiden, wenn das Spiel nicht nur einmal, sondern wiederholt, d.h. in mehreren Runden gespielt würde?
Übung: Spielen Sie das wiederholte Gefangenendilemma mit Ihrem Sitznachbarn / Ihrer –Nachbarin über zehn Runden. Wer gewinnt? Lässt sich eine erfolgreiche Langzeitstrategie identifizieren?
: Kooperiere in jeder Runde des Spiels : Defektiere in jeder Spielrunde : Kooperiere in der ersten Spielrunde und verhalte
Dich anschließend nichtkooperativ : Beginne das Spiel kooperativ und imitiere
anschließend das Verhalten des Gegenspielers
Langzeitstrategien – Beispiele
: Kooperiere in jeder Runde des Spiels : Defektiere in jeder Spielrunde : Kooperiere in der ersten Spielrunde und verhalte
Dich anschließend nichtkooperativ : Beginne das Spiel kooperativ und imitiere
anschließend das Verhalten des Gegenspielers Tit For Tat („Wie Du mir, so ich Dir“) als erfolgreichste Strategie (Wettbewerb 1979, Rapoport / Axelrod)
Langzeitstrategien – Beispiele
Ein Nullsummenspiel: „Matching Pennies“
Spieler 2
Kopf () Zahl ()
Spieler 1Kopf () +1 -1
Zahl () -1 +1
Übung: Spielen Sie das „Matching Pennies“ Spiel über mehrere Spielrunden mit Ihrem Nachbarn. Welche Langzeitstrategie bietet sich in dem Spiel an, um möglichst erfolgreich zu spielen?
Sequentielle Entscheidungen: Spielbäume (Extensivform)
𝑥0𝑠11 𝑠12
𝑥1 𝑥2
𝑥3 𝑥4 𝑥5𝑥6
𝑥7 𝑥8
𝑠21 𝑠22 𝑠21 𝑠22
𝑠11 𝑠12
Perfekte Entscheidungen durch Suchen
Tic Tac Toe
Juul, Jesper: „255,168 ways of playing Tic Tac Toe”http://www.jesperjuul.net/ludologist/255168-ways-of-playing-tic-tac-toe
…ein wenig abstrakter…
𝑥0
𝑥1 𝑥2
𝑥4 𝑥5 𝑥6 𝑥7 𝑥8 𝑥9 𝑥10 𝑥11 𝑥12
𝑥3
3 12 8 2 4 6 14 5 2
𝑠𝑀𝐴𝑋 1 𝑠𝑀𝐴𝑋 2𝑠𝑀𝐴𝑋 3
Welche Strategie sollte die das Spiel beginnende Spielerin (Dreieck) im oben wiedergegebenen Spiel mit zwei Spielrunden verfolgen, um optimal zu agieren und ihre Auszahlung zu maximieren? Wie wird sich wohl der Spieler (Quadrat) verhalten?
Der Minimax-Algorithmus
𝑥0
𝑥1 𝑥2
𝑥4 𝑥5 𝑥6 𝑥7 𝑥8 𝑥9 𝑥10 𝑥11 𝑥12
𝑥3
3 12 8 2 4 6 14 5 2
𝑠𝑀𝐴𝑋 1 𝑠𝑀𝐴𝑋 2𝑠𝑀𝐴𝑋 3
MAX
MIN 3 2 2
3
min(3,12,8)=3
min(2,4,6)=2
max(3,2,2)=3
min(14,5,2)=2
Menschliches Denken Rationales Denken
„[Die Automatisierung von] Aktivitäten, die wir dem menschlichen Denken zuordnen, Aktivitäten wie beispielsweise Entscheidungsfindung, Problemlösung, Lernen..“ (Bellman, 1978)
„Die Studie mentaler Fähigkeiten durch die Nutzung programmiertechnischer Modelle.“(Charniak und McDermott,1985)
Menschliches Handeln Rationales Handeln
„Das Studium des Problems, Computer dazu zu bringen, Dinge zu tun, bei denen ihnen momentan der Mensch noch überlegen ist.“(Rich und Knight, 1991)
„Computerintelligenz ist die Studie des Entwurfs intelligenter Agenten.“(Poole et al., 1998)
Fokussierungsweisen von KI nach Russell / Norvig
Digitale Spiele: Computer- und Videogames
Spiel I
Game Engine (der Motor im Hintergrund der Games)
Kapselt Funktionalität: Grafik-Engine (Rendering & Co., z.B. OGRE) Sound Spielphysik Spielsteuerung Netzwerkanbindung Reaktion auf Eingaben
Game Engines
Wiederverwendbarkeit?
Game engines
[Gregory, J: Game Engine Architecture. 2009]
Most two- and three-dimensional video games: „soft real-time interactive agent-based computer simulations“ [Gregory, J: Game engine Architecture. 2009]
Agentenbasiert: „Ein Agent ist ein System, das sich in einer Umgebung befindet und dazu fähig ist, selbstständig und eigenverantwortlich Handlungen zu vollziehen, um individuell relevante Ziele zu verfolgen und zu erreichen. Seine Umgebung nimmt der Agent wahr über Sensoren; Handlungen in der Umgebung des Agenten vollziehen sich durch Aktuatoren.“
Video Games
Forschungsfragen, eine Auswahl1. (Lassen sich Spiele in einem dedizierten Format (z.B.
XML-basiert) vollständig beschreiben, so dass ein Spieleinterpreter (Software) das Spiel spielen kann?)
2. Wie lassen sich glaubhaft agierende Bots / Agenten implementieren?
3. Wie konstituieren sich perfekte Entscheidungen in klassischen-, Computer- und Videospielen?
4. … ∞
Kontext Digitale Spiele
Ein Ansatz: Domain-specific entertainment languages. U.a.: Game Description Language (GDL) Zillions of Games Ludi Game Description Language UnrealScript GameXML
Spiele beschreiben
Game Description Language(Stanford Logic Group): Prolog-ähnliche Syntax (datalog), fokussiert auf “General Game Playing”
Beispiel TicTacToe:
;; Tictactoe;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Roles;;;;;;;;;;;;;;;;;;;;;;;;;(role x) (role o);;;;;;;;;;;;;;;;;;;;;;;;;;; Initial State;;;;;;;;;;;;;;;;;;;;;;;;;(init (cell 1 1 b)) (init (cell 1 2 b)) (init (cell 1 3 b)) (init (cell 2 1 b)) (init (cell 2 2 b)) […](<= (next (cell ?x ?y ?player)) (does ?player (mark ?x ?y)))(<= (next (cell ?x ?y ?mark)) (true (cell ?x ?y ?mark)) (does ?player (mark ?m ?n))
Spiele beschreiben: GDL
2013 General Game Playing Competition: http://games.stanford.edu/
GDL Competition
Agent
Wegfindung Dijkstra A*
Entscheidungsfindung Zustandsautomaten Verhaltensbäume Fuzzy Logic Markov Systeme
Lernen Bestärkendes Lernen Künstliche Neuronale Netze
Schwarmintelligenz
Agentenbasierte Modellierung(Anforderungen, u.a.):
Spiel I
Agent „Mario“
Agent „Fleischfressende Pflanze“
Agent „Pilz“ Agent „Pilz“
Agent „Schildkröte“
Agent „Wolke“?Agent „Münze“?
Agent „Münze“?
Agent „Kleiner Junge“
Agent „Fiese Möpp“Agent „Fiese Möpp“
Agenten?
Uninformierte Suche: Wegfindung
In Aktion („Command and Conquer“, HTML5):http://www.adityaravishankar.com/projects/games/pathfinding-javascript-rts-demo/
Ein Beispiel: Wiederverwendbares Verhalten
(vgl. Prof. Thaller: „Re-usable Content in 3D und Simulationssystemen”, www.hki.uni-koeln.de/display_course/232)
Welches Verfahren lässt sich dem Roboter / Agenten einpflanzen, damit er definitiv sein Ziel erreicht – und sich nicht verrennt?
Prämisse: Alle Ecken sind rechtwinklig Somit kommen nur Rechtsdrehungen und Linksdrehungen
um jeweils 90 Grad vor Wir verwalten unterwegs einen Umdrehungszähler, der:
bei jeder Linksdrehung um eins erhöht und bei jeder Rechtsdrehung um eins verringert wird (auch bei
der ersten Rechtsdrehung, die nach dem Auftreffen auf eine Wand ausgeführt wird).
Zu Beginn wird dieser Umdrehungszähler auf null gesetzt
Anschließend werden die beiden Anweisungen geradeaus, bis Wand erreicht Folge der Wand, bis Umdrehungszähler = 0
solange wiederholt, bis wir ins Freie gelangen
Pledge-Algorithmus
Wie
err
eich
t de
r A
gent
sei
n Z
iel (
den
Aus
gang
)?
Wie
err
eich
t de
r A
gent
sei
n Z
iel (
den
Aus
gang
)?
/
Insgesamt: 23 zu erzielende Punkte +2 +3 Punkte geschenkt 26 Punkte Klausurteilnahme bei 14 Punkten Wer keine 14 Punkte erreicht hat, bereitet uns auf
die Klausur vor
Klausurvorbereitung 03.07.2013
Bitte wegen Absprache der klausurvorbereitenden Sitzung nach Kursstunde vorbeischauen:
4862147 5674280 5609887 5518997 5610540 5635080 5595053 5645948 5591392 5595320 5404592 5575117 4304217 5102987 5400350 5598028
Klausurvorbereitung 03.07.2013
ToDo: Kurzreferat über Inhalte der Kursstunde Was war
wichtig? Was war nicht wichtig? Handout erstellen und bereitstellen über Inhalte der
Stunde, zusätzlich: Acht Beispielklausurfragen
Themen: Rechnerkommunikation
Albrecht, Odenthal Algorithmen der Bildverarbeitung: Kompression
Silva, Ludwig, Schmitz Algorithmen der Bildverarbeitung: Computer Vision –
Vorverarbeitung
Grundlagen der Suchmaschinenoptimierung Text Video und Audio
Türkoglu, Oude-Aoust Künstliche Intelligenz in Computer- und Videogames
Munsch, Christoph
Gibt‘s heute keine. Guten Semesterendspurt!
Hausaufgaben
Recommended