משחק לוח אינטליגנציה מלאכותית: האלגוריתם המינימקס: 8 שלבים

2024 מְחַבֵּר: John Day | [email protected]. שונה לאחרונה: 2024-01-30 09:14

תהיתם פעם כיצד מייצרים את המחשבים שאתם משחקים נגדם בשחמט או בדמקה? ובכן, אל תרחיק יותר מהמדריך הזה, שכן הוא יראה לך כיצד לבצע אינטליגנציה מלאכותית פשוטה אך יעילה (AI) באמצעות האלגוריתם המינימקס! באמצעות אלגוריתם המינימקס, ה- AI מבצע מהלכים מתוכננים וחושבים היטב (או לפחות מחקה תהליך חשיבה). עכשיו, אני יכול רק לתת לך את הקוד ל- AI שיצרתי, אבל זה לא יהיה כיף. אסביר את ההיגיון מאחורי בחירות המחשב.

במדריך זה אני אלווה אותך בשלבים כיצד ליצור AI עבור אותלו (AKA Reversi) בפייתון. תהיה לך הבנה בינונית כיצד לקודד בפייתון לפני שתתמודד עם הפרויקט הזה. להלן כמה אתרים טובים שאפשר להסתכל עליהם כדי להכין אותך למדריך זה: w3schools או learnpython. בסוף מדריך זה, אתה אמור להיות בעל AI שיבצע מהלכים מחושבים ואמור להיות מסוגל להביס את רוב בני האדם.

מכיוון שמדריך זה יעסוק בעיקר כיצד ליצור AI, לא אסביר כיצד לעצב משחק בפייתון. במקום זאת, אני אתן את הקוד למשחק שבו בן אדם יכול לשחק נגד בן אדם אחר ולשנות אותו כך שתוכל לשחק משחק שבו בן אדם משחק נגד ה- AI.

למדתי כיצד ליצור AI זה באמצעות תוכנית קיץ ב- Columbia SHAPE. היה לי טוב שם אז תסתכל באתר שלהם כדי לראות אם אתה מעוניין.

עכשיו לאחר שהוצאנו את הלוגיסטיקה מהדרך, נתחיל לקודד!

(שמתי כמה הערות בתמונות אז הקפד להסתכל עליהן)

אספקה

זה קל:

1) מחשב עם סביבת פייתון כגון Spyder או IDLE

2) הורד את הקבצים למשחק האותלו מה- GitHub שלי

3) המוח שלך עם סבלנות מותקן

שלב 1: הורד את הקבצים הדרושים

כשאתה נכנס ל- GitHub שלי, אתה אמור לראות 5 קבצים. הורד את כל 5 והנח את כולם באותה תיקיה. לפני שנפעיל את המשחק, פתח את כל הקבצים בסביבת הספיידר.

הנה מה שהקבצים עושים:

1) othello_gui.py קובץ זה יוצר את לוח המשחק לשחקנים עליו (בין אם אנושי או מחשב)

2) othello_game.py קובץ זה מנגן שני מחשבים אחד נגד השני ללא לוח המשחק ורק מציג את הציונים והעמדות הזזה

3) ai_template.py זה המקום שבו תשים את כל הקוד שלך כדי להפוך את ה- AI שלך

4) randy_ai.py זהו AI מלאכותי מראש שבוחר את המהלכים שלו באופן אקראי

5) othello_shared.py חבורה של פונקציות מוכנות מראש שתוכלו להשתמש בהן לביצוע ה- AI שלכם כגון בדיקת מהלכים זמינים, הציון או מצב הלוח.

6) שלושת הקבצים האחרים: Puma.py, erika_5.py ו- nathan.py, שנעשו על ידי אני, אריקה ונתן בהתאמה מתוכנית SHAPE, אלה שלושה AIs שונים עם קודים ייחודיים.

שלב 2: כיצד לפתוח ולשחק Python Othello

לאחר שכל הקבצים פתוחים, בפינה השמאלית התחתונה של המסך, הקלד "הפעל othello_gui.py" ולחץ על enter במסוף IPython. או במסוף Mac, הקלד "python othello_gui.py" (אחרי שאתה בתיקייה הנכונה כמובן). אז לוח אמור לצוץ על המסך שלך. מצב זה הוא מצב האדם לעומת האדם. אור הולך שני וחשוך ראשון. תסתכל על הסרטון שלי אם אתה מבולבל. i למעלה, יש את הציון של כל אריח צבע. כדי לשחק, לחץ על שטח הזזה תקף כדי למקם אריח ואז תן את המחשב ליריב שלך שיעשה את אותו הדבר וחוזר על עצמו.

