Шахматы 4x4

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

По доске Клейна
далеко ли ты скачешь,
сферический конь?

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

За это время я посчитал позиции с 10 и 11 фигурами (уникальные легальные позиции на доске 4х4): 4,595,929,598,727 и 27,669,037,598,574, соответственно. Это позволяет слегка уточнить оценку общего числа уникальных легальных позиций, которая теперь составляет 3,601,092,320,644,800, что слегка больше предыдущих оценок.

Если честно, все эти триллионы не очень хорошо укладываются у меня в голове. Глядя на доску 4х4, трудно представить как там помещается такая прорва позиций.

А огород вам заодно не вскопать? Знали б вы на сколько интересных проектов у меня не хватает рук и ног.

Неизвестно. Вы, как никто другой, должны понимать, что решение 3.6 квадриллионов позиций займёт некоторое время. В семифигурке самый длинный мат - 54 хода.

Да, именно так и получена приведённая оценка. (С небольшим изменением: теперь я отбрасываю не 2, а 3 первых члена ряда отношений UB/NULP).

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

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

5 фигур, мат в 33 хода

6 фигур, мат в 52 хода

Описание и хелп будут добавлены позже, пока что делаем вид что всё интуитивно. (Вопросы, конечно, приветствуются).

О любых багах и неполадках прошу сообщать.

Пока что тестируем на простых позициях, рекордные 7 и 8 фигур покажу через пару дней.

В моей интерпретации - да, могут.

2rp/k1N1/2R1/K3 w - - 0 1
1.Nb1+!! Kb3 2.Rb2+!! Ka4□ 3.Ra2+! Kb4 4.Na3! Rc3 5.Nc2+! Kc4 6.Kb2♢ Kd3 7.Na3!! Rb3+ 8.Kc1!! Rc3+ 9.Kd1! Rb3 10.Ra1! Rb4 11.Kc1!! Ra4 12.Ra2! Rb4 13.Nb1! Rc4+ 14.Kd1!! Ra4 15.Rd2+! Kc4□ 16.Rb2! Ra1 17.Kc2♢ d3+ 18.Kc1! Ra4 19.Nd2+! Kd4 20.Rb1! Kc3 21.Rb3+! Kd4□ 22.Nb1! Rc4+ 23.Kd2! Rc2+ 24.Kd1□ Kc4 25.Ra3☉!! Kb4 26.Rxd3!! Ra2 27.Nd2!! Ra3 28.Rd4+!! Kc3□ 29.Rc4+!! Kd3 30.Rb4!! Ra1+ 31.Nb1!! Ra2 32.Rb3+!! Kd4 33.Na3! Rd2+ 34.Kc1!! Ra2 35.Kb1! Ra1+ 36.Kb2♢ Ra2+ 37.Kc1! Ra1+ 38.Nb1! Ra2 39.Rb4+! Kd3□ 40.Kd1!! Ra4 41.Rb2! Rb4 42.Rd2+!! Kc4□ 43.Kc2♢ Ra4 44.Kc1! Rb4 45.Ra2! Rb3 46.Nd2+♢ Kb4 47.Nxb3! Kxb3 48.Rb2+♢ Ka3 49.Kc2♢ Ka4□ 50.Ra2+♢ Kb4□ 51.Ra1! Kc4□ 52.Ra4#

У вас не получилось посмотреть линию в веб-интерфейсе?

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

Позиции с максимальным расстоянием до мата в 7 и 8-фигурке:

7 фигур, 54 хода

8 фигур, 56 ходов

Посчитал 8-фигурку во всех четырёх метриках (DTM, DTC, DTZ, WDL). На этом временно приостанавливаю генерацию таблиц, чтобы продолжить разработку суперкомпрессии.

12 фигур - 125,170,155,996,618 позиций. Новая оценка общего числа позиций: 3.651 квадриллионов, если считать так же, как раньше. Если учесть постоянное уползание оценки вверх и построить более точную модель (детали пока опущу), то общая оценка получается: 3.695 квадриллионов.

Сделаю легенду. Может быть, даже завтра. Пока что можно смотреть легенду здесь.

Ещё не успел скопировать DTC таблицы с 7 и 8 фигурам на машину, хостящую интерфейс. Сегодня вечером будут доступны все метрики, от 2 до 8 фигур.

Судя по всему, с определённого момента наступает насыщение, и быстрый рост сменяется медленным. Это хорошо видно в шахматах 3х4, где насыщение произошло с семью фигурами и 40 ходами до мата. Добавление фигур до 12 увеличило длину максимальной линии всего до 43 ходов. Интересно, что на доске 4х4 быстрый рост maxDTM, похоже, закончился уже на 6 фигурах (52 хода).

Также интересно отметить, что точке насыщения maxDTM, похоже, всегда соответствует пик maxDTC и maxDTZ.

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

Самые обыкновенные мощности - десктоп на 2600K. Считать позиции можно и быстрее, у меня их подсчёт совмещён с кучей ненужных вычислений - выделением памяти, тестированием структур данных. Кроме того, я почти не занимался оптимизацией. (Так в сильно оптимизированный код сложнее вносить радикальные изменения).

Удалось улучшить сжатие таблиц примерно в 2-4 раза (зависит от числа фигур на доске). Причём, сохранён относительно быстрый доступ, поэтому это сжатие используется уже на этапе генерации таблиц. Размеры и плотность WDL таблиц:

Код:

Pieces    Positions          Bytes      Pos/Byte
   3            3,378             434     7.783
   4          227,362          13,915    16.339
   5        8,803,638         421,305    20.896
   6      226,104,696       8,544,456    26.462
   7    4,143,416,867     128,255,407    32.306
   8   56,389,004,075   1,460,432,535    38.611

То есть, храним 38.6 позиций в одном байте в 8-фигурке.

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

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

Рассматриваются. Нортон просто не сумел сформулировать мысль.

Можно придумать ещё критерии нелегальности, например:
5. Позиция с невозможным материалом (недостаточно пешек на все превращения).

6. Позиция с невозожным обходом пешечной цепи:

7. Позиция с правом рокировки, но король должен был ходить:

8. Позиция с правом взятия на проходе, где последний ход был не пешкой:


Мне кажется, реально проверять критерии 1, 2 и 5. Остальные слишком размыты, или требуют нетривиального анализа.

В шахматах 4х4 я использую только критерий 1 и 2, всё остальное - легально, включая любой невозможный материал. Пешки могут стоять на первой горизонтали (чёрные - на четвёртой).

По просьбе Killster-а, выкладываю ещё один набор таблиц: krkrp, 4 метрики, несжатые.

В шахматах 4х4 возможны 3,677,542,994,054,890 уникальных легальных позиций. Это точное число, а не оценка, как раньше. Теперь можно приступить к решению, чётко представляя себе сложность задачи.

Зашёл в Википедию посмотреть, как этот крокодил (10^15) называется.
Ясности никакой - то ли квадриллион, то ли биллиард. Зато встретил там такое замечательное слово, как дуцентдуомилианонгентновемдециллион (опять же, на выбор - 10^308760 или 10^617514).