Báo cáo Trí tuệ nhân tạo
Áp dụng giải thuật AlPha-beta trong game
cờ tướng
Giải thuật MiniMax
•
Là trò chơi đối kháng giữa 2 người Max và Min
•
Minimax tìm kiếm lời giải tối ưu thông qua hàm tìm kiếm cực
đại của Max và hàm cực tiểu hóa của Min
•
Sử dụng tri thức là 1 hàm lượng giá, khởi tạo = 0 ứng với khả
năng giành chiến thắng của Max và Min là như nhau
•
Cây trò chơi = Trạng thái bắt đầu + các nước đi hợp lệ
Cây trò chơi Minimax

Giải thuật Alpha-beta
•
“Nếu nó đã biết nó tồi thì đừng mất thời gian tìm hiểu xem nó
tồi đến đâu”


Tổng
giá trị
quân
mình
Tổng giá
trị quân
đối
phương
Hàm

4
152734 4.013 s
5
2753232 1’ 13s
6
6037273 2’ 39s
Nước Nút Thời gian
1
152734 3.668 s
2
99714 2.668 s
3
65471 2.071 s
4
87 708 3.419 s
5
82 126 2.675 s
6
41 044 2.043 s
Độ sâu 4
Tối ưu giải thuật
•
Hàm lượng giá
•
Thời gian chạy thuật toán
Demo chương trình