אם אינך יודע כיצד לשחק את אותלו, קרא את הכללים הבאים מאתר ultra boards:

שחור תמיד זז ראשון. מהלך מתבצע על ידי הנחת דיסק בצבע השחקן על הלוח במצב ש"חוצה "אחד או יותר מדיסקיות היריב. דיסק או שורה של דיסקים מוקפים כשהם מוקפים בקצותיהם בדיסקים בצבע ההפוך. דיסק עשוי להקיף כל מספר דיסקים בשורה אחת או יותר לכל כיוון (אופקי, אנכי, אלכסוני)…. (סיימו לקרוא באתר שלהם)

ההבדל בין המשחק המקורי למשחק הפיתון הזה הוא שכאשר לא נותרו מהלכים תקפים לשחקן אחד המשחק מסתיים

עכשיו שאתה יכול לשחק את המשחק עם חבר, בואו נכין AI שתוכל לשחק איתו.

שלב 3: אלגוריתם מינימקס: יצירת תרחישים

לפני שנדבר על איך לכתוב את זה בקוד, בואו נעבור על ההיגיון שמאחורי זה. אלגוריתם המינימקס הוא אלגוריתם קבלת החלטות ומעקב אחורי ומשמש בדרך כלל במשחקים מבוססי שני שחקנים. המטרה של AI זה היא למצוא את המהלך הטוב ביותר הבא ואת המהלכים הטובים הבאים עד שהוא ינצח את המשחק.

עכשיו איך האלגוריתם יקבע איזה מהלך הוא המהלך הטוב ביותר? עצרו וחשבו כיצד הייתם בוחרים את הצעד הבא. רוב האנשים היו בוחרים את המהלך שיעניק להם את מירב הנקודות, נכון? או שאם היו חושבים קדימה, הם היו בוחרים את הצעד אשר יקים מצב בו יוכלו לצבור עוד יותר נקודות. צורת החשיבה האחרונה היא הדרך שבה אלגוריתם המינימקס חושב. הוא צופה קדימה לכל מערכי הלוח העתידיים ועושה את הצעד שיוביל למרבית הנקודות.

קראתי לזה אלגוריתם חזרה, מכיוון שהוא מתחיל ביצירה והערכה ראשונית של כל מדינות הלוח העתידי עם הערכים הנלווים להן. המשמעות היא שהאלגוריתם ישחק את המשחק כמה שהוא צריך (ביצוע המהלכים לעצמו וגם ליריב) עד שכל תרחיש של המשחק ישחק. כדי לעקוב אחר כל מצבי הלוח (תרחישים), נוכל לצייר עץ (הסתכל בתמונות). העץ בתמונה למעלה הוא דוגמה פשוטה למשחק Connect 4. כל תצורה של לוח נקראת מצב לוח ולמקומה על העץ נקרא צומת. כל הצמתים בתחתית העץ הם מצבי הלוח הסופיים לאחר ביצוע כל המהלכים. ברור שחלק ממדינות הלוח טובות יותר לשחקן אחד מהשני. לכן, כעת עלינו לגרום ל- AI לבחור לאיזו מדינה לוח היא רוצה להגיע.

שלב 4: מינימקס: הערכת תצורות לוח

כדי לתת ערכים למצבי הלוח, עלינו ללמוד את אסטרטגיות המשחק שאנו משחקים: במקרה זה, האסטרטגיות של אותלו. מכיוון שהמשחק הזה הוא קרב של הפלת הדיסקים של היריב ושל הדיסקים שלך, מיקומי הדיסק הטובים ביותר הם אלה שהם יציבים ולא ניתן להפוך אותם. הפינה, למשל, היא המקום שבו כאשר מונחים דיסק לא ניתן לשנות אותו לצבע השני. לפיכך, נקודה זו תהיה בעלת ערך רב. עמדות טובות אחרות כוללות את צידי הלוח שיאפשרו לך לקחת הרבה אבנים. ישנן אסטרטגיות נוספות באתר זה.

כעת נוכל להקצות ערכים לתפקידים עבור כל מועצת מועצות מועצות. כאשר מיקום תפוס על ידי חתיכת ה- AI, אתה נותן מספר מסוים של נקודות בהתאם למיקום. לדוגמה, מצב לוח שבו היצירה של AI נמצאת בפינה, אתה יכול לתת בונוס של 50 נקודות, אבל אם זה היה במקום שלילי, היצירה עשויה להיות בעלת ערך 0. לאחר התחשבות בכל הערכים של את העמדות, אתה מקצה ללוח המדינה ערך. לדוגמה, אם ל- AI יש חתיכה בפינה מצב הלוח יכול לקבל ציון של 50 ואילו למצב לוח אחר עם חתיכת ה- AI באמצע יש ציון של 10.

ישנן דרכים רבות לעשות זאת, ויש לי שלוש היוריסטיקות שונות להערכת חלקי הלוח. אני מעודד אותך ליצור סוג היוריסטי משלך. העליתי ל- github שלי שלושה AIs שונים על ידי שלושה יוצרים שונים, עם שלושה היוריסטיקות שונות: Puma.py, erika5.py, nathanh.py.

שלב 5: אלגוריתם מינימקס: בחירת המהלך הטוב ביותר

עכשיו יהיה נחמד אם ה- AI יכול פשוט לבחור את כל המהלכים כדי להגיע למצב הלוח עם הציון הגבוה ביותר. אך זכור כי ה- AI גם בחר את המהלכים של היריב כאשר הוא יצר את כל מצבי הלוח ואם היריב חכם, הוא לא יאפשר ל- AI להגיע לניקוד הלוח הגבוה ביותר. במקום זאת, יריב חכם היה עושה את הצעד לגרום ל- AI להגיע למצב הלוח הנמוך ביותר. באלגוריתם אנו קוראים לשני השחקנים שחקן מקסימום ושחקן מזעור. ה- AI יהיה השחקן הממקסם מכיוון שהוא רוצה להשיג לעצמו את מירב הנקודות. היריב יהיה השחקן הממזער מכיוון שהיריב מנסה לבצע את הצעד שבו ה- AI מקבל את הנקודות הפחותות.

לאחר שנוצרו כל מצבי הלוח והוקצו ערכים ללוחות, האלגוריתם מתחיל להשוות את מצבי הלוח. בתמונות יצרתי עץ שייצג כיצד האלגוריתם יבחר את מהלכיו. כל פיצול בענפים הוא מהלך אחר שה- AI או היריב יכולים לשחק. משמאל לשורות הצמתים כתבתי אם השחקן המקסום או המזעור הולך. השורה התחתונה היא כל מדינות הלוח עם הערכים שלהן. בתוך כל אחד מהצמתים האלה יש מספר ואלו הציונים שאנו מקצים לכל אחד מהלוחות: ככל שהם גבוהים יותר, כך יש יותר טוב ל- AI.

הגדרות: צומת אב - צומת שנוצר או יוצר מתחתיו; מקור צמת הילדים - הצמתים המגיעים מאותו צומת אב

הצמתים הריקים מייצגים איזה מהלך ה- AI יעשה כדי להגיע למצב הלוח הטוב ביותר. זה מתחיל בהשוואת הילדים של הצומת השמאלי ביותר: 10, -3, 5. מכיוון שהשחקן המקסם היה מבצע את המהלך, הוא היה בוחר את המהלך שיעניק לו את מירב הנקודות: 10. לכן, לאחר מכן אנו בוחרים ומאחסנים את זה לנוע עם ציון הלוח ולכתוב אותו בצומת האב. כעת, כאשר 10 נמצא בצומת האב, כעת תור השחקנים הממזערים. עם זאת, הצומת שאנו היינו משווים אליו 10 הוא ריק, לכן עלינו להעריך את הצומת הראשון לפני שהשחקן הממזער יכול לבחור. אז נחזור לתורו של השחקן המקסם ביותר ומשווים את ילדי הצומת הסמוך: 8, -2. המקסום יבחר 8 ואנו כותבים זאת בצומת האב הריק. כעת, לאחר שהאלגוריתם סיים למלא את החללים הריקים לילדים של צומת שמעליו, השחקן המזעזע יכול להשוות את אותם ילדים - 10 ו -8 ולבחור 8. לאחר מכן האלגוריתם חוזר על תהליך זה עד למילוי העץ כולו. בסוף דוגמה זו, יש לנו את הציון 8. זהו מצב הלוח הגבוה ביותר שה- AI יכול לשחק בהנחה שהיריב משחק בצורה מיטבית. אז ה- AI יבחר את המהלך הראשון שמוביל למצב 8 הלוח, ואם היריב ישחק בצורה מיטבית, ה- AI צריך לשחק את כל המהלכים כדי להגיע למצב לוח 8. (עקוב אחר ההערות בתמונות שלי)

אני יודע שזה היה הרבה. אם אתה אחד מהסוגים שצריך שמישהו ידבר איתך כדי להבין משהו, הנה כמה סרטונים שצפיתי בהם כדי לעזור לי להבין את הרעיון מאחורי זה: 1, 2, 3.

שלב 6: אלגוריתם מינימקס: פסאודוקוד

לאחר שתבין את ההיגיון מאחורי האלגוריתם המינימקס, תסתכל על הפסאודוקוד הזה (הפונקציות שהם אוניברסליים לכל הקודים) מתוך ויקיפדיה:

הפונקציה minimax (צומת, עומק, maximizingPlayer) היא

אם עומק = 0 או הצומת הוא צומת מסוף

להחזיר את הערך ההוריסטי של הצומת

אם למקסם את Player אז

ערך: = −∞

עבור כל ילד של צומת

ערך: = מקסימום (ערך, מינימקס (ילד, עומק - 1, שקר))

ערך החזרה

אחר (* מזעור השחקנים *)

ערך: = +∞

עבור כל ילד של צומת

value: = min (ערך, מינימקס (ילד, עומק - 1, TRUE))

ערך החזרה

זוהי פונקציה רקורסיבית, כלומר היא קוראת לעצמה שוב ושוב עד שהיא מגיעה לנקודת עצירה. ראשית, הפונקציה לוקחת שלושה ערכים, הצומת, העומק, ותורו. ערך הצומת הוא המקום שבו ברצונך שהתוכנית תתחיל לחפש. העומק הוא עד כמה אתה רוצה שהתוכנית תחפש. לדוגמה, בדוגמת העץ שלי יש לו עומק של 3, מכיוון שהוא חיפש בכל מצבי הלוח לאחר 3 מהלכים. כמובן שהיינו רוצים שה- AI יבדוק כל מדינת לוח ויבחר זכייה מנצחת, אך ברוב המשחקים בהם יש אלפי אם לא מיליוני תצורות לוח, המחשב הנייד שלכם בבית לא יוכל לעבד את כל התצורות האלה. לכן, אנו מגבילים את עומק החיפוש של ה- AI ומכניסים אותו למצב הלוח הטוב ביותר.

פסאודוקוד זה משחזר את התהליך שהסברתי בשני השלבים הקודמים. עכשיו בואו ניקח את זה צעד קדימה ונתקן את זה בקוד פייתון.

שלב 7: יצירת AI שלך עם Ai_template.py

לפני שתסתכל על קוד ה- Minimax AI שלי, נסה לנסות ליצור AI משלך עם הקובץ ai_template.py והקוד הפסאודו עליו דיברנו בשלב האחרון. ישנן שתי פונקציות בתבנית ה- ai הנקראות: def minimax_min_node (לוח, צבע) ו- def minimax_max_node (לוח, צבע). במקום שהפונקציה מינימקס תקרא לעצמה רקורסיבית, יש לנו שתי פונקציות שונות, אשר קוראות זו לזו. כדי ליצור את ההיוריסטי להערכת מצבי לוח, יהיה עליך ליצור פונקציה משלך. יש פונקציות מוכנות מראש בקובץ othello_shared.py שתוכל להשתמש בהן לבניית ה- AI שלך.

ברגע שיש לך את ה- AI שלך, נסה להריץ אותו נגד, randy_ai.py. כדי להריץ שני אסי זה בזה, הקלד "python othello_gui.py (הכנס שם קובץ ai).py (הכנס שם קובץ).py" במסוף ה- mac או הקלד "הפעל othello_gui.py (הכנס שם קובץ ai).py (הכנס שם קובץ).py "וודא שאתה נמצא בספרייה הנכונה. כמו כן, עיין בסרטון שלי לשלבים המדויקים.

שלב 8: הזמן להילחם ב- AI

עכשיו קבל חבורה מחברי המחשב שלך וגרם להם לעצב AI משלהם! אז תוכל לערוך תחרות ולהוציא את הדוכס המלאכותי שלך החוצה. אני מקווה שגם אם לא תוכל לבנות AI משלך, הצלחת להבין כיצד פועל אלגוריתם המינימקס. אם יש לך שאלות, אל תהסס לפרסם שאלות בתגובות למטה.