JBerries

Ein Algorithmus zur Simulation von N Spielen am k-armigen Banditen (multi-armed bandit) wird in R implementiert. Der Algorithmus erlaubt die Auswahl einer Strategie zur Wahl des nächsten zu spielenden Armes. Als Strategien stehen die im Artikel "Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen vorgestellten Strategien zur Auswahl, es können aber leicht weitere Strategien implementiert und eingefügt werden.

Um beim Spiel am mehrarmigen Banditen einen möglichst hohen Gewinn zu erzielen, benötigt man eine Strategie, die einen Kompromiss zwischen Exploration und Exploitation herstellt. Es werden einfache Algorithmen vorgestellt, die dieses Problem lösen und ihre Eigenschaften werden mit Hilfe von Simulationen untersucht.

Kleiner Ratgeber mit methodischen Hinweisen zum Selbststudium.

Beim mehrarmigen Banditen oder genauer k-armigen Banditen kann man ein Glücksspiel durch Betätigen eines Armes auslösen. Mathematisch modelliert werden sie durch Zufallsvariablen mit unterschiedlichen Erwartungswerten. Möchte man am k-armigen Banditen N Spiele durchführen und dabei einen möglichst hohen Gewinn erzielen, gerät man in ein Dilemma: Einerseits muss man alle Arme untersuchen, um ihre Kennzahlen zu schätzen (Exploration), andererseits möchte man möglichst oft den besten Arm betätigen (Exploitation). Im nächsten Kapitel werden dann Algorithmen entwickelt, die versuchen einen Kompromiss zwischen Exploration und Exploitation herzustellen.

Ein wichtiger Bestandteil des Monte-Carlo-Tree-Search-Algorithmus ist es, aus einer gegebenen Spielsituation zahlreiche Spiele auszuführen, bei denen die Züge zufällig ausgewählt werden. Die Ergebnisse dieser Simulationen bestimmen dann, wie der Algorithmus den Spielbaum weiter untersucht. Um besser nachvollziehen zu können, wie der Monte-Carlo-Tree-Search-Algorithmus den Spielbaum untersucht und für die möglichen Züge Gewinn-Wahrscheinlichkeiten schätzt, werden für das Zahlenspiel 3-5-11 die Formeln hergeleitet, wie man zu gegebenem Anfangswert die Gewinn-Wahrscheinlichkeit berechnen kann, wenn sämtliche Züge eines Spiels zufällig ausgewählt werden (mit jeweils gleicher Wahrscheinlichkeit). Ferner werden Simulationen mit unterschiedlichen Anzahlen von Spielen durchgeführt, um zu beurteilen, wie gut die Ergebnisse der Simulation mit den berechneten Gewinn-Wahrscheinlichkeiten übereinstimmen.

Als weitere Methode zur Lösung von Abzählproblemen wird die Rekursion vorgestellt. Dies geschieht am Beispiel eines Zahlenspiels, für das der vollständige Spielbaum entwickelt wird. Dieser wirkt zwar sehr unregelmäßig und kann mit den bekannten kombinatorischen Formeln nicht bewältigt werden, aber aufgrund seiner rekursiven Struktur lassen sich Abzählprobleme auf das Aufstellen der Rekursionsformel und der Behandlung des Basisfalls zurückführen.

Um die Vorgehensweise beim Monte-Carlo-Tree-Search-Algorithmus besser erklären zu können, wird zunächst ein einfaches Zahlenspiel vorgestellt und analysiert. Es handelt sich um eine Variation des Nim-Spiels, für das man eine einfache Gewinnstrategie angeben kann und bei dem mit dem Anfangswert bereits festgelegt ist, welcher Spieler den Gewinn erzwingen kann. Dies hat den Vorteil, dass man später besser nachvollziehen kann, wie der Monte-Carlo-Tree-Search-Algorithmus vorgeht.

Programmieraufgaben zur Anwendung von Feldern und Zeigern, die im Sinne der strukturierten Programmierung zu lösen sind. Die Quelltexte sollen in reinem C geschrieben werden, also keine Konzepte verwenden, die nur in C++ verfügbar sind.

