Стюарт Рассел - Совместимость. Как контролировать искусственный интеллект

Доказательство того, что проблема остановки неразрешима, очень изящно. Вопрос: возможна ли программа проверки циклов LoopChecker (Р, Х), которая для любой программы Р и любого входа Х верно определяет за конечный промежуток времени, остановится ли Р, примененная к Х, выдав результат, или будет выполняться вечно? Допустим, программа LoopChecker существует. Напишем программу Q, использующую LoopChecker как подпрограмму с самой Q и Х в качестве входа и выполняющую противоположное тому, что предсказывает LoopChecker (Q, Х). Тогда, если LoopChecker сообщает, что Q остановится, Q не останавливается, и наоборот. Таким образом, предположение, что LoopChecker существует, приводит к противоречию, следовательно, LoopChecker не существует.

Я говорю «как представляется», потому что на сегодняшний день утверждение, что класс неполиномиальных задач требует сверхполиномиального времени (принятое обозначение: P ≠ NP), остается недоказанным. После почти 50 лет исследований, однако, почти все математики и специалисты в области компьютерных наук убеждены в его истинности.

Записи Лавлейс о вычислениях содержатся по большей части в ее примечаниях к собственному переводу комментариев итальянского инженера по поводу машины Бэббиджа: L. F. Menabrea, «Sketch of the Analytical Engine invented by Charles Babbage», trans. Ada, Countess of Lovelace, in Scientific Memoirs , vol. III, ed. R. Taylor (R. and J. E. Taylor, 1843). Оригинальная статья Менабреа, написанная на французском языке на основе лекций, с которыми Бэббидж выступал в 1840 г., вышла в издании Bibliothèque Universelle de Genève 82 (1842).

Одна из ранних эпохальных статей о возможности искусственного интеллекта: Alan Turing, «Computing machinery and intelligence», Mind 59 (1950): 433–60.

Проект «Шейки» Стэнфордского исследовательского института описан в воспоминаниях одного из его руководителей: Nils Nilsson, «Shakey the robot», technical note 323 (SRI International, 1984). В 1969 г. был снят 24-минутный фильм «Шейки: эксперименты по обучению и планированию в робототехнике», вызвавший общенациональный интерес.

Книга, ознаменовавшая начало разработки современного, вероятностного ИИ: Judea Pearl , Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Morgan Kaufmann, 1988).

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

Полное описание см. в главе 2 кн.: Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach , 3rd ed. (Pearson, 2010).

Размер пространства состояний в StarCraft рассматривается в статье: Santiago Ontañon et al., «A survey of real-time strategy game AI research and competition in StarCraft», IEEE Transactions on Computational Intelligence and AI in Games 5 (2013): 293–311. Огромное количество ходов возможно, потому что игрок может перемещать все юниты одновременно. Число ходов снижается с введением ограничений относительно того, сколько юнитов или их групп могут быть перемещены одновременно.

О состязании человека и машины в StarCraft: Tom Simonite, «DeepMind beats pros at StarCraft in another triumph for bots», Wired , January 25, 2019.

AlphaZero описана в: David Silver et al., «Mastering chess and shogi by self-play with a general reinforcement learning algorithm», arXiv:1712.01815 (2017).

Оптимальные маршруты определяются с помощью А алгоритма и множества производных от него: Peter Hart, Nils Nilsson, and Bertram Raphael, «A formal basis for the heuristic determination of minimum cost paths », IEEE Transactions on Systems Science and Cybernetics SSC- 4 (1968): 100–107.

Статья, представившая программу Advice Taker и системы знания на основе логики: John McCarthy, «Programs with common sense», in Proceedings of the Symposium on Mechanisation of Thought Processes (Her Majesty’s Stationery Office, 1958).

Чтобы составить некоторое представление о значимости систем на основе знания, рассмотрим системы баз данных. База данных содержит четкие отдельные факты вроде местоположения моих ключей и личностей четырех моих друзей в Facebook. Системы баз данных не могут хранить общие правила, например правила игры в шахматы или юридическое определение британского гражданства. Они могут сосчитать, сколько людей по имени Алиса имеют друзей, которые носят имя Боб, но не способны определить, отвечает ли конкретная Алиса условиям предоставления британского гражданства, или приведет ли к победе определенная последовательность шахматных ходов. Системы баз данных не могут соединить два фрагмента знания, чтобы получить третий: они поддерживают функцию запоминания, но не мышления. (Действительно, многие современные системы баз данных дают возможность добавлять правила и использовать эти правила для получения новых фактов; в той мере, в которой они это делают, они являются системами на основе знания.) Хотя они представляют собой ограниченные версии систем на основе знания, системы баз данных лежат в основе большей части сегодняшней коммерческой деятельности и приносят сотни миллиардов долларов ежегодно.