In questo articolo andremo a osservare e commentare la challenge proposta su https://www.codingame.com/multiplayer/bot-programming/spring-challenge-2021 e alcune interessanti strategie per risolverla.

Codingame è un sito estremamente affascinante, che raccoglie sfide di ogni genere che non solo possono risultare piuttosto dilettevoli, ma allenano la capacità di creare algoritmi e di codificare gli stessi in diversi linguaggi.

Da code golf all’ottimizzazione, su codingame.com ci si può cimentare nella risoluzione di problemi di diverso tipo, ma quelli che più ci interessano riguardano la scrittura di Ai.

Il sito presenta due volte all’anno una challenge di 10-11 giorni in cui i bot (programmi Ai) di due programmatori dovranno scontrarsi per scalare la classifica.

La challenge di quest’anno fa impersonare dai nostri codici uno spirito della foresta ispirato dall’iconico Totoro di Hayao Miyazaki, il suddetto spirito, istruito dai nostri comandi, dovrà gestire il ciclo naturale della semina, crescita e passaggio a miglior vita degli alberi della sua radura. In questo articolo andremo a parlare degli algoritmi a livello logico che permettono di superare le leghe “legno II”, “legno I” e “bronzo”, ma sarete voi a dovervi ingegnare per codificare queste strategie, poi per argento e oro vi serviranno idee tutte vostre.

Tutti gli esempi di codice, e le citazioni alle variabili riportate in questo articolo saranno in python3.

Le regole…

Qui riportiamo le regole che riteniamo più importanti per la risoluzione (quantomeno logica) del problema. C’è da sottolineare che man mano che il nostro algoritmo avanzerà di lega battendo i vari boss, il gioco si andrà a complicare sempre più, aggiungendo nuove regole.

Innanzitutto conviene scegliere uno Starter Kit scritto nel linguaggio di programmazione che si vuole adoperare, poi possiamo metterci all’opera.

…della lega legno II

• Si possono completare alberi di grandezza = 3
• Si possono fare infinite mosse all’interno di un giorno di gioco
• Completare un albero costa 4 soli
• Ogni albero ci da x punti sole ad inizio turno, dove x è la grandezza dell’albero stesso
• Tutte le mosse legali sono elencate negli input
• La partita dura un giorno
• Si guadagna 1 punto per ogni 3 punti sole risparmiato a fine partita
• Si guadagnano più punti al completamento di un albero se l’albero è piantata in una cella con cell.richness maggiore

La prima lega di una challenge su codingame.com in genere è molto semplice, qui vediamo che gli unici comandi che abbiamo a disposizione sono il completamento con

print("COMPLETE #indicecella")

Dove #indicecella sta per il numero della cella dove risiede l’albero da completare, e

print("WAIT")

Per concludere il proprio turno, quando entrambe le Ai avranno completato il proprio turno, il giorno diventerà il successivo, se game.day sarà uguale all’ultimo giorno della partita, la partita si concluderà.

Ad inizio partita, tutti gli alberi in questa lega saranno di dimensione tre, ovvero saranno completabili.

A questo punto dobbiamo porci la domanda, come facciamo a battere Totoboss?

L’algoritmo per uscire da legno è semplice, dobbiamo semplicemente completare gli alberi in ordine da quelli nella zona con cell.richness maggiore, a quelli nella zona con cell.richness minore.

Ps. in realtà anche eseguendo l’ultima azione disponibile in game.possible_actions, senza sapere ne leggere ne scrivere, siamo riusciti a raggiungere legno I senza sforzi, ma scegliere di completare l’albero migliore ci aiuterà in futuro.

…della lega legno I

• Ci sono 6 giorni di gioco
• Si possono far crescere gli alberi
• Il sole ruota attorno alla radura (un giorno, uno spostamento)

Riportiamo le regole di crescita:

Grow action

• Growing a size 1 tree into a size 2 tree costs 3 sun points + the number of size 2 trees you already own.
• Growing a size 2 tree into a size 3 tree costs 7 sun points + the number of size 3 trees you already own.

Non preoccupiamoci del comportamento del sole per ora

Chiaramente anche qui come prima dobbiamo prediligere la crescita degli alberi su un terreno con cell.richness migliore, e poi completarne il più possibile.

…della lega Bronzo

• Si possono piantare semi
• il costo di piantare un seme equivale al numero di propri semi già presenti in campo
• Gli alberi fanno ombra sulle zone circostanti in base alla propria grandezza.
• Non otteniamo punti sole dagli alberi sotto l’influsso di un’ombra creata da un albero di grandezza uguale o maggiore
• La partita consiste in 24 giornate
• Si ottiene un bonus per ogni pianta completata che diminuisce mano a mano che più piante vengono completate

Il motivo per il quale il sole gira attorno alla radura vi sarà ormai chiaro. Qui il gioco si fa dura, per arrivare ad argento bisognerà fare in modo che:

• I semi che si andranno a piantare copriranno uno spazio ampio, in modo che si eviti il rischio di fare ombra ai propri stessi alberi
• Il costo delle varie azioni deve essere ottimizzato, per riuscire a piantare e completare il numero massimo di piante
• Si completino la piante prima del proprio avversario, per sfruttare a meglio il bonus

Osservando la griglia di debug del campo di gioco, possiamo formulare matematicamente alcune condizioni per svolgere le varie azioni, in modo da adempire ai vari requisiti precedentemente discussi.

Per cominciare, un ottima strategia per evitare di ostacolarsi da soli tramite le ombre, è obbligare l’algoritmo a non piantare in celle che rispondono alla condizione action.target_cell_index in cell.neighbors dove la cella in esame è cell = action.origin_cell_index.

Un altra condizione interessante da implementare è quella che un seme non dovrebbe essere piantato in linea retta (per esempio 25, 11, 3) rispetto ad un altro albero di nostra proprietà, perché nei round futuri esso sarebbe posto all’ombra.

Inoltre siccome piantare un seme non costa punti sole solo se non ci sono altri nostri semi in gioco, conviene piantarne uno solo in questo particolare caso.

Infine riguardo alla tempistica, abbiamo scoperto che iniziare a completare alberi dal round 12 sembra proficuo, mentre fino all’ultimo round è conveniente avere sul terreno sempre almeno 3 alberi, per non rischiare di avere troppi pochi i punti sole generati ad inizio turno. Non eccedere invece mai invece il limite di 6/8 alberi piantati, oltre quel numero le ombre sul campo iniziano a diventare troppe e si rende impossibile tenerne traccia.

Se volete battere il sottoscritto dovete raggiungere le prime 150 posizioni della lega oro.

Buona fortuna per challenge.

Leonardo Bonadimani – Whatar – Filosoft

www.twitch.tv/whatartv