3.2 Minimax ຈຳກັດຄວາມເລິກ ແລະ ຟັງຊັນປະເມີນ

ຕັດຕົ້ນໄມ້ທີ່ຄວາມເລິກ d ແລະ ໃຊ້ຟັງຊັນປະເມີນແທນຄະແນນຈົບເກມ.

Minimax ຈຳກັດຄວາມເລິກ

ແທນທີ່ຈະສ້າງຕົ້ນໄມ້ຮອດຈົບເກມ ເຮົາສ້າງພຽງ d ຊັ້ນ (ເຊັ່ນ ຄິດລ່ວງໜ້າ 4 ຕາ). ຈຸດທີ່ຄວາມເລິກ d ບໍ່ແມ່ນຈຸດຈົບເກມ → ຕ້ອງໃຊ້ ຟັງຊັນປະເມີນ eval(s) ຄາດຄະເນວ່າສະຖານະນັ້ນດີສຳລັບ MAX ເທົ່າໃດ.

def minimax(s, depth, is_max):
    if depth == 0 or s.is_terminal():
        return eval(s)
    vals = [minimax(c, depth - 1, not is_max) for c in s.children()]
    return max(vals) if is_max else min(vals)

ຟັງຊັນປະເມີນທີ່ດີ

• ຄິດໄລ່ ໄວ.
• ສອດຄ່ອງ ກັບໂອກາດຊະນະແທ້.
• ມັກເປັນ ຜົນບວກນ້ຳໜັກ: eval(s) = w₁·f₁(s) + w₂·f₂(s) + ...

ຕົວຢ່າງ XO: eval(s) = (ຈຳນວນແຖວ/ຖັນ/ເສັ້ນຂວາງທີ່ X ຍັງຊະນະໄດ້) − (ຈຳນວນທີ່ O ຍັງຊະນະໄດ້).

ຕົວຢ່າງໝາກຮຸກ: ຄ່າໝາກ — ບີ້ = 1, ມ້າ/ໂຄນ = 3, ເຮືອ = 5, ແມ່ = 9; ບວກກັບ ຄວາມຄ່ອງຕົວ ແລະ ຄວາມປອດໄພຂອງຂຸນ.

ຂໍ້ຄວນລະວັງ

• ຜົນກະທົບຂອບຟ້າ (horizon effect): ອັນຕະລາຍທີ່ຢູ່ເລິກກວ່າ d ຈະບໍ່ຖືກເຫັນ.
• ຍິ່ງ d ເລິກ ຍິ່ງຫຼິ້ນເກັ່ງ ແຕ່ຍິ່ງຊ້າ → ຕ້ອງການ Alpha-Beta.