Begreper & referanser

1blad_F = 3  # @param -10..102 3# Roten A er MAX. B og C er MIN-noder, og bladene leses fra venstre mot høyre.4barn = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F", "G", "H"]}5blad = {"D": 3, "E": 7, "F": blad_F, "G": 8, "H": 6}6er_max = {"A": True, "B": False, "C": False}7evaluert, kuttet = [], []8 9def alfabeta(node, alfa, beta):10    if node in blad:11        evaluert.append(node)12        return blad[node], None13    v, valgt = (float("-inf") if er_max[node] else float("inf")), None14    for i, b in enumerate(barn[node]):15        w, _ = alfabeta(b, alfa, beta)16        if (er_max[node] and w > v) or (not er_max[node] and w < v):17            v, valgt = w, b18        if (er_max[node] and v >= beta) or (not er_max[node] and v <= alfa):19            kuttet.extend(barn[node][i + 1:])  # kutt også ved likhet20            break21        if er_max[node]:22            alfa = max(alfa, v)23        else:24            beta = min(beta, v)25    return v, valgt26 27verdi, trekk = alfabeta("A", float("-inf"), float("inf"))28print(f"Minimax-verdi i roten: {verdi}")29print(f"Valgt trekk: {trekk}")30print(f"Blader evaluert med alfa-beta: {len(evaluert)} av {len(blad)}")31print(f"Kuttede noder: {', '.join(kuttet) if kuttet else 'ingen'}")

Prøv: sett blad_F fra 3 til 4, og se at linja Kuttede noder: går fra G, H til ingen, mens Minimax-verdi i roten: først endrer seg ved 4.

1import random2 3b = 3  # @param 2..54d = 4  # @param 2..65random.seed(4)6blader = [random.randint(0, 99) for _ in range(b ** d)]7nivaa = [blader]  # eksakte minimax-verdier nivå for nivå, MAX på partall dybde8for k in range(d - 1, -1, -1):9    nivaa.insert(0, [(max if k % 2 == 0 else min)(nivaa[0][i * b:(i + 1) * b]) for i in range(b ** k)])10 11def alfabeta(k, i, alfa, beta, orden, teller):12    if k == d:13        teller[0] += 114        return blader[i]15    barn = [i * b + j for j in range(b)]16    if orden == "perfekt":  # beste trekk først, slik de eksakte verdiene sier17        barn.sort(key=lambda x: nivaa[k + 1][x], reverse=(k % 2 == 0))18    elif orden == "tilfeldig":19        random.shuffle(barn)20    for x in barn:21        w = alfabeta(k + 1, x, alfa, beta, orden, teller)22        alfa, beta = (max(alfa, w), beta) if k % 2 == 0 else (alfa, min(beta, w))23        if alfa >= beta:  # kutt, også ved likhet24            break25    return alfa if k % 2 == 0 else beta26 27tilfeldig, perfekt = [0], [0]28alfabeta(0, 0, -1, 100, "tilfeldig", tilfeldig)29alfabeta(0, 0, -1, 100, "perfekt", perfekt)30print(f"Blader uten beskjæring: {b ** d}")31print(f"Blader, tilfeldig ordning: {tilfeldig[0]}")32print(f"Blader, perfekt ordning: {perfekt[0]}")33print(f"Teoretisk b^(d/2): {b ** (d / 2):.0f}")

Prøv: sett b til 5 og d til 6, og se at linja Blader, perfekt ordning: blir 249, nær to ganger Teoretisk b^(d/2):, mens tilfeldig ordning trenger nesten ti ganger så mange.

1alfabeta(node, alfa, beta):2    hvis node er terminal:3        returner nytte(node)4    hvis cutoff(node):5        returner eval(node)6    hvis MAX trekker i node:7        v = -uendelig8        for barn i barna(node):                  # venstre mot høyre9            v = max(v, alfabeta(barn, alfa, beta))10            hvis v >= beta:11                returner v                       # kutt: MIN over vil aldri slippe hit12            alfa = max(alfa, v)13    ellers:14        v = +uendelig15        for barn i barna(node):16            v = min(v, alfabeta(barn, alfa, beta))17            hvis v <= alfa:18                returner v                       # kutt: MAX over har noe minst like godt19            beta = min(beta, v)20    returner v21 22# start: alfabeta(rot, -uendelig, +uendelig)

Samme rekursjon som minimax, men med to grenser som sendes nedover. Kuttet skjer også ved likhet, og verdien som returneres etter et kutt, er en grense.