База данных всех возможных ходов в шахматах

14

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

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

Таким образом, это означает, что нет необходимости в «шахматном движке», потому что все возможные ходы уже записаны.

Если такая база данных существует, она будет иметь следующие преимущества:

  • В быстрых блиц-играх шахматный движок наверняка проиграет против шахматной базы данных ходов
  • Мы можем точно знать, открытие будет иметь больше возможностей, чтобы выиграть против других.

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

Возможно ли существование такой базы данных?

Ахмад Азвар Анас
источник
5
Нет, это невозможно при любой мыслимой технологии.
Тони Эннис
Я бродил некоторое время .. И до сих пор не создал его. Ты прав. Ахаха.
Ахмад Азвар Анас
2
Удачи в создании базы данных с большим количеством байтов, чем атомов во Вселенной
Дэвид
Эй, я новичок в этом сообществе и я из MathStack. Просто чтобы поделиться тем, что во Вселенной меньше атомов, чем количество шахматных игр, возможных в шахматном матче. Попробуйте номер Шеннона ( youtube.com/watch?v=Km024eldY1A ).
Суджит Бхаттачарья

Ответы:

33

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

Подводя итог, можно предположить, что число возможных вариантов игры в шахматы составляет 10 ^ 120. Это поразительно огромное число, для сравнения, считают, что число атомов в наблюдаемой вселенной оценивается примерно в 10 ^ 80 . Другими словами, если бы вы использовали всю наблюдаемую вселенную в качестве жесткого диска, вам все равно нужно было бы хранить 10 ^ 40 комбинаций шахматных игр на каждом атоме , чтобы просто хранить все это. Излишне говорить, что это настолько далеко за пределами наших текущих и прогнозируемых технологий, что большинство людей считают это абсолютно невозможным.

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

Даниэль Б
источник
теперь я представляю, что есть алгоритм, который представляет таблицу конца игры .. ^^
Ахмад Азвар Анас
3
@AhmadAzwarAnas Ну, я думаю, что простые из них уже используются в шахматных движках, а более полные будут добавлены, если позволят технологии. С точки зрения алгоритма, я думаю, вы могли бы «сжать» таблицу финальной игры, проанализировав ее на предмет шаблонов и обобщив их в набор правил, которые явно приводят к результату. Однако, по всей вероятности, этот набор правил по-прежнему будет абсолютно массовым, поскольку крошечные изменения (например, наличие или отсутствие оппозиции) могут изменить результат игры.
Даниэль Б
@AhmadAzwarAnas на самом деле, почему бы не просто алгоритм для шахмат? в каждой проигранной игре должен быть ход, который не тот, верно? то есть ход, до которого существовал путь не проиграть независимо от хода противника, но после которого это уже не так. тогда «все», что должен сделать алгоритм, - это идентифицировать эти шаги, чтобы вы могли их избежать.
Майкл
1
@ Майкл, это сложнее, чем - как ты можешь знать, что существует путь для победы, независимо от того, что двигает противник? в лучшем случае это будет только 50% времени, потому что, если один человек выигрывает, другой вынужден проигрывать. Фактически позволяет вернуть его на исходные позиции - для того, чтобы в игре существовал дальнейший путь, в этот момент должен существовать «абсолютный выигрышный путь» - если мы это выяснили, то зачем кому-то играть проигрышный цвет? зная, что независимо от того, что они движутся, они потеряют? зачем вообще вообще играть в шахматы, если бы мы могли это сделать?
user2813274
2
+1 но твой анализ неверен. Для хранения таблицы нужно хранить только каждую позицию, а не каждую возможную игру. По оценкам Шеннона, существует около 10 ^ 43 позиций , что сопоставимо с 10-50 атомами в земле . Таким образом, вы можете решить шахматы, превратив всю землю в компьютер .
Дэвид Ричерби
8

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

Клод Шеннон подсчитал, что в шахматах есть около 10 43 возможных позиций, и ваша база данных должна будет хранить результаты всех этих действий (по сути, это будет база из 32 человек ). Тем не менее, по оценкам, на Земле содержится всего около 10 50 атомов, поэтому, даже если бы вы могли построить ячейку памяти из всего 10 000 000 атомов, вам все равно понадобился бы компьютер размером с Землю, чтобы хранить все позиции.

Но такой огромный компьютер приносит большие проблемы. Диаметр Земли составляет около 12 800 километров, и свету требуется около 43 мс, чтобы пересечь это расстояние. Это означает, что, если тактовый цикл длится дольше 43 мс, то у вас не только ужасный перекос часов, но и разные части вашего компьютера даже не находятся в одном и том же тактовом цикле. Отказ от этого ограничивает вашу тактовую частоту примерно до 23,5 Гц (не ГГц или МГц; только Гц). Даже если вы сможете полностью оценить позицию за один такт, это означает, что вашему компьютеру потребуется около 4,3x10 41 секунда для выполнения своей задачи. Это примерно 1,4х10 34 года. Это 14 миллионов миллиардов миллиардов миллиардов лет.

Астрофизики считают , что Вселенная будет выглядеть радикально отличается в 1.4x10 34 лет , чем сейчас. К тому времени, звезды будут уже давно перестали существовать и даже элементы, которые не в значимом смысле радиоактивного будет претерпевшим большое количество радиоактивного распада. Даже протоны, которые образуют атомные ядра, подвергнутся значительному радиоактивному распаду. Так что ваш компьютер размером с землю просто больше не будет существовать.

Дэвид Ричерби
источник
2
То есть вы имеете в виду шанс?
bpromas
6

Я думаю, что ответ Даниэля отличный (+1), но все равно хочу добавить несколько мыслей.

Будет ли 32-элементная настольная база действительно заменять шахматные движки? Ответ определенно нет!

Чтобы играть в хорошие шахматы, нужно больше информации, чем выигрыш, ничья или поражение. Конечно, такая база данных была бы непобедима, но вряд ли она кого-то победила бы.

Чтобы сильно играть в шахматы, недостаточно выбирать без потерь ход на каждом ходу. Из множества ходов розыгрыша в каждой позиции лишь немногие оказывают реальное давление на противника.

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

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

BlindKungFuMaster
источник
Вы неправильно поняли, что будет содержать база данных. Каждый возможный ход будет помечен как «Если я играю в это, мой противник может заставить выиграть, что бы я ни делал дальше», «Если я играю в это, я могу заставить выиграть, что бы ни делал мой противник в следующий раз», или «ничья». Таким образом, вы не будете играть «без потерь ходов на каждом ходу»: вы будете играть принудительные выигрыши на каждом ходу, пока такой ход существует.
Дэвид Ричерби
1
Ну, на самом деле я точно понял, что будет содержать база данных ... Я пытался подчеркнуть то, что в шахматных играх высокого уровня "Нет принудительных побед!" более чем на 90% позиций. И вам нужно гораздо больше информации, чем «этот ход тянет и этот ход проигрывает», чтобы действительно попасть на выигрышную позицию против приличного игрока.
BlindKungFuMaster
2
Для примера: в начальной позиции, по всей вероятности, единственной информацией в базе данных будет «Жеребьевка всех ходов». Таким образом , вы будете полностью по своему усмотрению. И если вы полностью по своему усмотрению, как вы получите выигрышную позицию против сильного игрока? Ответ таков: нет. Ваша позиция будет ухудшаться и ухудшаться до того момента, когда вы будете следовать единственной линии рисования.
BlindKungFuMaster
Нет, это не правильно. Это тривиально, чтобы получить ваш выигрышный ход. Просто рассчитайте все возможные ходы из текущей позиции, проверьте результирующие позиции в БД и выберите тот, который выигрывает или выигрывает. По определению, если ваша текущая позиция - «вы выигрываете», в следующих позициях будет по крайней мере одна позиция «вы выигрываете»; и если ваша текущая позиция «ничья», то по крайней мере одна из следующих позиций будет «ничья» (и, возможно, некоторая «вы выиграете», если ваш противник не играет идеально).
Игнасио Кальво
1
Дело в том , что текущее положение обычно не «вы выиграли». Например, очень вероятно, что в стартовой позиции нет принудительного выигрыша.
BlindKungFuMaster
3

Я думаю, что когда-нибудь шахматы будут решены. Почему? Потому что не так давно играть в шахматы против компьютера было странно и немыслимо! Как ты мог научить компьютер играть в шахматы? Ну, они сделали это! (Кроме того, идея компьютера была странной ...) Я считаю, что это может показаться странным, потому что мы никогда не видели и не слышали о нем. Это не то, что мы можем легко представить. Но технологии расширяются в геометрической прогрессии. Я не удивлюсь, если в ближайшем будущем (10+ лет) это будет решено, в той или иной форме.

Райан Орр
источник
1
Препятствием для решения шахмат является буквально астрономическое количество данных, которые вам нужно будет отсортировать. Shannon оценкам, насчитывается примерно 10 ^ 43 позиции в шахматах , и вы должны были бы хранить результаты для каждого из них. Для того, чтобы поставить это в перспективе, земля содержит около 10 ^ 50 атомов так, даже если бы вы могли построить ячейку памяти из 10000000 атомов, вам все равно нужно преобразовать всю землю в банк памяти только для хранения результата!
Дэвид Richerby
1
@DavidRicherby Скажем, шахматы - ничья с лучшей игрой. Тогда для каждого хода белых есть адекватный ответ для черных. К следующему ходу белых у черных также есть адекватный ответ и так далее. Вполне возможно, что для построения такого «дерева рисования» требуется намного меньше 10 ^ 43 позиций.
Даг Оскар Мадсен
4
@DagOskarMadsen Да, вполне возможно, что на самом деле хранение дерева потребовало бы намного меньше памяти (хотя все еще астрономическое количество). Тем не менее, текущий метод построения таких деревьев состоит в том, чтобы проводить ретроградный анализ со всех конечных позиций, что требует построения полной базы данных о том, что делать в каждой позиции, как минимум на промежуточной стадии.
Дэвид Ричерби
1
Извините, что объявляю, что вы не правы! @DagOskarMadsen Но если вы не знаете, как опровергнуть «неадекватные» ответы, действительно ли вы можете утверждать, что решили игру?
Дэвид
2

Вернувшись в колледж в начале 1980-х годов, я прочитал в игре игровой текст, что если бы компьютер мог планировать, оценивать и выполнять ход, любой отдельный ход от начала игры до всех возможных выводов каждую 1/3 наносекунды, это примерно 3 миллиарда ходов в секунду, чтобы сделать это для каждого мыслимого результата, потребуется от 10 до 120 веков. А кому так долго ждать?

Еще одна потрясающая статистика? Вы, очевидно, слышали о гуголе? Не Гугл, а номер? Это от 10 до 100 степени. 10 с последующими 100 нулями. Теперь представьте гуголплекс. Это 10 к власти гугол.

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

Джон
источник
0

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

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

Ласка
источник
-1

Да, я думаю, это было бы возможно. Но только если база данных была больше похожа на нейронную сеть, делала шаги, которые привели к ее потере, и удаляла их. Этот расчет основан на возведении в степень (несите с собой) всех возможных действий в шахматной игре на 1-м ходу, на 100 или около того. Между тем, если мы избавимся от повторов ((Ke3 Ke4 Ke3 Ke4) зацикливание) 10 ^ 120, вероятно, может стать чем-то вроде 10 ^ 70. Это все еще до смешного огромно, но если бы мы каким-то образом смогли закодировать его в четырехмерную плоскость (что, я считаю, возможно), это была бы детская игра.

user19889
источник
2
Добро пожаловать в шахматы ! Пожалуйста, возьмите тур, пока вы на нем. Ваш пост может быть опущен, потому что это скорее мнение, а не ответ, как мы ожидаем; см. статью справочного центра « Как ответить» .
Глорфиндель
2
Я не шахматист, и, к сведению, я тоже не из тех, кто вас голосовал, но я читал, что есть 10 ^ 43 разных позиций. Просто потому, что у вас есть метод, который позволяет отфильтровывать некоторые данные, почему вы автоматически предполагаете, что это делает это возможным? Я думаю, что вы недооцениваете, насколько большим должна быть эта база данных. Это так далеко выходит за рамки современных компьютерных технологий, что я не могу представить, что мы находимся на траектории, чтобы это произошло даже через сто лет. Но добро пожаловать в SE Chess. (И приветствую меня тоже, я полагаю: P)
Джо Маевски