Шахматы 4x4

Ничего особенно феноменального, если не считать мата в 56 ходов. (В 9-фигурке генератор сообщал о мате в 59 ходов, но позицию я ещё не видел).

Для меня в шахматах 4х4 пока что интереснее техническая сторона, чем шахматная. Индексирование, расход памяти, плотность сжатия таблиц.

В плане открытий более перспективен этап раскопок, который последует за генерацией таблиц (в моём подходе). До сих пор раскопками в 4х4 я почти не занимался.

Прекрасно, что эта тема вдохновляет всё новых участников на эксперименты!

kbnk на доске 17х17 помещается в (17*17)^4 = 6,975,757,441 байт - меньше 7 гигабайт, с наивным индексом (если нам хватает 1 байта, а его должно хватать). На машине с 8 ГБ должно быть несложно посчитать. Если индекс не совсем наивный, то можно ещё немного увеличить доску, например, догнать до 20х20.

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

Обыкновенно, malloc()/free(). Конечно, нужна 64-битная ОС и 64-битный компилятор. Под виндой я использую SDK, в его состав входит 64-битный компилятор, в отличие от бесплатной версии Visual C++.

Наборы из двух модулей по 4 ГБ в наших краях продают за порядка $50 - достаточно дёшево, чтобы не считать это роскошью.

Неплохо было бы составить страничку ссылок на старые обсуждения по теме. А вообще, в этом году как раз наблюдается некоторое оживление.

В минишахматах я использую следующие критерии нелегальности:

1. Король под боем стороны, чей ход.
2. Пешка на горизонтали превращения.
(3. Число белых или чёрных королей отлично от 1.)

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

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

Например, следующая диаграмма, при ходе чёрных, соответствует восьми позициям (у каждой из которых есть ещё симметричные варианты):


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

Как ни парадоксально, мы до сих пор не знаем числа уникальных легальных позиций даже в 3-фигурке на доске 8х8. Поэтому результаты независимых исследований невозможно сравнивать. Для сравнения и проверки результатов друг друга нужно придти к какому-то общему стандарту подсчёта позиций.

Мне вдруг стало интересно, почему никто не использует метрику "Расстояние до взятия"? Во всяком случае, я не встречал даже упоминания о такой метрике, так что решил поизучать её на маленькой доске. Сокращение для этой метрики будет "DTX".

Пока что я посчитал в DTX только шестифигурку на доске 4х4. По компактности DTX находится между DTM и DTC, и ближе к DTC (как и ожидалось). В будущем скорее всего также посчитаю 7-8 фигурку DTX и добавлю в веб-интерфейс.

Трудно понять, чем эта метрика привлекательна. Грубо говоря, метрики всего две: абсолютная (DTM) и "относительная", показывающая прогресс в каком-то смысле.
Во втором классе есть естественная DTZ, фиксирующая все необратимые изменения.
Сужение DTZ имеет смысл, если это послужит большей эффективности.
Например, "расстояние до мата, превращения или побития сильнейшей стороной", то есть с заточкой на прогресс сильнейшей стороны.

Очень просто - целью является мат либо взятие, сохраняющее выигрыш. Эта метрика похожа на DTC, с единственным различием: Превращение пешки больше не считается целью.

А я не утверждаю, что DTX чем-то особенно привлекательна, или что она лучше DTZ. Мне эта метрика нужна просто для полноты картины, как и DTC. В частности, интересно проверить её компактность, и спектр значений. Также интересно посмотреть максимально длинную линию DTX. Также, есть несколько идей о статистике на основе нескольких метрик.

DTZ остаётся моим предпочтением для практических целей (усиления игры), причём на доске 8х8 это будет DTZ50.

Жадный вариант DTZ, DTC, DTX - забавная мысль. Можно попробовать посчитать. Нужно только придумать как их обозначать. DTZG? (DTCG, DTXG)

Спектр значений DTM в шахматах 4x4. На горизонтальной оси - значения метрики, в порядке: ничья, мат, выигрыш в 1 ход, проигрыш в 1 ход, выигрыш в 2 хода, проигрыш в 2 хода, и т.д. На вертикальной оси - процент позиций с данной метрикой среди всех позиций с таким же числом фигур.

То же самое для метрики DTZ:

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

Спектры DTC и DTX похожи на DTZ, и чуть более пологие.

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

Мат в 59 ходов:


(ход белых)

N1p1/1k1p/1B1B/BK1b w - - 0 1
1.Nc3!! Bc2+ 2.Kc1☉□ Kb4 3.Na2+!! Ka4 4.Nb4♢ Kb3 5.Bd4♢ Ka3 6.Bac3! Kb3 7.Bb2! Ka4 8.Na2! Kb3 9.Nc3☉! Kb4 10.Nb1+! Ka4 11.Na3!! Kb3 12.B4c3!! Ka2 13.Nxc4♢ Ba4 14.Na3♢ Bb3 15.Bb4♢ Bc2 16.Bd4! Kb3 17.B2c3! Ka2 18.Nc4! Ba4 19.Ba3♢ Bb3 20.Nd2! Ba4 21.Bcb2! Bb3 22.Nb1! Bc2 23.Nc3+! Kb3□ 24.Kd2!! Kc4 25.Na2! Kb3 26.Nb4! Kc4 27.Bbc3! Kb3 28.Ba1! Kc4 29.Bdc3♢ Kb3 30.B1b2! Ka4 31.Kc1! Kb3 32.Bd2! Ka4 33.Na2! Kb3 34.Nc3☉! Kc4 35.Ba1! Kb3 36.Bb4☉! Kc4 37.Kb2! Kxb4 38.Nb1+♢ Ka4 39.Na3! Bb3 40.Bc3! d2 41.Bxd2!! Bc4 42.Nc2♢ Bb3 43.Nb4! Bc4 44.Bc3! Bb3 45.Nd3! Ba2 46.Nc1! Bc4 47.Bd2! Bb3 48.Bb4! Kxb4 49.Nxb3!! Ka4 50.Nd2♢ Kb4□ 51.Kc2♢ Ka4 52.Nb1♢ Kb4□ 53.Bd4♢ Ka4 54.Bb2! Kb4□ 55.Nc3! Kc4□ 56.Ba3! Kd4□ 57.Nb1! Kc4□ 58.Nd2+! Kd4□ 59.Bb2#

Посмотреть в интерфейсе

Конечно, 3 слона одного цвета - довольно странный материал, вряд ли встречавшийся хоть раз в реальной партии. На доске 4х4 в конфигурацях "слоны одного цвета против слонов другого цвета" часто получаются рекордные линии, особенно DTZ и DTC.

Вот ещё один мат в 59 ходов, с более нормальным материалом:


(ход белых)

2NR/1Pp1/K2P/1qkN w - - 0 1
1.Ka3□ c2 2.Ndb2!! Qa1+ 3.Kb4□ Kb1 4.Rd3!! c1N 5.Kc3!! Na2+ 6.Kd4□ Kc2 7.b4Q♢ Nxb4 8.Rc3+!! Kb1□ 9.Rb3!! Na2 10.Na3+!! Kc1□ 11.d3!! Nb4 12.Kc4! Nxd3 13.Nxd3+!! Kd1 14.Nb4! Kc1 15.Rd3! Kb2 16.Nbc2! Qa2+ 17.Kb4!! Kc1 18.Ka4!! Kb2 19.Nb4! Qa1 20.Rb3+! Kc1□ 21.Nd3+! Kd2 22.Kb4! Qd4+ 23.Nc4+□ Kc2 24.Ndb2!! Kc1 25.Ra3♢ Kc2 26.Na4! Qd3 27.Nc3!! Kc1 28.Ra4♢ Kc2 29.Ra2+! Kc1□ 30.Ra3! Kc2 31.Rb3! Kc1 32.Na2+! Kc2 33.Na3+! Kd2 34.Nb1+! Kc2 35.Nac3! Kc1 36.Ka3! Qc2 37.Na2+!! Kd1 38.Nbc3+! Kd2 39.Rb4! Kd3 40.Nb1!! Qd1 41.Kb2! Qc2+ 42.Ka1! Qc4 43.Rb2!! Qd4 44.Nb4+♢ Kc4 45.Na3+! Kc3□ 46.Nac2! Qd1+ 47.Ka2!! Kc4 48.Na3+!! Kc3 49.Nb1+! Kc4 50.Nc2! Qc1 51.Nba3+! Kc3 52.Rb3+! Kd2□ 53.Nb4! Kd1 54.Nd3! Qc2+ 55.Nxc2♢ Kxc2 56.Ra3♢ Kd2 57.Kb2♢ Kd1□ 58.Nb4♢ Kd2□ 59.Rd3#

(Посмотреть в интерфейсе)

Здесь нет цуцвангов, зато есть превращение в коня и 17 ходов с двумя восклицательными знаками (единственный выигрывающий ход из нескольких возможных). За 13 ходов позиция сводится к 6-фигурной KRNNKQ, где внешне бессмысленное двигание фигурами продолжается больше 40 ходов. К сожалению, первый ход - форсирован.

Zayats, спасибо за анализ и комментарии!

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

Очень интересно, мне совсем не очевидны стадии и ключевые позиции.

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

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

Решил 9-фигурку в DTM.

Самый длинный мат: 59 ходов, таких позиций 5 штук, выше приведены две. Самая длинная линия - проигрыш в 59 ходов, их тоже 5, но позиций я пока не видел.

9-фигурка DTM занимает 63.2 ГБ, на текущем этапе экспериментов с компрессией.

Очень интересно!! Вечером подвигаю эндшпиль на доске и попробую подумать.

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