Hier auf pewn.de sind nach mittlerweile über anderthalb Jahren schon 155 Spiele eingetragen – das sind fast 2 Spiele pro Woche. Da braucht man gerade als neuer Benutzer schon eine ganze Weile, bis man die alle gesichtet hat und ein paar für einen selbst interessante Spiele gefunden hat. Zum Glück gibt es vielfältige Möglichkeiten, wie man die Auswahl einschränken kann: Nach Bewertungen gehen, nach den Charts, bei den Entdeckungen stöbern… durch all diese Möglichkeiten habe ich schon selbst das ein oder andere Juwel hier entdeckt.
Doch nehmen wir einmal an, ich habe mich neu auf pewn registriert und suche nach Spielen, die mich interessieren. Ich gehe in die Spieledatenbank und lasse mir alle Spiele mit dem Hashtag „sciencefiction“ anzeigen – wow, gerade mal ein Ergebnis, eXperinox. Na gut, es sieht ziemlich gut aus, die Bewertungen sind dementsprechend, vielleicht spiele ich es sogar an und es gefällt mir. Aber: gibt es nicht noch mehr Spiele in diese Richtung, die mir auch gefallen könnten?
Jetzt könnte ich selbst anfangen, nach ähnlichen Spielen zu suchen. Vielleicht komme ich noch auf das Hashtag „scifi“, oder auf die Idee nach weiteren „weltraum“-Spielen zu gucken. Vielleicht aber auch nicht. Das ist der Punkt, an dem Empfehlungssysteme ansetzen. Nicht den User suchen lassen, sondern dem User schon passende Spiele vorschlagen, bevor er überhaupt auf die Idee kommt zu suchen. „Wenn Dir dieses Spiel gefällt, könnten Dir auch die folgenden gefallen…“ – inhaltsbasiertes Filtern nach möglichen, passenden Spielen.
Ich habe mal eine total stupide und naive Implementierung eines solchen Empfehlungssystems vorgenommen und testweise auf die Spiele bei pewn losgelassen. Der Aufwand war überraschend gering und die Ergebnisse überraschend gut. Den Java-Quellcode gibt es auf gitlab, ich werde hier kurz die Grundzüge erläutern und ein paar Ergebnisse präsentieren.
Das Prinzip
Ziel ist es also, zu einem gegebenen Spiel (oder allgemeiner „Item“) aus allen anderen Spielen diejenigen auszuwählen, die „am besten“ dazu passen. Doch wie ermitteln wir, wie gut zwei Spiele zueinander passen?
Das Schöne an pewn ist, dass jedes Spiel Hashtags hinzufügen kann. In je mehr Hashtags zwei Spiele übereinstimmen, desto ähnlicher sind sie sich wahrscheinlich. Schauen wir uns z. B. die drei Spiele eXperinox, Final Cumeda und Realms of Gondar mit ihren Hashtags an:
e: action, mmo, strategie, sciencefiction, weltraum, browsergame, browserspiel
f: action, mmo, strategie, scifi, weltraum, browsergame, simulation
r: simulation
Für jedes Hashtag, das im Spiel vorkommt, schreiben wir eine 1, für jedes, das fehlt, eine 0. Somit erhalten wir die Vektoren
e = (1, 1, 1, 0, 1, 1, 1, 1, 1, 0)
f = (1, 1, 1, 1, 0, 1, 1, 1, 0, 1)
r = (0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
Wie intuitiv klar sein sollte, sind sich eXperinox und Final Cumeda ähnlicher als Realms of Gondar und Final Cumeda. Sie stimmen in vielen Hashtags überein, Realms of Gondar stimmt zwar in 100 % seiner Hashtags mit Final Cumeda überein, hat aber auch nur dieses.
Ein (gutes) Maß zur Bestimmung der Ähnlichkeit ist nun die Kosinus-Ähnlichkeit, bei der die Winkel zwischen den Vektoren berechnet werden. Das liefert:
sim(e, f) = 5/7 = 0,714…
sim(r, f) = 1/sqrt(7) = 0,377…
Die Werte werden sich bei uns zwischen 0 und 1 bewegen, wobei 0 keiner Übereinstimmung entspricht und 1 einer vollständigen.
Werfen wir nun einen Blick auf die Hashtags aller Spiele, so stellen wir fest, dass einige Hashtags von ziemlich vielen Spielen verwendet werden und einige von zum Teil nur einem einzigen. Das Hashtag „windows“ wird z. B. sehr oft verwendet und ist natürlich nicht so aussagekräftig für die Ähnlichkeit zweier Spiele wie das viel seltenere Tag „puzzle“. Das können wir allerdings ausnutzen, um unsere Ergebnisse zu verbessern. Wir schätzen die Wichtigkeit eines Hashtags z. B. durch das „Tf-idf-Maß“ ab. Die Idee: in je mehr Spielen ein Hashtag vorkommt, desto unwichtiger wird es. Wir setzen dann den Wert im Vektor nicht mehr wie oben auf 1, sondern auf das zuvor berechnete Gewicht des Hashtags. Und die Ergebnisse können sich zum Teil sehen lassen.
Ausgewählte Ergebnisse
Mit der vollständigen Implementierung kann jede(r) Interessierte gerne selbst ein bisschen herumspielen, eine Liste der Spiele mit den jeweils 5 besten Empfehlungen ist auch verfügbar (werde ich aber voraussichtlich nicht aktualisieren). Ich werde hier nur kurz auf einige (in meinen Augen) interessante Ergebnisse eingehen.
Kehren wir noch einmal zu unserem Ausgangsbeispiel zurück: Was wird uns nun empfohlen, wenn wir gerade eXperinox betrachten? Final Cumeda, Da Vincis Erbe, PLANExT, Tycoopoli$ und Antares Open World – allesamt Spiele, die in meinen Augen sehr gut passen und die z. T. doch ein bisschen überraschend sind. Tatsächlich hat auch der Hälfte der Spieler, denen eXperinox gefällt, auch mindestens eines der anderen 5 gefallen – wie vom Modell gut vorhergesagt wurde.
Gerade Hashtags wie „Strategie“ und „Simulation“ liefern eine eigene „kleine Wolke“ von 9 Spielen, die sich allesamt gegenseitig „empfehlen“. Da taucht nur ganz selten eine Empfehlung auf, die nicht wirklich reinpasst. Hier sieht man schon einmal, wie hilfreich ein gutes Hashtag ist – am besten einfach mal selbst ausprobieren.
Weitere gute Empfehlungen kann man sogar auch erhalten, wenn ein Hashtag gar nicht existiert, die Zusammenhänge aber dennoch (durch andere Tags) aufgedeckt werden. So vermisse ich zum Beispiel schon seit geraumer Zeit ein Hashtag „pointandclick“ oder so ähnlich. Genügend Spiele, die dafür in Frage kämen, gäbe es. Gatio kündigt sich selbst z. B. mit „GATIO - ein Point & Click Adventure“ an, benutzt ein passendes Tag aber nicht. (Das Hashtag „pac“ wird nur von Gatio verwendet und soll eigentlich „pac-dk“ heißen, wird aber zu „pac“ geparst). Dennoch werden erstaunlich passende Spiele vorgeschlagen: Space Geekz - Die Knusperflockenverschwörung, No Way Out, Sherlock Holmes und die Thorbrücke, Skazka und The Forgotten Time. 3 davon ebenfalls Point & Click Adventure.
Ausblick
Ein inhaltsbasiertes Empfehlungssystem steht und fällt mit dem „Inhalt“, in diesem Fall den Hashtags. Die sind bei vielen Spielen bisher recht schwach, bei vielen sogar nicht einmal vorhanden. Ein gutes Beispiel hierfür ist u. a. das Hashtag „snake“. Limousnake und Battle Snakes verwenden es beide und haben dadurch beide eine sehr hohe Übereinstimmung. Andere Snake-Spiele wie Hexagon-Snake oder der Snake-Klon benutzen es nicht und tauchen deshalb momentan auch nicht als Empfehlungen bei den anderen beiden auf.
Wird das verbessert (z. B. dadurch, dass User Hashtags hinzufügen können oder Entwickler deutlich auf „gute“ und viele Hashtags hingewiesen werden), könnten schon mit wenig Aufwand richtig gute Empfehlungen erreicht werden – und Amazon, eBay, Last.fm, IMDb und viele, viele andere machen vor, wie hilfreich Vorschläge für die Nutzer sind.
Sehr zu empfehlen ist auch der (englische) Wikipedia-Artikel zum Thema: Recommender System.
Wenn Ihnen dieser Blog-Eintrag gefallen hat, gefällt Ihnen vielleicht auch dieser: „Empfehlungssysteme – Teil 2: Kollaboratives Filtern“. 
(Verfügbar, sobald in der pewn-Api auf Bewertungen zugegriffen werden kann.)
