Berechnung der Tor- und Passwahrscheinlichkeit

Die Tor- bzw. Passwahrscheinlichkeit gibt Aufschluss darüber, wie wahrscheinlich es ist, dass ein Pass bzw. Torschuss erfolgreich ausgeführt werden kann und ist somit die Grundlage vieler Entscheidungen des Taskmanager. Dabei ist zu beachten, dass es sich nicht um tatsächliche Wahrscheinlichkeiten handelt, sondern die Werte vielmehr einen Score angeben, welcher zwar mit der Wahrscheinlichkeit korreliert, jedoch nicht gleichbedeutend mit dieser ist. Die Berechnung dieser Werte ist Aufgabe des Observers.

Motivation

Bei Roboterfußball handelt es sich um ein Szenario, bei dem zwei Teams in direkter Konkurrenz zueinander stehen. Das Ziel ist es, selbst Torschüsse erfolgreich auszuführen, während der Gegner versucht dies zu verhindern. Gelingt dem Gegner dies, so stellt er für uns eine unmittelbare Gefahr da, daher ist es für das erfolgreiche Spiel wichtig, möglichst genau vorhersagen zu können, ob ein Torschuss oder Pass erfolgreich sein wird, oder ob stattdessen lieber eine alternative Option ausgeführt werden soll. Doch diese Vorhersage erweist sich oft als schwierig, da die Datenlage sehr komplex ist; Als Eingabedaten liegen lediglich die Positionen und Geschwindigkeiten des Balles und sämtlicher Roboter vor, aus diesen müssen nun besser Verwertbare Scores abgeleitet werden, die Aufschluss darüber geben, ob z.B. ein Torschuss unternommen werden sollte. Je besser und präzisier diese Berechnungen sind, desto wahrscheinlicher ist es, dass ein Schussversuch auch tatsächlich in einem Tor endet, statt dem Gegner die Konterchance zu bieten.

Die Spieltheorie besagt, dass stets angenommen werden sollte, dass der Gegner das für ihn beste Ergebnis anstrebt und somit seine Aktionen so wählen wird, dass er seine eigene Erfolgschance maximiert. In diesem Sinne sollte stets eine worst-case-Schätzung gemacht werden, was bedeutet dass angenommen werden sollte, dass ein Gegner den Ball abfangen wird, sofern es für ihn möglich ist, ein solches Abfangmanöver in der vorhandenen Zeit durchzuführen. Tatsächlich ist hierfür jedoch auch eine perfekte Prädiktion unseres Verhaltens erforderlich, was für den realen Gegner unrealisitisch ist. Daher wird im Folgenden angenommen, dass der Schusserfolg vielmehr durch eine Wahrscheinlichkeitsfunktion modelliert werden sollte, die die realen Fähigkeiten der Gegner berücksichtigt.

Bangkok 2022: Torwahrscheinlichkeit nach Schattenprinzip

Das erste Konzept zur Berechnung einer Torwahrscheinlichkeit wurde für den Wettkampf in Bangkok 2022 entwickelt. Die Berechnung besteht aus einer Heuristik, in der drei wesentliche Faktoren herangezogen werden: Der Abstand zum Tor, der Winkel zum Tor, die von Gegnern verdeckte Torfläche. Diese sind in der nachfolgenden Grafik dargestellt:

Abstand zum Tor
Der Abstand des Balls zum Tor wird in einem Score ausgedrückt, der mit größerem Abstand zum Tor abnimmt. Die Funktion ist dabei nicht linear, sondern in der eines atan(x), da davon ausgegangen wird, dass durch die Verlangserung des Balls während des Schusses es auf weite Distanzen immer schwieriger wird ein Tor zu schießen, während der Unterschied zwischen einem oder zwei Metern weniger signifikant ist. Ab etwa 4 Metern gibt es einen starken Abfall im Abstands-Score.
Winkel zum Tor
Je mittiger der Ball vor dem Tor liegt, desto einfacher ist es, dieses zu treffen, da die effektive Torfläche größer wird. Die effektive Torfläche kann durch eine cos(x)-Funktion ausgedrückt werden.
Verdeckte Torfläche
Bislang wurde nur die Lage des Balls relativ zum Gegnertor berücksichtigt, nicht jedoch die Lage der gegnerischen Roboter, die den Ball abfangen könnten. Um diese in die Berechnung miteinzubeziehen, wird der Ball als eine Lichtquelle angenommen, wobei Gegner das Licht blocken und Schatten werfen. Die verdeckte Torfläche lässt sich aus dem Verhältnis der beleuchteten Torfläche durch die Gesamte Torfläche bestimmen. Somit sinkt dieser Score, je mehr Gegner sich vor dem Tor befinden und je näher diese am Ball sind. Außerdem lässt sich auch der ideale Torschusspunkt anhand der Schatten bestimmen, wobei dieser in der Mitte der größten Beleuchteten Fläche liegt.

