k-Nearest-Neighbors-Darts

Was einem so die Langeweile und das Wissen aus dem Studium bringen können. Als ich in Japan – letztes Jahr bereits, glaube ich – einmal bei meinen Großeltern war, hatte ich für ein Stündchen oder zwei nichts zu tun. Es war am Nachmittag und ich wollte mich ausruhen.

Ich befand mich also im ersten Stock und das Fernsehprogramm sprach mich in dem Moment auch nicht an. Ich wandte mich dem Schreibtisch zu, kramte kurz auf ihm herum, nahm drei Pfeile in die Hand und stellte mich mit dem Gesicht zur Zimmerecke, einem Dartboard zugewandt.


Hintergrund

Denn ja, meine Großmutter spielt Darts. Oder zumindest hat sie das getan, als sie noch dazu in der Lage war, in den ersten Stock zu gehen. Seitdem sie das nicht mehr kann, steht das Dartboard ein wenig verlassen dort in der Zimmerecke und wird nur noch dann benutzt, wenn ich mal vorbeischaue.1

Aber in diesem Moment – es lag daran, wie die Pfeile auf dem Brett landeten (teilweise lag es auch daran, dass ich ein Genie bin) – kam ich auf eine glorreiche Idee: ich würde eine neue Spielart des Darts erfinden! Und diese Spielart müsse so unverständliche Regeln haben, dass es absolut keinen Spielspaß bieten würde.

Die Anordnung der Pfeile hat mich sofort an ein Klassifikationsproblem erinnert. Konkret hat es mich an den k-Nearest-Neighbors-Algorithmus erinnert, von dem ich dann glatt den Namen geklaut habe.2

Es soll daher nun eine Erklärung dieser Spielart, die ich k-Nearest-Neighbor-Darts nenne, geben. Zur Veranschaulichung werde ich Beispiele anhand der Abbildung 1 geben.


Das Spiel

Dartboard_diagram.svg

Abb. 1. Ein typisches Dartboard. (Quelle: wikipedia)

Ein Hinweis zur Notation: die Zahlentripel in eckigen Klammern repräsentieren die drei getroffenen Zahlen auf dem Brett. d und t werden den Zahlen nachgestellt, wenn ein double ring oder ein triple ring getroffen wurden. – steht dafür, dass das Brett (oder zumindest ein gültiges Feld) verfehlt wurde. Die Reihenfolge ist von links nach rechts. Die erste Ziffer ist das sog. Mittel (s.u.) und wird in den Beispielen und in der Notation fett markiert. [20, 8d, –] bedeutet, dass als erstes eine normale 20, dann eine doppelte 8 getroffen wurden und dass der letzte Wurf kein gültiges Feld getroffen hat.


Man starte mit einer Punktzahl von 501. Ziel ist es, als erster Spieler 0 Punkte zu haben. Man werfe nun einen Pfeil. Er trifft auf ein Feld, das zu einer Nummer (der Punktzahl) gehört. Man muss nun versuchen, in einem Rahmen von drei angrenzenden Nummern (die zuerst getroffene, die links daneben, die rechts daneben) jede Nummer ein Mal zu treffen. Das zuerst getroffene Feld nennen wir das ‚Mittelfeld‘ (oder nur ‚Mittel‘).

Wenn es gelingt, solch ein angrenzendes Tripel (dies nennen wir ein goldenes Tripel) zu treffen, nimmt man die Summe der Zahlen und verdreifacht sie. Die Multiplikatoren in Form der double rings and triple rings funktionieren wie im normalen Spiel (d.h. sie verdoppeln bzw. verdreifachen den Zahlenwert).

Nehmen wir als Beispiel an, dass wir als erstes die 20 treffen; sie stellt nun unser Mittel dar. Wir müssen also nun ein Feld der 5 und ein Feld der 1 treffen. Gehen wir davon aus, dass es gelingt und wir eine normale 5 und eine doppelte 1 treffen (damit haben wir [20, 5, 1d] getroffen). Wir haben somit die Punktzahl 81 erreicht ((20 + 5 + 2) * 3), die wir nun von den 501 abziehen (wir haben noch 420 Punkte).

Es kann aber sein, dass wir [20, 5, 12] treffen. Ein Blick auf das Brett verrät uns, dass es dennoch drei nebeneinanderliegende Zahlen sind. Da unser Mittel nun aber am Rand liegt, addieren wir die Werte lediglich (20 + 5 + 12 = 37). Es ist daher, wie wir sehen, möglich, auch andere Tripel zu erzielen (solch ein Tripel hier wird silbernes Tripel genannt).

Natürlich kann es nun aber sein, dass man es nicht schafft, drei nebeneinanderliegende Zahlen zu treffen. In diesem Fall gibt es mehrere Möglichkeiten, trotzdem noch Punkte zu erhalten. Gehen wir wieder davon aus, dass Mittel = 20.

Treffen wir nun z.B. [20, 5, 13] (oder verfehlen das Brett, [20, 5, –]), so addieren wir immerhin die beiden Zahlen 20 und 5 und nehmen das als unser Ergebnis (25) für diese Runde.

Angenommen, wir würden bereits mit dem zweiten Pfeil eine Zahl treffen, die nicht neben dem Mittel liegt (z.B. 13 in unserem Fall), dann haben wir zwei Möglichkeiten: entweder, wir treffen mit dem dritten Pfeil eine Zahl, die neben dem Mittel liegt (z.B. hätten wir dann [20, 13, 5]) oder wir treffen eine Zahl, die neben dem zweiten Pfeil liegt (an die 13 grenzen die 4 und die 6).

Der erste Fall wird wie bereits erwähnt behandelt, treffen wir jedoch z.B. eine 6 zum Schluss ([20, 13, 6]), haben wir immerhin ein Zweierpaar. Da dieses jedoch nichts mit dem Mittel gemein hat, addieren wir die beiden Werte (13 + 6 = 19) und halbieren den Wert dann (9,5) und runden ggf. auf (ergo bekommen wir in dieser Runde noch 10 Punkte).

Das Konzept des Mittels spielt hier also eine große Rolle. Wenn man zum Beispiel mehrere Pfeile (2 oder 3) ins Mittel wirft, addiert man die Werte und halbiert sie dann (und rundet ggf. auf). D.h. bei [20, 20d, 20] erhalte ich (20 + 40 + 20)/2 = 40 Punkte oder bei [12, –, 12t] erhalte ich (12 + 36)/2 = 24 Punkte. Gleiches gilt für z.B. [20, 20, 18]. In dem Fall, dass man drei Pfeile in das Mittel trifft, nennt man es bronzenes Tripel.

Wenn man jedoch das Mittel trifft und dann beide verbleibende Pfeile nicht ins Mittel, aber in die gleiche Zahl wirft, bekommt man keine Punkte, da sie nicht im Mittel sind. Zum Beispiel würde [20, 18, 18] zu keinen Punkten führen.


Bullseye!

Eine Sonderstellung nimmt, wie sollte es anders sein, das Bullseye ein. Hier ist es so: trifft man zuerst ein Bullseye (OBE = Outer Bullseye, IBE = Inner Bullseye), kann man danach alles auf dem Brett treffen und es wird addiert und verdreifacht. [OBE, 17d, 9] führt also zu (25 + 34 + 9) * 3 = 204 Punkten, [IBE, 2, 18] führt zu (50 + 2 + 18) * 3 = 210 Punkten. Diese Tripel nennt man Diamandtripel.

Trifft man nach dem Bullseye nur noch ein weiteres Feld (d.h. man verfehlt einen der beiden Würfe), werden die beiden Werte lediglich addiert. [OBE, –, 15] führt also zu 25 + 15 = 40 Punkten, [IBE, 1, –] führt zu 50 + 1 = 51 Punkten.

Wenn man allerdings zuerst eine normale Zahl trifft, zum Beispiel Mittel = 20, und dann einen BE, so ist für den letzten Wurf ebenfalls alles möglich. Es wird addiert und verdreifacht. [20, OBE, 6] führt zu (20 + 25 + 6) * 3 = 153 Punkte. Diese Art der Tripel heißt Kristalltripel.3

In dem Fall, dass man einen BE zum Schluss trifft, werden die Werte lediglich addiert, d.h. [12, 5, IBE] führt zu 12 + 5 + 50 = 67 Punkten, [17d, –, OBE] führt zu 34 + 25 = 59 Punkten.


Zum Schluss

Wie jedes Dartspiel auch gibt es immer eine besondere Art, wie man das Spiel zu beenden hat bzw. die letzten Punkte bis 0 wegzubekommen hat. In diesem Spiel ist das sehr einfach: man muss mit irgendeinem Dreierpaar beenden.4

Hat man also z.B. noch 87 Punkte übrig, könnte man das Spiel nun gewinnen, indem man [6, 13, 10] (= (6 + 13 + 10) * 3 = 87) oder [15d, 2t, 17t] (= 30 + 6 + 51 = 87) wirft. Und damit beende ich diesen Artikel.


Mumon

—————————————————————

Fußnoten

1 Im Erdgeschoss ist kein Platz dafür.

2 Bei dem k-Nearest-Neighbor-Algorithmus geht es darum, einen neuen, bisher ungesehen Datenpunkt zu klassifizieren. Das bedeutet, wir wollen ihm ein bestimmtes Label oder ihn einer Kategorie zuweisen. Das k in dem Namen ist eine Variable, der eine konkrete positive Ganzzahl zugewiesen werden kann. Nehmen wir k=1.

Wir haben jetzt also einen neuen Datenpunkt, den wir inmitten unzähliger bekannter Datenpunkte eintragen (diese Datenpunkte sind bereits klassifiziert). Bei dem Algorithmus geht es darum, die k nächsten Nachbarn zu unserem Datenpunkt anzuschauen und anhand der Klassifikation der bekannten Datenpunkte eine Klassifikation für den neuen Datenpunkt zu ermitteln.

Im Falle k=1 ist das einfach: der neue Datenpunkt kriegt das gleiche Label wie der ihm nächste Datenpunkt.

3 Es gibt auch das selten vorkommende und extrem schwierige Platintripel: drei Bullseye hintereinander. Schafft man das, hat der Spieler automatisch gewonnen.

4 Es gibt übrigens auch ein Tripel – neben dem Platintripel, wohlgemerkt –, mit dem man das Spiel direkt in der ersten Runde gewinnen kann. Findet Ihr es?

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.