Miglioramento dell'algoritmo di risoluzione del campo minato

Question

Ho implementato in Python un algoritmo per la risoluzione del gioco "Minesweeper". Il programma funziona come segue:

Supponiamo che il risolutore faccia clic su un quadrato denominato 'a'. Per esempio, lascia che il numero sia rivelato uguale a 2. I vicini del quadrato che sono ancora non clonati sono (sempre a titolo di esempio) chiamati "b" e "c". Il programma associa quindi il quadrato con l'espressione [2, {'b', 'c'}] e rimuove 'a' da tutte le altre espressioni. La deduzione di quali quadrati sono miniere e che non proviene da una semplificazione a coppie di tali espressioni in due circostanze.

• Se le piazze di una delle espressioni sono un sottoinsieme delle piazze della altra espressione:

  [2, {'a', 'b', 'c'}], [1, {'a', 'b'}] -> [1, {'c'}], [1, {'a', 'b'}] 
  

• Se tutte le piazze in un'espressione sono stabiliti ad essere miniere:

  [2, {'a', 'b'}], [1, {'b', 'c'}] -> [2, {'a', 'b'}], [0, {'c'}] 
  

Poi, per qualche espressione X, se X[0] == 0, siamo liberi di cl fai clic su tutti i riquadri denominati in X[1] e, se X[0] == len(X[1]), possiamo contrassegnarli.

Tuttavia, sto faticando a identificare quali coppie di espressioni per tentare di semplificare. Il mio attuale approccio è di mantenere una pila di quadrati; ogni volta che viene fatto clic su un quadrato o se la sua espressione è stata semplificata con successo, viene aggiunta allo stack (se non è già presente). Quando viene estratto un quadrato dalla pila, viene tentata una semplificazione tra la sua espressione (X) e qualsiasi altra espressione Y tale che X[1] & Y[1] != set(). L'algoritmo termina quando lo stack è esaurito. Attualmente tuttavia, sebbene funzioni abbastanza bene, non è in grado di risolvere correttamente tutte le configurazioni non ambigue, e quanto bene si comporta su una data scheda cambia in modo significativo se rimpiazzo lo stack con una coda, o uso qualche algoritmo per determinare quale quadrato popare !

Sarei molto grato per qualsiasi esempio di precedente al mio approccio, o strade di potenziale esplorazione.

Answer 1

Questo è quello che mi è venuto in mente, non ero completamente in grado di visualizzare quale fosse esattamente il tuo metodo.
Spero che presentare il mio in forma grafica ti aiuti a salvarti.

Le immagini procedono in "ordine di lettura".

E sembra adattarsi con il lavoro che ho fatto da quando questo distacco che l'aggiunta al valore dato a una tessera sconosciuta il numero di tessere noti che si sta guadagnando il suo valore di temperatura dal potrebbe aumentare ulteriormente la probabilità di modellare correttamente il rischio.
(usando questo, un valore di temperatura di 16 (o 8 con il primo metodo) è significativo in quanto è il numero uno miniera può raggiungere da sola)

---

sento un po 'cieco per non vedere questa prima .

Qualsiasi cosa con un valore che si normalizzi al 100% è in tutti i casi che riesco a trovare, una miniera.

Answer 2

Diversi anni fa ho scritto un risolutore del dragamine, ma purtroppo ho perso il codice da allora. Quello che ricordo è che si trattava di un metodo a forza bruta, che compilava serie di potenziali mine, piuttosto che lasciare le combinazioni impacchettate come si fa.

Credo fosse un po 'più capace dell'algoritmo con cui si sta lavorando. Il tuo approccio può "risolvere" una condizione se è completamente piena o vuota di mine o se è un sottoinsieme di un'altra condizione. Tuttavia, ci sono alcune deduzioni che questo non gestirà. Per esempio, prendere in considerazione questa piccola scheda 7x2, dove i a attraverso h piastrelle sono sconosciuti:

a 2 1 2 1 2 i 
b c d e f g h 

vostre condizioni saranno:

[2, {a, b, c, d}], 
[1, {c, d, e}], 
[2, {d, e, f}], 
[1, {e, f, g}], 
[2, {f, g, h, i}] 

Se ho capito bene, l'algoritmo non può fare detrazioni su questo. Tuttavia, se sei un giocatore esperto Minesweeper, si riconosce che il modello 1 2 1 al centro ha solo una soluzione unica, con le mine sotto i 1 s:

a 2 1 2 1 2 i 
b 2 * 2 * 2 h 

Ci sono ancora alcune incognite, con una mina sotto a o e un altro sotto h o i, ma se questo faceva parte di un puzzle più grande, potresti essere in grado di capirli in seguito (o potresti dover indovinare).

Credo che il mio gruppo di approccio mine funzionava così:

Per ogni tessera che è stata ampliata, raccoglie un insieme di tutti i suoi vicini non espansi (il "area"), e una lista contenente tutti i gruppi di mine che potrebbero verificarsi in quell'area. Così, per esempio, le 5 tessere noti nell'esempio precedente sarebbe generare (da sinistra a destra):

({a, b, c, d}, [{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}]) 
({c, d, e}, [{c}, {d}, {e}]) 
({d, e, f}, [{d, e}, {d, f}, {e, f}]) 
({e, f, g}, [{e}, {f}, {g}]) 
({f, g, h, i}, [{f, g}, {f, h}, {f, i}, {g, h}, {g, i}, {h, i}]) 

In ogni caso, per combinare due condizioni che avevo prima controllare che fossero sovrapposizioni, intersecando i set zona. Se non ci sono sovrapposizioni, le condizioni non possono essere combinate in modo utile.

Se ci fosse una sovrapposizione, la nuova condizione si estenderebbe dall'unione delle loro aree. Per quanto riguarda le serie di mine, farei un prodotto cartesiano dei set esterni per ottenere coppie di set interiori, quindi controlla se c'era una contraddizione. Una contraddizione sarebbe se, all'interno dell'intersezione delle aree, i due set non avessero esattamente le stesse mine. Se non ci fosse alcuna contraddizione, si formerebbe un nuovo insieme combinato dall'unione dei luoghi minerari. Ecco come le prime due righe di cui sopra sarebbero combinare:

Intersection of areas: {a, b, c, d} & {c, d, e} = {c, d} 
New combined area: {a, b, c, d} | {c, d, e} = {a, b, c, d, e} 
Cartesian product of mine sets (with X marking contradictions): 
    | {a, b} {a, c} {a, d} {b, c} {b, d} {c, d} 
---+------------------------------------------------- 
{c}|  X  {a, c} X  {b, c} X  X 
{d}|  X  X  {a, d} X  {b, d} X 
{e}| {a, b, e} X  X  X  X  X 

New condition: ({a, b, c, d, e}, [{a, b, e}, {a, c}, {b, c}, {a, d}, {b, d}]) 

è possibile calcolare la probabilità di qualsiasi tessera all'interno dell'area della condizione di essere una miniera semplicemente contando il numero dei set Fa parte del, rispetto a quanti set ci sono in totale Quindi, data la condizione combinata sopra, è possibile capire che a è un mio 3/5s del tempo, mentre e è solo 1/5 del tempo. Questa informazione è importante quando il programma deve indovinare una posizione da espandere quando non ci sono tessere sicure garantite. Penso di aver anche fatto un complicato calcolo combinatorio per tenere conto del numero di mine utilizzate (in modo che il caso {a, b, e} sopra sia ponderato in modo leggermente diverso dagli altri casi, poiché usa tre mine anziché due), ma temo di non ricordare i dettagli.

Minesweeper è un gioco piuttosto impegnativo.Credo che il mio programma sia stato in grado di risolvere schede equivalenti alla difficoltà "Difficile" circa il 50-60% delle volte, con la maggior parte delle perdite che si verificano all'inizio (quando è necessario indovinare con poche informazioni da cui partire) o direttamente a alla fine (quando ci sono spesso alcune aree irrisolvibili che devono essere indovinate). Di solito era piuttosto veloce, anche se occasionalmente ci sarebbe stato un pattern di tessere che lo ha fatto impantanare per 10 o 15 secondi prima di fare la sua prossima mossa. (Minesweeper is NP-complete, quindi non sorprende che alcuni input non possano essere risolti rapidamente!)