Самая короткая игра Халмы с 2 игроками

19

В шахматах игра может завершиться после 4 ходов (по 2 в каждом) с помощником дурака .

Ваша цель состоит в том, чтобы найти Дурака Матем Халма : игра Халмы для 2 игроков, которая сводит к минимуму количество ходов.

Существует более 10 56 состояний плат, и я видел, что коэффициент ветвления превышает 1000, так что скорее всего никто не найдет оптимального решения. Вместо этого вы пытаетесь найти лучшее решение, которое вы можете.

Вы должны предоставить список ходов и любой код, который вы использовали для генерации этих ходов.

Объяснение игры

Халма похожа на китайские шашки, но играется на доске размером 16 * 16.

Изначально плата выглядит так:

Стартовая доска

Цель игры состоит в том, чтобы переместить все ваши фигуры в исходные позиции фигур вашего противника.

На ходу игрока он / она может:

  • Пройти поворот

  • Переместите одну из его фигур в соседнее пустое пространство. Смежные пространства включают диагонали.

  • Возьмите одну из его / ее фигур и сделайте следующее любое количество раз: Перепрыгните фигуру на смежную фигуру, посадив ее на место напротив перепрыгнутой фигуры.

Вот пример, чтобы проиллюстрировать 2-й тип движения.

Переходы

правила

Отправить список законных ходов, которые приводят к окончанию игры.

Отправьте любой код, который вы использовали для создания списка.

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

Каждое движение должно быть либо Noneдля прохождения поворота, либо (x1,y1,x2,y2)для перемещения фигуры, где (x1,y1)находятся координаты фигуры для перемещения и (x2,y2)пункт назначения этой фигуры (для прыжковых движений игнорируйте промежуточные координаты). Координаты начинаются в (0,0)верхнем левом углу. x-координаты увеличиваются вправо, y-координаты увеличиваются вниз. Ходы должны быть разделены переносами.

Вы можете использовать этот скрипт Python для проверки ваших ходов. Используйте, python halma_verify.py < fileчтобы проверить движение file.

Самый короткий список побед.

картонная коробка
источник
6
некоторое техническое обсуждение ходов и решение в 47 ходов: arxiv.org/pdf/0803.1245.pdf
SeanC

Ответы:

17

Самая короткая игра в халму - 49 ходов

49 ход решения

Доказательство, что нет 48-ходового решения

Код, используемый для этого решения

Код теперь поддерживает проход

Обратите внимание, что решение с 47 ходами в статье предназначено для задачи переброски армии, а не для самой короткой игры в халму

Я надеюсь, что в эти выходные я смогу сделать правильную запись

Тон Хоспел
источник