2.2.3. Поиск с возвратом

Иногда приходится иметь дело с задачей поиска оптимального решения, когда невозможно применить ни один из известных методов, способных помочь отыскать оптимальный вариант решения, и остается прибегнуть к последнему средству – полному перебору. Приведем систематическое опи­сание метода полного перебора, называемого поиском с возвратом.

Рассмотрим игры двух лиц, которые обычно описываются множе­ством «позиций» и совокупностью правил перехода из одной позиции в другую, причем предполагается, что игроки ходят по очереди. Будем считать, что правилами разрешены лишь конечные последовательнос­ти позиций и что в каждой позиции имеется лишь конечное число раз­решенных ходов (рис. 24). Тогда для каждой позиции p найдется число N(p) такое, что никакая игра, начавшаяся в p, не может продолжаться более N(p) ходов.

Терминальными называются позиции, из которых нет разрешенных ходов. На каждой из них определена целочисленная функция f(p), зада-82

Ходы игрока

х

о

х

х х

х О

О О

-1

0

ххх

х О

х х

х х О

х х

х О

О О

1

О О

-1

0x0

0

х

х 0 х

х х 0

00

0

х х

х х 0

00 0

1

х 0 х

х 0

0x0

0

х х

0x0

0x0

1

х о х

х х 0

0x0

0

х 0 х

х х 0

0x0

0

ххх

0x0

0x0

1

Рис. 24. Дерево игры «крестики-нолики»

ющая выигрыш того из игроков, которому принадлежит ход в этой по­зиции; выигрыш второго игрока считается равным –f(p).

Если из позиции p имеется d разрешенных ходов p₁, …, p_d, возника­ет проблема выбора лучшего из них. Будем называть ход наилучшим, если по окончании игры он приносит наибольший возможный выиг­рыш при условии, что противник выбирает ходы, наилучшие для него (в том же смысле). Пусть f(p) есть наибольший выигрыш, достижимый в позиции p игроком, которому принадлежит очередь хода, против оп­тимальной защиты. Так как после хода в позицию p_i выигрыш этого игрока равен –f(p_i), имеем

f (p)

f (p) d = 0 ,

max { - f (p₁),..., - f (p_d )}, если d >

Эта формула позволяет индуктивно определить f(p) для каждой по­зиции p.

83

Функция f(p) равна тому максимуму, который гарантирован, если оба игрока действуют оптимально. Следует, однако, заметить, что она отражает результаты весьма осторожной стратегии, которая не обяза­тельно хороша против плохих игроков или игроков, действующих со­гласно другому принципу оптимальности. Пусть, например, имеются два хода в позиции p₁ и p₂, причем p₁ гарантирует ничью (выигрыш 0) и не дает возможности выиграть, в то время как p₂ дает возможность выиграть, если противник просмотрит очень тонкий выигрывающий ход. В такой ситуации можно предпочесть рискованный ход в p₂, если только нет уверенности в том, что противник всемогущ и всезнающ. Очень возможно, что люди выигрывают у шахматных программ таким именно образом.

Нижеследующий алгоритм, называемый поиском с возвратом, вы­числяет f(p).

function BackSearch(p: position): integer; {оценивает и возвращает выигрыш f(p) для позиции p} var

m,i,t,d: integer; begin

Определить позиции p₁,...,p_d, подчиненные p;

if d = 0 then BackSearch := f(p)

else begin m := -•; for i:= 1 to d do begin

t := – BackSearch(p_i); if t > m then m:= t; end;

BackSearch := m; end; end;

Здесь +∞ обозначает число, которое не меньше abs(f(p)) для любой терминальной позиции p; поэтому –∞ не больше f(p) и –f(p) для всех p. Этот алгоритм вычисляет f(p) на основе «грубой силы» – для каждой позиции он оценивает все возможные продолжения.

Если рассмотреть сложную игру (например, шахматы), в которой де­рево игры, являясь, в принципе, конечным, столь огромно, что любые попытки оценить его по данному методу обречены на неудачу.

Проблема для наиболее интересных игр состоит в том, что размер этого дерева является чрезвычайно огромным, порядка W^L, где W – сред-84

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