TechCodeview

• Алгоритъмът Mini-max е рекурсивен алгоритъм или алгоритъм за обратно проследяване, който се използва при вземане на решения и теория на игрите. Той осигурява оптимален ход за играча, ако приемем, че противникът също играе оптимално.
• Алгоритъмът Mini-Max използва рекурсия за търсене в дървото на играта.
• Алгоритъмът Min-Max се използва най-вече за игра на игри в AI. Като например шах, дама, тик-так-палец, го и различни игри за теглене на играчи. Този алгоритъм изчислява минимаксното решение за текущото състояние.
• В този алгоритъм двама играчи играят играта, единият се нарича MAX, а другият се нарича MIN.
• И двамата играчи се борят, тъй като противниковият играч получава минималната полза, докато те получават максималната полза.
• И двамата играчи в играта са опоненти един на друг, където MAX ще избере максималната стойност, а MIN ще избере минимизираната стойност.
• Алгоритъмът minimax изпълнява алгоритъм за първо търсене в дълбочина за изследване на пълното дърво на играта.
• Минимаксният алгоритъм продължава надолу до крайния възел на дървото, след което връща дървото обратно като рекурсия.

Псевдо код за алгоритъм MinMax:

 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, вярно)

Работа на алгоритъма Min-Max:

• Работата на минимаксния алгоритъм може лесно да се опише с помощта на пример. По-долу сме взели пример за дърво на играта, което представлява играта за двама играчи.
• В този пример има двама играчи, единият се нарича Maximizer, а другият се нарича Minimizer.
• Maximizer ще се опита да получи максималния възможен резултат, а Minimizer ще се опита да получи минималния възможен резултат.
• Този алгоритъм прилага DFS, така че в това дърво на играта трябва да преминем целия път през листата, за да стигнем до крайните възли.
• В терминалния възел се дават терминалните стойности, така че ние ще сравним тези стойности и ще се върнем към дървото, докато се появи първоначалното състояние. Следват основните стъпки, включени в решаването на дървото на играта за двама играчи:

Етап 1: В първата стъпка алгоритъмът генерира цялото дърво на играта и прилага функцията за полезност, за да получи стойностите на полезността за състоянията на терминала. В дървовидната диаграма по-долу, нека вземем А е първоначалното състояние на дървото. Да предположим, че максимизаторът вземе първи ход, който има първоначална стойност за най-лошия случай =- безкрайност, а минимизаторът ще вземе следващия ход, който има начална стойност за най-лошия случай = +безкрайност.

Стъпка 2: Сега, първо намираме стойността на помощните програми за Maximizer, нейната начална стойност е -∞, така че ще сравним всяка стойност в терминално състояние с началната стойност на Maximizer и ще определим стойностите на по-високите възли. Ще намери максимума сред всички.

• За възел D max(-1,- -∞) => max(-1,4)= 4
• За възел E max(2, -∞) => max(2, 6)= 6
• За възел F max(-3, -∞) => max(-3,-5) = -3
• За възел G max(0, -∞) = max(0, 7) = 7

Стъпка 3: В следващата стъпка е ред на минимизатора, така че той ще сравни стойността на всички възли с +∞ и ще намери 3-те^rdстойности на възел на слоя.

• За възел B= min(4,6) = 4
• За възел C= min (-3, 7) = -3

Стъпка 4: Сега е ред на Maximizer и той отново ще избере максималната стойност от всички възли и ще намери максималната стойност за основния възел. В това дърво на играта има само 4 слоя, следователно достигаме веднага до основния възел, но в реалните игри ще има повече от 4 слоя.

• За възел A max(4, -3)= 4

Това беше пълният работен процес на минимаксната игра за двама играчи.

Свойства на алгоритъма Mini-Max:

Завършен-Алгоритъмът Min-Max е завършен. Определено ще намери решение (ако съществува) в крайното дърво за търсене.Оптимално-Алгоритъмът Min-Max е оптимален, ако и двамата опоненти играят оптимално.времева сложност-Тъй като изпълнява DFS за дървото на играта, времевата сложност на алгоритъма Min-Max е О(б^м) , където b е факторът на разклоняване на игралното дърво, а m е максималната дълбочина на дървото.Космическа сложност-Пространствената сложност на алгоритъма Mini-max също е подобна на DFS, който е относно .

Ограничение на минимаксния алгоритъм:

Основният недостатък на алгоритъма minimax е, че става наистина бавен за сложни игри като шах, го и т.н. Този тип игри имат огромен фактор на разклоняване и играчът има много възможности за избор. Това ограничение на минимаксния алгоритъм може да бъде подобрено от алфа-бета резитба които сме обсъждали в следващата тема.