3.3 Minimax ກັບການຕັດກິ່ງ Alpha-Beta

ຕັດກິ່ງທີ່ບໍ່ມີຜົນຕໍ່ການຕັດສິນໃຈ ໂດຍໄດ້ຜົນຄືກັນກັບ Minimax.

ແນວຄິດ

ຫຼາຍກິ່ງໃນຕົ້ນໄມ້ເກມ ບໍ່ມີທາງ ປ່ຽນການຕັດສິນໃຈທີ່ຮາກໄດ້ → ບໍ່ຈຳເປັນຕ້ອງສຳຫຼວດ!

• α (alpha) = ຄ່າດີທີ່ສຸດທີ່ MAX ຮັບປະກັນໄດ້ແລ້ວ (ຂອບລຸ່ມ).
• β (beta) = ຄ່າດີທີ່ສຸດທີ່ MIN ຮັບປະກັນໄດ້ແລ້ວ (ຂອບເທິງ).
• ເມື່ອ α ≥ β → ຕັດກິ່ງ ທີ່ເຫຼືອ.

def alphabeta(s, depth, alpha, beta, is_max):
    if depth == 0 or s.is_terminal():
        return eval(s)
    if is_max:
        v = -INF
        for c in s.children():
            v = max(v, alphabeta(c, depth-1, alpha, beta, False))
            alpha = max(alpha, v)
            if alpha >= beta:
                break          # ຕັດ β
        return v
    else:
        v = +INF
        for c in s.children():
            v = min(v, alphabeta(c, depth-1, alpha, beta, True))
            beta = min(beta, v)
            if alpha >= beta:
                break          # ຕັດ α
        return v

ຕົວຢ່າງສັ້ນ

MAX ຢູ່ຮາກ. ລູກທຳອິດ (MIN) ໄດ້ຄ່າ 3 → α = 3. ລູກທີສອງ (MIN): ໃບທຳອິດມີຄ່າ 2 → MIN ຈະໄດ້ ≤ 2 < 3 → MAX ບໍ່ເລືອກທາງນີ້ແນ່ນອນ → ຕັດໃບທີ່ເຫຼືອ!

ປະສິດທິພາບ

• ຜົນລັບ ຄືກັນທຸກຢ່າງ ກັບ Minimax.
• ຖ້າຮຽງລູກດີ (ທາງທີ່ດີກ່ອນ) → ສຳຫຼວດພຽງ ~O(b^(d/2)) ຈຸດ → ຄິດໄດ້ ເລິກເປັນ 2 ເທົ່າ ໃນເວລາເທົ່າເກົ່າ.

🌳 ໃນຫ້ອງທົດລອງ ກົດ "ສຸ່ມຕົ້ນໄມ້" ແລ້ວປຽບທຽບຈຳນວນໃບທີ່ຖືກປະເມີນ ລະຫວ່າງ Minimax ແລະ Alpha-Beta.

🧪 ເປີດຫ້ອງທົດລອງສຳລັບບົດນີ້