Câu hỏi Thuật toán tối ưu cho game 2048 là gì?


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ỳ trong bốn hướng nào để 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ị của một trong hai 2 hoặc là 4. Trò chơi kết thúc khi tất cả các ô được lấp đầy và không có di chuyển nào có thể hợp nhất các ô hoặc bạn tạo một ô có giá trị 2048.

Một, tôi cần phải làm 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ị 2 và 4, đó là, tôi cố gắng có 2 và 4 gạch, càng ít càng tốt. Nếu tôi thử nó theo cách này, tất cả các loại gạch khác sẽ tự động được sáp nhập và chiến lược có vẻ tốt.

Nhưng, 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 AFAIK tối đa là hơn 20.000 điểm, lớn hơn điểm hiện tại của tôi. Có một thuật toán tốt hơn so với ở trên?


1755
2018-03-12 05:37


gốc


Điều này có thể giúp! ov3y.github.io/2048-AI - cegprakash
@ nitish712 bằng cách này, thuật toán của bạn là tham lam kể từ khi bạn có choose the move with large number of merges mà nhanh chóng dẫn đến optima địa phương - Khaled.K
@ 500-InternalServerError: Nếu tôi đã thực hiện một AI với việc cắt tỉa cây trò chơi alpha-beta, nó sẽ giả định rằng các khối mới được đặt ở vị trí bất lợi. Đó là một giả định tồi tệ nhất, nhưng có thể hữu ích. - Charles
Một sự phân tâm thú vị khi bạn không có thời gian để nhắm vào một điểm số cao: Hãy cố gắng để có được điểm số thấp nhất có thể. Về lý thuyết nó xen kẽ 2s và 4s. - Mark Hurd
Thảo luận về tính hợp pháp của câu hỏi này có thể được tìm thấy trên meta: meta.stackexchange.com/questions/227266/… - Jeroen Vannevel


Các câu trả lời:


Tôi đã phát triển một AI 2048 sử dụng expectimax tối ưu hóa, thay vì tìm kiếm minimax được sử dụng bởi thuật toán @ ovolve. AI chỉ 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 trên tất cả các ô có thể sinh ra (được xác định bởi xác suất gạch, nghĩa là 10% cho 4 và 90% cho 2). Theo như tôi biết, không thể tỉa tối ưu hóa mong muốn (ngoại trừ việc loại bỏ các nhánh cực kỳ khó xảy ra), và vì vậy thuật toán được sử dụng là tìm kiếm lực lượng 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 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 là 5-10 lần mỗi giây trong suốt toàn bộ trò chơi. Nếu độ sâu tìm kiếm bị giới hạn trong 6 lần di chuyển, 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 làm cho một số xem thú vị.

Để đánh giá hiệu năng điểm số của AI, tôi chạy AI 100 lần (được kết nối với trò chơi trình duyệt thông qua điều khiển từ xa). Đối với mỗi ô, dưới đây là tỷ lệ các trò chơi mà trong đó ô đó đã đạ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 số tối đa đạt được là 794076. Điểm số trung bình là 387222. AI không bao giờ thất bại trong việc có được 2048 ngói (vì vậy nó không bao giờ bị mất trò chơi ngay cả một lần trong 100 trò chơi); trên thực tế, nó đã đạt được 8192 gạch ít nhất một lần trong mọi lần chạy!

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

32768 tile, score 794076

Trò chơi này mất 27830 di chuyển trên 96 phút, hoặc trung bình 4,8 di chuyển mỗi giây.

Thực hiện

Cách tiếp cận của tôi mã hóa toàn bộ bảng (16 mục) thành một số nguyên 64 bit (trong đó các lát là các khối nybbles, tức là khối 4 bit). Trên máy tính 64 bit, điều này cho phép toàn bộ bảng được truyền xung quanh trong một thanh ghi máy đơn lẻ.

Thao tác 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 cột đơn là một số lượng 16 bit, do đó 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 một cột. Ví dụ: di chuyển được triển khai dưới dạng 4 lần tra cứu thành bảng "hiệu ứng di chuyển" được xác định trước, mô tả cách mỗi chuyển động ả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 "1122 -> 0023" mô tả cách hàng [2,2,4,4] trở thành hàng [0,0,4,8] khi di chuyển sang phải).

Ghi đ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 các điểm heuristic 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ủa các giá trị bảng trên mỗi hàng và cột.

Biểu diễn 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 (trê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).

