Battleship AI coding competition 1^ tornata: Strategie degli algoritmi

Kobayashi Maru 1.0  di  Fabio Rocca

Strategia di Attacco.

La strategia di attacco si divide principalmente in due fasi:

1) Ricerca delle Navi

2) Affondamento della nave colpita

 

Nella prima fase i colpi vengono sferrati basandosi principalmente su un pattern a scacchiera (è inutile colpire in tutti i punti della griglia dato che le dimensioni minime delle navi è di 2, si può colpire un colpo si ed uno no), seguendo dei gruppi di linee diagonali: uno principale ed uno secondario che “infittisce” i colpi.

Di questi pattern ne vengono generati due tipi (scelti casualmente per confondere l’avversario): uno con 26 colpi principali e 24 secondari, e l’altro con 30 principali e 20 secondari.

 

Pattern 1: 26+24

1

 

2

 

1

 

2

 

1

 

 

1

 

2

 

1

 

2

 

1

2

 

1

 

2

 

1

 

2

 

 

2

 

1

 

2

 

1

 

2

1

 

2

 

1

 

2

 

1

 

 

1

 

2

 

1

 

2

 

1

2

 

1

 

2

 

1

 

2

 

 

2

 

1

 

2

 

1

 

2

1

 

2

 

1

 

2

 

1

 

 

1

 

2

 

1

 

2

 

1

 

Pattern 2: 30+20

1

 

1

 

2

 

1

 

1

 

 

2

 

1

 

2

 

1

 

1

1

 

2

 

1

 

2

 

1

 

 

1

 

2

 

1

 

2

 

1

2

 

1

 

2

 

1

 

2

 

 

2

 

1

 

2

 

1

 

2

1

 

2

 

1

 

2

 

1

 

 

1

 

2

 

1

 

2

 

1

1

 

1

 

2

 

1

 

2

 

 

1

 

1

 

2

 

1

 

1

 

I colpi vengono scelti casualmente sul pattern generato ad inizio partita, dando prevalenza alle diagonali principali e poi secondarie.

Avevo iniziato ad implementare la scelta dei colpi in base alla tendenza dell’avversario a disporre le navi (sparare prima nei punti dove di solito sono state già messe le navi, ma sì è rilevata un’arma a doppio taglio, così dovrei ancora analizzare bene).

 

Quando un colpo va a segno, allora si passa nella seconda fase, quella di tentare di affondare la nave.

 

Entrando in questa modalità, vengono generati tutti i possibili colpi che sono adiacenti al colpo andato a segno e vengono memorizzati in una collezione.

In base alla tendenza dell’avversario di disporre le navi (Verticali od Orizzontali), viene scelta una direzione da seguire per tentare il colpo successivo a quello andato a segno.

Se il colpo successivo fallisce, allora si cambia direzione e si prende il colpo tra quelli adiacenti memorizzati, altrimenti vengono memorizzati ed accodati i colpi possibili adiacenti.

Se la nave viene affondata, viene fatto un controllo tra il numero dei colpi andati a segno nella fase di affondamento e la lunghezza della nave.

Se coincidono, allora la nave è affondata e si ritorna nella fase di ricerca navi, in caso contrario vuol dire che c’è una nave adiacente e quindi si rimane in modalità affondamento continuando a sparare i colpi memorizzati nella collezione ed adiacenti a quelli che hanno colpito la nave.

 

 

Strategia di Difesa.

La strategia di difesa si basa essenzialmente sulla disposizione delle proprie navi cercando di evitare le aree più soggette a “bombardamenti” da parte dell’avversario o, per lo meno, nei punti in cui l’avversario tendenzialmente colpisce più tardi.

Per riuscire in tale scopo, viene memorizzata una griglia in cui si sommano i colpi sparati dall’avversario però “appesantiti” dalla cronologia inversa; per esempio un colpo sparato all’inizio avrà un peso ed un valore maggiore rispetto ad uno sparato alla fine.

Basandosi su questa griglia, vengono estratte delle aree aventi le dimensioni delle navi, ordinate in modo crescente al valore della somma dei pesi. Le prime aree sono quelle che verranno scelte per posizionare le navi.

Infine l’orientamento della nave (Verticale od Orizzontale), viene scelto in modo opposto a come l’avversario tendenzialmente tenta di affondare la nave colpita.

 




Terminator 1.0.0.0  di  Andrea Angella & Valerio Vitacolonna

Strategia di difesa

Nessuna strategia. Il posizionamento delle navi e' completamente random.
In questo modo qualunque strategia di attacco non probabilistica dovrebbere essere poco efficace.

 
Strategia di attacco
Utilizza un algoritmo probabilistico sub-ottimale. Praticamente l'insieme di scelta ad ogni passo e' costituito da tutte le posizioni con massima probabilita' di trovare un nave avversaria. Nel caso in cui si colpisce una nave, viene utilizzato un algoritmo di affondamento che ha lo scopo di affondare la nave scoperta. Eventuali navi scoperte casualmente durante il processo vengono a loro volta affondate con la stessa strategia.

 



Deathflame 0.1.0.1  di  Mauro Bellati

Strategia di difesa

Le navi sono disposte in maniera completamente casuale [Essendo la griglia piuttosto piccola, lasciare una casella tra ogni nave, evitando cosi di farsi colpire una nave durante l'affondamento di un'altra, porta (se l'avversario si dovesse accorgere di questo pattern) a fargli escludere troppe caselle di contorno, lasciandogli un vantaggio, secondo me, troppo elevato. Il random mi pare essere il modo migliore]

Strategia di attacco

I colpi vengono sparati ad una distanza 'd' uno dall'altro (durante il gioco questa distanza varie in base a quali navi sono state affondate). Quando viene colpita una nave si seguono le caselle adiacenti fino all'affondamento. [La strategia con cui stringere o allargare la distanza minima tra i colpi penso essere il cuore dell'algoritmo (che non ho fatto in tempo a completare come avrei voluto. Speriamo di passare il turno e farlo per la seconda fase)]


Print | posted @ Tuesday, October 12, 2010 1:23 PM

Comments have been closed on this topic.