Strategia / algorytm dzielenia uczciwych zespołów na podstawie historii

Jesteśmy grupą osób regularnie grających w unihokeja. Każda sesja zaczyna się od trudnego zadania dzielenia zespołów ...

Więc co byłoby lepszego niż aplikacja do automatycznego wybierania zespołów?

Więc biorąc pod uwagę historię kombinacji drużyn i wyników oraz listę osób pojawiających się w tej konkretnej sesji, jaka byłaby dobra strategia na znalezienie optymalnych zespołów? Przez optymalne rozumiem zespoły, które są możliwie równe.

Jakieś pomysły?

Edycja: Aby to wyjaśnić, dane, na których muszę opierać wybieranie, byłyby mniej więcej takie:

[{ team1: ["playerA", "playerB", "playerC"],
   team2: ["playerD", "playerE", "playerF"],
   goals_team1: 10,
   goals_team2:  8 
 },
 { team1: ["playerD", "playerB", "playerC"],
   team2: ["playerA", "playerE", "playerG"],
   goals_team1:  2,
   goals_team2:  5
 },
 { team1: ["playerD", "playerB", "playerF"],
   team2: ["playerA", "playerE", "playerC"],
   goals_team1:  4,
   goals_team2:  2
 }]

Pierwszą rzeczą do rozważenia jest to coś na co dzień. To nie jest projektowanie systemu określania rund dla pucharu świata w piłce podłogowej. Jest przeznaczony do codziennych gier typu pick-up z grupą ludzi, którzy lubią dobrą grę zamiast wygranej.

Przypominam sobie, że Google ma generator kursów piłkarzyków. Wykonano na tym trochę więcej pracy niż ja. Szukając wzmianki o tym, znalazłem artykuł w SO i kalkulator True Skill, który jest używany przez Microsoft dla Xboksa .

Przyjmując znacznie bardziej uproszczone podejście, każdy gracz otrzymuje wynik stosunku punktów, które jego drużyna ma do gry. W grze 1 gracz A otrzyma 1,25 (10/8), a gracz D - 0,8 punktu (8/10). Znajdź średnią wszystkich liczb i to jest wynik gracza.

W przypadku opisanego zestawu gier zapewnia to:

  A 1.42
  B 1.22
  C 0.72
  D 1.07
  E 1.27
  F 1.40
  G 2.50

W tym momencie masz problem podobny do problemu partycji z tym, że każda drużyna potrzebuje tej samej liczby graczy, a wartości nie muszą być dokładne (ale tak blisko, jak to możliwe).

Szybkie i brudne podejście:

Oblicz wynik dla każdego gracza, który jest sumą punktów za stronę, na której gracz był podzielony przez całkowitą liczbę punktów w grze dla każdej gry, w której brał udział. Następnie posortuj graczy według wyniku. Umieść pierwszego gracza w drużynie A. Następnie dla każdego gracza dodaj go do drużyny o najniższym łącznym wyniku, aż połowa graczy będzie w jednej drużynie. Wszyscy pozostali gracze wchodzą do drugiej drużyny.

Jeśli nie chcesz zagłębiać się w mocny świat bayorskich priorów (pdf) i tak, ciekawym podejściem jest przydzielenie całkowitego zamówienia wszystkim graczom (na podstawie racji wygranych / przegranych, łącznych punktów itp.), A następnie podzielenie na zespoły korzystające z funkcji parzystości w następujący sposób.

Weź posortowaną listę graczy (od najlepszych do najgorszych) i podziel ich na drużyny parzyste i nieparzyste na podstawie liczby 1 bitów w indeksie (od 0). To daje następującą dystrybucję:

• 0000 (najlepszy) - Parzysty
• 0001 - Nieparzysty
• 0010 - Nieparzysty
• 0011 - Parzysty
• 0100 - Nieparzysty
• 0101 - Parzysty
• 0110 - Parzysty
• 0111 - Nieparzysty

...itp.

Funkcja parzystości zapewni równą liczbę graczy w każdej drużynie, dla dowolnej parzystej liczby graczy. Będzie się wtedy naprzemiennie dawać przewagę nieparzystemu graczowi jednej lub drugiej drużynie w taki sposób, że efekty z czasem się równoważą.

Ta funkcja działa najlepiej, gdy rozkład umiejętności gracza jest płaski. W rzeczywistości umiejętności gracza mają tendencję do podążania za rozkładem „sumy wartości losowych”, czyli Gaussa (choć strzeżcie się ogólnych zastosowań tego założenia w systemach takich jak TruSkill).

