- Мини-мак алгоритам је рекурзивни алгоритам или рекурзивни алгоритам који се користи у доношењу одлука и теорији игара. Он пружа оптималан потез за играча под претпоставком да противник такође игра оптимално.
- Мини-Мак алгоритам користи рекурзију за претрагу кроз стабло игре.
- Мин-Мак алгоритам се углавном користи за играње игара у АИ. Као што су шах, даме, тиц-тац-тое, го и разне игре за вучу. Овај алгоритам израчунава минималну одлуку за тренутно стање.
- У овом алгоритму два играча играју игру, један се зове МАКС, а други се зове МИН.
- Оба играча се боре против тога јер противнички играч добија минималну корист док они добијају максималну корист.
- Оба играча игре су противници један другом, при чему ће МАКС изабрати максималну вредност, а МИН ће изабрати минималну вредност.
- Минимак алгоритам изводи алгоритам претраге у дубину за истраживање комплетног стабла игре.
- Минимакс алгоритам наставља све до терминалног чвора стабла, а затим враћа стабло као рекурзију.
Псеудо-код за МинМак алгоритам:
function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva
Први позив:
Минимакс (чвор, 3, тачно)
Рад Мин-Мак алгоритма:
- Рад минимакс алгоритма може се лако описати на примеру. У наставку смо узели пример стабла игре које представља игру за два играча.
- У овом примеру постоје два играча, један се зове Максимизатор, а други се зове Минимизатор.
- Макимизер ће покушати да добије максималан могући резултат, а минимизатор ће покушати да добије минимални могући резултат.
- Овај алгоритам примењује ДФС, тако да у овом стаблу игре морамо проћи скроз кроз листове да бисмо дошли до терминалних чворова.
- На терминалном чвору, терминалне вредности су дате тако да ћемо упоредити те вредности и вратити се стаблу све док се не појави почетно стање. Следе главни кораци који су укључени у решавање стабла игре за два играча:
Корак 1: У првом кораку, алгоритам генерише цело стабло игре и примењује функцију корисности да добије вредности корисности за терминална стања. У дијаграму стабла испод, узмимо А почетно стање стабла. Претпоставимо да ће максимизатор узети први круг који има најгори случај почетне вредности =- бесконачност, а минимизатор ће узети следећи окрет који има почетну вредност у најгорем случају = +бесконачност.
Корак 2: Сада, прво проналазимо услужне вредности за Макимизер, његова почетна вредност је -∞, тако да ћемо упоредити сваку вредност у терминалном стању са почетном вредношћу Макимизер-а и одредити веће вредности чворова. Наћи ће максимум међу свима.
- За чвор Д мак(-1,- -∞) => мак(-1,4)= 4
- За чвор Е мак(2, -∞) => мак(2, 6)= 6
- За чвор Ф мак(-3, -∞) => мак(-3,-5) = -3
- За чвор Г мак(0, -∞) = мак(0, 7) = 7
Корак 3: У следећем кораку, долази на ред за минимизатор, тако да ће упоредити све вредности чворова са +∞ и пронаћи 3рдвредности чворова слоја.
- За чвор Б= мин(4,6) = 4
- За чвор Ц= мин (-3, 7) = -3
4. корак: Сада је на реду Макимизер, и он ће поново изабрати максималну вредност свих чворова и пронаћи максималну вредност за основни чвор. У овом стаблу игре постоје само 4 слоја, тако да одмах стижемо до коренског чвора, али у правим играма биће више од 4 слоја.
- За чвор А мак(4, -3)= 4
То је био комплетан радни ток минимакс игре за два играча.
Особине Мини-Мак алгоритма:
Ограничење минимакс алгоритма:
Главни недостатак минимакс алгоритма је тај што постаје веома спор за сложене игре као што су шах, го, итд. Ова врста игара има велики фактор гранања и играч има много избора да одлучи. Ово ограничење минимакс алгоритма може се побољшати алфа-бета обрезивање о чему смо говорили у следећој теми.