Алгоритм минимакса
В 1945 году Оскар Моргенштерн и Джон фон Нейман предложили метод минимакса, нашедший широкое применение в теории игр. Предположим, что противник использует оценочную функцию (ОФ), совпадающую с нашей ОФ. Выбор хода с нашей стороны определяется максимальным значением ОФ для текущей позиции. Противник стремится сделать ход, который минимизирует ОФ. Поэтому этот метод и получил название минимакса. На рис. 3.5 приведен пример анализа дерева ходов с помощью метода минимакса (выбранный путь решения отмечен жирной линией).
Рис. 3.5. Дерево ходов
Развивая метод минимакса, назначим вероятности для выполняемых действий в задаче о миссионерах и людоедах:
P([2 : 0]R) = 0; 8; P([1 : 1]R) = 0; 5; P([0 : 2]R) = 0; 9; P([1 : 0]R) = 0; 3; P([0 : 1]R) = 0; 3:
Интуитивно понятно, что посылать одного людоеда или одного миссионера менее эффективно, чем двух человек, особенно на начальных этапах. На каждом уровне мы будем выбирать состояние по критерию Pi. Даже такой простой подход позволит нам избежать части тупиковых состояний в процессе поиска и сократить время по сравнению с полным перебором. Кстати, этот подход достаточно распространен в экспертных продукционных системах.
