Анализ некоторых эндшпилей на досках разных размеров

Zayats

Ну тогда может, есть способ, как приблизить к королю - своего короля и одного коня. А далее, король с конем не позволят одинокому королю убежать в центр, и будут потихоньку оттеснять его ко второму коню или на край.

Ну хорошо, на доске 12х12 два коня точно могут загнать и выиграть, если пат считать как выигрыш. Это уже доказано. Ваши ставки на доску 14х14 и 16х16 ? Ведь 16х16 уже огромная доска.

Очевидно, что через пару миллионов ходов король вернется в центр, кони за это время успеют сделать десяток ходов на всех

Т.е. если я докажу, что на доске 16*16 король и 2 коня загоняют в угол, и патуют одинокого короля, то это будет весьма удивительным фактом?

Придется мне запустить свой генератор на доске 14х14 (или 16х16) и проверить, загоняют ли 2 коня в угол короля (пат определяю как выигрыш в этом окончании). Но у меня какое то смутное подозрение, что есть какой то секрет, который будет работать на досках любого размера, даже 1000х1000. Как то располагая короля и двух коней, с разных сторон, надо надвигаться на короля всеми 3-мя фигурами, чтобы куда бы он ни пошел, рано или поздно удасться сомкнуть все 3 фигуры, и настигнув короля, дальше уже гнать его в угол.

Лучше не тратить время на 14х14 (будет более чем удивительно, если там кони не патуют/матуют, чтобы поставить шах королю в углу централизованному коню - скажем, на g7 - требуется всего три хода), а сразу запустить генератор на 16х16. Это четыре доски, сдвинутые вместе. Думаю, ценность коня на такой доске должна упасть вдвое, т.е. два коня будут примерно равны одному слону (находиться в районе нематующей границы).

Интуитивно, 20% - невозможность мата уже на 16х16;
50% - 18х18;
80% - 20х20.

Если на доске 20х20 мат все же ставится, то, возможно, существует какой-то неочевидный алгоритм.

Так а что изменилось? Допустим, испугались и отступаем к бортику. Мы там будем на 250 тыс. ходов раньше, так что придется проявить выдержку. Когда вражеский король близок - выбираем сторону, начинаем бегство. Если король не хочет выпустить нас обратно в центр, то никаких темпов конь больше не получит (строго говоря, несколько темпов он все же может заработать, но каждый будет стоить десятки тысяч полей, отделяющих нас от центра).

P.S. Немного подвигал фигуры на гобане, с шахматной точки зрения это 18х18. По первым прикидкам, король с трудом, но уходит. Также убедился, что на 14х14 дела плохи, сейчас объясню где беда.


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

Ну что ж... Я так понял, в том, что 2 коня загоняют в угол и патуют на любой доске, вас не убедит ни факт выигрыша на досках 14х14, ни факт выигрыша на доске 16х16...

Придется все таки генерить это окончание на доске 20х20 ! Но это правда, очень долго! А потом я с вами сыграю - вы будете убегать своим королем, а я буду загонять вас в угол 2-мя конями, хорошо? Т.е. я сыграю по построенной базе.

PS Если и после этого вы скажете что-то типа, "ну значит на доске 20х20 кони выигрывают, но вот уже на доске 30х30, точно облом будет" - то я тогда уже и не буду знать, что ответить. Я не могу создавать эти базы на сколь угодно больших досках. Чем больше доска, тем дольше по времени надо генерить. Боюсь, что на доску 20х20 уйдет пару недель...

Zayats и MS.

Хорошо. Значит создаю для доски 20х20, следующую базу - 4_KNN-K, т.е. 2 коня против одинокого короля, с условием что выигрыш - и мат и пат. (если нет возможности сделать ход - это проигрыш). По такой базе будет видно, как играть, чтобы загнать короля в угол. Потому что запатовать можно именно там. Параллельно создаю программу с User Interface для игры по таким базам. Сжатие таких баз я писать не буду (лень). После того как база будет построена, она будет занимать примерно 12 ГБ на диске. Все оптимизации (которые у меня есть в обычном генератора, для доски 8х8) при генерации тоже писать долго, и лень. Распараллеливание расчетов сделаю. Потому база для доски 20х20 будет генерироваться предположительно, 2 недели на 4-ядерном процессоре, и генератор будет требовать около 12 ГБ места на винчестере, и 6 ГБ оперативной памяти (если бы оптимизировал, то было бы намного меньше, но я не хочу заниматься этими оптимизациями, а 6 ГБ оперативы у меня есть).

После того как я сделаю программы, сгенерю базу и скажу результаты. Не пропадайте с форума, думаю через месяцок мы всё выясним для доски 20х20. Когда сделаю, могу и программы скинуть - вы у себя тоже сможете сгенерировать базу.

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

Рад бы предоставить свои выч. мощности, но у меня компьютер не такой современный. Буду с нетерпением ждать результатов, и, как только базы + интерфейс появятся, постараюсь перевести алгоритм (если эта доска решается) на человеческий язык. В противном случае постараюсь распознать ничейные зоны.

Skipper_NORTON в первом посте упоминает, среди прочего, эндшпили KNK и KBK (причем пат считается выигрышем). На досках больше 6х6 в общем случае тут ничья (пат поставить нельзя).

Я посмотрел KNK и KBK на обычной доске 8х8, и получил интересные результаты. Естественно, даже на доске 8х8 существуют позиции, в которых король и конь таки ставят пат, тут ничего удивительного нет. Но! Угадайте, какая максимальная продолжительность игры? Я такого никак не ожидал: в рекордной позиции пат ставится аж в 14 ходов!! Вот одна из 9 таких позиций:


1.Ne3□ Ka1 2.Ka3□ Kb1 3.Kb3□ Kc1! 4.Kc3□ Kb1 5.Nc4! Kc1! 6.Nb2! Kb1 7.Nd3! Ka1! 8.Kb4 Ka2! 9.Ka4! Ka1! 10.Ka3! Kb1 11.Kb3□ Ka1 12.Nc1 Kb1 13.Na2 Ka1 14.Nc3#

Для KBK рекорд - 9 ходов:


1.Ka5 Ka3! 2.Kb5□ Ka2! 3.Kb4! Kb2! 4.Bb3! Kc1 5.Kc3□ Kb1 6.Bd1 Ka1! 7.Kb3 Kb1 8.Bc2! Kc1 9.Kc3#

Видимо, этим рассуждениям место именно здесь.

Вот первые соображения.

Защита должна строиться в каре, шахматная геометрия не нуждается в восьмиугольниках. Диагональ квадрата равна горизонтали или вертикали. Это расстояние называется диаметром (корень из числа коней). Углы следует оставлять пустыми, тогда каждый конь на границе будет защищен 3 или 4 раза, что затруднит противнику нахождение точки прорыва.

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

Следует учитывать, что при разрушении структуры ведут себя по-разному. Так, в игре Life (двумерная модель колонии идеальных бактерий) выделялись особо устойчивые к "вирусам" комбинации. Т.е. может оказаться, что некая симметричная и равнозащищенная структура прорывается сравнительно легко, а какая-то с виду уродливая - держит удар с любой стороны.

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

Фрагмент структуры с линейными дефектами.


По вертикали, горизонтали и любой диагонали ЮЗ-СВ сопротивляемость будет равна единице. В самом деле, рассмотрим взятие коня f6 по диагонали а1-h8 и по вертикали f. В обоих случаях он будет защищен 4 раза: с e8, g8, h7, h5 (кони e4 и d5 погибнут раньше, при уничтожении коня с3) и, соответственно, с e4, e8, g8, h7 (кони d5 и h5 погибнут на поле f4). Коней на единицу площади в полтора раза меньше, но ферзи будут продвигаться в полтора раза быстрее. Масштаб для нас значения не имеет, доска все равно бесконечная. Теперь обратим внимание на диагональ, фрагмент которой мы видим от поля g1 до поля a7. Конечно, сопротивляемость этого направления стремится к нулю при увеличении числа коней, для захвата пункта достаточно конечного числа ферзей (конкретно - пяти). Исходя из этих соображений я сделал ошибочный вывод о бесполезности дефектов (кроме двух эвакуационных путей для короля).

Это поверхностное и примитивное толкование верно лишь для дефектов с постоянным вектором Бюргенса, в этом случае ферзи проскальзывают вглубь коневой решетки как нож сквозь масло. Однако при прочих дефектах сопротивление будет падать незначительно, зато за время перестройки ферзей можно не только отвести короля (при наличии дефектов это можно осуществить и после начала атаки - времени вполне хватит за счет темпов, когда кони не могут взять ферзя), но и провести общеукрепляющие работы. При повышенной концентрации ферзей за полем а1 - сыграть, напр., Кh2-g4; на вертикали f - сыграть Kb8-d7. А королем скромно отступить вбок. Да, ферзей может хватить на разрыв коневой группировки на две части, но пока налаживаться новый штурм коридор вновь зарастет конями и король получит шанс перебраться на другую половину. Потери ферзей при таком методе наступления окажутся чудовищными.

Матует ли конь и слон одинокого короля на поле 9х9 или 11х11 или другое нечетное количество, если слон не цвета углов?

На всякий случай (в этой теме осталось неотмеченным): вопрос, о патовании двумя конями на доске 20х20 (см. пост 49) был решен в отрицательном смысле. Т.к. недостижимость пата была доказана на 16х16 (четыре обычные доски, положенные квадратом). Я ожидал, что критическим размером станет 18х18, поскольку на 16х16 вручную убедился, что король на h1 (или на а8, т.е. посередине края) может быть загнан в угол, хотя и с большим трудом. Однако, как оказалось, уже удовлетворительного оттеснения на край не существует.

The bishop and knight checkmate on a large chessboard

Дата публикации 7 мая 2024 года, сам же метод, как утверждается, был найден еще в 1983.