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

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

Почти все современные компьютерные программы для игры в шахматы имеют опцию для подключения таблиц Налимова.

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

Некоторые интересные позиции

Длиннейшие выигрыши

3-фигурные окончания. Мат в 28 ходов, FEN: 8/8/8/k7/8/K7/6P1/8 b.
4-фигурные окончания. Мат в 43 хода, FEN: 8/5k2/2PK4/5r2/8/8/8/8 w.
5-фигурные окончания. Мат в 127 ходов, FEN: 8/8/8/8/1p2P3/4P3/1k6/3K4 w.
6-фигурные окончания. Мат в 262 хода, FEN: 6k1/5n2/8/8/8/5n2/1RK5/1N6 w.
7-фигурные окончания. [tb7.chessok.com/probe/3/61 Мат в 549 ходов, FEN: 1n1k4/6Q1/5KP1/8/7b/1r6/8/8 w.]

Расчёт

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

Для расчёта всех пятифигурных таблиц на компьютере с процессором «Атлон» 1,2 ГГц требуется 5 суток, для расчета шестифигурных таблиц на нём же потребовалось бы уже 860 дней, а всех семифигурных — около семи столетий. Таким образом, время и производительность компьютеров являются преградой для расчёта «эндшпильных» баз всех 32-х фигур.

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

Размер

• Все 3-фигурные окончания занимают 62,4 КБ.
• Все 4-фигурные окончания занимают 29,5 МБ.
• Все 5-фигурные окончания занимают 7,03 ГБ.
• Все 6-фигурные окончания занимают 1,205 ТБ.
• Все 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 года.. Публичный онлайн доступ к 7-фигурным таблицам окончаний пока отсутствует. В 2016 году бесплатный доступ к таблицам стал частично открыт, но пока только для пользователей телефонов с операционной системой Android, через специальное приложение.

См. также

• Компьютерные шахматы
• Эндшпиль

Ссылки

