Soluzione algoritmica per Dragamine

Sto cercando di fare il risolutore dragamine. Come sai ci sono 2 modi per determinare quali campi nel campo minato sono sicuri da aprire, o per determinare quali campi sono estratti e devi segnalarlo. In primo modo per determinare è banale e noi abbiamo qualcosa di simile:Soluzione algoritmica per Dragamine

if (numero di mine attorno X - attuale numero di miniere di scoperte intorno X) = numero di campi aperti intorno X poi Tutti i campi aperti intorno a X sono minate

se (numero di miniere di tutto X == attuale numero di miniere di scoperte intorno X) quindi Tutti i campi aperti intorno a X non sono estratti

Ma la mia domanda è: che dire di situazione in cui non siamo in grado di trovare qualsiasi estratto o campo sicuro e abbiamo bisogno di guardare più di 1 campo?

http://img541.imageshack.us/img541/4339/10299095.png

Per esempio questa situazione. Non possiamo determinare nulla usando il metodo precedente. Quindi ho bisogno di un aiuto con l'algoritmo per questi casi.

Devo usare l'algoritmo A * per farlo. Ecco perché ho bisogno di tutti gli stati sicuri possibili per il prossimo passo nell'algoritmo. Quando trovo tutti i possibili stati sicuri li aggiungerò al percorso corrente più breve e, in base alla funzione euristica, ordinerò l'elenco dei percorsi e sceglierò il prossimo campo che deve essere aperto.

fonte

2013-04-11 user216799

Si potrebbe evitare di scrivere l'algoritmo e lasciare che il computer impari da solo, ma non posso dirti altro ...:/ – BlackBear

Non capisco l'immagine di esempio che fornisci. Il "2" più a sinistra indica che entrambi i campi nella seconda riga a sinistra sono estratti, ma il secondo "2" ne suggerisce solo uno. In che contesto di gioco si presenterebbe? Stai immaginando che le informazioni del gioco potrebbero essere contraddittorie? – pjmorse

Ma tu puoi trovare un campo sicuro in quell'immagine, usando il tuo algoritmo. Prendi il 2 circondato dai due; il numero di mine intorno ai due è uguale al numero attuale di mine scoperte intorno ai due. Quindi potresti scoprire il campo vuoto sopra di esso. Oppure, intendi, se avessi quel campo senza bandiere ancora segnato, come sapresti segnare quelle due bandiere? – Kevin

Impressionante problema, prima di essere troppo eccitato, leggere NP Completeness and Minesweeper, così come l'accompagnamento presentation che sviluppa alcuni esempi di casi peggiori e di come un essere umano potrebbe risolverli. Tuttavia, in previsione, molto probabilmente non colpiremo una barriera temporale, se usassimo potature ed euristiche di base.

La domanda di generazione del gioco viene richiesta qui: Minesweeper solving algorithm. C'è un post molto interessante sui metodi algebraic. Puoi anche provare a fare il backtracking (ad esempio, cerca di indovinare e vedi se ciò invalida le cose), simile al caso in cui le informazioni locali non sono sufficienti per qualcosa come sudoku. Vedi questa fantastica discussione su questo technique.

fonte

2013-04-11 19:45:01

Se hai il permesso di fare retromarcia dai tuoi errori, puoi scoprire ogni quadrato una sola volta e tenere traccia di quali quadrati hanno mine. Penso che forse l'OP è alla ricerca di un solutore che segua le stesse regole di un umano, cioè che tu fallisca se fai una mossa sbagliata. – mbeckish

Sì, certo, usa il backtracking quando tutto il resto fallisce altrimenti chiaramente l'albero cresce esponenzialmente. –

Ma come puoi tornare indietro senza scoprire una mina e perdere la partita? – mbeckish

Come @tigger ha detto che questo non è un problema che può essere risolto con un semplice insieme di regole. Minesweeper è un buon esempio in cui gli algoritmi di backtracking come DPLL sono utili. Con qualcosa di semplice come la logica proposizionale, è possibile implementare un risolutore molto efficiente per dragamine. Non sono sicuro che tu abbia familiarità con l'inferenza logica del raggiro di intelligenza artificiale & - In caso contrario, potresti dare un'occhiata al libro "Intelligenza artificiale - Un approccio moderno" di Stuart Russel e Peter Norvig. Per un rapido riferimento a DPLL e alla logica proposizionale, cerca "wumpus world propositional logic" su Google.

fonte

2013-04-11 22:07:44 aaronqli

risposta

Problemi correlati