Романтика искусственного интеллекта
Шрифт:
Глава 2
Вся жизнь – игра
Есть один вид человеческой деятельности в высшей степени интеллектуальный, но тем не менее, как оказалось, легко поддающийся алгоритмизации. Я имею в виду игру. Первые программы, эффективно играющие против человека, появились еще на заре развития вычислительной техники. Что интересно, штурм игры искусственным интеллектом пришелся на шахматы, каковые следует признать одной из наиболее сложных игр. И успех пришел достаточно быстро. Начало шахматных разработок можно отсчитывать от статьи Клода Шеннона, опубликованной еще в 1949 году, в которой рассмотрены основные проблемы игровых моделей. Шеннон впервые представил
Рис. 2.1. Клод Элвуд Шеннон
Клод Элвуд Шеннон (рис. 2.1) – американский инженер и математик, его работы являются синтезом математических идей с конкретным анализом чрезвычайно сложных проблем их технической реализации. Является основателем теории информации, нашедшей применение в современных высокотехнологичных системах связи. Шеннон внес огромный вклад в теорию вероятностных схем, теорию автоматов и теорию систем управления – области наук, входящие в понятие «кибернетика».
Первым проект Шеннона реализовал Тьюринг, но его программа, показав принципиальную приемлемость, тем не менее не смогла выиграть даже у слабого шахматиста. Первой если не сильной, то вполне играющей шахматной программой можно считать проект MANIAC–I, реализованный в 1956 году группой сотрудников Лос-Аламосской лаборатории. Эта программа наиболее точно соответствовала идее Шеннона, ей также не удалось показать выдающихся результатов, но одну из трех партий против слабого игрока она уже могла выиграть.
Дальнейшее развитие игровых программ было связано с двумя факторами: развитием математического аппарата игровых программ и ростом ресурсов вычислительных машин. На годы главной игрой, на которой упражнялись специалисты по искусственному интеллекту, остались шахматы, но со временем, с ростом доступности компьютеров, появлением большого числа программистов, руки стали доходить и до других игр. Сегодня в сети можно найти программы, играющие против человека в самые различные игры. Что же касается шахмат, то здесь были достигнуты просто великолепные результаты. Программы, использующие ресурсы персональных компьютеров, вполне успешно играют против хороших шахматистов, а гроссмейстеры-суперкомпьютеры смогли разделить шахматный пьедестал с гроссмейстерами-людьми.
В 1996 году состоялся первый матч Deep Blue с Гарри Каспаровым, в котором чемпион мира одержал победу со счетом 4:2. Deep Blue – это 6-процессорный суперкомпьютер, способный просчитывать 100 млн позиций в секунду. Через год состоялся матч-реванш с модернизированным 8-процессорным Deep Blue, считающим вдвое быстрее. Компьютер впервые победил лучшего шахматиста планеты со счетом 3,5:2,5. Пока компьютер не умел оценивать позицию, как человек, рост силы игры достигался по большей части за счет увеличения мощности «железа». Даже в качестве алгоритма перебора все еще использовался «брутфорс» (грубая сила), перебиралось как можно больше вариантов, но очень быстро. В 2003 году состоялся еще один матч Каспарова против компьютера – Deep Junior, работавшего на 4-процессорной системе с процессорами Pentium IV 1,9 ГГц и 3 Гб оперативной памяти. Junior стал первой программой, демонстрирующей «человечную» игру и способной пойти на жертву ради инициативы. Матч закончился вничью.
Компьютер против человека. Как это выглядит в принципе?
Для меня лично, когда я впервые увлекся проблемами искусственного разума, было самым большим открытием то, что моделирование интеллекта выполняется на базе очень простых принципов. Их техническая реализация может быть трудоемкой и даже очень трудоемкой, так как есть необходимость учитывать огромное количество деталей, и одной формулой процесс не опишешь. Но базовых идей очень немного, и их понимание не требует исключительной одаренности.
В этой главе мы рассмотрим принципы создания программ, играющих в интеллектуальные игры. Информации главы вполне достаточно, чтобы написать несложную программу, которая будет вполне прилично играть, при условии что вы – технически грамотный программист. Конечно, я не советую пытаться соревноваться с коллективами, пишущими программы, играющие в шахматы или го. Для начала можно попробовать реализовать игру попроще.
А теперь поговорим о том, как это работает. Базовые идеи разберем на шахматах, думаю, что хотя бы правила этой игры известны всем. Две вещи сомнения не вызывают: для принятия решения об очередном ходе необходимо уметь оценивать ситуацию, насколько она хороша или насколько она плоха, и необходимо уметь просчитывать течение игры на некоторое количество ходов вперед. Просчет игры заключается в построении всех возможных вариантов с точки зрения «грубой силы» или всех разумных вариантов, если есть хорошая эвристика.
Как эту работу выполняет человек
В решении задач искусственного интеллекта возможны два общих подхода. Можно попытаться реализовать человеческий способ мышления, и можно придумать метод, решающий ту же задачу, но иначе, не по-человечески. Примеров успешной реализации второго подхода масса. Например, движущийся по земле аппарат человек снабдил колесами, а не ногами. Наши летательные аппараты также принципиально отличаются от устройства птицы или летающего насекомого. А значит, и программа, играющая в шахматы или шашки, не обязана выглядеть по образцу и подобию своего создателя. Но тем не менее рассмотреть процесс игрового мышления человека полезно. На картинке (рис. 2.2) этюд мастера шахматной композиции Рихарда Рети.
Рис. 2.2. Этюд мастера Рети
По замыслу автора, белые, начиная, должны свести игру к ничьей. Попробуем провести человеческий анализ этой позиции. В чем здесь проблема? Позиция содержит две угрозы. С одной стороны, черная пешка рвется к последней горизонтали, и белый король ее уже не догонит. Аналогичная угроза есть и для черных, белая пешка через два хода может стать фигурой, но черный король успевает ее перехватить, а белый не успевает прийти на помощь своей пешке. То есть перед белым королем стоят две задачи: помощь своей пешке и перехват черной – не решаемые по отдельности.
Однако если две задачи не решаются каждая в отдельности, это не означает, что не решаема и их комбинация. Белый король имеет возможность, двигаясь по черной диагонали, одновременно приближаться к зоне перехвата черной пешки и к зоне поддержки своей. Если черные будут выполнять движение пешкой, то белый король успеет поддержать свою, а если черные решат уничтожить белую пешку, то белый король успеет перехватить черную. Таким образом, правильным решением для белых оказывается движение по диагонали.