Strategia / algoritmo per dividere equi team in base alla storia

La prima cosa da considerare, questa è per qualcosa di casuale. Non sta progettando un sistema per determinare i round per la coppa del mondo di palla da pavimento. Si tratta di giochi casual di raccolta con un gruppo di persone che amano un buon gioco piuttosto che una vittoria sbilenca.

Ricordo qualcosa di Google che ha un generatore di scommesse su calciobalilla. Un bel po 'di lavoro è stato fatto su quello che sto facendo su questo. Cercando una soluzione per questo, ho trovato un articolo in SO e un True Skill calcolatrice utilizzata da Microsoft per la xbox .

Adottando un approccio molto più semplicistico, ogni giocatore ottiene il punteggio del rapporto tra i punti della propria squadra per il gioco. Per la partita 1, il giocatore A otterrebbe 1,25 (10/8) mentre il giocatore D otterrebbe 0,8 punti (8/10). Trova la media di tutti i numeri e questo è il punteggio del giocatore.

Per il set di giochi descritto, questo fornisce:

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

A questo punto, hai un problema simile a quello del problema di partizione con il vincolo che ogni squadra ha bisogno del lo stesso numero di giocatori e di valori non deve essere esatto (ma il più vicino possibile).

Approccio rapido e sporco:

Calcola un punteggio per ogni giocatore che è il totale dei punti per il lato su cui quel giocatore è stato diviso per il totale dei punti nel gioco per ogni partita a cui hanno partecipato. Quindi ordina i giocatori per punteggio. Posiziona il primo giocatore della squadra A. Quindi, per ogni giocatore, aggiungili alla squadra con il punteggio aggregato più basso fino a metà dei giocatori in una squadra. Tutti i giocatori rimanenti vanno nell'altra squadra.

Se non vuoi scavare nel mondo inebriante di Bayesian priors (pdf) e questo, un approccio interessante è quello di assegnare un ordine totale a tutti i giocatori (basato su razione di vincita / perdita, punti cumulativi, ecc.) E poi dividersi in i team che utilizzano la funzione di parità come segue.

Prendi l'elenco ordinato dei giocatori (il meglio per il peggio) e separali in gruppi pari e dispari in base al numero di 1 bit nel loro indice (a partire da 0). Ciò fornisce la seguente distribuzione:

• 0000 (migliore) - Anche
• 0001 - Dispari
• 0010 - Dispari
• 0011 - Anche
• 0100 - Dispari
• 0101 - Anche
• 0110 - Anche
• 0111 - Dispari

... etc.

La funzione parità assicurerà un numero uguale di giocatori per ogni squadra, per ogni numero pari di giocatori. Si alternerà quindi dando il vantaggio del giocatore numerato dispari a una squadra o l'altra in modo tale che gli effetti tendono a bilanciarsi nel tempo.

Questa funzione funziona meglio quando la distribuzione delle abilità del giocatore è piatta. In realtà, l'abilità del giocatore tende a seguire la distribuzione di "somma di valori casuali", a.k.a il gaussiano (sebbene si guardino da applicazioni coperte di tale ipotesi in sistemi come TruSkill).

Per compensare lacune di grandi abilità, è possibile applicare permute a questo elenco. Ad esempio, per contrastare un giocatore superiore molto strong 0000, puoi scambiare il giocatore 0011 con un giocatore Odd di livello più basso, come ad esempio 0100. Qui è dove le cose si fanno mano ondulate, ma almeno fornisce un buon punto di partenza che non richiede una misura accurata dell'abilità assoluta, ma semplicemente un ordinamento basato sull'abilità relativa.

A seconda di quanto tempo hai, inizia le prime sessioni selezionando casualmente i capitani delle squadre e disponi di una bozza prima di ogni partita. Tieni traccia di quale giocatore sceglie un giocatore. I pronostici precedenti ottengono punteggi più alti:

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

Winning a game = 5 pts

Tutto dipenderà dal numero di giocatori per squadra. I punti totali potrebbero dover essere convertiti in una media giornaliera o di gioco se c'è una grande discrepanza nella partecipazione. Puoi anche assegnare una squadra per un maggiore margine di vittoria.

I giocatori selezionati in anticipo e giocati su una squadra vincente ottengono il maggior numero di punti di forza.

Quindi lascia che il computer faccia la stesura (selezionando le squadre) bilanciando i punti di potenza per ogni squadra e mettendo i team con punteggi quasi uguali l'uno contro l'altro. I giocatori che vengono selezionati in anticipo, ma continuano a giocare nelle squadre perdenti cadrà nelle classifiche.

La soluzione più semplice sarebbe quella di fornire una valutazione / peso dell'abilità stimata e cercare di bilanciare il punteggio per ogni squadra.

Da lì, potresti seminare una rete bayesiana con questi valori e quindi potresti dedurre il backward in base al risultato osservato di ogni matchup nei dati storici che hai.

Come punto di interesse da parte mia: Infer.NET rende questo relativamente facile da immaginare e potenzialmente implementare, e potrebbe predire le probabilità di una vincita dato i matchup della squadra. Infer.NET è qualcosa che sto iniziando davvero a conoscere ultimamente.

Supponiamo che nell'interesse della discussione sia possibile assegnare ad ogni giocatore un valore intero e questi valori si sommano, cioè un giocatore con punteggio X vale quanto tre giocatori con punteggi A, B e C, se A + B + C = X. L'obiettivo è quindi di separare il gruppo in due squadre in modo che entrambe le squadre abbiano all'incirca il valore di somma uguale.

Questa è la versione di ottimizzazione del famoso problema di PARTITION che è NP-completo. Pertanto, il tuo problema è per tutto ciò che sappiamo difficile da risolvere. Tuttavia, PARTITION è debolmente NP-completo e ammette alcune strategie di approssimazione ragionevoli.

Un esempio è un approccio avido simile a quello che Steven propone. Questa è un'approssimazione di 4/3, cioè la squadra più strong non è mai più di circa il 33% più strong di una divisione ottimale.

Nota che probabilmente hai vincoli aggiuntivi, ad esempio hai bisogno di almeno un numero fisso di giocatori per squadra. Quindi, se metti Michael Jordan in una classe di bambini in età prescolare, non sarai in grado di creare squadre quasi giuste con un numero intero. Un tale limite inferiore (costante) sulla dimensione della squadra non dovrebbe influire sulla durezza del problema sottostante ma potrebbe distruggere i limiti di approssimazione validi per il problema generale.

Quanto vuoi essere ridicolo? È sempre possibile utilizzare regressione lineare multipla per generare coefficienti per ciascun giocatore in base ai punteggi delle proprie squadre nei giochi precedenti. Quindi ordina l'elenco e seleziona.

In realtà probabilmente non funzionerebbe dato che non modella la dinamica tra i giocatori, ma ti darà una ragione per giocare con R . (< - guarda, ho mantenuto la programmazione correlata)

Se vuoi che il tuo algoritmo sia ragionevolmente, semplici algoritmi non lo taglieranno. Ti daranno spesso strani risultati

Dovrai utilizzare qualcosa come ELO o Trueskill (ELO lo fa non funziona per le squadre senza modifiche, però).