Есть ли идеальный алгоритм для шахмат?

Ответ 1

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

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

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

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

Сделайте математику при открытии ходов. В то время как только около 20 шагов открытия, есть что-то вроде 30 или около того вторых ходов, поэтому к третьему ходу мы смотрим 360 000 альтернативных состояний игры.

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

Ответ 2

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

Прежде всего, мы должны помнить, что белые должны идти первым, и, возможно, это дает ему преимущество; возможно, это дает Черному преимущество.

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

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

Есть только три возможности:

• Белый всегда может побеждать, если он отлично играет.
• Черный всегда может побеждать, если он отлично играет.
• Один игрок может выиграть или выиграть, если он сыграет отлично (и если оба игрока играют отлично, то они всегда падают)

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

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

Ответ 3

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

Исследователи провели почти два десятилетия, пройдя через 500 миллиардов миллиардов возможных позиций шашек, что, кстати, по-прежнему представляет собой бесконечно малую долю числа шахмат. В шашки были включены лучшие игроки, которые помогли шагам в программе проверки программных программ в программное обеспечение, которое классифицировало ходы как успешные или неудачные. Затем исследователи позволяют программе работать в среднем по 50 компьютеров ежедневно. Несколько дней программа работала на 200 машинах. В то время как исследователи следили за прогрессом и соответственно подстраивали программу. Фактически, Чинук избил людей, чтобы выиграть чемпионат мира по шашкам еще в 1994 году.

Да, вы можете решить шахматы, нет, вы не скоро придете.

Ответ 4

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

