Присоединяйтесь к пяти

«Join Five» (также известный как пасьянс «Морпион», игра «Кросс-н-линии» или игра «Линии» ) — это игра с бумагой и карандашом для одного или двух игроков, в которую играют на сетке точек в форме плюса. Истоки игры, вероятно, находятся в Северной Европе. Упоминания об игре впервые появились во французских публикациях в 1970-х годах. ^{[ 1 ]} Помимо развлечения, игра была предметом теоретических исследований. ^{[ 2 ]} и компьютер ищет решения. ^{[ 3 ]}

Как играть

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

Во время каждого поворота рисуйте прямую линию длиной ровно пять «точек», такую, что:

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

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

Подсчет очков

Игра заканчивается, когда на сетке больше нельзя нарисовать сегменты.

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

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

Стратегия

Стратегия различается в зависимости от того, ведется ли игра в одиночку или против противника. В первом случае ходы оптимизированы на максимально возможное количество ходов; во втором случае цель состоит в том, чтобы быть «неэффективным» с выбором ходов, чтобы ограничить доступные ходы противника.

Вариации

Правила могут быть изменены, требуя линий из 4 отмеченных точек подряд, а не из 5, с уменьшенной стартовой конфигурацией. Кроме того, «непересекающийся» вариант игры не позволяет двум параллельным линиям иметь общую конечную точку, тогда как стандартная «касающаяся» версия позволяет это. ^{[ 4 ]}

Записи и компьютерные поиски

Для «трогательной» версии игры с линиями, состоящими из 5 отмеченных точек, нынешний рекорд в 178 линий был установлен 12 августа 2011 года с помощью поиска Монте-Карло алгоритмиста Кристофера Розина. ^{[ 5 ]}^{[ 6 ]} Это на восемь ходов больше, чем предыдущий рекорд 1976 года в 170 строк. ^{[ 3 ]}^{[ 5 ]}^{[ 7 ]} Запись 1976 года была сделана вручную, и компьютерный поиск не смог приблизиться к этой записи. ^{[ 7 ]} несмотря на существенный прогресс, ^{[ 8 ]} до августа 2010 года, когда Кристофер Розин использовал поиск в Монте-Карло и получил результат в 172 хода, превысивший рекорд 1976 года, и 178 ходов год спустя. ^{[ 6 ]}

Для «непересекающегося» варианта игры с линиями, состоящими из 5 отмеченных точек, рекорд — 82 линии. ^{[ 9 ]} был получен с помощью компьютерного поиска, также найден Кристофером Розином. Предыдущий рекорд в 80 строк был найден в 2008 году Тристаном Казенавом. ^{[ 10 ]} В 2020 году было найдено 67-шаговое решение с использованием подхода, подобного AlphaZero . ^{[ 11 ]}

Теория

Обобщенный морпионный пасьянс, в котором стартовой конфигурацией может быть любой конечный набор отмеченных точек, относится к NP-трудному классу задач, для которых не известен эффективный вычислительный метод поиска оптимального решения. Даже задача нахождения приближенно оптимального решения обобщенного морпионного пасьянса является NP-трудной. ^{[ 2 ]}

Для стандартных версий пасьянса «Морпион» не существует бесконечно больших решений; верхние границы доказаны ^{[ 2 ]} на максимальное количество строк, которое можно получить. ^{[ 12 ]}

Ссылки

^ «Пасьянс Морпион — Происхождение» . www.morpionsolitaire.com . Получено 19 февраля 2023 г. и ссылки в нем.
^ Jump up to: ^а ^б ^с Демейн, Эрик Д .; Демейн, Мартин Л .; Лангерман, Артур; Лангерман, Стефан (2006), «Пасьянс Морпион» (PDF) , Теория вычислительных систем , 39 (3): 439–453, doi : 10.1007/s00224-005-1240-4 , MR 2218413 , S2CID 9664785
^ Jump up to: ^а ^б Т. Казенав, «Рефлексивный поиск в Монте-Карло» , Семинар компьютерных игр, 2007 г.
^ Бойер, Кристиан. «Пасьянс Морпион – Правила игры» . www.morpionsolitaire.com . Проверено 19 февраля 2023 г.
^ Jump up to: ^а ^б Бойер, Кристиан. «Пасьянс Морпион – Рекордные сетки (игра 5Т)» . www.morpionsolitaire.com . Проверено 19 февраля 2023 г.
^ Jump up to: ^а ^б Розин, Крис. «Новая запись пасьянса Морпион через поиск Монте-Карло» . www.chrisrosin.com . Проверено 19 февраля 2023 г.
^ Jump up to: ^а ^б Бойер, Кристиан. «Пасьянс Морпион – Список новостей сайта добавлен 15 февраля 2010 г.» . www.morpionsolitaire.com . Проверено 19 февраля 2023 г.
^ Х. Хюрё и Т. Поранен (2007). «Новая эвристика пасьянса Морпион» .
^ Бойер, Кристиан. «Пасьянс Морпион – Рекордные сетки (5D-игра)» . www.morpionsolitaire.com . Проверено 19 февраля 2023 г.
^ Т. Казенав, «Вложенный поиск в Монте-Карло» , IJCAI 2009, стр. 456–461.
^ Ван, Хуэй; Пройсс, Майк; Эммерих, Майкл; Плаат, Аске (14 июня 2020 г.). «Решение пасьянса «Морпион» с помощью обучения с подкреплением вознаграждений в стиле AlphaZero». arXiv : 2006.07970 [ cs.AI ].
^ Бойер, Кристиан. «Пасьянс Морпион – Ограничения по очкам» . www.morpionsolitaire.com . Проверено 19 февраля 2023 г.

Внешние ссылки

[1] «Пасьянс Морпион — Происхождение» . www.morpionsolitaire.com . Получено 19 февраля 2023 г. и ссылки в нем.

[theory-2] Jump up to: ^а ^б ^с Демейн, Эрик Д .; Демейн, Мартин Л .; Лангерман, Артур; Лангерман, Стефан (2006), «Пасьянс Морпион» (PDF) , Теория вычислительных систем , 39 (3): 439–453, doi : 10.1007/s00224-005-1240-4 , MR 2218413 , S2CID 9664785

[reflexive-3] Jump up to: ^а ^б Т. Казенав, «Рефлексивный поиск в Монте-Карло» , Семинар компьютерных игр, 2007 г.

[4] Бойер, Кристиан. «Пасьянс Морпион – Правила игры» . www.morpionsolitaire.com . Проверено 19 февраля 2023 г.

[5trecords-5] Jump up to: ^а ^б Бойер, Кристиан. «Пасьянс Морпион – Рекордные сетки (игра 5Т)» . www.morpionsolitaire.com . Проверено 19 февраля 2023 г.

[montecarlo-6] Jump up to: ^а ^б Розин, Крис. «Новая запись пасьянса Морпион через поиск Монте-Карло» . www.chrisrosin.com . Проверено 19 февраля 2023 г.

[feb2010-7] Jump up to: ^а ^б Бойер, Кристиан. «Пасьянс Морпион – Список новостей сайта добавлен 15 февраля 2010 г.» . www.morpionsolitaire.com . Проверено 19 февраля 2023 г.

[8] Х. Хюрё и Т. Поранен (2007). «Новая эвристика пасьянса Морпион» .

[9] Бойер, Кристиан. «Пасьянс Морпион – Рекордные сетки (5D-игра)» . www.morpionsolitaire.com . Проверено 19 февраля 2023 г.

[nested-10] Т. Казенав, «Вложенный поиск в Монте-Карло» , IJCAI 2009, стр. 456–461.

[11] Ван, Хуэй; Пройсс, Майк; Эммерих, Майкл; Плаат, Аске (14 июня 2020 г.). «Решение пасьянса «Морпион» с помощью обучения с подкреплением вознаграждений в стиле AlphaZero». arXiv : 2006.07970 [ cs.AI ].

[12] Бойер, Кристиан. «Пасьянс Морпион – Ограничения по очкам» . www.morpionsolitaire.com . Проверено 19 февраля 2023 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]