Aus diesen drei Einzelfaktoren kann nun ein Gesamtscore berechnet werden, indem die einzelnen Faktoren multipliziert werden. Dieses Vorgehen gibt zwar in etwa Aufschluss darüber, ob ein Torschuss unternommen werden sollte, hat jedoch einige Schwächen:

Durch die Multiplikation werden die Werte allgemein sehr klein. Schon ein Gesamtscore von 0,02 kann gut und ein Indiz dafür sein, dass ein Schussversuch unternommen werden sollte; Das macht diese Werte schwer interpretierbar.
Die Werte sind nicht gewichtet. Dies könnte behoben werden, indem die Einzelscores mit Geichtungsfaktoren multipliziert und danach aufaddiert werden, jedoch ist hier die Wahl von geeigneten Gewichtungsfaktoren schwierig und unterliegt dem menschlichen Bias.
Einige der verwendeten Parameter sind ebenfalls arbiträr gewählt und wurden nicht anhand von Spieldaten verifiziert. Hierzu gehört beispielsweise die Wahl der Funktion bei Berechnung des Distanz-Scores. Auch hier macht sich ein menschlicher Bias bemerkbar.
Die Faktoren werden durch die Multiplikation als unabhängig voneinander angenommen, was sie in Wahrheit jedoch nicht sein sollten. So sollte etwa der Winkel mit steigendem Abstand vom Tor an Bedeutung gewinnen, da es durch die Kicker-Streuung immer schwieriger wird, das Tor zu treffen.
Die Schatten sind zwar eine einfache Art und Weise auf die Gegnerische Roboter berücksichtigt werden können, jedoch ist das Prinzip eher ungeeignet. Gibt es im Tor mehrere beleuchtete Flächen, steigt die Torwahrscheinlichkeit, obwohl nur auf eine der Flächen geschossen werden kann; hier wäre die maximale Fläche ggfs. sinnvoller. Das Schattenprinzip nimmt die Gegner als statische Objekte an, die sich nicht bewegen; Jede mögliche Schusslinie, die nicht direkt durch einen Gegner hindurchgeht und das Tor trifft, würde gleichwertig zu einer Erhöhung der Torwahrscheinlichkeit betragen, unabhängig davon, ob ein Gegner durch eine minimale Bewegung den Ball abfangen könnte oder nicht.

Bias: Unter einem Bias wird eine kognitive Verzerrung der Wirklichkeit durch die menschliche Voreingenommenheit verstanden. Dies tritt insbesondere bei der Gewichtung von Faktoren auf, bei der die menschliche Intuition zu einem sehr subjektiven Ergebnis führt. Um den Bias zu reduzieren, sollten Daten anhand von Simulationen geprüft und Verifiziert werden, wobei jedoch zu beachten ist, dass auch die Wahl und das Setup der Simulation einen Bias beinhalten kann. Weitere Infos:

Bordeaux 2023: Passwahrscheinlichkeit auf Interception-Basis

Für den RoboCup in Bordeaux sollten die Berechnungen komplett überarbeitet werden, um die in Bangkok festgestellten Probleme zu beheben. Hierzu wurde ein neues Konzept entwickelt, welches rein auf einem Interception-Score basiert. Dieser repräsentiert die Wahrscheinlichkeit, dass es einem Gegner gelingt, einen Ball abzufangen. Außerdem wurde durch Adathresh ein System entwickelt, das die Fähigkeiten des Gegners unsere Bälle abzufangen analysiert und somit einen dynamischen Schwellwert basierend auf den Erfahrungen während des Spieles festlegt, ab dem ein Schuss tatsächlich ausgeführt werden sollte.

