Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 46
похоже автор статьи решил сделать ещё один вариант таблицы Налимова.
На фото в заголовке статьи нереалистическая ситуация.
Ситация вполне возможная, если чёрный король сам будет лезть под мат.
Я об этом написал в последнем абзаце, перед разделом «Мат в 1 ход».
Я об этом написал в последнем абзаце, перед разделом «Мат в 1 ход».
На первой черный король уходит с b1 на a1 из под шаха белым слоном и след ход белых конем — мат. Ситуация возможна, но черные играли в поддавки
Уважаемый, вы тексты читаете или только картинки смотрите? :)
Я привёл пример невозможного мата, и написал об этом.
Я привёл пример невозможного мата, и написал об этом.
Вторая невозможная.
А первая — очень даже.
Если вывести фигуры в начальную позицию
Черный король — b1
Белый — a3
Конь — a5
Слон — d1
Пусть ход белых.
d1-c2 — шах
Вместо того, чтобы тихо слопать слона, черные уходят в угол
b1-a1
Ну и дальше закономерный мат конем
a5-b3
А первая — очень даже.
Если вывести фигуры в начальную позицию
Черный король — b1
Белый — a3
Конь — a5
Слон — d1
Пусть ход белых.
d1-c2 — шах
Вместо того, чтобы тихо слопать слона, черные уходят в угол
b1-a1
Ну и дальше закономерный мат конем
a5-b3
Сделал ссылку для вашей комбинации, но переставил коня на поле d4, чтобы слона нельзя было есть:
http://videosharp.info/chess/?fen=8/8/8/8/3N4/K7/2B5/1k6
http://videosharp.info/chess/?fen=8/8/8/8/3N4/K7/2B5/1k6
возможная но нереалистическая, ктож под мат будет лезть намеренно :)
посчитайте мат двумя конями может, забавы ради. такой мат нельзя поставить при правильной игре черных.
мат двумя конями невозможен при правильной игре.
(для хранения чисел от 0 до 33 нужно таки 6 бит, а не 5)
Точно :) Просчитался, сейчас исправлю.
Зато фигуру и ход можно закодировать 5-ю битами. У коня и короля только 8 вариантов хода — это 3 бита, а у слона не более 13 вариантов. Для слона надо 4 бита, но т.к. фигур всего 3 — то один бит для слона можно взять из фигуры.
Как-то так:
0 0 NNN — король
0 1 NNN — конь
1 NNNN — слон
Как-то так:
0 0 NNN — король
0 1 NNN — конь
1 NNNN — слон
Гениально. Я тоже об этом много думал. Но это неоправданно усложнит алгоритм, а целого байта выиграть всё равно не выйдет.
Можно уложиться в 3 бита!
Объяснение
«перевернуть» задачу и хранить ходы для чёрных.
Значит, на каждую запись решения достаточно два байта:
Получается, можно и в 1 байт.
После моего предыдущего комментария должно быть очевидно
при сохранении для каждой позиции 5 бит на ход белых и ещё 3 на ход чёрных (из неё же).
В таком случае счётчик ходов вообще не нужен. В случае чего, его можно будет восстановить, переходя туда-сюда по предлагаемым ходам, пока не будет мат.
Для описания позиций, из которых результат недостижим, можно в описание хода слона добавить 14ый вариант, который будет это отмечать.
В таком случае счётчик ходов вообще не нужен. В случае чего, его можно будет восстановить, переходя туда-сюда по предлагаемым ходам, пока не будет мат.
Для описания позиций, из которых результат недостижим, можно в описание хода слона добавить 14ый вариант, который будет это отмечать.
> В случае чего, его можно будет восстановить, переходя туда-сюда по предлагаемым ходам, пока не будет мат.
ага, в дереве из ~6-7 млн. узлов, с глубиной до 65 (полуходов), это почти тот же самый алгоритм, что и тот который нам эту базу рассчитывает, можно тогда уж не хранить ее вообще, а на каждом ходе рассчитывать просто лучший ход =)
ага, в дереве из ~6-7 млн. узлов, с глубиной до 65 (полуходов), это почти тот же самый алгоритм, что и тот который нам эту базу рассчитывает, можно тогда уж не хранить ее вообще, а на каждом ходе рассчитывать просто лучший ход =)
После того, как найдены все оптимальные ходы, для любой позиции за можно быстро (за 65 переходов в худшем случае) найти количество ходов до конца игры.
Непосредственно во время игры рассчитывать 6-7 млн узлов нет смысла, а вот вопрос типа «за сколько ходов выиграют белые» вполне может возникнуть.
Непосредственно во время игры рассчитывать 6-7 млн узлов нет смысла, а вот вопрос типа «за сколько ходов выиграют белые» вполне может возникнуть.
Оптимизация размера с одноцветным слоном не самая оптимальная, имхо )
Можно сократить размер базы в четыре раза, если рассматривать только позиции, в которых черный король находится в верхней половине доски, а белый — в левой (а слон и конь могут занимать любое поле). Ну или выбрать другую пару фигур. Все остальные позиции можно свести к этим одним или двумя отражениями (по вертикали и горизонтали)
Можно сократить размер базы в четыре раза, если рассматривать только позиции, в которых черный король находится в верхней половине доски, а белый — в левой (а слон и конь могут занимать любое поле). Ну или выбрать другую пару фигур. Все остальные позиции можно свести к этим одним или двумя отражениями (по вертикали и горизонтали)
У меня была мысль использовать только 16 позиций белого короля (левый нижний угол 4х4), а все остальные комбинации получать отражением.
Но переделывать уже не стал.
Но переделывать уже не стал.
Симметрий больше чем две, так что достаточно рассмотреть всего 10 позиций короля. Кроме того, использовать симметрию можно не только в начальной позиции, но и во всем графе.
совершенно верно, это позволит сократить файл до 2,5 МиБ, но значительно усложнит алгоритм расчета графа
Так же и при чтении этой БД потом придется либо сразу распаковывать ее на «полный граф», либо при каждом ходе делать пересчет координат, читать запись и пересчитывать обратно
Если уж нужна экономия места — проще использовать сжатие, этот файл достаточно хорошо сжимается (обычным zip-ом до 6 МБ запросто)
в общем все зависит еще от того, нужна ли скорость или экономия десятка мегабайт (что не так уж и много даже для мобильного приложения)
Так же и при чтении этой БД потом придется либо сразу распаковывать ее на «полный граф», либо при каждом ходе делать пересчет координат, читать запись и пересчитывать обратно
Если уж нужна экономия места — проще использовать сжатие, этот файл достаточно хорошо сжимается (обычным zip-ом до 6 МБ запросто)
в общем все зависит еще от того, нужна ли скорость или экономия десятка мегабайт (что не так уж и много даже для мобильного приложения)
Вы как в воду глядите! База решений в 16 мб запокавались зипом в 5.99 мегобайт.
Я точно не знаю, как устроены настоящие таблицы Налимова, но и наивный подход к использованию симметрии даст очевидную экономию. В качестве вершин графа нужно брать только «каноничные» позиции (например, где белый король находится на одном из 10 полей треугольника a1-d1-d4). На ребрах графа помимо ходов нужно добавить преобразование симметрии (элемент группы D4), такое что при применении к каноничной позиции получается требуемая. Этот граф и строить быстрее, и хранить проще, и использовать. В нем вершин примерно в 6 раз меньше, чем в исходном. Усложнение алгоритма незначительно: нужно лишь при прохождении графа перемножать преобразования (элементы группы), стоящие на ребрах, по которым проходим.
> Количество возможных комбинаций — 64 * 64 * 64 * 64 = 16,777,216.
У вас проблема с подсчётом комбинаций. Правильная цифра 64*63*62*61. Т.к., если король стоит на клетке, то там никак не может стоять конь.
У вас проблема с подсчётом комбинаций. Правильная цифра 64*63*62*61. Т.к., если король стоит на клетке, то там никак не может стоять конь.
Речь идёт о размере массива для хранения позиций.
Далее идёт пояснение, цитирую:
Далее идёт пояснение, цитирую:
На самом деле комбинаций ещё меньше: на одной клетке не может стоять две фигуры, короли не могут стоять на соседних клетках, чёрный король не может быть под шахом и так далее. Забегая вперёд скажу, что в базе решений оказалось 5,609,790 комбинаций, массив будет заполнен на 67%.
Здесь фишка еще в том, что сама позиция записи в файле является важной информацией — это координаты фигур, если хранить только возможные позиции, тр придется хранить еще и координаты всех фигур, в итоге выйдет очень затратно и займет такой файл еще больше чем описанный
У вас проблема с подсчётом комбинаций. Правильная цифра 64*63*62*61. Т.к., если король стоит на клетке, то там никак не может стоять конь.
По-хорошему, количество комбинаций больше в два раза — важно, какой игрок собирается ходить. Но автор сделал иначе и сохранял только те варианты, в которых должны ходить белые.
возможно я где то ошибаюсь но картинка к посту у вас подозрительная т.к. мат слоном и конем ставиться в углу цвета слона пруфлинк.
Будучи школьниками, с одноклассником шутили на тему одной интересной позиции.
Белые: Слон на а1, конь на f6, король на f7 (или g6 — не имеет значения);
Чёрные: король на h8.
Ход белых. Мат в один ход.
Решение простое: конь подпрыгивает и зависает в воздухе. Назвали этот мат, как мат Рица.
Потом пришёл отец одноклассника и сказал, что мы ничего не понимаем в шахматах и сделал за чёрных простой ход — король подпрыгнул и завис в воздухе.
P. S. А почему статья здесь, а не на Хабре?
Белые: Слон на а1, конь на f6, король на f7 (или g6 — не имеет значения);
Чёрные: король на h8.
Ход белых. Мат в один ход.
Решение простое: конь подпрыгивает и зависает в воздухе. Назвали этот мат, как мат Рица.
Потом пришёл отец одноклассника и сказал, что мы ничего не понимаем в шахматах и сделал за чёрных простой ход — король подпрыгнул и завис в воздухе.
P. S. А почему статья здесь, а не на Хабре?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Мат конём и слоном. База решений