מבנה
נתונים ואלגוריתמים
באופן דומה מכל
אחד מהצמתים הללו קיימות הסתעפויות נוספות לצמתים בנים. על אלגוריתם המשחק, למעשה,
לחפש עלה בעץ המתאים לתוצאה הרצויה (goal state) - בדרך כלל המטרה הינה למצוא
את המסלול הקצר ביותר ממצב ההתחלה למצב הסיום (אם קיים מצב שכזה). בדרך זו ניתן
לבנות תוכנות למשחקים כגון puzzle-8 וקוביה הונגרית.
קיימים מספר
אלגוריתמים לחיפוש, כגון: חיפוש לרוחב (BFS), חיפוש לעומק (DFS), A* -
עליהם לא נרחיב.
המצב שונה
במשחקים בהם ישנה התמודדות של שחקן אחד כנגד השני (כגון: איקס-מיקס-דריקס, שחמט
ודמקה).
במצב כזה בהנחה
שכל שחקן ינקוט בצעד הטוב ביותר האפשרי מבחינתו, הרי שבכל פעם שיגיע תורך תבחר
הצעד הטוב ביותר, ואילו כאשר יגיע תורו של יריבך הוא יבחר את הצעד הטוב ביותר
מבחינתו שהינו גם (תיאורטית) הצעד הגרוע ביותר מבחינתך. גם במקרה זה ניתן לתאר את
מהלך המשחק כעץ, כאשר ברמה שבה תורו של השחקן לשחק נבחר צומת הבן בעל הערך
המקסימלי, וברמה שבה תור היריב לשחק נבחר הצומת הבן בעל הערך המינימלי. אלגוריתם
זה נקרא MinMax.
על פי אלגוריתם
זה נתונים הערכים בעלים שהם למעשה המצבים הסופיים, ומהם יש לעלות במעלה
העץ עד לשורש
תוך חישוב הצמתים ברמות השונות.
|
|
|
במשחקים בהם
קיימות הסתעפויות רבות ומספר עצום של אפשרויות, כגון בשחמט, לא ניתן להגיע לעלים
(מצבי הסיום)
אשר מהם ומעלה יש לחשב את ערכי הצמתים עד לשורש. לכן במשחקים כגון אלו
משתמשים בשיטות
יוריסטיות לחישוב ערכים של צמתים אשר מהם ומעלה מחשבים על פי האלגוריתם.
תוכנית נאיבית
תנסה לשחק משחק כגון שחמט באופן הבא:
א.
בדיקה של מספר
הצעדים אשר יכולים להתבצע מהמצב הנוכחי.
ב.
עבור כל צעד:
1)
יישום הצעד
למיקום הנוכחי,
2)
חישוב ה"ניקוד"
עבור המיקום החדש,
3)
אם הגענו לעומק
החיפוש ה"מקסימלי", החזר את החזר את הערך הזה כערך עבור המהלך.
4)
אחרת קרא באופן
רקורסיבי לתוכנית עם מיקום חדש.
ג.
בחר את המהלך
עם הניקוד הגבוה ביותר והחזר את הערך שלו ואת הפעלת הצעד לפונקציה הקוראת.
בגלל שישנם
לפחות 20 צעדים אפשריים בכל מצב נתון בשחמט, על מנת לחפש בעומק m יש צורך
ב- ~20m צעדים. בגלל ששחקן אנושי טוב מסתכל בדרך כלל על 10 או
יותר צעדים קדימה, האלגוריתם
הפשוט יהיה
איטי ביותר גם עבור יכולות של המחשבים המודרניים המהירים.
בכל אופן, ניתן
להקטין בצורה דרמטית את מספר הצעדים אשר יש צורך לסרוק - דבר המאפשר
למחשב לסרוק
עמוק יותר בזמן סביר, וכפי שהאירועים האחרונים הראו, לאפשר למחשב להיות יריב
הולם אף לשחקני
השחמט האנושיים הטובים ביותר.
אלגוריתם זה
מקטין את מספר הצעדים אותם צרכים לבדוק על ידי "קיצוץ" אזורים של עץ
המשחק, אשר
לא יכולים
ליצור תוצאות טובות יותר מאשר התוצאות אשר כבר הושגו באותו אזור של העץ אשר כבר
נסרק.
|
|
|
חזור ל: תוכן עניינים