게임 해결 알고리즘(Buttonia, Lights-out 변형)

https://stackoverflow.com/questions/1211560

06-07-2019
|

문제

게임 알고리즘에 대한 해결 가능성 함수를 만들려고 합니다.기본적으로 주어진 게임에 대해 true 또는 false를 반환하는 함수는 해결 가능한지 여부를 나타냅니다.

이 게임은 일종의 소등게임인 Buttonia.com(아직 알고리즘을 구현하지 않은)입니다.기본적으로 버튼 그리드가 있으며 각 버튼을 누르면 이웃 버튼의 상태가 변경됩니다.현재 저는 임의의 게임 구성을 생성한 다음 가능한 한 경험적 방법을 적용합니다.나머지는 무차별 대입 검색으로 결정됩니다.

지금까지 제가 진행한 작업은 게임을 모델링하기 위한 방정식 시스템을 만드는 것이었습니다.다운 상태가 되려면 각 버튼이 홀수 번 상태를 변경해야 하므로 방정식은 다음과 같습니다.

버튼_A = 1 - (버튼_1 + 버튼_2 + ...+ 버튼_X) % 2

여기서 버튼_1부터 버튼_X까지는 버튼_A에 영향을 미치는 버튼의 상태입니다.일부 버튼은 다른 버튼에 종속되지 않는 경우 즉시 해결될 수 있습니다.나머지 부분에서는 충돌이 발생할 때까지 하나의 구성을 시도한 다음 다시 추적합니다.

현재 이 알고리즘은 소규모 게임 구성에 실용적입니다.3x3 게임부터 10x10 크기까지 테스트했습니다.6x6은 실제 플레이의 상한선에 가깝습니다.

방정식은 무차별 공격으로 인한 검색 공간을 크게 줄여 실용적으로 만듭니다.방정식 시스템을 해결하는 순전히 수학적 방법이 있을 수 있습니다.

