1 Einleitung

23

1.1 Ich freue mich, dass Sie dabei sind

24

1.2 Was erwartet Sie in diesem Buch?

24

1.3 Abgrenzung zu modernen KI-Technologien

25

1.4 Was genau ist in diesem Buch zu finden?

27

1.4.1 Eliza und KI-Grundlagen

27

1.4.2 Nim und der Minimax-Algorithmus

28

1.4.3 Tic-Tac-Toe und Reinforcement Learning

29

1.4.4 Reversi

30

1.4.5 Sudoku und die Verbindung zur prozeduralen Generierung

31

1.4.6 Maze Madness

32

1.4.7 Maze-Man (angelehnt an: Pac-Man)

32

1.4.8 Tut’s Treasure

33

1.5 Ist dieses Buch für Sie geeignet?

34

1.5.1 Für Programmierer mit Python-Kenntnissen

35

1.5.2 Für Einsteiger in die Programmierung

35

1.5.3 Warum es keine Grundlagenkapitel gibt

35

1.5.4 Aufbauende Projekte für kontinuierliches Lernen

36

1.6 Das Ziel dieses Buches

37

1.7 Wenn ich weiter gesehen habe …

38

2 Software

41

2.1 Alternative 1: Installation von Python

42

2.2 Alternative 2: Installation von Anaconda

44

2.3 Installation von Pygame

45

2.4 Installation von Visual Studio Code

46

2.5 Erste Schritte mit Visual Studio Code

48

2.6 Extensions installieren und nutzen

50

2.7 JupyterLab installieren

52

3 Hi! I’m Eliza

55

3.1 Was ist Eliza?

56

3.2 Was ist ein Turing-Test?

57

3.3 Woher kommt der Name Eliza?

59

3.4 Das MVC-Entwurfsmuster

60

3.5 Ablauflogik von Eliza

62

3.6 Implementierung von Eliza

64

3.6.1 Das Hauptprogramm

65

3.6.2 Der Startbildschirm

66

3.6.3 Laden und Speichern von Daten

69

3.6.4 Hallo und Tschüss

80

3.6.5 Texteingabe und -analyse

81

3.7 Ausblick

94

3.8 Literatur und Quellenangaben

94

4 Eliza revamped

95

4.1 Was ist Pygame?

96

4.1.1 Vorteile von Pygame

97

4.1.2 Nachteile von Pygame

97

4.2 Pygame installieren

97

4.2.1 Pygame importieren und initialisieren

98

4.3 Architektur einer Pygame-Anwendung

98

4.4 Pygame trifft Eliza

105

4.4.1 Designidee: Messenger-Optik

105

4.4.2 Bildschirmauflösung und Layout

106

4.4.3 Hintergrundbild erzeugen

106

4.4.4 Do Androids Dream of Electric Sheep?

108

4.4.5 Hintergrundbild einbinden

109

4.4.6 Message-Bubble erstellen

111

4.4.7 Testumgebung erstellen

118

4.4.8 Die Klasse Text_Field

121

4.4.9 Ein blinkender Cursor

126

4.4.10 Das Textfeld zeichnen

129

4.4.11 Ein Scrollbalken

131

4.4.12 Das Eliza-Skript integrieren

136

4.5 Elizas Struktur

138

4.6 Zusammenfassung

140

4.7 Ausblick

141

4.8 Literatur- und Quellenangaben

141

5 Nim

143

5.1 Ordnerstrukturen für größere Projekte

144

5.2 Backtracking und Rekursion

146

5.2.1 Rekursion

148

5.2.2 Die Fakultätsfunktion

148

5.2.3 Die Fibonacci-Funktion

151

5.2.4 Das N-Damen-Problem

154

5.3 Strategie und Mathematik hinter Nim

158

5.3.1 Die vereinfachte Version von Nim

158

5.4 Der Minimax-Algorithmus

159

5.4.1 Spielbäume

159

5.4.2 Der optimale Schritt

163

5.5 Implementierung von Minimax am Beispiel von Nim

166

5.5.1 Die einzelnen Fälle

167

5.5.2 Der Basisfall

168

5.5.3 Der rekursive Fall

168

5.5.4 Optimierung des Codes

170

5.5.5 Die Bewertungsfunktion

171

5.5.6 Die Zugfunktion

172

5.5.7 Den besten Zug ermitteln

173

5.6 Der komplette Quelltext

174

5.7 Ausblick

177

5.8 Literatur und Quellenangaben

178

6 Nim unleashed

179

6.1 Projektstruktur anlegen

180

6.1.1 Konstanten auslagern

181

6.1.2 Farben auslagern

182

6.1.3 Die Klasse Game auslagern

183

6.1.4 Die neue Struktur ist MVC-kompatibel

183

6.2 Nim nach PyGame migrieren

184

6.2.1 Designentscheidungen

184

6.2.2 Hintergrundbild erzeugen

184

6.2.3 Hintergrundbild einbinden

185

6.2.4 Buttons einbinden

187

6.2.5 Eine TextArea erstellen und einbinden

190

6.2.6 Der Scrollbalken VScrollBar

193

6.2.7 MessageBox einbinden

194

6.2.8 Erstellen der Oberfläche

198

6.2.9 Das Spielbrett und der Spielzustand

204

6.2.10 Münzen für den View

206

6.2.11 Die KI integrieren

207

6.3 Ich krieg Zustände …

211

6.4 Eine Optimierung für die GUI-Komponenten

214

6.5 Ausblick

216

6.6 Literatur und Quellenangaben

216

7 Tic-Tac-Toe

217

7.1 Projektstruktur anlegen

218

7.2 Das Board und die Regeln

218

7.3 Die drei KIs

221

7.3.1 AbstractAI

223

7.3.2 RandomAI

224

7.3.3 MiniMaxAI

225

7.3.4 ScoreAI

229

7.4 Die GUI erstellen

235

7.4.1 Ein Hintergrundbild einbinden

235

7.4.2 Farbgebung

236

7.4.3 GridView

236

7.4.4 DropDown

241

7.4.5 YesNoMessageBox

243

7.4.6 Button

246

7.5 Die Control-Klasse

247

7.6 Ausblick

254

8 Tic-Tac-Q

255

8.1 Q-Learning

256

8.1.1 Woher stammt der Name?

256

8.1.2 Alltagsbeispiel: Fahrradfahren lernen

257

8.1.3 Formale Beschreibung des Reinforcement Learnings

259

8.1.4 Training des Agenten

260

8.2 Swampy Fields

262

8.3 Q-Learning in Tic-Tac-Toe

270

8.3.1 Unterschiedliche Tabellen

270

8.3.2 Eine andere Lernstrategie als bei Swampy Fields

271

8.3.3 Ein komplettes Beispiel

271

8.3.4 Hyperparameter

281

8.4 Ausblick

282

8.5 Literatur und Quellenangaben

282

9 Black & White

283

9.1 Projektstruktur anlegen

285

9.2 Das Board und die Regeln

286

9.2.1 Spielfeld und Startposition

286

9.2.2 Regeln

287

9.2.3 Ziel des Spiels

290

9.2.4 Die Klasse Board

291

9.3 Alpha-Beta Pruning

301

9.4 Die KI

304

9.4.1 AbstractAI

306

9.4.2 RandomAI oder Planlos Peter

306

9.4.3 MaxAI oder Gier Gundula

307

9.4.4 MobilityAI oder Mobi Max

308

9.4.5 PositionalAI oder Positions Paula

309

9.4.6 MiniMaxAI oder Minimax Mike

312

9.4.7 AlphaBetaAI oder Alpha Anna

314

9.4.8 Konfig Karl

317

9.5 Die GUI erstellen

317

9.5.1 Hintergrundbild einbinden

318

9.5.2 Farbgebung

318

9.5.3 GridView

319

9.5.4 Stone

323

