Есть ли идеальный алгоритм для шахмат?
Недавно я беседовал с не-кодером о возможностях шахматных компьютеров. Я не очень хорошо разбираюсь в теории, но думаю, что знаю достаточно.
Я утверждал, что не может существовать детерминистская машина Тьюринга, которая всегда побеждала или пала в шахматах. Я думаю, что даже если вы будете искать по всему пространству всех комбинаций ходов игрока 1/2, единственный ход, который компьютер выбирает на каждом шаге, основан на эвристике. Основанный на эвристике, он не обязательно побеждает ВСЕ ходы, которые мог сделать противник.
Напротив, мой друг думал, что компьютер всегда будет выигрывать или проигрывать, если он никогда не совершит "ошибку" (но вы это определяете?). Тем не менее, будучи программистом, взявшим CS, я знаю, что даже ваш удачный выбор - при наличии мудрого противника - может заставить вас сделать "ошибочные" шаги в конце. Даже если вы знаете все, ваш следующий шаг будет жадным в соответствии эвристике.
Большинство шахматных компьютеров пытаются сопоставить возможную конечную игру с развивающейся игрой, что по сути является следом динамического программирования. Опять же, рассматриваемый эндшпиль можно избежать.
Редактировать: Хм... похоже, что я взъерошил некоторые перья здесь. Это хорошо.
Размышляя об этом снова, кажется, что нет теоретической проблемы с решением конечной игры, такой как шахматы. Я бы сказал, что шахматы немного сложнее, чем шашки в том смысле, что победа не обязательно заключается в численном истощении фигур, но в мате. Мое первоначальное утверждение, вероятно, неверно, но, опять же, я думаю, что я указал на то, что еще не было удовлетворительно доказано (формально).
Я предполагаю, что мой мысленный эксперимент состоял в том, что всякий раз, когда берется ветвь в дереве, алгоритм (или запоминаемые пути) должен находить путь к мату (без соединения) для любой возможной ветки на ходах противника. После обсуждения я куплю, что, учитывая больше памяти, чем мы можем мечтать, все эти пути могут быть найдены.
27 ответов
"Я утверждал, что не может быть детерминированной машины Тьюринга, которая всегда побеждала или зашла в тупик".
Ты не совсем прав. Там может быть такая машина. Проблема заключается в огромности государственного пространства, которое ему придется искать. Это конечно, просто ДЕЙСТВИТЕЛЬНО большое.
Вот почему шахматы возвращаются к эвристике - пространство состояний слишком велико (но конечно). Даже перечислять - намного меньше искать каждый совершенный ход по каждому курсу каждой возможной игры - было бы очень, очень большой проблемой поиска.
Вскрытие сценариев позволяет вам перейти к середине игры, которая дает вам "сильную" позицию. Неизвестный результат. Даже окончательные игры - когда их меньше - сложно перечислить, чтобы определить лучший следующий ход. Технически они конечны. Но количество альтернатив огромно. Даже у 2 ладей + короля есть что-то вроде 22 возможных следующих ходов. И если для спаривания требуется 6 ходов, вы смотрите на 12 855 002 631 049 216 ходов.
Сделайте математику на начальных ходах. В то время как есть только около 20 начальных ходов, есть что-то около 30 или около того вторых ходов, поэтому к третьему ходу мы смотрим на 360000 альтернативных состояний игры.
Но шахматные игры (технически) конечны. Огромный, но конечный. Там отличная информация. Есть определенные начальное и конечное состояния, нет бросков монет и бросков кубиков.
Я почти ничего не знаю о том, что на самом деле было обнаружено в шахматах. Но как математик, вот мои рассуждения:
Сначала мы должны помнить, что белые должны идти первыми, и, возможно, это дает им преимущество; возможно, это дает черным преимущество.
Теперь предположим, что для черных не существует идеальной стратегии, которая позволяла бы ему всегда побеждать / тупить. Это означает, что независимо от того, что делают черные, существует стратегия, которой белые могут следовать, чтобы выиграть. Подождите минуту - это значит, что у белых есть идеальная стратегия!
Это говорит нам о том, что по крайней мере один из двух игроков имеет идеальную стратегию, которая позволяет этому игроку всегда выигрывать или ничьей.
Тогда есть только три возможности:
- Белые всегда могут выиграть, если они отлично играют
- Черные всегда могут выиграть, если играют идеально
- Один игрок может выиграть или сыграть вничью, если он играет идеально (и если оба игрока играют отлично, то они всегда зашли в тупик)
Но что из этого действительно правильно, мы никогда не узнаем.
Ответ на вопрос - да: для шахмат должен быть идеальный алгоритм, по крайней мере, для одного из двух игроков.
Для игры в шашки было доказано, что программа всегда может выиграть или завязать игру. То есть, нет выбора ходов, которые один игрок может сделать, что заставит другого игрока проиграть.
Исследователи потратили почти два десятилетия, просматривая 500 миллиардов возможных позиций в шашках, что, кстати, все еще составляет бесконечно малую долю от числа шахматных позиций. Усилия по проверке включали лучших игроков, которые помогли программе проверки правил исследовательской программы в программное обеспечение, которое классифицировало шаги как успешные или неудачные. Затем исследователи запускают программу в среднем на 50 компьютерах в день. Несколько дней программа работала на 200 машинах. Пока исследователи следили за прогрессом и соответствующим образом настраивали программу. Фактически, Chinook победил людей, чтобы выиграть чемпионат мира по шашкам еще в 1994 году.
Да, вы можете решить шахматы, нет, вы не будете в ближайшее время.
Это не вопрос компьютеров, а только игра в шахматы.
Вопрос в том, существует ли надежная стратегия, чтобы никогда не проигрывать игру? Если такая стратегия существует, то компьютер, который знает все, всегда может использовать ее, и она больше не является эвристической.
Например, игра в крестики-нолики обычно ведется на основе эвристики. Но существует надежная стратегия. Что бы ни двигался противник, вы всегда найдете способ избежать проигрыша, если вы делаете это с самого начала.
Таким образом, вам нужно доказать, что такая стратегия существует или не существует для шахмат. Это в основном то же самое, просто пространство возможных ходов значительно больше.
Я очень поздно приду к этой теме, и вы уже поняли некоторые проблемы. Но, как бывший мастер и бывший профессиональный программист, я подумал, что могу добавить несколько полезных фактов и цифр. Существует несколько способов измерения сложности шахмат:
- Общее количество шахматных партий составляет примерно 10^(10^50). Это число невообразимо велико.
- Количество шахматных партий в 40 ходов или меньше составляет около 10^40. Это все еще невероятно большое количество.
- Количество возможных шахматных позиций составляет около 10^46.
- Полное дерево поиска в шахматах (число Шеннона) составляет около 10 123, исходя из среднего коэффициента ветвления 35 и средней продолжительности игры 80.
- Для сравнения, число атомов в наблюдаемой вселенной обычно оценивается в 10^80.
- Все финалы из 6 штук или меньше были сопоставлены и решены.
Мой вывод: хотя шахматы теоретически разрешимы, у нас никогда не будет денег, мотивации, вычислительной мощности или хранилища, чтобы когда-либо это делать.
Некоторые игры фактически были решены. Крестики-нолики - это очень простой способ создания ИИ, который всегда будет выигрывать или связывать. Недавно было решено и Connect 4 (и было показано, что это несправедливо по отношению ко второму игроку, поскольку из-за идеальной игры он проигрывает).
Шахматы, однако, не были решены, и я не думаю, что есть какие-либо доказательства того, что это честная игра (т. Е. Дает ли идеальная игра ничью). Говоря строго с теоретической точки зрения, шахматы имеют конечное число возможных конфигураций фигур. Следовательно, пространство поиска конечно (хотя и невероятно велико). Следовательно, существует детерминированная машина Тьюринга, которая могла бы отлично играть. Может ли кто-либо когда-либо быть построен, однако, это другой вопрос.
К 2040 году настольный компьютер за 1000 долларов сможет решить задачи проверки всего за 5 секунд (5х10^20 расчетов).
Даже при такой скорости 100 из этих компьютеров все равно понадобятся примерно 6,34 х 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, и даже она может возрасти быстрее, чем предполагалось.
Многое из этого зависит от того, есть ли у нас, как людей, стремление решать шахматы, но вычислительная мощь сделает это возможным примерно в это время (до тех пор, пока продолжается наш темп).
С другой стороны, игра Tic-Tac-Toe, которая намного, намного проще, имеет 2 653 002 возможных вычислений (с открытой доской). Вычислительная мощность для решения Tic-Tac-Toe примерно за 2,5 (1 миллион вычислений в секунду) секунд была достигнута в 1990 году.
Если двигаться в обратном направлении, то в 1955 году компьютер смог разгадать крестики-нолики примерно за 1 месяц (1 расчет в секунду). Опять же, это основано на том, что вы получите за 1000 долларов, если бы вы могли упаковать его в компьютер (настольного компьютера за 1000 долларов, очевидно, не существовало в 1955 году), и этот компьютер был бы предназначен для решения Tic-Tac-Toe.... который в 1955 году это было не совсем так. Вычисления были дорогостоящими и не использовались бы для этой цели, хотя я не верю, что есть какая-то дата, когда компьютерная игра в крестики-нолики считалась "решенной", но я уверен, что он отстает от фактической вычислительной мощности.
Кроме того, учтите, что 1000 долларов за 45 лет будут стоить примерно в 4 раза меньше, чем сейчас, поэтому гораздо больше денег может уйти на такие проекты, в то время как вычислительные мощности будут продолжать дешеветь.
На самом деле оба игрока могут иметь выигрышные стратегии в бесконечных играх без упорядочивания; Тем не менее, шахматы хорошо упорядочены. Фактически, из-за правила 50 ходов существует верхний предел количества ходов, которые может иметь игра, и, таким образом, существует только конечное число возможных игр в шахматы (которые можно перечислить, чтобы решить точно... теоретически, по крайней мере:)
Ваш конец аргумента подтверждается тем, как работают современные шахматные программы. Они работают таким образом, потому что слишком ресурсоемко кодировать шахматную программу, чтобы действовать детерминистически. Они не всегда будут работать таким образом. Возможно, что когда-нибудь шахматы будут решены, и если это произойдет, то, скорее всего, их решит компьютер.
Я думаю, что вы мертвы. Такие машины, как Deep Blue и Deep Thought, запрограммированы с помощью ряда предопределенных игр и хитроумных алгоритмов для разбора деревьев на концах этих игр. Это, конечно, драматическое упрощение. Всегда есть шанс "обыграть" компьютер по ходу игры. Под этим я подразумеваю движение, которое заставляет компьютер делать движение, которое не является оптимальным (что бы это ни было). Если компьютер не может найти наилучший путь до истечения срока для перемещения, он вполне может ошибиться, выбрав один из менее желательных путей.
Есть еще один класс шахматных программ, в которых используется реальное машинное обучение или генетическое программирование / эволюционные алгоритмы. Некоторые программы были разработаны и используют нейронные сети и др. Для принятия решений. В этом случае я мог бы предположить, что компьютер может совершать "ошибки", но все же в конечном итоге победит.
Об этом типе семейных врачей есть увлекательная книга Blondie24, которую вы можете прочитать. Речь идет о шашках, но это может относиться к шахматам.
Как шахматный программист 1970-х годов, у меня определенно есть мнение по этому поводу. То, что я написал около 10 лет назад, все еще в основном верно сегодня:
"Незаконченная работа и вызовы шахматным программистам"
Тогда я думал, что мы могли бы решить шахматы условно, если все сделано правильно.
Шашки были решены недавно (Yay, Университет Альберты, Канада!!!), но это было эффективно сделано Brute Force. Чтобы заниматься шахматами условно, нужно быть умнее.
Если, конечно, квантовые вычисления не станут реальностью. Если это так, шахматы будут решаться так же легко, как крестики-нолики.
В начале 1970-х в Scientific American произошла короткая пародия, которая привлекла мое внимание. Это было объявление о том, что игра в шахматы была решена русским шахматным компьютером. Он определил, что есть один идеальный ход для белых, который обеспечит победу с идеальной игрой с обеих сторон, и этот ход: 1. a4!
Шахматы - пример матричной игры, которая по определению имеет оптимальный результат (подумайте о равновесии по Нэшу). Если каждый из игроков 1 и 2 делает оптимальные ходы, ВСЕГДА будет достигнут определенный результат (будь то выигрыш в ничью, пока неизвестно).
Для справки, есть компьютеры, которые могут выиграть или сыграть в шашки. Я не уверен, можно ли сделать то же самое для шахмат. Количество ходов намного выше. Кроме того, все меняется, потому что части могут двигаться в любом направлении, а не только вперед и назад. Я думаю, что хотя я не уверен, что шахматы являются детерминированными, но существует слишком много возможных ходов для компьютера, чтобы в настоящее время определить все ходы за разумное количество времени.
Из теории игр, о которой идет речь в этом вопросе, ответ - да, в шахматы можно играть идеально. Игровое пространство известно / предсказуемо, и да, если бы у вас были квантовые компьютеры вашего внука, вы, вероятно, могли бы устранить всю эвристику.
Вы можете написать идеальный компьютер для игры в крестики-нолики сейчас на любом языке сценариев, и он будет отлично играть в режиме реального времени.
"Отелло" - это еще одна игра, в которую современные компьютеры могут легко играть безупречно, но памяти машины и процессору потребуется небольшая помощь
Шахматы теоретически возможны, но практически невозможны (в 2008 году)
i-Go сложен, его пространство возможностей выходит за рамки количества атомов во вселенной, поэтому нам может потребоваться некоторое время, чтобы создать идеальную машину i-Go.
Это прекрасно решаемо.
Есть 10^50 нечетных позиций. По моим расчетам, каждая позиция требует минимум 64 круглых байта для хранения (каждый квадрат имеет: 2 бита присоединения, 3 бита по частям). Как только они сопоставлены, позиции, которые являются контрэмами, могут быть идентифицированы, и позиции могут быть сравнены, чтобы сформировать отношение, показывая, какие позиции приводят к другим позициям в большом дереве результатов.
Тогда программе нужно только найти самые нижние только односторонние корни матов, если такая вещь существует. В любом случае, шахматы были довольно просто решены в конце первого абзаца.
Множество ответов здесь приводят важные теоретические моменты игры:
- Шахматы - это конечная, детерминированная игра с полной информацией о состоянии игры.
- Вы можете решить конечную игру и определить идеальную стратегию
- Однако шахматы настолько велики, что вы не сможете решить их полностью методом грубой силы
Однако эти наблюдения упускают важный практический момент: нет необходимости идеально решать полную игру, чтобы создать непобедимую машину.
На самом деле вполне вероятно, что вы могли бы создать непобедимую шахматную машину (то есть никогда не проиграете и всегда вызовете выигрыш или ничью) без поиска даже крошечной доли возможного пространства состояний.
Следующие методы, например, все значительно сокращают требуемое пространство поиска:
- Методы сокращения деревьев, такие как Alpha/Beta или MTD-f, уже значительно сокращают пространство поиска
- Предоставляемая выигрышная позиция. В эту категорию попадает множество концовок: вам не нужно искать KR против K, например, это доказанный выигрыш. С некоторой работой можно доказать еще много гарантированных побед.
- Почти определенные победы - для "достаточно хорошей" игры без каких-либо глупых ошибок (скажем, относительно ELO 2200+?) Многие шахматные позиции - это почти определенные победы, например, приличное материальное преимущество (например, дополнительный рыцарь) без компенсирующего позиционного преимущества. Если ваша программа может форсировать такую позицию и имеет достаточно хорошей эвристики для определения позиционного преимущества, она может смело предполагать, что она победит или, по крайней мере, сыграет вничью со 100% вероятностью.
- Эвристика поиска по дереву - при достаточно хорошем распознавании образов вы можете быстро сосредоточиться на соответствующем подмножестве "интересных" ходов. Вот как играют человеческие гроссмейстеры, так что это явно не плохая стратегия..... и наши алгоритмы распознавания образов постоянно улучшаются
- Оценка риска - лучшая концепция "рискованности" позиции позволит гораздо более эффективный поиск, сосредоточив вычислительную мощь на ситуациях, когда результат более неопределенный (это естественное расширение Quiescence Search)
С правильной комбинацией вышеупомянутых методов, я бы с уверенностью утверждал, что можно создать "непобедимую" шахматную игровую машину. Мы, вероятно, не так уж далеки от современных технологий.
Обратите внимание, что почти наверняка труднее доказать, что эту машину невозможно победить. Вероятно, это было бы что-то вроде гипотезы Реймана - мы были бы совершенно уверены, что он играет идеально и имели бы эмпирические результаты, показывающие, что он никогда не проигрывал (включая несколько миллиардов стрит-дро против себя), но на самом деле у нас не было бы возможности Докажите это.
Дополнительное примечание относительно "совершенства":
Я стараюсь не описывать машину как "совершенную" в теоретико-игровом смысле, потому что это подразумевает необычайно сильные дополнительные условия, такие как:
- Всегда выигрывать в любой ситуации, в которой возможно добиться выигрыша, независимо от сложности выигрышной комбинации. Будут ситуации на границе между выигрышем / ничьей, когда это чрезвычайно трудно рассчитать идеально.
- Использование всей доступной информации о потенциальном несовершенстве игры вашего оппонента, например, вывод о том, что ваш оппонент может быть слишком жадным и намеренно разыгрывает немного более слабую линию, чем обычно, на том основании, что у него больше шансов соблазнить оппонента на ошибку. Против несовершенных противников на самом деле может быть оптимальным сделать проигрыш, если вы считаете, что ваш оппонент, вероятно, не заметит принудительный выигрыш, и это дает вам более высокую вероятность выиграть самостоятельно.
Совершенство (особенно учитывая несовершенных и неизвестных противников) является гораздо более сложной проблемой, чем просто непобедимость.
если вы будете искать во всем пространстве все комбинации ходов игрока 1/2, то единственный ход, который компьютер выбирает на каждом шаге, основан на эвристике.
Там есть две конкурирующие идеи. Во-первых, вы ищите все возможные варианты, а во-вторых, вы выбираете на основе эвристики. Эвристика - это система для правильного предположения. Если вы просматриваете каждое возможное движение, то вы больше не угадываете.
Я нашел эту статью Джона МакКуарри, в которой упоминается работа "отца теории игр" Эрнста Фридриха Фердинанда Цермело. Это делает следующий вывод:
В шахматах либо белые могут принести победу, либо черные могут выиграть, либо обе стороны могут сыграть хотя бы ничью.
Логика кажется мне здоровой.
"Есть ли идеальный алгоритм для шахмат?"
Да, есть. Может быть, белые всегда побеждают. Может быть, это для черных всегда побеждать. Может быть, это для обоих всегда связывать по крайней мере. Мы не знаем что, и мы никогда не узнаем, но это, безусловно, существует.
Смотрите также
В вашем мысленном эксперименте есть две ошибки:
Если ваша машина Тьюринга не "ограничена" (в памяти, скорости, ...), вам не нужно использовать эвристику, но вы можете рассчитать оценку конечных состояний (выигрыш, проигрыш, ничья). Чтобы найти идеальную игру, вам нужно будет использовать алгоритм Minimax (см. http://en.wikipedia.org/wiki/Minimax), чтобы рассчитать оптимальные ходы для каждого игрока, что приведет к одной или нескольким оптимальным играм.
Также нет ограничений по сложности используемой эвристики. Если вы можете рассчитать идеальную игру, есть способ вычислить идеальную эвристику из нее. Если нужно, это просто функция, которая отображает шахматные позиции следующим образом: "Если я нахожусь в этой ситуации S, мой лучший ход - М".
Как уже указывали другие, это закончится тремя возможными результатами: белые могут добиться победы, черные могут добиться победы, один из них может вызвать ничью.
Результат идеальной игры в шашки уже был "вычислен". Если человечество не уничтожит себя раньше, когда-нибудь будет вычисление для шахмат, когда компьютеры разовьются достаточно, чтобы иметь достаточно памяти и скорости. Или у нас есть несколько квантовых компьютеров... Или пока кто-то (исследователь, шахматные эксперты, гений) не найдет некоторые алгоритмы, которые значительно уменьшают сложность игры. Для примера: какова сумма всех чисел от 1 до 1000? Вы можете либо вычислить 1+2+3+4+5...+999+1000, либо вы можете просто вычислить: N*(N+1)/2 с N = 1000; результат = 500500. Теперь представьте, что вы не знаете об этой формуле, вы не знаете о математической индукции, вы даже не знаете, как умножить или сложить числа,... Итак, возможно, что в настоящее время существует Неизвестный алгоритм, который в конечном итоге уменьшает сложность этой игры, и потребуется всего 5 минут, чтобы вычислить лучший ход с текущим компьютером. Возможно, было бы даже возможно оценить это как человека с ручкой и бумагой, или даже в вашем уме, если бы у вас было больше времени.
Итак, быстрый ответ: если человечество выживет достаточно долго, это всего лишь вопрос времени!
Математически шахматы были решены алгоритмом Minimax, который восходит к 1920-м годам (найден Борелем или фон Нейманом). Таким образом, машина Тьюринга действительно может играть в идеальные шахматы.
Однако вычислительная сложность шахмат делает его практически невозможным. Современные двигатели используют несколько улучшений и эвристики. Лучшие двигатели сегодня превзошли лучших людей с точки зрения игровой силы, но из-за эвристики, которую они используют, они могут не играть идеально, если им дается бесконечное время (например, столкновения хешей могут привести к неверным результатам).
Самым близким, что у нас есть в плане идеальной игры, являются настольные базы для эндшпиля. Типичный метод их генерации называется ретроградным анализом. В настоящее время все позиции до шести штук были решены.
Я знаю, что это немного затруднительно, но я должен поставить здесь свои 5 центов. Компьютер или человек могут в этом случае завершить каждую игру в шахматы, в которой он / она / она участвует, либо в выигрыше, либо в патовой ситуации.
Однако, чтобы достичь этого, вы должны точно знать каждый возможный ход и реакцию, и так далее, вплоть до каждого возможного результата игры, и чтобы визуализировать это или сделать легкий способ анализа этой информации, подумайте о это как карта ума, которая постоянно разветвляется.
Центральный узел будет началом игры. Каждая ветвь каждого узла будет символизировать движение, каждое из которых будет отличаться от его движений. Представление этого в этом поместье потребовало бы много ресурсов, особенно если вы делали это на бумаге. На компьютере это может занять сотни терабайт данных, так как у вас будет очень много повторяющихся ходов, если только вы не заставите ответвления вернуться.
Запоминать такие данные, однако, было бы неправдоподобно, если не невозможно. Заставить компьютер распознавать наиболее оптимальный ход, чтобы извлечь из (максимально) 8 мгновенно возможных ходов, было бы возможно, но не правдоподобно... так как этот компьютер должен был бы быть способен обрабатывать все ветви после этого движения, вплоть до заключения, подсчитайте все выводы, которые приводят к выигрышу или патовой ситуации, а затем воздействуйте на это количество выигрышных выводов против проигрышных выводов, и для этого потребуется ОЗУ, способное обрабатывать данные в террабайтах или даже больше! А с современными технологиями подобный компьютер потребовал бы больше, чем банковский счет 5 самых богатых мужчин и / или женщин в мире!
Так что после всего этого рассмотрения это могло быть сделано, однако, никто не мог сделать это. Для такой задачи потребовалось бы 30 самых ярких умов, живущих сегодня, не только в шахматах, но и в науке и компьютерных технологиях, и такую задачу можно было бы выполнить только на (давайте рассмотрим ее полностью в базовой перспективе)... крайне гипертонически суперский компьютер... который не мог существовать, по крайней мере, столетие. Будет сделано! Только не в этой жизни.
Я только на 99,9% убежден утверждением, что размер государственного пространства не позволяет надеяться на решение.
Конечно, 10^50 - это невероятно большое число. Назовем размер пространства состояний n.
Каково количество ходов в самой длинной игре? Поскольку все игры заканчиваются за конечное число ходов, существует такая граница, назовите ее m.
Исходя из начального состояния, вы не можете перечислить все n ходов в пространстве O(m)? Конечно, это занимает O(n) времени, но аргументы от размера вселенной прямо не обращаются к этому. O(м) пространство может даже не быть очень много. Для пространства O(m) вы не могли бы также отслеживать, во время этого обхода, ведет ли продолжение какого-либо состояния вдоль пути, по которому вы проходите, к EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin или BlackMayWinOrForceDraw? (Существует решетка, в зависимости от того, чья она очередь, аннотируйте каждое состояние в истории вашего обхода с помощью решетки).
Если я что-то не упустил, это алгоритм O(n) time / O(m) для определения того, в какую из возможных категорий попадают шахматы. Википедия приводит оценку возраста Вселенной примерно в 10 60 раз по Планку. Не вдаваясь в космологические аргументы, давайте предположим, что до жары / холода / любой смерти вселенной осталось примерно столько времени. Это оставляет нам необходимость оценивать один ход каждые 10^10 раз Планка или каждые 10^-34 секунд. Это невероятно короткое время (примерно на 16 порядков короче, чем самое короткое время, которое когда-либо наблюдалось). Давайте с оптимизмом скажем, что с супер-хорошей реализацией, работающей на вершине линейной существующей или предполагаемой не квантовой P-is-a-должной-подмножестве NP-технологии, мы могли бы надеяться оценить (взять на один шаг вперед классифицируйте результирующее состояние как промежуточное состояние (или одно из трех конечных состояний) с частотой 100 МГц (один раз каждые 10-8 секунд). Так как этот алгоритм очень распараллеливаемый, то нам нужно 10–26 таких компьютеров или около одного на каждый атом моего тела, а также возможность собирать их результаты.
Я полагаю, что всегда есть некоторая надежда на решение о грубой силе. Нам может повезти, и, изучая только один из возможных начальных ходов белых, оба выбирают тот, у которого размах намного ниже среднего, и тот, в котором белые всегда выигрывают или выигрывают или ничьи.
Мы могли бы также надеяться несколько уменьшить определение шахмат и убедить всех, что это по-прежнему морально та же самая игра. Действительно ли нам нужно, чтобы позиции повторялись 3 раза перед розыгрышем? Неужели нам нужно, чтобы убегающая группа продемонстрировала способность сбежать на 50 ходов? Кто-нибудь вообще понимает, что, черт возьми, происходит с правилом en passant?;) Если быть более серьезным, нужно ли нам на самом деле заставлять игрока двигаться (в отличие от ничьей или проигрыша), когда его или ее ход только для того, чтобы избежать проверки или тупиковая ситуация является захватом в пассивном режиме? Можем ли мы ограничить выбор фигур, на которые может быть повышена пешка, если желаемое повышение не для королевы не приводит к немедленной проверке или мату?
Я также не уверен в том, насколько разрешить каждому компьютеру доступ на основе хеш-функции к большой базе данных о поздних состояниях игры и их возможных результатах (которые могут быть относительно возможными на существующем оборудовании и с существующими базами данных конечных игр) может помочь в сокращении поиска раньше. Очевидно, что вы не можете запоминать всю функцию без хранения O(n), но вы можете выбрать большое целое число и запомнить, что многие конечные игры перечисляются в обратном порядке от каждого возможного (или даже не совсем доказуемого невозможного, я полагаю) конечного состояния.
Это может быть просто решаемо, но что-то беспокоит меня: даже если бы можно было пройти по всему дереву, все равно невозможно предсказать следующий ход противника. Мы должны всегда основывать наш следующий ход на состоянии оппонента и делать "лучший" ход доступным. Затем, основываясь на следующем состоянии, мы делаем это снова. Таким образом, наш оптимальный ход может быть оптимальным, если противник движется определенным образом. Для некоторых ходов противника наш последний ход мог быть неоптимальным.
Я просто не понимаю, как может быть "идеальный" шаг на каждом шагу.
Чтобы это было так, для каждого состояния [в текущей игре] должен быть путь в дереве, который ведет к победе, независимо от следующего хода противника (как в крестики-нолики), и у меня есть трудный время понять это.
Да, в математике шахматы классифицируются как определенная игра, это означает, что у них есть идеальный алгоритм для каждого первого игрока, это подтверждается даже для бесконечной шахматной доски, поэтому однажды, вероятно, квантовый ИИ найдет идеальную стратегию, и игра ушла
Подробнее об этом в этом видео: https://www.youtube.com/watch?v=PN-I6u-AxMg
Также есть квантовые шахматы, где нет математических доказательств того, что это решительная игра http://store.steampowered.com/app/453870/Quantum_Chess/
и вот вам подробное видео о квантовых шахматах https://chess24.com/en/read/news/quantum-chess
Конечно, есть только 10 из пятидесяти возможных комбинаций фигур на доске. Имея это в виду, чтобы играть на каждом этапе, вам нужно будет сделать меньше 10 до степени пятидесяти ходов (включая повторения, умножьте это число на 3). Итак, в силе ста ходов в шахматах меньше десяти. Просто выберите те, которые приводят к мату, и вы готовы идти
64-битная математика (= шахматная доска) и побитовые операторы (= следующие возможные ходы) - все, что вам нужно. Так просто. Грубая сила найдет самый лучший способ, как правило. Конечно, не существует универсального алгоритма для всех позиций. В реальной жизни расчет также ограничен во времени, тайм-аут остановит его. Хорошая шахматная программа означает тяжелый код (пройденные, сдвоенные пешки и т. Д.). Маленький код не может быть очень сильным. Открытие и окончание базы данных просто экономят время обработки, какие-то предварительно обработанные данные. Устройство, я имею в виду - ОС, многопоточность, среда, аппаратные средства определяют требования. Язык программирования важен. Во всяком случае, процесс разработки интересен.