Bài học và trò chơi học tập

AI trong game: minimax và xa hơn

Teach a Raspberry Pi to play: perfect tic-tac-toe with minimax, then a Connect Four opponent built on alpha-beta, evaluation, a clock and random games.

Khóa học

AI trong game: minimax và xa hơn là một khóa Coding chuyên sâu gồm bảy bài học, tất cả bằng Python trên Raspberry Pi 4. Bàn cờ được vẽ dạng văn bản trên Serial Monitor và nước đi được gõ vào, mỗi bước đều được kiểm tra với những gì Pi in ra hoặc đèn nào sáng lên.

  1. Cây trò chơi: caro (tic-tac-toe) là một danh sách 9 ô, kiểm tra người thắng từ một bảng các đường thẳng, và đệ quy đếm mọi ván đấu từ một thế cờ (3.468 ván tính từ nước thứ hai).
  2. Minimax: chấm điểm một thế cờ với giả định cả hai người chơi đều hoàn hảo, chọn nước đi tốt nhất, ưu tiên thắng nhanh, và giải toàn bộ trò chơi với một memo chứa cả 5.478 thế cờ. Sau đó chơi với nó, và tốt nhất là hòa.
  3. Alpha-beta: đếm khối lượng tính toán, rồi cắt tỉa nó. Từ nước thứ hai, 7.332 thế cờ còn 871, rồi 768 khi sắp xếp ô trung tâm trước, và toàn bộ trò chơi giải xong trong 7.865 mà không cần memo.
  4. Evaluation: Connect Four, a four-in-a-row check from the last move, and a score built from the 69 windows of four. A one-move player trusts it and misses a block, which is the case for searching deeper.
  5. Độ sâu và thời gian: alpha-beta dạng negamax với giới hạn độ sâu, bảng số nút và mili giây theo từng độ sâu, tăng dần độ sâu trong một ngân sách thời gian, và một lần tìm kiếm 3 nước tìm ra nước thắng bắt buộc.
  6. Tìm kiếm Monte Carlo: các ván chơi ngẫu nhiên, chọn nước bằng Monte Carlo phẳng, nhiễu so với số lần lấy mẫu, và UCB1, quy tắc nằm trong tìm kiếm cây Monte Carlo.
  7. Boss: an unbeatable Connect Four.

Hồi kết

The boss lesson is a Connect Four game against the Pi on the Serial Monitor. You are X and type a column; the Pi answers with an alpha-beta search, first at a fixed depth of 4 and then with iterative deepening on a time budget, printing how deep it looked. The gallery's traffic light module shows the game: green for your move, amber while the Pi thinks, red when it wins.

Connect Four is solved: the first player wins with perfect play. The course says so, and explains what a truly perfect engine would add (a transposition table, better ordering, a sharper evaluation and an opening book). For nearly everyone who sits down to play, the Pi is unbeatable.

Trên Pi

Dòng mô tả trong danh mục khóa học này nói đến một ESP32 với màn hình cảm ứng. Nó chạy trên Pi thay vào đó, nên các engine là Python thuần bạn có thể đọc và sửa, với bàn cờ dạng văn bản.

Pi chạy MicroPython 1.29, không phải CPython, và điều đó thể hiện ở đây:

  • time.monotonic() theo đồng hồ mô phỏng, vốn tính mỗi vòng lặp Python một chi phí nhỏ như nhau. Thời gian tìm kiếm và độ sâu mà đồng hồ cho phép vì thế giống nhau ở mỗi lần chạy và trên mọi máy tính.
  • random là bộ sinh riêng của MicroPython. Với random.seed(2026) các ván chơi ngẫu nhiên lặp lại chính xác, nhưng các số khác với của CPython.
  • Dict không giữ thứ tự khóa, nên kết quả được in ra từng dòng thay vì in cả dict.
  • Tìm kiếm chậm hơn trên máy tính để bàn, nên các bài học giữ mỗi lần tìm kiếm trong vài nghìn thế cờ. Bạn hãy tự tăng độ sâu hoặc ngân sách để thấy nó lớn dần.