Sử dụng Trí tuệ nhân tạo để giải quyết Trò chơi 2048 (mã JAVA)

• 7 Tháng Tư, 2014
• Vasilis Vryniotis
• . 6 Bình luận

Đến bây giờ hầu hết các bạn đã nghe / chơi Trò chơi 2048 bởi Gabriele Cirulli. Đây là một trò chơi bảng đơn giản nhưng gây nghiện cao, đòi hỏi bạn phải kết hợp số lượng ô để đạt được số 2048. Theo dự kiến, độ khó của trò chơi sẽ tăng lên khi có nhiều ô chứa đầy giá trị cao. Cá nhân mặc dù tôi đã dành một khoảng thời gian hợp lý để chơi trò chơi, tôi không bao giờ có thể đạt đến năm 2048. Vì vậy, điều tự nhiên cần làm là cố gắng phát triển một bộ giải AI trong JAVA để đánh bại trò chơi 2048. 🙂

Trong bài viết này, tôi sẽ thảo luận ngắn gọn về cách tiếp cận của tôi để xây dựng Bộ giải trí thông minh nhân tạo của trò chơi 2048, tôi sẽ mô tả các phương pháp phỏng đoán mà tôi đã sử dụng và tôi sẽ cung cấp mã hoàn chỉnh được viết bằng JAVA. Mã này có nguồn mở theo giấy phép GPL v3 và bạn có thể tải xuống từ Github.

Phát triển trò chơi 2048 trong JAVA

Trò chơi gốc được viết bằng JavaScript, vì vậy tôi đã phải viết lại nó bằng JAVA từ đầu. Ý tưởng chính của trò chơi là bạn có một lưới 4 × 4 với các giá trị Số nguyên, tất cả đều là lũy thừa của 2. Các ô có giá trị bằng không được coi là trống. Tại mọi thời điểm trong trò chơi, bạn có thể di chuyển các giá trị theo 4 hướng Lên, Xuống, Phải hoặc Trái. Khi bạn thực hiện một bước di chuyển, tất cả các giá trị của lưới sẽ di chuyển theo hướng đó và chúng dừng lại khi đến đường viền của lưới hoặc khi đến ô khác có giá trị khác 2. Nếu ô trước đó có cùng giá trị, hai ô được hợp nhất thành một ô có giá trị gấp đôi. Vào cuối mỗi nước đi, một giá trị ngẫu nhiên được thêm vào bảng ở một trong các ô trống và giá trị của nó là 0.9 với xác suất 4 hoặc 0.1 với xác suất 2048. Trò chơi kết thúc khi người chơi tạo được ô có giá trị XNUMX (thắng) hoặc khi không còn nước đi nào khác để thực hiện (thua).

Trong triển khai ban đầu của trò chơi, thuật toán di chuyển hợp nhất hơi phức tạp vì nó tính đến tất cả các hướng. Một thuật toán đơn giản hóa tốt đẹp có thể được thực hiện nếu chúng ta sửa hướng mà chúng ta có thể kết hợp các mảnh và xoay bảng cho phù hợp để thực hiện di chuyển. Maurits van der Schee gần đây đã viết một bài báo về nó mà tôi tin là đáng để kiểm tra.

Tất cả các lớp được ghi lại với các bình luận Javadoc. Dưới đây chúng tôi cung cấp một mô tả cấp cao về kiến ​​trúc của việc thực hiện:

1. Lớp học

Lớp bảng chứa mã chính của trò chơi, chịu trách nhiệm di chuyển các quân cờ, tính điểm, xác nhận nếu trò chơi bị chấm dứt, v.v.

2. ActionStatus và Direction Enum

ActionStatus và Direction là hai enum thiết yếu lưu trữ kết quả của một nước đi và hướng đi của nó.

3. Lớp ConsoleGame

ConsoleGame là lớp chính cho phép chúng ta chơi trò chơi và kiểm tra độ chính xác của Bộ giải AI.

4. Lớp AIsolver

AIsolver là lớp chính của mô-đun Trí tuệ nhân tạo chịu trách nhiệm đánh giá bước đi tốt nhất tiếp theo được đưa ra cho một Hội đồng cụ thể.

Kỹ thuật trí tuệ nhân tạo: Cắt tỉa Minimax vs Alpha-beta

Một số phương pháp đã được xuất bản để giải quyết tự động trò chơi này. Đáng chú ý nhất là cái được phát triển bởi Matt Overlan. Để giải quyết vấn đề, tôi đã thử hai cách tiếp cận khác nhau, sử dụng thuật toán Minimax và sử dụng cắt tỉa Alpha-beta.

Thuật toán Minimax