• [www.shredderchess.com/online-chess/online-databases/endgame-database.html Endgame Database] shredderchess.com
• [www.k4it.de/index.php?topic=egtb&lang=en On-line анализ вплоть до 6-и фигурного эндшпиля.]
• [chessok.com/?page_id=27966 Lomonosov Endgame Tablebases (про 7-фигурные).]
• [horizonchess.com/FAQ/Winboard/egtb.html#%5BA.9%5D A guide to Endgames Tablebase]
• [chess-practic.fatal.ru/view_party/1_art_full/art_material/tbl_nalimov/tbl_nalimov.html Эндшпильные таблицы Налимова.]
• Мичи Д., Джонстон Р. Компьютер-творец / Пер. с англ.— М. Мир, 1987.— стр.68, «Странный случай с таблицей Томпсона».
• [chessok.com/?page_id=27966 Lomonosov Endgame Tablebases] (англ.) // ChessOK.com

Отрывок, характеризующий Эндшпильные таблицы Налимова

Гости сидели за ужином. Княгиня Курагина, массивная, когда то красивая, представительная женщина сидела на хозяйском месте. По обеим сторонам ее сидели почетнейшие гости – старый генерал, его жена, Анна Павловна Шерер; в конце стола сидели менее пожилые и почетные гости, и там же сидели домашние, Пьер и Элен, – рядом. Князь Василий не ужинал: он похаживал вокруг стола, в веселом расположении духа, подсаживаясь то к тому, то к другому из гостей. Каждому он говорил небрежное и приятное слово, исключая Пьера и Элен, которых присутствия он не замечал, казалось. Князь Василий оживлял всех. Ярко горели восковые свечи, блестели серебро и хрусталь посуды, наряды дам и золото и серебро эполет; вокруг стола сновали слуги в красных кафтанах; слышались звуки ножей, стаканов, тарелок и звуки оживленного говора нескольких разговоров вокруг этого стола. Слышно было, как старый камергер в одном конце уверял старушку баронессу в своей пламенной любви к ней и ее смех; с другой – рассказ о неуспехе какой то Марьи Викторовны. У середины стола князь Василий сосредоточил вокруг себя слушателей. Он рассказывал дамам, с шутливой улыбкой на губах, последнее – в среду – заседание государственного совета, на котором был получен и читался Сергеем Кузьмичем Вязмитиновым, новым петербургским военным генерал губернатором, знаменитый тогда рескрипт государя Александра Павловича из армии, в котором государь, обращаясь к Сергею Кузьмичу, говорил, что со всех сторон получает он заявления о преданности народа, и что заявление Петербурга особенно приятно ему, что он гордится честью быть главою такой нации и постарается быть ее достойным. Рескрипт этот начинался словами: Сергей Кузьмич! Со всех сторон доходят до меня слухи и т. д.
– Так таки и не пошло дальше, чем «Сергей Кузьмич»? – спрашивала одна дама.
– Да, да, ни на волос, – отвечал смеясь князь Василий. – Сергей Кузьмич… со всех сторон. Со всех сторон, Сергей Кузьмич… Бедный Вязмитинов никак не мог пойти далее. Несколько раз он принимался снова за письмо, но только что скажет Сергей … всхлипывания… Ку…зьми…ч – слезы… и со всех сторон заглушаются рыданиями, и дальше он не мог. И опять платок, и опять «Сергей Кузьмич, со всех сторон», и слезы… так что уже попросили прочесть другого.
– Кузьмич… со всех сторон… и слезы… – повторил кто то смеясь.
– Не будьте злы, – погрозив пальцем, с другого конца стола, проговорила Анна Павловна, – c'est un si brave et excellent homme notre bon Viasmitinoff… [Это такой прекрасный человек, наш добрый Вязмитинов…]
Все очень смеялись. На верхнем почетном конце стола все были, казалось, веселы и под влиянием самых различных оживленных настроений; только Пьер и Элен молча сидели рядом почти на нижнем конце стола; на лицах обоих сдерживалась сияющая улыбка, не зависящая от Сергея Кузьмича, – улыбка стыдливости перед своими чувствами. Что бы ни говорили и как бы ни смеялись и шутили другие, как бы аппетитно ни кушали и рейнвейн, и соте, и мороженое, как бы ни избегали взглядом эту чету, как бы ни казались равнодушны, невнимательны к ней, чувствовалось почему то, по изредка бросаемым на них взглядам, что и анекдот о Сергее Кузьмиче, и смех, и кушанье – всё было притворно, а все силы внимания всего этого общества были обращены только на эту пару – Пьера и Элен. Князь Василий представлял всхлипыванья Сергея Кузьмича и в это время обегал взглядом дочь; и в то время как он смеялся, выражение его лица говорило: «Так, так, всё хорошо идет; нынче всё решится». Анна Павловна грозила ему за notre bon Viasmitinoff, а в глазах ее, которые мельком блеснули в этот момент на Пьера, князь Василий читал поздравление с будущим зятем и счастием дочери. Старая княгиня, предлагая с грустным вздохом вина своей соседке и сердито взглянув на дочь, этим вздохом как будто говорила: «да, теперь нам с вами ничего больше не осталось, как пить сладкое вино, моя милая; теперь время этой молодежи быть так дерзко вызывающе счастливой». «И что за глупость всё то, что я рассказываю, как будто это меня интересует, – думал дипломат, взглядывая на счастливые лица любовников – вот это счастие!»
Среди тех ничтожно мелких, искусственных интересов, которые связывали это общество, попало простое чувство стремления красивых и здоровых молодых мужчины и женщины друг к другу. И это человеческое чувство подавило всё и парило над всем их искусственным лепетом. Шутки были невеселы, новости неинтересны, оживление – очевидно поддельно. Не только они, но лакеи, служившие за столом, казалось, чувствовали то же и забывали порядки службы, заглядываясь на красавицу Элен с ее сияющим лицом и на красное, толстое, счастливое и беспокойное лицо Пьера. Казалось, и огни свечей сосредоточены были только на этих двух счастливых лицах.
Пьер чувствовал, что он был центром всего, и это положение и радовало и стесняло его. Он находился в состоянии человека, углубленного в какое нибудь занятие. Он ничего ясно не видел, не понимал и не слыхал. Только изредка, неожиданно, мелькали в его душе отрывочные мысли и впечатления из действительности.
«Так уж всё кончено! – думал он. – И как это всё сделалось? Так быстро! Теперь я знаю, что не для нее одной, не для себя одного, но и для всех это должно неизбежно свершиться. Они все так ждут этого , так уверены, что это будет, что я не могу, не могу обмануть их. Но как это будет? Не знаю; а будет, непременно будет!» думал Пьер, взглядывая на эти плечи, блестевшие подле самых глаз его.
То вдруг ему становилось стыдно чего то. Ему неловко было, что он один занимает внимание всех, что он счастливец в глазах других, что он с своим некрасивым лицом какой то Парис, обладающий Еленой. «Но, верно, это всегда так бывает и так надо, – утешал он себя. – И, впрочем, что же я сделал для этого? Когда это началось? Из Москвы я поехал вместе с князем Васильем. Тут еще ничего не было. Потом, отчего же мне было у него не остановиться? Потом я играл с ней в карты и поднял ее ридикюль, ездил с ней кататься. Когда же это началось, когда это всё сделалось? И вот он сидит подле нее женихом; слышит, видит, чувствует ее близость, ее дыхание, ее движения, ее красоту. То вдруг ему кажется, что это не она, а он сам так необыкновенно красив, что оттого то и смотрят так на него, и он, счастливый общим удивлением, выпрямляет грудь, поднимает голову и радуется своему счастью. Вдруг какой то голос, чей то знакомый голос, слышится и говорит ему что то другой раз. Но Пьер так занят, что не понимает того, что говорят ему. – Я спрашиваю у тебя, когда ты получил письмо от Болконского, – повторяет третий раз князь Василий. – Как ты рассеян, мой милый.
Князь Василий улыбается, и Пьер видит, что все, все улыбаются на него и на Элен. «Ну, что ж, коли вы все знаете», говорил сам себе Пьер. «Ну, что ж? это правда», и он сам улыбался своей кроткой, детской улыбкой, и Элен улыбается.
– Когда же ты получил? Из Ольмюца? – повторяет князь Василий, которому будто нужно это знать для решения спора.
«И можно ли говорить и думать о таких пустяках?» думает Пьер.
– Да, из Ольмюца, – отвечает он со вздохом.
От ужина Пьер повел свою даму за другими в гостиную. Гости стали разъезжаться и некоторые уезжали, не простившись с Элен. Как будто не желая отрывать ее от ее серьезного занятия, некоторые подходили на минуту и скорее отходили, запрещая ей провожать себя. Дипломат грустно молчал, выходя из гостиной. Ему представлялась вся тщета его дипломатической карьеры в сравнении с счастьем Пьера. Старый генерал сердито проворчал на свою жену, когда она спросила его о состоянии его ноги. «Эка, старая дура, – подумал он. – Вот Елена Васильевна так та и в 50 лет красавица будет».