Bản thân tìm kiếm expectimax được mã hóa như là một tìm kiếm đệ quy xen kẽ giữa các bước "mong đợi" (kiểm tra tất cả các vị trí và giá trị của vị trí gạch có thể, và tăng trọng số tối ưu của chúng theo xác suất của từng khả năng) và "tối đa hóa". và chọn người có điểm số cao nhất). Tìm kiếm cây chấm dứt khi nó nhìn thấy một vị trí nhìn thấy trước đó (sử dụng một bảng chuyển vị), khi đạt đến giới hạn độ sâu được xác định trước hoặc khi đạt đến trạng thái bảng không chắc chắn (ví dụ: nó đạt được bằng cách nhận được cá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 di chuyển.

Heuristics

Một số heuristics được sử dụng để chỉ đạo các thuật toán tối ưu hóa theo hướng 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 heuristics khác nhau được cân nhắc và kết hợp thành một điểm số vị trí, trong đó xác định như thế nào "tốt" một vị trí ban nhất định là. Tìm kiếm tối ưu hóa sau đó sẽ nhằm mục đích tối đa hóa điểm số trung bình của tất cả các vị trí có thể có của hội đồng quản trị. Điểm số thực tế, như được hiển thị bởi trò chơi, là không phải được sử dụng để tính toán điểm số của bảng, vì nó quá nặng nề có lợi cho việc hợp nhất gạch (khi việc sáp nhập bị trì hoãn có thể tạo ra lợi ích lớn).

Ban đầu, tôi đã sử dụng hai phỏng đoán rất đơn giản, cấp "tiền thưởng" cho các ô vuông mở và có các giá trị lớn trên cạnh. Những chẩn đoán được thực hiện khá tốt, thường xuyên đạt được 16384 nhưng không bao giờ nhận được đến 32768.

Petr Morávek (@xificurk) lấy AI của tôi và bổ sung thêm hai chẩn đoán mới. Các heuristic đầu tiên là một hình phạt cho có hàng không đơn điệu và cột tăng lên khi xếp hạng tăng lên, đảm bảo rằng hàng không đơn điệu của 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ó số lượng lớn làm tổn thương đáng kể điểm số. Phương pháp heuristic thứ hai tính 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 chẩn đoán này được sử dụng để đẩy thuật toán 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 với nhiều lần hợp nhất (khuyến khích nó sắp xếp các hợp nhất khi có thể để có hiệu ứng lớn hơn).

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

Hiệu quả của những thay đổi này là cực kỳ quan trọng. Thuật toán đi từ việc đạt được 16384 ngói khoảng 13% thời gian để đạt được nó trên 90% thời gian, và thuật toán bắt đầu đạt 32768 trên 1/3 thời gian (trong khi các heuristics cũ không bao giờ một lần sản xuất một gạch 32768) .

Tôi tin rằng vẫn còn chỗ để cải thiện về chẩn đoán. 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 nó khá gần.


Đó là AI đạt được 32768 viên gạch trong hơn một phần ba các 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 nếu bất kỳ người chơi nào đã đạt được 32768 trận đấu chính thức (tức là không sử dụng các công cụ như savestates hoặc undo). Tôi nghĩ rằng ngói 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.


1132
2018-03-19 07:22



@ RobL: 2 xuất hiện 90% thời gian; 4 xuất hiện 10% thời gian. Nó ở trong mã nguồn: var value = Math.random() < 0.9 ? 2 : 4;. - nneonneo
Hiện đang chuyển sang Cuda để GPU hoạt động với tốc độ tốt hơn! - nimsson
@nneonneo Tôi đã chuyển mã của bạn bằng emscripten sang javascript và nó hoạt động khá tốt trong trình duyệt hiện nay! Cool để xem, mà không cần phải biên dịch và tất cả mọi thứ ... Trong Firefox, hiệu suất khá tốt ... - reverse_engineer
Giới hạn lý thuyết trong một lưới 4x4 thực sự IS 131072 không 65536. Tuy nhiên đòi hỏi phải có một 4 trong thời điểm thích hợp (tức là toàn bộ hội đồng quản trị đầy 4 .. 65536 mỗi một lần - 15 lĩnh vực chiếm đóng) và hội đồng quản trị phải được thiết lập tại đó thời điểm để bạn thực sự có thể kết hợp. - Bodo Thiesen
@nneonneo Bạn có thể muốn kiểm tra AI của chúng tôi, điều này có vẻ tốt hơn, nhận được 32 nghìn trong 60% trò chơi: github.com/aszczepanski/2048 - cauchy


Tôi là tác giả của chương trình AI mà người khác đã đề cập trong chủ đề này. Bạn có thể xem AI trong 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 chạy trong javascript trong trình duyệt trên máy tính xách tay của tôi cho khoảng 100 mili giây suy nghĩ mỗi lần di chuyển, vì vậy trong khi không hoàn hảo (chưa!) Nó hoạt động khá tốt.

Vì trò chơi là 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ờ đam, 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 đó, cụ thể là minimax  Tìm kiếm 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 chẩn đoán chính mà tôi sử dụng trong chức năng đánh giá tĩnh và chính thức hóa nhiều trực giác mà người khác đã thể hiện ở đây.

Tính đơn điệu

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

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

A perfectly monotonic 2048 board

Êm ái

Các heuristic trên một mình có xu hướng tạo ra các cấu trúc trong đó gạch liền kề đang giảm giá trị, nhưng tất nhiên để hợp nhất, gạch liền kề cần phải có cùng một giá trị. Do đó, độ mịn của heuristic chỉ đo lường sự khác biệt về giá trị giữa các ô lân cận, cố gắng giảm thiểu số lượng này.

Một người bình luận trên Hacker News đã cho một cách chính thức thú vị của ý tưởng này về lý thuyết đồ thị.

Đây là một ảnh chụp màn hình của một lưới hoàn toàn trơn tru, lịch sự của cái nĩa tuyệt vời này.

A perfectly smooth 2048 board

Gạch miễn phí

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

Và đó là nó! Tìm kiếm thông qua 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 tốt đáng kể. Một lợi thế để sử dụng một cách tiếp cận tổng quát như thế này chứ không phải là một 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 thấy các giải pháp thú vị và bất ngờ. Nếu bạn xem nó chạy, nó thường sẽ làm cho những động tác đáng ngạc nhiên nhưng hiệu quả, như đột nhiên chuyển đổi tường hoặc góc mà nó xây dựng chống lại.

Chỉnh sửa:

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

4096

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


1224
2018-03-13 20:04



Bạn có thể xử lý máy tính đặt các ô '2' và '4' làm 'đối thủ'. - Wei Yen
@WeiYen Chắc chắn, nhưng liên quan đến nó như là một vấn đề minmax không trung thành với logic trò chơi, bởi vì máy tính được đặt gạch ngẫu nhiên với xác suất nhất định, hơn là cố ý giảm thiểu số điểm. - koo
Mặc dù AI là ngẫu nhiên đặt gạch, mục tiêu là không để mất. Không may mắn là điều tương tự khi đối thủ chọn động thái tồi tệ nhất cho bạn. Phần "min" có nghĩa là bạn cố gắng chơi thận trọng để không có những động thái khủng khiếp mà bạn có thể trở nên không may mắn. - FryGuy
Tôi đã có một ý tưởng để tạo ra một ngã ba của năm 2048, nơi mà các máy tính thay vì đặt 2s và 4s ngẫu nhiên sử dụng AI của bạn để xác định nơi để đặt các giá trị. Kết quả: tuyệt đối không thể. Có thể thử ở đây: sztupy.github.io/2048-Hard - SztupY
@ SztupY Wow, đây là điều ác. Làm tôi nhớ đến qntm.org/hatetris Hatetris, mà cũng cố gắng để đặt các mảnh đó sẽ cải thiện tình hình của bạn ít nhất. - Patashu


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ĩ ý 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ỉ trông một gạch phía trước. Nó đã được gửi sớm trong tiến trình 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 may mắn đơn giản gần kết thúc (bạn buộc phải di chuyển xuống, mà bạn không bao giờ nên làm, và một gạch xuất hiện nơi cao nhất của bạn nên được. Chỉ cần cố gắng giữ cho hàng đầu đầy, vì vậy di chuyển trái không phá vỡ các mô hình), nhưng về cơ bản bạn kết thúc có một phần cố định và một phần di động để chơi với. Đây là mục tiêu của bạn:

Ready to finish

Đâ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ờ nhấn một phím (di chuyển bị cấm), và nếu bạn làm thế, bạn nhấn ngược lại và cố sửa nó. Đối với các tile trong tương lai, model luôn mong đợi tile ngẫu nhiên tiếp theo là 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, khi hàng đầu tiên được hoàn thành, phía dưới bên trái góc).