9.6 Animationen und Daumenkinos

325

9.6.1 Phasen der Animation

325

9.6.2 Animation mit Einzelbildern

326

9.6.3 Animation mit einem Spritesheet

328

9.6.4 Animationen selbst erstellen

329

9.7 Die Control-Klasse

331

9.8 Ausblick

338

9.9 Literatur und Quellenangaben

339

10 Black & White: Denken und Steuern

341

10.1 State Charts

342

10.1.1 Wofür wurden State Charts entwickelt?

343

10.2 Beispiele für State Charts

344

10.2.1 Ein Schalter

344

10.2.2 Ein Schalter mit Lampe

347

10.2.3 Eine Lampe mit Zeitschaltung

349

10.2.4 Eine Verkehrsampel

354

10.3 Ein Menüsystem

358

10.3.1 Die Struktur des Menüsystems

360

10.3.2 Die Klasse bw

361

10.3.3 Die Klasse Game

362

10.3.4 Der Basiszustand BaseState

366

10.3.5 Die Klasse GameMenu

367

10.3.6 Die Klasse GameRules

371

10.3.7 Die Klassen GameOver und GamePlay

379

10.4 Optimierung des Alpha-Beta Prunings

379

10.4.1 Startzustand – zurück zu Minimax

380

10.4.2 Optimierung 1 – die Bewertungsfunktion

384

10.4.3 Optimierung 2 – deepcopy umgehen

386

10.4.4 Optimierung 3 – Alpha-Beta statt Minimax

388

10.4.5 Optimierung 4 – eine Transposition Table einführen

391

10.4.6 Optimierung 5 – Züge sortieren

396

10.4.7 Optimierung 6 – Züge parallelisieren

398

10.5 Ausblick

400

11 Von Sudoku zu intelligenten Lösungen

401

11.1 Was ist ein CSP?

402

11.1.1 Formale Definition eines CSP

402

11.1.2 Einfache Beispiele für CSPs

403

11.2 Warum Sudoku?

403

11.3 Was ist ein Sudoku?

404

11.3.1 Eine Reise in die Vergangenheit

405

11.3.2 Wie ist ein Sudoku aufgebaut?

405

11.3.3 Ein Sudoku lösen

406

11.4 Sudokus erzeugen

414

11.4.1 Sudokus mit CSP erzeugen

415

11.4.2 Sudokus ohne CSP erstellen

419

11.4.3 Tauschen von Zeilen in einem Sudoku

421

11.4.4 Tauschen von Spalten in einem Sudoku

422

11.4.5 Tauschen von Zeilen von Blöcken

423

11.4.6 Tauschen von Spalten von Blöcken

423

11.4.7 Tauschen von Zahlen

424

11.4.8 Das Geheimnis der leeren Felder: Wie ein Sudoku zum Leben erwacht

425

11.4.9 Formen der Harmonie

426

11.4.10 Referenzen im Quelltext

428

11.5 Schrödingers Sudoku – Aspekte der Quantenmechanik

428

11.5.1 Schrödingers Katze

429

11.5.2 Superposition

429

11.5.3 Kollaps der Wellenfunktion

430

11.5.4 Bezug zwischen Sudokus und der Quantenmechanik

430

11.6 Sudokus lösen

432

11.6.1 Das Strategy-Pattern

432

11.6.2 Backtracking als Lösungstechnik

432

11.6.3 Naked Singles

434

11.6.4 Hidden Singles

436

11.6.5 Naked Pair

437

11.6.6 Hidden Pair

438

11.7 Wo ist das Projekt?

439

11.8 Sound und Musik

440

11.8.1 Hintergrundmusik finden

441

11.8.2 Hintergrundmusik laden

441

11.8.3 Hintergrundmusik abspielen

441

11.8.4 Lautstärke einstellen

442

11.8.5 Hintergrundmusik anhalten und fortsetzen

442

11.8.6 Soundeffekte finden

443

11.8.7 Soundeffekte laden

443

