Bài viết sưu tầm

CÂY TÌM KIẾM VÀ CÁC ĐẤU THỦ.

    Trong nhiều trò chơi trên máy tính có thể sinh ra các cây ứng với các nước đi của đấu thủ. Đặc thù của loại trò chơi này là chúng thể hiện sụ luân phiên giữa hai đấu thủ. Việc chọn các nước đi cho mỗi đấu thủ tương ứng với việc tìm kiếm cây. Để quyết định một trong những lựa chọn có thể được, người ta phải nhớ nhiều tình huống của bài toán. Tuy nhiên không thể lưu trữ quá nhiều thông tin và cũng không xử lý tất cả trạng thái của bài toán được. Do vậy người ta có thể dùng một chiến thuật phù hợp, chỉ quyết định trên tập tình huống hạn chế.

Thủ tục minimax.

    Xét trò chơi với hai đấu thủ Max và Min, Max tìm cách làm cực đại giá trị hàm ước lượng thông qua việc xác định gá trị hàm ước lượng ở mỗi nước đi có thể và chọn nước đi tương ứng với giá trị lớn nhất, tiếp theo đó đối thủ Min tìm cách làm cực tiểu giá trị ước lượng này.

     Diễn đạt theo ngôn ngữ đồ thị Và/Hoặc, Mỗi đỉnh tương ứng với nước đi của Max, giá trị của đỉnh này sẽ lấy giá trị cực đại của các giá trị của các đỉnh con và  đỉnh này quy ước gọi là đỉnh Hoặc. Một đỉnh tương ứng với nước đi của Min sẽ lấy giá trị cực tiểu trong số các giá trị đối với các đỉnh con của nó và đỉnh này quy ước gọi là đỉnh loại Và.

Ví dụ. Trò chơi caro trên bảng ô vuông. Đấu thủ Max đặt các dấu X, đấu thủ Min đặt dấu O. Ta xét ước lượng c(p) đối với mỗi thế cờ p như sau:

     c(p) = (số dòng, số cột, số đường chéo còn mở đới với Max) –

                 (số dòng, số cột, số đường chéo còn mở đối với min)

     Giả sử ta hạn chế kích thước 3x3 và ở mỗi nước đi, các đấu thủ tính trước hai nước. Nếu đấu thủ Max đi trước độc giả có thể kiểm tra, nước đi đầu tiên của Max sẽ là: