3.3. Minimax algoritmus

Cél: a támogatott játékosnak, -nek, egy adott állásban „elég jó” lépést ajánlani. Az algoritmus számára át kell adni

3.3.1. Az algoritmus fő lépései

  1. A játékfa állapotot szemléltető csúcsából kiinduló részének előállítása mélységig.

  2. A részfa leveleiben található állások jóságainak becslése a heurisztika segítségével: .

  3. Szintenként csökkenő sorrendben a részfa nem levél csúcsai jóságainak számítása: ha az csúcs gyermekei rendre , akkor

    Equation 3.. 


Javaslat: az állásból egy olyan lépést tegyen meg , amelyik az csúcs „jóság” értékével megegyező értékű gyermekébe vezet.


               function Minimax-lépés(A, kezdő, V, O, állapot, korlát, hJ)
  max ← −∞
  operátor ← Nil
  for 
               all o ∈ O do
    if Előfeltétel(állapot, o) then
      új-állapot ← Alkalmaz(állapot, o)
      v ← Minimax-Érték(A, kezdő, V, O, új-állapot, korlát − 1, hJ)
      if v ≥ max then
        max ← v
        operátor ← o
      end 
               if
    end 
               if
  end 
               for
  return operátor
end 
               function

            

               function Minimax-Érték(A, kezdő, V, O, állapot, mélység, hJ)
  if állapot ∈ V or mélység = 0 then
    return hJ(állapot)
  else 
               if Játékos[állapot] = J then
    max ← −∞
    for 
               all o ∈ O do
      if Előfeltétel(állapot, o) then
        új-állapot ← Alkalmaz(állapot, o)
        v ← Minimax-Érték(A, kezdő, V, O, új-állapot,mélység − 1, hJ)
        if v ≥ max then
          max ← v
        end 
               if
      end 
               if
    end 
               for
    return max
  else
    min ← ∞
    for 
               all o ∈ O do
      if Előfeltétel(állapot, o) then
        új-állapot ← Alkalmaz(állapot, o)
        v ← Minimax-Érték(A, kezdő, V, O, új-állapot,mélység − 1, hJ)
        if v ≤ min then
          min ← v
        end 
               if
      end 
               if
    end 
               for
    return min
  end 
               if

               end 
               function