Какова самая высокая известная нижняя граница для мате в N от начальной позиции?

Редактировать : Кажется, мой вопрос не был достаточно ясен. Позвольте мне перефразировать: Какой самый большой N, для которого мы можем сознательно сказать, что «шахматы с исходной позиции не являются вынужденным помощником в N ходов»?

Шахматы не решены, т.е. неизвестно, какому результату исходной позиции дается идеальная игра.

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

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

По сути, это вопрос сложности игры в шахматы. Обратите внимание , что конечность, мы знаем , что шахматы будет определенно, но мы не знаем , если стартовая позиция является победой белого, победой для черного, или ничьей. Сложность игры в шахматы примерно равна минимальному количеству позиций, которые мы должны проверить в дереве игры, чтобы определить состояние начальной позиции. Это известно как число Шеннона . Во влиятельной статье « Программирование компьютера для игры в шахматы» Шеннон подсчитал, что число Шеннона составляет не менее 10 ^ {120). Обратите внимание, что число частиц во Вселенной оценивается в 10 ^ (80). Чтобы ответить на вопрос, мы на самом деле хотим знать высотуигрового дерева, когда начальная позиция становится определенной. Мы также должны разделить эту высоту на 2, поскольку ход в шахматах обычно считается ходом белых и черных. Коэффициент ветвления дерева оценивается примерно в 30. Таким образом, мы можем взять наибольшее N такое, что 30 ^ (2N) <10 ^ (120).

Ответ. На обратной стороне конверта работает N = 40. По случайному совпадению это средняя продолжительность игры между гроссмейстерами (хотя они часто уходят в отставку и фактически не играют в игру до конца).

Редактировать. Мораль этой истории в том, что я пытался оценить верхнюю границу для вашей нижней границы. Первая часть рассуждений Шеннона не круглая; он говорит, что есть приблизительно 30 законных ходов с каждой позиции, и это число является достаточно постоянным для первой части игры.

Таким образом, мы можем оценить текущее известное значение N (которое на самом деле то, что вы просите, давайте назовем это N '), чтобы оно было не более log_30 (C), где C равно количеству вычислительной мощности, существовавшей в истории. человечества. Даже с консервативными оценками для C мы получаем что-то вроде N 'не более 20. На практике я не думаю, что кто-то выполнил это вычисление очень далеко вверх по дереву, поскольку априори мы знаем, что вычисление становится недостижимым после очень небольшого роста и нет необходимости тщательно искать дерево, чтобы писать хорошие шахматные программы.

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

Это неправда, что стартовая позиция не может быть выиграна за 5 ходов или меньше, используя каноническое определение полного хода в шахматах. Это можно сделать за 2 хода через Fool's Mate .

Чтобы ответить на ваш вопрос, сила шахматного движка зависит от программного и аппаратного обеспечения. В 1997 году Deep Blue стал доказательством аппаратной концепции, суперкомпьютера с массивным параллелизмом, способного оценивать 200 миллионов ходов в секунду со средней глубиной 7-8 ходов. Однако в 2006 году Deep Fritz, работающий на двухъядерном персональном компьютере, дал эквивалентные результаты, оценив лишь 8 миллионов движений в секунду.

Сегодня самым сильным суперкомпьютером, который был применен в шахматах, является Blue Gene . Используя 131 000 процессоров, Blue Gene может вычислять 280 триллионов операций в секунду . Хотя нет данных, подтверждающих глубину, на которую может рассчитать Blue Gene, я бы предположил, что она будет достаточно глубокой. Конечно, это зависит от того, как долго работает компьютер.

Однако в этом случае мы не можем использовать термин «исчерпывающий» при «решении» и открытии. Шахматному движку не нужно идти до конца линии, когда он уверен, что конечный результат является решающим. В таком случае программа закроется, когда станет ясно, что оценка явно в пользу одной из сторон. Это известно в теоретической информатике как альфа-бета-обрезка .

Если бы мне пришлось сделать приблизительную оценку, я бы сказал, что Blue Gene сможет рассчитывать от 15 до 20 ходов в секунду. Хотя его аппаратное и программное обеспечение чрезвычайно впечатляет, мы должны помнить, что сложность шахматных масштабов экспоненциально. Согласно последним оценкам , сложность игры в шахматы составляет не менее 10 ^ 123, а количество потенциальных позиций - 10 ^ 46,7.

Если предположить, что с данной позиции есть выигрышное продолжение, и предполагается, что идеальная игра подразумевает, что Nона фиксированная, а не ограниченная (в противном случае это не идеальная игра!).

В этом случае нужно по-настоящему работать задом наперед - что достигается Endgame Tablebase

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

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

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

Позвольте мне также воспроизвести комментарии Бурзучки: «Могут существовать еще более глубокие окончания из 7 человек, но я сомневаюсь в этом. То, что такая большая глубина все еще возможна при такой большой огневой мощи на доске, позволяет предположить, что даже более глубокие окончания могут возникнуть с 8 частями, возможно, в krnnkbbn. Это окончание может быть сгенерировано с 64 ГБ ОЗУ в течение нескольких месяцев на быстрой однопроцессорной машине и около 5 терабайт памяти. Любые желающие? "

Изменить: Извините, похоже, я неправильно прочитал вопрос. Я предполагаю, что любой разумный N находится далеко за горизонтом компьютера. Если мы настроим очень мощный компьютер для расчета начальной позиции, который, вероятно, будет единственной достоверной буквой X, которую мы можем показать, скажем, он может 10 миллионов узлов в секунду через 10 дней, мы можем вычислить 10 * 86400 * 10 ^ 8 узлов = 8,64 * 10. ^ 13 узлов. Если мы предположим, что средняя позиция в первые 20 ходов имеет около 15 допустимых ходов (ниже, потому что начало имеет намного меньше и, возможно, даже немного ниже из-за обрезки альфа-бета), что составляет всего около 12 ходов через 10 дней (позиция только после хода 6 ) так что вы видите, почему эта проблема безобразна. Тем не менее, я думаю, что практическая игра, вероятно, предполагает гораздо, гораздо, гораздо большую ценность Я'

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

Таким образом, это означает, что у нас может быть 49,5 ходов на захват или пешку. Каждая пешка может перемещаться до 6 раз, и для каждой стороны можно захватить по 15 фигур (хотя одна часть должна оставаться, чтобы поставить мат), поэтому мы можем установить верхнюю границу для количества ходов.

Это получается до 49,5 * (8 * 2 * 6 (ходы пешки) + 29) = 6187,5. Таким образом, это означает, что если шахматы - это принудительная победа белых с соблюдением правила 50 ходов, то для белых у них не более 6188 ходов. , Я, вероятно, мог бы понизить это немного, не делая слишком много, сказав, что все K + фигуры против K товарищей, которые вынуждены (Ладья только на Queen), выполнимы существенно меньше, чем за 50 ходов (я думаю о 16 играх с Налимовым для некоторые "тяжелые" случаи. Так что я думаю, что мы можем, вероятно, вычесть 34 хода из этой суммы уверенно для 6134!

Поэтому: если шахматы - это вынужденная победа белых с соблюдением правила 50 ходов, то это не более 6134 ходов.