Felder werden durch Zeiger organisiert und es ist gerade ein Charakteristikum der Sprache C, dass dies nicht nur intern verwendet wird, sondern dass man diesen Mechanismus selbst nutzen kann. Für den Einsteiger ist dies meist mit Schwierigkeiten verbunden, da man oft nicht entscheiden kann, mit welchem Objekt man gerade arbeitet (Zeiger oder Variable eines fundamentalen Datentyps). Die meisten der mit Feldern verbundenen Schwierigkeiten wie etwa die Zeigerarithmetik, die Ausgabe und der Vergleich von Feldern werden erklärt. Wie man Felder an Funktionen übergibt oder als Rückgabewert zurückerhält, wird im nächsten Kapitel erläutert.

In einem Feld werden mehrer Komponenten von gleichem Datentyp zu einem Objekt zusammengefasst. Die Anzahl der Komponenten muss bei der Deklaration angegeben werden und darf sich während der Laufzeit des Programmes nicht ändern. Der häufigste Fehler beim Umgang mit Feldern besteht im Zugriff auf Komponenten jenseits des deklarierten Bereichs, was zu unbestimmtem Verhalten des Programmes führen kann. Die unterschiedlichen Möglichkeiten zur Initialisierung eines Feldes werden vorgestellt. Felder können in beliebig vielen Dimensionen angelegt werden; besprochen werden hier nur eindimensionale Felder (Vektoren) und zweidimensionale Felder (Matrizen).

Zeiger sind Variable, deren Wert eine Adresse ist. Man kann sie mit der Adresse einer anderen Variable initialisieren. Da unterschiedliche Datentypen unterschiedlich großen Speicherplatz belegen, muss bei der Deklaration eines Zeigers angegeben werden, welchen Datentyp die Variable besitzt, auf deren Speicherplatz er verweist. Diese Eigenschaften von Zeigern und mit welchen Operatoren (Adressoperator, Indirektionsoperator) dies realisiert wird, wird hier ausführlich diskutiert. Als Anwendung wird gezeigt, wie man mit Zeigern Funktionen realisieren kann, die mehrere Rückgabewerte besitzen.

Das Damenproblem, also die Aufgabe möglichst wenige Damen auf einem Schachbrett so aufzustellen, dass das gesamte Schachbrett beherrscht wird, wird in ein Problem der Graphentheorie übersetzt. Zu dessen Lösung wird ein brute-force-Algorithmus entwickelt, der darauf beruht, dass man das Schachbrett mit einer Adjazenz-Matrix beschreibt und diese geeignet auswertet.

Der neue WildFly 18 Anwendungsserver ist sowohl Jakarta EE 8 als auch Java EE 8 zertifiziert. Die Entwickler legten auch viel Arbeit in eine bessere Abstimmung der APIs mit der Jakarta Community.

Die Funktion lapply() ersetzt eine Iteration über die Komponenten einer Liste, wobei auf jede Komponente eine Funktion FUN angewendet wird; die Rückgabewerte werden wieder zu einer Liste zusammengefasst. Entsprechend wird mit mapply() über mehrere Listen iteriert, wobei in jedem Schritt entsprechende Komponenten ausgewählt werden und darauf wird die Funktion FUN angewendet. Die Funktion Map() ist ein Wrapper für mapply(), der die wichtigsten Anwendungsfälle abdeckt. Die meisten Funktionen in R sind vektorisiert, können also nicht nur auf einen Eingabewert, sondern auf einen Vektor angewendet werden. Die Vektorisierung von Funktionen ist ein in R zentrales Konzept, das ein besseres Verständnis der Funktion mapply() liefert. Zuletzt wird die Funktion outer() mit einigen Anwendungen besprochen. Die Funktion outer() besitzt zwei Vektoren (oder Felder) als Eingabewert und baut daraus ein komplexeres Feld auf.

In der Familie der apply-Funktionen gibt es mehrere Vertreter, mit den über die Elemente einer Liste iteriert werden kann, wobei auf jede Komponente eine Funktion f() angewendet wird. Besprochen werden lapply(), sapply(), vapply() und rapply(). Die Funktion lapply() ist dabei der grundlegende Vertreter, der die bei der Iteration entstehenden Rückgabewerte wieder zu einer Liste zusammensetzt. Dagegen versucht sapply() einen möglichst einfachen Rückgabewert zu erzeugen (Vektor oder Feld). Der Funktion vapply() kann eine Vorlage für den Rückgabewert übergeben werden, so dass man bessere Kontrolle für weitere Berechnungen hat. Mit rapply() können bestimmte Datentypen aus einer Liste selektiert werden und nur auf diese wird die Funktion f() angewendet; zudem wird die Anwendung von f() rekursiv an die Komponenten der Liste weitergereicht.