עקרונות:

• עץ החיפוש הוא אותו עץ עבור שני השחקנים
  • רמה זוגית מייצגת מהלך של שחקן 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 ]