הועלה לאתר:  
מספר עמודים: 47
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

בינה מלאכותית

ספר אלקטרוני מאת: ניר אדר

5.4.3. גיזום - ((α-β pruning

plot:\[\alpha  - \beta \] זוהי שיטה ל"גיזום" ענפים בעץ המשחק, המקיימת שעץ רגיל ועץ גזום יחזירו את אותו הערך.

האלגוריתם מוותר על פיתוח ענפים שאינם יכולים לשנות את ערך המינימקס של השורש.

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

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

חסמי החיתוך

חסם α: חסם החיתוך לצומת j מסוג Min הוא חסם תחתון הנקרא α. זהו הערך הגבוה ביותר שקים לעת עתה לכל אבות ה-Max של j. ניתן להפסיק את פיתוח j ברגע שהערך שלו שווה ל- או גדול מ-β.

חסם β: חסם החיתוך לצומתj מסוג Max הוא חסם עליון הנקרא β. זהו הערך הנמוך ביותר שקים לעת עתה לכל אבות ה-Min של j. ניתן להפסיק את פיתוחj ברגע שהערך שלו שווה ל- או גדול מ-β.

Minimax-ab(board, depth, type, alpha, beta)
  if depth=0 then return(evaluate(board))
  else
    if type=max then
      cur-max plot:\[ \leftarrow \] -infinity
      loop for b in succ(board)
        b-val plot:\[ \leftarrow \] minimax-ab(b,depth-1,min,alpha,beta)
        cur-max plot:\[ \leftarrow \] max(b-val, cur-max)
        alpha plot:\[ \leftarrow \] max(cur-max, alpha)
        if cur-max plot:\[ \geqslant \] beta then finish loop
      end loop
      return cur-max
    else (type=min)
      cur-min plot:\[ \leftarrow \] infinity
      loop for b in succ(board)
        b-val plot:\[ \leftarrow \] minimax-ab(b,depth-1,max,alpha,beta)
        cur-min plot:\[ \leftarrow \] min(b-val,cur-min)
        beta plot:\[ \leftarrow \] min(cur-min,beta)
        if cur-min plot:\[ \leqslant \] alpha then finish loop
      end loop
      return cur-min



הקריאה לפונקציה Minimax תעשה על ידי:

plot:\[{\text{Minimax - ab(board, D, max,  - }}\infty {\text{,  + }}\infty {\text{)}}\]

דוגמא לגיזום:

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

תגיות המסמך:

לפרק הקודם5.4.2. פרוצדורת מינימקס מעודכנת
לפרק הבא5.4.4. סידור יוריסטי
מאת: אוריה

אבל הוא עדיין לא נפתח...

מאת: אוריה

סליחה, זה ב-9

והקובץ יורד בסדר
מאת: ניר

אני עם אקרובט 8.1.1

הקובץ נפתח בלי שום בעייה
מאת: shoshan

אני מציע שתנסה שוב ב-acrobat 8

כי זה עובד לי בסדר גמור ב-Acrobat 9 וב-Foxit...

יכול להיות שהקובץ ירד לך לא טוב או חתוך או קטן מידי ?
מאת: אוריה

ב-5 זה נפתח

מאת: אוריה

לא נפתח

לא נפתח ב Acrobat Reader 8, הוא כותב שהקובץ לא נתמך או שהוא ניזוק.
שיתוף:
| עוד