Wenn die Maschine den Menschen schlägt - AlphaZero amBeispiel von 4-Gewinnt

Abstract

Inhalt dieser Arbeit ist die Veranschaulichung von AlphaZero. AlphaZero ist das erfolgreichste Computerprogramm für komplexe Brettspiele, welche es sich mit Hilfe eines neuartigen Algorithmus selbst beibringt. Um dies zu veranschaulichen, wurde basierend auf AlphaZero eine eigene Implementation für das Spiel Vier-Gewinnt entwickelt. In AlphaZero wird eine Monte Carlo Tree-Search von einem neuronalen Netz geleitet. Das neuronale Netz gibt Wahrscheinlichkeiten P an, aus gegebenem Zustand die möglichen Folgezüge auszuwählen. Zusätzlich approximiert es einen Wert v für das Spielergebnis z, anstatt dieses durch ein rollout zu schätzen, wodurch die zeitintensive Phase des rollouts in der Monte Carlo Tree-Search entfällt. Am Ende einer Simulation der Monte Carlo Tree-Search in AlphaZero liefert diese ebenfalls Wahrscheinlichkeiten, die Folgezüge auszuw ählen. Diese Wahrscheinlichkeiten, als (pi) bezeichnet, können als eine Verbesserung der initialen Wahrscheinlichkeiten P angesehen werden. Die verbesserten Wahrscheinlichkeiten (pi) sowie das tatsächliche Spielergebnis z werden genutzt, um v und P des neuronalen Netzes zu verbessern. Für die eigene Implementation werden Optimierungsmöglichkeiten aufgezeigt und unterschiedliche Ansätze für die Gestaltung der Architektur und Wahl der Parameter diskutiert.

The goal of this paper is to illustrate AlphaZero, which is the most succesful computer program for complex board games so far. It learns to play these boardgames solely by self-play, using a novel algorithm. For the purpose of demonstrating AlphaZero, an own implementation of Connect-Four, based on AlphaZero, has been developed. In AlphaZero a Monte Carlo Tree-Search is guided by a neural network. The neural network outputs probabilties, called P, for choosing the next move. Additionally, a value v for the game result z is approximated by the neural network, instead of performing a rollout to guess z. By doing so, the time-consuming simulation phase of Monte Carlo Tree-Search gets omitted. At the end of a simulation of Monte Carlo Tree-Search in AlphaZero, the performed simulation returns probabilities (pi), which also represent which of the following moves to choose next. (Pi) can be viewed as an improvement over the initial probabilites P. (Pi) and z are used to improve P and v of the neural network. Possible ways to improve the own implementation and different approaches to creating the neural networks, as well as choosing parameters, are discussed in this paper.