3.4. Negamax 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.4.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ének -szeresével megegyező értékű gyermekébe vezet.


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

            

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

               end 
               function