11.8.8 Soundeffekte abspielen

443

11.9 Export als PDF, PNG, PPT

444

11.10 Ausblick

445

11.11 Literatur und Quellenangaben

446

12 Maze Madness

447

12.1 Irrgärten erzeugen

448

12.2 Das Spielkonzept von Maze Madness

457

12.3 Steuerung des Spiels

459

12.3.1 Steuerung über die Tastatur

459

12.3.2 Steuerung über das GamePad

463

12.4 Grafiken

467

12.4.1 Die Grafiken für den Irrgarten einbinden

468

12.4.2 Grafiken für den Spieler einbinden

470

12.4.3 Grafiken für den Geist einbinden

471

12.4.4 Grafiken für das Gold einbinden

471

12.5 Gold einbinden

471

12.6 Die Geister

473

12.6.1 KI in Maze Madness

474

12.6.2 Geister auf Patrouille

474

12.6.3 Pixelgenaue Bewegung der Geister

478

12.7 Selina V2.0

480

12.8 Erweiterungen an Maze und MazeCell

485

12.9 Die Geister V2.0

487

12.10 Das finale Gameplay

490

12.10.1 Sackgassen

491

12.10.2 Eine Lupenfunktion

492

12.11 Wo ist das Projekt?

494

12.12 Ausblick

494

12.13 Literatur und Quellenangaben

495

13 Die Geister, die ich rief

497

13.1 Urheberrecht

498

13.2 Maze Man

499

13.3 Prozedurale Irrgärten

499

13.3.1 Der Sourcecode

508

13.3.2 Von Blöcken zu Pixeln

516

13.4 Die Logik der Gegner

518

13.4.1 Die Gegner allgemein

518

13.4.2 Der rote Gegner »Fredo«

527

13.4.3 Der rosa Gegner »Rosie«

528

13.4.4 Der hellblaue Gegner »Azuro«

529

13.4.5 Der orangene Gegner »Tango«

530

13.5 Der Spieler

531

13.6 Wie geht es nun weiter?

531

13.6.1 Punkte fressen

531

13.6.2 Level abgeschlossen

531

13.6.3 Maze Mans Tod

532

13.6.4 Wechsel der Gegner-KI

532

13.6.5 Sprites und Animationen

532

13.7 Ausblick

532

13.8 Literatur und Quellenangaben

533

14 Tut’s Treasure

535

14.1 Urheberrecht

537

14.2 Ideen für unser Spiel

539

14.3 WFC – Wave Function Collapse

540

14.3.1 Superposition im Sudoku

541

14.3.2 Superposition auf einer Feier

541

14.3.3 Land, Küste, Wasser

542

14.4 Ist WFC künstliche Intelligenz?

545

14.5 Mit WFC zu Platformer-Leveln

546

14.5.1 Der Level-Editor

547

14.5.2 Analyse der Level

548

14.5.3 Das Analyseprogramm

550

14.5.4 Die WFC-Daten

550

14.6 Der WFC-Code

550

14.6.1 gameplaywfc

551

14.6.2 Tile

553

14.6.3 TileWorld

557

14.7 Wegesuche mit A*

562

14.8 A* Im Irrgarten

564

14.9 Überblick über das Spiel

575

14.9.1 Menü

575

14.9.2 Der Level-Editor

576

14.9.3 Die Level-Auswahl

578

14.9.4 Der Parallax-Effekt

579

14.9.5 Das Kamera-System

583

14.9.6 Das HUD

585

14.9.7 Audiovisuelles Feedback

586

14.9.8 Der Ausgang

588

14.9.9 Die Charaktere

591

14.9.10 Der Hero

592

14.9.11 Die Mumie

596

14.10 Ausblick

607

14.11 Literatur und Quellenangaben

608

15 Spektiven

609

15.1 Retro-Spektive

610

15.2 Per-Spektive

612

15.3 Pro-Spektive

612

15.4 Intro-Spektive

613

15.5 Das Ende einer Reise – die Freude bleibt

614