Home / Tài liệu CNTT / Thuật Toán / Ứng dụng thuật toán Minimax trong game Tic-Tac-Toe (Cờ Caro)

Ứng dụng thuật toán Minimax trong game Tic-Tac-Toe (Cờ Caro)

Bài viết này lần đầu được đăng lên trang Never Stop Building bởi Jason Fox vào 13/12/2013 tại http://neverstopbuilding.com/minimax. Dưới đây chỉ là bài dịch của bài viết trên.

Mình vừa mới làm ra một trò chơi Tic Tac Toe (tương tự như Caro nhưng chỉ có 9 ô) “bất khả chiến bại”. Tuy dự án trên khá đơn giản, nhưng nó đã giúp mình tìm hiểu thêm về nhiều thứ xoay quanh về giải thuật và lập trình. Nếu bạn muốn chiêm ngưỡng, hay đơn giản là không tin, bạn có thể thử chơi một vài ván Tic Tac Toe ở đây.

Để tạo ra một chương trình Tic Tac Toe hoàn hảo, một thuật toán có thể tính toán tất cả nước đi và xác định nước đi có lợi là thiết yếu. Sau một lúc tìm hiểu về các thuật toán, thuật toán Minimax là lựa chọn hợp lý nhất.

Phải mất một lúc mình mới hiểu được nguyên tắc của thuật toán Minimax và ứng dụng nó vào trong trò chơi của mình. Mình có lướt qua một số ví dụ trên mạng kèm theo chú thích, nhưng theo mình không có ví dụ nào thật sự dễ hiểu như quá trình mình làm project này. Vì vậy, mình mong bài viết này có thể giúp các bạn hiểu rõ hơn về thuật toán Minimax, đồng thời chiêm ngưỡng vẻ đẹp mà thuật toán mang lại.

Miêu tả một trò chơi Tic Tac Toe hoàn hảo

Vậy thế nào là một trò chơi Tic Tac Toe hoàn hảo? Một trò chơi Tic Tac Toe “bất khả chiến bại” được định nghĩa rằng:

Nếu mình chơi một cách hoàn hảo, thì trong tất cả các ván Tic Tac Toe mình sẽ Thắng hoặc Hòa, và nếu mình chơi với một người chơi hoàn hảo khác, thì cả hai sẽ luôn luôn Hòa.

Vậy làm thế nào để ta có thể miêu tả ba kết quả Thắng, Thua, và Hòa để chương trình có thể hiểu và quyết định nước đi? Trong trường hợp này, mình sẽ lần lượt gán điểm số vào ba tình huống của trò chơi:

  • Mình thắng. Ngon đấy! Mình được 10 điểm rồi.
  • Mình thua. Mất 10 điểm (vì người chơi kia đã lấy 10 điểm).
  • Mình hòa. Huề cả làng. Điểm số giữ nguyên.

Nhờ vào việc gán các điểm tương ứng, chúng ta có thể xác định số điểm của một ván bất kỳ.

Ví dụ

Để hiểu rõ hơn, hãy lấy một ví dụ từ một ván Tic Tac Toe gần tới hồi kết, đồng thời là lượt đi của mình (mình là X). Mục tiêu của mình rõ ràng là tối ưu hóa điểm số, đồng nghĩa với việc chiến thắng và ra về với 10 điểm.

Hình ở trên miêu tả ba nước đi mình có thể đi khi rơi vào một nước như vậy, và rõ ràng một trong ba nước sẽ làm mình thắng trò chơi và có 10 điểm. Và nếu mình không đi nước đó, thì O sẽ cướp lấy cơ hội và chiến thắng trò chơi này. Cơ mà mình không muốn O thắng, nên mục tiêu của mình, với cơ hội là người đi trước trước khi O lội ngược dòng, là lựa nước đi dẫn tới kết quả thắng.

Còn O thì sao?

Chúng ta biết gì về O? Giả định O muốn chiến thắng trò chơi cũng như chúng ta, O đương nhiên sẽ chọn nước đi bất lợi cho chúng ta nhất (có lợi cho O), đồng nghĩa với việc lựa nước đi tối thiểu hoá điểm số của chúng ta. Hãy nhìn trò chơi dưới góc nhìn của O ở hai trường hợp ở trên, khi mà chúng ta không thể thắng ngay lập tức như trường hợp ở trên.

Rõ ràng O sẽ chọn nước đi để chúng ta bị trừ 10 điểm.

Miêu tả thuật toán Minimax

Chìa khóa của thuật toán Minimax chính là lượt chơi qua lại giữa hai người chơi, khi mà cả hai đều mong muốn nước đi có điểm cao nhất. Điểm số của từng nước đi của ta được quyết định bởi đối thủ, người quyết định nước nào sẽ mang lại điểm số nhỏ nhất cho chúng ta. Ngược lại, điểm số của đối thủ lại được quyết định bởi chúng ta, người tìm cách tối ưu hóa điểm số. Nói ngắn gọn thì thuật toán Minimax trong trò chơi Tic Tac Toe chính là thử hết các nước đi có thể cho đến khi trò chơi kết thúc.

Giả dụ đang tới lượt X, thì trò chơi sẽ có quy trình như sau:

  • Nếu trò chơi kết thúc, trả về điểm số dưới góc nhìn của X.
  • Không thì thu thập các nước đi có thể ở lượt mới.
  • Tạo một mảng (một cấu trúc dữ liệu bao gồm một nhóm các giá trị phần tử hoặc biến) chứa các điểm số tương ứng với các nước nêu trên.
  • Đối với từng tình huống, cập nhật điểm số tính bởi thuật Minimax vào mảng nêu trên.
  • Nếu lượt đi là của X, trả về điểm số lớn nhất trong mảng.
  • Nếu lượt đi là của O, trả về điểm số nhỏ nhất trong mảng.

Bạn sẽ để ý rằng thuật toán Minimax là một thuật toán đệ quy – sự qua lại giữa lượt đi của hai người chơi cho đến khi số điểm cuối cùng được tìm thấy.

Hãy cũng xem qua nguyên lý của thuật toán đối với một cây nước đi đầy đủ và chỉ ra làm sao mà nước đi dẫn tới chiến thắng được lựa chọn:

  • Tình huống 1 là lượt đi của X. X tạo ra 3 tình huống 2, 3, và 4 và áp dụng thuật toán Minimax trên từng tình huống.
  • Tình huống 2 trả về điểm +10 cho mảng điểm của tình huống 1, bởi vì trò chơi đã đến hồi kết.
  • Tình huống 3 và 4 chưa tới hồi kết nên lần lượt tạo ra các tình huống 5, 6 và 7, 8 đồng thời áp dụng thuật toán Minimax.
  • Tình huống 5 trả về điểm -10 cho mảng điểm của tình huống 3, tương tự với tình huống 7 trả về điểm -10 cho mảng 4.
  • Tình huống 6 và tình huống 8 chỉ tạo ra một tình huống, đồng thời là tình huống cuối cùng dẫn tới trò chơi kết thúc với X là người thắng, nên cả hai sẽ lần lượt trả về điểm +10 cho mảng 3 và 4.
  • Bởi vì sau tình huống thứ 3 và thứ 4 là lượt đi của O, nên O sẽ đi nước đi dẫn tới điểm số thấp nhất. Bởi vì cả hai tình huống đều có mảng chứa +10 và -10, nên tình huống 3 và 4 sẽ trả về -10 cho mảng điểm của tình huống 1 (điểm thấp nhất).
  • Trong mảng điểm của tình huống 1 sẽ chứa các điểm lần lượt là +10, -10, -10. Vì tình huống 1 là lượt đi của X nên X sẽ lựa nước đi có điểm cao nhất, nghĩa là chọn nước đi dẫn tới số điểm +10 – nước đi tương tự tình huống thứ 2.

Tuy đơn giản, nhưng quá trình trên cần rất nhiều công sức. Bởi vậy nên chúng ta mới cần máy tính để chạy chương trình thay cho chúng ta.

Tới đây, mình mong rằng bạn đã hiểu về nguyên lý hoạt động của thuật toán Minimax khi lựa chọn nước đi phù hợp. Dưới đây là một đoạn pseudo code để các bạn tham khảo:

Người thắng được +10, người thua bị -10, và hòa là 0. Bạn sẽ để ý rằng người chơi là X hay O không quan trọng, mà quan trọng là lượt đi của ai.

Và dưới đây là là ứng dụng của thuật toán Minimax đầy đủ; lưu ý rằng nước đi (move) có dạng hàng/cột, ví dụ như [0, 2] chính là hàng thứ 0, cột thứ 2, đồng thời là ô phải trên cùng.

Khi thuật toán này được áp dụng trong một lớp PerfectPlayer , nước đi hoàn hảo nhất được lưu trữ trong biến @choice , biến được sử dụng để trả lại các tình huống mà người chơi đã đi.

Tuy vậy, trong quá trình test trò chơi, mình chợt nhận ra một điều thú vị rằng thuật toán này có đôi chút “bi quan”. Nghĩa là, khi đặt trò chơi vào một tình huống hiển nhiên thua, thì trò chơi sẽ chọn một nước đi “bi quan” – thua ngay lập tức. Thuật toán còn có thể hiểu rằng: “Này anh bạn, đằng nào tôi cũng thua nên thua ở nước đi kế tiếp hay nước đi thứ 6 chả quan trọng đâu.”

Mình phát hiện ra điều này khi đụng độ một tình huống có sẵn, hoặc là một lỗi trong quá trình mình lập trình trò chơi. Mình mong chờ máy tính ít nhất phải đứng lên chặn đường thắng của mình, nhưng không:

Hãy xem những gì sẽ xảy ra bằng cây nước đi (Lưu ý, mình đã lược bỏ vài tình huống để cho ví dụ đỡ rối hơn):

  • Giả định tình huống 1 khi cả hai cùng chơi một cách hoàn hảo, và O là máy tính. O chọn bước đi như tình huống 5 và thua ngay lập tức khi X chọn như tình huống 9.
  • Nhưng nếu O chặn X như tình huống 3, X sẽ chặn O như tình huống 7.
  • Điều này dẫn đến chiến thắng chắc chắn cho X như tình huống 10 và 11. Như vậy, bất kể O đi nước nào trong tình huống 7, X vẫn thắng.

Bởi lẽ chúng ta đang chạy vòng lặp cho từng ô trống, từ trái sang phải, từ trên xuống dưới, tất cả nước đi đều tương đương nhau và dẫn tới phần thua cho O, nước đi trong tình huống 5 được chọn bởi vì nó là nước đi cuối cùng trong tất cả các nước đi có thể chứa trong mảng move ở tình huống 1. Thứ tự của các phần tử trong mảng lần lượt là: [[0, 0], [0, 2], [1, 0], [1, 1]].

Vậy một bậc thầy về Tic Tac Toe sẽ làm gì trong tình huống này?

Chơi kiên cường: Chiều sâu

Chìa khóa để cải thiện thuật toán này, khiến cho máy tính kháng cự cho tới khi trò chơi thật sự ngã ngũ, chính là cân nhắc chiều sâu, hay nói cách khác là số lượt, trong quá trình tính toán. Về cơ bản thì người chơi hoàn hảo phải chơi một cách hoàn hảo, song phải kéo dài trò chơi lâu nhất có thể.

Để làm được điều này, chúng ta sẽ trừ đi chiều sâu của game (số lượt) từ số điểm tính ra khi trò chơi kết thúc. Khi đó, càng nhiều lượt thì điểm càng thấp, càng ít lượt thì điểm càng cao. Do đó, đoạn code ở trên sau khi chỉnh sửa sẽ như sau:

Vậy nên mỗi khi áp dụng thuật Minimax, độ sâu được tăng 1 và khi trò chơi kết thúc, điểm số sẽ được tính dựa trên chiều sâu. Cùng xem nó sẽ ra sao khi áp dụng vào ví dụ phía trên:

Lần này, chiều sâu đã tạo ra sự khác biệt về điểm số giữa các tình huống kết thúc của trò chơi. Và bởi vì ở tình huống 0, thuật toán Minimax đang tìm kiếm điểm số lớn nhất, điểm -6 sẽ được chọn vì lớn hơn điểm -8. Do đó, ngay cả khi biết trước được cái chết của mình, máy tính sẽ chọn chặn nước đi của đối thủ, thay vì tự tử mổ bụng seppuku như samurai.

Kết luận

Mình mong rằng cuộc thảo luận này đã giúp bạn hiểu rõ hơn về thuật toán Minimax và chinh phục trò chơi Tic Tac Toe. Nếu bạn có thêm thắc mắc hoặc cần giải đáp rõ hơn, vui lòng để lại bình luận và mình sẽ cải thiện bài viết của mình. Tất cả những đoạn code của trò chơi Tic Tac Toe có thể được tìm thấy trên Github nếu bạn có nhu cầu.

Ngoài Tic Tac Toe, thuật toán Minimax còn được áp dụng rộng rãi nhiều trong lý thuyết trò chơi. Tiêu biểu là cờ Caro, cờ vua … và các game đối kháng hai người trong đó nước đi có thể dự đoán được (khác với oẳn tù tì, khi xác suất ra búa, bao, kéo đều như nhau).

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *