NP-трудно правильно играть международные шашки?

26

Является ли следующая проблема NP-трудной?

Учитывая конфигурацию доски для n×n международных шашек , найдите один законный ход.

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

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

Как и в шашках, одна и та же фигура может быть использована для захвата серии фигур за один ход. Однако, в отличие от шашек, захваченные фрагменты в международных проектах не удаляются, пока не закончится вся последовательность. Захватывающая фигура может перепрыгивать или приземляться в одном и том же пустом квадрате несколько раз, но она не может перепрыгивать фигуру противника более одного раза.

Наконец, и шашки, и международные шашки имеют правило принудительного захвата: если вы можете захватить фигуру противника, вы должны это сделать. Тем не менее, правила правила не согласны, когда есть несколько вариантов для нескольких. В шашках вы можете выбрать любую максимальную последовательность захватов; другими словами, вы можете выбрать любую последовательность захвата, которая заканчивается, когда часть захвата больше не может захватывать. В международных шашках вы должны выбрать самую длинную последовательность захватов. Таким образом, моя проблема эквивалентна следующему:

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

Достаточно доказать, что следующая задача является NP-полной. (Это очевидно в NP.)

Учитывая конфигурацию доски для международных драфтов с участием только королей , может (и поэтому должен) один игрок захватить все фигуры своего противника за один ход?N×N

На соответствующую задачу проверки можно ответить за полиномиальное время; это занимательное домашнее задание. Эта проблема выглядит более похожей на анализ Демейном, Демейном и Эппштейном финальных матчей Футбола ; решение развлекательной домашней работы появляется в конце их статьи. Решение также появляется в документе FOCS 1978 Frankel et al. это доказывает, что оптимально играть в шашки очень сложно; см. также доказательство Робсона 1984 года о том, что шашки на самом деле завершены.

Jeffε
источник
опечатка? «это очевидно в P» - может быть, вы имеете в виду «в NP»? Кроме того, ГДЕ вы получаете эти вопросы?
Суреш Венкат
Да, исправлено. Также перефразировал проблему; не ясно, что количество законных ходов с данной позиции является только полиномиальным.
Джефф
Это выходит из написания решения для "развлекательной домашней работы".
Джефф
Я предполагаю, что невысказанный дополнительный вопрос состоит в том, какова сложность самой игры (определяя, может ли один игрок выиграть)? Это EXPTIME-полная, как шашки? Возможно, но доказательство для шашек довольно сложно.
Боб Хирн

Ответы:

24

Хорошо, вот сокращение. Оказывается, вам не нужна планарность в конце концов. Кроме того, для «найти законный ход» я принимаю вопрос о решении как «ход Х законен?».

Во-первых, давайте вместо этого поработаем с игрой, в которой фигуры движутся ортогонально, а не по диагонали. Эта игра эквивалентна (просто посмотрите на доску для шашек, повернутую на 45 градусов), за исключением свойств ребер, которые мы не будем использовать. Мы используем два гаджета: слияние / разделение и кроссовер. См. Http://www.hearn.to/draughts.pdf . Мы предполагаем, что на доске есть один белый король для перемещения. (Ни одна другая фигура не сможет захватить сколько-нибудь значительное количество фигур.) Она будет перемещаться по указанным коридорам, захватывая черные фигуры по пути.

Во-первых, слияние: если король входит в любой из N путей A (посредством захвата черной фигуры, не показана), он может выйти в точке B. Аналогичным образом, если мы перевернем гаджет и он войдет в точку B, захватив показанную фигуру, он может выйти по любому пути A (опять же, захватывая внешнюю черную фигуру). Это одноразовый гаджет (потому что выходной черный кусок может быть захвачен только один раз).

Во-вторых, кроссовер. Если король входит через A (C), он может выйти в B (D). Он не может остановиться посередине и изменить маршруты, потому что это будет сегмент захвата без захвата.

