3.1 ຕົ້ນໄມ້ເກມ ແລະ ອັລກໍຣິທຶມ Minimax

ຜູ້ຫຼິ້ນ MAX ແລະ MIN, ການສົ່ງຄ່າຂຶ້ນຕົ້ນໄມ້.

ເກມສອງຄົນທີ່ມີຂໍ້ມູນຄົບ

ເຊັ່ນ XO, ໝາກຮຸກ, ໝາກຈີນ, ໝາກລ້ອມ (Go): ຜູ້ຫຼິ້ນ 2 ຄົນສະຫຼັບກັນ, ທັງສອງເຫັນກະດານທັງໝົດ. ເຮົາເອີ້ນຜູ້ຫຼິ້ນທີ່ເຮົາຊ່ວຍວ່າ MAX (ຢາກໃຫ້ຄະແນນສູງ) ແລະ ຄູ່ແຂ່ງວ່າ MIN (ຢາກໃຫ້ຄະແນນຕ່ຳ).

ຕົ້ນໄມ້ເກມເຕັມ (complete game tree)

ຮາກ = ສະຖານະປັດຈຸບັນ.
ແຕ່ລະ ຊັ້ນ ສະຫຼັບລະຫວ່າງ MAX ແລະ MIN.
ໃບ = ສະຖານະຈົບເກມ ມີຄະແນນ: ຊະນະ = +1, ແພ້ = −1, ສະເໝີ = 0.

ອັລກໍຣິທຶມ Minimax

ສົ່ງຄ່າຈາກໃບຂຶ້ນໄປຫາຮາກ:

ຈຸດຂອງ MAX = ຄ່າສູງສຸດ ຂອງລູກ.
ຈຸດຂອງ MIN = ຄ່າຕ່ຳສຸດ ຂອງລູກ.

def minimax(state, is_max):
    if state.is_terminal():
        return state.score()
    values = [minimax(c, not is_max) for c in state.children()]
    return max(values) if is_max else min(values)

MAX ເລືອກການເຄື່ອນທີ່ທີ່ໄປຫາລູກທີ່ມີຄ່າ minimax ສູງສຸດ — ໝາຍຄວາມວ່າ ສົມມຸດວ່າຄູ່ແຂ່ງຫຼິ້ນດີທີ່ສຸດສະເໝີ.

ບັນຫາ

ຕົ້ນໄມ້ເກມເຕັມ ໃຫຍ່ຫຼາຍ: ໝາກຮຸກມີປະມານ 35 ທາງເລືອກຕໍ່ຕາ ແລະ ເກມຍາວ ~100 ຕາ → 35¹⁰⁰ ຈຸດ! ດັ່ງນັ້ນເຮົາຕ້ອງ ຈຳກັດຄວາມເລິກ ແລະ ຕັດກິ່ງ (ບົດຕໍ່ໄປ).

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