TdP-prove-finali / Introduzione

Istruzioni e documentazione per la proposta e lo svolgimento delle prove finali relative al corso di Tecniche di Programmazione.
http://bit.ly/tecn-progr
Apache License 2.0
4 stars 13 forks source link

Creazione di un Tool per la risoluzione automatica di Sifde Creazione Rosa FIFA #39

Closed AlbertoDeBenedictis closed 4 years ago

AlbertoDeBenedictis commented 4 years ago

Studente proponente

s245313 Alberto De Benedictis

Titolo della proposta

Tool per la risoluzione automatica di Sifde Creazione Rosa FIFA

Descrizione del problema proposto

Nel celebre gioco di calcio per console è presente la modalità di gioco Ultimate Team, in cui ogni utente deve gestire le proprie risorse (crediti) per formare la sua squadra ideale, da utilizzare nelle competizioni amatoriali e professioniste. Nelle cosiddette "sfide creazione rosa", viene richiesta una rosa di 11 giocatori (ognuno di questi deve essere acquistato sul mercato, se non è già in possesso dell'utente) che soddisfi determinati requisiti, da scambiare per una ricompensa in crediti (o altro). Trovare la giusta combinazione degli 11 giocatori spesso può diventare una procedura lunga e onerosa, pertanto l'utilizzo di un algoritmo per la soluzione potrebbe giovare a un grande numero di utenti.

Descrizione della rilevanza gestionale del problema

La risoluzione in modo ottimale di un tale tipo di sfide è uno dei metodi più efficaci per ricavare un profitto in crediti(inteso come RICOMPENSA_SFIDA_COMPLETATA - SPESA_GIOCATORI) considerevole in poco tempo. Considerando che EA Sports permette l'acquisto di "FIFA Points" a prezzi poco competitivi e con una resa in crediti molto bassa (Statisticamente si possono ottenere 100.000 crediti con una spesa di 50 €)**, l'utilizzo di questa applicazione permetterebbe all'utente medio di accumulare abbastanza crediti per formare una squadra competitiva in poco tempo.

** Nelle fasi iniziali del gioco, un giocatore come dybala costa 400.000 crediti, mentre un top player come Cristiano Ronaldo può costare 2-3 milioni di crediti.

Descrizione dei data-set per la valutazione

https://www.kaggle.com/stefanoleone992/fifa-20-ultimate-team-players-dataset

Dataset pubblico, estratto dal sito www.futbin.com, nel quale sono presenti diverse statistiche rilevanti ai fini dell'analisi. Per ogni giocatore, avremo a disposizione una serie di informazioni, tra cui le più importanti:

Verrà probabilmente utilizzato anche un dataset di moduli (da creare ad hoc), che specifica l'elenco dei ruoli e delle connessioni (si veda il punto successivo per chiarezza) per ogni modulo.

Descrizione preliminare degli algoritmi coinvolti

Per affrontare in modo efficiente il problema, la rosa di 11 giocatori può essere assimilata ad una grafo con 11 vertici. La struttura del grafo varierà in base alla scelta del modulo (input dell'utente). Sebbene i vertici (rappresentati dai giocatori) siano sempre 11, gli archi che collegano i vertici (e la densità del grafo, in generale) sono soggetti a cambiamenti in base al tipo di modulo utilizzato (difesa a 3, utilizzo di una sola punta, etc.).

(Per una visualizzazione più chiara del problema, con l'ausilio delle immagini: https://www.easports.com/it/fifa/ultimate-team/features/squad-building-challenges )

L'algoritmo ricorsivo principale si occuperà di provare combinazioni di 11 giocatori che soddisfino i vincoli imposti dall'utente. Il vincolo principale sarà il modulo da utilizzare: la scelta del modulo influenzerà in modo decisivo l'esecuzione del programma, poichè a ogni modulo è associato un grafo di tipo diverso. In particolare, questi potrebbero essere alcuni dei vincoli presenti:

L'intesa della squadra è un parametro che rappresenta l'affinità tra i giocatori in campo: come accade nel calcio giocato, giocatori che abbiano giocato insieme (nello stesso campionato, nella stessa squadra o magari in nazionale) hanno maggiore affinità. Il valore dell'intesa varia da 0 a 10 per ogni giocatore, da 0 a 100 per la squadra. Questo parametro viene modellizzato considerando degli archi pesati: il peso dell'arco in questo caso rappresenta la qualità del collegamento tra due giocatori. Nell'interfaccia del gioco viene espressa con collegamenti di colore diverso (rosso, arancione, verde). Nel programma si potrà fare riferimento a collegamenti di livello (PESO) 0,1,2. In particolare:

Oltre all'algoritmo ricorsivo che ricerca una soluzione, è prevista l'implementazione di un'altra funzione che cerca di ridurre la spesa totale richiesta dalla soluzione trovata. A livello operativo, la soluzione dovrà percorrere il grafo soluzione, e per ogni vertice cercare un'alternativa equivalente di prezzo minore. (Esempio: sostituire un centrocampista francese che gioca nella Premier League che costa 2000 crediti con un centrocampista della stessa nazione e campionato che però costa 1400).

Descrizione preliminare delle funzionalità previste per l’applicazione software

L'utente inserirà come parametri il budget che vuole destinare alla sfida, il modulo della rosa e l'intesa minima della squadra (vincoli obbligatori), più una serie di vincoli opzionali. Nell'interfaccia sarà presente un pulsante (button) "Trova Soluzione" che avvierà l'algoritmo di ricerca della risoluzione ottimale (rosa che soddisfi i vincoli). Se viene trovata una soluzione che rientra nel budget, il programma restituirà la rosa ottimale con la lista dei nomi giocatori, accompagnata dai relativi prezzi; in caso contrario, verrà mostrato il gap tra il budget destinato e la soluzione trovata. Il secondo button "Riduci il costo" può essere premuto solo dopo aver trovato una soluzione (a prescindere dal fatto che rientri nel budget o meno): questa funzione restituirà (se possibile) una variante della soluzione più economica, ottenuta sostituendo alcuni componenti della rosa.

fulcorno commented 4 years ago

Non ci capisco nulla di FIFA, e molto poco di calcio, ma mi sembra che il problema sia interessante e ben formulato. Puoi procedere con il lavoro. Farei attenzione alla complessità della ricorsione, visto che devi selezionare 11 giocatori da un insieme di centinaia di giocatori possibili (11^100 è un bel numero...).