Может ли программа определить, играет ли другая программа в шахматы?

Question

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

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

Под «игрой в шахматы» я имею в виду некоторое представление шахматной доски и фигур, применение последующих ходов для черного и белого, происходящих из встроенного механизма шахматного ИИ.

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

---

(Правка) Что касается проблемы остановки, я могу решить ее следующим образом:

Загрузить программу на виртуальной машине, которая имеет N битов (жесткий диск, память и регистры процессора в целом). Эта виртуальная машина может принимать не более 2 ^ N различных состояний.

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

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

---

(Edit2) Кажется, существует некоторая двусмысленность относительно (не) конечности сканируемого исполняемого файла или (виртуальной) машины, на которой он запущен. Допустим, сканируемые исполняемые файлы могут занимать не более 1 ГБ (этого должно быть достаточно, поскольку большинство шахматных программ значительно меньше) и должны работать на ПК (или ВМ) с 10 ГБ оперативной памяти.

Наша теоретическая программа обнаружения шахмат может использовать произвольное количество овна.

Answer 1

Нет, нет такого алгоритма, который бы определял, играет ли исполняемый файл в шахматы.

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

При наличии компьютерной программы эта программа в конечном итоге завершается?

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

1. Взять в качестве входных данных другую компьютерную программу P.
2. Запустить программу P.
3. Если программа P завершается, сыграйте в шахматы.

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

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

Надеюсь, это поможет, и извините за ответ "нет"!

Answer 2

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

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

Однако выдобавил это ограничение, потому что вы хотели быть «практичным, а не теоретическим», так что вот вам еще одна практичность: перечислить все 256-битные программы (с миллиардом ПК, каждый из которых перечисляет миллиард программво-вторых) займет значительно больше времени, чем возраст вселенной.Таким образом, вы вряд ли можете себе представить, сколько времени потребуется для перечисления всех программ размером менее 1 ГБ (~ 1 000 000 000 бит).

Из-за этого на самом деле практичнее моделировать реальные компьютеры как машины Тьюринга, чемкак конечные автоматы;и в этой модели, как доказал @templatetypedef, это невозможно.

Answer 3

Нет.Это эквивалентно проблеме остановки.

Answer 4

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

Например, если вы спросите: «Существует ли кодировка ходов, при которой эта программа играет в шахматы?» затем голый интерпретатор Python играет в шахматы - в кодировке, которая требует ввода:

• играющая в шахматы программа Python плюс первый ход противника, если вы хотите, чтобы он играл черным
• программа на Python для игры в шахматы, если вы хотите, чтобы она играла белым

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