Шахматы 3x4 - решены

Тема в разделе "Машинное отделение", создана пользователем Kirr, 2 окт 2009.

  1. TopicStarter Overlay

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

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

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

    Число позиций: 167,303,246,916 (учитывая все возможные симметрии).

    Самая длинная линия до мата: 43 хода (85 полуходов).

    Подробности на английском языке:
    Страничка проекта (В процессе создания)
    Обсуждение

    Вопросы/комментарии приветствуются. :)
  2. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.225
    Симпатии:
    2.528
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Вот ведь как!
  3. TopicStarter Overlay

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

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

    • Участник
    Рег.:
    15.05.2007
    Сообщения:
    101
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    а размерчик баз на диске какой?
  5. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    167 ГБ в несжатом виде. Теперь я уже сжал их в 59 ГБ. Можно сжимать и сильнее, но ценой падения скорости обращения. Возможно ещё поэкспериментирую со сжатием, но 59 ГБ меня пока устраивают.

    Сейчас я строю DTC таблицы, в них тоже обнаруживаются залежи интересного. DTC таблицы сжимаются, конечно, гораздо лучше. 12-фигурка в DTC превращается в бит-базу. :)
  6. corplayer Учаcтник

    • Участник
    Рег.:
    15.05.2007
    Сообщения:
    101
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    59 Гб в сжатом виде - это конечно не подвиг Налимова в 6-фигурных, но всё равно приличная размерность.

    Очень интересно сравнение DTC и DTM.

    Разница в размерах? Разница в скорости генерации?

    На одном из форумов я читал, что DTC генерируются в 2 раза быстрее. Непонятно почему.
  7. corplayer Учаcтник

    • Участник
    Рег.:
    15.05.2007
    Сообщения:
    101
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Интересно, а какая следующая задача на повестке дня. Как я понимаю 4x4, но похоже, что слишком круто увеличивается размерность, это будет посложнее 6-фигурных таблиц Налимова.
  8. Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.136
    Симпатии:
    554
    Репутация:
    25
    Адрес:
    Киев
    Оффлайн
    3x5 чуть меньше
  9. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    Kirr, а шашки (чекерс) решили строго или нет, решение надёжное?
  10. TopicStarter Overlay

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

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

    Меньше максимальное значение метрики, следовательно нужно меньше итераций. Кроме того DTC лучше жмётся, что ускоряет чтение и запись на диск.

    4x4 - это, конечно, очень интересно. Боюсь что на него у меня пока что не хватит мощей железа. (Если речь о полном решении). Но в любом случае сначала нужно 3х4 докопать до дна. :)
  11. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Да, 3х5 хороший вариант. Есть ещё 4х3 и 5х3, они немного проще, чем 3х4 и 3х5, но и менее интересны.
  12. TopicStarter Overlay

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

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

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    Не строго из-за очень малой вероятности ошибки или в другом смысле? Вы чем уверены в строгости (полноте, безошибочности) своего теперешного доказательства?
  14. TopicStarter Overlay

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

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

    Как вы любите всё мешать в одну кучу! Уверен, что потом вы радостно назовёте это всё хаосом.

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

    Моё решение строго, так как не использует эвристики. Я не пытаюсь рассуждать "здесь у белых два ферзя за коня, наверное белые победят". Для каждой позиции я вычисляю точную оценку.

    Моё решение полно, так как включает в себя все вообразимые легальные позиции.

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

    Кстати, для таблиц до 6 фигур без пешек и без 5-1 мне прислал статистику Марк Буржуцкий. Он использовал модифицированный генератор Налимова. Наибольшие расстояния до выигрыша у нас с ним совпали по всем таблицам. Число позиций сравнить не удалось, так как в его статистике позиции считаются по-другому. Я считаю только строго уникальные позиции, он считает некоторые позиции дважды.

    Для сравнения, решение шашек командой Chinook - не строгое и не полное. Ну а насчёт безошибочности они, по-видимому, могут быть уверены настолько же, насколько и я.

    Да, ошибки могут быть нескольких типов:
    1. Ошибка нестрогого доказательства.
    2. Ошибка в программе.
    3. Случайная аппаратная ошибка.

    Ошибок первого типа у меня быть не может. Ошибки второго типа - исключить полностью нельзя, но успешная верификация 9-фигурки позволяет надеяться на их отсутствие. Ошибки третьего типа - будут исключены если найдётся доброволец и сгенерирует все таблицы моей программой на своём железе, и если его статистика совпадёт с моей.
  15. TopicStarter Overlay

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

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

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

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

    (DTC таблицы посчитаны до 10 фигур целиком, 11-фигурные считаются).
  17. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.225
    Симпатии:
    2.528
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Сколько времени занял полный расчёт? Сколько выходит в среднем на одну позицию? Другими словами, нельзя ли просто поставить заданное начальное положение, и достаточно быстро получить абсолютную оценку нормальным, а не ретроанализом?
  18. TopicStarter Overlay

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

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

    О сравнении с обычным анализом нужно думать.. :) Если задача просчитать всего одну позицию, то обычный анализ скорее всего быстрее. Если же нужно просчитать окончание целиком (определённую конфигурацию фигур), то только ретроанализ. Даже верификация таблицы, состоящая из поиска на глубину один полуход, занимает больше времени, чем собственно построение таблицы.
  19. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    Нет, на этот раз не назову :D , я отдаю себе отчёт о разницах между этими понятиями. Просто хотел предоставить Вам возможность высказаться более подробно :) .

    Было впечатление, что команда Chinook-а не опиралась на такого сорта эвристики, а на строгие теоретические доказательства предложений типа, скажем, "здесь у белых два ферзя за коня, заведомо белые победят" :D . Но если тип был, как Вы сказали, "здесь у белых два ферзя за коня, наверное белые победят", то я немного разочарован командой Шэффера ;) .

    Если имеем строгое теоретическое (без полного исчерпывающего счёта) доказательство для некоторого класса позиций, то полный счёт не нужен (лишний), ибо лишь подтвердит теоретическое доказательство. К примеру, незачем считать "ладью против голого короля" в обычных шахматах, можно доказать, что какой бы ни была исходная позиция, ладья всегда выигрывает. Стратегия этого выгрыша/доказательства знакома каждому любителю, разумеется.
  20. TopicStarter Overlay

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

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

    Ну, в шашках такой подход вполне может быть оправдан. Со стороны мне трудно судить. Вообще, Хайдук, у меня к вам предложение. Раз вам так интересно решение шашек, давайте вы ознакомитесь со статьями Шаефера, и потом уже вы мне расскажете какие именно у них решение.

    Под "неполнотой" решения шашек командой Chinook я имел ввиду, что они решили не все возможные позиции, а только 10-фигурные эндшпили, и некоторое множество позиций, достижимых из начальной позиции (но не все такие позиции). Понятное дело, что они и не ставили цель решить все позиции. И это нисколько не умаляет их заслуг. Они сделали, наверное, максимум возможного на текущем этапе. Их решение шашек заняло где-то 20 лет, за одно это они заслуживают крайнего уважения.
  21. TopicStarter Overlay

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

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

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

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

    wkpnpRpK..P.N. 9 фигур, расстояние до конверсии - 16 ходов (31 полуход).

    wRQBKB.PPPk.q. 10 фигур, всего 2 свободных поля, расстояние до конверсии - 14 ходов (27 полуходов) :|
  23. vasa Опытный перворазрядник

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    33.213
    Симпатии:
    14.491
    Репутация:
    528
    Адрес:
    Ростов-на-Дону
    Онлайн
    Даже на такой куцей доске мат конём и слоном еле ставится :) :D
  24. Edwards Ветеран

    • Ветеран
    Рег.:
    10.02.2006
    Сообщения:
    6.325
    Симпатии:
    311
    Репутация:
    20
    Адрес:
    CПб
    Оффлайн
    Kirr, не вижу фигур на этой доске :( Только какие-то мелкие надписи.
  25. TopicStarter Overlay

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

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

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

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

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    16
    Репутация:
    0
    Оффлайн
    Вот это там рубилово идет на таком пятачке) как в игре 15 )
  28. TopicStarter Overlay

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

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

    Теперь можно посмотреть, например, самый длинный выигрыш королём и слоном, или как долго (и из какой позиции) максимум держится голый король против 10 фигур, и т.д.

    (Такая же подборка, какую я собирал для обычных шахмат вот здесь: http://kirill-kryukov.com/chess/longest-checkmates/)
  29. TopicStarter Overlay

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

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

    Документация будет дорабатываться, на вопросы буду рад ответить.
  30. dan77790 Учаcтник

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    16
    Репутация:
    0
    Оффлайн
    А шахматы 4х4 намного сложнее, чем 3х4?)

    4х4 - это почти 8х8) Пол-пути пройдено щщитай....
  31. Кузьмич Никита

    • Участник
    Рег.:
    29.12.2009
    Сообщения:
    217
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Санкт-Петербург
    Оффлайн
    Прогрессия расчёта нужна не геометрическая, а экспоненциальная, причём сильно экспоненциальная. Поэтому половиной пути там даже не пахнет)
  32. Alexander Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    12.02.2006
    Сообщения:
    2.087
    Симпатии:
    315
    Репутация:
    15
    Оффлайн
    Забавные клаустрофобские шахматы :)
    Рекордный по продолжительности мат
    Сначала напоминает пятнашки. Потом по мере опустошения доски напрашиваются любопытные сравнения с нормальными шахматами.

    Черные на обычной доске легко делают ничью перемещаясь слоном по свободным клеткам диагонали а5-е1 с целью съесть коня при первой возможности. Попытка так же защищаться на доске 3х4 не проходит, так как белые жертвуют слона b1 а потом догоняют и отнимают слона черных :)
    Или еще в варианте может быть такое:

    Белые в 8х8 быстро матуют попадая конем на b3 — слон не в состоянии препятствовать этому. А в 3х4 нужна еще целая партия :)
    Зато матование конем и слоном происходит по канонам: король загоняется в белый угол, который правда расположен недалеко.
  33. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    До 4х4 предстоит долгий путь. Если, конечно, речь о полном решении. Что-то вроде 6 - 7-фигурки можно посчитать довольно легко.
  34. TopicStarter Overlay

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

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

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

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

    1. Добавлено сжатие LZMA.

    2. Добавлено автоопределение оптимального метода компрессии для каждого блока данных.

    3. Немного изменён формат таблиц: блоки иногда объединяются вместе, иногда нет.

    4. Позиции под шахом сохраняются отдельно от остальных.

    5. Добавлен поиск, как в нормальном движке (очень примитивный). Теперь можно успешно запрашивать позиции для которых нет таблицы.

    6. Добавлена команда '-shrink' - дополнительное урезание базы путём удаления по одной таблице из каждой пары. Например, "krkp - kpkr" - это пара таблиц. '-shrink' оставит только одну из них, а вторую удалит.

    В результате всех этих мер полная база DTM, от 3 до 12 фигур, занимает теперь 50.6 ГБ. После удаления 12-фигурных таблиц и урезания 3-11-фигурных остаются всего 11.8 ГБ, позволяющие тем не менее проверять любую из возможных позиций.

    Формат таблиц не совместим с версией 1.0.0 генератора, нужно генерировать всё с нуля.

    Вопросы, баг-репорты, умные мысли и добрые советы приветствуются. :)

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