Berechnung der Passwahrscheinlichkeit

Die Passwahrscheinlichkeit ist im allgemeinen ein einfacherer Fall der Torwahrscheinlichkeit, da der Ball auf einen definierten Punkt statt durch eine definierte Fläche gespielt werden soll. Das allgemeine Vorgehen ist dabei wie folgt:

Bestimmung der Kickstärke: Je nach Abstand zum Ziel sollte die Kick-Geschwindigkeit eingestellt werden, sodass der Ball mit einer definierten Geschwindigkeit am Ziel ankommt. Dies soll die Annahme des Balles vereinfachen. Langsamere Pässe vereinfachen dabei im allgemeinen die Ballannahme, sind jedoch auch einfacher abzufangen. In praktischen Tests haben sich Annahmegeschwindigkeiten von etwa 2-3m/s sinnvol erwiesen. Die Kick-Geschwindigkeit gibt dabei die initiale Geschwindigkeit des Balles direkt nach dem Kick an und muss auf die Reibwerte des Spielfeldes angepasst werden. Dies kann durch eine Kalibrierung des Systems erfolgen, bei der automatisch Lookup-Tabellen erstellt werden, aus denen für eine gegebene Distanz die optimale Kickstärke entnommen werden kann. Dies könnte folgendermaßen aussehen:

Bestimmung der Aktionsradien für jeden Gegner: Es wird abgeschätzt, wie viel Zeit ein Gegner hätte, um den Ball abzufangen. Dies ist abhängig von der maximalen Gegnergeschwindigkeit, der Schussgeschwindigkeit, der Ausführzeit des Schusses, sowie vom Abstand vom Gegner zum Ball. Der Aktionsradius ergibt sich dabei aus der Gegnergeschwindigkeit geteilt durch die Intercept-Zeit, wobei sich die Intercept-Zeit zusammensetzt aus der Zeit, die der Schütze zum Schießen braucht (insbesondere Ausrichtung) sowie der Zeit, die der Ball braucht, um den Gegner zu erreichen. Auch diese Zeiten lassen sich kalibrieren, was folgendermaßen aussieht:

Berechnung des minimalen Abstandes von jedem Gegner zur Schusslinie: Es wird angenommen, dass der die direkte Fahrt auf das Schussliniensegment dem idealen Pfad des Intercept-Manövers entspricht. Folglich wird für jeden Gegner die kürzeste Distanz zum Liniensegment bestimmt. Die notwendigen Formeln hierfür finden sich z.B. hier: Stack Overflow: Distance Point to Line Segment
Berechnung der Abfangwahrscheinlichkeit für jeden Gegner: Aus dem Verhältnis der Distanz zum Liniensegment sowie des Aktionsradius ergibt sich die Wahrscheinlichkeit, dass der Gegner nicht an den Ball kommt. Ist diese größer als eins, bedeutet das, dass die Schusslinie den Aktionskreis des Gegners nicht schneidet, wodurch dieser Gegner keine Chance hat, die Schussbahn rechtzeitig zu erreichen und so den Ball abzufangen. Werte kleiner als eins bedeuten, dass es theoretisch möglich wäre, dass der Gegner an den Ball kommt. Hohe Werte deuten dabei darauf hin, dass ein Intercept des Gegners unwahrscheinlich ist, da er hierfür eine perfekte Prädiktion der Schusstrajektorie benötigen würde. Niedrige Werte bedeuten, dass der Schuss selbst durch einen stillstehenden Gegner geblockt werden könnten. Durch eine quadrierung des Wertes können zudem Schüsse die nah am Gegner vorbei gehen noch stärker bestraft werden.
Berechnung der Gesamten Passwahrscheinlichkeit: Um die letztendliche Gesamtwahrscheinlichkeit zu berechnen, werden zunächst die Einzelwahrscheinlichkeiten der einzelnen Gegner miteinander multipliziert. Dabei werden nur Gegner berücksichtigt, die theoretisch rechtzeitig an den Ball kommen könnten, also deren Aktionskreise das Liniensegment des Schusses schneiden. Je mehr Gegner den Ball erreichen könnten und je näher diese sich an der Schusslinie befinden, desto geringer wird die Wahrscheinlichkeit, dass das Ball sein Ziel erreicht. Gegner die sich weiter von der Startposition des Balles entfernt befinden, haben zudem einen größeren Aktionsradius und somit mehr Zeit, die Schusslinie zu erreichen, was wiederum in einer höheren Abfangwahrscheinlichkeit resultiert.

