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