Берлекамп игра переключения - Berlekamp switching game - Wikipedia

В Берлекамп игра переключения это математическая игра предложенный американским математиком Элвин Берлекамп.^[1] Его также называли Игра с переключением Гейла – Берлекампа, после Дэвид Гейл, которые открыли ту же игру независимо,^[2] или игра с разбалансировкой света.^[3] Он включает в себя систему лампочки управляется двумя группами переключателей: один игрок пытается включить много лампочек, а другой - выключить как можно больше. Его можно использовать для демонстрации концепции радиус покрытия в теория кодирования.

Правила

Оборудование для игры состоит из комнаты, содержащей прямоугольный набор лампочек размером ${\displaystyle a\times b}$ для некоторых номеров ${\displaystyle a}$ и ${\displaystyle b}$. Банк ${\displaystyle ab}$ переключатели на одной стороне комнаты управляют каждой лампочкой индивидуально. При повороте одного из этих переключателей его лампочка переключается с включенной на выключенную или с включенной на выключенную, в зависимости от ее предыдущего состояния. По другую сторону комнаты находится еще один блок ${\displaystyle a+b}$ переключатели, по одному на каждый ряд или столбец лампочек. Каждый раз, когда любой из этих переключателей щелкает, каждая лампочка в строке или столбце, которыми он управляет, переключается с включенного на выключенное или с включенного на выключенное, в зависимости от своего предыдущего состояния. При переключении более чем одного переключателя порядок, в котором переключатели переключаются, не имеет значения для результата: одни и те же лампочки будут гореть в конце последовательности переключений независимо от того, в каком порядке они переключены.

Игра состоит из двух туров. В первом раунде первый игрок использует переключатели, управляющие отдельными огнями, чтобы произвольно включать или выключать свет. Во втором раунде второй игрок использует переключатели, которые управляют рядами или столбцами огней, изменяя набор огней, установленный первым игроком, на другой образец (или, возможно, оставляя его без изменений). Цель первого игрока состоит в том, чтобы в конце игры оставалось гореть как можно больше огней, а цель второго игрока - оставить гореть как можно меньше огней. Следовательно, первый игрок должен выбрать такую ​​схему огней, при которой второй игрок не может выключить много источников света.

История

Берлекамп работал в Bell Labs в Мюррей Хилл, Нью-Джерси с 1966 по 1971 гг.^[4] Находясь там, он сконструировал физический экземпляр этой игры для случая ${\displaystyle 10\times 10}$ в комнате общего пользования математического факультета.^[1][2] Дэвид Гейл также самостоятельно изобрел игру, за некоторое время до 1971 года.^[5]

Ранние исследования по связанным проблемам включали публикации Эндрю М. Глисон  (1960 ), чьи компьютерные эксперименты можно интерпретировать как запрашивающие ${\displaystyle 15\times 15}$ игра, насколько хорошо второй игрок может выступить против первого игрока, который играет случайным образом,^[6] и Дж. У. Мун и Лео Мозер  (1966 ), которые теоретически рассматривают вопрос Глисона, показывая, что для почти все выбор первого игрока, в пределе больших размеров игрового поля оптимальное значение игры близко к ${\displaystyle {\tfrac {1}{2}}n^{2}}$.^[7]

Анализ

Математически можно описать огни, включенные ходом первого игрока, как набор ${\displaystyle S}$, и наименьшее количество огней, которое может быть достигнуто лучшей игрой для второго игрока в виде числа ${\displaystyle f(S)}$. Лучшая игра для первого игрока - выбрать сет. ${\displaystyle S}$ что максимизирует ${\displaystyle f(S)}$. Следовательно, можно описать наибольшее количество огней, которое может быть достигнуто при лучшей игре для первого игрока, как число ${\textstyle R_{a,b}=\max _{S}f(S)}$. Помимо вопроса о том, как хорошо играть в отдельной игре, более широкий вопрос, который был предметом математических исследований, состоит в том, чтобы охарактеризовать ценность ${\displaystyle R_{a,b}}$ в общем, как функция ${\displaystyle a}$ и ${\displaystyle b}$, чтобы определить его поведение как функцию или вычислить его значение для как можно большего количества комбинаций ${\displaystyle a}$ и ${\displaystyle b}$ насколько возможно.

