Thuật toán tối ưu cho trò chơi 2048 là gì?

1941
nitish712 2014-03-12 19:37.

Gần đây tôi đã tình cờ gặp trò chơi 2048 . Bạn hợp nhất các ô tương tự bằng cách di chuyển chúng theo bất kỳ hướng nào trong bốn hướng để tạo các ô "lớn hơn". Sau mỗi lần di chuyển, một ô mới xuất hiện ở vị trí trống ngẫu nhiên với giá trị là 2hoặc 4. Trò chơi kết thúc khi tất cả các ô được lấp đầy và không có nước đi nào có thể hợp nhất các ô hoặc bạn tạo ô có giá trị là 2048.

Một, tôi cần tuân theo một chiến lược được xác định rõ ràng để đạt được mục tiêu. Vì vậy, tôi đã nghĩ đến việc viết một chương trình cho nó.

Thuật toán hiện tại của tôi:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

Những gì tôi đang làm là tại bất kỳ thời điểm nào, tôi sẽ cố gắng hợp nhất các ô với các giá trị 24, tức là, tôi cố gắng có 24ô, tối thiểu nhất có thể. Nếu tôi thử theo cách này, tất cả các ô khác sẽ tự động được hợp nhất và chiến lược có vẻ tốt.

Tuy nhiên, khi tôi thực sự sử dụng thuật toán này, tôi chỉ nhận được khoảng 4000 điểm trước khi trò chơi kết thúc. Điểm tối đa AFAIK là hơn 20.000 điểm một chút, lớn hơn nhiều so với điểm hiện tại của tôi. Có thuật toán nào tốt hơn thuật toán trên không?

14 answers

1285
nneonneo 2014-03-19 21:22.

Tôi đã phát triển một AI 2048 bằng cách sử dụng tối ưu hóa expectimax , thay vì tìm kiếm minimax được sử dụng bởi thuật toán của @ ovolve. AI chỉ đơn giản là thực hiện tối đa hóa tất cả các bước di chuyển có thể, theo sau là kỳ vọng đối với tất cả các lần xuất hiện ô có thể xảy ra (được tính theo xác suất của ô, tức là 10% cho điểm 4 và 90% cho 2). Theo như tôi biết, không thể cắt bỏ tối ưu hóa expectimax (ngoại trừ loại bỏ các nhánh cực kỳ khó xảy ra), và do đó, thuật toán được sử dụng là tìm kiếm vũ phu được tối ưu hóa cẩn thận.

Hiệu suất

AI trong cấu hình mặc định của nó (độ sâu tìm kiếm tối đa là 8) mất từ ​​10ms đến 200ms để thực hiện một bước di chuyển, tùy thuộc vào độ phức tạp của vị trí bảng. Trong thử nghiệm, AI đạt được tốc độ di chuyển trung bình từ 5-10 bước di chuyển mỗi giây trong toàn bộ trò chơi. Nếu độ sâu tìm kiếm được giới hạn ở 6 lần di chuyển, thì AI có thể dễ dàng thực hiện hơn 20 lần di chuyển mỗi giây, điều này tạo ra một số hoạt động xem thú vị .

Để đánh giá hiệu suất điểm số của AI, tôi đã chạy AI 100 lần (kết nối với trò chơi trên trình duyệt thông qua điều khiển từ xa). Đối với mỗi ô, đây là tỷ lệ trò chơi mà ô đó đã đạt được ít nhất một lần:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

Điểm tối thiểu trên tất cả các lần chạy là 124024; điểm tối đa đạt được là 794076. Điểm trung bình là 387222. AI không bao giờ thất bại trong việc lấy được ô 2048 (vì vậy nó không bao giờ thua trò chơi dù chỉ một lần trong 100 trận); trên thực tế, nó đã đạt được ô 8192 ít nhất một lần trong mỗi lần chạy!

Đây là ảnh chụp màn hình của lần chạy tốt nhất:

Trò chơi này mất 27830 lần di chuyển trong 96 phút, tức trung bình 4,8 lần di chuyển mỗi giây.

Thực hiện

Phương pháp tiếp cận của tôi mã hóa toàn bộ bảng (16 mục nhập) dưới dạng một số nguyên 64 bit duy nhất (trong đó các ô là các nybbles, tức là các khối 4 bit). Trên máy 64-bit, điều này cho phép truyền toàn bộ bảng trong một thanh ghi máy duy nhất.

Các phép toán dịch chuyển bit được sử dụng để trích xuất các hàng và cột riêng lẻ. Một hàng hoặc một cột là số lượng 16 bit, vì vậy một bảng có kích thước 65536 có thể mã hóa các phép biến đổi hoạt động trên một hàng hoặc cột. Ví dụ: các bước di chuyển được triển khai dưới dạng 4 tra cứu vào một "bảng hiệu ứng di chuyển" được tính toán trước mô tả cách mỗi bước di chuyển ảnh hưởng đến một hàng hoặc cột (ví dụ: bảng "di chuyển sang phải" chứa mục nhập "1122 -> 0023" mô tả cách row [2,2,4,4] trở thành hàng [0,0,4,8] khi được chuyển sang bên phải).

Việc chấm điểm cũng được thực hiện bằng cách sử dụng tra cứu bảng. Các bảng chứa điểm số theo kinh nghiệm được tính trên tất cả các hàng / cột có thể có và điểm số kết quả cho một bảng chỉ đơn giản là tổng các giá trị bảng trên mỗi hàng và cột.

Biểu diễn bảng này, cùng với phương pháp tra cứu bảng để di chuyển và ghi điểm, cho phép AI tìm kiếm một số lượng lớn các trạng thái trò chơi trong một khoảng thời gian ngắn (hơn 10.000.000 trạng thái trò chơi mỗi giây trên một lõi của máy tính xách tay giữa năm 2011 của tôi).

Bản thân tìm kiếm expectimax được mã hóa là tìm kiếm đệ quy xen kẽ giữa các bước "kỳ vọng" (kiểm tra tất cả các vị trí và giá trị có thể xuất hiện ô, đồng thời tính điểm số được tối ưu hóa của chúng theo xác suất của từng khả năng) và các bước "tối đa hóa" (kiểm tra tất cả các bước có thể và chọn một trong những điểm tốt nhất). Tìm kiếm cây kết thúc khi nó nhìn thấy vị trí đã thấy trước đó (sử dụng bảng chuyển vị ), khi nó đạt đến giới hạn độ sâu được xác định trước hoặc khi nó đạt đến trạng thái bảng rất khó xảy ra (ví dụ: nó đã đạt được bằng cách nhận được 6 ô "4" liên tiếp từ vị trí bắt đầu). Độ sâu tìm kiếm điển hình là 4-8 lần di chuyển.

Heuristics

Một số heuristics được sử dụng để hướng thuật toán tối ưu hóa đến các vị trí thuận lợi. Sự lựa chọn chính xác của heuristic có ảnh hưởng rất lớn đến hiệu suất của thuật toán. Các kinh nghiệm học khác nhau được tính trọng số và kết hợp thành một điểm vị trí, xác định mức độ "tốt" của một vị trí bảng nhất định. Sau đó, tìm kiếm tối ưu hóa sẽ nhằm mục đích tối đa hóa điểm trung bình của tất cả các vị trí bảng có thể. Điểm số thực tế, như được hiển thị trong trò chơi, không được sử dụng để tính điểm bảng, vì nó có trọng số quá lớn có lợi cho việc hợp nhất các ô (khi hợp nhất chậm có thể tạo ra một lợi ích lớn).

Ban đầu, tôi sử dụng hai phương pháp heuristics rất đơn giản, cấp "tiền thưởng" cho các ô vuông mở và cho các giá trị lớn trên cạnh. Các heuristics này hoạt động khá tốt, thường xuyên đạt được 16384 nhưng không bao giờ đạt đến 32768.

Petr Morávek (@xificurk) đã lấy AI của tôi và thêm hai phương pháp heuristics mới. Phương pháp heuristic đầu tiên là một hình phạt khi có các hàng và cột không đơn điệu tăng lên khi xếp hạng tăng lên, đảm bảo rằng các hàng không đơn điệu gồm các số nhỏ sẽ không ảnh hưởng mạnh đến điểm số, nhưng các hàng không đơn điệu của các số lớn sẽ ảnh hưởng đáng kể đến điểm số. Phương pháp heuristic thứ hai đếm số lượng các hợp nhất tiềm năng (các giá trị bằng nhau liền kề) ngoài các không gian mở. Hai phương pháp heuristics này phục vụ để thúc đẩy thuật toán hướng tới các bảng đơn điệu (dễ hợp nhất hơn) và hướng tới các vị trí bảng có nhiều hợp nhất (khuyến khích nó sắp xếp các bảng hợp nhất nếu có thể để có hiệu quả lớn hơn).

Hơn nữa, Petr cũng tối ưu hóa các trọng số theo phương pháp heuristic bằng cách sử dụng chiến lược "tối ưu hóa tổng hợp" (sử dụng thuật toán gọi là CMA-ES ), trong đó các trọng số được điều chỉnh để có được điểm trung bình cao nhất có thể.

Hiệu quả của những thay đổi này là vô cùng đáng kể. Thuật toán đã đi từ việc đạt được ô 16384 trong khoảng 13% thời gian thành đạt được hơn 90% thời gian và thuật toán bắt đầu đạt được 32768 trong 1/3 thời gian (trong khi các phương pháp heuristics cũ chưa từng tạo ra ô 32768) .

Tôi tin rằng vẫn còn chỗ để cải thiện về kinh nghiệm. Thuật toán này chắc chắn chưa phải là "tối ưu", nhưng tôi cảm thấy như nó đang tiến khá gần.


Việc AI đạt được ô 32768 trong hơn một phần ba số trò chơi của nó là một cột mốc quan trọng; Tôi sẽ ngạc nhiên khi biết liệu có người chơi nào đạt được 32768 trên trò chơi chính thức (tức là không sử dụng các công cụ như savestates hoặc hoàn tác) hay không. Tôi nghĩ rằng ô 65536 là trong tầm tay!

Bạn có thể thử AI cho chính mình. Mã có sẵn tại https://github.com/nneonneo/2048-ai .

1259
ovolve 2014-03-14 10:04.

Tôi là tác giả của chương trình AI mà những người khác đã đề cập trong chủ đề này. Bạn có thể xem AI đang hoạt động hoặc đọc nguồn .

Hiện tại, chương trình đạt được khoảng 90% tỷ lệ chiến thắng khi chạy bằng javascript trong trình duyệt trên máy tính xách tay của tôi với khoảng 100 mili giây thời gian suy nghĩ mỗi lần di chuyển, vì vậy mặc dù chưa hoàn hảo (chưa hoàn hảo!) Nhưng nó hoạt động khá tốt.

Vì trò chơi là một không gian trạng thái rời rạc, thông tin hoàn hảo, trò chơi theo lượt như cờ vua và cờ caro, nên tôi đã sử dụng các phương pháp tương tự đã được chứng minh là hoạt động trên các trò chơi đó, đó là tìm kiếm minimax với cắt tỉa alpha-beta . Vì đã có rất nhiều thông tin về thuật toán đó, tôi sẽ chỉ nói về hai phương pháp kinh nghiệm chính mà tôi sử dụng trong hàm đánh giá tĩnh và phương pháp này chính thức hóa nhiều trực giác mà người khác đã bày tỏ ở đây.

Tính đơn điệu

Phương pháp heuristic này cố gắng đảm bảo rằng các giá trị của ô đều tăng hoặc giảm dọc theo cả hướng trái / phải và lên / xuống. Chỉ riêng heuristic này đã nắm bắt được trực giác mà nhiều người khác đã đề cập, rằng các ô có giá trị cao hơn nên được gom lại ở một góc. Nó thường sẽ ngăn các ô nhỏ có giá trị nhỏ hơn không bị lẫn lộn và sẽ giữ cho bảng rất có tổ chức, với các ô nhỏ xếp thành tầng và lấp đầy các ô lớn hơn.

Đây là ảnh chụp màn hình của một lưới đơn sắc hoàn hảo. Tôi thu được điều này bằng cách chạy thuật toán với hàm eval được đặt để bỏ qua các phương pháp heuristics khác và chỉ xem xét tính đơn điệu.

Độ mịn

Riêng heuristic ở trên có xu hướng tạo ra các cấu trúc trong đó các ô liền kề đang giảm giá trị, nhưng tất nhiên để hợp nhất, các ô liền kề cần có cùng giá trị. Do đó, heuristic độ mịn chỉ đo chênh lệch giá trị giữa các viên gạch láng giềng, cố gắng giảm thiểu số lượng này.

Một nhà bình luận trên Hacker News đã đưa ra một hình thức hóa thú vị về ý tưởng này về mặt lý thuyết đồ thị.

Dưới đây là ảnh chụp màn hình của một lưới hoàn toàn trơn tru, nhờ sự phân biệt bắt chước tuyệt vời này .

Gạch miễn phí

Và cuối cùng, sẽ bị phạt nếu có quá ít ô trống, vì các tùy chọn có thể nhanh chóng hết khi bảng trò chơi quá chật chội.

Và đó là nó! Tìm kiếm trong không gian trò chơi trong khi tối ưu hóa các tiêu chí này mang lại hiệu suất đáng kể. Một lợi thế khi sử dụng cách tiếp cận tổng quát như thế này thay vì chiến lược di chuyển được mã hóa rõ ràng là thuật toán thường có thể tìm ra các giải pháp thú vị và bất ngờ. Nếu bạn quan sát nó chạy, nó thường sẽ thực hiện những bước đi đáng ngạc nhiên nhưng hiệu quả, chẳng hạn như đột ngột chuyển bức tường hoặc góc mà nó đang dựng lên.

Biên tập:

Đây là một minh chứng về sức mạnh của phương pháp này. Tôi đã mở rộng các giá trị ô (vì vậy nó tiếp tục tăng sau khi đạt đến năm 2048) và đây là kết quả tốt nhất sau tám lần thử nghiệm.

Vâng, đó là 4096 cùng với 2048. =) Có nghĩa là nó đạt được ô 2048 khó nắm bắt ba lần trên cùng một bảng.

152
Ronenz 2014-05-25 23:25.

Tôi bắt đầu quan tâm đến ý tưởng về một AI cho trò chơi này không chứa trí thông minh được mã hóa cứng (tức là không có tính toán kinh nghiệm, chức năng tính điểm, v.v.). AI chỉ nên "biết" các quy tắc trò chơi và "tìm ra" cách chơi của trò chơi. Điều này trái ngược với hầu hết các AI (như những AI trong chủ đề này) nơi trò chơi về cơ bản là bạo lực được điều khiển bởi một chức năng tính điểm thể hiện sự hiểu biết của con người về trò chơi.

Thuật toán AI

Tôi đã tìm thấy một thuật toán chơi đơn giản nhưng hiệu quả đáng ngạc nhiên: Để xác định nước đi tiếp theo cho một bàn cờ nhất định, AI sẽ chơi trò chơi trong bộ nhớ bằng cách sử dụng các nước đi ngẫu nhiên cho đến khi trò chơi kết thúc. Việc này được thực hiện nhiều lần trong khi vẫn theo dõi được điểm số cuối trò chơi. Sau đó, điểm kết thúc trung bình cho mỗi lần di chuyển bắt đầu được tính. Nước đi bắt đầu với điểm kết thúc trung bình cao nhất được chọn là nước đi tiếp theo.

Chỉ với 100 lần chạy (tức là trong trò chơi trí nhớ) mỗi lần di chuyển, AI đạt được 80% ô 2048 và 5096 ô 50% số lần. Sử dụng 10000 lần chạy sẽ nhận được 100% ô 2048, 70% cho ô 4096 và khoảng 1% cho ô 8192.

Xem nó trong hành động

Điểm tốt nhất đạt được được hiển thị ở đây:

Một thực tế thú vị về thuật toán này là trong khi các trò chơi chơi ngẫu nhiên khá tệ, việc chọn nước đi tốt nhất (hoặc ít xấu nhất) dẫn đến chơi trò chơi rất tốt: Một trò chơi AI điển hình có thể đạt 70000 điểm và kéo dài 3000 lần di chuyển, nhưng các trò chơi chơi ngẫu nhiên trong bộ nhớ từ bất kỳ vị trí nhất định nào mang lại trung bình 340 điểm cộng thêm trong khoảng 40 lần di chuyển trước khi chết. (Bạn có thể tự mình thấy điều này bằng cách chạy AI và mở bảng điều khiển gỡ lỗi.)

Biểu đồ minh họa điểm này: Đường màu xanh lam hiển thị số điểm trên bàn cờ sau mỗi nước đi. Đường màu đỏ hiển thị điểm kết thúc trò chơi ngẫu nhiên tốt nhất của thuật toán từ vị trí đó. Về bản chất, các giá trị màu đỏ đang "kéo" các giá trị màu xanh lam về phía chúng, vì chúng là dự đoán tốt nhất của thuật toán. Thật thú vị khi thấy đường màu đỏ chỉ nằm trên đường màu xanh một chút ở mỗi điểm, tuy nhiên đường màu xanh lam tiếp tục tăng ngày càng nhiều.

Tôi thấy khá ngạc nhiên khi thuật toán không cần thực sự thấy trước việc chơi tốt trò chơi để chọn nước đi tạo ra nó.

Tìm kiếm sau đó, tôi thấy thuật toán này có thể được phân loại là thuật toán Tìm kiếm cây Monte Carlo thuần túy .

Triển khai và Liên kết

Đầu tiên, tôi đã tạo một phiên bản JavaScript có thể xem hoạt động tại đây . Phiên bản này có thể chạy 100 lần chạy trong thời gian khá. Mở bảng điều khiển để biết thêm thông tin. ( nguồn )

Sau đó, để chơi thêm một số thứ nữa, tôi đã sử dụng @nneonneo cơ sở hạ tầng được tối ưu hóa cao và triển khai phiên bản của tôi bằng C ++. Phiên bản này cho phép lên đến 100000 lần chạy mỗi lần di chuyển và thậm chí 1000000 nếu bạn có đủ kiên nhẫn. Hướng dẫn xây dựng được cung cấp. Nó chạy trong bảng điều khiển và cũng có điều khiển từ xa để chơi phiên bản web. ( nguồn )

Các kết quả

Đáng ngạc nhiên, việc tăng số lần chạy không cải thiện đáng kể việc chơi trò chơi. Dường như có giới hạn đối với chiến lược này ở khoảng 80000 điểm với ô 4096 và tất cả các ô nhỏ hơn, rất gần với việc đạt được ô 8192. Tăng số lần chạy từ 100 lên 100000 làm tăng tỷ lệ đạt đến giới hạn số điểm này (từ 5% lên 40%) nhưng không vượt qua được.

Chạy 10000 lần chạy với mức tăng tạm thời lên 1000000 gần các vị trí quan trọng đã quản lý để phá vỡ rào cản này dưới 1% số lần đạt được điểm số tối đa là 129892 và ô 8192.

Cải tiến

Sau khi triển khai thuật toán này, tôi đã thử nhiều cải tiến bao gồm sử dụng điểm số tối thiểu hoặc tối đa hoặc kết hợp giữa tối thiểu, tối đa và trung bình. Tôi cũng đã cố gắng sử dụng chiều sâu: Thay vì cố gắng K chạy cho mỗi nước đi, tôi đã cố gắng K di chuyển cho mỗi nước đi danh sách của một chiều dài nhất định ( "lên, lên, trái" chẳng hạn) và chọn di chuyển đầu tiên của danh sách ghi bàn di chuyển tốt nhất.

Sau đó, tôi thực hiện một cây tính điểm có tính đến xác suất có điều kiện để có thể chơi một nước đi sau một danh sách nước đi nhất định.

Tuy nhiên, không có ý tưởng nào trong số này cho thấy lợi thế thực sự so với ý tưởng đầu tiên đơn giản. Tôi đã để lại mã cho những ý tưởng này được bình luận trong mã C ++.

Tôi đã thêm cơ chế "Tìm kiếm sâu" để tăng số lần chạy tạm thời lên 1000000 khi bất kỳ lần chạy nào vô tình đạt đến ô cao nhất tiếp theo. Điều này cung cấp một cải tiến về thời gian.

Tôi muốn biết liệu có ai có ý tưởng cải tiến khác để duy trì sự độc lập miền của AI hay không.

2048 Biến thể và Nhân bản

Để giải trí, tôi cũng đã triển khai AI như một bookmarklet , gắn vào các điều khiển của trò chơi. Điều này cho phép AI hoạt động với trò chơi gốc và nhiều biến thể của nó .

Điều này có thể xảy ra do bản chất không phụ thuộc vào miền của AI. Một số biến thể khá khác biệt, chẳng hạn như bản sao Lục giác.

129
Daren 2014-03-13 06:05.

CHỈNH SỬA: Đây là một thuật toán ngây thơ, mô hình hóa quá trình suy nghĩ có ý thức của con người và nhận được kết quả rất yếu so với AI tìm kiếm tất cả các khả năng vì nó chỉ nhìn một ô phía trước. Nó đã được gửi sớm trong dòng thời gian phản hồi.

Tôi đã tinh chỉnh thuật toán và đánh bại trò chơi! Nó có thể thất bại do vận rủi đơn giản ở gần cuối (bạn buộc phải di chuyển xuống, điều mà bạn không bao giờ nên làm và một ô xuất hiện ở nơi cao nhất của bạn. Chỉ cần cố gắng giữ cho hàng trên cùng được lấp đầy, vì vậy di chuyển sang trái không phá vỡ khuôn mẫu), nhưng về cơ bản bạn sẽ có một phần cố định và một phần di động để chơi cùng. Đây là mục tiêu của bạn:

Đây là mô hình tôi đã chọn theo mặc định.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

Góc được chọn là tùy ý, về cơ bản bạn không bao giờ bấm một phím (di chuyển bị cấm), và nếu có, bạn bấm ngược lại và cố gắng sửa nó. Đối với các ô trong tương lai, mô hình luôn mong đợi ô ngẫu nhiên tiếp theo là số 2 và xuất hiện ở phía đối diện với mô hình hiện tại (trong khi hàng đầu tiên chưa hoàn thành, ở góc dưới cùng bên phải, sau khi hoàn thành hàng đầu tiên, ở phía dưới bên trái góc).

Đây là thuật toán. Khoảng 80% chiến thắng (có vẻ như luôn có thể giành chiến thắng với các kỹ thuật AI "chuyên nghiệp" hơn, tôi không chắc về điều này.)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

Một vài gợi ý về các bước còn thiếu. Đây:

Mô hình đã thay đổi do may mắn là gần với mô hình dự kiến. Mô hình mà AI đang cố gắng đạt được là

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

Và chuỗi để đạt được điều đó đã trở thành:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

Các Okhoảng cấm đại diện ...

Vì vậy, nó sẽ nhấn sang phải, sau đó lại phải một lần nữa, sau đó (phải hoặc trên cùng tùy thuộc vào vị trí 4 đã tạo) sau đó sẽ tiếp tục hoàn thành chuỗi cho đến khi:

Vì vậy, bây giờ mô hình và chuỗi đã trở lại:

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

Điểm thứ hai, nó đã gặp xui xẻo và vị trí chính của nó đã bị chiếm đoạt. Có khả năng nó sẽ thất bại, nhưng nó vẫn có thể đạt được nó:

Đây là mô hình và chuỗi:

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

Khi đạt được 128, nó lại đạt được toàn bộ hàng:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x
96
Nicola Pezzotti 2014-03-27 12:13.

Tôi sao chép ở đây nội dung của một bài đăng trên blog của tôi


Giải pháp tôi đề xuất rất đơn giản và dễ thực hiện. Mặc dù, nó đã đạt đến số điểm là 131040. Một số điểm chuẩn của các hiệu suất thuật toán được trình bày.

Thuật toán

Thuật toán chấm điểm heuristic

Giả định mà thuật toán của tôi dựa trên khá đơn giản: nếu bạn muốn đạt điểm cao hơn, bảng phải được giữ càng ngăn nắp càng tốt. Đặc biệt, thiết lập tối ưu được đưa ra bởi một thứ tự giảm tuyến tính và đơn điệu của các giá trị ô. Trực giác này cũng sẽ cung cấp cho bạn giới hạn trên cho một giá trị ô: với n là số ô trên bảng.

(Có khả năng đạt đến ô 131072 nếu ô 4 được tạo ngẫu nhiên thay vì ô 2 khi cần)

Hai cách tổ chức bảng có thể được hiển thị trong các hình ảnh sau:

Để thực thi thứ tự sắp xếp của các ô theo thứ tự giảm dần đơn điệu, điểm si được tính bằng tổng các giá trị được tuyến tính hóa trên bảng nhân với các giá trị của một dãy hình học có tỷ lệ chung r <1.

Một số đường thẳng có thể được đánh giá cùng một lúc, điểm cuối cùng sẽ là điểm tối đa của bất kỳ đường nào.

Quy tắc quyết định

Quy tắc quyết định được thực hiện không hoàn toàn thông minh, mã bằng Python được trình bày ở đây:

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

Việc triển khai minmax hoặc Expectiminimax chắc chắn sẽ cải thiện thuật toán. Rõ ràng là một quy tắc quyết định phức tạp hơn sẽ làm chậm thuật toán và nó sẽ cần một thời gian để thực hiện. Tôi sẽ thử triển khai minimax trong tương lai gần. (giữ nguyên)

Điểm chuẩn

  • T1 - 121 bài kiểm tra - 8 đường dẫn khác nhau - r = 0,125
  • T2 - 122 bài kiểm tra - 8 đường dẫn khác nhau - r = 0,25
  • T3 - 132 bài kiểm tra - 8 đường dẫn khác nhau - r = 0,5
  • T4 - 211 bài kiểm tra - 2 đường dẫn khác nhau - r = 0,125
  • T5 - 274 bài kiểm tra - 2 đường dẫn khác nhau - r = 0,25
  • T6 - 211 bài kiểm tra - 2 đường dẫn khác nhau - r = 0,5

Trong trường hợp T2, bốn bài kiểm tra trong mười bài tạo ra ô 4096 với điểm trung bình là 42000

Bạn có thể tìm thấy mã trên GiHub tại liên kết sau: https://github.com/Nicola17/term2048-AI Nó dựa trên term2048 và được viết bằng Python. Tôi sẽ triển khai một phiên bản hiệu quả hơn trong C ++ càng sớm càng tốt.

43
cauchy 2015-12-22 00:49.

Tôi là tác giả của bộ điều khiển 2048 có điểm số tốt hơn bất kỳ chương trình nào khác được đề cập trong chủ đề này. Việc triển khai hiệu quả bộ điều khiển có sẵn trên github . Trong một repo riêng biệt cũng có mã được sử dụng để đào tạo chức năng đánh giá trạng thái của bộ điều khiển. Phương pháp đào tạo được mô tả trong bài báo .

Bộ điều khiển sử dụng tìm kiếm expectimax với chức năng đánh giá trạng thái được học từ đầu (không có chuyên môn của con người năm 2048) bằng một biến thể của việc học khác biệt theo thời gian (một kỹ thuật học tăng cường). Hàm giá trị trạng thái sử dụng mạng n-tuple , về cơ bản là một hàm tuyến tính có trọng số của các mẫu được quan sát trên bảng. Tổng cộng nó liên quan đến hơn 1 tỷ trọng lượng .

Hiệu suất

Ở 1 lần di chuyển / s: 609104 (trung bình 100 trận)

Ở 10 lần di chuyển / s: 589355 (trung bình 300 trận)

Ở tốc độ 3 lớp (khoảng 1500 di chuyển / s): 511759 (trung bình 1000 trận)

Thống kê ô cho 10 lần di chuyển / s như sau:

2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%

(Dòng cuối cùng có nghĩa là có các ô đã cho cùng một lúc trên bảng).

Đối với 3 lớp:

2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%

Tuy nhiên, tôi chưa bao giờ quan sát thấy nó có được ô 65536.

43
caub 2015-03-03 19:35.

Nỗ lực của tôi sử dụng expectimax giống như các giải pháp khác ở trên, nhưng không có bitboard. Giải pháp của Nneonneo có thể kiểm tra 10 triệu lượt di chuyển, xấp xỉ độ sâu 4 với 6 gạch còn lại và 4 bước di chuyển có thể (2 * 6 * 4) 4 . Trong trường hợp của tôi, độ sâu này mất quá nhiều thời gian để khám phá, tôi điều chỉnh độ sâu của tìm kiếm expectimax theo số ô trống còn lại:

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

Điểm số của bảng được tính bằng tổng bình phương của số ô trống và tích số chấm của lưới 2D với điều này:

[[10,8,7,6.5],
 [.5,.7,1,3],
 [-.5,-1.5,-1.8,-2],
 [-3.8,-3.7,-3.5,-3]]

lực lượng sắp xếp các ô xếp giảm dần theo kiểu con rắn từ ô trên cùng bên trái.

mã bên dưới hoặc trên github :

var n = 4,
	M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
	var p;
	while ((p = predict(ai)) != null) {
		move(p, ai);
	}
	//console.log(ai.grid , maxValue(ai.grid))
	ai.maxValue = maxValue(ai.grid)
	console.log(ai)
}

function initialize(ai) {
	ai.grid = [];
	for (var i = 0; i < n; i++) {
		ai.grid[i] = []
		for (var j = 0; j < n; j++) {
			ai.grid[i][j] = 0;
		}
	}
	rand(ai.grid)
	rand(ai.grid)
	ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
	var newgrid = mv(p, ai.grid);
	if (!equal(newgrid, ai.grid)) {
		//console.log(stats(newgrid, ai.grid))
		ai.grid = newgrid;
		try {
			rand(ai.grid)
			ai.steps++;
		} catch (e) {
			console.log('no room', e)
		}
	}
}

function predict(ai) {
	var free = freeCells(ai.grid);
	ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
	var root = {path: [],prob: 1,grid: ai.grid,children: []};
	var x = expandMove(root, ai)
	//console.log("number of leaves", x)
	//console.log("number of leaves2", countLeaves(root))
	if (!root.children.length) return null
	var values = root.children.map(expectimax);
	var mx = max(values);
	return root.children[mx[1]].path[0]

}

function countLeaves(node) {
	var x = 0;
	if (!node.children.length) return 1;
	for (var n of node.children)
		x += countLeaves(n);
	return x;
}

function expectimax(node) {
	if (!node.children.length) {
		return node.score
	} else {
		var values = node.children.map(expectimax);
		if (node.prob) { //we are at a max node
			return Math.max.apply(null, values)
		} else { // we are at a random node
			var avg = 0;
			for (var i = 0; i < values.length; i++)
				avg += node.children[i].prob * values[i]
			return avg / (values.length / 2)
		}
	}
}

function expandRandom(node, ai) {
	var x = 0;
	for (var i = 0; i < node.grid.length; i++)
		for (var j = 0; j < node.grid.length; j++)
			if (!node.grid[i][j]) {
				var grid2 = M.copy(node.grid),
					grid4 = M.copy(node.grid);
				grid2[i][j] = 2;
				grid4[i][j] = 4;
				var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
				var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
				node.children.push(child2)
				node.children.push(child4)
				x += expandMove(child2, ai)
				x += expandMove(child4, ai)
			}
	return x;
}

function expandMove(node, ai) { // node={grid,path,score}
	var isLeaf = true,
		x = 0;
	if (node.path.length < ai.depth) {
		for (var move of[0, 1, 2, 3]) {
			var grid = mv(move, node.grid);
			if (!equal(grid, node.grid)) {
				isLeaf = false;
				var child = {grid: grid,path: node.path.concat([move]),children: []}
				node.children.push(child)
				x += expandRandom(child, ai)
			}
		}
	}
	if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
	return isLeaf ? 1 : x;
}



var cells = []
var table = document.querySelector("table");
for (var i = 0; i < n; i++) {
	var tr = document.createElement("tr");
	cells[i] = [];
	for (var j = 0; j < n; j++) {
		cells[i][j] = document.createElement("td");
		tr.appendChild(cells[i][j])
	}
	table.appendChild(tr);
}

function updateUI(ai) {
	cells.forEach(function(a, i) {
		a.forEach(function(el, j) {
			el.innerHTML = ai.grid[i][j] || ''
		})
	});
}


updateUI(ai);
updateHint(predict(ai));

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai);
		updateUI(ai);
		updateHint(p);
		requestAnimationFrame(runAI);
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
		updateHint(predict(ai));
	}
}


function updateHint(dir) {
	hintvalue.innerHTML = ['↑', '→', '↓', '←'][dir] || '';
}

document.addEventListener("keydown", function(event) {
	if (!event.target.matches('.r *')) return;
	event.preventDefault(); // avoid scrolling
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai);
		updateHint(predict(ai));
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai);
	updateHint(predict(ai));
}


function stats(grid, previousGrid) {

	var free = freeCells(grid);

	var c = dot2(grid, snake);

	return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
	return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		r += a[i] * b[i];
	return r
}

function dot2(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		for (var j = 0; j < a[0].length; j++)
			r += a[i][j] * b[i][j]
	return r;
}

function product(a) {
	return a.reduce(function(v, x) {
		return v * x
	}, 1)
}

function maxValue(grid) {
	return Math.max.apply(null, grid.map(function(a) {
		return Math.max.apply(null, a)
	}));
}

function freeCells(grid) {
	return grid.reduce(function(v, a) {
		return v + a.reduce(function(t, x) {
			return t + (x == 0)
		}, 0)
	}, 0)
}

function max(arr) { // return [value, index] of the max
	var m = [-Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > m[0]) m = [arr[i], i];
	}
	return m
}

function min(arr) { // return [value, index] of the min
	var m = [Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < m[0]) m = [arr[i], i];
	}
	return m
}

function maxScore(nodes) {
	var min = {
		score: -Infinity,
		path: []
	};
	for (var node of nodes) {
		if (node.score > min.score) min = node;
	}
	return min;
}


function mv(k, grid) {
	var tgrid = M.itransform(k, grid);
	for (var i = 0; i < tgrid.length; i++) {
		var a = tgrid[i];
		for (var j = 0, jj = 0; j < a.length; j++)
			if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
		for (; jj < a.length; jj++)
			a[jj] = 0;
	}
	return M.transform(k, tgrid);
}

function rand(grid) {
	var r = Math.floor(Math.random() * freeCells(grid)),
		_r = 0;
	for (var i = 0; i < grid.length; i++) {
		for (var j = 0; j < grid.length; j++) {
			if (!grid[i][j]) {
				if (_r == r) {
					grid[i][j] = Math.random() < .9 ? 2 : 4
				}
				_r++;
			}
		}
	}
}

function equal(grid1, grid2) {
	for (var i = 0; i < grid1.length; i++)
		for (var j = 0; j < grid1.length; j++)
			if (grid1[i][j] != grid2[i][j]) return false;
	return true;
}

function conv44valid(a, b) {
	var r = 0;
	for (var i = 0; i < 4; i++)
		for (var j = 0; j < 4; j++)
			r += a[i][j] * b[3 - i][3 - j]
	return r
}

function MatrixTransform(n) {
	var g = [],
		ig = [];
	for (var i = 0; i < n; i++) {
		g[i] = [];
		ig[i] = [];
		for (var j = 0; j < n; j++) {
			g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
			ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations
		}
	}
	this.transform = function(k, grid) {
		return this.transformer(k, grid, g)
	}
	this.itransform = function(k, grid) { // inverse transform
		return this.transformer(k, grid, ig)
	}
	this.transformer = function(k, grid, mat) {
		var newgrid = [];
		for (var i = 0; i < grid.length; i++) {
			newgrid[i] = [];
			for (var j = 0; j < grid.length; j++)
				newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
		}
		return newgrid;
	}
	this.copy = function(grid) {
		return this.transform(3, grid)
	}
}
body {
	font-family: Arial;
}
table, th, td {
	border: 1px solid black;
	margin: 0 auto;
	border-collapse: collapse;
}
td {
	width: 35px;
	height: 35px;
	text-align: center;
}
button {
	margin: 2px;
	padding: 3px 15px;
	color: rgba(0,0,0,.9);
}
.r {
	display: flex;
	align-items: center;
	justify-content: center;
	margin: .2em;
	position: relative;
}
#hintvalue {
	font-size: 1.4em;
	padding: 2px 8px;
	display: inline-flex;
	justify-content: center;
	width: 30px;
}
<table title="press arrow keys"></table>
<div class="r">
    <button id=init>init</button>
    <button id=runai>run AI</button>
    <span id="hintvalue" title="Best predicted move to do, use your arrow keys" tabindex="-1"></span>
</div>

28
Vincent Lecrubier 2014-03-13 08:57.

Tôi nghĩ rằng tôi đã tìm thấy một thuật toán hoạt động khá tốt, vì tôi thường đạt điểm trên 10000, cá nhân tôi tốt nhất là khoảng 16000. Giải pháp của tôi không nhằm vào việc giữ những con số lớn nhất ở một góc, mà là giữ nó ở hàng trên cùng.

Vui lòng xem mã bên dưới:

while( !game_over ) {
    move_direction=up;
    if( !move_is_possible(up) ) {
        if( move_is_possible(right) && move_is_possible(left) ){
            if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) 
                move_direction = left;
            else
                move_direction = right;
        } else if ( move_is_possible(left) ){
            move_direction = left;
        } else if ( move_is_possible(right) ){
            move_direction = right;
        } else {
            move_direction = down;
        }
    }
    do_move(move_direction);
}
26
baltazar 2014-03-13 23:16.

Đã có một triển khai AI cho trò chơi này ở đây . Trích từ README:

Thuật toán lặp đi lặp lại làm sâu thêm tìm kiếm alpha-beta đầu tiên. Hàm đánh giá cố gắng giữ cho các hàng và cột đơn điệu (tất cả đều giảm hoặc tăng) trong khi giảm thiểu số lượng ô trên lưới.

Trên Hacker News cũng có một cuộc thảo luận về thuật toán này mà bạn có thể thấy hữu ích.

23
Khaled.K 2014-03-13 10:15.

Thuật toán

while(!game_over)
{
    for each possible move:
        evaluate next state

    choose the maximum evaluation
}

Đánh giá

Evaluation =
    128 (Constant)
    + (Number of Spaces x 128)
    + Sum of faces adjacent to a space { (1/face) x 4096 }
    + Sum of other faces { log(face) x 4 }
    + (Number of possible next moves x 256)
    + (Number of aligned values x 2)

Chi tiết đánh giá

128 (Constant)

Đây là một hằng số, được sử dụng làm đường cơ sở và cho các mục đích sử dụng khác như thử nghiệm.

+ (Number of Spaces x 128)

Nhiều khoảng trống hơn làm cho trạng thái linh hoạt hơn, chúng tôi nhân với 128 (là trung vị) vì lưới có 128 mặt là trạng thái không thể tối ưu.

+ Sum of faces adjacent to a space { (1/face) x 4096 }

Ở đây, chúng tôi đánh giá các khuôn mặt có khả năng hợp nhất, bằng cách đánh giá lùi chúng, ô 2 có giá trị 2048, trong khi ô 2048 được đánh giá là 2.

+ Sum of other faces { log(face) x 4 }

Ở đây, chúng ta vẫn cần kiểm tra các giá trị được xếp chồng lên nhau, nhưng theo cách nhỏ hơn mà không làm gián đoạn các tham số linh hoạt, vì vậy chúng ta có tổng của {x trong [4,44]}.

+ (Number of possible next moves x 256)

Một trạng thái linh hoạt hơn nếu nó có nhiều quyền tự do chuyển đổi hơn.

+ (Number of aligned values x 2)

Đây là một kiểm tra đơn giản về khả năng có các hợp nhất trong trạng thái đó, mà không cần xem xét trước.

Lưu ý: Các hằng số có thể được điều chỉnh ..

12
Sandipan Dey 2017-03-07 11:37.

Đây không phải là câu trả lời trực tiếp cho câu hỏi của OP, đây là nhiều thứ hơn (thí nghiệm) mà tôi đã thử cho đến nay để giải quyết vấn đề tương tự và thu được một số kết quả và có một số quan sát mà tôi muốn chia sẻ, tôi tò mò nếu chúng ta có thể có một số hiểu biết thêm từ điều này.

Tôi vừa thử triển khai minimax của mình bằng cách cắt tỉa alpha-beta với mức cắt độ sâu của cây tìm kiếm ở 3 và 5. Tôi đang cố gắng giải quyết vấn đề tương tự cho lưới 4x4 như một bài tập dự án cho khóa học edX ColumbiaX: Trí tuệ nhân tạo CSMM.101x ( AI) .

Tôi đã áp dụng kết hợp lồi (đã thử các trọng số heuristic khác nhau) của một vài hàm đánh giá heuristic, chủ yếu từ trực giác và từ những hàm đã thảo luận ở trên:

  1. Tính đơn điệu
  2. Dung lượng trống có sẵn

Trong trường hợp của tôi, trình phát máy tính là hoàn toàn ngẫu nhiên, nhưng tôi vẫn giả định cài đặt đối địch và triển khai tác nhân trình phát AI làm trình phát tối đa.

Tôi có lưới 4x4 để chơi trò chơi.

Quan sát:

Nếu tôi gán quá nhiều trọng số cho hàm heuristic đầu tiên hoặc hàm heuristic thứ hai, cả hai trường hợp điểm số mà người chơi AI nhận được đều thấp. Tôi đã chơi với nhiều bài tập trọng số có thể có cho các hàm heuristic và thực hiện một tổ hợp lồi, nhưng rất hiếm khi người chơi AI có thể ghi được 2048. Hầu hết các lần nó đều dừng lại ở 1024 hoặc 512.

Tôi cũng đã thử heuristic góc, nhưng vì một số lý do nó làm cho kết quả tồi tệ hơn, bất kỳ trực giác nào tại sao?

Ngoài ra, tôi đã cố gắng tăng giới hạn độ sâu tìm kiếm từ 3 lên 5 (tôi không thể tăng thêm vì tìm kiếm không gian đó vượt quá thời gian cho phép ngay cả khi cắt tỉa) và thêm một kinh nghiệm nữa xem xét các giá trị của các ô liền kề và đưa ra nhiều điểm hơn nếu chúng có thể hợp nhất, nhưng tôi vẫn không thể nhận được 2048.

Tôi nghĩ sẽ tốt hơn nếu sử dụng Expectimax thay vì minimax, nhưng tôi vẫn muốn giải quyết vấn đề này chỉ với minimax và đạt được điểm cao như 2048 hoặc 4096. Tôi không chắc liệu mình có thiếu thứ gì không.

Hình ảnh động bên dưới hiển thị một số bước cuối cùng của trò chơi do nhân viên AI chơi bằng trình phát máy tính:

Mọi thông tin chi tiết sẽ thực sự rất hữu ích, cảm ơn trước. (Đây là liên kết của bài đăng trên blog của tôi cho bài viết: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve -2048-game-with-computer / và video trên youtube: https://www.youtube.com/watch?v=VnVFilfZ0r4 )

Hình ảnh động sau đây cho thấy một vài bước cuối cùng của trò chơi được chơi trong đó tác nhân người chơi AI có thể nhận được 2048 điểm, lần này cũng thêm vào giá trị tuyệt đối heuristic:

Các số liệu sau đây cho thấy cây trò chơi được khám phá bởi tác nhân AI của người chơi, giả sử máy tính là kẻ thù chỉ trong một bước duy nhất:

9
wvdz 2014-04-04 14:49.

Tôi đã viết một bộ giải năm 2048 bằng Haskell, chủ yếu là vì tôi đang học ngôn ngữ này ngay bây giờ.

Cách triển khai trò chơi của tôi hơi khác so với trò chơi thực tế, ở chỗ một ô mới luôn là '2' (thay vì 90% 2 và 10% 4). Và rằng ô mới không phải ngẫu nhiên, mà luôn là ô có sẵn đầu tiên từ trên cùng bên trái. Biến thể này còn được gọi là Det 2048 .

Do đó, bộ giải này là xác định.

Tôi đã sử dụng một thuật toán toàn diện ủng hộ các ô trống. Nó hoạt động khá nhanh ở độ sâu 1-4, nhưng ở độ sâu 5 thì nó khá chậm với khoảng 1 giây mỗi lần di chuyển.

Dưới đây là đoạn mã thực hiện thuật toán giải. Lưới được biểu diễn dưới dạng một mảng Số nguyên có độ dài 16. Và việc ghi điểm được thực hiện đơn giản bằng cách đếm số ô vuông trống.

bestMove :: Int -> [Int] -> Int
bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]

gridValue :: Int -> [Int] -> Int
gridValue _ [] = -1
gridValue 0 grid = length $ filter (==0) grid  -- <= SCORING
gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]

Tôi nghĩ rằng nó khá thành công vì sự đơn giản của nó. Kết quả mà nó đạt được khi bắt đầu với một lưới trống và giải quyết ở độ sâu 5 là:

Move 4006
[2,64,16,4]
[16,4096,128,512]
[2048,64,1024,16]
[2,4,16,2]

Game Over

Có thể tìm thấy mã nguồn tại đây: https://github.com/popovitsj/2048-haskell

6
API-Beast 2014-03-15 11:53.

Thuật toán này không tối ưu để giành chiến thắng trong trò chơi, nhưng nó khá tối ưu về hiệu suất và số lượng mã cần thiết:

  if(can move neither right, up or down)
    direction = left
  else
  {
    do
    {
      direction = random from (right, down, up)
    }
    while(can not move in "direction")
  }
4
alan2here 2015-08-11 04:39.

Nhiều câu trả lời khác sử dụng AI với tính toán tốn kém tìm kiếm các tương lai có thể có, nghiên cứu kinh nghiệm, học tập và những thứ tương tự. Đây là những điều ấn tượng và có lẽ là con đường chính xác về phía trước, nhưng tôi muốn đóng góp một ý kiến ​​khác.

Mô hình hóa loại chiến lược mà những người chơi giỏi của trò chơi sử dụng.

Ví dụ:

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

Đọc các ô vuông theo thứ tự hiển thị ở trên cho đến khi giá trị ô vuông tiếp theo lớn hơn giá trị hiện tại. Điều này cho thấy vấn đề khi cố gắng hợp nhất một ô khác có cùng giá trị vào ô vuông này.

Để giải quyết vấn đề này, họ có 2 cách để di chuyển không còn sót lại hoặc tệ hơn và kiểm tra cả hai khả năng có thể ngay lập tức phát hiện ra nhiều vấn đề hơn, điều này tạo thành một danh sách các yếu tố phụ thuộc, mỗi vấn đề yêu cầu một vấn đề khác được giải quyết trước. Tôi nghĩ rằng tôi có chuỗi này hoặc trong một số trường hợp là cây phụ thuộc trong nội bộ khi quyết định bước đi tiếp theo của mình, đặc biệt là khi bị mắc kẹt.


Ngói cần hợp nhất với hàng xóm nhưng quá nhỏ: Hợp nhất hàng xóm khác với hàng này.

Ô lớn hơn theo cách: Tăng giá trị của ô nhỏ hơn xung quanh.

Vân vân...


Toàn bộ cách tiếp cận có thể sẽ phức tạp hơn thế này nhưng không phức tạp hơn nhiều. Đó có thể là cảm giác máy móc thiếu điểm số, trọng lượng, tế bào thần kinh và tìm kiếm sâu về các khả năng. Cây khả năng thậm chí cần phải đủ lớn để không cần phân nhánh.

