Шахматы 3x4 - решены

Шахматы на доске 3х4 - строго решены. Это означает что для любой позиции известен результат (при оптимальной игре обеих сторон) и лучший ход. Я использовал метрику DTM - расстояние до мата.

Правила: Доска - 3 поля по горизонтали, 4 по вертикали. Нет рокировки, нет двойного первого хода пешки, остальные правила те же что в шахматах. Начальная позиция - неопределена, поэтому просчитаны все возможные позиции, включая позиции с пешками на первой горизонтали (последней для чёрных).

Число позиций: 167,303,246,916 (учитывая все возможные симметрии).

Самая длинная линия до мата: 43 хода (85 полуходов).

Подробности на английском языке:
Страничка проекта (В процессе создания)
Обсуждение

Вопросы/комментарии приветствуются.

Вот ведь как!

Там дальше объясняется, почему это не так. Нужно считать не все позиции, а только те, где нам ещё не мат, не пат, и не шах. Правильный ответ сейчас вычисляется.

167 ГБ в несжатом виде. Теперь я уже сжал их в 59 ГБ. Можно сжимать и сильнее, но ценой падения скорости обращения. Возможно ещё поэкспериментирую со сжатием, но 59 ГБ меня пока устраивают.

Сейчас я строю DTC таблицы, в них тоже обнаруживаются залежи интересного. DTC таблицы сжимаются, конечно, гораздо лучше. 12-фигурка в DTC превращается в бит-базу.

DTC генерируется быстрее. Точно сейчас не скажу на сколько, так как DTM я генерировал без сжатия, а DTC сразу сжимаю. Разницу в размерах опишу на сайте, когда закончу построение DTC. Многое будет зависеть от того, насколько сильно сожмётся 12-фигурка.

Меньше максимальное значение метрики, следовательно нужно меньше итераций. Кроме того DTC лучше жмётся, что ускоряет чтение и запись на диск.

4x4 - это, конечно, очень интересно. Боюсь что на него у меня пока что не хватит мощей железа. (Если речь о полном решении). Но в любом случае сначала нужно 3х4 докопать до дна.

Да, 3х5 хороший вариант. Есть ещё 4х3 и 5х3, они немного проще, чем 3х4 и 3х5, но и менее интересны.

Как я понимаю, нет, не строго, но решение надёжное и с очень большой вероятностью безошибочное.

Не строго из-за использования эвристик для отсечения перебора.

Как вы любите всё мешать в одну кучу! Уверен, что потом вы радостно назовёте это всё хаосом.

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

Моё решение строго, так как не использует эвристики. Я не пытаюсь рассуждать "здесь у белых два ферзя за коня, наверное белые победят". Для каждой позиции я вычисляю точную оценку.

Моё решение полно, так как включает в себя все вообразимые легальные позиции.

Насчёт безошибочности судить наверняка сложно. Таблицы до 9 фигур прошли автоматическую проверку. Но в коде проверки в принципе тоже могут быть ошибки. В идеале нужно независимое подтверждение.

Кстати, для таблиц до 6 фигур без пешек и без 5-1 мне прислал статистику Марк Буржуцкий. Он использовал модифицированный генератор Налимова. Наибольшие расстояния до выигрыша у нас с ним совпали по всем таблицам. Число позиций сравнить не удалось, так как в его статистике позиции считаются по-другому. Я считаю только строго уникальные позиции, он считает некоторые позиции дважды.

Для сравнения, решение шашек командой Chinook - не строгое и не полное. Ну а насчёт безошибочности они, по-видимому, могут быть уверены настолько же, насколько и я.

Да, ошибки могут быть нескольких типов:
1. Ошибка нестрогого доказательства.
2. Ошибка в программе.
3. Случайная аппаратная ошибка.

Ошибок первого типа у меня быть не может. Ошибки второго типа - исключить полностью нельзя, но успешная верификация 9-фигурки позволяет надеяться на их отсутствие. Ошибки третьего типа - будут исключены если найдётся доброволец и сгенерирует все таблицы моей программой на своём железе, и если его статистика совпадёт с моей.

