Шахматы 4x4

Тема в разделе "Машинное отделение", создана пользователем Kirr, 6 май 2011.

  1. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.248
    Симпатии:
    2.558
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    По-моему, погоня закончится тем, что от табуна отделятся один или два скакуна, и они будут прыгать за королём, не отдаляясь и не приближаясь. Остальные отстанут.
  2. Zayats Без определенного статуса

    • Ветеран
    • Старожил
    Рег.:
    08.01.2007
    Сообщения:
    2.181
    Симпатии:
    1.266
    Репутация:
    134
    Оффлайн
    На бесконечной доске с одним углом короля, бегущего по диагонали, будут преследовать полтора коня, что, конечно, мало. Даже невзирая на помощь дальнобойного слона. Однако, если на бесконечной доске разбросаны небольшие засады из двух-трех коней каждая, то результат уже не столь очевиден. Возможно, что существует алгоритм расстановки засад, такой что королю, стартующему с любой позиции не удается избежать мата и число_коней(n)/n**2 стремится к нулю при возрастающем n, где n - число вертикалей/горизонталей для оценки плотности распределения коней.
  3. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Король со слоном и конем легко загоняют короля в угол на любой доске. И там его фиксируют. Остается подогнать второго коня и поставить мат. Поэтому KBNN матуют голого короля на любой доске.
  4. Zayats Без определенного статуса

    • Ветеран
    • Старожил
    Рег.:
    08.01.2007
    Сообщения:
    2.181
    Симпатии:
    1.266
    Репутация:
    134
    Оффлайн
    Не на любой, конечно. Только на конечной, односвязной, с углами. Скажем, на сферической доске нет матовых позиций (только патовые), а на бесконечной король удирает. С многосвязными досками надо разбираться отдельно, в некоторых частных случаях мат возможен.

    Единственное, что смущает - от заявленной темы мы несколько отвлеклись. То ли вынести рассуждения о досках 12х12 и пр. в отдельную тему, то ли эту переименовать в "Матование голого короля" или еще как-то.
  5. Edwards Ветеран

    • Ветеран
    Рег.:
    10.02.2006
    Сообщения:
    6.325
    Симпатии:
    311
    Репутация:
    20
    Адрес:
    CПб
    Оффлайн
    На бесконечной доске король и от ферзя с королём сможет вечно удирать.
    Вряд ли есть смысл рассматривать случай бесконечной доски.
  6. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.248
    Симпатии:
    2.558
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    По доске Клейна
    далеко ли ты скачешь,
    сферический конь?
  7. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Хотя наверно в угол оттеснить конем и слоном проблематично. Но на край доски должно получиться.
  8. dan77790 Учаcтник

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    16
    Репутация:
    0
    Оффлайн
    Сферический конь в вакууме набигает
  9. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Я думаю так: со слоном и двумя конями можно заматовать короля на любой доске конечных размеров, даже
    1000 х 1000. Два коня может и не угонятся за королем, но один конь, король, и слон - угоняются. И могут оттеснить если и не в угол, то на край доски. Затем король фиксируется на краю доски, подгоняется другой конь, и ПО КРАЮ доски, король перегоняется в нужный угол. Т.е. не выпускается на свободу, и с помощью трех легких фигур, пошагово оттесняется в нужную сторону.

    PS Тремя конями возможно, мат действительно не ставится на достаточно больших досках. И то - не факт. Если удастся оттеснить короля на край доски с помощью короля и двух коней, и потом его там зафиксировать, пока не подтянем третьего коня - то мат возможен и тремя конями.
  10. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Утихли споры о сферических конях и бесконечных досках, значит можно вернуться к изначальной теме. :)

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

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

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    Kirr вот завместо фигнёй страдать сделай лучше мне генератор ходов для русских шашек на PHP и JavaScript. Мне это нужно для моего сайта, а у меня рук на всё не хватает. Тебе за это будет респект и уважуха в ЗАЛЕ СЛАВЫ. :)
  12. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Да, действительно странно... А какой на доске 4х4 самый длинный путь к мату? Может, каких нибудь 200 ходов?
  13. miptus Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    1.159
    Симпатии:
    78
    Репутация:
    5
    Оффлайн
    Теперь наверное можно уточнить аппроксимирующий многочлен и получить еще более точную оценку?
  14. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    А огород вам заодно не вскопать? Знали б вы на сколько интересных проектов у меня не хватает рук и ног. :)

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

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

    • Участник
    • Старожил
    Рег.:
    29.04.2010
    Сообщения:
    987
    Симпатии:
    391
    Репутация:
    12
    Оффлайн
    А вы могли бы эту позицию показать?
    Очень интересно.
  16. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Покажу, конечно! И эту и другие интересные позиции. Но для полного счастья нужен ещё веб-интерфейс к базе, чтобы можно было побродить по вариантам, посмотреть решение и боковые ветки. Надеюсь за эти выходные доработать и дотестировать интерфейс, и тогда смогу полноценно показывать позиции.
  17. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Прошу тестировать веб-интерфейс. Первая сырая версия, недостающие фичи будут добавляться, баги - исправляться. Если сервер недоступен, значит всё уже упало. :) Удивляться этому не нужно.

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

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

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

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

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

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    А в шахматах 4х4 пешки значит, могут стоять на последней горизонтали?
    И какие 52 хода будут при лучшей игре обоих сторон?
  19. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    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#

    У вас не получилось посмотреть линию в веб-интерфейсе?
  20. Котэ Восьмикратный чемпион подъезда

    • Участник
    • Старожил
    Рег.:
    29.04.2010
    Сообщения:
    987
    Симпатии:
    391
    Репутация:
    12
    Оффлайн
    Просмотрел линии от начала до конца. Все работает отлично.
  21. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Починил несколько багов, в том числе от балды расставляемые значки цуцвангов и выпадения в позициях с голыми королями. :)

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

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

    8 фигур, 56 ходов
  22. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Посчитал 8-фигурку во всех четырёх метриках (DTM, DTC, DTZ, WDL). На этом временно приостанавливаю генерацию таблиц, чтобы продолжить разработку суперкомпрессии.

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

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    1.159
    Симпатии:
    78
    Репутация:
    5
    Оффлайн
    Еще бы легенду для значков сделать.
    Для DTC метрики интерфейс почему-то показывает бесконечность для всех ходов, это что значит?
  24. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Сделаю легенду. Может быть, даже завтра. :) Пока что можно смотреть легенду здесь.

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

    • Участник
    • Старожил
    Рег.:
    29.04.2010
    Сообщения:
    987
    Симпатии:
    391
    Репутация:
    12
    Оффлайн
    Как то медленно по сравнению с доской 8Х8 идет прирост необходимых для мата ходов в рекордных позициях. Может так получится что при дальнейшем увеличением количества фигур количество ходов необходимых для постановки мата в рекордных позициях начнет уменьшаться?
  26. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    До 32-х фигур, на доске 8х8 будет только увеличиваться.
  27. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Kirr.

    Если вы считаете 125,170,155,996,618 позиций, то у вас, наверное, есть хорошие компьютерные мощности. Лучше бы посчитали на моем генераторе какие-нибудь интересные 7-фигурные базы.
    Меня вот интересует 7_KBBP-KRP. Два слона с пешкой против ладьи с пешкой, очевидно выиграют, но возможно, найдутся позиции, которые будут выигрываться за 500 ходов. Правда, придется для этого еще - много младших беспешечных посчитать.
  28. TopicStarter Overlay

    Kirr Администратор

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

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

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

    [​IMG]
  29. TopicStarter Overlay

    Kirr Администратор

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

  30. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Удалось улучшить сжатие таблиц примерно в 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-а, или к любым другим, а является кульминацией долгих экспериментов с суперкомпрессией).

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

    • Участник
    Рег.:
    14.09.2007
    Сообщения:
    524
    Симпатии:
    7
    Репутация:
    0
    Адрес:
    Пересвет, Россия
    Оффлайн
    Сначала не мог понять, почему такое малое количество позиций с фигурами против множества позиций с пешками. Потом всё же догадался, что автор считает позиции типа и одинаковыми. А с пешками это иногда не прокатывает из-за их "однонаправленности". Но мне всё же не понятно, почему не рассматриваются позиции с шахом? Их довольно много. И они, смею Вас заверить, легальны:)
    Кстати, необходимо сформулировать критерии легальности позиции. По определению, легальной считается позиция,которая теоретически может случится в партии со всеми легальными ходами. Раз так, то критерии нелегальности могу назвать следующие:
    1. Король под боем любой вражеской фигуры (включая вражеского короля) и ход противника.
    2. Пешки на крайних горизонталях.
    3. Сдвоенные пешки при наличии пешек на соседних вертикалях или отсутствии вертикали. Критерий не точен, но подразумевается что-то типа такого:

    4. Позиция, в которой нельзя определить последний ход стороны, не обладающей правом хода. По сути, это позиции пункта 1, но прошедшие не через шах, а через пат:
    Ход белых.
    Все эти позиции не должны учитываться, очевидно. Все остальные позиции считаются легальными.
  32. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Рассматриваются. Нортон просто не сумел сформулировать мысль.

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

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

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

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


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

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

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
  34. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    В шахматах 4х4 возможны 3,677,542,994,054,890 уникальных легальных позиций. Это точное число, а не оценка, как раньше. Теперь можно приступить к решению, чётко представляя себе сложность задачи. :)
  35. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.248
    Симпатии:
    2.558
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Зашёл в Википедию посмотреть, как этот крокодил (10^15) называется.
    Ясности никакой - то ли квадриллион, то ли биллиард. Зато встретил там такое замечательное слово, как дуцентдуомилианонгентновемдециллион (опять же, на выбор - 10^308760 или 10^617514).

Поделиться этой страницей