Ciao a tutti,
L'altro giorno mio figlio ha chiesto di giocare alla versione su carta millimetrata di "Battleship". Ogni persona aveva 5 "navi" lunghe 5, 4, 3, 3 e 2 unità (e larghe un'unità). Le "navi" erano posizionate su una griglia 10 per 10 nello spazio XY; ogni "nave" aveva un set unico di coordinate (x,y). Ad esempio, una delle 3 "navi" unità poteva avere coordinate (3,4), (4,4) e (5,4). Non più di una "nave" può occupare la stessa coordinata (x,y). Le "navi" possono essere posizionate solo in verticale o in orizzontale, non è consentita alcuna disposizione diagonale.
Poi ci siamo alternati nel chiamare coppie di coordinate (x,y) per vedere chi aveva colpito direttamente la "nave" di qualcun altro. Ognuno di noi aveva solo 16 turni per provare a colpire (o affondare) quante più "navi" dell'altra persona. Mentre stavamo facendo questo, ho pensato che doveva esserci un approccio migliore per massimizzare le proprie possibilità di colpire (e/o affondare) la "nave" di un'altra persona rispetto al chiamare semplicemente le coordinate a caso. Ovviamente, non chiameresti una coordinata (x,y) che hai già usato perché sapresti se hai colpito una "nave" o no.
All'inizio, ho pensato che forse la piattaforma Custom Design sarebbe stata la strada giusta da seguire, ma se crei un design in cui Y è "Hit" (0/1 per no/sì) e X1 = x e X2 = coordinate y (numeri discreti a 10 livelli), la piattaforma genererà un design in cui utilizza solo i livelli alto e basso per ogni X e Y. A proposito, i termini del modello sono solo x, y e il termine incrociato x*y. Quindi, sfortunatamente, Custom Design non funziona.
La piattaforma DOE fattoriale completo non funzionerà perché vuole effettuare 100 esecuzioni (fattoriale 10x10) e abbiamo solo 16 esecuzioni (tentativi) ciascuna.
La piattaforma RSM DOE funziona solo sui livelli alto/basso e inserendo 1 e 10 per i livelli basso/alto. Le opzioni di progettazione CCD non riempiono realmente lo spazio della griglia 10 per 10 in cui verrebbero posizionate le "navi": troppi centri di corsa per coprire lo spazio della griglia.
L'unica altra piattaforma applicabile a questo sarebbe lo Space Filling Design. Utilizzando le stesse impostazioni basso/alto, 1/10 per x e y e "Hit" come risposta (questo sarebbe binario, 0/1 per no/sì), posso ottenere una tabella DOE con coppie (x,y) che riempiono lo spazio della griglia. Non sono sicuro di quale sarebbe la scelta migliore per i metodi di progettazione di riempimento dello spazio, FFF o Uniform, o Latin Hypercube, ecc.
Penso che la cosa più importante sia che il DOE è fisso, non è "adattabile" nel senso che, in base al risultato della prima esecuzione, come verrebbe modificato il DOE per tenere conto delle informazioni note. Utilizzando le coordinate della barca a 3 unità di cui sopra, diciamo che la mia prima esecuzione consiste nel chiamare le coordinate (3,4) e ottengo un risultato. Sapendo che la disposizione delle "navi" è orizzontale o verticale, la mia chiamata successiva non sarebbe quella di seguire il DOE, ma piuttosto di chiamare (3,5), (3,3), (2,4) o (4,4) -- aumenterei x o y di un'unità e vedrei qual è il risultato. E così via fino a quando la barca non affonda o si sposta alla successiva possibile coordinata di partenza.
Vorrei trovare un metodo più scientifico per generare un DOE adattivo che possa ottimizzare le 16 esecuzioni per generare "hit". Partire da un DOE statico non lo farebbe perché dopo ogni esecuzione, una coordinata viene "esaurita" e apprendo se è un hit o meno. Ogni esecuzione informa l'esecuzione successiva n+1. Per quanto ne so, non esiste un DOE che possa gestire qualcosa del genere, ma non sono nemmeno un esperto in questo campo.
La selezione casuale di un punto di partenza è la cosa migliore che si possa fare in "Battleship"? Non credo, ma ho difficoltà a capire come avere un DOE adattivo che sostanzialmente contenga istruzioni "if/then" in modo da ottimizzare l'uso dei miei 16 tentativi tenendo conto delle informazioni del passaggio precedente. Sarebbe bello avere un DOE "adattabile" che ottimizzi le tue scelte per ogni esecuzione in modo da massimizzare le tue possibilità di vincere in 16 tentativi.
Grazie per la discussione!
S.S.
PS, cercando JMP e "Battleship", ho trovato questo post di @Jordan_Hiller che mostra come JMP può essere usato per giocare a diversi giochi, e @brady_brady ha scritto codice JSL per giocare effettivamente a "Battleship". Molto bello! Scaricherò presto quel JSL!
CIAO @Giordania_Hiller ,
Grazie per il link al blog, l'articolo mi è piaciuto.
Generalmente capisco il concetto alla base di come hanno calcolato la probabilità che una nave si trovi in un certo quadrato -- questo sarebbe diverso per ogni tipo di nave. Tuttavia, poiché lo stato di probabilità per il tabellone cambierebbe dopo ogni round di gioco, la scelta della casella successiva su cui sparare cambia, che per me non è altro che un design di riempimento dello spazio ri-ottimizzato che tiene conto dei colpi/fallimenti/ dimensioni della barca/e numero di giri rimasti.
Il poster del blog è stato in grado di generare un algoritmo in grado di eseguire il gioco in 34 mosse, che è esattamente il doppio del numero di caselle occupate dalle barche. Presumibilmente, sarebbe possibile generare un percorso decisionale ottimale che potrebbe portare il numero richiesto di mosse per vincere più vicino a 17. Forse non esattamente 17, ma molto vicino.
Certamente un approccio ML/AI può costruire un algoritmo per vincere la partita, ma sono d'accordo, è eccessivo e non è quello che sto davvero cercando. Sono più interessato a forse una miscela di ciò che ha fatto la persona del blog e l'utilizzo di un DOE. Chiaramente la funzione di densità di probabilità per il tabellone è fondamentale per prendere decisioni. Ma si potrebbe modificarlo da un calcolo puramente probabilistico a uno basato su un riempimento dello spazio ottimizzato, quasi come alimentare la funzione di probabilità del tabellone come funzione di "ponderazione" per il DOE in modo tale che il DOE generi i colpi più probabili. Mi sembra che generare prima il numero di colpi più alto e poi concentrarsi sull'affondamento porterebbe a una vittoria più rapida rispetto a come l'ha fatto il blogger, che era concentrarsi sull'affondamento di una nave prima di passare alla modalità di caccia.
Ad ogni modo, ho trovato interessante considerarlo e pensarci, e apparentemente anche altri lo hanno fatto!
Grazie!,
DS
Idea divertente, Diedrich!
Ecco un vecchio post sul blog su questo argomento, qualcuno ha capito come calcolare la probabilità che una nave si trovi su ogni quadrato della griglia per un dato stato di gioco. https://www.datagenetics.com/blog/december32011/ Dopodiché, non hai nemmeno bisogno di un modello, puoi solo scegliere il quadrato più probabile. Ci sono anche alcuni progetti di apprendimento automatico là fuori, ma sembra eccessivo!
Giordania
