PacMan: loại heuristics nào được sử dụng chủ yếu?

Question

Bên cạnh A *, BFS, DFS và các loại tương tự, các thuật toán tìm kiếm đường dẫn khác/heuristics được sử dụng phổ biến trong Pacman là gì? Tôi không nghĩ rằng những người tôi đã đề cập sẽ làm việc nếu có nhiều hơn một loại trái cây cho pacman để tìm.

Tôi cần một số thuật toán tìm đường dẫn tốt mà PacMan có thể sử dụng để hoàn thành mê cung với số bước ít nhất có thể. Tôi đã cố gắng tìm kiếm một hướng dẫn, nhưng cho đến nay không có may mắn. A * với Manhattan khoảng cách được đề cập ở khắp mọi nơi nhưng nó sẽ chỉ làm việc với mê cung chỉ với một (hoặc hai? Hoặc có thể lên đến một vài?) Trái cây để có được.

BTW, để giữ mọi thứ đơn giản, giả sử không có bóng ma xung quanh.

Một số ví dụ từ những vấn đề PacMan gốc: First, Second và Third

Answer 1

Bạn nhận xét bạn đang tìm kiếm Đường đi ngắn nhất. Vấn đề này là một biến thể của TSP trên biểu đồ phẳng, và do đó là NP-Hard.

chẩn đoán có thể chức năng cho A* có thể giải quyết vấn đề nhưng không phải là admissible [do đó con đường tìm thấy không đảm bảo được tối ưu]:

Sum khoảng cách manhattan từ tất cả các loại trái cây để các đại lý.

Bạn cũng có thể sử dụng phương pháp phỏng đoán có thể phát hiện, của #fruits - nhưng sẽ mất nhiều thời gian.

Nếu bạn đang tìm kiếm tối ưu, tốt - thật khó. Bạn có thể thử tất cả hoán vị của các loại trái cây và kiểm tra tổng khoảng cách bạn cần để đi du lịch. Giải pháp này là giai thừa trong số lượng các loại trái cây, và nếu nó lớn hơn thì 20 - với bruteforce ngây thơ - nó sẽ mất quá nhiều thời gian. Bạn bằng cách nào đó có thể làm cho nó tốt hơn bằng cách giảm vấn đề xuống TSP và sử dụng giải pháp lập trình động, cũng là theo cấp số nhân hoặc một số giải pháp cho TSP.

---

Người ta cũng có thể cải thiện các giải pháp dựa trên kinh nghiệm không thể chấp nhận được để cung cấp một any-time algorithm:

lặp đi lặp lại chạy A* với một hàm heuristic, giảm: h(v) = h'(v)/m, nơi h' là chức năng dựa trên kinh nghiệm trên lặp cuối cùng của A *, và m > 1. Điều này đảm bảo rằng tại một số điểm, chức năng heuristic của bạn h sẽ được chấp nhận - và giải pháp tìm thấy sẽ được tối ưu. Tuy nhiên, mỗi lần lặp lại được dự kiến ​​sẽ mất nhiều thời gian hơn sau đó quá trình lặp lại [dài hơn theo cấp số nhân ..]

Answer 2

Bạn có thể brute force nó cho số lượng nhỏ các loại trái cây trong một mê cung có kích thước hợp lý.

• Tạo biểu đồ có nút cho từng mẩu trái cây trong mê cung.
• Sử dụng A * hoặc tương tự để tìm khoảng cách giữa mỗi cặp trái cây. (Bạn sẽ cần O(n^2) lần chạy của A * để nhận được tất cả khoảng cách cặp đôi giữa n quả.)
• Liên kết các nút (quả) trong biểu đồ với các cạnh được tính theo khoảng cách.
• Tìm chu kỳ rẻ nhất trong biểu đồ (truy cập tất cả các nút ít nhất một lần) bằng vũ lực. Xem cheapest cost traveral on complete graph.

Answer 3

Tôi biết điều này là cũ, nhưng có thể có rất nhiều người khác đang tìm cách giải quyết vấn đề này (đó là một phần của Lớp AI miễn phí của Berkeley). Có rất nhiều gợi ý brute force, vì vậy tôi sẽ đóng góp một khá đơn giản mà được khá chặt chẽ và thể được thừa nhận :

1. Tìm quả gần
2. Di chuyển trái cây từ danh sách các loại trái cây còn lại và thêm khoảng cách với tổng
3. Tìm quả gần quả này
4. trở lại bước 2 và lặp lại cho đến khi không có nhiều trái cây
5. trở lại tổng

chỉnh sửa: Xác nhận quyền sở hữu trước đây rằng đây là giả thuyết thừa nhận là sai. Lấy làm tiếc!

Answer 4

Heuristic mà làm việc cho tôi nếu bạn biết giao diện của mê cung:

1. Tìm khoảng cách thực sự giữa hai loại trái cây hiện xa nhất trong mê cung - hãy gọi đó là x.
2. Tìm khoảng cách thực tế từ vị trí Pacman hiện tại đến gần hơn hai quả trước đó - hãy gọi số y.

Sau đó, câu trả lời chỉ là: x + y. Lưu ý rằng khoảng cách thực không phải là khoảng cách Manhattan, nhưng khoảng cách là real trong mê cung - bạn có thể tính toán (thậm chí tính toán trước nếu bạn muốn) vì bạn biết giao diện mê cung (bạn biết tất cả các bức tường, ...). Thông tin này (khoảng cách thực sự giữa hai điểm trong mê cung) là tĩnh bởi vì các bức tường không thay đổi.

Việc giải thích của x + y công thức này có thể là một cái gì đó như thế này:

• x - một trong hai cách, bạn sẽ phải đi khoảng cách này, ít nhất là vào cuối
• y - trong khi bạn đang ở một trong hai loại trái cây xa xôi nhất, tốt hơn là thu thập thức ăn gần với nó để bạn không phải quay lại

Nếu bạn giải quyết điều này như một phần của dự án Berkeley AI class, fo r tính toán khoảng cách thực giữa hai điểm bạn có thể sử dụng hàm mazeDistance(pos1, pos2, gameState) đã được triển khai và đang sử dụng triển khai bfs của bạn.Ngoài ra, heuristic này là có thể chấp nhận và nhất quán, ít nhất là đối với các trường hợp thử nghiệm của chúng. Bằng cách này, với heuristic này tôi quản lý để mở rộng chỉ 376 nút trong trickySearch mê cung.

Answer 5

Tôi tìm thấy thực phẩm gần nhất (sử dụng khoảng cách manhattan) nhưng đối với heuristic của tôi, tôi đã sử dụng khoảng cách thực tế từ vị trí của tôi đến thức ăn gần nhất. Điều này tôi thêm 1 cho tất cả những điểm thực phẩm mà không chia sẻ hàng hoặc cột với vị trí của tôi hoặc điểm thực phẩm gần nhất.

Bởi vì các điểm thực phẩm chia sẻ hàng hoặc col với vị trí của tôi hoặc vị trí thức ăn gần nhất sẽ được ăn trong khi đi từ vị trí của tôi đến thức ăn gần nhất và tôi đã tính chi phí này trong khoảng cách thực tế tôi đã đề cập trong hàng.

Vì vậy, trong ngắn hạn: dựa trên kinh nghiệm = mazeDistance (vị trí của tôi, ước thực phẩm gần nhất) + điểm bỏ

Đây là chấp nhận và nhất quán. Với điều này tôi đã mở rộng 5500 nút và nhận được 5/4 trên FoodHeuristic. https://github.com/sukritiverma1996/Intro-to-AI-course

Answer 6

nếu bạn muốn giảm số lượng nút được mở rộng và không quan tâm đến thời gian chạy, tôi khuyên bạn nên sử dụng cây tối thiểu Spanning Tree, chi phí cạnh phải là mazeDistance và sử dụng priorityQueue, mỗi khi thêm nút vào nút truy cập, tìm nút gần nhất để chỉ thêm nút và sau đó thêm nút đó vào nút đã truy cập, cho đến khi tất cả nút thực phẩm đã được thêm vào nút đã truy cập. Nếu bạn đang làm với vấn đề khóa học AI, nút mở rộng nên rất thấp.

Answer 7

trong trạng thái trò chơi nào đó, nói md(x) là manhattan khoảng cách từ pacman đến nút x, hãy xem xét minmd(X) như một chức năng mà trở xmin s.t md(xmin)<=md(x) cho tất cả x trong X. hãy để X là bộ thực phẩm pacman đã để lại để ăn. Nghĩ về nó - nếu bạn nghĩ đến việc thư giãn thế giới pacman của bạn mà không có tường, pacman cant đi dưới md(xmin) nơi xmin=minmd(X) để ăn một ít trái cây, và nếu muốn ăn trái cây khác, anh ta phải đi không ít hơn md(xmin1) trong đó xmin1=minmd(X-{xmin}) v.v. trả lại tổng số mds pacman đi từ xmin đến xmin1 đến xmin2 và cứ như thế và vì đây là giải pháp tối ưu cho việc thư giãn, bạn có thể nhận được được chấp nhận và cosistent chức năng heuristic! Một điểm khác cần xem xét, là bạn thậm chí có thể có được một heuristic tốt hơn nếu bạn xem xét các bức tường, đây là vấn đề khó khăn hơn vì vậy tôi đã không nhận được vào nó nhiều, nhưng tôi nhận thấy rằng nếu bạn ràng buộc pacman trong một hình chữ nhật với các trái cây tối ưu tiếp theo, anh ta sẽ phải trả thêm ít nhất 2 hành động nếu có một số đường thẳng đứng hoặc nằm ngang giữa chúng bởi vì anh ta sẽ phải thoát khỏi hình chữ nhật bao quanh và nhập lại nó trả ít nhất 2 hành động trong khi làm như vậy cho mỗi bức tường đó. Điều này có thể được kiểm tra thêm và bạn cũng có thể tìm thấy nhiều tính năng đặc biệt hơn trong hình chữ nhật này.

Answer 8

Giả sử điều này là dành cho dự án Berkeley AI:

Trong trường hợp chung, việc tìm đường đi ngắn nhất đến từng điểm là NP-hard. Tuy nhiên, điều đó không có nghĩa là khó thực hành. Lý do là vì có fixed parameter tractable algorithms và mê cung Pacman được cung cấp thuộc trường hợp đồ thị dễ giải quyết.

Cụ thể, đối với bất kỳ chiều rộng nhánh nào, đường đi ngắn nhất có thể được tìm thấy trong đa thức thời gian theo kích thước của biểu đồ (nhưng theo cấp số nhân trong chiều rộng chi tiết của đồ thị) bằng một ứng dụng lập trình động đơn giản. Điều này không vi phạm NP-độ cứng vì đồ thị tùy ý có thể có chiều rộng nhánh lớn, nhưng điều đó có nghĩa là vấn đề có thể được giải quyết hiệu quả nếu bạn chỉ quan tâm đến đồ thị có chiều rộng nhánh thấp. Các mê cung Pacman cung cấp có kết nối kém, và do đó một chiều rộng chi nhánh thấp.

Để biết thêm chi tiết, see this post.