Related questions

MORE COOL STUFF

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett đã bất chấp những lời khuyên hẹn hò điển hình khi cô gặp chồng mình.

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Michael Sheen là một diễn viên phi lợi nhuận nhưng chính xác thì điều đó có nghĩa là gì?

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Ngôi sao của Hallmark Colin Egglesfield chia sẻ về những cuộc gặp gỡ với người hâm mộ ly kỳ tại RomaDrama Live! cộng với chương trình INSPIRE của anh ấy tại đại hội.

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Bạn sẽ phải phủi sạch đầu đĩa Blu-ray hoặc DVD để xem tại sao Northern Exposure trở thành một trong những chương trình nổi tiếng nhất của thập niên 90.

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

8 công dụng tuyệt vời của Baking Soda và Giấm

8 công dụng tuyệt vời của Baking Soda và Giấm

Bạn biết đấy, hai sản phẩm này là nguồn điện để làm sạch, riêng chúng. Nhưng cùng với nhau, chúng có một loạt công dụng hoàn toàn khác.

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Thủy điện rất cần thiết cho lưới điện của Hoa Kỳ, nhưng nó chỉ tạo ra năng lượng khi có nước di chuyển. Bao nhiêu nhà máy thủy điện có thể gặp nguy hiểm khi các hồ và sông cạn kiệt?

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Tóc tỉa từ các tiệm và các khoản quyên góp cá nhân có thể được tái sử dụng như những tấm thảm thấm dầu và giúp bảo vệ môi trường.

BoJack Horseman vẫn gan ruột và gan dạ hơn bao giờ hết trong phần 3

BoJack Horseman vẫn gan ruột và gan dạ hơn bao giờ hết trong phần 3

BoJack Horseman (Ảnh: Netflix) BoJack Horseman bắt đầu mùa thứ ba với sự xuất hiện của nhân vật tiêu biểu, người vẫn đang theo đuổi những lời khen ngợi từ giới phê bình trong một nỗ lực tuyệt vọng để tìm ra ý nghĩa trong cuộc sống của mình. Mùa thứ hai về số phận bi kịch của Raphael Bob-Waksberg dày đặc những trò đùa cũng như tuyệt vọng.

Xem cách tính năng lái tự động cập nhật của Tesla bùng phát như thế nào khi bạn bỏ qua các cảnh báo của nó

Xem cách tính năng lái tự động cập nhật của Tesla bùng phát như thế nào khi bạn bỏ qua các cảnh báo của nó

Bản nâng cấp Phiên bản 8.0 gần đây của Tesla đối với hệ thống Lái xe tự động được thiết kế để cải thiện hệ thống và mối quan hệ của nó với người lái.

UnREAL, Chương trình Truyền hình Về Truyền hình Thực tế Chúng tôi Không biết Chúng tôi Cần

UnREAL, Chương trình Truyền hình Về Truyền hình Thực tế Chúng tôi Không biết Chúng tôi Cần

Chắc chắn khi con cái chúng ta xem lại các chương trình chúng ta đã xem vào khoảng năm 2015, chúng sẽ thấy UnREAL, một chương trình truyền hình mới chiếu vào tối Thứ Hai của Lifetime — bạn sẽ thấy đúng lúc, sẽ phát sóng ngay sau khi The Bachelor kết thúc — như một chương trình không thể được thực hiện vào bất kỳ thời điểm nào khác trong lịch sử truyền hình, nhưng một chương trình cảm thấy cần thiết để xem bây giờ. UnREAL có sự tham gia của Shiri Appleby trong vai Rachel, một nhà sản xuất truyền hình cho một chương trình về cơ bản là The Bachelor, mặc dù trong thế giới này, nó được gọi là Vĩnh viễn.

Sau tất cả, Josh Trank sẽ không đạo diễn bộ phim tuyển tập Star Wars thứ hai

Sau tất cả, Josh Trank sẽ không đạo diễn bộ phim tuyển tập Star Wars thứ hai

Thông báo chính thức đến trực tiếp từ trang web của Star Wars: Fantastic Four, đạo diễn Josh Trank, một người bí ẩn không xuất hiện tại đại hội Star Wars Celebration gần đây, sẽ không chỉ đạo phần hai Star Wars Anthology. Đây là tuyên bố được đăng ngày hôm qua: Tất cả thực sự là ngôn ngữ rất lịch sự, nhưng một bài báo của Hollywood Reporter cho thấy tất cả đều không tốt ở hậu trường, gọi sự ra đi là "một vụ sa thải" một phần dựa trên "hành vi bất thường" của Trank trong khi quay Fantastic Four: The Bài báo trích dẫn các nguồn gọi là Trank “đôi khi thiếu quyết đoán và thiếu sáng tạo,” và lưu ý rằng Fantastic Four, khởi chiếu vào ngày 7 tháng 8, đã được khởi động lại vào cuối tháng 4.

Edwin McCain ra mắt Grand Ole Opry: Quay cảnh hậu trường với nhạc sĩ 'I'll Be'

Edwin McCain ra mắt Grand Ole Opry: Quay cảnh hậu trường với nhạc sĩ 'I'll Be'

McCain, người đang làm việc cho một album mới, lần đầu tiên bước vào vòng kết nối vào tối thứ Sáu ở Nashville

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa. Từ Hollywood đến New York và mọi nơi ở giữa, hãy xem các ngôi sao yêu thích của bạn đang làm gì!

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

Các nhà điều tra đang xem xét liệu nhóm và nghi phạm có biết nhau trước vụ tấn công hay không

Tôi viết như thế nào

Tôi viết như thế nào

Đối với tôi, mọi thứ là về dòng đầu tiên đó và nó sẽ đưa bạn đến đâu. Một số nhà văn bị điều khiển bởi cốt truyện, sự sắp xếp tinh tế của các quân cờ, trong khi những người khác bị lôi cuốn bởi một nhân vật và khả năng thực hiện một cuộc hành trình với một người bạn hư cấu mới.

Đường băng hạ cánh

Đường băng hạ cánh

Cuối hè đầu thu là mùa hoài niệm. Những chiếc đèn đường chiếu ánh sáng của chúng qua những con đường đẫm mưa, và những chiếc lá dưới chân - màu đỏ cam tắt trong bóng chạng vạng - là lời nhắc nhở về những ngày đã qua.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Vào năm 2021, tôi khuyến khích bạn suy nghĩ lại mọi thứ bạn biết về khách hàng mà bạn phục vụ và những câu chuyện bạn kể cho họ. Lùi lại.

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Vào ngày sinh nhật thứ 9 của Felix The Cat, tôi nhớ về một trong những mất mát lớn nhất trong cuộc đời trưởng thành của tôi - Sophie của tôi vào năm 2013. Tôi đã viết bài luận này và chia sẻ nó trên nền tảng này một thời gian ngắn vào năm 2013.

Language