Теперь, учитывая ориентированный граф, построим соответствующую игровую конфигурацию следующим образом. Для каждой вершины создайте слияние, которое подает в разбиение. Направьте выходы разделения на входы слияния гаджетов вершин (слияние + разделение), соответствующие вершинам, к которым соединяются выходящие ребра, при необходимости используя кроссоверы. Запустите короля на дополнительном входе в любую вершину (чтобы захватить черный кусок, чтобы он вошел в вершину).

Наконец, выровняйте все «длины ребер», добавив дополнительные черные фигуры вдоль путей вывода / ввода по мере необходимости. Если есть V вершин и k черных фигур вдоль каждого ребра, то король может захватить 2V + kV + 1 кусков тогда и только тогда, когда существует гамильтонова схема соответствующего графа. Если у короля есть альтернативный ход, захватывая простую цепочку фигур 2V + kV, то определение того, законен ли этот альтернативный ход, является NP-завершенным.

Боб Хирн
источник
2
Хорошее сокращение!
Джефф
Но вы можете ответить на второй вопрос? Является ли выигрыш за один ход NP-сложным?
Джефф
Может быть ... Я думаю, что гаджеты можно изменить так, чтобы после завершения гамильтоновой схемы король мог затем захватить все черные фигуры на "проводах". Внутренние части слияния / разделения будут все еще должны быть захвачены во время гамильтоновой схемы, так что это все равно будет NP-сложным. Идея состояла бы в том, чтобы открыть промежутки в коридорах, смежных с черными фигурами, которые позволили бы пересечь коридоры, но не выходить изнутри.
Боб Хирн
Я предполагаю, что это также потребовало бы некоторого дополнительного навигационного оборудования вне коридоров, но это должно быть выполнимо.
Боб Хирн
5

Вот возможная альтернатива редукции Боба, на этот раз из (ненаправленного) гамильтонова цикла. Я не уверен на 100%, что детали верны - я уже нашел и исправил несколько проблем, - но я уверен, что это можно перевести в правильное доказательство. Как указывает Боб, это сокращение имеет серьезную ошибку; белый король может легко отклониться от своего канонического пути через доску. Эту ошибку можно исправить, добавив перекрестный гаджет Боба в соответствующие места (я думаю) , но тогда он существенно не отличается от его сокращения.

гNмг-1

О(N2)×О(N2)О(N2+м)ККчасNчас

угловой гаджет

горизонтальный 4-сплиттер

запасной гаджет

ККК(я,J)яJИксY

один край

часN2+4Nг

Jeffε
источник
Очень хорошо. Но я вижу пару проблем, одну из которых имеет и мое сокращение. Во-первых, когда король выходит из угла, он может остановиться где угодно, потенциально позволяя ему неуместно войти в другой угол. Во-вторых, нет ничего, чтобы заставить короля вернуться в исходную вершину; это может закончиться на любой вершине. У шахты та же проблема, но ее легко исправить для любого сокращения, добавив соответствующий дополнительный фрагмент для захвата внутри начальной вершины.
Боб Хирн
Вторую проблему легко решить: переместить начальную локацию короля вглубь орды.
Джефф
Но первая проблема более серьезная. Я думаю, нам нужны твои кроссоверы. Убирайся!
Джефф
Я думаю, что удаление черной фигуры выхода из углового гаджета и добавление черной фигуры на каждую руку входного сплиттера для каждой вершины также может помочь.
Боб Хирн
3

Теперь, почему вы не представляли мне эту проблему, когда я работал над диссертацией?

Хорошо, у меня есть сокращение от плоско-направленного гамильтонова цикла.

Боб Хирн
источник
1
Скажи! (Можете ли вы кратко описать сокращение?)
Райан Уильямс
Извини, Боб; тогда не думал об этом. Да, пожалуйста, опишите (или ссылку на) сокращение!
Джефф
Это не совсем ответ.
Дэйв Кларк
1
Нет ... Я думал, что добавил комментарий в то время. Сейчас я не вижу, как добавить комментарий к основному сообщению.
Боб Хирн
Вам нужно 100 репутации, чтобы добавить комментарий. Это feechur.
Джефф