Sản phẩm Minimax là một thuật toán đệ quy có thể được sử dụng để giải các trò chơi có tổng bằng hai người chơi. Trong mỗi trạng thái của trò chơi, chúng tôi liên kết một giá trị. Thuật toán Minimax tìm kiếm trong không gian của các trạng thái trò chơi có thể tạo ra một cây được mở rộng cho đến khi đạt đến độ sâu được xác định trước cụ thể. Khi đạt được các trạng thái lá đó, các giá trị của chúng được sử dụng để ước tính các trạng thái của các nút trung gian.

Ý tưởng thú vị của thuật toán này là mỗi cấp độ đại diện cho lượt của một trong hai người chơi. Để giành chiến thắng, mỗi người chơi phải chọn nước đi tối thiểu hóa mức chi trả tối đa của đối thủ. Dưới đây là một video trình bày đẹp về thuật toán minimax:

[Nhúng nội dung]

Dưới đây bạn có thể thấy mã giả của Thuật toán Minimax:

chức năng minimax (nút, độ sâu, maximizingPlayer)
    if độ sâu = 0 or nút là một nút thiết bị đầu cuối
        trở lại giá trị heuristic của nút
    if tối đa hóaPlayer bestValue: = -∞
        cho mỗi con của nút val: = minimax (con, độ sâu - 1, FALSE)) bestValue: = max (bestValue, val);
        trở lại giá trị tốt nhất
    khác
        giá trị tốt nhất: = +
        cho mỗi con của nút val: = minimax (con, độ sâu - 1, TRUE)) bestValue: = min (bestValue, val);
        trở lại giá trị tốt nhất
(* Cuộc gọi ban đầu để tối đa hóa trình phát *)
minimax (nguồn gốc, độ sâu, TRUE)

Cắt tỉa Alpha-beta

Sản phẩm Thuật toán cắt tỉa Alpha-beta là một sự mở rộng của minimax, làm giảm mạnh (cắt tỉa) số lượng nút mà chúng ta phải đánh giá / mở rộng. Để đạt được điều này, thuật toán ước tính hai giá trị alpha và beta. Nếu trong một nút đã cho, beta nhỏ hơn alpha thì phần còn lại của cây con có thể được cắt bớt. Dưới đây là một video trình bày đẹp về thuật toán alphabeta:

[Nhúng nội dung]

Dưới đây bạn có thể thấy mã giả của Thuật toán cắt tỉa Alpha-beta:

chức năng alphabeta (nút, độ sâu, α,, maximizingPlayer)
    if độ sâu = 0 or nút là một nút thiết bị đầu cuối
        trở lại giá trị heuristic của nút
    if tối đa hóa
        cho mỗi con của nút α: = max (α, alphabeta (con, độ sâu - 1, α, β, FALSE))
            if β ≤
                phá vỡ (* cắt *)
        trở lại α
    khác
        cho mỗi con của nút β: = min (β, alphabeta (con, độ sâu - 1, α, β, TRUE))
            if β ≤
                phá vỡ (* α bị cắt *)
        trở lại β
(* Cuộc gọi ban đầu *)
alphabeta (nguồn gốc, độ sâu, -∞, +, TRUE)

AI được sử dụng để giải quyết Game 2048 như thế nào?

Để sử dụng các thuật toán trên, trước tiên chúng ta phải xác định hai người chơi. Người chơi đầu tiên là người chơi trò chơi. Người chơi thứ hai là máy tính chèn ngẫu nhiên các giá trị vào các ô của bảng. Rõ ràng người chơi đầu tiên cố gắng tối đa hóa điểm số của mình và đạt được sự hợp nhất 2048. Mặt khác, máy tính trong trò chơi gốc không được lập trình cụ thể để chặn người dùng bằng cách chọn nước đi tồi tệ nhất có thể cho anh ta mà chỉ chèn ngẫu nhiên các giá trị vào các ô trống.

Vậy tại sao chúng tôi sử dụng các kỹ thuật AI để giải quyết các trò chơi có tổng bằng không và cụ thể giả định rằng cả hai người chơi đều chọn cách di chuyển tốt nhất có thể cho họ? Đáp án đơn giản; mặc dù thực tế chỉ là người chơi đầu tiên cố gắng tối đa hóa điểm số của mình, các lựa chọn của máy tính có thể chặn tiến trình và ngăn người dùng hoàn thành trò chơi. Bằng cách mô hình hóa hành vi của máy tính như một người chơi không ngẫu nhiên chỉnh hình, chúng tôi đảm bảo rằng sự lựa chọn của chúng tôi sẽ là một sự vững chắc độc lập với những gì máy tính chơi.

Phần quan trọng thứ hai là gán giá trị cho các trạng thái của trò chơi. Vấn đề này tương đối đơn giản vì bản thân trò chơi cho chúng tôi một số điểm. Thật không may, cố gắng tự tối đa hóa điểm số không phải là một cách tiếp cận tốt. Một lý do cho điều này là vị trí của các giá trị và số lượng ô có giá trị trống rất quan trọng để giành chiến thắng trong trò chơi. Ví dụ: nếu chúng ta phân tán các giá trị lớn trong các ô từ xa, sẽ rất khó để chúng ta kết hợp chúng. Ngoài ra, nếu chúng tôi không có ô trống, chúng tôi có nguy cơ mất trò chơi bất cứ lúc nào.

Vì tất cả các lý do trên, một số heuristic đã được đề xuất chẳng hạn như Monoticity, độ mịn và Gạch miễn phí của bảng. Ý tưởng chính là không sử dụng điểm số một mình để đánh giá từng trạng thái trò chơi mà thay vào đó xây dựng một điểm tổng hợp heuristic bao gồm các điểm số đã nói ở trên.

Cuối cùng, chúng ta nên lưu ý rằng mặc dù tôi đã phát triển một triển khai thuật toán Minimax, nhưng số lượng lớn các trạng thái có thể làm cho thuật toán rất chậm và do đó việc cắt tỉa là cần thiết. Kết quả là trong quá trình triển khai JAVA, tôi sử dụng việc mở rộng thuật toán cắt tỉa Alpha-beta. Ngoài ra, không giống như các triển khai khác, tôi không tích cực cắt tỉa các lựa chọn của máy tính bằng cách sử dụng các quy tắc tùy ý mà thay vào đó tôi đưa tất cả chúng vào tài khoản để tìm ra cách di chuyển tốt nhất có thể của người chơi.

Phát triển hàm số heuristic

Để đánh bại trò chơi, tôi đã thử một số chức năng heuristic khác nhau. Một trong những điều tôi thấy hữu ích nhất là:

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

Hàm trên kết hợp điểm thực tế của bảng, số ô / ô trống và số liệu gọi là điểm phân cụm mà chúng ta sẽ thảo luận sau. Chúng ta hãy xem từng thành phần chi tiết hơn:

1. Điểm thực tế: Vì những lý do rõ ràng, khi chúng ta tính toán giá trị của một bảng, chúng ta phải tính đến điểm của nó. Bảng có điểm cao hơn thường được ưa thích so với bảng có điểm thấp hơn.
2. Số lượng ô trống: Như chúng tôi đã đề cập trước đó, việc giữ một vài ô trống là rất quan trọng để đảm bảo rằng chúng tôi sẽ không thua trò chơi trong các bước tiếp theo. Các trạng thái bảng có nhiều ô trống hơn thường được ưa thích so với các ô khác có ít hơn. Một câu hỏi đặt ra liên quan đến việc chúng ta sẽ đánh giá những ô trống đó như thế nào? Trong giải pháp của tôi, tôi cân chúng bằng logarit của điểm thực tế. Điều này có tác dụng như sau: Điểm càng thấp, càng ít quan trọng để có nhiều ô trống (Điều này là do khi bắt đầu trò chơi kết hợp các ô khá dễ dàng). Điểm càng cao, điều quan trọng là phải đảm bảo rằng chúng tôi có các ô trống trong trò chơi của mình (Điều này là do vào cuối trò chơi, có nhiều khả năng bị mất do thiếu các ô trống.
3. Điểm phân cụm: Chúng tôi sử dụng điểm số phân cụm để đo mức độ phân tán các giá trị của bảng của chúng tôi. Khi các ô có giá trị tương tự gần nhau, chúng sẽ dễ kết hợp hơn, nghĩa là khó thua trò chơi hơn. Trong trường hợp này, điểm số cụm có giá trị thấp. Nếu các giá trị của bảng bị phân tán, thì điểm này nhận được giá trị rất lớn. Điểm này được trừ vào hai điểm trước đó và hoạt động giống như một hình phạt đảm bảo rằng các bảng cụm sẽ được ưu tiên.

Trong dòng cuối cùng của chức năng, chúng tôi đảm bảo rằng điểm số không âm. Điểm số phải cực kỳ tích cực nếu điểm của bảng là dương và chỉ bằng XNUMX khi bảng của điểm bằng không. Các hàm max và min được xây dựng để chúng ta có được hiệu ứng này.

Cuối cùng, chúng ta nên lưu ý rằng khi người chơi đạt đến trạng thái trò chơi cuối và không được phép di chuyển nữa, chúng ta không sử dụng điểm số trên để ước tính giá trị của trạng thái. Nếu trò chơi chiến thắng, chúng tôi sẽ gán giá trị nguyên cao nhất có thể, trong khi nếu trò chơi bị mất, chúng tôi chỉ định giá trị không âm thấp nhất (0 hoặc 1 với logic tương tự như trong đoạn trước).

Tìm hiểu thêm về Điểm phân cụm

Như chúng ta đã nói trước đó, điểm số phân cụm đo lường mức độ phân tán của các giá trị của bảng và hoạt động như một hình phạt. Tôi đã xây dựng điểm số này theo cách sao cho nó kết hợp các mẹo / quy tắc từ những người dùng đã thành thạo trò chơi. Quy tắc được đề xuất đầu tiên là bạn cố gắng giữ các ô có giá trị tương tự gần nhau để kết hợp chúng dễ dàng hơn. Quy tắc thứ hai là các ô có giá trị cao phải gần nhau và không xuất hiện ở giữa bảng mà thay vào đó là các cạnh hoặc góc.

Chúng ta hãy xem cách tính điểm của cụm. Đối với mỗi ô của bảng, chúng tôi ước tính tổng số chênh lệch tuyệt đối từ các ô lân cận (không bao gồm các ô trống) và chúng tôi lấy mức chênh lệch trung bình. Lý do tại sao chúng ta lấy trung bình là để tránh đếm nhiều hơn một lần ảnh hưởng của hai ô lân cận. Tổng số điểm phân cụm là tổng của tất cả các trung bình.

Điểm cụm có các thuộc tính sau:

1. Nó nhận được giá trị cao khi các giá trị của bảng bị phân tán và giá trị thấp khi các ô có giá trị tương tự gần nhau.
2. Nó không quá nặng so với hiệu ứng của hai tế bào lân cận.
3. Các tế bào trong lề hoặc góc có ít hàng xóm hơn và do đó điểm thấp hơn. Kết quả là khi các giá trị cao được đặt gần lề hoặc góc, chúng có điểm nhỏ hơn và do đó hình phạt sẽ nhỏ hơn.

Độ chính xác của thuật toán

Như mong đợi, độ chính xác (hay còn gọi là tỷ lệ phần trăm các trò chơi giành được) của thuật toán phụ thuộc rất nhiều vào độ sâu tìm kiếm mà chúng tôi sử dụng. Độ sâu tìm kiếm càng cao, độ chính xác càng cao và thời gian cần thiết để chạy. Trong các thử nghiệm của tôi, tìm kiếm với độ sâu 3 kéo dài dưới 0.05 giây nhưng cho 20% cơ hội chiến thắng, độ sâu 5 kéo dài khoảng 1 giây nhưng cho 40% cơ hội chiến thắng và cuối cùng độ sâu 7 kéo dài 27-28 giây và mang lại khoảng 70-80% cơ hội chiến thắng.

Mở rộng trong tương lai

Đối với những bạn quan tâm đến việc cải thiện mã, đây là một vài điều mà bạn có thể xem xét:

1. Cải thiện tốc độ: Cải thiện tốc độ của thuật toán sẽ cho phép bạn sử dụng độ sâu lớn hơn và do đó có được độ chính xác tốt hơn.
2. Tạo đồ họa: Có một lý do chính đáng tại sao việc thực hiện của Gabriele Cirulli trở nên nổi tiếng như vậy. Đó là tìm kiếm tốt đẹp! Tôi không bận tâm đến việc phát triển GUI nhưng tôi thích in kết quả trên bảng điều khiển khiến trò chơi khó theo dõi và chơi hơn. Tạo một GUI đẹp là điều bắt buộc.
3. Giai điệu Heuristic: Như tôi đã đề cập trước đó, một số người dùng đã đề xuất các phương pháp phỏng đoán khác nhau. Người ta có thể thử nghiệm cách tính điểm, trọng số và đặc điểm của bảng được tính đến. Cách tiếp cận của tôi về việc đo điểm cụm được cho là kết hợp các đề xuất khác như Đơn điệu và Độ mịn, nhưng vẫn còn chỗ để cải thiện.
4. Điều chỉnh độ sâu: Người ta cũng có thể cố gắng điều chỉnh / điều chỉnh độ sâu của tìm kiếm tùy thuộc vào trạng thái trò chơi. Ngoài ra, bạn có thể sử dụng Lặp đi lặp lại tìm kiếm sâu đầu tiên thuật toán được biết là cải thiện thuật toán cắt tỉa alpha-beta.

Đừng quên tải xuống mã JAVA từ Github và thử nghiệm. Tôi hy vọng bạn thích bài viết này! Nếu bạn đã làm xin vui lòng dành một chút thời gian để chia sẻ bài viết trên Facebook và Twitter. 🙂