27-01-2005, 13:20
|
|
|
|
חבר מתאריך: 20.06.03
הודעות: 5,616
|
|
פעם אחרונה שאני מעלה את זה לפורום...
עקרונות:
- עץ החיפוש הוא אותו עץ עבור שני השחקנים
- רמה זוגית מייצגת מהלך של שחקן A .
- רמה אי-זוגית מייצגת מהלך של שחקן B.
- כל שחקן, ברמה שלו, מחפש מצב מטרה שלו (לכל שחקן המטרה שונה)
- כל שחקן מעריך את המצבים על-פי הפונקציה ההיוריסטית שלו.
- המהלך הטוב ביותר עבור A מוביל למצב הגרוע ביותר עבורB .
- A מחפש את המהלך הטוב ביותר עבורו בהנחה שB- יחפש את המהלך הטוב ביותר עבורו.
עקרונות minimax:
- חפש את המעבר הבא הטוב ביותר עבורA , כך שעבור כל מעבר של B (בפרט המעבר הטוב ביותר עבור A) הוא ישפר את מצבו.
- בכל שלב, בדוק את ערכי כל הצאצאים, בחר את המקסימום אם זה תור של A ואת המינימום אם זה תור של B.
- בצע בדיקת ערכי מינימקס d צעדים קדימה.
- ייצר את כל הקודקודים עד רמה DFS) d)
- פעפע את ערכי מינימקס מהעלים.
דוגמת קוד (פסאודו) minimax:
קוד:
function MinMax-Decision(game) returns an operator
for each op in Operator[game] do
Value[op] := MinMax-Value(Apply(op,game),game)
end
return the op with the highest Value[op]
function MinMax-Value(state,game) returns a utility value
if Terminal-Test[game](state) then
return Utility[game](state)
else if MAX’s turn
return the highest MinMax-Value of Successors(state)
else //MIN’s turn
return the lowest MinMax-Value of Successors(state)
end
אלגוריתם נוסף היכול להתאים לך הוא NegaMax, דוגמה פה:
http://www.angelfire.com/wi/wickmann/cs002.html
כמו כן, תוכל למצא המון תוכניות ברשת מוכנות מהן תוכל ללמוד את העקרונות...
נערך לאחרונה ע"י fat fish בתאריך 27-01-2005 בשעה 13:24.
|