Aby zrekompensować duże braki umiejętności, możesz zastosować permutacje do tej listy. Na przykład, aby przeciwstawić się bardzo silnemu najlepszemu graczowi 0000, możesz zamienić gracza 0011 na gracza z nieparzystym rankingiem, np. 0100. To jest miejsce, w którym faliste ręce są faliste, ale przynajmniej zapewnia dobry punkt wyjścia, który nie wymagają dokładnego pomiaru umiejętności absolutnych, ale po prostu uporządkowania na podstawie umiejętności względnych.

W zależności od tego, ile masz czasu, rozpocznij kilka pierwszych sesji, losowo wybierając kapitanów drużyn, i przygotuj draftu przed każdą grą. Śledź, który gracz wybiera. Wcześniejsze typy otrzymują wyższe oceny:

Round #1 = 8 pts, Round #2 = 6 pts, Round #3 = 4 pts, etc

Winning a game = 5 pts

Wszystko to zależy od liczby graczy w zespole. Że suma punktów , konieczne może być przekształcany do średniej dobowej lub gry, jeżeli istnieje duża rozbieżność w udziale. Możesz także nagrodzić drużynę za większy margines zwycięstwa.

Gracze, którzy zostali wybrani wcześniej i grali w zwycięskiej drużynie, otrzymują najwięcej punktów mocy.

Następnie pozwól komputerowi sporządzić projekt (wybór drużyn), równoważąc punkty mocy dla każdej drużyny i ustawiając drużyny o prawie równych ocenach względem siebie. Gracze, którzy zostaną wybrani wcześniej, ale nadal będą grać w przegranych drużynach, spadną z rankingu.

Najłatwiejszym rozwiązaniem byłoby podanie oceny / wagi szacowanej umiejętności i próba zrównoważenia wyniku dla każdej drużyny.

Stamtąd możesz zaszczepić sieć bayesowską tymi wartościami, a następnie wnioskować wstecz na podstawie obserwowanego wyniku każdego pojedynku w posiadanych danych historycznych.

Z mojego punktu widzenia: Infer.NET sprawia, że ​​jest to stosunkowo łatwe do przewidzenia i potencjalnie zaimplementowania, i może przewidzieć szanse na wygraną w pojedynkach drużynowych. Infer.NET to coś, do czego naprawdę zaczynam ostatnio wchodzić.

Załóżmy dla celów dyskusji, że możesz przypisać każdemu graczowi wartość całkowitą, a te wartości sumują się, to znaczy gracz z wynikiem X jest tak samo cenny jak trzej gracze z wynikiem A, B i C, jeśli A + B + C = X. Celem jest następnie podzielenie grupy na dwie drużyny, aby obie drużyny miały w przybliżeniu jednakową zsumowaną wartość.

To jest wersja optymalizacyjna znanego problemu PARTITION, który jest NP-zupełny. Dlatego problem jest dla wszystkich wiemy trudno rozwiązać. Jednak PARTITION słabo uzupełnia NP i dopuszcza pewne rozsądne strategie przybliżenia.

Jednym z przykładów jest chciwe podejście podobne do tego, co proponuje Steven. Jest to przybliżenie 4/3, co oznacza, że ​​silniejszy zespół nigdy nie jest większy niż około 33% silniejszy niż w optymalnym podziale.

Pamiętaj, że prawdopodobnie masz dodatkowe ograniczenia, takie jak potrzeba co najmniej stałej liczby graczy na drużynę. Jeśli więc umieścisz Michaela Jordana w klasie przedszkolaków, nie będziesz w stanie stworzyć prawie sprawiedliwych zespołów, które będą miały pełną liczbę. Taka (stała) dolna granica wielkości zespołu nie powinna wpływać na twardość leżącego u podstaw problemu, ale może zniszczyć granice przybliżenia ważne dla problemu ogólnego.

Jak absurdalnie chcesz się dostać? Zawsze możesz użyć wielu regresji liniowej, aby wygenerować współczynniki dla każdego gracza na podstawie wyników ich drużyn z poprzednich gier. Następnie posortuj listę i wybierz.

W rzeczywistości, to prawdopodobnie nie będzie działać, ponieważ nie modelować dynamikę między graczami, ale to daje powód, by bawić się z R . (<- patrz, utrzymywałem to związane z programowaniem)

Jeśli chcesz, aby Twój algorytm był rozsądny, proste algorytmy po prostu go nie wycinają. Często dają dziwne wyniki

Będziesz musiał skorzystać z czegoś takiego jak ELO lub system Trueskill (ELO nie działa jednak dla zespołów bez modyfikacji).