Мінімаксний алгоритм пошуку для прийняття рішень у стратегічних іграх

Abstract

Часто для вирішення нестандартних складних задач доводиться застосовувати алгоритми з використанням евристик, що дає змогу розв’язати задачу за обмежений час та прийняти рішення. Таким алгоритмом пошуку, що застосовується при програму-ванні інтелектуальних інформаційних систем, є мінімаксний алгоритм. Він спрямований на мінімізацію очікуваних втрат, для цього гравець припускає, що рішення, прийняте його опонентом, буде несприятливим, а найгірший сценарій очікується до руху суперника. Біля основи дерева суперник робить перший хід, тому очікується найгірший результат. Тоді на другому рівні інший гравець повинен прагнути максимізувати свій прибуток, беручи до уваги рішення, прийняте раніше противником. Функція оцінки – це статичне число, яке присвоюється кожному вузлу відповідно до характеристик самої гри.