Ứng dụng thuật toán Minimax viết AI cho trò chơi Tic Tac Toe

Ứng dụng thuật toán Minimax viết AI cho trò chơi Tic Tac Toe

Trong bài viết này, mình sẽ giải thích về thuật toán minimax mình sử dụng để viết trò chơi này. Nhưng trước hết mình nên giải thích cho mọi người hiểu về AI là gì nhỉ!

AI(Artificial Intelligence) có khá nhiều định nghĩa. Chúng ta hãy xem nguồn gốc về định nghĩa AI để hiểu rõ hơn.

Vào tháng 10/1950, nhà bác học Alan Turning đã suy nghĩ về một chương trình AI. Ông tự hỏi liệu máy tính có thể suy nghĩ như con người không? Ông đưa ra một trò chơi như sau: Trò chơi gồm có 3 thành viên tham gia, gồm hai người và một máy tính. Một người sẽ làm người đặt ra câu hỏi, và hai thành viên kia sẽ trả lời (dưới dạng ẩn danh). Trò chơi diễn ra đến khi người đặt câu hỏi không phân biệt được đâu là câu trả lời của người, đâu là câu trả lời của máy, thì khi đó máy tính coi như là đã “suy nghĩ” như con người.

Thế chúng ta có thể hiểu rằng, AI xem như là trí thông minh của máy tính, xây dựng bằng cách mô phỏng lại suy nghĩ của con người, cách xử lí vấn đề giống con người. Trong ngành khoa học máy tính, người ta định nghĩa rằng: AI là những thiết bị có khả năng cảm nhận được môi trường xung quanh và lựa chọn giải pháp với tỉ lệ thành công cao để đạt được mục đích của nó. (Wikipedia).

Thử áp dụng AI vào trong cờ caro, ta có định nghĩa về AI trong trò đánh caro như sau: AI trong trò caro là một cách đưa ra các giải pháp và lựa chọn giải pháp có tỉ lệ thắng cao nhất.

Thật vậy, thuật toán Minimax cũng đưa ra các bước đi, đánh giá xem bước đi nào có tỉ lệ thắng cao nhất, và lựa chọn nó. Nó cũng dựa trên trò chơi Zero-sum (trò chơi có tổng bằng 0), hiểu cơ bản là khi người chơi thứ nhất muốn cộng điểm, thì người chơi thứ hai sẽ cố gắng trừ số điểm đó xuống.

Trò Tic tac toe có 3^9 = 19683 trường hợp, đủ để máy tính có thể xử lí, nên ta có thể dùng Minimax xét các trường hợp được. Nhưng nếu những trò có nhiều trường hợp hơn (như cờ vua), ta phải dùng thêm phương pháp Alpha-beta pruning (cắt tỉa alpha-beta) để giảm thiểu số trường hợp cần xử lí.

Chúng ta hãy cùng xem các bước mà minimax làm trong trò caro. (Phần hack não sắp bắt đầu, chuẩn bị tinh thần nhé 😂)

Giả sử chúng ta có bàn cờ như sau:

Với lượt X là lượt của máy, và lượt O là lượt của người. Đến lượt máy tính đi, lúc này thuật toán minimax sẽ chạy như sau:

Trước khi đọc sơ đồ, ta có các quy ước sau:

1.                    Với bàn cờ WIN - phần thắng dành cho X (máy), ta sẽ cộng 10 điểm; Với bàn cờ LOSE - phần thắng dành cho O (người), ta sẽ trừ 10 điểm; Với bàn cờ DRAW - hòa, ta sẽ nhận 0 điểm.

2.                    Với lượt của X, ta luôn tìm bàn cờ nào có điểm số cao nhất; Với lượt của O, ta luôn tìm bàn cờ nào có điểm số thấp nhất.

Xong. Bây giờ chúng ta sẽ giải thích từ từ như sau.

Với bàn cờ (1), tới lượt của X(máy) ta có 3 lựa chọn để đi: (2), (3), (4). Với lựa chọn (4), ta dành phần thắng nên số điểm sẽ là 10. Còn lựa chọn (2) và (3) thì chưa rõ ràng, ta tiếp tục đào sâu để tìm thêm.

Lựa chọn (2), tới lượt của O(người): Ta có 2 lựa chọn (5) và (6). Cả 2 lựa chọn khi đi sâu xuống depth = 3, ta được số điểm của (9) và (10) lần lượt là +7 và 0 (Mình sẽ giải thích lí do tại sao là +7 mà không phải +10 sau). Khi truyền lên trên, bàn cờ (5) và (6) có số điểm cũng lần lượt là +7 và 0. Tại vị trí (5)(6) này, là lượt của min (lượt O – người), ta sẽ lựa chọn bàn cờ có số điểm thấp nhất. (Lí do giống như trong trò chơi có tổng bằng không đã nói, ở lượt đối thủ, họ luôn muốn giảm số điểm của mình xuống). Từ đó, bàn cờ (2) nhận giá trị là 0.

Lựa chọn (3), tới lượt của O(người): Ta có 2 lựa chọn (7) và (8). Lựa chọn (7) chúng ta bị thua và sẽ trừ điểm xuống -8; còn lựa chọn (8) ta nhận được số điểm là 0 (như hình). Với 2 lựa chọn (7)(8), số điểm tương ứng là -8 và 0, và với lượt chơi là min, ta chọn cho bàn cờ (3) số điểm thấp nhất là -8.

Cả 3 bàn cờ (2)(3)(4) lần lượt có số điểm là 0, -8 và 9. Vì đây là lượt của ta và ta có xu hướng lựa chọn bàn cờ có số điểm cao nhất +9, ta sẽ chọn bàn cờ (4).

Giải thích: Một dấu chấm hỏi lớn đặt ra là: Tại sao có trường hợp thắng (4) là +9 mà không phải +10, trường hợp thua (7) là -8 mà không phải là -10. Mình sẽ cho các bạn thấy:

Nếu cùng là bàn cờ thắng, nhưng nếu càng xuống sâu (càng đánh lâu), thì tỉ lệ thắng càng thấp, vì mỗi lần xuống là một loạt các nhánh khác (có thể thắng, có thể hòa, có thể thua). Nếu là bạn thì bạn sẽ chọn lựa chọn nào mà ít sâu hơn phải không? Nên số điểm chiến thắng sẽ được tính bằng 10 – depth, càng sâu thì số điểm sẽ càng giảm.

Còn ngược lại thì như sau:

Giữa lựa chọn có thể khiến cho đối thủ thắng ngay lập tức và lựa chọn câu thời gian để tìm cơ hội chiến thắng thì bạn sẽ chọn thế nào, tất nhiên là câu giờ rồi nhỉ. Càng câu thời gian, tức với các bàn thua càng đi xuống sâu, thì càng có lợi cho ta, nên giá trị của trận thua sẽ được tính bằng -10 + depth.

Như thế coi như chúng ta đã hoàn thành trò chơi Tic tac toe này rồi.

Về phần code thì mình sẽ không bàn đến vì code của mình chưa tham khảo của ai hết, mà suy nghĩ còn non nên còn nhiều cái dư thừa quá 😁.

Nội dung bài viết thuộc về Lê Công Diễn.

Người viết: Lê Công Diễn

Mang đi nhớ ghi nguồn