Существует ли идеальный алгоритм для шахмат? [закрытый]

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

Вы не совсем правы. Может быть такая машина. Проблемой является громадность пространства состояний, которое это должно было бы искать. Это конечно, это всего ДЕЙСТВИТЕЛЬНО большое.

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

Открытия заданы сценарием для получения Вас к середине игры, которая дает Вам "сильное" положение. Не известный результат. Даже игры конца - когда существует меньше частей - трудно перечислить для определения лучшего следующего перемещения. Технически они конечны. Но количество альтернатив огромно. Даже 2 грачи + король имеют что-то как 22 возможных следующих перемещения. И если требуется 6 перемещений для спаривания, Вы смотрите на 12,855,002,631,049,216 перемещений.

Делают математику при открытии перемещений. В то время как существует только приблизительно 20 вводных перемещений, существует что-то как приблизительно 30 вторых перемещений, таким образом, третьим перемещением мы смотрим на 360 000 альтернативных игровых состояний.

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

при поиске всего пространства всех комбинаций перемещений player1/2 единственное перемещение, которое выбирает компьютер на каждом шаге, основано на эвристике.

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

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

мне просто не удается видеть, как могло быть "идеальное" перемещение на каждом шаге.

Для этого для имения место, там должен для каждого состояния [в текущей игре] быть путем в дереве, которое приводит к победе, независимо от следующего перемещения противника (как в tic-tac-toe), и мне нелегко изображать это.

Шахматы являются примером матричной игры, которая по определению имеет оптимальный результат (думайте Равновесие Нэша). Если плеер 1 и 2 каждый возьмет оптимальные перемещения, определенный результат будет ВСЕГДА достигаться (является ли это потерей связи победы, все еще неизвестно).

От теории игр, которая является тем, о чем этот вопрос, ответ - да, в Шахматы можно играть отлично. Игровое пространство известно/предсказуемо и да, если бы у Вас были Вы квантовые компьютеры внука, то Вы могли бы, вероятно, устранить всю эвристику.

Вы могли записать идеальную tic-tac-toe машину в наше время в любом языке сценариев, и он будет играть отлично в режиме реального времени.

Отелло является другой игрой, в которую данные компьютеры могут легко играть отлично, но память и ЦП машины будут нуждаться в небольшом количестве помощи

, Шахматы теоретически возможны, но не практически возможны (в 2008)

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

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

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

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

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

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

Некоторые игры были, на самом деле, решены. Tic-Tac-Toe является очень легким, для которого можно создать AI, который будет всегда выигрывать или связывать. Недавно, Подключение 4 было решено также (и показано быть несправедливым к второму плееру, так как идеальная игра заставит его проигрывать).

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

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

• общее количество игры в шахматы приблизительно 10^ (10^50). То число является невообразимо большим.
• количество игры в шахматы 40 перемещений или меньше вокруг 10^40. Это - все еще невероятно большое количество.
• количество возможных шахматных положений вокруг 10^46.
• полное шахматное дерево поиска (Шенноновское число) вокруг 10^123, на основе среднего коэффициента ветвления 35 и средней игровой длины 80.
• Для сравнения, количество атомов в заметной вселенной, как обычно оценивается, вокруг 10^80.
• Все эндшпили 6 частей или меньше было сопоставлено и решило .

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

Это не вопрос о компьютерах, но только об игре шахмат.

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

, Например, в игру tic-tac-toe обычно играют на основе эвристики. Но, там существует отказоустойчивая стратегия. Независимо от того, что противник перемещается, Вы всегда находите способ постараться не проигрывать игру, если Вы делаете это с самого начала на.

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

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

исследователи провели почти два десятилетия прохождение через 500 миллиардов миллиардов возможных положений средств проверки, который является все еще бесконечно мало небольшой частью количества шахматных положений, между прочим. Усилие по средствам проверки включало лучших игроков, которые помогли эмпирическим правилам средств проверки программы исследовательской группы в программное обеспечение, которое категоризировало перемещения как успешные или неудачные. Тогда исследователи позволяют прогону программы на среднем числе 50 компьютеров ежедневно. В некоторые дни программа работала на 200 машинах. В то время как исследователи контролировали прогресс и настроили программу соответственно. На самом деле чинуки побеждают людей, чтобы вернуть чемпионат мира средств проверки в 1994.

Да, можно решить шахматы, нет, Вы не будете в ближайшее время.

Как шахматный программист с 1970-х, у меня определенно есть мнение об этом. Что я описал приблизительно 10 лет назад, все еще в основном верно сегодня:

"Незаконченная Работа и вызовы Шахматным Программистам"

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