ASCII로 된 샘플 3x3 게임( 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

해결 방법은 다음을 누르세요.(0,0), (2,0), (1, 2), (0, 1), (1, 1), (2,1)

이 게임의 방정식:

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

잠재적인 해결책:

모듈러스가 필요하지 않도록 수학적 함수를 변경하면 왼쪽의 항을 오른쪽으로 이동하여 가우스 방법에 필요한 깔끔한 행렬 설정을 만들 수 있습니다.따라서 처음 두 방정식은 각각 다음과 같이 변환됩니다.

-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

여기에서 논의된 솔루션: 사용자 정의 연산자를 사용한 가우스 제거

가까워지고 있습니다.전체 솔루션을 게시할 준비가 거의 완료되었습니다. 이진 네트워크 반전

해결책

이것은 f에 대한 선형 방정식 시스템입니다₂, 두 요소 0 및 1을 포함하는 필드.

정상적인 선형 방정식처럼 해결할 수 있지만 산술 모듈로 2를 수행해야합니다.

편집하다:이 경우의 선형 대수는 작업을 교체해야한다는 점을 제외하고는 실수와 똑같이 작동합니다.

추가 및 뺄셈은 독점적이거나, 즉 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0이됩니다.
곱셈이되고 : 0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1
분할은 하나만 가능합니다 : 0 / 1 = 0, 1 / 1 = 1.

방정식의 모든 계수와 미지의 가능한 값은 0 또는 1입니다.

따라서 모듈로는 당신이 쓴 것처럼 방정식의 외부에 비틀리지 않으며, 그것은 작업에 암시 적입니다.

방정식 시스템을 해결할 수없는 경우 방정식 0 = 1을 얻을 수 있습니다.

다른 팁

임의의 상태로 시작하는 대신, 무작위 스위치를 뒤집어 시작 위치를 생성하지 않는 이유, 즉, 해결 된 상태에서 시작 상태로 뒤로 작동합니다. 그렇게하면 해결 가능한 퍼즐 만 생성합니다.

이것은 거의 선형 방정식 시스템 (모드 2 제외)과 거의 같으므로이를 해결하기위한 일반적인 기술 중 하나를 적응할 수 있습니다. (위키 백과).

이것은 시간 제한적인 문제가 아니기 때문에 (하루도 채되지 않아서 할 수 있다고 가정 할 때), 아마도 깊이 제한 너비 우선 검색을 위해, 각각의 가능한 이동을 레벨에서 가져간 다음 각각의 움직임을 이동시킬 것입니다. 각 움직임에서 따라갑니다.

느리지 만 답이 있다면 대답을 찾는 것이 거의 보장됩니다!

당신이 방정식 시스템을 만들어 최선을 다해 해결했다고 가정 해 봅시다. 그러나 일부 행은 방정식의 왼쪽에있는 모든 0을 모두로 끝났다고 가정 해 Z2 링에서 (이 특정 예에 대한 실제적인 용어로는 유일한 변화는 1+1 = 0이라는 것을 의미합니다. 그렇지 않으면 모든 것이 동일하게 유지됩니다 ...따라서 우리에게 필요한 유일한 연산자는 XOR입니다. 다음 행렬로 끝났습니다.

이 예에서 볼 수 있듯이 4번째 행은 모두 0입니다. 이는 이에 대한 답을 얻지 못했다는 의미입니다.그러나 이렇게 생각해보세요.모두 0인 행은 해당 변수가 솔루션에 영향을 미치지 않음을 의미합니다.정말 잘못된 단어 선택이네요...이는 단지 값이 무엇이든 가질 수 있다는 의미일 뿐입니다. (실수와 달리 모든 값은 1 또는 0을 의미하므로 여기서는 운이 좋습니다...따라서 이는 이 시스템에 대해 2가지 솔루션이 있음을 의미합니다.

이유는 다음과 같습니다.이 시점에서 알아야 할 것은 가장 오른쪽 열에 여전히 게임에 대한 유효한 솔루션이 포함되어 있다는 것입니다.예를 들어 첫 번째 줄을 살펴보겠습니다.그것은 말한다

button_0 + button_3 = 1

하지만 우리는 버튼 3이 무엇이든 될 수 있다는 것을 알고 있습니다(라인 3은 모두 0이므로).이 시점에서 버튼 3은 0입니다(행 3의 가장 오른쪽 열은 이 시점에서 0입니다). 이제 우리는 이것이 무엇을 의미하는지 알 수 있습니다.

button_0 + 0 = 1

그래서 우리는 버튼_0이 1이라는 사실을 알고 있습니다.따라서 이 시스템에서는 Button_3을 직접 찾을 수 없더라도 여전히 유효한 솔루션이 있습니다.

위에서 생성된 행렬은 해결 가능성을 확인하기에 충분합니다.행에 모두 0이 포함되어 있으면 본질적으로 다음과 같습니다.

nothing = nothing

또는 이것이 작동하는 이유를 더 잘 시각화하려면

0x = 0

즉, 시스템은 여전히 유효합니다.그러나 모두 0인 행을 만나면 제외하고 가장 오른쪽 비트, 즉

0000 1

그 말이겠지

0x = 1

이는 불가능하므로 이제 우리는 이와 같은 불가능한 상황을 해결할 수 없기 때문에 시스템을 해결할 수 없다는 것을 알고 있습니다.

그러므로 간단히 말해서, 가능한 한 최선을 다해 방정식을 풀어보십시오. 변수 중 일부가 무엇인지 정확히 알 수 없더라도 걱정하지 마십시오. 어떤 지점에서든지 제가 방금 설명한 불가능한 행을 만나지 않는 한 그러면 게임이 해결 가능하다고 언급됩니다.

하지만 우리가 원한다면 어떨까요? 가장 짧은 시스템에 대한 솔루션?여기서 우리는 가능한 모든 해결책을 검토해야 합니다.모든 값이 될 수 있는 버튼_3이 있습니다. 즉, 3열의 1은 해당 항목이 있는 행이 버튼_3의 영향을 받는다는 의미입니다.따라서 Button_3을 사용하는 솔루션이 더 짧은지 확인하고 싶다고 가정해 보겠습니다.우리는 또 다른 행렬을 생성하지만 지금은 버튼_3을 1로 설정합니다(이전에 무엇이든 될 수 있다고 설정했고 거기에 이미 0이 있으므로 이제 1을 확인합니다).이제 다음 행렬로 끝납니다.

우리는 이를 가능한 한 많이 줄였으며 이제 다음 매트릭스로 끝납니다.

이는 여전히 유효한 솔루션이지만 솔루션이 더 길다는 것을 알 수 있으므로(버튼을 2번 누르는 대신 3번 필요) 이를 폐기합니다.우리가 찾은 행을 모두 0에서 1로 설정하는 모든 순열에 대해 이 작업을 수행해야 합니다.따라서 모두 0인 x개의 행이 있는 경우 시스템에는 x^2개의 솔루션이 있으며 이를 모두 확인해야 합니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow