Применение эвристики «наибольшего числа выигрышных линий» в игре «крестики-нолики».

Рассмотрим игру в "крестики-нолики". Исчерпывающий поиск (полный пе­ребор вариантов) в этой игре затруднителен, но возможен. На каждый из девяти первых ходов существует восемь возможных ответов. На которые, в свою очередь, можно отве­тить семью различными вариантами и т.д. Простой анализ позволяет найти общее число возможных состояний, которые следует рассмотреть в исчерпывающем поиске,— 9х8х7х...,или9!.

Учитывая симметрию задачи, можно уменьшить пространство поиска. Проблема множества возможных конфигураций в действительности сводится к поиску возможных симметричных конфигураций игровой доски. Таким образом, существует не девять, а только три возможных первых хода — в угол, на верхнюю центральную клетку и в центр решетки. Редукции на втором уровне и далее сокращают размерность пространства до 12x7!, как показано на рис. 4.1. Симметрия игрового пространства, подобная рассмот­ренной выше, может быть описана как математический инвариант, и если она существу­ет в задаче, то может быть успешно использована для значительного уменьшения про­странства состояний. Простая эвристика может свести на нет необходимость поиска: мы можем делать такие ходы на доске, в которых крестики имеют наибольшее количество выигрышных линий. (Первые три состояния игры "крестики-нолики" просчитаны имен­но таким образом, рис. 4.2.) Если число потенциальных побед равно, берется первое из таких состояний. Затем алгоритм выбирает состояние с наивысшим эвристическим зна­чением. Для хода X берем центральную клетку. Заметим, что при этом отбрасываются не только остальные возможные ходы, но и их потомки. Отсюда следует, что после первого хода размерность пространства состояний уменьшается на 2/3 (рис. 4.3).

Оппонент после первого хода может выбрать один из двух возможных ответных хо­дов (как показано на рис. 4.3). Что бы ни выбрал оппонент, к результирующему состоя­нию игры может быть применена эвристика. Эвристика использования "наибольшего числа выигрышных линий" выбирает среди возможных ходов наилучший. При продол­жении поиска каждый новый ход устраняет необходимость обработки потомков отбро­шенных узлов, таким образом, полный перебор не требуется. На рис. 4.3 продемонстри­рован редукционный поиск на первых трех шагах игры. Каждое состояние игры помече­но соответствующим ему эвристическим значением.

 

Хотя точное количество возможных состояний в игре вычислить трудно, верхний предел этого количества состояний может быть вычислен, если допустить, что минимальное число ходов в игре — 9, и каждый ход имеет по 8 потомков. В действительности число состояний будет гораздо меньше, так как доска заполняется, и с каждым ходом число возможных ответов уменьшается. Более того, оппонент делает половину всех ходов. Несмотря на это, грубый верхний предел — 9x8, или 72 состояния, что на 4 порядка меньше величины 9!.

 

Стратегия "жадного" поиска.

Одна из наиболее простых стратегий эвристического поиска базируется на минимизации оценки стоимости решения из каждого шага поиска. Эта стратегия часто называется стратегия "жадного" поиска (greedy search). Функция, при помощи которой осуществляется вычисление оценки стоимости решения из каждого шага, называется эвристической функцией (heuristic function). Эвристическую функцию определим следующим образом

h(n) = <оценка стоимости наиболее дешевого пути из узла n до целевого узла>

 

Стратегия "жадного" поиска использует функцию h для выбора очередного расширяемого узла. Функция h может иметь любой вид и обычно принимает нулевое значение при достижении целевого узла. Проиллюстрируем стратегию "жадного" поиска на примере решения задачи нахождения пути из города A в город Z. В качестве эвристической функции выберем функцию, задающую кратчайшее расстояние, "по прямой" (КР), из текущего города до города Z.

 

h_КР(n) = <кратчайшее расстояние из города n до города Z>

 

Рис. 4.4 иллюстрирует развитие "жадного" поиска при решении задачи нахождения пути из города A в город Z.

Рис. 4.4Пример развития "жадного" поиска. Узлы помечены значениями функции h_КР(n)

 

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

 

Стратегия А^* поиска.

Стратегия А^* поиска лишена отмеченных недостатков стратегии "жадного" поиска и обладает свойствами оптимальности и завершенности. Эта стратегия, для выбора очередного расширяемого узла, использует функцию общей стоимости пути, являющейся суммой функции стоимости всего пути - g(n) и эвристической функции оценки решения из текущего шага - h(n):

f(n) = g(n) + h(n)

Стратегия А^* поиска выбирает для расширения узел имеющий наименьшее значение функции f(n). На эвристическую функцию h(n) обычно накладывается ограничение, заключающееся в том, что функция h(n) не должна переоценивать (overestimates) стоимость решения. Эвристическая функция, обладающая таким свойством, называется допустимой эвристикой (admissible heuristic). Если h(n) допустимая эвристика, то f(n) никогда не переоценит реальную стоимость лучшего решения из n, что обеспечивает стратегии А^* поискасвойства оптимальности и завершенности. На рис. 4.5 приведены несколько первых шагов стратегии А^* поискапути из города А в город Z. В качестве допустимой эвристики выбрана функция h_КР(n).

 

Рис. 4.5Пример развития А* поиска.

Узлы помечены значениями функции f = g + h_КР

Заданиe:

 

Студенты имеющие нечетный порядковый номер в списке выполняют 1-й вариант, четный – 2-й вариант. При программировании использовать среду Delphi.

 

 

Варианты:

1. Написать программу игры в «крестики - нолики» с использованием эвристики «наибольшего числа выигрышных линий».

 

2. Написать программу нахождения пути из города А в город Х с использованием алгоритма А*. Количество городов не менее 10. Расстояния задаются пользователем. Реализовать графический интерфейс.