Случай квадрата ${\displaystyle n\times n}$ массив был решен для ${\displaystyle n\leq 12}$. Кроме того, нижняя граница за ${\displaystyle R_{n,n}}$ были найдены для ${\displaystyle n\leq 20}$.^[8][9] Вот эти числа:

Решения для ${\displaystyle n\times n}$

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
${\displaystyle R_{n,n}}$	0	1	2	4	7	11	16	22	27	35	43	54	≥ 60	≥ 71	≥ 82	≥ 94	≥ 106	≥ 120	≥ 132	≥ 148

Асимптотически, эти числа растут как ${\displaystyle {\tfrac {n^{2}}{2}}-\Theta (n^{3/2})}$.^[2][5][10]

Вычислительная сложность

Поскольку существует экспоненциально много вариантов переключения переключателей, исчерпывающий поиск оптимального выбора невозможен для больших ${\displaystyle n}$, задавая вопрос о том, насколько хорошо в эту игру могут играть игроки с ограниченными вычислительными возможностями.

Первый игрок может вызвать ожидаемую ценность игры. ${\displaystyle {\tfrac {n^{2}}{2}}-O(n^{3/2})}$ играя в случайном порядке. Точно так же второй игрок может получить значение, ожидаемое расстояние от которого ${\displaystyle {\tfrac {n^{2}}{2}}}$ является ${\displaystyle \Omega (n^{3/2})}$ играя в случайном порядке; это значение может быть больше или меньше, чем ${\displaystyle {\tfrac {n^{2}}{2}}}$, но если он больше, второй игрок может перевернуть все переключатели строк, чтобы получить значение, меньшее на ту же величину.^[2][5][10] Эту случайную стратегию для второго игрока можно сделать неслучайной, используя метод условных вероятностей, давая полиномиальное время алгоритм, который гарантирует то же значение решения. Отличающийся дерандомизация дает параллельный алгоритм в классе сложности NC.^[11]

Поиск оптимального выбора для второго игрока в игре после того, как первый игрок выбрал, какие лампочки зажигать, является NP-жесткий проблема.^[12] Однако есть схема полиномиальной аппроксимации для ${\displaystyle n\times n}$ игра, которая может найти выбор для второго игрока, который оставляет только ${\displaystyle (1+\varepsilon )}$ раз минимально возможное количество зажженных лампочек для любого ${\displaystyle \varepsilon >0}$, во время ${\displaystyle O(n^{2})+2^{O(1/\varepsilon ^{2})}}$.^[13]

Связь с теорией кодирования

Игру переключения Berlekamp можно использовать в теория кодирования как демонстрация радиус покрытия определенного двоичного линейный код. Двоичный линейный код длины ${\displaystyle n}$ и размер ${\displaystyle d}$ определяется как ${\displaystyle d}$-размерный линейное подпространство из ${\displaystyle n}$-размерный векторное пространство ${\displaystyle \mathbb {F} _{2}^{n}}$ над конечное поле с двумя элементами, ${\displaystyle \mathbb {F} _{2}}$. Элементы подпространства называются кодовыми словами, а радиус покрытия - наименьшее число. ${\displaystyle r}$ так что каждая точка ${\displaystyle \mathbb {F} _{2}^{n}}$ внутри Расстояние Хэмминга ${\displaystyle r}$ кодового слова.

Позволять ${\displaystyle n=ab}$ и ${\displaystyle d=a+b-1}$. Для этих значений параметров векторное пространство ${\displaystyle \mathbb {F} _{2}^{n}}$ описывает все возможные схемы горящих лампочек на ${\displaystyle a\times b}$ массив лампочек с операцией сложения вектора, которая объединяет два шаблона, зажигая лампочки, которые появляются точно в одном из двух шаблонов ( симметричная разница работа на наборах зажженных лампочек). Можно определить линейное подпространство, состоящее из всех шаблонов, которые второй игрок может полностью выключить, или, что эквивалентно, всех шаблонов, которые второй игрок может создать, начиная с полностью выключенной доски. Хотя у второго игрока ${\displaystyle 2^{a+b}}$ выбор того, как установить второй блок переключателей, это подпространство ${\displaystyle 2^{a+b-1}}$ элементы, придавая ему размер ${\displaystyle a+b-1}$, потому что переключение всех переключателей второго игрока не влияет на узор горящих лампочек.

