Có lẽ bạn cũng từng như tôi, khi tìm kiếm “Tic Tac Toe” trên Google và bất ngờ phát hiện ra một phiên bản game tích hợp sẵn, cho phép bạn chơi ngay lập tức. Điều thực sự khơi dậy sự tò mò của tôi chính là tùy chọn độ khó “Impossible” (Không thể thắng). Làm thế nào một trò chơi đơn giản như Tic Tac Toe lại có thể trở nên “không thể thua” được? Bí mật đằng sau khả năng bất bại này là gì, và liệu có cách đánh bại Tic Tac Toe không thể thắng này không? Câu hỏi đó đã dẫn tôi vào một hành trình khám phá sâu hơn, để tìm hiểu cách thức mà trí tuệ nhân tạo (AI) trong game này hoạt động, và cuối cùng, tự tay xây dựng một phiên bản tương tự.
Khám Phá “Thành Phần Bí Mật”: Thuật Toán Minimax
Khi tìm hiểu, tôi phát hiện ra rằng chìa khóa cho khả năng “bất bại” của Tic Tac Toe ở chế độ khó nhất không phải là một giải pháp máy học phức tạp, mà là một thuật toán tương đối đơn giản, có thể được viết chỉ trong vài chục dòng mã. Đó chính là thuật toán Minimax.
Thuật toán Minimax, theo JavaPoint, là “một thuật toán đệ quy hoặc quay lui được sử dụng trong việc ra quyết định và lý thuyết trò chơi. Nó cung cấp nước đi tối ưu cho người chơi, giả định rằng đối thủ cũng đang chơi tối ưu.” Điều này có nghĩa là, AI sử dụng Minimax sẽ luôn tính toán mọi nước đi có thể trong tương lai để đảm bảo rằng nó sẽ không bao giờ thua, hoặc ít nhất là đạt được kết quả tốt nhất có thể (hòa hoặc thắng). Khi hiểu được điều này, tôi nhận ra rằng, để thực sự đánh bại Tic Tac Toe không thể thắng, chúng ta cần hiểu sâu về logic mà nó vận hành.
Vượt Qua Nỗi Sợ Hãi: Hành Trình Chinh Phục Thuật Toán
Ban đầu, khi phát hiện ra rằng giải pháp là một thuật toán, tôi đã cảm thấy khá nản lòng. Đó là khoảng thời gian tôi đang học môn Thuật toán ở trường đại học và kết quả không mấy khả quan. Tôi thực sự không muốn dính dáng gì đến thuật toán. Ý định của tôi là tái tạo lại trò chơi Tic Tac Toe “impossible” đó, nhưng tôi không chắc mình có muốn học một thuật toán khác để làm điều đó không. Một mặt, đây có thể là cơ hội tuyệt vời để tôi vượt qua nỗi sợ hãi về thuật toán; mặt khác, nó đồng nghĩa với việc đối mặt với điều tôi sợ nhất trong đời.
Đó là lúc tôi tìm thấy video này của Sebastian Lague, một trong những YouTuber yêu thích của tôi. Video đó thực sự khiến tôi tin rằng mình có thể hoàn thành dự án nếu cố gắng. Và tôi đã làm được. Phần còn lại là câu chuyện về sự kiên trì tuyệt đối và khao khát cải thiện bản thân.
Quyết Định Nền Tảng: Chọn Lựa Công Nghệ Phù Hợp
Một trong những quyết định đầu tiên tôi cần đưa ra là lựa chọn công nghệ cho giao diện người dùng (frontend) – phần hiển thị bảng trò chơi và xử lý tương tác của người chơi. Tôi biết rằng đây phải là một giải pháp đa nền tảng, vì tôi muốn xuất bản ứng dụng trên Play Store như một dự án kỹ thuật, nhưng cũng muốn nó có sẵn trên web để bạn bè có thể dễ dàng chơi mà không cần tải xuống.
Lựa chọn ban đầu của tôi là Unity. Nó đáp ứng tất cả các yêu cầu và là một framework vững chắc để phát triển game. Tuy nhiên, Unity quá “nặng ký” cho một trò chơi đơn giản như Tic Tac Toe. Hơn nữa, đường cong học tập của nó cũng khá cao. Mục tiêu của dự án này là học về thuật toán, chứ không phải phát triển game chuyên sâu. Đó là lý do tôi quyết định chọn Flutter.
Tại Sao Lại Là Flutter?
Tôi đã khá quen thuộc với Flutter và nó hỗ trợ nhiều nền tảng hơn Unity. Tôi nhận ra rằng việc phát triển giao diện người dùng với Flutter sẽ tốn ít thời gian hơn đáng kể. Có thể bạn đang nghĩ, nếu Flutter tuyệt vời như vậy, tại sao nó không phải là lựa chọn đầu tiên? Bởi vì Flutter chủ yếu là một framework phát triển ứng dụng. Tôi chưa bao giờ nghĩ rằng, bảng trò chơi Tic Tac Toe thực chất chỉ là một số ô lưới và các yếu tố UI ứng dụng thông thường. Flutter rất phù hợp cho những điều này. Nó cũng có thể xử lý bất kỳ loại tương tác nào từ người dùng, dù là chạm đơn, nhấn giữ hay thậm chí là cử chỉ.
Sau khi chọn được framework, đã đến lúc xây dựng giao diện người dùng. Đáng ngạc nhiên, việc này chỉ tốn của tôi khoảng 2 giờ. Sau đó, tôi xem video này của Daniel Shiffman từ Coding Train, một người hùng cá nhân khác của tôi. Video của anh ấy thực sự giúp tôi hiểu rõ hơn về cách triển khai và các trường hợp biên của thuật toán.
Đối Mặt Thử Thách và Tối Ưu Hiệu Suất AI
Mặc dù việc tạo giao diện người dùng mất rất ít thời gian, tôi ước gì có thể nói điều tương tự với thuật toán. Ngôn ngữ lập trình tôi sử dụng, Dart, thực sự rất giống với Javascript – ngôn ngữ mà Dan đã dùng để tạo AI. Vì vậy, tôi nghĩ rằng đây sẽ là một nhiệm vụ rất dễ dàng. Nhưng tôi đã sai. Trong quá trình viết code, lần đầu tiên trong đời tôi đối mặt với lỗi khét tiếng StackOverflow. Đây là một trong những lỗi đáng sợ nhất tôi từng gặp. Chương trình sẽ ngốn quá nhiều tài nguyên đến mức tôi không còn cách nào khác ngoài việc tắt máy tính cùi bắp của mình khi đó. Nhưng từng lỗi một, tôi đã khắc phục được tất cả. Tuy nhiên, mọi việc vẫn chưa suôn sẻ.
Tăng Tốc Với Alpha-beta Pruning
Cuối cùng tôi cũng hoàn thành dự án. Tôi có thể chơi game và AI sẽ kiểm tra tất cả các nước đi có thể và chọn nước đi tốt nhất. Nhưng có một vấn đề: sau khi tôi đặt “X” đầu tiên của mình, AI phải kiểm tra 255.168 bước có thể tiếp theo (nếu tôi không nhầm). Điều này có nghĩa là tôi phải chờ rất lâu để AI hoàn thành các phép tính và chọn phương án tốt nhất. Và điều này, không cần nói cũng biết, không hề thú vị chút nào. Điều này chỉ có nghĩa một điều: tôi phải tối ưu hóa thuật toán. Đó là lúc tôi tìm hiểu về Alpha-beta pruning.
Alpha-beta pruning là một thuật toán tìm kiếm nhằm giảm số lượng nút được thuật toán Minimax đánh giá trong cây tìm kiếm của nó. Nói một cách đơn giản, nó giảm đáng kể số bước mà AI phải kiểm tra.
Xử Lý Đa Luồng Với Isolates trong Dart
Thậm chí Alpha-beta pruning cũng chưa đủ với tôi. Sau đó, tôi tìm hiểu về Isolates trong Dart. Đây thực chất là một cách nói hoa mỹ để chỉ việc tôi đã triển khai đa luồng (multithreading). Điều này cho phép tôi không chặn giao diện người dùng trong khi quá trình tính toán đang diễn ra ở chế độ nền, vì cả hai tác vụ này được xử lý trong các luồng riêng biệt. Sau khi tất cả những điều này được thực hiện, dự án cuối cùng đã hoàn thành. Tôi đã tạo ra một trò chơi Tic Tac Toe mà không ai có thể đánh bại. Và tôi không thể diễn tả được niềm hạnh phúc của mình.
Vị Ngọt Của Thành Công: Chinh Phục Điều “Không Thể”
Tôi đã chấp nhận một thử thách, thực hiện nghiên cứu sâu rộng, đánh bại một trong những nỗi sợ lớn nhất của mình, và hoàn thành dự án một cách thành công. Tôi biết mình đang kể nghe như thể đang mô tả cốt truyện của IT (2017), nhưng đó chính là cảm giác của tôi.
Hành trình khám phá và xây dựng phiên bản Tic Tac Toe “không thể thắng” đã không chỉ cung cấp cho tôi cái nhìn sâu sắc về cách các AI trong game hoạt động mà còn giúp tôi vượt qua rào cản tâm lý với thuật toán. Điều quan trọng nhất không phải là cách đánh bại Tic Tac Toe không thể thắng theo nghĩa đen, mà là hiểu được logic và cấu trúc đằng sau nó, từ đó nhận ra rằng mọi thử thách kỹ thuật đều có thể được giải quyết bằng kiến thức và sự kiên trì.
Nếu bạn tò mò về cách thức thuật toán này hoạt động, hãy tham khảo đoạn mã sau đây.
Mã nguồn thuật toán Minimax và tối ưu hóa cho game Tic Tac Toe
Cảm ơn bạn rất nhiều nếu bạn đã đọc đến đây. Đây là lần đầu tiên tôi viết một cái gì đó cho chính mình. Vì vậy, những suy nghĩ và góp ý của bạn rất được trân trọng. Đừng quên để lại bình luận nhé.
Tài liệu tham khảo
- Minimax Algorithm: https://en.wikipedia.org/wiki/Minimax
- Alpha-beta Pruning: https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning
- Dart Isolates: https://dart.dev/guides/language/concurrency
- Video Sebastian Lague: https://www.youtube.com/watch?v=l-hh51ncgDI
- Video Daniel Shiffman: https://www.youtube.com/watch?v=trKjYdBASyQ
- Unity: https://unity.com/
- Flutter: https://flutter.dev/
- Dart: https://dart.dev/
- JavaPoint: https://www.javatpoint.com/
- StackOverflow: https://en.wikipedia.org/wiki/Stack_overflow