Stellen Sie sich einen 1-zu-1-Wettbewerb (keine Teams) zwischen KI-Bots vor, wie die Google AI Challenge . Den verschiedenen Bots wird eine ELO-Bewertung zugewiesen, die auf dem Ergebnis der verschiedenen Versus-Matches basiert. Der Grund, warum ich KI-Bots spezifiziere, da sie rund um die Uhr ohne Rücksicht auf Spielerermüdung, Geolokalisierung usw. antreten können.
Bei begrenzten Serverressourcen können nur so viele Kämpfe pro Tag ausgeführt werden. Ich suche nach einer Heuristik (oder einem optimalen Algorithmus), um zu entscheiden, welche zwei Bots als nächstes konkurrieren sollen.
Alle vergangenen Wettbewerbe wurden verfolgt. Damit meine ich, dass der Algorithmus mehr zu tun hat als nur die ELO-Bewertungen.
Die Anwendungsfälle, an denen ich besonders interessiert bin:
- Die Konkurrenz hat sich seit einiger Zeit zufällig gepaart und jetzt möchte ich eine intelligente Paarungsentscheidung treffen.
- Die Elo-Bewertung hat sich stabilisiert und ein Bot wird aktualisiert.
- Die Elo-Bewertungen haben sich stabilisiert und ein neuer Bot wird in die Konkurrenz eingeführt.
Update:
Ich muss klären. Ich suche keinen Algorithmus, der faire Übereinstimmungen liefert. Ich suche nach einem Algorithmus, der Übereinstimmungen findet, die die Elo-Bewertungen der Bots am wahrscheinlichsten auf ihre "wahren" Bewertungen mit der geringsten Anzahl von Übereinstimmungen aktualisieren .
quelle
Antworten:
Bei einem normalen Elo-System gibt es so etwas wahrscheinlich nicht. Es variiert die Punktzahl basierend auf der Differenz zwischen einer erwarteten Punktzahl und der tatsächlichen Punktzahl. Sie können also sehen, dass Personen mit gleichen Fähigkeiten wahrscheinlich gleichziehen (oder eine 50% ige Gewinnchance haben), um die Punktzahl zu erreichen ändert sich nicht, und wenn Sie komplette Gegensätze kombinieren, schlägt der Veteran fast immer den Neuling (wie erwartet), sodass sich die Punktzahlen auch dort nicht ändern.
Das einzige, was wahrscheinlich dazu führt, dass ein Elo weniger genau punktet als ein anderer, ist, dass er weniger Kämpfe gespielt hat. Dies bedeutet, dass Sie möchten, dass sie mehr spielen. Sie haben noch keine Informationen über ihre tatsächliche Fähigkeitsstufe, daher ist es wichtig, sie dazu zu bringen, in Kämpfe einzutreten und diese Stufe festzulegen.
Unter diesen Bedingungen würde ich mich einfach dafür entscheiden, sicherzustellen, dass Bots so viele verschiedene Bots wie möglich spielen, einen Bot auswählen, gegen den sie noch nicht angetreten sind, und die Auswahl von Bots bevorzugen, die nicht viel gespielt haben. Neue Bots, die dem System beitreten, sollten bevorzugt werden, um schnell ihre ungefähren Werte zu ermitteln.
quelle
Ich weiß, dass Sie bereits eine Antwort markiert haben, aber um ehrlich zu sein, ist sie zu stark vereinfacht und behandelt keines der Kernprobleme eines ELO-Systems, egal ob Sie es mit Bots oder echten Spielern zu tun haben. Die wichtigsten Überlegungen bei der Erstellung eines fairen / genauen ELO-Systems wären beispielsweise: Anzahl der Spieler, Anzahl der Spiele, relative Auswirkung der Fähigkeiten (dh Zufall) auf das Ergebnis, Effizienz der Matchmaking und wie unterschiedlich die Bewertungen pro Sieg sind /Verlust.
In einer idealen Welt könnten Sie Menschen mit gleichen Fähigkeiten erreichen, und in einem Geschicklichkeitsspiel würden sie eine Gewinnrate von 50% erreichen. Dies setzt jedoch voraus, dass Sie die Fähigkeiten aller kennen und dass die Auswirkungen des Zufalls relativ gering sind. Da Sie das erstere nicht kennen (und das letztere nicht spezifiziert haben), müssen Sie eine Reihe von Dingen tun, um die Fähigkeiten auf effiziente Weise genau zu bestimmen, und es ist nicht so einfach wie das Spielen von Bots viele verschiedene Bots wie möglich:
1) Sie müssen eine Grundlinie für Fertigkeiten für "neue" Spieler auf einer Skala einrichten, die sich nach oben oder unten bewegen kann und die Grundlinie den erwarteten Durchschnitt einer normalen Glockenkurve darstellt. IE: 1250 auf einer Skala von 1-2500.
2) Neue Spieler müssen eine bestimmte Anzahl von "Platzierungs" -Spielen spielen, um ihre anfängliche Bewertung festzulegen. Dies erfolgt normalerweise in 10 bis 20 Spielen, die stärker bewertet werden als nachfolgende Spiele. IE: Der Gewinn / Verlust der Bewertung ist bei Platzierungen doppelt so hoch wie später, um eine schnelle Trennung der Spieler zu fördern.
3) Sie müssen andere Faktoren in Ihrem Matchmaking berücksichtigen, wie z. B. die Gewinnrate im Verhältnis zu den Gesamtspielen, damit Spieler an den äußersten Enden der Fertigkeitskurve schneller zu ihrer "wahren" Fertigkeit bewegt werden, indem sie sich Personen gegenübersehen, die höher oder niedriger liegen ihre aktuelle Bewertung. IE: Ein Spieler mit einer Gewinnrate von 80% über eine anständige Stichprobengröße sollte sich Personen stellen, die weiter über seiner Bewertung liegen, und die Leiter schneller erklimmen als jemand mit einer Gewinnrate von 55%, die näher an seiner wahren Fähigkeit liegt.
4) Sie müssen ein gutes Verständnis dafür haben, wie sich der Zufall auf das Ergebnis auswirkt, und Sie müssen die Matchmaking-Geschwindigkeit (Warteschlangenzeiten) berücksichtigen, wenn Sie bestimmen, wer übereinstimmen soll, um die Varianz der Fertigkeiten angemessen zu halten. Bei Verwendung der vorherigen Skala sollte unter keinen Umständen ein 1250-Spieler einem 2000-Spieler gegenüberstehen (außer wenn beide nicht bewertet sind). Es ist kein faires Match-up und es erlaubt Ihnen nicht, Punkte genau zu ihrem ELO hinzuzufügen / daraus zu entfernen.
Die Art und Weise, wie ich ein System einrichten würde, wäre, zwei Modifikatoren für einen Basispunkt-Gewinn / Verlust-Wert zu erstellen, einen unter Verwendung des erwarteten Ergebnisses basierend auf der Bewertungsvarianz und einen basierend auf einer Gewinnrate zum Gesamtübereinstimmungswert. IE: Jemand mit einer Bewertung von 1500, der eine Gewinnrate von 70% hat, die einen Spieler mit einer Bewertung von 1600 übertrifft, erhält mehr Punkte für eine hohe Gewinnrate UND für das Schlagen eines Spielers mit einer höheren Bewertung.
Dann müssen Sie nur noch sicherstellen, dass die Spieler eine angemessene Stichprobengröße von Spielen vervollständigen, und Sie erhalten das "effizienteste" System, basierend darauf, wie viel Chance in dem "Spiel" steckt, für das Sie das ELO-System implementieren. Ein Spiel mit relativ geringer Chance könnte nur ein paar Dutzend Spiele dauern, um genau zu sein, ein Spiel mit relativ hoher Chance könnte Hunderte ...
PS: Für die Aufzeichnung möchten Sie nicht, dass Leute mit drastisch unterschiedlichen Fähigkeiten spielen, weil dies nur die Genauigkeit des Systems beeinträchtigt. Selbst wenn Sie es so verzerren, dass Übereinstimmungen über einer bestimmten Varianz nur sehr geringe Auswirkungen haben, entstehen Probleme, da sich die Spieler für Spiele mit hoher Varianz entweder nicht belohnt oder übermäßig bestraft fühlen.
edit: Ich habe vergessen, den "bereits bewerteten" Teil Ihrer Frage anzusprechen, aber es ist ziemlich einfach. Sie stimmen mit Personen überein, die auf der nächstgelegenen in der Warteschlange verfügbaren Fähigkeitsbewertung basieren, da dies die gleichmäßigste Übereinstimmung ist und der Gewinn / Verlust von Punkten (unter der Annahme ähnlicher Gewinnraten) der statische Wert ist. Wenn die Spieler genau bewertet werden, behalten sie die Gewinnrate von 50% bei und steigen oder fallen weder. Wenn nicht der Fall ist, gewinnt der erfahrenere Spieler mehr als verliert und seine Bewertung wird aktualisiert.
Die Einführung eines neuen Spielers ist noch einfacher. Sie beginnen an der Grundlinie und werden mit Spielern dieser Fähigkeit (mit erhöhtem Gewinn / Verlust) verglichen, bis ihre Platzierungen abgeschlossen sind. Nehmen wir also an, dass der normale Punktgewinn / -verlust pro Spiel 15 ohne Modifikator beträgt. Hier ein Beispiel für die Platzierung und Bewertung neuer Spieler (mit doppeltem Gewinn / Verlust):
quelle