Кіріспе
Expectiminimax алгоритмі — екі ойыншыдан тұратын нөлдік жиынтық ойындарды ойнайтын жасанды интеллект жүйелерінде қолдану үшін minimax алгоритмінің бір түрі, мысалы, backgammon, онда нәтиже ойыншының шеберлігі және кездейсоқ факторлардың, мысалы, құймақтарды лақтырудың үйлесіміне байланысты. Дәстүрлі minimax ағашының "минима" және "макс" түйіндеріне қоса, бұл нұсқада "шешім" ("табиғаттың қадамы") түйіндері бар, олар кездейсоқ оқиғаның күтілетін мәнін есептейді. Ойын теориясы тұрғысынан, expectiminimax ағашы — толық емес, бірақ жетілдірілген ақпаратты қамтитын кеңейтілген ойынның ойын ағашы. Дәстүрлі minimax әдісінде ағаштың деңгейлері ағаштың тереңдік лимитіне жеткенге дейін максимумнан минимумға ауысады. Expectiminimax ағашында "шешім" түйіндері макс және мин түйіндерімен кезегімен орналасады. Бала түйіндерінің пайдалылық мәндерінің максималды немесе минималды мәнін алудың орнына, шешім түйіндері салмақталған орташа мәнді есептейді, мұнда салмақ бала түйінге жету ықтималдығын көрсетеді. Оның псевдокоды төменде келтірілген. функциясы expectiminimax(түйін, тереңдік) егер түйін терминалды түйін болса немесе тереңдік = 0 болса түйіннің эвристикалық мәнін қайтар егер қарсылас түйінде ойнаса // Ең төменгі мәнді бала түйіннің мәнін қайтар α := +∞ түйіннің әр баласы үшін α := min(α, expectiminimax(бала, тереңдік - 1)) әйтпесе, егер біз түйінде ойнасақ // Ең жоғары мәнді бала түйіннің мәнін қайтар α := -∞ түйіннің әр баласы үшін α := max(α, expectiminimax(бала, тереңдік - 1)) әйтпесе, егер түйінде кездейсоқ оқиға болса // Барлық бала түйіндерінің мәндерінің салмақталған орташасын қайтар α := 0 түйіннің әр баласы үшін α := α + (Ықтималдық[бала] × expectiminimax(бала, тереңдік - 1)) қайтар α
if node is a terminal node or depth = 0
return the heuristic value of node
if the adversary is to play at node
// Return value of minimum valued child node
let α := +∞
foreach child of node
α := min(α, expectiminimax(child, depth 1))
else if we are to play at node
// Return value of maximum valued child node
let α := ∞
foreach child of node
α := max(α, expectiminimax(child, depth 1))
else if random event at node
// Return weighted average of all child nodes' values
let α := 0
foreach child of node
α := α + (Probability[child] × expectiminimax(child, depth 1))
return α
Ескеріңіз, кездейсоқ түйіндер үшін әр балаға жетудің белгілі бір ықтималдығы болуы керек. (Көптеген кездейсоқ ойындарда бала түйіндер тең салмақта болады, яғни қайтарылатын мән барлық бала түйіндерінің орташа мәні болуы мүмкін.)
Expectimax іздеу
Экспектимакс іздеуі – Том Эверитт пен Маркус Хаттердің «Жалпы жасанды интеллект: алгоритмдік ықтималдыққа негізделген тізбекті шешімдер» (2005) кітабында сипатталған бір түрі.