Thuật toán khả giải Mahjong: Cách nó hoạt động

Một thuật toán khả giải Mahjong là một quy trình ra quyết định xác định liệu một bàn Mahjong solitaire cho trước có thể được dọn sạch hoàn toàn bằng cách ghép và loại bỏ các cặp quân theo thứ tự, đúng với luật chơi hay không. Hiểu thuật toán khả giải Mahjong là gì đồng nghĩa với việc đối mặt với một trong những bài toán thú vị hơn của lý thuyết trò chơi tổ hợp: về mặt hình thức, câu hỏi này là NP-complete trong điều kiện biết đầy đủ thông tin, nghĩa là chưa có thuật toán nào được biết là giải hiệu quả cho mọi cấu hình bàn có thể có. Phần mềm thực tế vượt qua rào cản này bằng các heuristic, vòng lặp thử lại và chiến lược dự phòng. Khoảng cách giữa độ khó lý thuyết và khả năng chơi thực tế chính là nơi diễn ra phần kỹ thuật hữu ích nhất.

Độ phức tạp tính toán cho chúng ta biết gì về khả giải Mahjong?

Độ phức tạp tính toán là ngành nghiên cứu hình thức về mức độ khó của một bài toán đối với máy tính. Hai lớp độ phức tạp quan trọng nhất ở đây là NP và PSPACE.

NP-complete mô tả các bài toán mà việc kiểm tra một lời giải thì nhanh, nhưng việc tìm ra lời giải có thể cần thời gian hàm mũ. Mahjong solitaire với đầy đủ thông tin là NP-complete đối với bài toán quyết định: với một bàn mà mọi vị trí quân đều đã biết, liệu có thể loại bỏ hết tất cả quân hay không? Kết quả này có nghĩa là không có thuật toán nào được đảm bảo trả lời nhanh câu hỏi đó cho mọi bố cục có thể.

PSPACE-complete là một lớp còn khó hơn nữa. Bài toán tối đa hóa xác suất dọn sạch là PSPACE-complete và PSPACE-hard khi xấp xỉ trong phạm vi một hệ số n mũ bất kỳ hằng số dương nào. Kết quả này loại trừ cả các lời giải xấp xỉ chạy trong thời gian đa thức, trừ khi những giả định nền tảng của lý thuyết độ phức tạp sụp đổ.

Dưới đây là ý nghĩa thực tế của hai kết quả này:

• Phiên bản quyết định (bàn này có dọn được không?) là NP-complete. Các bộ giải chính xác phải đối mặt với thời gian tệ nhất là hàm mũ.
• Phiên bản tối ưu hóa (chuỗi nào tối đa hóa xác suất dọn sạch?) là PSPACE-complete. Nó còn khó hơn phiên bản quyết định.
• Kiểm tra khả giải chính xác đòi hỏi tính toán tệ nhất là hàm mũ hoặc tốn nhiều bộ nhớ. Các bộ giải thực tế dựa vào heuristic hoặc giới hạn bố cục.
• Khả giải phụ thuộc vào cách phát biểu bài toán và mô hình trò chơi. Không có một thuật toán phổ quát nào phù hợp cho mọi biến thể Mahjong.

Bài học cốt lõi từ lý thuyết độ phức tạp không phải là Mahjong không thể giải. Mà là việc giải chính xác cho các bàn bất kỳ đắt đến mức tính toán, đến nỗi không có engine trò chơi sản xuất nào cố làm trực tiếp.

Sự phân biệt này định hình mọi quyết định thiết kế trong phần mềm Mahjong. Nhà phát triển không chờ một câu trả lời được chứng minh là đúng. Họ xây dựng hệ thống tạo ra các bàn có khả năng giải cao, rồi kiểm tra thay vì chứng minh.

Khả giải được mô hình hóa như thế nào, và vì sao bùng nổ tổ hợp lại quan trọng?

Cấu trúc toán học của Mahjong solitaire xoay quanh việc ghép cặp quân. Mỗi quân thuộc một trong 36 nhóm, và mỗi nhóm có đúng bốn quân. Để dọn bàn, mỗi quân phải được ghép với một trong ba quân giống hệt còn lại.

Đây là thách thức tổ hợp cốt lõi, từng bước một:

1. Đếm số lựa chọn ghép cặp. Với bất kỳ nhóm bốn quân giống nhau nào, có đúng ba cách để ghép chúng thành hai cặp tương ứng.
2. Nhân trên tất cả các nhóm. Với 36 nhóm và mỗi nhóm có 3 lựa chọn, tổng số cấu hình ghép cặp là 3^36, xấp xỉ 1,5 × 10^17. Đó là khoảng 150 nghìn tỷ nghìn tỷ tổ hợp.
3. Nhận ra sự bất khả thi của tìm kiếm vét cạn. Kiểm tra mọi cấu hình, ngay cả với tốc độ một tỷ phép toán mỗi giây, cũng sẽ mất hơn bốn năm tính toán liên tục. Không có engine trò chơi nào có thể chịu nổi chi phí đó cho mỗi bàn.
4. Tách việc ghép cặp khỏi thứ tự nước đi. Thứ tự loại bỏ không ảnh hưởng đến kết quả khả giải cuối cùng một khi các cặp đã được cố định. Đây là một nhận thức then chốt. Nó có nghĩa là không gian tìm kiếm được xác định bởi các lựa chọn ghép cặp, chứ không phải bởi chuỗi nước đi.
5. Tập trung tìm kiếm vào các mẫu ghép cặp. Việc giảm không gian trạng thái bằng cách diễn đạt lại trò chơi thành bài toán phụ thuộc giữa ghép cặp và loại bỏ giúp giảm độ phức tạp. Không gian vẫn lớn, nhưng dễ xử lý hơn nhiều so với việc theo dõi mọi chuỗi nước đi có thể.
6. Áp dụng tiền nén. Các bộ giải hiệu quả tập trung vào việc quân nào có thể tiếp cận được dựa trên bố cục bàn hiện tại, cắt tỉa các nhánh mà quân bị chặn khiến việc ghép cặp là bất khả thi về mặt vật lý, bất kể lựa chọn ghép cặp trừu tượng ra sao.

Mẹo hay: Khi phân tích một bàn Mahjong bằng tay, hãy nghĩ theo các cam kết ghép cặp thay vì từng nước đi riêng lẻ. Xác định những quân nào chỉ có một đối tác hợp lệ có thể tiếp cận, rồi khóa các cặp đó trước. Điều này phản ánh cách các bộ giải thuật toán cắt tỉa cây tìm kiếm.

Sự bùng nổ tổ hợp khiến tìm kiếm vét cạn trở nên không khả thi. Thực tế đó buộc mọi triển khai thực tế phải hướng tới heuristic và chiến lược thử lại ngẫu nhiên thay vì liệt kê đầy đủ. Hiểu ràng buộc này là nền tảng của các thuật toán Mahjong được giải thích trong bất kỳ bối cảnh phần mềm nghiêm túc nào.

Các triển khai thực tế tạo ra bàn Mahjong có thể giải như thế nào?

Phần mềm Mahjong sản xuất không cố chứng minh khả giải từ những nguyên lý đầu tiên. Nó xác minh khả giải thông qua một hệ thống hai lớp, kết hợp việc xây dựng bàn nhanh với một bộ giải kiểm tra kết quả.

Kiến trúc tiêu chuẩn hoạt động như sau:

• Lớp 1: Tạo dựng có chủ đích. Engine xây dựng bàn bằng một phương pháp được thiết kế để tạo ra bố cục có thể giải. Cách này nhanh nhưng không đảm bảo thành công mọi lúc.
• Lớp 2: Xác thực khả giải. Một bộ giải chạy trên bàn được tạo ra. Nếu bàn không vượt qua kiểm tra, engine sẽ thử lại.
• Vòng lặp thử lại. Các triển khai phổ biến chạy buildSolvableWithRetries tối đa 2.000 lần trước khi chuyển sang chiến lược khác. Con số đó phản ánh tinh chỉnh thực nghiệm, không phải nhu cầu lý thuyết.
• Chiến lược thay thế. Sau khi dùng hết ngân sách thử lại chính, engine chuyển sang một thuật toán xây dựng khác với vòng lặp thử lại riêng.
• Phương án dự phòng bàn ngẫu nhiên. Nếu mọi cách khác đều thất bại, engine tạo một bàn ngẫu nhiên và chạy kiểm tra giải trực tiếp trên đó. Điều này đảm bảo luôn cung cấp được một bàn có thể chơi.

Mẹo hay: Nếu bạn đang xây dựng một trình tạo câu đố Mahjong, hãy bắt đầu bằng cách tiếp cận xây dựng ngược: đặt các quân theo một thứ tự đã biết là có thể giải, rồi xáo trộn trong các ràng buộc cho phép. Cách này giảm mạnh số lần thử lại cần thiết trước khi tìm được một bàn hợp lệ.

Bảng dưới đây tóm tắt mẫu dự phòng ba giai đoạn được dùng trong các codebase sản xuất:

Hệ thống hai lớp với các lần thử lại lặp đi lặp lại và chiến lược dự phòng là tiêu chuẩn sản xuất để cung cấp các bàn câu đố có thể giải. Tư duy kỹ thuật ở đây là có chủ đích: đừng chứng minh khả giải trước. Hãy xây nhanh, xác minh nhanh, và thử lại khi cần. Cách tiếp cận đó phù hợp với những gì lý thuyết độ phức tạp dự đoán. Chứng minh chính xác thì đắt. Xác minh thì rẻ.

Kiến thức về khả giải cải thiện chiến lược và thiết kế game Mahjong như thế nào?

Hiểu cách khả giải hoạt động sẽ thay đổi cả cách nhà phát triển xây dựng trò chơi lẫn cách người chơi tiếp cận việc giải các câu đố Mahjong. Hai góc nhìn này củng cố lẫn nhau.

Từ góc độ chiến lược người chơi, các hiểu biết về khả giải chuyển trực tiếp thành quyết định tốt hơn:

• Ưu tiên các quân đang mở có ít đối tác. Nếu một quân chỉ có một cặp ghép có thể tiếp cận, thì đến một lúc nào đó phải thực hiện cặp đó. Trì hoãn có thể khiến bàn bị chặn.
• Tránh cô lập các nhóm quân. Loại bỏ những quân không mở ra thêm quân nào sẽ làm giảm lựa chọn trong tương lai mà không cải thiện vị thế của bạn. Khái niệm này được phân tích sâu trong bối cảnh cô lập quân và vì sao nó làm suy yếu khả giải.
• Nghĩ theo lớp, không phải từng nước đi riêng lẻ. Khả giải phụ thuộc vào các cam kết ghép cặp trên toàn bộ bàn. Người chơi lập kế hoạch trước hai hoặc ba nước thường xuyên chơi tốt hơn người chỉ phản ứng với cơ hội của từng quân.
• Dùng tính năng xáo trộn một cách chiến lược. Hầu hết các game Mahjong số đều có chức năng xáo trộn hoặc gợi ý. Những tính năng này dựa trên cùng các thuật toán khả giải chạy nền để xác nhận rằng vẫn còn một đường đi hợp lệ.

Từ góc độ thiết kế game, các thuật toán khả giải quyết định chất lượng trải nghiệm của người chơi:

• Các bố cục được tạo ra mà không kiểm tra khả giải thường xuyên tạo ra bàn không thể thắng. Người chơi gặp phải điều này sẽ mất niềm tin vào trò chơi, chứ không phải vào kỹ năng của chính họ.
• Cách sắp xếp quân ảnh hưởng trực tiếp đến độ khó. Những thiết kế mở ra ít quân hơn ở giai đoạn đầu buộc người chơi vào cây quyết định hẹp hơn, làm tăng độ phức tạp hiệu dụng của việc giải câu đố Mahjong.
• Các biến thể có thông tin ẩn, nơi mặt quân bị che cho đến khi được mở ra, chuyển bài toán từ ra quyết định NP-complete sang suy luận xác suất. Điều này làm thay đổi hoàn toàn tính chất của trò chơi.
• Những nhà phát triển hiểu thuật toán AI Mahjong có thể điều chỉnh độ khó bằng cách thay đổi mức độ mà bộ tạo dựng ưu tiên các bố cục có nhiều đường giải hợp lệ.

Mối liên hệ giữa lý thuyết thuật toán và trải nghiệm người chơi là trực tiếp. Một bàn được tạo bằng thuật toán khả giải vững chắc sẽ cho bạn một câu đố công bằng. Một bàn không có nó có thể là bất khả thi, và bạn sẽ không bao giờ biết vì sao mình thua.

Những điểm chính cần nhớ

Thuật toán khả giải Mahjong là NP-complete đối với bài toán quyết định và PSPACE-complete đối với bài toán tối ưu hóa, vì vậy các phương pháp dựa trên heuristic và thử lại là con đường thực tế duy nhất để tạo ra các bàn có thể giải trong phần mềm sản xuất.

Vì sao lý thuyết thôi sẽ không giúp bạn xây một game Mahjong tốt hơn

Tôi đã dành khá nhiều thời gian phân tích cách khả giải Mahjong được triển khai trong thực tế, và khoảng cách giữa các kết quả độ phức tạp học thuật với những gì kỹ sư thực sự phát hành là rất đáng chú ý. Các chứng minh NP-complete và PSPACE-complete thì thỏa mãn về mặt trí tuệ. Chúng cho bạn biết một điều đúng và quan trọng về bài toán. Nhưng chúng không cho bạn biết cách xây một trò chơi mà người chơi thích.

Điều tôi nhận ra là cách tiếp cận dựa trên thử lại không phải là một sự thỏa hiệp. Nó là câu trả lời đúng cho lớp bài toán này. Khi không gian tìm kiếm của bạn có 150 nghìn tỷ nghìn tỷ cấu hình, bạn không cần khám phá hết tất cả. Bạn cần một bộ tạo nhanh thành công phần lớn thời gian, một bộ xác minh rẻ để bắt lỗi, và một phương án dự phòng đảm bảo đầu ra. Kiến trúc đó đáng tin cậy hơn trong sản xuất so với bất kỳ bộ giải chính xác nào.

Nhận thức rằng thứ tự nước đi không ảnh hưởng đến khả giải một khi các cặp đã được cố định là kết quả bị đánh giá thấp nhất trong lĩnh vực này. Nó có nghĩa là bạn có thể giảm một bài toán tưởng như tuần tự thành một bài toán tổ hợp, và các bài toán tổ hợp phản ứng rất tốt với lan truyền ràng buộc và cắt tỉa. Nếu bạn đang xây một bộ giải Mahjong hoặc nghiên cứu độ phức tạp của trò chơi giải đố, hãy bắt đầu từ đó.

Lời khuyên của tôi cho bất kỳ ai muốn triển khai kiểm tra khả giải là: đừng bắt đầu từ tài liệu lý thuyết độ phức tạp. Hãy bắt đầu với một vòng lặp thử lại hoạt động được, gắn đo đạc để biết mỗi giai đoạn dự phòng kích hoạt bao nhiêu lần, rồi tinh chỉnh từ đó. Lý thuyết cho bạn biết trần trên. Đo lường cho bạn biết bạn đang ở đâu.

— Dmytro Romaniuk

Chơi các câu đố Mahjong được xây trên việc tạo bàn có thể giải

Mỗi câu đố tại Mahjong Online Club đều được tạo bằng cách tiếp cận ưu tiên khả giải như mô tả trong bài viết này. Không có bàn nào được đưa đến bạn mà chưa vượt qua bước xác thực của bộ giải. Điều đó có nghĩa là mọi ván bạn bắt đầu đều có thể thắng, và mọi thất bại đều là vấn đề chiến lược, không phải do bố cục bị lỗi.

Bạn có thể chơi Mahjong miễn phí trực tiếp trên trình duyệt mà không cần đăng ký. Nền tảng này được xây dựng xoay quanh trải nghiệm không gây xao nhãng, nhằm hỗ trợ sự tập trung và nhận diện mẫu. Nếu bạn muốn đưa các khái niệm thuật toán ở đây vào thực hành, đây chính là nơi để làm điều đó.

Câu hỏi thường gặp

Thuật toán khả giải Mahjong là gì?

Thuật toán khả giải Mahjong là một quy trình tính toán xác định liệu một bàn Mahjong solitaire có thể được dọn sạch hoàn toàn bằng cách ghép và loại bỏ tất cả các cặp quân hay không. Phiên bản quyết định của bài toán này về mặt hình thức là NP-complete trong điều kiện biết đầy đủ thông tin.

Khả giải Mahjong hoạt động về mặt toán học như thế nào?

Khả giải phụ thuộc vào các lựa chọn ghép cặp trên 36 nhóm quân, mỗi nhóm có 3 cách ghép có thể, tạo ra khoảng 150 nghìn tỷ nghìn tỷ cấu hình tổng cộng. Vì thứ tự nước đi không làm thay đổi kết quả một khi các cặp đã được cố định, các bộ giải tập trung vào các ràng buộc ghép cặp thay vì chuỗi nước đi.

Vì sao phần mềm không thể giải chính xác các bàn Mahjong mọi lúc?

Việc kiểm tra khả giải chính xác đòi hỏi tính toán hàm mũ trong trường hợp xấu nhất, điều này không thực tế đối với các engine trò chơi thời gian thực. Các hệ thống sản xuất dùng bộ tạo dựng có vòng lặp thử lại tối đa 2.000 lần và các giai đoạn dự phòng để đảm bảo có một bàn có thể chơi mà không cần chứng minh chính xác.

Sự khác nhau giữa np-complete và pspace-complete trong Mahjong là gì?

Bài toán quyết định (bàn này có dọn được không?) là NP-complete. Bài toán tối ưu hóa (chuỗi nào tối đa hóa xác suất dọn sạch?) là PSPACE-complete, một lớp còn khó hơn hẳn và cũng loại trừ các thuật toán xấp xỉ hiệu quả.

Chiến lược chơi Mahjong liên hệ thế nào với các thuật toán khả giải?

Người chơi ưu tiên các quân có ít đối tác có thể tiếp cận và tránh cô lập các nhóm quân đang áp dụng cùng logic cắt tỉa ràng buộc mà các bộ giải thuật toán sử dụng. Hiểu cách khả giải được cấu trúc sẽ giúp các quyết định chiến lược trở nên có chủ đích hơn và ít phụ thuộc vào đoán mò hơn.

Đề xuất

• Cách chơi Mahjong Solitaire — Luật, quân và chiến lược
• Vì sao cô lập quân phá hỏng các ván Mahjong cho mọi người chơi
• Cheat Mahjong Titans: Bộ giải, gợi ý và các mẹo hợp lệ
• Mục tiêu của Mahjong là gì? Luật chơi và chiến lược