- אלגוריתם מיני-מקס הוא אלגוריתם רקורסיבי או חוזר לאחור המשמש בקבלת החלטות ובתורת המשחקים. זה מספק מהלך אופטימלי לשחקן בהנחה שגם היריב משחק בצורה אופטימלית.
- אלגוריתם Mini-Max משתמש ברקורסיה כדי לחפש דרך עץ המשחק.
- אלגוריתם Min-Max משמש בעיקר למשחקים ב-AI. כגון שחמט, דמקה, טיק-טק, go ומשחקי גרר שונים. אלגוריתם זה מחשב את החלטת המינימקס עבור המצב הנוכחי.
- באלגוריתם זה שני שחקנים משחקים את המשחק, אחד נקרא MAX והשני נקרא MIN.
- שני השחקנים נלחמים בזה מכיוון ששחקן היריב מקבל את התועלת המינימלית בעוד שהם מקבלים את התועלת המקסימלית.
- שני שחקני המשחק יריבים זה לזה, כאשר MAX יבחר את הערך המקסימלי ו-MIN יבחר את הערך הממוזער.
- אלגוריתם המינימקס מבצע אלגוריתם חיפוש עומק ראשון לחקירה של עץ המשחק השלם.
- אלגוריתם המינימקס ממשיך כל הדרך עד לצומת הטרמינל של העץ, ואז חוזר אחורה מהעץ בתור הרקורסיה.
פסאודו-קוד עבור אלגוריתם 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
שיחה ראשונית:
Minimax(צומת, 3, נכון)
עבודה של אלגוריתם Min-Max:
- ניתן לתאר בקלות את פעולתו של אלגוריתם המינימקס באמצעות דוגמה. להלן לקחנו דוגמה של עץ משחק המייצג את המשחק של שני שחקנים.
- בדוגמה זו, ישנם שני שחקנים האחד נקרא Maximizer והשני נקרא Minimizer.
- Maximizer ינסה להשיג את הציון המקסימלי האפשרי, ו-Minimizer ינסה להשיג את הציון המינימלי האפשרי.
- האלגוריתם הזה מחיל DFS, אז בעץ המשחק הזה, אנחנו צריכים לעבור את כל הדרך דרך העלים כדי להגיע לצמתים הטרמינלים.
- בצומת הטרמינל, ערכי הטרמינל ניתנים ולכן נשווה את הערכים הללו ונחזור על העץ עד להתרחשות המצב ההתחלתי. להלן השלבים העיקריים הכרוכים בפתרון עץ המשחקים לשני שחקנים:
שלב 1: בשלב הראשון, האלגוריתם מייצר את כל עץ המשחק ומחיל את פונקציית השירות כדי לקבל את ערכי השירות עבור מצבי הטרמינל. בתרשים העץ למטה, ניקח ש-A הוא המצב ההתחלתי של העץ. נניח שהמקסם יקבל את הסיבוב הראשון שיש לו ערך התחלתי במקרה הגרוע =- אינסוף, והמזעור יקבל את הסיבוב הבא שיש לו ערך התחלתי במקרה הגרוע ביותר = +אינסוף.
שלב 2: כעת, ראשית אנו מוצאים את ערך השירותים עבור Maximizer, הערך ההתחלתי שלו הוא -∞, אז נשווה כל ערך במצב טרמינלי עם הערך ההתחלתי של Maximizer ונקבע את ערכי הצמתים הגבוהים יותר. זה ימצא את המקסימום בין כולם.
- עבור צומת D max(-1,- -∞) => max(-1,4)= 4
- עבור Node E max(2, -∞) => max(2, 6)= 6
- עבור Node F max(-3, -∞) => max(-3,-5) = -3
- עבור צומת G max(0, -∞) = max(0, 7) = 7
שלב 3: בשלב הבא, זה תור למזעור, כך שהוא ישווה את כל ערך הצמתים עם +∞, וימצא את ה-3מחקר ופיתוחערכי צומת שכבה.
- עבור צומת B= min(4,6) = 4
- עבור צומת C= min (-3, 7) = -3
שלב 4: כעת הגיע התור למקסימייזר, והוא יבחר שוב את הערך המקסימלי של כל הצמתים וימצא את הערך המקסימלי עבור צומת השורש. בעץ המשחק הזה יש רק 4 שכבות, מכאן שאנחנו מגיעים מיד לצומת השורש, אבל במשחקים אמיתיים יהיו יותר מ-4 שכבות.
- עבור צומת A max(4, -3)= 4
זה היה זרימת העבודה המלאה של משחק מינימקס שני שחקנים.
מאפייני אלגוריתם מיני-מקס:
הגבלה של אלגוריתם המינימקס:
החיסרון העיקרי של אלגוריתם המינימקס הוא שהוא נהיה ממש איטי עבור משחקים מורכבים כמו שחמט, גו וכו'. לסוג זה של משחקים יש גורם הסתעפות עצום, ולשחקן יש הרבה אפשרויות להחליט. ניתן לשפר מגבלה זו של אלגוריתם המינימקס גיזום אלפא ביתא שעליו דנו בנושא הבא.