Đây là thuật toán. Khoảng 80% thắng (có vẻ như luôn luôn có thể giành chiến thắng với nhiều kỹ thuật AI "chuyên nghiệp" hơn, mặc dù tôi không chắc chắn 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: model change

Mô hình đã thay đổi do may mắn được gần gũi hơn với mô hình dự kiến. Mô hình 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 O đại diện cho không gian bị cấm ...

Vì vậy, nó sẽ bấm phải, sau đó phải một lần nữa, sau đó (phải hoặc đầu tùy thuộc vào nơi mà 4 đã tạo ra) sau đó sẽ tiến hành hoàn thành chuỗi cho đến khi nó được:

Chain completed

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

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

Con trỏ thứ hai, nó đã có may mắn và vị trí chính của nó đã được thực hiện. Có khả năng nó sẽ thất bại, nhưng nó vẫn có thể đạt được nó:

Enter image description here

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

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

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

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x

119
2018-03-12 16:05



execute move with best score làm thế nào bạn có thể đánh giá số điểm tốt nhất trong số các tiểu bang có thể có tiếp theo? - Khaled.K
heuristic được định nghĩa trong evaluateResult về cơ bản bạn cố gắng để đạt được gần nhất với kịch bản tốt nhất có thể. - Daren
@ Daren Tôi đang chờ chi tiết cụ thể của bạn - ashu
@ashu Tôi đang làm việc trên đó, hoàn cảnh bất ngờ đã để lại cho tôi mà không có thời gian để hoàn thành nó. Trong khi đó tôi đã cải thiện thuật toán và bây giờ nó giải quyết được 75% thời gian. - Daren
Những gì tôi thực sự thích về chiến lược này là tôi có thể sử dụng nó khi chơi các trò chơi bằng tay, nó đã cho tôi lên đến 37k điểm. - Cephalopod


Tôi đã trở nên quan tâm đến ý tưởng về AI cho trò chơi này có chứa không có thông tin mã hóa cứng (nghĩa là không có chẩn đoán, chức năng ghi điểm vv). AI nên "biết" chỉ quy tắc trò chơi và "tìm ra" chơi trò chơi. Điều này trái ngược với hầu hết các AI (giống như những người trong chủ đề này), nơi chơi trò chơi về cơ bản là sức mạnh vũ phu được điều khiển bởi một hàm điểm biểu diễ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 đáng ngạc nhiên: Để xác định bước di chuyển tiếp theo cho một bảng đã cho, AI sẽ chơi trò chơi trong bộ nhớ bằng di chuyển ngẫu nhiên cho đến khi trò chơi kết thúc. Điều này được thực hiện nhiều lần trong khi theo dõi điểm số trận đấu kết thúc. Sau đó, điểm kết thúc trung bình mỗi lần di chuyển được tính toán. Việc di chuyển bắt đầu với điểm kết thúc trung bình cao nhất được chọn là bước di chuyển 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 2048 lượt gạch 80% số lần và 4096 ô xếp 50% số lần. Sử dụng 10000 lần chạy được 2048 lát 100%, 70% cho 4096 lát và khoảng 1% cho gạch 8192.

Xem nó trong hành động

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

best score

Một thực tế thú vị về thuật toán này là trong khi các trò chơi ngẫu nhiên không đáng ngạc nhiên lắm, việc chọn di chuyển tốt nhất (hoặc ít nhất là xấu) 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à 3000 lần di chuyển cuối cùng, trò chơi chơi ngẫu nhiên trong bộ nhớ từ bất kỳ vị trí cụ thể nào mang lại trung bình 340 điểm bổ sung trong khoảng 40 lần di chuyển trước khi chết. (Bạn có thể thấy điều này cho chính mình bằng cách chạy AI và mở bảng điều khiển gỡ lỗi.)

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

scoring graph

Tôi thấy nó khá ngạc nhiên khi thuật toán không cần phải thực sự thấy trước chơi trò chơi tốt để chọn những động tác 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à Pure Monte Carlo Tree tìm kiếm thuật toán.

Thực hiện và Liên kết

Đầu tiên tôi tạo một phiên bản JavaScript có thể nhìn thấy trong hành động ở đây. Phiên bản này có thể chạy 100 chạy trong thời gian tốt. Mở bảng điều khiển để biết thêm thông tin. (nguồn)

Sau đó, để chơi xung quanh một số chi tiết 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 trong C ++. Phiên bản này cho phép lên tới 100000 lần chạy mỗi lần di chuyển và thậm chí 1000000 nếu bạn có sự kiên nhẫn. Hướng dẫn xây dựng được cung cấp. Nó chạy trong giao diện điều khiển và cũng có một đ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, tăng số lượng chạy không cải thiện đáng kể chơi trò chơi. Dường như có giới hạn cho chiến lược này vào khoảng 80000 điểm với gạch 4096 và tất cả những cái nhỏ hơn, rất gần với việc đạt được gạch 8192. Tăng số lần chạy từ 100 lên 100000 tăng tỷ lệ cược của việc đạt đến giới hạn số điểm này (từ 5% đến 40%) nhưng không vượt qua nó.

Chạy 10000 chạy với mức tăng tạm thời lên 1000000 gần các vị trí quan trọng được quản lý để phá vỡ rào cản này ít hơn 1% số lần đạt được số điểm tối đa là 129892 và gạch 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 min, max và avg. Tôi cũng đã cố gắng sử dụng độ sâu: Thay vì thử K chạy mỗi lần di chuyển, tôi đã thử di chuyển K mỗi lần di chuyển danh sách của một độ dài nhất định (ví dụ: "lên, lên, trái") và chọn di chuyển đầu tiên của danh sách di chuyển điểm tốt nhất.

Sau đó tôi đã thực hiện một cây ghi điểm có tính đến khả năng có điều kiện của việc có thể chơi một động thái sau một danh sách di chuyển nhất định.

Tuy nhiên, không ai trong số những ý tưởng này cho thấy bất kỳ lợi thế thực sự nào so với ý tưởng đầu tiên đơn giản. Tôi để lại mã cho những ý tưởng này nhận xét 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 được quản lý vô tình chạm đến ô xếp cao nhất tiếp theo. Điều này giúp cải thiện thời gian.

Tôi muốn được quan tâm để nghe nếu có ai có ý tưởng cải tiến khác để duy trì sự độc lập của AI.

2048 Biến thể và bản sao

Chỉ để cho vui, tôi cũng triển khai AI làm bookmarklet, hooking vào điều khiển của trò chơi. Điều này cho phép AI làm việc với trò chơi gốc và nhiều biến thể của nó.

Điều này là có thể do tính chất độc lập của AI. Một số biến thể khá khác biệt, chẳng hạn như lục giác lục giác.


114
2018-05-25 09:25



+1. Là một sinh viên AI, tôi thấy điều này thực sự thú vị. Sẽ có cái nhìn tốt hơn về điều này trong thời gian rảnh. - Isaac
Thật đáng kinh ngạc! Tôi đã dành hàng giờ để tối ưu hóa trọng lượng cho một chức năng heuristic tốt cho expectimax và tôi thực hiện điều này trong 3 phút và điều này hoàn toàn đập vỡ nó. - Brendan Annable
Sử dụng tốt mô phỏng Monte Carlo. - nneonneo
Việc xem vở kịch này đang kêu gọi chứng ngộ. Điều này thổi tất cả các heuristics nhưng nó hoạt động. Xin chúc mừng ! - Stéphane Gourichon
Đến nay, giải pháp thú vị nhất ở đây. - shebaw


Tôi sao chép ở đây nội dung của đă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 131040. Một số điểm chuẩn của các buổi biểu diễn thuật toán được trình bày.

Score

Thuật toán

Thuật toán tính đ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 được điểm số cao hơn, hội đồng quản trị phải được giữ càng gọn 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ị xếp kề. Trực giác này cũng sẽ cung cấp cho bạn giới hạn trên cho giá trị lát: s trong đó n là số ô trên bảng.

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

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

enter image description here

Để thực thi sự sắp xếp của các gạch theo một thứ tự giảm đơn điệu, điểm số si tính như tổng của các giá trị tuyến tính trên bảng nhân với các giá trị của một chuỗi hình học với tỷ số chung r <1.

s

s

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

Quy tắc quyết định

Quy tắc quyết định được triển khai không hoàn toàn thông minh, mã trong 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 tinh vi sẽ làm chậm thuật toán và nó sẽ yêu cầu một thời gian để được triển khai. Tôi sẽ thử triển khai minimax trong tương lai gần. (hãy chú ý theo dõi)

Điểm chuẩn

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

enter image description here enter image description here enter image description here enter image description here

Trong trường hợp T2, bốn thử nghiệm trong mười tạo ra ngói 4096 với điểm số trung bình là s 42000

Mã số

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 Dựa theo term2048 và nó được viết bằng Python. Tôi sẽ thực hiện một phiên bản hiệu quả hơn trong C ++ càng sớm càng tốt.


88
2018-03-26 22:13



Không tệ, minh hoạ của bạn đã cho tôi một ý tưởng, lấy các vectơ hợp nhất vào đánh giá - Khaled.K


Nỗ lực của tôi sử dụng expectimax như các giải pháp khác ở trên, nhưng không có bitboard. Nneonneo của giải pháp có thể kiểm tra 10millions di chuyển đó là khoảng một chiều sâu của 4 với 6 gạch trái và 4 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ố lượng ô miễn phí còn lại:

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

Điểm số của các bảng được tính bằng tổng trọng số của hình vuông số lượng gạch miễn phí và sản phẩm 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]]

mà lực lượng sắp xếp gạch giảm dần trong một loại rắn từ gạch trên cùng bên trái.

Mã dưới đây hoặc jsbin:

  
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)

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


hint.onclick = function() {
	hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)]
}
document.addEventListener("keydown", function(event) {
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai)
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(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 {
	text-align: center
}
table, th, td {
    border: 1px solid black;
    margin: 5px auto;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}
<table></table>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>


30
2018-03-03 05:35



Không chắc chắn tại sao điều này không có nhiều upvotes hơn. Nó thực sự hiệu quả vì nó đơn giản. - David Greydanus
Cảm ơn, câu trả lời trễ và nó hoạt động không thực sự tốt (hầu như luôn ở trong [1024, 8192]), hàm chi phí / số liệu thống kê cần nhiều công việc hơn - caub
Làm thế nào bạn có trọng lượng các không gian trống? - David Greydanus
Nó đơn giản cost=1x(number of empty tiles)²+1xdotproduct(snakeWeights,grid) và chúng tôi cố gắng tối đa hóa chi phí này - caub
Điều này cần nhiều Upvotes hơn! Great Code! - Smartis


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 cao hơn 10000, tốt nhất cá nhân của tôi là khoảng 16000. Giải pháp của tôi không nhằm mục đích giữ số lớn nhất trong một góc, nhưng để 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);
}

