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

20

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
 }]
Vegar
źródło
4
Co to jest piłka do unihokeja?
Dynamiczny
1
Zakładam, że masz tylko wyniki drużynowe, a nie wynik indywidualny?
Gort the Robot
1
@Dynamic: Domyślam się, że to inna nazwa dla hokeja na podłodze - hokej grał na podłodze w sali gimnastycznej z małą gumową piłką zamiast na lodzie z krążkiem (oczywiście bez łyżew).
FrustratedWithFormsDesigner
2
Możesz wyjaśnić, że jedyną informacją, która może być użyta w tym algorytmie, jest liczba zwycięskich / przegranych drużyn, w których był każdy gracz.
TehShrike
2
@TehShrike Dla każdego rozegranego meczu mam informacje o tym, kto grał w jakiej drużynie i jaki był wynik końcowy. Na przykład. {Team1: [„a”, „b”, „c”], Team2: [„d”, „e”, „f”], wynik: „10-5”}
Vegar

Odpowiedzi:

6

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).

Społeczność
źródło
Taka sama liczba graczy lub tak bliska, jak to możliwe, jeśli pojawi się nieparzysta liczba graczy ;-)
Vegar
Dziękujemy za odniesienie do problemu z partycją ! Dajesz czadu, @ user40980
Eric Gopak
3

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.

Gort the Robot
źródło
Takie podejście może działać, nawet jeśli dana kombinacja ludzi jest zupełnie nowa.
Vegar
Robienie lepiej wygląda jak wariant problemu z plecakiem . Wagi mogą być również istotne - z tego, co pamiętam, najcięższy gracz (ja) był zawsze wybierany jako ostatni.
Steve314
To chciwe podejście jest znane z przybliżania 4/3 optymalnego rozwiązania (Wikipedia)
Radek
3

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.

Richard Nelson
źródło
2

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.

JeffO
źródło
Świetna odpowiedź! Może to działać dla przeciętnego zespołu, ale niektóre zespoły są strategiczne. Na przykład, jeśli chcesz, aby cała drużyna była obrońcami, wtedy mielibyście gorszych graczy grających w wyższych rundach. Ale chyba nie prosiłem o kanonikę: P. Dzięki!
Dynamiczny
To świetny sposób na rozpoczęcie. W pierwszych kilku rundach wszystko oparte na wynikach zespołu nie będzie miało zastosowania indywidualnie, ponieważ będziesz mieć członków zespołu, którzy grają razem w każdej rundzie.
Gort the Robot
1

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ć.

Steven Evers
źródło
Czy posiadasz wystarczającą ilość danych, aby mieć sens, że prawdopodobnie będzie tylko garść gier?
Gort the Robot
Miałem nadzieję rozwiązać ten problem za pomocą javascript lub ruby, ale infer.net i tak wygląda interesująco.
Vegar
@StevenBurnap: Zależy od tego, jak dobre / dokładne są twoje początkowe domysły co do umiejętności gracza - co będziesz musiał zrobić dla większości lub wszystkich systemów. Zaletą korzystania z sieci jest możliwość wnioskowania o nowych wynikach dla każdego gracza w miarę upływu czasu w celu poprawy tej wartości.
Steven Evers
1

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.

Raphael
źródło
1
Nie można zmieścić bardzo wielu graczy na podłodze w sali gimnastycznej. Przy 20 graczach, zakładając, że chcesz 10 na stronie, do sprawdzenia jest tylko 92378 kombinacji. Ale nie potrzeba wielu graczy, zanim liczba kombinacji sprawi, że wyczerpujące wyszukiwanie stanie się niepraktyczne.
kevin cline
@kevincline: Right. Domyślnie założyłem, że brutalna siła nie wchodzi w grę (inaczej, po co pytać?).
Raphael
W każdym zespole nigdy nie będzie więcej niż sześć osób. Częściej cztery.
Vegar
@Vegar: Twoje pytanie brzmi: jak wykorzystać wyniki zespołu do modelowania wartości zawodników, a mniej na temat algorytmów, prawda?
Raphael
1
O ile nie uda ci się znaleźć sposobu, aby naprawdę punktować ludzi dokładnie według ich talentu, dokładność algorytmu prawdopodobnie nie jest tak ważna. Przy obecnym problemie mamy tylko wyniki drużynowe i garść prób. Każda ocena gracza będzie szalonym szacunkiem.
Gort the Robot
0

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)

Grandmaster B.
źródło
1
Zastanawiam się nad stworzeniem aplikacji, aby uniknąć 2-minutowego zadania dwa razy w tygodniu, zmuszając mnie do spędzenia prawie takiej samej ilości czasu na zapisywanie wyników do przyszłych obliczeń. Tak absurdalne, jak sądzę ...
Vegar
-1

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).

catbert
źródło
1
To nie jest prawda. Musi istnieć algorytm, który działałby.
Dynamiczny