Алгоритм решения игры (Буттония, вариант с выключением света)

https://stackoverflow.com/questions/1211560

06-07-2019
|

Вопрос

Я пытаюсь создать функцию разрешимости для игрового алгоритма.По сути, это функция, которая возвращает true или false для данной игры, если она разрешима или нет.

Это игра Buttonia.com (которая пока не реализует алгоритм), разновидность игры без света.По сути, у вас есть сетка кнопок, каждая из которых при нажатии меняет состояние некоторых своих соседей.В настоящее время я генерирую случайную конфигурацию игры, а затем, насколько это возможно, применяю эвристику.Остальное решается перебором.

На данный момент моим прогрессом было создание системы уравнений для моделирования игры.Поскольку каждой кнопке необходимо изменить состояние нечетное количество раз, чтобы оказаться в нажатом состоянии, ее уравнение будет таким:

button_A = 1 - (кнопка_1 + кнопка_2 + ...+ кнопка_X) % 2

Где от button_1 до button_X — это состояния кнопок, влияющих на кнопку_A.Некоторые кнопки могут быть разрешены сразу, если они не зависят от других.В остальном я пробую одну конфигурацию, пока не возникнет конфликт, а затем возвращаюсь назад.

В настоящее время этот алгоритм практичен для небольших конфигураций игр.Я тестировал его от игр 3x3 до размеров 10x10.Где 6x6 — это верхний предел практической игры.

Уравнения значительно сокращают пространство поиска от грубой силы, делая его практичным.Возможно, существует чисто математический способ решения системы уравнений.

Пример игры 3х3 в ascii (из 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), так что вы можете использовать один из обычных методов для их решения - например, сокращение строк системы в матричной форме (википедия) .

Поскольку это не ограниченная по времени проблема (ну, если предположить, что это можно сделать менее чем за день), я бы, вероятно, пошел на поиск в ширину с ограничением по глубине, принимая каждое возможное движение на уровне, а затем каждый ход, следующий за каждым ходом.

Он будет медленным, однако почти гарантированно найти ответ, если он есть!

Предположим, вы построили систему уравнений и решили их наилучшим образом, но некоторые строки оказались со всеми нулями в левой части уравнения (я представляю уравнения в виде расширенной матрицы) Предположим, вы пытались решить систему в кольце 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

поэтому мы точно знаем, что button_0 равен 1. Поэтому в этой системе, хотя мы не могли напрямую определить button_3, у нас все еще есть правильное решение.

Сгенерированной выше матрицы достаточно для проверки на разрешимость. Если строка содержит все 0, то по сути это означает, что

nothing = nothing

или, чтобы лучше понять, почему это работает,

0x = 0

, что имеет смысл, система все еще действует. Однако, если мы встречаем строку со всеми 0s кроме самого правого бита, т.е.

0000 1

что бы сказать

0x = 1

что невозможно, поэтому мы теперь знаем, что система не может быть решена, поскольку мы не можем решить невозможную ситуацию, подобную этой.

Поэтому, в двух словах, попытайтесь решить уравнение как можно лучше, не беспокойтесь, если вы не можете точно определить, что представляют собой некоторые переменные, если вы в любой момент не можете встретить невозможное. Строка, которую я только что упомянул, тогда игра разрешима.

Но что, если нам нужно самое короткое решение для системы? Здесь мы должны рассмотреть все возможные решения. У нас есть кнопка_3, которая может иметь любое значение, поэтому это означает, что любая 1 в столбце 3 означает, что на строку, в которой она найдена, действует кнопка_3. Итак, предположим, что мы хотим проверить, будет ли решение, использующее button_3, короче. Мы создаем другую матрицу, но теперь устанавливаем для button_3 значение 1 (поскольку ранее мы установили, что это может быть что угодно, и у нас там уже было 0, поэтому теперь мы проверяем 1). Теперь мы получим следующую матрицу:

Мы уменьшили это настолько, насколько смогли, и теперь получаем следующую матрицу:

Это все еще верное решение, однако мы видим, что решение длиннее (требуется 3, а не 2 нажатия кнопок), поэтому мы отбрасываем его. Мы должны сделать это для каждой перестановки установки строк, которые мы нашли как все 0s к 1. Поэтому, если у нас есть x строк, которые были всеми 0, то у системы есть x ^ 2 решения, и мы должны проверить все из них.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow