Шахматы 4x4

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

Страница 2 из 6

  1. Мобуту спаситель нации

    • Заслуженный
    • Ветеран
    Рег.:
    15.02.2006
    Сообщения:
    6.866
    Симпатии:
    3.772
    Репутация:
    133
    Адрес:
    Заир
    Оффлайн
    У Великой Проги может быть только великий алгоритм. Ещё свежо воспоминание, как она крошила всех, не больно разбирая - белковый там, силиконовый, чайник или чемпион мира. От всех оставалась лужица крови.
    Мобуту, 17 май 2011
    #36
  2. TopicStarter Overlay

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

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

    Интересно будте увидеть! Мат слоном и конём на доске 10х10, конечно, ставится, но на доске 9х9 (а также 11х11 и любого другого нечётного размера) - только с правильным слоном. :)

    Раз уж вы заинтересовались этой темой (как минимум настолько, чтобы зайти и написать, что она вам неинтересна), воспользуюсь возможностью спросить: Известно ли вам число уникальных легальных позиций в шахматах с 3-мя фигурами, с 4-мя и т.д. и в каждом из решённых вами окончаний? Интересно было бы сравнить это число с мини-шахматными аналогами.
    Kirr, 17 май 2011
    #37
  3. TopicStarter Overlay

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

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

    Если вы думаете, что все позиции на доске 3х3 настолько же просты, попробуйте порешать задачи на страничке варианта (Под заголовком "Problems"). Например, маты в 10 и более ходов (без движка). Какие-то удастся решить, какие-то нет, но главное в том, что многие задачи заставят задуматься, и это - самое ценное, то, чего мы интуитивно не ожидаем от такой маленькой доски. :)

    Согласен. Но, в отличие от позиций 3x3, эту позицию человеку будет решить уже непросто. (А главный вызов, как я уже упомянул - прежде всего найти эту позицию).
    Kirr, 17 май 2011
    #38
  4. TopicStarter Overlay

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

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

    [​IMG]

    Горизонтальная ось - заполненность доски фигурами. "raw" - несжатые таблицы, остальные сжаты.

    На доске 3х4 - несжатые таблицы до 8 фигур, сжатые DTM и DTC - до 12 (100% заполненность). На доске 4х4 - несжатые DTM и сжатые в четырёх метриках (DTM, DTC, DTZ, WDL) - до 7 фигур.
    Kirr, 17 май 2011
    #39
  5. TopicStarter Overlay

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

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

    [​IMG]

    На этом графике - только сжатые таблицы.

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

    Из неожиданного. Я ожидал большего преимущества DTZ над DTC, и большего преимущества WDL над остальными метриками.

    Видно, что 4x4 DTC - компактнее, чем 3x4 DTC. Из чего следует, что компактность метрик DTC, DTZ и WDL - растёт с увеличением доски. (Что вобщем-то было и так очевидно).

    Заметим, что графики DTC, DTZ и WDL обязаны встретиться в точке 100% заполненности доски. :)
    Kirr, 17 май 2011
    #40

  6. Skipper_NORTON Старожил

    • Участник
    • Старожил
    Рег.:
    14.12.2007
    Сообщения:
    515
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Конечно известно. Там же после построения каждой базы, выводится файл статистики (.txt), в нем - все количества позиций по каждому множеству. С ходами белых+черных получается -

    3_KN-K - 54 926
    3_KB-K - 53 380
    3_KR-K - 51 044
    3_KQ-K - 47 136
    3_KP-K - 165 676

    Все 3-фигурные - 372 162 уникальные позиции. Аналогично можно посчитать для 4-фигурных, 5-фигурных и т.д.
    Skipper_NORTON, 17 май 2011
    #41
  7. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Отлично! Можете посчитать для 4, 5 и 6 фигур?

    Я правильно понимаю, что в этом числе учтены только легальные позиции, и только уникальные (все возможные симметричные и повёрнутые варианты позиции считаются вместе как одна позиция)?

    И, для ясности, правильно ли я понимаю, что позиции с правом взятия на проходе и без него вы считаете как отдельные позиции, и что позиции с правом рокировки не учтены?
    Kirr, 18 май 2011
    #42

  8. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    399
    Симпатии:
    475
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    А как можно вообще оценить число возможных позиций на доске NxN при наличии на ней не более M фигур?
    Существует давно известный метод - представить позицию строкой бит, тогда число возможных позиций будет равно 2^B, где B - длина битовой строки.
    Будем строить нашу битовую строку следующим образом:
    1. Определяем битбоард длиной NxN, в котором 0 - пустое поле, 1 - на поле что-то есть.
    2. Рядом с этоим битбоардом располагаем список фигур.
    Всего возможных типов фигур равно 12, поэтому для каждой фигуры в списке хватит 4 бит.
    Итого имеем битовую строку длиной NxN+Mx4.
    Для доски 4х4 имеем:
    4 фигуры: 4x4+4x4=32бита, т.е. всего возможных позиций примерно 4 миллиарда.
    Добавление каждой фигуры увеличивает длину битовой строки на 4 бита, а число возможных позиций в 16 раз.
    Придется добавить еще один бит за право хода и еще несколько бит на рокировки и взятия на проходе.

    Конечно, это все оценка сверху. По этому методу получается, что для нормальных шахмат 8x8 с 32 фигурами нужно 192 бита, а число возможных позиций порядка 10^57.
    Но я где-то читал, что кто-то сумел посчитать число позиций, и получилось, что их 10^43.
    Т.е. удалось уместить представление произвольной позиции в 128 или 129 бит.
    Интересно, как это было сделано?
    Осипов Юрий, 18 май 2011
    #43

  9. NS_Serg Зарегистрирован

    Рег.:
    18.05.2011
    Сообщения:
    15
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Интересно, как? Чтоб поставить мат нужно перегнать короля из неправильного угла.
    Но для этого нужно выпустить короля с края доски. На доске 8x8 он далеко при этом не уйдет, но на доске 10х10 должны возникнуть проблемы.
    NS_Serg, 18 май 2011
    #44

  10. Crest Админ, МГ

    • Команда форума
    Рег.:
    05.02.2006
    Сообщения:
    57.091
    Симпатии:
    20.860
    Репутация:
    607
    Адрес:
    Москва, Россия
    Оффлайн
    Думаю, и на 10х10 короля удастся перегнать в нужный угол. Конечно, труднее, чем на 8х8, но все-таки, по ощущениям, должен найтись способ.
    Crest, 18 май 2011
    #45

  11. Skipper_NORTON Старожил

    • Участник
    • Старожил
    Рег.:
    14.12.2007
    Сообщения:
    515
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Для 6 фигур - пока не могу, т.к. я их все еще не построил. Для 4,5 - могу. Если не забуду, то дома посчитаю. Сейчас я не дома. Да и вы сами можете это посчитать, посмотрев файлы статистики у Налимова. Т.е. нужно просуммировать все количества в файлах. Во всех типах эндшпильных баз, все количества позиций (по всем множествам) в моих базах и в базах Налимова - полностью совпадают.

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

    Насчет симметричных. Если уж вдаваться в подробности...
    Для позиций с пешками - абсолютно верно, как вы написали. А для позиций без пешек, тоже учитываются повороты, и зеркальные отражения доски, т.е. позиции уникальные. Но есть все таки исключения - примерно 1% позиций, которые логически - уникальны, но в базе на них заводится два идентификатора, т.е. они рассматриваются как две разные позиции. Но таких очень немного, повторяю, примерно 1%, и к тому же - только в беспешечных типах эндшпилей, и с двумя королями на одной главной диагонали. Почему так нужно было делать при написании генератора - долго объяснять, нужно глубоко разбираться в данной области.

    Видимо, Налимов поймет, почему так сделано... :) Потому что у Налимова абсолютно то же самое в базах.

    Также, позиции с правом взятия на проходе и без него - конечно же, я считаю, как отдельные позиции. Позиции с правом рокировки не учтены. Какая может быть рокировка, когда на доске 6-7 фигур? У меня все, как у Налимова.
    Метрика - DTM. Только формат отличается. И архиватор на 20% хуже. Зато у меня наиболее оптимизированный генератор. Это самое главное сейчас. Построить сами базы, и чтобы было наиболее дешево. А потом можно их переконвертировать в любой формат, хоть даже в истинный формат Налимова. Или в WDL.
    Переконвертация - на пару порядков менее трудоемкая задача, чем построение.
    Skipper_NORTON, 18 май 2011
    #46

  12. Skipper_NORTON Старожил

    • Участник
    • Старожил
    Рег.:
    14.12.2007
    Сообщения:
    515
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Я тоже так думаю, что должен найтись способ. Неужели уже конь со слоном (и с королем) не могут справится с задачей - оттеснить одинокого короля с любой угол? А в позициях "два коня против пешки", это делают даже король с одним конем (!!!), при пассивной слабой поддержке другого коня, который должен блокировать пешку (пока король не будет загнан в угол) А уж со свободными слоном и конем эта задача думаю, будет на порядок проще. Впрочем, напишу генератор баз на досках 10*10 - проверим.
    Skipper_NORTON, 18 май 2011
    #47

  13. NS_Serg Зарегистрирован

    Рег.:
    18.05.2011
    Сообщения:
    15
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    С такой задачей - даже на доске 8х8 не справятся.
    NS_Serg, 19 май 2011
    #48

  14. NS_Serg Зарегистрирован

    Рег.:
    18.05.2011
    Сообщения:
    15
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    На доске любого размера конь с слоном и королем оттесняют голого короля соперника в угол, а вот в угол какого цвета - зависит от желания слабейшей строны. Но на доске 8х8 есть способ по краю перегнать короля из неправильного угла в правильный, но конкретно этот способ на доске 10х10 работать не будет.
    NS_Serg, 19 май 2011
    #49

  15. Crest Админ, МГ

    • Команда форума
    Рег.:
    05.02.2006
    Сообщения:
    57.091
    Симпатии:
    20.860
    Репутация:
    607
    Адрес:
    Москва, Россия
    Оффлайн
    А зачем нужен конкретно этот же способ?
    Почему бы не найтись еще десятку других?
    Речь не о полном сходстве, которое не имеет смысла. А об оценке позиции.

    И аналогия от Skipper_NORTON про короля с конем, оттесняющим короля, как раз весьма красноречива. Судя по всему, у сильнейшей стороны есть немалый запас надежности, которого хватит при некотором расширении доски.
    Кстати, было бы интересно вычислить точные размеры... Впрочем, и тут ответ напрашивается. Скорее всего, на 12х12 уже не удастся загнать.
    Но всё это лишь интуитивные ощущения.

    Ждем вердикта компов! :)
    Crest, 19 май 2011
    #50

  16. Skipper_NORTON Старожил

    • Участник
    • Старожил
    Рег.:
    14.12.2007
    Сообщения:
    515
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Ну что ж... Осталось написать генератор для доски 10*10, да проверить все это. Может даже побольше - сразу 12*12, чтобы убедить всех, что слон и конь выиграют на любой доске? Что могут перегнать короля из одного угла в другой угол?
    Skipper_NORTON, 19 май 2011
    #51

  17. NS_Serg Зарегистрирован

    Рег.:
    18.05.2011
    Сообщения:
    15
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Если на доске 10х10 есть еще сомнения по поводу невозможности перегона короля из угла в угол, то на доске 12х12 у меня сомнений пока нет.
    P.S. А можно мне восстановить старый ник? А то система восстановления пароля на форуме не работает.
    NS_Serg, 19 май 2011
    #52

  18. Мобуту спаситель нации

    • Заслуженный
    • Ветеран
    Рег.:
    15.02.2006
    Сообщения:
    6.866
    Симпатии:
    3.772
    Репутация:
    133
    Адрес:
    Заир
    Оффлайн
    Надо бы аналог налимовской базы создать, но попробую своими силами. В нормальных шахматах для матования конём и слоном самая важная позиция - наверное, вот эта:



    Надо перегнать короля в другой угол.

    1. Nf7+ Kg8 2. Kf6 Kf8 3. Bh7 Ke8



    Чтобы продолжить оттеснять короля в сторону a8, приходится выпустить его с последнего ряда.

    4. Ne5 Kd8 5. Ke6 Kc7 6. Nd7 Kb7 7. Bd3

    На доске 8x8 белые быстро ставят мат, королю мешает бортик доски. Но что будет, если добавить пару вертикалей?



    Доска продолжается дальше первой горизонтали вниз и дальше линии "h" вбок. Можно ли наладить оттеснение короля так, чтобы это не почувствовалось? Думаю, что можно. Продолжение - в сдвинутой нотации:

    7... Kc7 8. Kf5 Kb6 9. Ke4 Kc5 10. Kd3 Kb4 11. Bd5 Ka3 12. Kc3



    Королю не удалось дорваться не то что до поля a-1, но даже и до a1. Дальше a3 не пустили. Дальше - матуем, как на обычной доске.

    P.S. Насчёт бОльших досок - предлагаю гипотезу. Для любого числа коней n существует такая размерность доски N, что слон и n коней не могут заматовать короля. Просто по причине того, что если король даст дёру в одном из направлений, то табун коней, вынужденный ходить по очереди, за ним не угонится.
    Мобуту, 19 май 2011
    #53

  19. Skipper_NORTON Старожил

    • Участник
    • Старожил
    Рег.:
    14.12.2007
    Сообщения:
    515
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Ладно, пишу стоклеточные шахматы... Не только генератор эндшпильных баз, а и саму игровую программу. Захотелось поиграть в такие. Доска 10*10. Какой делать стартовую позицию? предпоследние ряды - будут пешки, а на последних нужно добавить 2 фигуры. Предлагаю добавить ферзя и слона. Т.е. получится один король, два — ферзя, ладьи и коня, и три слона. Последовательность у белых - ладья, конь, слон чернопольный, слон белопольный, ферзь, ферзь, король, слон белопольный, конь, ладья. Рокировку можно сделать только в короткую сторону - в длинную не нравится, что король будет прыгать на 5 полей. У черных получится наоборот - два чернопольных слона и один белопольный. Белопольный в этом случае окажется, ценнее, т.к. потеряв его - теряем преимущество двух слонов, которое действует только если слоны разноцветные.
    Skipper_NORTON, 19 май 2011
    #54

  20. NS_Serg Зарегистрирован

    Рег.:
    18.05.2011
    Сообщения:
    15
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Неубедительно.
    На 11. Bd5 - 11... Кс5
    Король не в углу, и без помощи коня в угол ты его не загонишь.
    NS_Serg, 19 май 2011
    #55

  21. miptus Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    1.159
    Симпатии:
    78
    Репутация:
    5
    Оффлайн
    А я бы вместо лишних ферзя и слона добавил двух коней. Не нарушается симметрия, кони прыгучие, с ними интереснее и богаче позиции. Кроме того, будет ближе к военным реалиям (пехота>конница>все остальные).
    miptus, 19 май 2011
    #56

  22. Skipper_NORTON Старожил

    • Участник
    • Старожил
    Рег.:
    14.12.2007
    Сообщения:
    515
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Ну можно ферзя и коня добавить... Пока не знаю. Но 1 ферзь и 4 коня - какой то дисбаланс. Хотя бы 2 ферзя должно быть. Двумя ферзями играть интересно - больше возможностей при атаках.
    Skipper_NORTON, 19 май 2011
    #57

  23. miptus Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    1.159
    Симпатии:
    78
    Репутация:
    5
    Оффлайн
    Но вообще 10х10 будут менее интересные шахматы чем обычные, слишком большое расстояние между пешками. Сразу жесткой борьбы в центре не получится, будет долгое позиционное копание на своей половине доски. Так что генератор интереснее чем игровая программа, хотелось бы увидеть хотя бы одну позицию с разной оценкой на 8х8 и 10х10.
    miptus, 19 май 2011
    #58

  24. Мобуту спаситель нации

    • Заслуженный
    • Ветеран
    Рег.:
    15.02.2006
    Сообщения:
    6.866
    Симпатии:
    3.772
    Репутация:
    133
    Адрес:
    Заир
    Оффлайн


    Да ладно, тут король заматуется без проблем. Первый ход - 12. Ke4, дальше потихоньку затягиваем петлю. Возьмите хотя бы налимовскую базу 8x8 и попробуйте против неё - не устоять, конечно - а вывести короля из загона, огороженного слоном, т.е. за диагональ a2-g8. Наверняка не удастся, т.е. рекомендуемый ею мат в 20 ходов на доске 8x8 без каких-либо изменений является решением и для нашей доски, где нет границы по 1 ряду и по вертикали h.
    Мобуту, 19 май 2011
    #59

  25. NS_Serg Зарегистрирован

    Рег.:
    18.05.2011
    Сообщения:
    15
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    разрешить пешке первым ходом ходить на три поля.
    NS_Serg, 19 май 2011
    #60

  26. NS_Serg Зарегистрирован

    Рег.:
    18.05.2011
    Сообщения:
    15
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Зачем на вы? :)
    Попробовал. Налимовские базы выпускают в угол a1. А потом из него пытаются заматовать.
    NS_Serg, 19 май 2011
    #61

  27. NS_Serg Зарегистрирован

    Рег.:
    18.05.2011
    Сообщения:
    15
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Вру. Похоже 10x10 матуется. Но 12х12 то всяко не выйдет.
    NS_Serg, 19 май 2011
    #62

  28. Crest Админ, МГ

    • Команда форума
    Рег.:
    05.02.2006
    Сообщения:
    57.091
    Симпатии:
    20.860
    Репутация:
    607
    Адрес:
    Москва, Россия
    Оффлайн
    Видимо, в этой теме примерно через 15 страниц ожесточенных споров последует похожий пост:

    :D :D :D
    Crest, 19 май 2011
    #63

  29. NS_Serg Зарегистрирован

    Рег.:
    18.05.2011
    Сообщения:
    15
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    NS_Serg Сегодня в 21:40:26
    NS_Serg, 19 май 2011
    #64
  30. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Отправил письмо на email, с которым был зарегистрирован старый ник. С возвращением!
    Kirr, 19 май 2011
    #65
  31. TopicStarter Overlay

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

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

    P.S. Вождь - голова!
    Kirr, 19 май 2011
    #66
  32. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Отличный бонусный побочный эффект этой темы. :)
    Kirr, 19 май 2011
    #67
  33. TopicStarter Overlay

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

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

    Для начала, прикинем оценку сверху числа позиций для N фигур: UB(N) = 78 * 10^(N-2) * C(14,N-2). Здесь 78 - это число уникальных легальных расстановок королей (в том случае, если на доске есть пешки. Без пешек число меньше (21), но для оценки сверху используем большее, для простоты, чтобы не делить позиции на с пешками и без).

    Код:
    Pieces             UB
   2                       78
   3                   10,920
   4                  709,800
   5               28,392,000
   6              780,780,000
   7           15,615,600,000
   8          234,234,000,000
   9        2,676,960,000,000
  10       23,423,400,000,000
  11      156,156,000,000,000
  12      780,780,000,000,000
  13    2,839,200,000,000,000
  14    7,098,000,000,000,000
  15   10,920,000,000,000,000
  16    7,800,000,000,000,000
    Это на самом деле уже довольно неплохая оценка сверху. Теперь попробуем получить более точную оценку. Для этого посчитаем настоящее число уникальных легальных позиций (NULP) с различным числом фигур (всё время речь о доске 4x4). Пока что я посчитал до 9 фигур:
    Код:
      Pieces       NULP
     2               21
     3            3,378
     4          227,362
     5        8,803,638
     6      226,104,696
     7    4,143,416,867
     8   56,389,004,075
     9  582,127,548,496
    Обратим внимание на отношение UB/NULP:
    Код:
    Pieces  UN/NULP
   2   3.714286
   3   3.232682
   4   3.121894
   5   3.225030
   6   3.453179
   7   3.768774
   8   4.153895
   9   4.598580
    Этот ряд, без первых двух элементов, хорошо приближается многочленом второй степени: y = 0.04171*N^2 - 0.24261*N + 3.41340, где N - число фигур. Таким образом достраиваем недостающие отношения:
    Код:
    Pieces  UN/NULP
  10   5.1583 
  11   5.7916 
  12   6.5083 
  13   7.3085 
  14   8.1920 
  15   9.1590 
  16  10.2094
    После чего получаем приближённые значения NULP:
    Код:
      Pieces         NULP
    10      4,540,914,642,421
    11     26,962,497,410,042
    12    119,966,442,953,020
    13    388,481,294,280,874
    14    866,452,962,761,321
    15  1,192,269,898,460,530
    16    764,001,802,260,662
    Суммируем все NULP вместе, получаем общую оценку: 3,363,318,707,877,400 уникальных легальных позиций в шахматах 4х4. Это практически очень важное число, так как оно позволяет оценить затраты времени и места для полного решения.

    То же самое приближение можно было бы получить, просто аппроксимируя известные значения NULP. Использование отдельно посчитанных оценок сверху всего лишь упрощает этот процесс.

    Для шахмат 8х8 этот метод скорее всего не годится, так как в настоящий момент нам известно слишком мало значений NULP (а строго говоря - лишь одно - для двух голых королей).
    Kirr, 19 май 2011
    #68
  34. TopicStarter Overlay

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

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

    Всё ясно, спасибо за ответ.
    Kirr, 19 май 2011
    #69

  35. Skipper_NORTON Старожил

    • Участник
    • Старожил
    Рег.:
    14.12.2007
    Сообщения:
    515
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Думаю, что гипотеза неверна. Если со слоном и одним конем - на больших досках типа 12*12 еще есть сомнения, то со слоном и двумя конями - можно поставить мат НА ЛЮБОЙ доске, даже 1000*1000. Табун коней отлично гонится за королем, т.к. кони быстрее короля.
    Skipper_NORTON, 19 май 2011
    #70
Страница 2 из 6

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