Negamax
Această intrare sau secțiune despre matematică nu citează sursele necesare sau cei prezenți sunt insuficienți . |
Negamax este o mică variație a algoritmului minimax care se bazează pe proprietățile jocurilor cu sumă zero cu doi jucători.
Prin definiție, valoarea poziției jucătorului A într-un anumit joc este negarea valorii poziției jucătorului B. Astfel, jucătorul care trebuie să se deplaseze va căuta o mișcare care să maximizeze negarea valorii poziției rezultată din mutare: prin definiție, această poziție a succesorului trebuie să fi fost evaluată de adversar. Veridicitatea acestei afirmații este menținută indiferent dacă A sau B trebuie să se miște. Aceasta înseamnă că un singur calcul poate fi utilizat pentru a evalua toate pozițiile. Aceasta este o simplificare în ceea ce privește minimaxul, care necesită A pentru a alege mișcarea cu cea mai mare valoare a secvenței și B cu minimul.
Negamax nu trebuie confundat cu negascout , o variantă modernă a agoritmului de tăiere alfa-beta descoperită în anii 1980, devenind ea însăși o versiune mai avansată de minimax sau negamax.
Multe motoare de căutare adversare sunt programate folosind o formă a algoritmului negamax.
Pseudo cod
Mai jos este pseudocodul pentru o căutare negamax cu adâncime limitată utilizând tăierea alfa-beta.
funcția negamax (nod, adâncime, α, β)
dacă nodul este un nod terminal sau adâncimea = 0
returnează valoarea euristică a nodului
altceva
pentru fiecare fiu
α: = max (α, -negamax (fiul, adâncimea-1, -β, -α))
{ceea ce urmează, dacă este verificat, constituie tăierea alfa-beta}
dacă α ≥ β
retur β
întoarce α
La primul apel, argumentele α și β trebuie setate respectiv la cele mai mari și mai mici valori posibile pentru fiecare nod.
