Он реализован на примере игры «Спички». Суть игры в следующем: имеется N спичек, два игрока по очереди берут по 1 или 2 спички, выигрывает тот, кто возьмет последнюю спичку.
Краткая теория
Такие игры, как шахматы или шашки, естественно рассматривать как задачи, представленные И / ИЛИ-графами. Игры такого рода называются играми двух лиц с полной информацией. Можно считать, что существует только два возможных исхода игры: ВЫИГРЫШ и НЕВЫИГРЫШ. Так как участники игры ходят по очереди, то имеются два вида позиций, в зависимости от того, чей ход. Участников игры можно называть "игрок" и "противник", тогда будут иметься следующие два вида позиций: позиция с ходом игрока ("позиция игрока") и позиция с ходом противника ("позиция противника"). Пусть начальная позиция Р - это позиция игрока. Каждый вариант хода игрока в этой позиции приводит к одной из позиций противника Q1, Q2, Q3, ... (см. рис. 1). Далее каждый вариант хода противника в позиции Q1 приводит к одной из позиций игрока R11, R12, ... . В И / ИЛИ-дереве, показанном на рис. 1, вершины соответствуют позициям, а дуги - возможным ходам. Уровни позиций игрока чередуются в дереве с уровнями позиций противника. Для того, чтобы выиграть в позиции Р, нужно найти ход, переводящий Р в выигранную позицию Qi. (при некотором i). Таким образом, игрок выигрывает в позиции Р, если он выигрывает в Q1, или Q2, или Q3, или... . Следовательно, Р - это ИЛИ-вершина. Для любого i позиция Qi - это позиция противника, поэтому если в этой позиции выигрывает игрок, то он выигрывает и после каждого варианта хода противника. Другими словами, игрок выигрывает в Qi, если он выигрывает во всех позициях Ri1 и Ri2 и ... . Таким образом, все позиции противника - это И-вершины. Целевые вершины - это позиции, выигранные согласно правилам игры, например позиции, в которых король противника получает мат. Позициям проигранным соответствуют задачи, не имеющие решения. Для того, чтобы решить игровую задачу, нужно построить решающее дерево, гарантирующее победу игрока независимо от ответов противника. Такое дерево задает полную стратегию достижения выигрыша: для каждого возможного продолжения, выбранного противником, в дереве стратегии есть ответный ход, приводящий к победе.
В общем случае Формулировка игровой задачи для игры двух лиц в
форме И / ИЛИ-дерева представлена на рис.1
Рис. 1. Формулировка игровой задачи для игры двух лиц в
форме И / ИЛИ-дерева; участники игры: "игрок" и "противник".
Идея, лежащая в основе большинства эвристических алгоритмов, состоит в том, чтобы оценивать (с помощью численных оценок) перспективность нераскрытых вершин пространства состояний (с точки зрения достижения цели), и выбирать для продолжения поиска наиболее перспективную вершину. Самый обычный способ использования эвристической информации – введение так называемой эвристической оценочной функции. Эта функция определяется на множестве вершин пространства состояний и принимает числовые значения. Значение оценочной функции может интерпретироваться как перспективность раскрытия вершины, или вероятность ее расположения на решающем пути. Обычно считают, что меньшее значение оценочной функции соответствует более перспективной вершине, и вершины раскрываются в порядке увеличения (возрастания) значения оценочной функции.
Найденный путь решения задачи может быть получен и другими методами перебора, но использование оценочной функции приводит к существенно меньшему числу раскрытий вершин. Но, в общем случае (в среднем) алгоритм эвристического поиска обнаруживает решение быстрее алгоритмов слепого перебора.
Рассмотрим ситуацию, когда начальное количество спичек – 7 и первый делает ход компьютер.
Пример работы программы
Листинг программы на языке Turbo Prolog
domains
predicates
repeat
game
start(integer, integer)
draw(integer)
minimax(integer, integer)
foc(integer, integer)
goal
game.
clauses
repeat.
repeat:-repeat.
draw(0).
draw(N):-N<0,N=0.
draw(N):-write("| "), N1=N-1, draw(N1).
game:-repeat,
makewindow(1,10,11,"Palochki =)",0,0,25,80),
write("Viigraet tot, kto zabral poslednuu palochky!"),nl,
write("________________________________"),nl,
write("Vvedite chislo palochek:"),nl,
write(">"),readint(M),nl,
write("Kto hodit pervim?"),nl,
write("1-igrok"),nl,
write("2-komp"),nl,
write("Vash vibor: "),
readint(F),nl,
start(M, F),
write("Vihod? (y/n)"),nl,
write(">"),
readln(C),
C="y",removewindow,!.
start(-1,2):-write("Vi viigrali!!!!"),nl, nl,!.
start(0,2):-write("Vi viigrali!!!!"),nl, nl,!.
start(0,1):-write("Vi proigrali...."),nl, nl,!.
start(1,2):-draw(1),nl, nl,
write("Komp vzjal odny palochky"),nl, nl,
write("Vi proigrali..."),nl, nl,!.
start(2,2):-draw(2),nl, nl,
write("Komp vzjal 2 palochki"),nl, nl,
write("Vi proigrali..."),nl, nl,!.
start(N,1):-draw(N),nl, nl,
write("Vi mogete vzjat 1 ili 2 palochki"),nl,
write("Berete: "),
readint(Kol),nl,
N1=N-Kol,
start(N1,2),!.
start(N,2):-draw(N),nl, nl,
minimax(N, Kol),
write("Komp beret: "),
N1=N-Kol,
write(Kol),nl, nl,
start(N1,1),!.
foc(Pos,1):-Pos mod 3=0,!.
foc(Pos,-1):-Pos mod 3 <>0,!.
minimax(Pos, PosL):-Pos1=Pos-1,
Pos2=Pos-2,
foc(Pos1,Ots1),
foc(Pos2,Ots2),
Ots1>Ots2,
PosL=1,!.
minimax(Pos, PosL):-PosL=2.
