Algoritmo di risoluzione dei giochi (Buttonia, variante senza luci)

https://stackoverflow.com/questions/1211560

06-07-2019
|

Domanda

Sto cercando di creare una funzione di solvibilità per un algoritmo di gioco. Fondamentalmente una funzione che restituisce vero o falso per un dato gioco se è risolvibile o meno.

Il gioco è Buttonia.com (che non implementa ancora l'algoritmo), un tipo di gioco senza luci. Fondamentalmente hai una griglia di pulsanti, ognuno dei quali, quando premuto, cambierà lo stato di alcuni dei suoi vicini. Attualmente generi una configurazione di gioco casuale e quindi applico l'euristica per quanto possibile. Il resto è deciso dalla ricerca della forza bruta.

I miei progressi finora sono stati la creazione di un sistema di equazioni per modellare il gioco. Poiché ogni pulsante deve cambiare stato un numero dispari di volte per finire in uno stato down, l'equazione sarebbe questa:

button_A = 1 - (button_1 + button_2 + ... + button_X)% 2

Dove button_1 tramite button_X sono gli stati dei pulsanti con un effetto su button_A. Alcuni pulsanti possono essere risolti immediatamente, se non dipendono da altri. Per il resto, provo una configurazione fino a quando non ho un conflitto e poi torno indietro.

Attualmente questo algoritmo è pratico per configurazioni di giochi più piccole. L'ho provato da giochi 3x3 fino a dimensioni di 10x10. Dove 6x6 è vicino a un limite superiore per il gioco pratico.

Le equazioni riducono enormemente lo spazio di ricerca dalla forza bruta, rendendolo pratico. Potrebbe esserci un modo puramente matematico di risolvere il sistema di equazioni.

Esempio di gioco 3x3 in ascii (da buttonia.com/?game=2964 ):

||#
-o-
+#|

Legend:
o = affect only self
- = affect left and right neighbors
| = affect above and below neighbors
+ = affect left, right, above and below neighbors
# = affect all 8 surrounding neighbors

Soluzione, premere questi: (0,0), (2,0), (1, 2), (0, 1), (1, 1), (2,1)

Equazioni per questo gioco:

Button_0_0 = 1 - (0) % 2
Button_1_0 = 1 - (Button_2_0) % 2
Button_2_0 = 1 - (0) % 2
Button_0_1 = 1 - (Button_0_0 + Button_0_2 + Button_1_2) % 2
Button_1_1 = 1 - (Button_1_0 + Button_2_0 + Button_0_1 + Button_2_1 + Button_1_2) % 2
Button_2_1 = 1 - (Button_2_0 + Button_1_2 + Button_2_2) % 2
Button_0_2 = 1 - (Button_1_2) % 2
Button_1_2 = 1 - (Button_0_2) % 2
Button_2_2 = 1 - (Button_1_2) % 2

Soluzione potenziale:

La modifica delle funzioni matematiche per evitare la necessità del modulo ci consente di spostare i termini dal lato sinistro a quello destro, creando la matrice ordinata necessaria per il metodo gaussiano. Quindi le prime due equazioni si convertiranno rispettivamente in:

-1 = -1*B00 +  0*B10 +  0*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22
-1 =  0*B00 + -1*B10 + -1*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22

Soluzione discussa qui: Eliminazione gaussiana con operatori personalizzati

Avvicinarsi. Quasi pronto per pubblicare la soluzione completa: Inversione di reti binarie

Soluzione

Questo è un sistema di equazioni lineari su F ₂, il campo contenente i due elementi 0 e 1.

Puoi risolverlo proprio come le normali equazioni lineari, ma devi fare l'aritmetica modulo 2.

Modifica L'algebra lineare per questo caso funziona esattamente come per i numeri reali, tranne per il fatto che è necessario sostituire le operazioni:

L'aggiunta e la sottrazione diventano esclusive o, cioè 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0.
La moltiplicazione diventa AND: 0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1
La divisione è possibile solo per uno: 0/1 = 0, 1/1 = 1.

Tutti i coefficienti nelle tue equazioni e i possibili valori di incognite sono 0 o 1.

Quindi il modulo non è schiaffeggiato all'esterno delle equazioni come hai scritto, è implicito nelle operazioni.

Se il tuo sistema di equazioni non è risolvibile otterrai un'equazione 0 = 1, che ovviamente non è risolvibile.

Altri suggerimenti

Invece di iniziare con uno stato casuale, perché non generare la posizione iniziale lanciando interruttori casuali, ovvero lavorare all'indietro da uno stato risolto a uno stato iniziale. In questo modo si generano solo enigmi risolvibili.

Sembra quasi un sistema di equazioni lineari (tranne la mod 2), quindi potresti essere in grado di adattare una delle normali tecniche per risolverle, ad es. riduzione di riga del sistema in forma di matrice (wikipedia) .

Dato che questo non è un problema limitato nel tempo (beh, supponendo che possa essere fatto in meno di un giorno), probabilmente farei una ricerca in profondità limitata in profondità, prendendo ogni possibile mossa a un livello e poi ogni mossa che segue ogni mossa.

Sarà lento, tuttavia è quasi certo di trovare una risposta, se ce n'è una!

Supponi di aver creato un sistema di equazioni e di averle risolte nel miglior modo possibile, ma alcune righe sono finite con tutti gli 0 sul lato sinistro dell'equazione (sto rappresentando le equazioni come una matrice aumentata) Supponiamo che tu abbia provato a risolvere il sistema nell'anello Z2 (che in termini pratici per questo esempio particolare significa che l'unica modifica è che 1 + 1 = 0, altrimenti tutto rimane uguale ... ergo l'unico operatore di cui abbiamo bisogno è XOR) e ha finito con la seguente matrice:

Come puoi vedere in questo esempio, la quarta riga è tutta 0, il che significa che non abbiamo una risposta per questo. Tuttavia, pensala in questo modo: una riga di tutti 0 indica che quella variabile non influisce sulla soluzione. In realtà è una pessima scelta di parole ... significa solo che possono avere qualsiasi valore (e siamo fortunati qui, poiché tutti i valori significano 1 o 0, a differenza dei numeri reali ... Quindi questo significa che abbiamo 2 soluzioni per questo sistema).

Ecco perché: ciò che devi sapere a questo punto è che la colonna più a destra contiene ancora una soluzione valida per il tuo gioco. Prendiamo ad esempio la prima riga. Lo dice

button_0 + button_3 = 1

ma sappiamo che il pulsante 3 può essere qualsiasi cosa (poiché la riga 3 è tutta 0). A questo punto il pulsante 3 è 0 (la colonna più a destra della riga 3 è 0 a questo punto), quindi ora sappiamo che significa

button_0 + 0 = 1

quindi sappiamo per certo che button_0 è 1. Pertanto in questo sistema anche se non siamo riusciti a scoprire direttamente button_3, abbiamo ancora una soluzione valida.

La matrice generata sopra è sufficiente per verificare la solvibilità. Se una riga contiene tutti gli 0, in pratica lo sta dicendo

nothing = nothing

oppure, per visualizzare meglio perché funziona,

0x = 0

il che ha senso, il sistema è ancora valido. Se tuttavia incontriamo una riga che è tutta 0 tranne il bit più a destra, cioè

0000 1

questo direbbe

0x = 1

il che è impossibile, quindi ora sappiamo che il sistema non può essere risolto, dal momento che non possiamo risolvere una situazione impossibile come questa.

Quindi, in poche parole, prova a risolvere l'equazione nel miglior modo possibile, non preoccuparti se non riesci a scoprire esattamente quali sono alcune variabili, purché non trovi, in nessun punto, l'impossibile riga che ho appena menzionato, il gioco è risolvibile.

E se volessimo la soluzione più breve al sistema? Qui dovremo esaminare tutte le possibili soluzioni. Abbiamo button_3 che può essere qualsiasi valore, quindi ciò significa che qualsiasi 1 nella colonna 3 significa che la riga in cui si trova, è influenzata da button_3. Supponiamo quindi di voler verificare se la soluzione che utilizza button_3 sarà più corta. Creiamo un'altra matrice, ma impostiamo button_3 su 1 ora (poiché abbiamo stabilito in precedenza che potrebbe essere qualsiasi cosa, e avevamo già uno 0 lì dentro, quindi ora controlliamo per 1). Ora finiamo con la seguente matrice:

Riduciamo il più possibile e ora finiamo con questa matrice:

Questa è ancora una soluzione valida, tuttavia possiamo vedere che la soluzione è più lunga (richiede 3, anziché 2 pressioni di pulsanti), quindi la scartiamo. Dobbiamo farlo per ogni permutazione dell'impostazione delle righe che abbiamo trovato come tutti gli 0 su 1. Pertanto, se abbiamo x righe che erano tutte 0, allora il sistema ha x ^ 2 soluzioni e dobbiamo controllarle tutte.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow