Семь главных игр в истории человечества. Шашки, шахматы, го, нарды, скрабл, покер, бридж
Шрифт:
Так как же играет компьютер? Представьте, что вы стоите у подножия очень высокого дерева и смотрите вверх. Дерево – это совокупность всех возможных вариантов будущего игры. Ствол представляет собой ваш следующий ход, большой сук – какой-то возможный ход после этого, ветви поменьше – дальнейшие ходы, а бесчисленные мелкие веточки и листья наверху – продолжение возможных ходов в отдаленном будущем игры – эндшпили.
Люди смотрят на дерево снизу вверх и вспоминают о деревьях, на которые забирались, которые видели и о которых им раньше рассказывали друзья. У нас есть интуитивное, врожденное понимание того, какие ветви могут легко выдержать наш вес, а какие прогнутся, мы также знаем, какие веточки, судя по всему, крепкие. Мы помним,
А вот компьютеры не обладают такой интуицией в отношении дерева. Однако они способны добираться до всех частей кроны, причем очень быстро, точно колония муравьев. Это называется поиском. В каждой точке дерева, куда они попадают, муравьи производят небольшие вычисления, определяя качество этого места и присваивая ему баллы. Это называется оценкой. Перед тем как сделать ход в игре вроде шашек, компьютерные муравьи могут обежать миллионы мест на дереве, накапливая вычисления. Если какой-то путь наверх набирает более высокую оценку, компьютер направится именно туда. Компьютеры забираются на деревья – то есть играют в игры – с помощью поиска и оценки, поиска и оценки, поиска и оценки.
И поиск, и оценка – серьезные технические задачи. Начать с того, что в шашках существует 500 995 484 682 338 672 639 возможных позиций, то есть около 500 миллиардов миллиардов. Шеффер приводит такую аналогию: если бы Тихий океан высох и вам нужно было бы наполнить его с помощью маленькой чашки, то количество вливаемых порций было бы равно количеству возможных позиций в этой игре. Или такую: если бы площадь всей суши на нашей планете представляла совокупность возможных позиций в шашках, то каждой позиции соответствовала бы примерно одна сотая квадратного сантиметра. Таким образом, эффективность поиска имеет важнейшее значение. Если действовать путем простого перебора и смотреть на каждую из позиций в течение тысячной доли секунды примерно так, как машина Сэмюэла, то время, необходимое для просмотра их всех, превысило бы возраст Вселенной.
Оценка каждой позиции, когда мы на нее смотрим, – непростая задача. В шашках определенные особенности позиции являются желательными: хорошо иметь больше шашек, больше дамок, контролировать центральную часть доски и так далее. Есть и нежелательные особенности: расположение шашек по краям доски, незащищенная последняя горизонталь и так далее. Фокус в том, чтобы преобразовать всю эту мозаику особенностей и их сложные нелинейные математические взаимодействия в одно-единственное число, которое будет понятно вашей компьютерной программе.
Марион Тинсли опирался на интуицию и расчет, а также на способность осмысливать и усваивать опыт игры в шашки, накопленный теми, кто играл до него. Он мог взглянуть практически на любое дерево и найти оптимальный путь к его вершине с небольшими затратами энергии, характерными для человеческого мозга. Но в 1970 году, когда он после перерыва возобновил шашечную карьеру, муравьи уже размножались и набирали скорость.
Может возникнуть вопрос: зачем специалисту по вычислительным системам тратить свое дорогое время, энергию и деньги грантодателей на создание компьютерных программ для настольных игр? Специалисты обычно дают один из следующих дежурных ответов: игры – это испытательные стенды; игры обеспечивают контрольные задачи для оценки эффективности систем искусственного интеллекта; игры позволяют легко сравнивать результативность компьютера с результативностью человека; игры – это упрощенные модели аспектов «реального мира». Или (если специалист чуть более откровенен): игры – это увлекательно. Такие ответы хороши, но ни один из них не является до конца правдивым.
Истинная мотивация специалиста по вычислительным системам, разрабатывающего ИИ для игр, не слишком отличается
Шеффер, который родился в Торонто в 1957 году, с детства играл в разные игры. В книге «На шаг впереди» (One Jump Ahead), посвященной его шашечной одиссее и созданию игровой компьютерной программы, он живо рассказывает о своем детском увлечении шахматами с их «фигурами воинов короля Артура, отстаивающими королевскую честь» и «тщательно срежиссированным балетом». Шеффер отмечал сходство между своим пристрастием к этой игре и любовью, испытываемой знатоками «к изящным искусствам или музыке». В 16 лет он завоевал титул мастера спорта по шахматам. В Торонтском университете Шеффер сначала изучал математику, потом занялся физикой, а затем переключился на компьютерные науки, поверив в то, что даже если сам он никогда не станет чемпионом мира по шахматам, ему, возможно, удастся написать программу, которая сумеет завоевать этот титул. Он учился программированию, анализируя существующую шахматную программу, написанную на фортране, одном из первых языков программирования. В Университете Ватерлоо Шеффер тратил так много времени на программирование, стремясь научить компьютеры играть, что «запорол» свою диссертацию. Но это не имело значения. Он оформил в виде диссертации работу в области шахмат, дал ей академически корректное название «Эксперименты в области поиска и знаний» (Experiments in Search and Knowledge) и защитился в 1986 году.
Два года спустя, уже работая преподавателем в Университете провинции Альберта, он решил заняться шашками. По его представлениям, это не должно быть чем-то сложным (так же до него думал Сэмюэл). В конце концов, это всего лишь шашки. Шеффер не испытывал любви к этой игре, и его не трогали таящиеся в ней стратегические сокровища, привлекавшие Тинсли. В основе его интереса лежали приземленные побуждения. «Я мог бы привести множество научно обоснованных причин, но глубоко в душе у меня был настоящий ответ, – писал он. – Я мог победить». Шашки стали главным в жизни Шеффера.
Работа над системой, первоначально носившей название Beast, началась 2 июня 1989 года. Шеффер быстро обзавелся помощниками, подрядив двоих коллег, которые как-то за обедом нечаянно натолкнули его на идею заняться шашками. Он обратился к работам Сэмюэла, написанным три десятилетия назад. Кроме того, он разместил сообщение – по сути, крик о помощи – в конференции Usenet, посвященной шахматам (конференции, посвященной шашкам, не существовало).
Содержание сообщения было следующим: «Требуется функция оценки или рекомендации по ее разработке».
Единственный ответ пришел из Радиоастрофизической обсерватории Доминиона (Британская Колумбия) от Нормана Трелора, который на тот момент был безработным. Шеффер пригласил его в Эдмонтон. Трелор, «низкорослый, типичный англичанин в скромном костюме», внимательно прочитал работу Сэмюэла и заявил, что в ней есть серьезные изъяны, но он знает, как их исправить. Как оказалось, Трелор, в отличие от Шеффера и Сэмюэла, отлично играл в шашки.
Система Beast получила новое название – Chinook. Шеффер взял на себя разработку ее поисковой функции, а Трелор – алгоритм оценки. Они были готовы построить машину, способную взбираться на дерево шашек лучше, чем любой человек, даже сам Тинсли.