חיפוש יריב הוא חיפוש, שבו אנו בוחנים את הבעיה המתעוררת כאשר אנו מנסים לתכנן לפני העולם וסוכנים אחרים מתכננים נגדנו.

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

סוגי משחקים ב-AI:

מידע מושלם:משחק עם המידע המושלם הוא זה שבו סוכנים יכולים להסתכל על הלוח המלא. לסוכנים יש את כל המידע על המשחק, והם יכולים לראות גם אחד את השני זז. דוגמאות הן שחמט, דמקה, גו וכו'.מידע לא מושלם:אם במשחק אין לסוכנים את כל המידע על המשחק ואינם מודעים למה שקורה, משחקים מסוג זה נקראים משחק עם מידע לא מושלם, כגון טיק-tac-toe, Battleship, blind, Bridge וכו'.משחקים דטרמיניסטיים:משחקים דטרמיניסטים הם אותם משחקים העוקבים אחר דפוס ומערכת חוקים קפדנית למשחקים, ואין אקראיות הקשורה אליהם. דוגמאות הן שחמט, דמקה, גו, טיק-טק וכו'.משחקים לא דטרמיניסטיים:לא דטרמיניסטיים הם אותם משחקים שיש להם אירועים בלתי צפויים שונים ויש להם גורם של סיכוי או מזל. גורם זה של סיכוי או מזל מוצג על ידי קוביות או קלפים. אלה הם אקראיים, וכל תגובת פעולה אינה קבועה. משחקים כאלה נקראים גם משחקים סטוכסטיים.
דוגמה: שש בש, מונופול, פוקר וכו'.

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

משחק סכום אפס

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

משחק סכום אפס: חשיבה משובצת

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

• מה לעשות.
• איך להחליט על המהלך
• צריך לחשוב גם על היריב שלו
• גם היריב חושב מה לעשות

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

פורמליזציה של הבעיה:

ניתן להגדיר משחק כסוג של חיפוש ב-AI אשר ניתן לפורמל של המרכיבים הבאים:

מצב התחלתי:זה מפרט איך המשחק מוגדר בהתחלה.שחקן(ים):זה מציין איזה שחקן עבר במרחב המדינה.פעולות:זה מחזיר את סט המהלכים המשפטיים במרחב המדינה.תוצאות, א:זהו מודל המעבר, המפרט את התוצאה של מהלכים במרחב המדינה.מבחן מסוף:מבחן מסוף נכון אם המשחק נגמר, אחרת הוא שקר בכל מקרה. המצב שבו המשחק מסתיים נקרא מצבים מסוף.כלי שירות(ים, p):פונקציית שירות נותנת את הערך המספרי הסופי עבור משחק שמסתיים במצבי מסוף s עבור שחקן p. זה נקרא גם פונקציית תשלום. עבור שחמט, התוצאות הן ניצחון, הפסד או תיקו וערכי התמורה שלו הם +1, 0, ½. ולגבי מטקות, ערכי השירות הם +1, -1 ו-0.

עץ המשחק:

עץ משחק הוא עץ שבו צמתים של העץ הם מצבי המשחק וקצוות העץ הם המהלכים של השחקנים. עץ המשחק כולל מצב התחלתי, פונקציית פעולות ופונקציית תוצאה.

דוגמה: עץ המשחק Tic-Tac-Toe:

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

• יש שני שחקנים MAX ו-MIN.
• לשחקנים יש תור חלופי והם מתחילים עם MAX.
• MAX ממקסם את התוצאה של עץ המשחק
• MIN ממזער את התוצאה.

הסבר לדוגמה:

• מהמצב ההתחלתי, ל-MAX יש 9 מהלכים אפשריים כשהוא מתחיל ראשון. MAX מקום x ו-MIN מקום o, ושני השחקנים משחקים לחילופין עד שנגיע לצומת עלה שבו לשחקן אחד יש שלושה ברציפות או שכל המשבצות מלאות.
• שני השחקנים יחשבו כל צומת, מינימקס, ערך המינימקס שהוא הכלי הטוב ביותר שניתן להשיג מול יריב אופטימלי.
• נניח ששני השחקנים מודעים היטב לתקתק ומשחקים את המשחק הטוב ביותר. כל שחקן עושה כמיטב יכולתו כדי למנוע מאחד אחר לנצח. MIN משחק נגד מקס במשחק.
• אז בעץ המשחק, יש לנו שכבה של Max, שכבה של MIN, וכל שכבה נקראת בשם Ply . מקסימום מקום x, ואז MIN שם o כדי למנוע מ-Max לנצח, והמשחק הזה ממשיך עד הצומת הטרמינל.
• בזה או MIN ניצחונות, MAX ניצחונות, או שזה תיקו. עץ המשחק הזה הוא כל מרחב החיפוש של האפשרויות ש-MIN ו-MAX משחקים טיק-טק ומתחלפים לסירוגין.

מכאן שחיפוש יריב אחר נוהל המינימקס פועל באופן הבא:

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

בעץ משחק נתון, ניתן לקבוע את האסטרטגיה האופטימלית מתוך ערך המינימקס של כל צומת, אותו ניתן לכתוב כ-MINIMAX(n). MAX מעדיף לעבור למצב של ערך מקסימלי ו-MIN מעדיף לעבור למצב של ערך מינימלי אז: