Tiểu Luận Thuật toán minimax

Mục Lục​ A. Thuật toán Minimax. 2
I. Thuật toán minimax. 2
II. Các Alpha-beta Cutoff Thủ tục. 4
B. Trò chơi tíc tắc toe. 9
I. Giới thiệu trò chơi 9
II. Mục tiêu trò chơi 9
III. Hướng giải quyết 9
IV. Thuật toán. 10
V. Giới thiệu chương trình. 15
1. Giao diện chính của chương trình. 15
2. Chức năng chính của chương trình. 15
3. Kết quả của trò chơi 17
C. Tài liệu tham khảo. 19


A. Thuật toán Minimax I. Thuật toán minimax Thuật toán minimax chứa đựng tất cả các khả năng của việc chuyển đổi các trạng thái từ 1 trạng thái được đưa ra và từ đó bao phủ lên các khoảng trống . Thuật toán này có ứng dụng trong trò chơi có khả năng chuyển đổi trạng thái từ 1 trạng thái thử nghiệm cho trước. Một ví dụ thông dụng là ta có thể bắt trước thuật toán minimax qua trò chơi Nim game Đây là 1 trò chơi giữa 2 người chơi.Trò chơi bắt đầu với 1 số lẻ các que.thông thường là 7 hoặc 9 .mỗi vị trí trên 1 dòng đơn được gọi là 1 cọc mốc .Mỗi người chơi sẽ lần lượt được đặt 1 cọc mốc để phá vỡ 2 mốc kia của đối phương trên 1 dòng.trò chơi sẽ kết thúc khi người kia ko đưa ra được bước đi thành công.Người nào ko đưa ra được bước đi thành cồng đầu tiên sẽ thua. Theo quy ước tiêu chuẩn chúng tôi đặt tên cho hai người chơi là MINIMIZER và MAXIMIZER NIM là 1 trò chơi phòng thủ vì vậy người chơi mở ở đây gọi là MINIMIZER Biểu đồ của của trò chơi NIM được biểu diễn như hình in fig. 4.12 (a) , phân ranh giới bước đi của MAXIMIZER và MINIMIZER