Thuật toán minimax trong game caro java

  -  

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.

Bạn đang xem: Thuật toán minimax trong game caro java

Để 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.


Mục Lục


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.

Xem thêm: Tổng Quan Về Kỳ Thi Chứng Chỉ Bec Là Gì, Tổng Quan Về Kỳ Thi Chứng Chỉ Bec Vantage

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.

Xem thêm: Game Cá Lớn Cá Bé Cực Hay - Game Cá Lớn Nuốt Cá Bé Cực Hay

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: