נושא: אלגוריתם minimax

נשלח בתאריך: 23 February 2009 בשעה 16:52 | IP רשוּם

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

קראתי את המאמר באתר על בינה מלאכותית ולא הבנתי איך אני אפשר לממש את

האלגוריתם MINIMAX על הדמקה:

• התחל מרמת העלים של עץ המשחק.

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

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

• בסיום התהליך מסומן שורש העץ בסימון. זהו הערך הטוב ביותר שיכול השחקן להשיג במשחק

אם היריב משחק אופטימלית.

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

אופטימלי נקבל תוצאה טובה יותר.

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

אם אפשר הסבר קצת ספציפי לדמקה..

TNX

נשלח בתאריך: 24 February 2009 בשעה 00:40 | IP רשוּם

א. לא בדיוק הבנתי מה מייצגים המספרים..

ב.אם אתה יכול לתת הסבר ספציפי לדמקה+אלגוריתם מתאים, כי בכל האתרים ההסבר הוא כללי ולא הבנתי אותו...

תודה מראש

נשלח בתאריך: 28 February 2009 בשעה 01:28 | IP רשוּם

שלום,

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

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

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

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

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

זהו זה, פשוט וקל.

שיהיה בהצלחה.

נשלח בתאריך: 28 February 2009 בשעה 01:40 | IP רשוּם

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

נשלח בתאריך: 24 March 2010 בשעה 16:22 | IP רשוּם

שלום לכולם,

אולי תוכלו לעזור לי ולהסביר על אלגוריתם הMinMax אבל על איקס עיגול...