Средства проверки был недавно решен (Yay, Альбертский университет, Канада!!!), но это была эффективно сделанная Грубая сила. Чтобы сделать шахматы традиционно, необходимо будет быть более умными.

, Если, конечно, Квантовые вычисления не становятся действительностью. Если так, шахматы будут решены так же легко как Tic-Tac-Toe.

в начале 1970-х в Научном американце, была короткая пародия, которая привлекла мое внимание. Это было объявление, что игра шахмат была решена российским шахматным компьютером. Это решило, что существует одно идеальное перемещение для белого, который гарантировал бы победу идеальной игрой обеими сторонами, и то перемещение: 1. a4!

I know next to nothing about what's actually been discovered about chess. But as a mathematician, here's my reasoning:

First we must remember that White gets to go first and maybe this gives him an advantage; maybe it gives Black an advantage.

Now suppose that there is no perfect strategy for Black that lets him always win/stalemate. This implies that no matter what Black does, there is a strategy White can follow to win. Wait a minute - this means there is a perfect strategy for White!

This tells us that at least one of the two players does have a perfect strategy which lets that player always win or draw.

There are only three possibilities, then:

• White can always win if he plays perfectly
• Black can always win if he plays perfectly
• One player can win or draw if he plays perfectly (and if both players play perfectly then they always stalemate)

But which of these is actually correct, we may never know.

The answer to the question is yes: there must be a perfect algorithm for chess, at least for one of the two players.

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

"Существует ли идеальный алгоритм для шахмат?"

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

См. также

• Алгоритм Бога

Меня только на 99,9% убеждает утверждение, что размер пространства состояний не позволяет надеяться на решение.

Конечно, 10^50 - это невозможно большое число. Назовем размер пространства состояний n.

Каково ограничение на число ходов в самой длинной возможной игре? Поскольку все игры заканчиваются конечным числом ходов, такая граница существует, назовем ее m.

Начиная с начального состояния, нельзя ли перечислить все n ходов в пространстве O(m)? Конечно, это займет O(n) времени, но аргументы от размера вселенной не имеют прямого отношения к этому. O(m) пространства может быть даже не очень много. Для O(m) пространства вы не могли бы также отслеживать во время обхода, приводит ли продолжение любого состояния на пути, который вы обходите, к EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin или BlackMayWinOrForceDraw? (Есть решетка в зависимости от того, чей сейчас ход, аннотируйте каждое состояние в истории обхода с помощью встречи решетки.)

Если я ничего не упустил, это алгоритм O(n) времени / O(m) пространства для определения того, к какой из возможных категорий относятся шахматы. Википедия приводит оценку возраста Вселенной примерно в 10^60-е планковские времена. Не вдаваясь в спор о космологии, давайте предположим, что до тепловой/холодной/какой угодно смерти Вселенной осталось примерно столько же времени. Это оставляет нам необходимость оценивать одно движение каждые 10^10-е планковские времена, или каждые 10^-34 секунды. Это невозможно короткое время (примерно на 16 порядков короче, чем самые короткие времена, когда-либо наблюдавшиеся). Давайте оптимистично скажем, что с супер-пупер-хорошей реализацией, работающей на вершине линейки существующих или предвиденных неквантовых технологий, мы могли бы надеяться оценить (сделать один шаг вперед, классифицировать полученное состояние как промежуточное или одно из трех конечных состояний) состояния со скоростью 100 МГц (один раз в 10^-8 секунд). Поскольку этот алгоритм очень хорошо поддается распараллеливанию, нам потребуется 10^26 таких компьютеров, или примерно по одному на каждый атом в моем теле, а также возможность собирать их результаты.

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

Мы также можем надеяться несколько сузить определение шахмат и убедить всех, что с моральной точки зрения это все та же игра. Действительно ли нам нужно требовать, чтобы позиции повторялись 3 раза перед ничьей? Неужели нужно заставлять убегающую сторону демонстрировать способность убежать в течение 50 ходов? Кто-нибудь вообще понимает, что за хрень с правилом en passant? ;) Более серьезно, действительно ли нам нужно заставлять игрока двигаться (в отличие от ничьей или проигрыша), когда его или ее единственным ходом для спасения от шаха или патовой ситуации является en passant взятие? Можем ли мы ограничить выбор фигур, на которые может быть продвинута пешка, если желаемое продвижение без короны не ведет к немедленному шаху или мату?

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

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

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

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