Вычислился. Если учитывать только позиции где ход белых, и где белым не мат, не шах, и не пат, то белые набирают 66.10% очков.

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

(DTC таблицы посчитаны до 10 фигур целиком, 11-фигурные считаются).

Сколько времени занял полный расчёт? Сколько выходит в среднем на одну позицию? Другими словами, нельзя ли просто поставить заданное начальное положение, и достаточно быстро получить абсолютную оценку нормальным, а не ретроанализом?

Полное решение в метрике DTM заняло где-то неделю. Одна позиция решается в среднем за 3.8 микросекунды.

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

Что ж, приходится признать, вам это удалось.

Ну, в шашках такой подход вполне может быть оправдан. Со стороны мне трудно судить. Вообще, Хайдук, у меня к вам предложение. Раз вам так интересно решение шашек, давайте вы ознакомитесь со статьями Шаефера, и потом уже вы мне расскажете какие именно у них решение.

Под "неполнотой" решения шашек командой Chinook я имел ввиду, что они решили не все возможные позиции, а только 10-фигурные эндшпили, и некоторое множество позиций, достижимых из начальной позиции (но не все такие позиции). Понятное дело, что они и не ставили цель решить все позиции. И это нисколько не умаляет их заслуг. Они сделали, наверное, максимум возможного на текущем этапе. Их решение шашек заняло где-то 20 лет, за одно это они заслуживают крайнего уважения.

Итак, трум-трум-трум... Под барабанную дробь на сцену выносят доску 3х4. На доске мат в 43 хода. Посмотреть в интерфейсе.

Ещё пара интересных позиций, теперь в метрике DTC.

wkpnpRpK..P.N. 9 фигур, расстояние до конверсии - 16 ходов (31 полуход).

wRQBKB.PPPk.q. 10 фигур, всего 2 свободных поля, расстояние до конверсии - 14 ходов (27 полуходов) :|

Даже на такой куцей доске мат конём и слоном еле ставится

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

Сделал графическую доску. Коряво, но пока пойдёт... (Дизайнер проекту бы не помешал).

Завершён первый этап "раскопок" - я сохранил по одной позиции с наибольшим расстоянием до мата для каждой конфигурации фигур. Скачать

Теперь можно посмотреть, например, самый длинный выигрыш королём и слоном, или как долго (и из какой позиции) максимум держится голый король против 10 фигур, и т.д.

(Такая же подборка, какую я собирал для обычных шахмат вот здесь: http://kirill-kryukov.com/chess/longest-checkmates/)

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

Документация будет дорабатываться, на вопросы буду рад ответить.

До 4х4 предстоит долгий путь. Если, конечно, речь о полном решении. Что-то вроде 6 - 7-фигурки можно посчитать довольно легко.

Настоящие пятнашки там происходят в метрике DTC, например, здесь или здесь. Попробуйте пройти по первой линии до размена.

Всем привет! Я выложил новую версию генератора (1.1.0) на страничку проекта. Список изменений. В основном изменения направлены на уменьшение размера таблиц:

1. Добавлено сжатие LZMA.

2. Добавлено автоопределение оптимального метода компрессии для каждого блока данных.

3. Немного изменён формат таблиц: блоки иногда объединяются вместе, иногда нет.

4. Позиции под шахом сохраняются отдельно от остальных.

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

6. Добавлена команда '-shrink' - дополнительное урезание базы путём удаления по одной таблице из каждой пары. Например, "krkp - kpkr" - это пара таблиц. '-shrink' оставит только одну из них, а вторую удалит.

В результате всех этих мер полная база DTM, от 3 до 12 фигур, занимает теперь 50.6 ГБ. После удаления 12-фигурных таблиц и урезания 3-11-фигурных остаются всего 11.8 ГБ, позволяющие тем не менее проверять любую из возможных позиций.

Формат таблиц не совместим с версией 1.0.0 генератора, нужно генерировать всё с нуля.

Вопросы, баг-репорты, умные мысли и добрые советы приветствуются.