Das Ergebnis dieses Verfahrens wird im folgenden Bild beispielhaft für einen Pass zwischen den zwei blauen Robotern demonstriert. Die Drehzeit des Roboters ist für die Ausführung des Schusses ist fix und nur vom Winkel abhängig, wodurch beide gelben Roboter den selben Bonus zu ihrem Aktionsradius erhalten. Der sich weiter weg befindene Gegner erhält dennoch einen größeren Aktionsradius, da der Ball ihn nach längerer Zeit erst erreicht. Die Grafik zeigt, dass beide Aktionkreise das Liniensegment schneiden, somit könnten beide Gegner theoretisch den Ball rechtzeitig abfangen. Für den rechten Gegner ist die Abfangwahrscheinlichkeit dabei geringer, da es eine geringere Überschneidung mit der Schusslinie gibt. Die Gesamtwahrscheinlichkeit für einen erfolgreichen Pass wäre in diesem Fall (1-0.01) * (1-0.1) = 89,1%.

Erweiterung zur Torwahrscheinlichkeit

Das beschriebene Konzept lässt sich erweitern und anpassen, um statt Pässen auch Torschüsse bewerten zu können. Die Grundidee des Algorithmus ist hierführ identisch, doch statt der Passposition werden mehrere Punkte auf der Torlinie verwendet. Diese Punkte werden in regelmäßigen Abständen von etwa 5cm auf der gegnerischen Torlinie generiert und stellen verschiedene Schussbahnen dar, mit denen das Tor theoretisch getroffen werden könnte. Für jede Linie wird wie oben beschrieben die Erfolgschance berechnet, wobei die Kickgeschwindigkeit stets mit den laut Regelwerk maximal zulässigen 6,5m/s angenommen wird.
Die Gesamtwahrscheinlichkeit für einen erfolgreichen Torschuss ist das Maximum der einzelergebnisse. Alle weiteren Schusslinien können verworfen werden, da letztlich nur eine der Schussmöglichkeiten auch tatsächlich ausgeführt werden kann. Hierdurch wird somit sowohl die Wahrscheinlichkeit als auch der ideale Torschusspunkt festgelegt.

Im Falle eines leeren Tores wären die Wahrscheinlichkeiten für jeden Punkt gleich und zwar bei 1,0. In diesem Fall würde der Algorithmus einen zufälligen Punkt wählen. Liegt dieser Nah am Pfosten, kann es durch die Streuung des Kickers zum Verfehlen des Tores kommen. Es empfiehlt sich daher, Punkten mittig des Tores einen kleinen Bonus und Punkten am Rand einen kleinen Malus zu geben, um so sicherzustellen, dass der Roboter mittige Punkte bevorzugt. Außerdem sollten Punkte mit einem Mindestabstand zu den Pfosten generiert werden, um das Anvisieren des Pfostens zu vermeiden.

Prinzip der Generation von möglichen Zielpunkten auf der Torlinie:

Visualisierung der Torwahrscheinlichkeit als Heatmap; rot = hohe wahrscheinlichkeit, lila = geringe Wahrscheinlichkeit. Aufgrund der "aimless-kick"-Regel in Div B wurden hier Positionen auf der eigenen Hälfte zusätzlich bestraft:

Eindhoven 2024:

Für Eindhoven werden die Konzepte und Berechnungen von Bordeaux 2023 ohne weiteren Änderungen übernommen.

Ideen zur Weiterentwicklung

Anstelle der Heuristiken könnte supervised machine Learning verwendet werden, um einen Klassifikator zu trainieren, der die Erfolgschancen eines Passes oder Torschusses einschätzt. Hier würden sich random forests, adaboost oder neuronale Netze anbieten. Zu bedenken ist aber, dass die Trainingsszenarien realisitisch zu wählen sind, um Overfitting zu vermeiden; Hierbei sind auch unterschiedliche Verhaltensweisen des Verteidigers zu simulieren. Aufgrund der stochastischen Natur muss zudem eine sehr hohe Anzahl an Trainingsdaten generiert werden.