потом ${\displaystyle R_{a,b}}$ - радиус покрытия этого кода. Набор зажженных лампочек, выбранный первым игроком с лучшей игрой, дает очко ${\displaystyle \mathbb {F} _{2}^{n}}$ то есть как можно дальше от линейного подпространства. Набор лампочек, состояние которых изменяется вторым игроком с наилучшей игрой, дает ближайшую точку в линейном подпространстве. Набор лампочек, которые остаются гореть после этого выбора, - это те, номер которых определяет расстояние Хэмминга между этими двумя точками.^[1]

Смотрите также

• Lights Out (игра), другая головоломка, включающая выключение лампочек с помощью переключателей, управляющих несколькими лампочками.

Рекомендации

1. Слоан, Н. Дж. А. (1987). «Нерешенные проблемы, связанные с радиусом покрытия кодов». В Обложка, Томас М.; Гопинатх, Б. (ред.). Открытые проблемы в коммуникации и вычислениях. Нью-Йорк: Спрингер. С. 51–56. Дои:10.1007/978-1-4612-4808-8_11.
2. Спенсер, Джоэл (1994). «Лекция 6: Хаос из порядка». Десять лекций о вероятностном методе. CBMS-NSF Серия региональных конференций по прикладной математике. 64 (Второе изд.). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. С. 45–50. Дои:10.1137/1.9781611970074. ISBN  0-89871-325-0. МИСТЕР  1249485.
3. Араужо, Густаво; Пеллегрино, Даниэль (2019). «Проблема переключения перестановок Гейла – Берлекампа в высших измерениях». Европейский журнал комбинаторики. 77: 17–30. Дои:10.1016 / j.ejc.2018.10.007. МИСТЕР  3872901.
4. Сандерс, Роберт (18 апреля 2019 г.). «Элвин Берлекамп, теоретик игр и пионер программирования, умер в возрасте 78 лет». Новости Беркли. Калифорнийский университет в Беркли.
5. Brown, Thomas A .; Спенсер, Джоэл Х. (1971). "Минимизация ${\displaystyle \pm 1}$ матрицы при сдвиге строк ». Математический коллоквиум. 23: 165–171, 177. Дои:10.4064 / см-23-1-165-171. МИСТЕР  0307944.
6. Глисон, Эндрю М. (1960). "Проблема поиска в ${\displaystyle n}$-куб ». В Беллман, Ричард; Холл, Маршалл-младший. (ред.). Комбинаторный анализ. Материалы симпозиумов по прикладной математике. 10. Провиденс, Род-Айленд: Американское математическое общество. С. 175–178. МИСТЕР  0114323.
7. Moon, J. W .; Мозер, Л. (1966). «Экстремальная задача теории матриц». Математики Весник. 3(18) (37): 209–211. МИСТЕР  0207570.
8. Карлсон, Иордания; Столярский, Даниэль (октябрь 2004 г.). «Правильное решение игры переключения Берлекампа». Дискретная математика. 287 (1–3): 145–150. Дои:10.1016 / j.disc.2004.06.015. МИСТЕР  2094708.
9. Слоан, Н. Дж. А. (ред.). «Последовательность A005311 (решение игры Берлекэмпа (или игры с лампочкой) на доске n X n)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
10. Комлос, Я.; Сулек, М. (1970). "По сумме элементов ${\displaystyle \pm 1}$ матрицы ». Комбинаторная теория и ее приложения, II (Proc. Colloq., Balatonfüred, 1969). С. 721–728. МИСТЕР  0299500.
11. Бергер, Бонни (1997). «Метод четвертого момента». SIAM Журнал по вычислениям. 26 (4): 1188–1207. Дои:10.1137 / S0097539792240005. МИСТЕР  1460721.
12. Рот, Рон М .; Вишванатан, Кришнамурти (2008). «О сложности декодирования кода Гейла – Берлекампа». IEEE Transactions по теории информации. 54 (3): 1050–1060. Дои:10.1109 / TIT.2007.915716. МИСТЕР  2445050.
13. Карпинский, Марек; Шуди, Уоррен (2009). «Схема линейной аппроксимации времени для игры Гейла – Берлекампа и связанных с ней задач минимизации». В Митценмахер, Майкл (ред.). Материалы 41-го ежегодного симпозиума ACM по теории вычислений, STOC 2009, Бетесда, Мэриленд, США, 31 мая - 2 июня 2009 г.. ACM. С. 313–322. Дои:10.1145/1536414.1536458.