algoritmo de jogo resolução (Buttonia, lights-out variante)

Question

Eu estou tentando criar uma função de solvabilidade de um algoritmo de jogo. Basicamente uma função que retorna verdadeiro ou falso para um determinado jogo que se pode ser resolvido ou não.

O jogo é Buttonia.com (que não implementar o algoritmo ainda), um tipo de jogo de luzes apagadas. Basicamente, você tem uma grade de botões, cada um dos quais, quando pressionado, irá mudar o estado de alguns de seus vizinhos. Atualmente eu gerar uma configuração de jogo aleatório e depois aplicar heurística na medida do possível. O resto é decidido pela busca por força bruta.

O meu progresso até agora foi criar um sistema de equações para modelar o jogo. Como cada botão precisa de mudança de estado um número ímpar de vezes para acabar em um estado para baixo, é a equação seria esta:

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

Onde button_1 através button_X são os estados dos botões com um efeito sobre button_A. Alguns botões podem ser resolvidos imediatamente, se eles não são dependentes dos outros. Quanto ao resto, eu tento uma configuração até que eu comece um conflito e depois voltar acompanhar.

Atualmente esse algoritmo é prático para configurações menores de jogos. Eu testei-o de 3x3 jogos até tamanhos de 10x10. Onde 6x6 está perto de um limite superior para o jogo prático.

As equações extremamente reduzir o espaço de busca a partir de força bruta, tornando-se prático. Pode haver uma maneira puramente matemática de resolver o sistema de equações.

---

jogo 3x3 Sample em ASCII (de 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

Solução, pressionar estes: (0,0), (2,0), (1, 2), (0, 1), (1, 1), (2,1)

As equações para este jogo:

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

solução potencial:

Alterar as funções matemáticas para evitar a necessidade do módulo permite mover os termos do lado esquerdo para o direito, criando a configuração de matriz limpa que precisamos para o método de Gauss. Assim, as duas primeiras equações iria respectivamente converter em:

-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

solução discutido aqui: Gaussian eliminação com operadores personalizados

Chegando mais perto. Quase pronto para postar solução completa: Inverting binário redes

Answer 1

Trata-se de um sistema de equações lineares sobre F ₂ , o campo que contém os dois elementos de 0 e 1.

Você pode resolvê-lo apenas como equações lineares normais, mas você tem que fazer o módulo aritmética 2.

Editar: álgebra linear para este caso funciona exatamente como para os números reais, exceto que você tem que substituir as operações:

• A adição e subtracção tornar exclusivo ou, isto é, 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0.

• A multiplicação torna-E: 0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1

• Divisão só é possível por um:. 0/1 = 0, 1/1 = 1

Todos os coeficientes em suas equações e os possíveis valores de incógnitas são 0 ou 1.

Assim, o módulo não é um tapa na parte externa das equações como você escreveu, está implícito nas operações.

Se o seu sistema de equações não é solucionável você vai ter uma equação 0 = 1, que obviamente não é solucionável.

Answer 2

Em vez de começar com um estado aleatório, por que não geram a posição inicial lançando interruptores aleatório, isto é, ao contrário de trabalho de um estado resolvido para um estado inicial. Dessa forma, você só gerar enigmas que podem ser resolvidos.

Answer 3

Este parece quase como um sistema de equações lineares (exceto o mod 2), de modo que você pode ser capaz de adaptar uma das técnicas normais para resolver aqueles - por exemplo, redução de linha do sistema de matriz em forma (Wikipedia) .

Answer 4

Como este não é um problema limitado no tempo (bem, supondo que isso pode ser feito em menos de um dia), eu provavelmente iria para uma busca em largura primeiro profundidade limitada, tendo cada movimento possível em um nível e, em seguida, cada movimento que surge na sequência de cada movimento.

Será lento, no entanto, é quase garantida para encontrar uma resposta, se houver um!

Answer 5

Suponha que você construiu um sistema de equações e resolveu-los da melhor maneira possível, mas algumas linhas acabou com todos os 0 está no lado esquerdo da equação (Estou representando as equações como uma matriz aumentada) Suponha que você tentou resolver o sistema no anel Z2 (que em termos práticos para este exemplo meios específicos que a única mudança é que 1 + 1 = 0, senão tudo permanece o mesmo ... ergo a necessidade só nós operador XOR) e acabou com a seguinte matriz:

1001 1
0100 1
0011 0
0000 0

Como você pode ver neste exemplo, a linha 4 é tudo 0, o que significa que não temos uma resposta para isso. No entanto pense da seguinte maneira: uma fileira de todos os 0 significa que essa variável não afeta a solução. Isso é realmente uma má escolha de palavras ... Significa apenas que eles podem ter qualquer valor (e estamos com sorte aqui, já que todos os meios valores 1 ou 0, ao contrário de números reais ... Então isso significa que temos 2 soluções para este sistema).

Aqui está o porquê: o que você precisa saber neste momento é que a coluna mais à direita ainda contém uma solução válida para o seu jogo. Vamos dar a primeira linha, por exemplo. Ele diz que

button_0 + button_3 = 1

mas sabemos que a tecla 3 pode ser qualquer coisa (desde a linha 3 é todos os 0s). Neste ponto botão 3 é 0 (a coluna mais à direita na linha 3 é 0, neste ponto) então agora nós sabemos que significa

button_0 + 0 = 1

por isso sabemos para um fato que button_0 é 1. Portanto, neste sistema, embora não conseguimos encontrar diretamente button_3, ainda temos uma solução válida.

A matriz gerado acima é suficiente para verificar se há solvabilidade. Se uma linha contém todos os 0s então é essencialmente dizendo que

nothing = nothing

ou, para melhor visualizar por que isso funciona,

0x = 0

o que faz sentido, o sistema ainda é válido. Se, no entanto, encontramos uma linha que é todos os 0s , exceto o bit mais à direita, i.

0000 1

que estaria dizendo

0x = 1

o que é impossível, portanto, agora sabemos que o sistema não pode ser resolvido, uma vez que não pode resolver uma situação impossível assim.

Portanto, em poucas palavras, e tentar resolver a equação da melhor maneira possível, não se preocupe se você não consegue encontrar exatamente o que algumas das variáveis ??são, contanto que você não encontrar, em qualquer ponto, o impossível Row que acabei de mencionar, em seguida, o jogo tem solução.

Mas o que se deseja que o menor solução para o sistema? Aqui nós vamos ter que examinar todas as soluções possíveis. Temos button_3 que pode ser qualquer valor, de modo que meios que qualquer 1 na coluna 3 significa que a linha em que é encontrado, é afectada por button_3. Então, suponha que queremos verificar se a solução usando button_3 será mais curto. Nós criamos uma outra matriz, mas conjunto button_3 a 1 agora (desde que estabelecemos anteriormente que poderia ser qualquer coisa, e já tinha um 0 ali, então agora vamos verificar para 1). Nós agora acabar com a seguinte matriz:

1001 1
0100 1
0011 0
0001 1

Nós reduzimos que, tanto quanto pudermos e agora acabar com esta matriz:

1000 0
0100 1
0010 1
0001 1

Esta é ainda uma solução válida, no entanto, podemos ver que a solução é mais (o que exige 3, em vez de 2 pressiona o botão), portanto, descartá-lo. Temos que fazer isso para cada permutação de definir as linhas encontramos como todos os 0s para 1. Portanto, se tivermos x linhas que eram todos os 0s, então o sistema tem x ^ 2 soluções, e nós temos que verificar todos eles.