Представление игры в виде игрового дерева

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

Однако, в некоторых случаях можно найти приемлемую стратегию, основываясь промежуточной оценке игровой ситуации. При этом матричная форма решения неприемлема, но можно производить поиск по дереву. Для получения более правильной оценки ситуации можно производить оценивание после серии ходов. Получаемая оценка называется статической, а процедура, производящая оценку статическим оценщиком. Положительное значение оценки обычно говорит о преимуществе одного игрока, а отрицательное о преимуществе другого.

Игровое дерево это семантическое дерево, в котором узлы обозначают игровые ситуации, а ветви обозначают ходы.

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

Минимах процедура

Стратегия данного метода предельно проста: каждый игрок на своем уровне делает выбор согласно своей роли – максимизатор выбирает ситуацию, приводящую к максимальному выигрышу, а минимизатор – к минимальному.

Рисунок 3 – Дерево игры

Процедура, реализующая данную стратегию следующая:

• Если достигнута предельная глубина поиска, то провести статическое оценивание игровой ситуации и вернуть оценку

• Иначе если это уровень минимизатора применить процедуру минимакса ко всем детям текущего узла, вернуть наименьший результат

• Иначе применить процедуру минимакса ко всем детям текущего узла, вернуть наибольший результат