Hackathon Linux Day 2022
In questo post vi racconterò come ho vinto l’hackathon del Linux Day 2022.
In realtà non l’ho vinto tutto da solo, ma con l’aiuto del mio team composto da me, Michelino e Peppe.
La challenge, organizzata dalla par-tec, consisteva nel progettare e implementare un agente che giocasse a battlesnake.
Per chi non conoscesse battlesnake (io in primis non l’avevo mai sentito nominare prima) è un gioco dove ogni giocatore implementa delle (web) api che consentono al proprio snake di giocare contro gli altri.
L’ultimo che sopravvive, vince!
Le regole del gioco sono:
- Ad ogni turno, ogni snake dovrà decidere (dato lo stato interno della mappa) quale mossa fare. Se non risponde, o se risponde in maniera non conforme alle interfacce, verrà eliminato.
- Ogni serpente ha una vita, indicata con un numero da 0 a 100. Ad ogni turno la vita cala di una certa quantità. Se la vita scende a 0, il serpente muore.
- Per ripristinare la vita bisogna mangiare uno dei frutti presenti sul tavolo.
- Se la testa di un serpente collide con il corpo di un altro (o con il proprio) oppure contro uno dei bordi, esso muore.
- L’ultimo serpente in vita vince la battlesnake!
Fase 1 - Setup
La prima fase della challeng consisteva nel istanziare un agente, in maniera coerente con lo standard.
Una passeggiata!
Questo era la nostra configurazione.
|
|
Il nome del nostro eroe era MrPeroni, da cui il nome del team: Team Peroni.
Fase 2 - First steps
La seconda fase consisteva nello scrivere un primo agente (banale) che sopravvivesse (in solitaria) almeno 100 turni.
Dato che a disposizione avevamo pochissimo tempo (meno di un’ora se non ricordo male) abbiamo tutti quanti adottato l’aproccio “cerca di non morire”, oppure “evita gli ostacoli”. Banalmente, la strategia era questa:
- Guardati intorno.
- Tra le 3 possibili direzioni, scarta quelle pericolose.
- Se ci sono mosse caute disponibili, scegline una a caso, altrimenti muori :(
Facile no?
Per far compiere l’azione a MrPeroni, bisognava esporre una api che rispondesse quale mossa fare.
Infatti, l’istanza del gioco, fa ad ogni turno una richiesta POST
ad ogni agente, passando un json contenente lo stato globale della mappa.
|
|
Il json game_state
è composto dalle seguenti informazioni:
board
: descrive tutte le informazioni sul “campo di battaglia”:food
: la lista delle coordinate in cui si trovano i frutti da mangiare.hazards
: la lista delle coordinate in cui si trovano gli eventuali muri.snakes
: la lista che contiene tutte le informazioni sugli altri player. Utile per sapere dove sono i corpi degli altri serpenti (da evitare).height
: l'altezza della griglia.width
: la larghezza della griglia.
game
: metadati sulla partita (non particolarmente utili).turn
: il turno corrente.you
: descrive tutte le informazioni sul tuo agente:body
: la lista di coordinate del corpo del serpente. Per fortuna ordinate dalla testa alla coda.customizations
: lo stile dello snake.head
: le coordinate della testa, ovveroyou.body[0]
.health
: vita (da 0 a 100) del serpente.id
: numero seriale identificativo.length
: lunghezza del serpente, ovveroyou.body.length
.- altro…
|
|
A questo punto, l’algoritmo da implementare è abbastanza semplice.
- Step 0. Scarto la mossa che farebbe collidere la testa di MrPeroni col suo collo.
- Step 1. Scarto tutte le mosse che farebbero uscire MrPeroni dalla mappa.
- Step 2. Scarto le mosse che farebbero collidere MrPeroni con se stesso (caso generale dello Step 0).
- Final Step. Se ci sono mosse rimanenti, ne scelgo una a caso, altrimenti decido la mossa
vai giù
(tanto qualsiasi mossa porterebbe MrPeroni verso la morte).
|
|
Ho deciso di non implementare un controllo per evitare gli altri serpenti perché in questo step ancora non ce ne sono: si gioca in solitaria.
Alcuni di voi potrebbero pensare:
“Ma perché, tra le mosse disponibili, ne scegli una totalmente a caso? Se c’è un cibo vicino, perché non mangiarlo?"
Beh potrebbe essere una strategia ragionevole quella di scegliere, tra le mosse disponibili, quella di mangiare (se presente del cibo nelle vicinanze). Anche perché la vita del serpente diminuisce di turno in turno se non si mangia, e quando arriva a 0 si perde.
Però, euristicamente, abbiamo notato che mangiando sempre si moriva più in fretta. Infatti, mangiando troppo spesso MrPeroni diventava lungo molto velocemente, e quando era troppo lungo facilmente finiva per incastrarsi da solo!
Visto che comunque muovendosi a caso ogni tanto capitava di mangiare, era davvero poco probabile morire di fame. E dato che la crescita di MrPeroni era “rallentata”, la sua durata di vita migliorava.
Ed ecco che a mani basse passiamo anche il secondo turno, entrando a gamba tesa nella fase finale della gara!
Fase 3 - Facciamo sul serio
Arrivati alla fase finale bisognava far combattare tra di loro le diverse squadre!
Dato che ci siamo presi una bella pausa pranzo, avevamo a disposizione poco più di un’ora e mezza per migliorare MrPeroni in modo tale da poter essere minimamente competitivo.
Da buon informatico appassionato di algoritmi, sono partito dal modellare lo stato della mappa come un grafo.
Tutto è un grafo!
Step 1
Come prima cosa ho rappresentato il campo di gioco come un grafo a griglia, dove per ogni cella $(i,j)$ c’è un nodo $v_{i,j}$, e per ogni coppia di celle **adiacenti** $(i,j), (h,k)$ c’è un arco $(v_{i,j}, v_{h,k})$.
|
|
Step 2
Dopodiché, rimuoviamo tutti i nodi che possono rappresentare ostacoli.
|
|
Anche il corpo di MrPeroni stesso può rappresentare un ostacolo, infatti deve essere rimosso. L’unico pezzo di corpo che NON deve essere rimosso è la testa di MrPeroni. Infatti la sua testa non deve essere rimossa per due motivi:
- La testa di MrPeroni non può schiantarsi sulla sua stessa casella.
- Il nodo rispettivo alla testa di MrPeroni ci sarà utile come punto di partenza per una visita sul grafo della mappa di gioco.
Il codice corretto è quindi
|
|
Step 3
Modellizzata la nostra istanza, siamo ora in grado di calcolare la mossa da fare ad ogni turno.
L’idea di base è molto semplice:
- faccio partire una visita in ampiezza radicata nel nodo $v_{\text{head}}$ che rappresenta la **testa** di MrPeroni. Dato che il grafo è **non pesato**, allora l'**albero BFS** risultante equivale esattamente allo **Shortest Path Tree**.
- Se nel BFS-tree risultante è presente almeno un nodo cibo $x$, allora come mossa successiva percorriamo il primo passo del cammino minimo $v_{\text{head}} \leadsto x$.
- Se invece nessun nodo cibo è raggiungibile non ci resta che adottare la politica “cerca di non morire finché un cibo non risulterà raggiungibile”.
Nella figura in esempio ci sono ben 3 cibi raggiungibili.
Scegliamone uno a caso, per esempio quello in coordinata $(0,1)$.
La mossa di MrPeroni in questo turno sarà quindi UP
.
Euristica
Facendo alcuni test abbiamo notato che MrPeroni tendeva a morire più frequentemente quando era vicino ai bordi. Infatti, se il serpente è vicino ai bordi è più probabile che finisca in un “vicolo cieco”, andando così incontro alla sua morte.
Perciò come euristica abbiamo pensato che sarebbe stato più ragionevole scegliere di mangiare i cibi nella regione più centrale della mappa.
Applicando questa euristica abbiamo notato un notevole incremento del 25%-30% nella longevità di MrPeroni.
|
|
Possibili miglioramenti
Anche se ci si avvicina parecchio, MrPeroni non è un essere perfetto: può essere migliorato!.
Un’ulteriore euristica che si può adottare è quella precedente del “mangiare poco”, ovvero non buttarsi in maniera aggressiva sul cibo ad ogni turno.
Nello specifico sarebbe più ragionevole andare alla ricerca di cibo solamente quando la vita di MrPeroni scende sotto una certa soglia critica (per esempio sotto il 75%), evitando quanto possibile il cibo.
Un’altra euristica invece si basa sulla scelta del cibo da raggiungere. MrPeroni usa la politica “il più vicino al centro/lontano dai bordi”, però non è l’unica polita ragionevole. Osserviamo che l’albero bfs radicato sulla testa del serpente ha al più 3 sottoalberi, perché dalle mosse “safe” dobbiamo rimuovere per forza il collo. Un polita ragionevole potrebbe quindi essere quella di scegliere, tra i sottoalberi che contengono del cibo, il sottoalbero più grande. L’idea è che se mi dirigo in un sottoalbero piccolo potrei finire facilmente in un vicolo cieco.
Insomma, ci possono essere una infinità di miglioramente che potevamo fare al nostro eroe, però purtroppo il tempo era poco (circa un ora e mezza) e questo è il meglio che siamo riusciti a progettare, implementare e testare.
Se hai qualche idea su come poterlo migliorare sei invitato a contattarmi, e ne discuteremo davanti a una birra (offro io).
Final code
Il codice finale della funzione move
è una cosa del genere:
|
|
La resa dei conti
È arrivato il momento che MrPeroni dimostri la sua superiorità!
Non ci sono parole per la magnificenza di MrPeroni, quindi lascio che le testimonianze video parlino.
L’emozione di vedere MrPeroni, la mia creatura malvagia, distruggere letteralmente la concorrenza è stato indescrivibile.
Ma l’emozione più grande non è conseguenza della gloria della vittoria, quanto nell'umiliazione dei “nemici”. Infatti una cosa non vi ho ancora detto: eravamo nella struttura di ingegneria contro tutti ingegneri informatici!
Eravamo in territorio nemico e circondati, però ne siamo usciti vincitori nel migliore dei modi: 9 partite vinte su 10, di cui l'unica persa è stato perché MrPeroni si è “ammazzato” da solo (un auto goal insomma).
Informatica vs Ing. Informatica
Nessuno vuole ammetterlo pubblicamente, ma la differenza tra informatici ed ingegneri informatici (in italia) esiste!
La vera differenza non sta nelle conoscenze, perché bene o male noi e gli ingegneri informatici studiamo più o meno le stesse cose, ma nel mindset cln cui affrontiamo l’informatica.
Noi informatici, essendo una branca della matematica, studiamo in maniera rigorosa e formale l’informatica, soprattutto gli algoritmi. L’ingengere fa invece uno studio degli algoritmi meno formale, concentrandosi di più sul loro utilizzo: come si dice in questi casi fanno un utilizzo black box degli algoritmi.
Dato che da quando ho iniziato a studiare informatica campo a “pane e grafi”, mi è venuto immediato e naturale modellizzare il problema come un problema di visita su grafi. Cosa che nessuno degli altri concorrenti ha fatto, nemmeno gli esperti della par-tec che hanno voluto partecipare.
Non che la mia sia una soluzione geniale.
Tuttaltro, è una idea banalissima!
Andando a vedere i codici degli altri team che hanno partecipato, altro non erano che una seria di if-then-else
statements: erano un enorme switch-case
code!
Non voglio assolutamente criticare gli ingegneri informatici, anche perché ne conosco alcuni di cui nutro un profondo rispetto. Allo stesso modo non voglio esaltare gli informatici: conosco informatici il cui rispetto (professionale) da perte mia è meno che nullo…
È inutile anche criticare la disciplina dell’ingegneria informatica, alla fine è un modo di fare informatica. Infatti nel resto del mondo non esiste tutta questa distinzione tra informatica ed ingegnere informatico come in Italia.
Quello che critico è che l’informatica è in primis una scienza, e in quanto tale deve essere fatta in maniera formale.
Ciò che l’informatica in quanto scienza pone nelle menti degli studenti che la studiano è il mindset agloritmico.
Ecco cosa vedo che spesso manca agli ing. ingormatici, l’approccio algoritmico!
Dato che in informatica alla fine tutto è un algoritmo (anche il computer è un algoritmo), ritengo sia inaccettabile non avere questo modo di vedere il mondo.
Invece il processo di “rendere reale” l’informatica per me è fare ingegneria.
Ritengo sia sbagliato che in Italia ci sai questa distinzione tra queste due discipline.
Il vero Informatico è sia uno scienziato che un ingegnere.
Il vero Informatico (con la I
maiuscola) deve essere in grado di modellizzare un probelma in maniera formale, progettare un algoritmo che lo risolva ed analizzarne correttezza e complessità, ma deve anche essere in grado di implementarlo, in modo che tutto il lavoro formale fatto possa essere utilizzato.
Effettivamente non so quanto in realtà venga fatta bene la teoria e la pratica nelle rispettive facoltà (sicuramente varia anche da università a università), ma so che se proprio devo scegliere tra un percorso teorico ed uno pratico sceglierei quello teorico. Questo perché:
Infatti, nonostante la mia predisposizione per le tematiche teoriche, mi ritengo comunque abbastanza competitivo anche dal punto di vista pratico. Questo perché impiego lo stesso tempo ed interesse per studiare argomenti teorici e pratici nella mia giornata.
La differenza è che: tutte le tecnologie che conosco le ho imparate da solo, grazie anche alle solide basi teoriche che ho acquisito. Non penso però che avrei potuto imparare quanto so di teroico con le sole conoscenze pratiche…
Questa tematica è a me molto cara, e sicuramente ne parlerò meglio in un futuro blog post.