25
2018-03-12 18:57



Tôi chạy 100.000 trò chơi thử nghiệm điều này so với chiến lược tuần hoàn tầm thường "lên, phải, lên, trái, ..." (và xuống nếu nó phải). Chiến lược tuần hoàn đã hoàn thành "điểm số trung bình của" 770.6, trong khi cái này chỉ có 396.7. Bạn có đoán tại sao điều đó có thể là? Tôi nghĩ rằng nó có quá nhiều thăng trầm, ngay cả khi trái hoặc phải sẽ hợp nhất nhiều hơn nữa. - Thomas Ahle
Gạch có xu hướng xếp chồng theo những cách không tương thích nếu chúng không bị dịch chuyển theo nhiều hướng. Nói chung, sử dụng một chiến lược tuần hoàn sẽ dẫn đến những viên gạch lớn hơn ở trung tâm, khiến cho việc điều động trở nên chật chội hơn nhiều. - bcdan


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 thực hiện hiệu quả bộ điều khiển có sẵn trên github. Trong một repo riêng biệt đó cũng là 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 giấy.

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 2048) bằng một biến thể sự khác biệt thời gian học tập (một kỹ thuật học tăng cường). Hàm giá trị trạng thái sử dụng một 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. Nó liên quan nhiều hơn 1 tỷ trọng lượng, Tổng cộng.

Hiệu suất

Tại 1 lần di chuyển / giây: 609104 (100 trò chơi trung bình)

Với 10 lần di chuyển / giây: 589355 (300 trò chơi trung bình)

Tại 3-ply (khoảng 1500 di chuyển / s): 511759 (Trung bình 1000 trò chơi)

Số liệu thống kê ô cho 10 lần di chuyển / giây 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 viên gạch đã 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 nó có được lát gạch 65536.


25
2017-12-21 10:49



Kết quả khá ấn tượng. Tuy nhiên có thể bạn có thể cập nhật câu trả lời để giải thích (khoảng, trong thuật ngữ đơn giản ... Tôi chắc chắn các chi tiết đầy đủ sẽ là quá dài để đăng ở đây) làm thế nào chương trình của bạn đạt được điều này? Như trong một lời giải thích thô về cách thuật toán học tập hoạt động như thế nào? - Cedric Mamo
@CedricMamo: có một tham chiếu về github: arxiv.org/abs/1604.05085 - Florian Castellane