Tìm kiếm và AI trò chơi: A* và minimax trong Python

Khái niệm bằng lời đơn giản

AI cổ điển giải bài toán bằng cách tìm kiếm qua các trạng thái có thể. A* tìm đường rẻ nhất bằng cách cộng chi phí đã đi với ước lượng chi phí còn lại, còn minimax chọn nước đi trong trò chơi hai người với giả định đối thủ chơi tốt.

Tìm đường ngắn nhất trên lưới bằng A* và chọn nước đi tốt nhất trong trò chơi bằng minimax.

Ý chính

A* tìm được đường tốt nhất khi ước lượng (heuristic) không bao giờ vượt quá chi phí thật.
Minimax duyệt cây trò chơi tới một độ sâu cố định hoặc tới khi kết thúc ván.
Cắt tỉa alpha-beta bỏ qua những nhánh không thể làm thay đổi quyết định.
Thuật toán di truyền tìm kiếm theo cách khác: nó tiến hóa một quần thể lời giải ứng viên.

Khi nào nên sử dụng?

Hiểu điều gì diễn ra bên trong mạng nơ-ron và các thư viện AI.
Nắm ý tưởng trước khi tự cài đặt nó trong các thử thách tương ứng.
Chuẩn bị cho khóa học machine learning, phỏng vấn và dự án.

Xem trực quan

Nhấn Phát để xem A* khám phá lưới; nhấp vào ô để thêm hoặc bỏ tường. Trong cây trò chơi, nhấp vào một lá để đổi điểm của nó.

Code ví dụ

Chạy code →

main.py

import heapq

# A* finds the cheapest path using cost so far + a guess of the cost left.
grid = ["S..#",
        ".#..",
        "...G"]
start, goal = (0, 0), (2, 3)
guess = lambda r, c: abs(r - goal[0]) + abs(c - goal[1])   # Manhattan distance

frontier = [(guess(*start), 0, start, [start])]
seen = set()
while frontier:
    _, cost, (r, c), path = heapq.heappop(frontier)
    if (r, c) == goal:
        print("path:", path, "cost:", cost)
        break
    if (r, c) in seen:
        continue
    seen.add((r, c))
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 4 and grid[nr][nc] != "#":
            heapq.heappush(frontier, (cost + 1 + guess(nr, nc), cost + 1, (nr, nc), path + [(nr, nc)]))

# Minimax: the maximizer assumes the opponent always picks the worst for it.
def minimax(node, maximizing):
    if isinstance(node, int):
        return node
    values = [minimax(child, not maximizing) for child in node]
    return max(values) if maximizing else min(values)

tree = [[3, 5], [2, 9], [0, 7]]   # our move, then the opponent's reply
print("best guaranteed score:", minimax(tree, True))

Kết quả dự kiến

path: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3)] cost: 5
best guaranteed score: 3

Cách hoạt động

Hàng đợi ưu tiên luôn mở rộng ô có chi phí + ước lượng nhỏ nhất, trong đó ước lượng là khoảng cách Manhattan tới đích, nên A* tới G sau 5 bước vòng qua tường. minimax() lấy giá trị lớn nhất ở lượt của ta và nhỏ nhất ở lượt đối thủ; nước đầu tiên đảm bảo được 3, tốt nhất trong ba trường hợp xấu nhất.

Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.

Bài tập mở rộng

Hãy sửa code theo các bài tập dưới đây để hiểu rõ cách hoạt động thay vì chỉ sao chép kết quả.

Đổi đầu vào hoặc trọng số và đoán kết quả trước khi chạy.
In các giá trị trung gian để theo dõi từng bước tính toán.
Giải các thử thách được liên kết bên dưới để tự cài đặt ý tưởng.

Chạy trong Python IDE →

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách