Шахматы 4x4

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

  1. TopicStarter Overlay

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

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

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

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

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

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

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

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

    Сравнение с 3х4:
    [​IMG]
  3. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Сравнение максимальных значений метрики в различных вариантах мини-шахмат:
    [​IMG]
  4. dan77790 Учаcтник

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    16
    Репутация:
    0
    Оффлайн
    А нельзя все шахматы решить четверной рекомбинацией шахмат 4 на 4?)
    Ведь доска состоит из 4 кусков 4 на 4...
  5. TopicStarter Overlay

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

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

    • Участник
    Рег.:
    31.03.2006
    Сообщения:
    1.193
    Симпатии:
    60
    Репутация:
    11
    Оффлайн
    Не проще ли создать игровую прогу, где она уже на 80 полуходов будет в среднем расчитывать? По крайней мере шахматы 6 на 6 более реальны. На заре программирования их использовали. Возможно можно просто переделать немного Ипполит какой нибудь и доску до 6 уменьшить. Правда с оценкой позиционной траблы будут. Все равно забавная вещь.
  7. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.222
    Симпатии:
    2.526
    Репутация:
    90
    Адрес:
    Москва
    Онлайн
    А шахматы 2х2 - четверной рекомбинацией шахмат 1х1 ! :D
  8. Котэ Восьмикратный чемпион подъезда

    • Участник
    • Старожил
    Рег.:
    29.04.2010
    Сообщения:
    987
    Симпатии:
    391
    Репутация:
    12
    Оффлайн
    Шахматы 1x1 любой кот в уме решит :)
  9. dan77790 Учаcтник

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    16
    Репутация:
    0
    Оффлайн
    Есть ли стратегия и тактика в шахматах 1x1?
  10. TopicStarter Overlay

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

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

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

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    33.190
    Симпатии:
    14.449
    Репутация:
    528
    Адрес:
    Ростов-на-Дону
    Оффлайн
    И какова в них теория правды? :)
  12. miptus Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    1.159
    Симпатии:
    78
    Репутация:
    5
    Оффлайн
    Ну может в 4х4 прога будет досчитывать до мата из начальной позиции, тогда получится таблица WDL без генерации.
  13. ber-viking Учаcтник

    • Участник
    Рег.:
    10.05.2006
    Сообщения:
    1.881
    Симпатии:
    93
    Репутация:
    12
    Адрес:
    Россия, Казань
    Оффлайн
    Я правильно понял, что 4х4 просчитана? Какой результат игры?
  14. miptus Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    1.159
    Симпатии:
    78
    Репутация:
    5
    Оффлайн
    Для 7 фигур только, а надо 16.
  15. TopicStarter Overlay

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

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

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

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    123
    Репутация:
    1
    Оффлайн


    Вот рекомендую решить конкретную позицию 4х4 (естественно что доску обрезаем до 4х4). Ход белых, естественно.
  17. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Что тут решать, всё форсировано. 1.axb3+ Qxb3 2.cxb3+ Kb4 3.bxa4Q+ Kxa4 4.bxc3 Rc4 5.Qb3#. То есть мат в 5 ходов. В том и фишка - очень непросто найти сбалансированную нетривиальную позицию, которую можно было бы назвать стартовой.
  18. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    388
    Симпатии:
    390
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    Тогда непонятно, как решать шахматы 4х4, если нет стартовой позиции?
  19. miptus Заслуженный

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

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

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

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

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

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

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    Ну так поищите, например Монтекарлом можно сгенерить пару тысяч позиций и выбрать самую "огнеупорную" :)
  22. Killster Учаcтник

    • Участник
    Рег.:
    12.05.2011
    Сообщения:
    75
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Так какая разница: тут либо ничья, либо победа какой-либо стороны. Про какую огнеупорность вы говорите? :/
  23. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    А о такой, что, например белые побеждают но в 150 ходов, а не в 5 как в предыдущей позиции.
  24. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Если белые из начальной позиции побеждают (пусть даже в 150 ходов), то, рано или поздно, это будет найдено, и дальнейшая игра из этой позиции станет неинтересна. На такой маленькой доске любая фиксированная стартовая позиция будет быстро изучена вдоль и поперёк, и утратит интерес. По-моему, единственный способ сделать из этой головоломки осмысленную шахматную игру, не прибегая к экзотике, вроде поочерёдного выставления фигур, это сгенерировать набор стартовых позиций, по примеру шахмат Фишера. Каждая из стартовых позиций должна быть, желательно, ничейна, иметь длинные проигрыши и позволять нетривиальную игру. Я пробовал искать такие позиции на доске 3х4, но не нашёл ни одной достаточно интересной классически выглядящей позиции (пешки на второй и третрей горизонталях, одинаковые наборы фигур у белых и чёрных, и т.д.). Если же не требовать классической формы, то таких позиций множество, и возникает проблема выбора "нетривиальных".
  25. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    Если нужна игровая стартовая позиция то тогда надо начинать с доски 4х5 типа вот такой,

    и не тратить время на всякую ерунду типа 3х3 или 4х4
  26. Мобуту спаситель нации

    • Заслуженный
    • Ветеран
    Рег.:
    15.02.2006
    Сообщения:
    6.445
    Симпатии:
    2.036
    Репутация:
    103
    Адрес:
    Заир
    Оффлайн
    ИМХО программу, которая бы разыгрывала такие позиции, надо создавать не на основе перебора всех позиций, а по образу и подобию Великой Проги, т.е. перебор наиболее осмысленных вариантов и минимакс. Позиции тут острые, варианты не слишком длинные, тягучей стратегии нет. Скорее всего, любая позиция просчитается если не до мата, то до решающего перевеса.


    Мат быстрее ставится. 1. cxd3+ Rxd3 2. Qxd3+ Kxd3 3. dxc3+ и мат на d4 тремя способами.
  27. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    388
    Симпатии:
    390
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    Довольно странные представления о Фритце. Причем, как я понимаю, речь идет о 10-й версии.
    Я изучал алгоритм этой проги. Более тупого перебора ВСЕХ вариантов я не видел больше ни у кого. Именно за счет этого тупого счета Фритц часто находит решения в сложных позициях. Простая оценка, быстрый перебор, и минимум отсечений/сокращений - вот и всё.
    Современные проги, в отличие от Фритца, отличаются как раз тем, что стараются сократить перебор за счет отсечения или сокращения менее перспективных вариантов. Из-за этого у них бывают проколы, но в целом игра становится сильнее. Кстати, следующие (после 10-й) версии Фритца пошли по этому же пути и заметно прибавили.
  28. TopicStarter Overlay

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

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

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

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

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    Ну так позиции в студию!
  30. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.222
    Симпатии:
    2.526
    Репутация:
    90
    Адрес:
    Москва
    Онлайн
  31. TopicStarter Overlay

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

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

    [​IMG]

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

    EDIT: Thanks, Пух!
  32. TopicStarter Overlay

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

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

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    Пух, можешь не верить но я показ подписей в форуме отключил :)
  34. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Шахматы на доске 4*4 неинтересны. Я думаю, более интересно было бы поиграть на больших досках, 9*9, или даже 10*10, с двумя стартовыми ферзями у каждой из сторон и т.д. Больше жизненного пространства - как то лучше воспринимается. Будут более красивые атаки, меньше процент ничьих и т.д. Может, существуют компьютерные программы для шахмат на больших досках?

    В будущем, планирую написать эндшпильный генератор для шахмат на больших досках.. Кто-то утверждал, что на доске 10*10 нельзя поставить мат слоном и конем - одинокому королю. Интересно будет все это проверить :)

    На доске 8*8 с 32 фигурами она будет ОЧЕНЬ большой.
    Максимальная длина выигрыша с 4-мя фигурами - 43 хода, с 5 фигурами - 128 ходов (стало больше в 3 раза), с 6 фигурами - 262 хода (стало больше в 2 раза), с 7 фигурами - пока никто не знает, но известны позиции с матом примерно 545 ходов. Еще в 2 раза больше.

    Т.е. примерно такая ситуация: +1 фигура - это увеличение максимальной длины выигрыша в 2 раза. Поэтому можно примерно предсказать, что максимальная длина выигрыша для 8-фигурных - будет - 1000 ходов, для 9-фигурных - 2000 ходов, и т.д. для 32-фигурных -
    примерно 16 000 000 000 ходов.

    Но найти такую позицию практически невозможно - т.к. таких позиций будет очень мало. Думаю, из стартовой позиции шахмат, белые выигрывают за какие-нибудь 2000 ходов, хотя возможны позиции с 32 фигурами, где до выигрыша требуется сделать 16 миллиардов ходов.
  35. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    388
    Симпатии:
    390
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    В приведенной позиции 3х3 решение тривиально. Вариант практически один, разветвления быстро приводят к пату или повтору ходов. Если написать игровой движок, то он найдет решение почти мгновенно. Да и для человека понадобится несколько минут, не больше.
    Позицию 4х3 не смотрел, но думаю, что для игрового движка она будет не намного сложнее.

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