Средний рабочий стол за тысячу долларов сможет решить шашки всего за 5 секунд к 2040 году (расчеты 5x10 ^ 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 х 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 возможных расчета (с открытой доской). В 1990 году была достигнута вычислительная мощность для решения Tic-Tac-Toe примерно в 2,5 (1 млн. Вычислений в секунду) секунд.

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

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

Ответ 8

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

Ответ 9

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

Ответ 10

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

Ответ 11

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

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

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

Ответ 12

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

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

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

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

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

Ответ 13

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

Ответ 14

Как программист на шахматы 1970-х годов, я определенно имею на это мнение. То, что я написал около 10 лет назад, по-прежнему остается в силе сегодня:

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

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

Шашки были решены недавно (Yay, Университет Альберты, Канада!!!), но это было эффективно сделано Brute Force. Чтобы сделать шахматы условно, вам нужно быть умнее.

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

В начале 1970 года в Scientific American была короткая пародия, которая привлекла мое внимание. Это было объявление о том, что игра в шахматы была решена российским шахматным компьютером. Он определил, что есть один идеальный ход для белых, который обеспечит победу с идеальной игрой с обеих сторон, и этот ход: 1. a4!

Ответ 15

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

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

Ответ 16

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

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

См. также

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

Ответ 17

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

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

Мне кажется, что логика кажется мне интересной.

Ответ 18

Здесь много ответов дают важные теоретико-игровые моменты:

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

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

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

Следующие методы, например, все значительно уменьшают требуемое пространство поиска:

• Методы обрезки деревьев, такие как Alpha/Beta или MTD-f, уже значительно уменьшают пространство поиска
• Предоставить выигрышную позицию. В эту категорию входит множество окончаний: вам не нужно искать KR vs K, например, это проверенная победа. С некоторыми работами можно доказать еще много гарантированных побед.
• Почти определенные победы - для "достаточно хорошей" игры без каких-либо глупых ошибок (скажем, об ELO 2200+?), многие шахматные позиции почти наверняка выигрывают, например, достойное материальное преимущество (например, дополнительный рыцарь) без компенсирующего позиционного преимущества, Если ваша программа может форсировать такую ​​позицию и обладает достаточно хорошими эвристиками для определения позиционного преимущества, она может с уверенностью предположить, что она выиграет или, по крайней мере, нарисует со 100% -ной вероятностью.
• Эвристика поиска дерева - с достаточно хорошим распознаванием образов, вы можете быстро сосредоточиться на соответствующем подмножестве "интересных" ходов. Вот как играют гроссмейстеры, так что это явно не плохая стратегия..... и наши алгоритмы распознавания образов постоянно улучшаются.
• Оценка риска - лучшая концепция "рискованности" позиции позволит значительно более эффективный поиск, сосредоточив вычислительную мощность на ситуациях, когда результат более неопределен (это естественное расширение Quiescence Search)

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

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

Дополнительная заметка о "совершенстве":

Я стараюсь не описывать машину как "идеальную" в теоретико-игровом смысле, потому что это подразумевает необычно сильные дополнительные условия, такие как:

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

Совершенство (особенно с учетом несовершенных и неизвестных противников) - гораздо сложнее, чем просто быть непобедимым.

Ответ 19

Совершенно разрешимо.

Есть 10 ^ 50 нечетных позиций. Каждая позиция, по моим расчетам, требует хранения не менее 64 байтов (каждый квадрат имеет: 2 бита принадлежности, 3 бита). После их сопоставления позиции, которые могут быть идентифицированы, могут быть идентифицированы, а позиции можно сравнить, чтобы сформировать взаимосвязь, показывая, какие позиции приводят к другим позициям в большом дереве результатов.

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

Ответ 20

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

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

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

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

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

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

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

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

Ответ 21

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

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

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

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

Ответ 22

В вашем мысленном эксперименте есть две ошибки:

• Если ваша машина Тьюринга не "ограничена" (в памяти, скорости,...), вам не нужно использовать эвристику, но вы можете рассчитать оценку конечных состояний (выигрыш, потеря, ничья). Чтобы найти идеальную игру, вам просто нужно будет использовать алгоритм Minimax (см. http://en.wikipedia.org/wiki/Minimax), чтобы вычислить оптимальные ходы для каждого игрока, что приведет к одной или нескольким оптимальным играм.

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

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

Результат идеальных игр с шашками уже "вычислен". Если человечество не уничтожит себя раньше, в какой-то день будет также вычисление для шахмат, когда компьютеры развились достаточно, чтобы иметь достаточно памяти и скорости. Или у нас есть несколько квантовых компьютеров... Или кто-то (исследователь, шахматные эксперты, гений) найдет некоторые алгоритмы, которые значительно уменьшают сложность игры. Чтобы привести пример: Какова сумма всех чисел от 1 до 1000? Вы можете рассчитать 1 + 2 + 3 + 4 + 5... + 999 + 1000, или вы можете просто вычислить: N * (N + 1)/2 с N = 1000; result = 500500. Теперь представьте, что вы не знаете об этой формуле, вы не знаете о математической индукции, вы даже не знаете, как умножить или добавить числа,... Таким образом, возможно, что есть неизвестный алгоритм, который в конечном итоге снижает сложность этой игры, и для вычисления наилучшего движения с текущего компьютера потребуется всего 5 минут. Возможно, было бы даже возможно оценить его как человека с ручкой и бумагой или даже в вашем сознании, учитывая еще некоторое время.

Итак, быстрый ответ: если человечество выживет достаточно долго, это просто вопрос времени!

Ответ 23

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

Я просто не понимаю, как может быть "идеальный" ход на каждом шагу.

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

Ответ 24

Математически шахматы были решены с помощью Minimax algorithm, который восходит к 1920-м годам (или найденному Борелом или фон Нейманом). Таким образом, машина turing действительно может играть в совершенные шахматы.

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

Ближайшим, что мы имеем в настоящее время в плане идеальной игры, являются endgame tablebases. Типичный метод их создания называется ретроградным анализом. В настоящее время все позиции с шестью частями решены.

Ответ 25

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

Ответ 26

64-битная математика (= шахматная доска) и побитовые операторы (= следующие возможные ходы) - это все, что вам нужно. Так просто. Обычно Brute Force найдет самый лучший способ. Конечно, универсального алгоритма для всех позиций нет. В реальной жизни расчет также ограничен во времени, тайм-аут остановит его. Хорошая шахматная программа означает тяжелый код (пройденный, удвоенные пешки и т.д.). Маленький код не может быть очень сильным. Базы данных для открытия и окончания эстафеты просто сохраняют время обработки, некоторые предварительно обработанные данные. Устройство, я имею в виду - ОС, потоковая связь, среда, оборудование определяют требования. Язык программирования важен. Во всяком случае, процесс разработки интересен.