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

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

5.4.2. פרוצדורת מינימקס מעודכנת

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

Minimax(board, depth, type)
; If we reached the depth limit, use the heuristic function
; to rank the board.
if depth=0 then
    return(evaluate(board))
else

    ; If it is our turn now, make the choice that will
    ; give us the maximum result
    if type=max then
      cur-max $plot:\[ \leftarrow \]$ -infinity
      loop for b in succ(board)
        b-val $plot:\[ \leftarrow \]$ minimax(b, depth-1, min)
        cur-max $plot:\[ \leftarrow \]$ max(b-val, cur-max)
      end loop
      return cur-max

    ; If it is the enemy turn, choose the best board for him.
    else (type=min)
      cur-min $plot:\[ \leftarrow \]$ infinity
      loop for b in succ(board)
        b-val $plot:\[ \leftarrow \]$ minimax(b, depth-1, max)
        cur-min $plot:\[ \leftarrow \]$ min(b-val,cur-min)
      end loop
      return cur-min