Однако запомнить такие данные было бы неправдоподобно, если вообще возможно. Сделать так, чтобы компьютер распознал наиболее оптимальный ход из (максимум) 8 мгновенно возможных ходов, было бы возможно, но не правдоподобно ...так как этот компьютер должен иметь возможность обрабатывать все ветви, прошедшие, которые движутся, вплоть до заключения, подсчитывать все выводы, которые приводят к выигрышу или тупику, затем действовать на этом количестве правильных выводов против проигрышных выводов, и что потребуется ОЗУ, способное обрабатывать данные в террабайтах или больше! А с современными технологиями для такого компьютера потребовалось бы больше, чем банковский баланс 5 самых богатых мужчин и / или женщин в мире!

Итак, после всех этих размышлений, это можно было сделать, однако никто не мог этого сделать. Такая задача потребовала бы 30 самых ярких умов, живущих сегодня, не только в шахматах, но и в науке и компьютерных технологиях, и такая задача могла быть выполнена только в (давайте полностью рассмотрим это в базовой перспективе) ... чрезвычайно, в конечном счете, гипер супер-пупер компьютер ... который не мог существовать по крайней мере столетие. Это будет сделано! Только не в этой жизни.

К 2040 году средний настольный компьютер стоимостью 1000 долларов будет способен решать шашки всего за 5 секунд (5x10^20 вычислений).

Даже при такой скорости, 100 таким компьютерам потребуется примерно 6,34 x 10^19 лет, чтобы решить шахматы. Все еще не осуществимо. Даже близко нет.

Примерно в 2080 году наши средние настольные компьютеры будут производить примерно 10^45 вычислений в секунду. У одного компьютера будет достаточно вычислительной мощности, чтобы решить шахматы примерно за 27,7 часа. Это определенно будет сделано к 2080 году, если вычислительная мощность будет продолжать расти, как это было последние 30 лет.

К 2090 году на настольном компьютере стоимостью $1000 будет достаточно вычислительной мощности, чтобы решить шахматы примерно за 1 секунду... так что к этому времени они станут совершенно тривиальными.

Учитывая, что шашки были решены в 2007 году, а вычислительная мощность для их решения за 1 секунду будет отставать примерно на 33-35 лет, мы можем приблизительно оценить, что шахматы будут решены где-то между 2055-2057 годами. Вероятно, раньше, поскольку, когда появится больше вычислительных мощностей (что произойдет через 45 лет), больше можно будет посвятить таким проектам, как этот. Однако я бы сказал не ранее 2050 года и не позднее 2060 года.

В 2060 году 100 средним настольным компьютерам потребуется 3,17 x 10^10 лет для решения шахматных задач. Следует понимать, что я использую в качестве эталона компьютер стоимостью $1000, в то время как более крупные системы и суперкомпьютеры, вероятно, будут доступны, поскольку их соотношение цена/производительность также улучшается. Кроме того, их вычислительная мощность увеличивается более быстрыми темпами. Считайте, что суперкомпьютер сейчас может выполнять 2,33 x 10^15 вычислений в секунду, а компьютер за $1000 - около 2 x 10^9. Для сравнения, 10 лет назад разница составляла 10^5 вместо 10^6. К 2060 году разница будет составлять 10^12, и даже она может увеличиваться быстрее, чем ожидается.

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

С другой стороны, в игре "Крестики-нолики", которая намного, намного проще, имеется 2 653 002 возможных вычислений (при открытой доске). Вычислительная мощность, позволяющая решить игру "Крестики-нолики" примерно за 2,5 (1 миллион вычислений в секунду) секунды, была достигнута в 1990 году.

Если двигаться назад, то в 1955 году компьютер мог решить задачу "Крестики-нолики" примерно за 1 месяц (1 вычисление в секунду). Опять же, это основано на том, что 1000 долларов можно было бы получить, если бы вы могли упаковать их в компьютер (настольный компьютер за 1000 долларов, очевидно, не существовал в 1955 году), и этот компьютер был бы посвящен решению задачи Tic-Tac-Toe...., чего просто не было в 1955 году. Вычисления были дорогими и не использовались бы для этой цели, хотя я не верю, что есть дата, когда Tic-Tac-Toe считался "решенным" компьютером, но я уверен, что она отстает от реальной вычислительной мощности.

Кроме того, учтите, что 1000 долларов через 45 лет будет стоить в 4 раза меньше, чем сейчас, поэтому гораздо больше денег может пойти на такие проекты, как этот, в то время как вычислительная мощность будет продолжать дешеветь.

Я нашел эту статью Джона Маккуорри, в которой упоминается работа "отца теории игр" Эрнста Фридриха Фердинанда Цермело. Он делает следующий вывод:

В шахматах либо белые могут форсировать выигрыш, либо черные могут форсировать выигрыш, либо обе стороны могут форсировать по крайней мере ничью.

Логика кажется мне здравой.

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