В основе многих работ в сфере ИИ лежит важное различение между
двумя методами решения задач. Один метод называется алгоритмическим,
а другой - эвристическим. Алгоритмы обычно определяются как проце-
дуры, гарантирующие решение задач данного типа; эвристика есть набор
эмпирических правил или стратегий, которые в итоге действуют подобно
правилу большого пальца. Различие между этими методами можно проил-
люстрировать на примере шахматной задачи. Шахматы для компьюте-
ра - это игра, в которой во всякий данный момент существует ограничен-
ное количество ходов для каждого игрока. И на каждый из возможных
ходов противник может ответить также ограниченным набором ходов. Для
практических целей количество этих перестановок конечно - т.е. игра
должна закончиться выигрышем (поражением) или вничью. На Рис. 15.12
показана часть еще более разветвленного дерева ходов, возможных в шах-
матной партии. Конечно, нельзя изобразить возможные ходы для всей
партии, ибо такая диаграмма содержит около 1020 различных путей. Что-
бы представить себе это огромное число возможных ходов в шахматной
игре, вообразите пространство, необходимое для отображения всех этих
перестановок. Если все возможные пути закодировать в виде мельчайших
точек, они бы многократно заполнили все библиотеки мира! Тем не менее,
алгоритмический поиск, при котором исследуются все варианты, неизбеж-
но привел бы к ряду вариантов игры с выигрышем, проигрышем или ничь-
ей. Не только люди, но даже и самые сложные компьютеры из всех, кото-
рые только можно вообразить, неспособны воспользоваться этим мето-

Искусственный интеллект
527

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

Компьютер- Выше мы описывали, как при помощи оптимального сканера, работающе-
ные шахма- г(э с компьютером, можно было бы разобрать смысл простого паттерна
гы методом сравнения матриц (с. 506). Обсуждая анализ паттернов, мы выяс-
нили, что паттерны сложны и что модель распознавания паттернов чело-
веком, основанная только на сопоставлении матриц, не способна имитиро-
вать разнообразие, сложность и экономичность, характерные для челове-
ческой способности к распознаванию паттернов при кратком предъявле-
нии.

Если бы для распознавания каждого из разнообразных паттернов, встре-
чающихся в повседневной жизни, нужно было иметь по отдельной матри-
це. они переполнили бы емкость хранения даже самого большого компью-
тера. Но давайте выберем для сопоставления матриц умеренно простой
паттерн - что-нибудь среднее между опознанием вашей бабушки и счи-
тыванием стоимости фунта масла (код напечатан на упаковке). В шахма-
тах мы имеем как раз такие паттерны: простая сетка 8х8 попеременно
окрашенных клеток; ходы четко определяются (например, ладья может
ходить на любое количество клеток по вертикали или горизонтали при
условии, что на ее пути нет других фигур, пешка может ходить на одно
тле вперед, за исключением... и т.д.); ходы можно выбирать путем грубо-
го поиска, а количество перестановок конечно, хотя и огромно. При усло-
вии очень большого объема хранения и такого же запаса времени можно
для каждого хода определить вероятность, с которой он приближает вы-

Рис. 15.12. Часть дерева
вероятных ходов в шахмат-
ной партии.

Возмажныв
начальные
ходы Белых

Возможные
ответные
ходы Черных

Возможные
последующие
ответные
ходы Белых

.\1Ы1илсние и. интеллект - естественный и искусственный
528

Короли, Ферзи и кремниевые чипы

Для шахматных чемпионов это была плохая
неделя. Когда Анатолий Карпов отставал па
игру от Гари Каспарова на чемпионате мира
по шахматам, проходившем к концертном
зале Чайковского в Москве, в Редиссон Хол-
ле в Денвере происходило другое расстрой-
ство. Шахматная машина мирового класса и
стоимостью 14 миллионов долларов, супер-
компьютер Cray X-MP/48 при запуске про-
граммы под названием "Блиц" в Северо-аме-
риканском шахматном чемпионате проигры-
вал партию машине Hitech - сделанной на
заказ стойке из кремниевых чипов, соеди-
ненной с мини-компьютером Sun ценой
20000.

Если Карпов и Каспаров сидели лицом к
лицу. то эти два компьютера разделяло 750
миль: Cray находился в Мендота Хайте, штат
Миннесота, a Sun - в университете Карне-
ги-Меллона в Питтсбурге. Ходы компьюте-
ров посылались по телефонным линиям в
Денвер и транслировались на стационарную
шахматную доску. Но расстояние не повре-
дило игре. Мастер по шахматам Дэвид Леви
сказал: "В первый раз программа играла как
сильный игрок-человек".

Компьютеры стали сносно играть в шах-
маты с 1966 года, когда студент из МТИ Ри-
чард Гринблат написал программу МакХэк,
побившую Хуберта Дрейфуса, философа из
Беркли, который настаивал, что ни один ком-
пьютер никогда не. превзойдет 10-летнего ре-
бенка. Современные шахматные машины по-
беждают большинство случайных игроков, а
лучшие программы могут постоять за себя
против всех, кроме самых сильных мастеров13.

Подход шахматных компьютеров обычно
заключается ь грубой силе. Они просчиты-
вают от 4 до 8 ходов вперед, изучают наибо-
лее возможную игру и контригру и выбира-
ют ход, минимизирующий выигрыш оппонен-
та.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239