Министерство образования и науки российской федерации федеральное агентство по образованию санктпетербургский государственный университет
 Скачать 1.41 Mb.
|
|
локального поиска. Пусть первоначально Тверь 276+716+(161) =1153 С.Петербург 276+476+ (634) = 1386 Рига 276+(839) =1115 Хельсинки 100+(897) =997 С.Петербург 313+(634) =947 Таллин Хельсинки 276+377+(897) =1550 Москва 276+(839) =1115 7 8 5 3 1 6 4 2 6 3 4 7 8 5 2 1 37 ферзи расставлены каждый на своей вертикали произвольно следующим образом: В каждой свободной клетке показано значение эвристической функции при условии перемещения на эту клетку ферзя в пределах вертикали. Рамкой обведены клетки с минимальным значением эвристики. Таким образом, имеется 8 вариантов равноценных перемещений. После любого из них все эвристики пересчитываются и определяются кандидаты на следующее перемещение. Через пять ходов значение эвристики может достигнуть единицы, что очень близко к решению. Эта разновидность поиска называется жадным локальным поиском. Этот поиск часто показывает хорошую производительность, но и заходит в тупик по следующим причинам (рис.2.6): 18 14 14 15 17 18 14 14 13 18 14 17 16 13 13 12 15 13 15 15 12 16 12 14 14 14 14 13 15 13 15 18 15 17 14 12 14 13 16 12 12 14 12 16 14 14 14 16 14 16 16 18 16 14 15 12 Локальный максимум Плато 38 Рис. 2.6. Локальный максимум и плато 1. Локальные максимумы. Преодолеть их локальный поиск не в состоянии. 2. Плато. Область, в которой эвристика не меняется от хода к ходу. Для устранения недостатков используются следующие модификации локального поиска: движение в сторону (разрешение на определенное число ходов при неизменной или ухудшающейся эвристике); стохастический поиск с восхождением к вершине (выбор случайным образом одного из вариантов восхождения к вершине); поиск с восхождением к вершине и перезапуском. Каждая из разновидностей поиска, естественно, требует увеличенного числа локальных итераций, но радикально ускоряет общее движение к цели. Так, поиск с восхождением к вершине и перезапуском для варианта с тремя миллионами ферзей позволяет находить решение меньше, чем за минуту. Еще одной из разновидностей локального поиска является генетический алгоритм. Основными этапами алгоритма, обуславливающими его название, являются отбор, скрещивание и мутации. В задаче о восьми ферзях этот алгоритм может использоваться следующим образом: 1. Выбираются позиции с лучшими значениями эвристик (отбор). 2. Доска «разрезается» по вертикали или по горизонтали, и части доски от разных позиций соединяются вместе (скрещивание). 3. В полученные новые комбинации вносятся случайные изменения (мутации). 4. Если полученная позиция хуже предыдущих, она отбрасывается, если лучше, запоминается (отбор). 5. Из имеющихся лучших позиций все повторяется с п.2. Генетические алгоритмы широко используются при решении оптимизационных задач, хотя до сих пор не ясно, вызвана их популярность высокой эффективностью или эстетической привлекательностью и сходством с теорией эволюции Дарвина. 2.4. Поиск в условиях противодействия В предыдущих задачах сложность нахождения решения определялась только размерностью пространства состояний. Существует класс задач, в которых присутствует элемент неопределенности. К ним относятся все игровые задачи. Мы не будем рассматривать шахматы (оцените сами комбинаторную сложность на первые 40 ходов, коэффициент ветвления на первом ходе 20), а вернемся к игре в спички. На первый взгляд здесь то же самое дерево решений. Игрок и его противник имеют 3 варианта хода на каждом этапе. Проблема заключается в том, что если мы выбрали ветвь дерева, которая приводит нас к победе, то это никак не устраивает противника, и он вовсе не будет двигаться по этой ветви, а примет все меры, чтобы не дать нам выиграть. 39 Так, показанная на рисунке цепочка 5 – 3 – 0 спичек нас устраивает (узлы отображают число спичек, остающееся после сделанного хода), но противник так никогда не будет ходить, а возьмет вместо трех спичек две, что приведет к нашему проигрышу. Чтобы оценить целесообразность того или иного хода, присвоим нашей победе значение 1, а победе противника – значение 0. В таком случае наша стратегия заключается в том, чтобы максимизировать результат, а стратегия противника – его минимизировать. Назовем для ясности противника – МИН, а себя – МАКС. Спускаясь по дереву решений, мы можем дать оценку каждому узлу на самом нижнем уровне (показан фрагмент дерева). Выигрыш МАКСА (1) показан светлой заливкой, выигрыш МИНА (0) – темной. Предполагая, что оба игрока действуют в своих интересах разумно, мы можем дать оценку каждому ходу игроков на каждый уровень выше, а именно: из всех вариантов ходов МИН предпочтет те, которые дадут оценку 0, а МАКС – ходы, дающие оценку 1. Таким образом, оценка каждого хода МАКСА будет равна минимуму оценок ответных ходов МИНА и наоборот, оценка каждого хода МИНА будет равна максимуму оценок ответных ходов МАКСА. 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 МАКС МАКС МИН 6 4 5 3 2 1 3 3 1 4 2 МАКС 2 5 3 4 1 2 2 3 1 7 2 1 2 2 3 1 МИН 1 2 1 1 2 1 1 1 МИН 2 1 1 1 1 1 2 1 1 1 1 1 1 МИН 5 3 4 2 1 0 2 2 1 0 3 1 Ход игрока Ход противника 40 Данный алгоритм получил название алгоритм минимакса или минимаксный алгоритм. Легко видеть, что оценки по минимаксу являются пессимистическими для каждого из игроков и, следовательно, гарантируют успешный результат. В общем случае минимаксный алгоритм состоит из следующих шагов: 1. Выбор шкалы оценок исходов игры. 2. Спуск по дереву и присвоение оценок конечным состояниям. 3. Последовательное присвоение оценок родительским узлам: для МИНА – максимальной из дочерних, для МАКСА – минимальной. 4. После присвоения значения начальной позиции можно начинать делать ходы. Очевидным недостатком минимаксного алгоритма является его трудоемкость, поскольку необходимо выполнить обход всего дерева. Модификацией данного алгоритма, существенно укорачивающей его сложность является альфа-бета отсечение. Рассмотрим еще раз тот же фрагмент, теперь уже с позиции МАКСА, цель которого максимизировать результат. Спускаясь по дереву вглубь по левым ветвям, мы можем убедиться, что ход МАКСА 7 – 6 (взятие одной спички при семи в наличии) дает возможность МИНУ выиграть ходом 6 – 5. А поскольку оценка хода МАКСА определяется минимумом оценок возможных ответов МИНА, спускаться по соседним ветвям 6 – 4 и 6 – 3 нет необходимости и можно сразу переходить к спуску по ветви 7 – 5. 1 0 0 1 1 0 0 0 1 1 0 1 1 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 МАКС МАКС МИН 6 4 5 3 2 1 3 3 1 4 2 МАКС 2 5 3 4 1 2 2 3 1 7 2 1 2 2 3 1 МИН 1 2 1 1 2 1 1 1 МИН 2 1 1 1 1 1 2 1 1 1 1 1 1 МИН 41 И наоборот, если мы видим, что ход МАКСА 7 – 5 имеет оценку 1, нам нет необходимости проверять ветвь 7 – 4. Эффективность альфа-бета отсечения существенно зависит от порядка проверки узлов. Если бы мы вначале проверили ход 7 – 5, то нам бы не пришлось проверять ход 7 – 6. Это означает, что спуск по дереву целесообразно начинать с наиболее перспективных ходов. Разумеется, это возможно только если мы располагаем такой информацией. 2.5. Шахматные программы Алгоритм минимакса даже при использовании альфа-бета отсечения все же требует спуска до терминального состояния по многим ветвям, следовательно, его применимость сильно ограничена. Иными словами, на практике он не используется, за исключением совсем простых случаев. Более практичным является применение эвристических оценок каждой позиции без спуска до нижних листов дерева. Такой подход используется, например, в шахматных программах, где шахматистами давно отработана методика оценки как отдельных фигур, так и позиций в целом. Так, пешка имеет стоимость 1, конь или слон – 3, ладья – 5, ферзь – 9. Оцениваются также такие характеристики, как безопасность короля, хорошая пешечная структура и т.д. Таким образом, каждый ход может быть сразу оценен. Это не значит, что можно ограничиться глубиной поиска в один ход. Хорошая позиция может быть достигнута через 5 или 8 ходов. Модификация альфа-бета отсечения в этом случае заключается в том, чтобы ограничить верхнее значение оценки альфа (по принципу «от добра добра не ищут») и нижнее значение бета (минимально допустимое временное ухудшение позиции). Здесь все же всегда есть риск пропустить отличный ход или наоборот, «зевнуть». Более надежный подход заключается в использовании 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1 МАКС МАКС МИН 6 5 3 4 2 МАКС 5 3 4 1 2 2 3 1 7 2 1 2 2 3 1 МИН 1 2 1 1 2 1 1 1 МИН 2 1 1 1 1 1 1 МИН 42 ранее рассмотренного итеративного углубления в пределах отведенного времени. В этом случае в любой момент времени имеется все более совершенное решение, но выбор точки останова лежит вне программы, что нельзя признать удовлетворительным. Машина будет одинаково долго думать над простыми и сложными ходами. Одно из решений, называемое поиском спокойных позиций, заключается в том, что останавливать поиск можно только в спокойных позициях, когда от хода к ходу оценка позиции меняется незначительно. В позициях же, существенно меняющихся (например, проход пешки в ферзи), поиск надо продолжать. При поиске спокойных позиций возникает проблема устранения эффекта горизонта, проявляющегося тогда, когда в перспективе имеется ход, причиняющий нам серьезный ущерб, который мы можем только отсрочить своими ходами, но являющийся неизбежным. Наши ходы, отвлекающие противника (например, объявление серии шахов), могут вывести опасный для нас ход за пределы горизонта поиска. Первая шахматная программа была разработана в 1951 году Аланом Тьюрингом. Эта программа практически не эксплуатировалась, а ее алгоритм проверялся путем моделирования вручную. Первой успешной отечественной программой стала Kaissa, разработанная в 1974 году в Институте теоретической и экспериментальной физики под руководством экс-чемпиона мира М.Ботвинника. Это программа победила на первом чемпионате мира по компьютерным шахматам в Стокгольме. Наилучшей шахматной программой, которая победила Гарри Каспарова в 1997 году, является Deep Blue, созданная в компании IBM. Программа работала на параллельном компьютере с 30 процессорами IBM RS/6000. На этом компьютере эксплуатировались средства «программного поиска» и 480 специализированных СБИС шахматных процессоров, вырабатывающих ходы. На этом компьютере программа Deep Blue в среднем осуществляла поиск 126 миллионов узлов в секунду, а пиковая скорость составляла 330 миллионов. На каждый ход программа формировала до 30 миллиардов позиций, достигая глубины поиска 14. Основой программы является обычный альфа-бета поиск с итеративным углублением, но ключевой особенностью программы является способность углублять поиск в интересных позициях до 40 ходов. Помимо обычного поиска программа использовала справочник дебютов из 4000 позиций, большую базу эндшпилей и базу из 700 000 игр гроссмейстеров. Только такая добавка к программе позволила уравнять ее с чемпионом мира, который также обладает такими знаниями и использует шаблонные решения. Группа разработчиков Deep Blue отказалась от предложенного Каспаровым реванша. Вместо этого на соревнованиях в 2002 году против Владимира Крамника выступила программа Deep Fritz, уже на обычном персональном компьютере. Deep Fritz – это разработка Франса Морха (Голландия) и Матиаса Фиеста (Германия). В этой программе применена техника нулевого хода (null move), заключающаяся в том, что в ходе поиска 43 игроку позволяется сделать два хода подряд (другой игрок пропускает ход). Благодаря этому легче обнаруживаются слабые ходы. Матч из восьми игр против Deep Fritz закончился ничьей, что позволило Крамнику заявить: «Теперь очевидно, что эта лучшая шахматная программа и чемпион мира играют на равных». 2.6. Контрольные вопросы 1. Какой вид поиска с каждой стороны должен использоваться при двунаправленном поиске? 2. Предложите эвристику для примера, рассматриваемого в подразд. 2.3, которая будет учитывать потери времени на промежуточных посадках и стыковках рейсов. 3. Оцените комбинаторную сложность игры в крестики-нолики на поле размером 3х3 и предложите метод сокращения размерности поиска. Насколько упрощается поиск? 4. Оцените комбинаторную сложность игры «23 спички» в случае развертывания дерева поиска от конечного состояния к начальному. 44 3. Поиск на основе логики В разд. 2.1 мы рассматривали решение задачи о волке, козе и капусте методом поиска в пространстве состояний. Между тем, в литературе эта задача называется логической. Следовательно, ее решение должно быть получено путем умозаключений. Попробуем применить пропозиционную логику (булеву логику) для нахождения решения. Обозначим состояния волка, козы, капусты и фермера переменными W, G, C и F соответственно и присвоим им значения «истина» или логическая единица, если они находятся на левом берегу, и «ложь» или 0, если на правом. Тогда стартовое состояние будет W=1, G=1, C=1, F=1, а конечное – W=0, G=0, C=0, F=0. Запрещенными состояниями будут следущие: WG¬F – волк и коза на левом берегу, фермер – на правом; GС¬F – коза и капуста на левом берегу, фермер – на правом; ¬W¬GF – волк и коза на правом берегу, фермер – на левом; ¬W¬GF – коза капуста на правом берегу, фермер – на левом. Для решения этой задачи нужны входные и выходные переменные. Обозначим W1, G1, C1 и F1 в качестве выходных переменных. Решение задачи в логике первого порядка должно выглядеть следующим образом: f(W,G,C,F) => (W1,G1,C1,F1) = (0,0,0,0). К сожалению, эта задача не решается за один шаг, поэтому решение будет заключаться в последовательности преобразований переменных W,G,C,F в W1,G1,C1,F1. При перемещении с левого на правый берег не должны быть истинными выражения W1G1 или G1C1. (F & W & ¬G¬C) => (F1 = 0, W = 0, G1=G, C1=C) – фермер везет волка; (F & G) => (F1 = 0, W1 = W, G1=0, C1=C) – фермер везет козу. Конфликта быть не может в принципе, так как волк не ест капусту; (F & С & ¬W¬G) => (F1 = 0, C1 = 0, W1=W, G1=G) – фермер везет капусту. Попробуем теперь выразить в виде булевой функции условие перемещения фермера с правого берега на левый без груза. Это возможно в том случае, если фермер находится на правом берегу (¬F), и с его уходом оттуда волк не съест козу (¬W¬G), а коза – капусту (¬G¬C): ( ¬F & ¬W¬G & ¬G¬C ) => (W1 = W, G1 = G, C1 = C, F1 = ¬F). Таким же образом можно написать булевы функции для разрешения конфликтов на правом берегу. Объединив все эти импликации с помощью дизъюнкции, получим универсальную функцию для одного шага решения этой задачи, правда, без устранения повторяющихся состояний. Заметим, что написание этих функций представляет собой весьма кропотливую работу, причем для другой задачи эти функции должны быть написаны заново. Формализация решения подобных задач может быть достигнута использованием таблиц истинности. Выпишем все возможные комбинации переменных: 45 № W G C F W1 G1 C1 F1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 0 3 1 1 1 1 1 1 0 1 4 1 1 1 1 1 1 0 0 5 1 1 1 1 1 0 1 1 6 1 1 1 1 1 0 1 0 ... … … … … … … … ... Теперь удалим из таблицы строки, соответствующие запрещенным комбинациям. К таким относятся вышеперечисленные W1G1¬F1, G1С1¬F1, ¬W1¬G1F1, ¬W1¬G1F1, а также такие, в которых изменяется состояние более, чем одной из переменных W, G, C (по условию задачи на борт нельзя взять более одного груза), или не изменяется состояние переменной F (без лодки переправиться нельзя), либо лодка и груз движутся в противоположном направлении (одна из переменных меняется с 0 на 1, а F – с 1 на 0 и наоборот). Также из таблицы можно удалить строки, не отвечающие конечной цели (движение лодки порожняком с левого берега на правый). Таким образом, исходная таблица из 256 строк превращается в таблицу из 10 строк: № W G C F W1 G1 C1 F1 1 1 1 1 1 1 0 1 0 2 1 0 1 0 1 0 1 1 3 1 0 1 0 1 1 1 1 4 1 0 1 1 0 0 1 0 5 1 0 1 1 1 0 0 0 6 0 0 1 0 0 1 1 1 7 0 0 1 0 1 0 1 1 8 0 1 1 1 0 1 0 0 9 0 1 0 0 0 1 0 1 10 0 1 0 1 0 0 0 0 Поиск решения на основе таблицы истинности заключается в следующем: 1. Находим строку с исходным состоянием переменных (в нашем случае – первая строка). 2. полученные обновленные значения переменных W1, G1, C1 и F1 используем для поиска соответствующих значение переменных W, G, C и F в таблице. 3. Поиск заканчивается, когда значения W1, G1, C1 и F1 будут равны целевым значениям. Данный метод позволяет сравнительно просто формализовать решение подобных задач. Проблема бесконечного блуждания, а в ее наличии легко убедиться, решается вычеркиванием в ходе поиска тех строк из таблицы, которые соответствуют уже посещенным состояниям. Рассмотрим, каким образом можно применять логику первого порядка в задачах, где невозможен поиск методом проб и ошибок на примере игры 46 «Сапер». В начале игры мы не располагаем никакой информацией о расположении мин и первый ход делаем наугад. Если в открытой нами ячейке мины нет, то она открывается, а на смежных клетках отображается информация о количестве мин в восьми соседних клетках. Запишем это для ячейки (i,j) в виде N i,j . Если это число равно нулю, то все соседние клетки открываются автоматически, поскольку тут решение совершенно очевидно. Если же N i,j > 0, то требуется принятие решения, какую (какие) из соседних клеток пометить заминированными. Следует отметить, что, поставив флажок, мы лишь предполагаем, что там находится мина. Узнать этот факт точно мы можем только подорвавшись на ней. Тем не менее, мы будем считать такой факт установленным и будем обозначать его M i,j = 1. Используя эти обозначения мы можем записать ситуацию после первого шага разминирования: M 1,1 = 0; M 1,2 = 0; M 1,3 = 0; M 1,4 = 0; M 2,1 = 0; M 2,2 = 0; M 2,3 = 0; M 2,4 = 0; M 3,1 = 0; N 1,4 = 1; |