Таким образом, легендарная программа Сэмюэла является прародителем не только разумного вида, ИИ, но также и его наиболее современной боковой ветви, ИЖ, Искусственной жизни. Хотя эта программа и легендарна, сегодня лишь немногие знакомы с примечательными подробностями ее появления, многие из которых заслуживают широкой известности
287. Первая программа игры в шашки была написана Сэмюэлем в 1952 году для IBM 701, но способная к обучению версия появилась лишь в 1955‐м и работала на IBM 704; более поздняя версия была написана для IBM 7090. Сэмюэл нашел изящный способ закодировать любое возможное положение фишек в шашках с помощью четырех тридцатишестибитных «слов», а любой ход – посредством простого арифметического действия с этими словами. (В сравнении с современными чрезмерно расточительными компьютерными программами объемом в мегабайты, простейшая программа Сэмюэла была микроскопической – подлинно «низкотехнологичным» геномом, состоящим менее чем из шести тысяч строк кода – однако в то время ему приходилось писать машинным кодом, ибо дни языков программирования еще не настали.) Решив проблему перевода процесса простой игры в шашки в «понятный» компьютеру вид, он встал перед поистине трудной задачей: как сделать так, чтобы компьютерная программа оценивала ходы и при каждом удобном случае могла выбрать наилучший (или, по крайней мере, один из лучших)?
Как работала бы эффективная оценочная функция? У некоторых простейших игр наподобие крестиков-ноликов есть фактически осуществимые алгоритмические решения. Один из игроков обязательно победит или сыграет вничью, и наилучшую стратегию можно просчитать за обозримый период времени. Шашки – совсем другая игра. Сэмюэл указывал, что в пространстве возможных партий в шашки порядка 1040 точек выбора, «и если принимать три решения в миллимикросекунду, все равно потребуется 1021 веков, чтобы все их рассмотреть»
288. Хотя современные компьютеры в миллионы раз быстрее, чем неуклюжие гиганты времен Сэмюэла, они все еще не способны приблизиться к решению этой задачи путем обстоятельного прямолинейного перебора вариантов. Пространство поиска Чрезвычайно велико, и потому следует применить «эвристический» метод: полуразумные, близорукие демоны должны безжалостно подрезать ветви раскидистого древа возможных ходов, оставив для рискованного, полного случайностей исследования лишь крошечную его часть.
Эвристический поиск – одна из ключевых идей Искусственного интеллекта. Можно даже определить задачу данной исследовательской области как создание и исследование эвристических алгоритмов. Однако в информатике и математике существует и традиция, противопоставляющая эвристические и алгоритмические методы: эвристические методы рискованны и, в отличие от алгоритмов, не гарантируют результатов. Как нам разрешить подобное «противоречие»? Противоречия вовсе нет. Как и все алгоритмы, эвристические алгоритмы – механические процедуры, которые обязательно достигают своей цели, но в их случае цель предполагает поиск, который вовсе не обязательно приведет к результатам! Нет гарантии, что они что-нибудь отыщут, или, по крайней мере, они далеко не обязательно отыщут то, что искали, в отпущенное на это время. Но, подобно хорошо организованным состязаниям в мастерстве, удачные эвристические алгоритмы обычно в обозримое время приводят к весьма интересным, надежным результатам. Дело это рискованное, но в случае хорошего алгоритма шансы весьма высоки. За них можно поручиться головой
289. Неспособность осознать тот факт, что алгоритмы могут быть эвристическими процедурами, сбила с толку немало критиков Искусственного интеллекта. В частности, из‐за нее обманулся Роджер Пенроуз, взгляды которого станут темой пятнадцатой главы.
Сэмюэл видел, что Чрезвычайно большое пространство шашечных партий было бы возможно исследовать лишь методом, предполагающим рискованное обрубание ветвей древа поиска. Но как подойти к созданию обрубающих и отбирающих демонов, которые могли бы это сделать? Какие легко программируемые правила прекращения поиска или функции оценки с наибольшей вероятностью позволят вести поиск в правильных направлениях? Сэмюэл искал надежный алгоритмический метод поиска и делал это эмпирически, начав с разработки способов механизации всех очевидных практических правил, какие только приходили ему на ум. В их список, разумеется, входили «семь раз отмерь» и «на ошибках учатся», а следовательно, система должна была обладать памятью для хранения информации о полученном опыте. Прототип довольно успешно развивался за счет «зубрежки»: просто накапливая память о тысячах ситуаций, с которыми он уже сталкивался и о чьих последствиях знал. Но эффективность зубрежки ограничена; когда программа Сэмюэла накопила в ближайшем окружении миллионы слов описаний предшествующего опыта и начала испытывать проблемы с упорядочением и поиском информации, эффективность стратегии резко снизилась. Когда требуется большая эффективность или универсальность, приходится прибегать к иной конструкторской стратегии: обобщению.
Вместо того чтобы пытаться самостоятельно набрести на нужную процедуру, Сэмюэл попытался сделать так, чтобы ее отыскал компьютер. Он хотел, чтобы компьютер сам разработал для себя оценочную функцию – математическую формулу (многочлен), присваивающую положительное или отрицательное число каждому оцениваемому ходу, так чтобы в целом соблюдалось правило: чем выше число, тем лучше ход. Многочлен должен был состоять из многих одночленов, каждый из которых бы увеличивал или уменьшал общую сумму, умноженных на тот или другой коэффициент и учитывающих разные другие обстоятельства, но Сэмюэл понятия не имел, какого рода сочетание элементов будет действенным. Он составил примерно тридцать восемь фрагментов программы – «слагаемых» – и поместил их в «библиотеку». Некоторые из слагаемых были интуитивно значимыми (например, те, что присуждали очки за увеличение подвижности или потенциально «съеденные» шашки противника), но другие были взяты более-менее наобум (например, ДАМБА: «параметру засчитывается 1 очко за каждую линию из неподвижных шашек, занимающих три соседние клетки по диагонали»). В каждый момент времени шестнадцать слагаемых сочетались, образуя рабочий геном активного многочлена, тогда как прочие оставались в библиотеке. После множества вдохновенных догадок и еще более вдохновенной наладки и настройки Сэмюэл разработал правила, позволяющие исключать участников из состязания, и понял, как сделать так, чтобы котел бурлил, а поиск методом проб и ошибок с высокой вероятностью приводил к составлению удачных комбинаций слагаемых и коэффициентов (и такие комбинации распознавались). Программа была разделена на Альфу (быстро изменяющуюся новаторскую часть) и Бету (ее консервативную соперницу, воспроизводящую стратегию, приведшую к победе в последней игре). «После каждого хода Альфа обобщает свой опыт, изменяя коэффициенты в своем оценочном многочлене и заменяя слагаемые, оказавшиеся несущественными, новыми параметрами, взятыми из листа ожидания»
290.
