Эндшпильные таблицы Налимова

Шахматные турниры на форуме, обсуждение теории и новостей

Эндшпильные таблицы Налимова

Сообщение Oleg » Пн ноя 28, 2016 11:20 am

Эндшпильные таблицы Налимова — базы данных шахматных окончаний

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

Размер таблиц и время расчета
Время расчета и объем таблиц Налимова экспоненциально возрастает с количеством участвующих фигур.
Для расчета всех 5-и фигурных таблиц на компьютере с процессором «Атлон» 1,2 ГГц требуется 5 суток, для расчета 6-фигурных таблиц на нем же потребовалось бы уже 860 дней, а всех 7-фигурных около семи столетий. Таким образом, время и производительность компьютеров являются преградой для расчета «эндшпильных» баз всех 32-х фигур. Но, согласитесь, шахматы полностью утратили бы свою прелесть, если бы потеряли возможность использования творческого подхода.
К настоящему времени имеются базы данных, рассчитанные по таблицам Налимова, для всех 3-6- фигурных окончаний (включая двух королей). Решения для 7-и фигурных окончаний все еще рассчитываются, и, ориентировочно, будут готовы к 2015 году.
Размеры таблиц:
3-фигурные окончания занимают 80 КБ.
4-фигурные окончания занимают 30 МБ.
5-фигурные окончания занимают 7,03 ГБ.
6-фигурные окончания занимают 1,205 ТБ. Все 7-фигурные окончания будут занимать порядка 300—400 ТБ.
Аватара пользователя
Oleg
Администратор
Администратор
 
Сообщения: 75645
Зарегистрирован: Вс окт 09, 2005 9:08 pm
Откуда: Москва
Медали: 10
Пол: Мужской
Соционический тип: Бальзак
Тип по психе-йоге: Сократ (ВЛЭФ)
Темперамент: Флегматик
Профессия: Программист, оптимизатор

Эндшпильные таблицы Налимова

Сообщение Oleg » Пн ноя 28, 2016 11:24 am

Время расчёта и объём баз данных шахматных окончаний экспоненциально возрастает с количеством участвующих фигур.

К настоящему времени имеются базы данных для всех трёх-, четырёх-, пяти-, шести- и семифигурных окончаний (включая двух королей). Расчет восьмифигурных окончаний пока ещё не планируется.

Размеры баз данных зависят как от количества фигур, так и от формата самой базы.

Эндшпильные таблицы Налимова
Все 3-фигурные таблицы занимают 62,4 КБ.
Все 4-фигурные таблицы занимают 29,5 МБ.
Все 5-фигурные таблицы занимают 7,03 ГБ.
Все 6-фигурные таблицы занимают 1,205 ТБ.
Базы Ломоносова
Все 3—7-фигурные таблицы занимают 140 ТБ.
Все 8-фигурные таблицы будут занимать приблизительно 10 ПБ.

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

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

В 1970 году Томас Штрохлейн (нем. Thomas Ströhlein) защитил докторскую диссертацию в которой анализировались такие окончание как KQK, KRK, KPK, KQKR, KRKB, и KRKN.

В 1977 году Кен Томпсон на конференции Международной федерации по обработке информации в Торонто представил построенную им таблицу для всех возможных положений в эндшпиле KRKQ «ладья и король против ферзя и короля». Общее число позиций для него составляет около 4 миллионов. Кен Томпсон провел несколько показательных выступлений - компьютер играл за игрока, владеющего ладьёй. Этот эндшпиль теоретически проигрышный, шахматист уровня мастера, владея ферзём, обычно легко выигрывает его у любого противника. Поэтому компьютеру была поставлена задача максимально оттянуть свой теоретически неизбежный проигрыш. Результаты экспериментов, в которых компьютер играл с шахматистами, были довольно интересными. Против программы пытались играть Ханс Берлинер, экс-чемпион мира в игре по переписке, и Лоуренс Дей, чемпион Канады. Ни тот, ни другой не смогли выиграть у программы, хотя любая позиция была для них выигрышной. Дело в том, что теоретически безупречная игра компьютера часто выглядела нелогично, противоречила принципам, предписываемым шахматной теорией (например, обычно рекомендуется не уводить ладью далеко от короля, но программа нередко делала это), необычные ходы компьютера сбивали шахматиста с толку, и он упускал выигрыш, не успевая за 50 ходов поставить мат или выиграть ладью.

В 1970-е и 1980-е годы идея предварительно рассчитанных эндшпилей развивалась очень медленными темпами, так как быстродействие и объём памяти тогдашних компьютеров были существенным ограничением и не позволяли получать подробные таблицы. Тем не менее, Кен Томпсон и другие энтузиасты продолжали медленно генерировать малофигурные окончания и спустя некоторое время, были посчитаны все 4-фигурные окончания, а к концу 1980-х уже все 5-фигурные окончания, включая такие интересные позиции как KBBKN, KQPKQ и KRPKR.

В 1995 году Льюис Стиллер (англ. Lewis Stiller) опубликовал работу посвященную исследованию некоторых 6-фигурных окончаний.

В 1998 году Евгений Налимов создал генератор шахматных окончаний, который оказался чрезвычайно эффективен. Благодаря новому эффективному генератору и росту производительности компьютеров, к началу 2000-х посчитаны были все 6-фигурны окончания, что произвело настоящую революцию в понимании некоторых эндшпилей. Вскоре 6-фигурные окончания стали общедоступными в интернете и являются таковыми по сей день.

В 2012 году были рассчитаны 7-фигурные таблицы для следующих материальных соотношений — четыре фигуры против трёх и пять фигур против двух. Расчёты проводились весной-летом 2012 года, авторы таблиц — Владимир Махнычев и Виктор Захаров, сотрудники ВМК МГУ. База данных названа таблицами Ломоносова, так как они рассчитывались на суперкомпьютерах «Ломоносов» и IBM Blue Gene/P, установленных в Московском государственном университете имени М. В. Ломоносова. 7-фигурные таблицы окончаний впервые активно использовались при анализе партий Чемпионата Мира по шахматам 2012 года.[3][4]. Публичный онлайн доступ к 7-фигурным таблицам окончаний пока отсутствует. В 2016 году бесплатный доступ к таблицам стал частично открыт, но пока только для пользователей телефонов с операционной системой Android, через специальное приложение[
Аватара пользователя
Oleg
Администратор
Администратор
 
Сообщения: 75645
Зарегистрирован: Вс окт 09, 2005 9:08 pm
Откуда: Москва
Медали: 10
Пол: Мужской
Соционический тип: Бальзак
Тип по психе-йоге: Сократ (ВЛЭФ)
Темперамент: Флегматик
Профессия: Программист, оптимизатор

Эндшпильные таблицы Налимова

Сообщение Oleg » Пн ноя 28, 2016 11:26 am

На нашем факультете оказывается эту задачу решили 8-)
Аватара пользователя
Oleg
Администратор
Администратор
 
Сообщения: 75645
Зарегистрирован: Вс окт 09, 2005 9:08 pm
Откуда: Москва
Медали: 10
Пол: Мужской
Соционический тип: Бальзак
Тип по психе-йоге: Сократ (ВЛЭФ)
Темперамент: Флегматик
Профессия: Программист, оптимизатор


  • { SIMILAR_TOPICS }
    Ответы
    Просмотры
    Последнее сообщение

Вернуться в Шахматы

Кто сейчас на конференции

Зарегистрированные пользователи: cooler462, GoGo [Bot], Google [Bot], KostyaAndreev, rtanya, vadimr, Yandex 3.0 [Bot], Yandex [Bot], на лошади весёлой