Шахматы 4x4

В процессе решения шахматы на доске 4х4. Сейчас я тестирую первую более-менее рабочую версию решателя. В метрике DTM уже построил и проверил таблицы до 7-ми фигур, в DTC и DTZ - до 5-ти. Предлагаю обсудить, если здесь есть интересующиеся мини-шахматами.

Одно из направлений эксперимента - сравнение метрик и методов сжатия. Интересно посмотреть разницу между DTC и DTZ, попробовать другие альтернативные метрики и способы сжатия.

В том случае, если кто-то пробовал строить таблицы 4х4, можно сравнить статистику.

Также все желающие приглашаются попробовать угадать длину самого длинного выигрыша, и сопутствующие конфигурации фигур. (для 3-фигур, 4-х, 5-ти и т.д.)

Шахматы 3х3 были решены в 2004 году, шахматы 3х4 - в 2009. Экстраполируя, можно предположить 2014 год, как ориентир для 4х4, но уложимся или нет, сказать сложно.

Приблизительная оценка общего числа уникальных легальных позиций в шахматах 4х4: 3.46 квадриллиона.

Сравнение с 3х4:

Сравнение максимальных значений метрики в различных вариантах мини-шахмат:

Если б это было возможно, я бы давно решил шахматы 4х4 четверной рекомбинацией шахмат 2х2.

А шахматы 2х2 - четверной рекомбинацией шахмат 1х1 !

Игровую прогу - конечно проще. Но прога отвечает на другие вопросы, менее интересные.

Шутки шутками, но вот какой вопрос по этой теме меня занимает. Понятно, что самые миниатюрные из возможных шахматных вариантов - это 3x1 и 1x3 (из прямоугольных двумерных вариантов). Очевидно что ходов в них нет, и на доске либо мат, либо нет мата. То есть максимальная длина выигрыша - 0 ходов. Теперь обобщим и возьмём доски Nx1 и 1xN. К какой функции от N будет сходиться максимальная длина выигрыша, при увеличении N от 3-х в сторону бесконечности? Подозреваю, что к чему-то вроде N/2, нужно подумать, но должно быть элементарно. Теперь, собственно, вопрос: То же самое для досок Nx2 и 2xN - какой функцией от N выражается максимальная длина выигрыша? (под выигрышем подразумеваем последовательность оптимальных ходов каждой стороны, заканчивающуюся матом). (Правило 50 ходов можно для простоты проигнорировать )

И какова в них теория правды?

Да, наверное будет досчитывать. (Хотя я уже видел мат в 56 ходов, и DTZ в 46 ходов, не факт что игровой движок такие позиции просчитает приемлимо быстро). Но на доске 4x4 нет стандартной начальной позиции, поэтому непонятно что делать с игровым движком, даже если бы он был. Считать произвольные позиции, или все позиции подряд? (а вот это уже точно займёт вечность)

Для меня более интересны вопросы, в ответе на которые игровой движок помочь бессилен. Например: Какова максимально возможная длина выигрыша на доске 4x4? (И при каждом наборе фигур). Сколько позиций всего, и сколько из них выигранных, проигранных и ничейных? Сколько цуцвангов, в каком цуцванге самые длинные проигрывающие линии? Какие максимально возможные значения DTC и DTZ с каждым набором фигур (особенно в многофигурных позициях)? В конце концов, есть ли на доске 4x4 Бэбсон-таск?

Что тут решать, всё форсировано. 1.axb3+ Qxb3 2.cxb3+ Kb4 3.bxa4Q+ Kxa4 4.bxc3 Rc4 5.Qb3#. То есть мат в 5 ходов. В том и фишка - очень непросто найти сбалансированную нетривиальную позицию, которую можно было бы назвать стартовой.

А какую позицию вы считаете начальной? (Посчитаны все семи- и частично восьми-фигурные позиции.)

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

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

Есть обширное множество интересных вопросов (в этом контексте, шахматных вариантов). И менее обширное множество вопросов, на которые реально можно ответить (вариантов, которые реально посчитать). Там, где эти множества пересекаются, можно посчитать что-то интересное.

Если белые из начальной позиции побеждают (пусть даже в 150 ходов), то, рано или поздно, это будет найдено, и дальнейшая игра из этой позиции станет неинтересна. На такой маленькой доске любая фиксированная стартовая позиция будет быстро изучена вдоль и поперёк, и утратит интерес. По-моему, единственный способ сделать из этой головоломки осмысленную шахматную игру, не прибегая к экзотике, вроде поочерёдного выставления фигур, это сгенерировать набор стартовых позиций, по примеру шахмат Фишера. Каждая из стартовых позиций должна быть, желательно, ничейна, иметь длинные проигрыши и позволять нетривиальную игру. Я пробовал искать такие позиции на доске 3х4, но не нашёл ни одной достаточно интересной классически выглядящей позиции (пешки на второй и третрей горизонталях, одинаковые наборы фигур у белых и чёрных, и т.д.). Если же не требовать классической формы, то таких позиций множество, и возникает проблема выбора "нетривиальных".

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

Кто мог подумать до полного решения, что на доске 3х3 есть мат в 16 ходов? Допускаю что композитор, наверное, мог допетрить и составить ту позицию без компа, так как идея там довольно простая. Но мат в 43 хода на доске 3х4 - это за пределами возможностей любого супер-мозга.

Вот! Я ж и говорю, не всё так просто на этих мини-досках, как кажется на первый взгляд.

Да вот же они, по ссылке у Kirr-а в подписи:
http://kirr.homeunix.org/chess/3x3-chess/positions.shtml

Это я всегда рад, просто обычно не спамлю зря то что все и так знают. 3x3, мат в 16 ходов (один из многих):



Посмотреть во вьювере

EDIT: Thanks, Пух!

3x4, мат в 43 хода:



Вьювер