Bài tập 2: Tìm kiếm đối kháng

1. Giới thiệu¶

Bài tập 2 Đấu trường Trốn Tìm được thiết kế nhằm giúp sinh viên hiểu rõ, cài đặt và tối ưu hóa các thuật toán tìm kiếm và tìm kiếm đối kháng, được gọi là adversarial search, thông qua một môi trường tự động mô phỏng trò chơi trốn tìm. Tại đây, các sinh viên sẽ tranh tài trực tiếp để giành thứ hạng cao nhất.

Mỗi sinh viên sẽ phát triển hai loại tác nhân sau:

Tác nhân Trốn, được gọi là Ghost: nhiệm vụ là lẩn trốn càng lâu càng tốt.
Tác nhân Tìm, được gọi là Pacman: nhiệm vụ là tìm kiếm và bắt đối phương nhanh nhất có thể.

Các tác nhân sẽ được ghép cặp tự động trong Đấu trường để tính toán tỷ lệ thắng và xếp hạng chung cuộc.

2. Đấu trường¶

Đấu trường là một hệ thống tự động được viết bằng ngôn ngữ Python, đóng vai trò là môi trường thi đấu cho các tác nhân. Dựa trên bài nộp của sinh viên, hệ thống sẽ thực hiện ba chức năng chính: tự động nạp mã nguồn tác nhân của từng sinh viên, vận hành loạt trận đấu giữa các sinh viên và xuất kết quả cuối cùng.

Quá trình tương tác được mô tả chi tiết trong Thuật toán 1.

Algorithm 1  Vòng lặp tương tác giữa Agent và Môi trường
1: while tập (episode) chưa kết thúc do
2:     ap ← PacmanAgent.step()
3:     ag ← GhostAgent.step()
4:     Environment.step(ap, ag)
5:     Cập nhật vị trí các agent
6:     Kiểm tra va chạm hoặc điều kiện kết thúc
7:     Quan sát trạng thái mới của môi trường
8: end while

# # # # # # # # # # # # # # # # # # # # #
# . . . . . . . . . # . . . . . . . . . #
# . # # # . # # # . # . # # # . # # # . #
# . # # # . # # # . # . # # # . # # # . #
# . . . . . . . . . . . . . . . . . . . #
# . # # # . # . # # # # # . # . # # # . #
# . . . . . # . . . # . . . # . . . . . #
# # # # # . # # # . # . # # # . # # # # #
# # # # # . # . . . G . . . # . # # # # #
# # # # # . # . # # . # # . # . # # # # #
# . . . . . . . # . . . # . . . . . . . #
# # # # # . # . # # # # # . # . # # # # #
# # # # # . # . . . . . . . # . # # # # #
# # # # # . # . # # # # # . # . # # # # #
# . . . . . . . . . # . . . . . . . . . #
# . # # # . # # # . # . # # # . # # # . #
# . . . # . . . . . P . . . . . # . . . #
# # # . # . # . # # # # # . # . # . # # #
# . . . . . # . . . # . . . # . . . . . #
# . # # # # # # # . # . # # # # # # # . #
# . . . . . . . . . . . . . . . . . . . #
# # # # # # # # # # # # # # # # # # # # #

Hình 1: Minh họa bản đồ Đấu trường (P: Pacman, G: Ghost, #: Tường, .: Đường đi)

Tại mỗi bước trong Thuật toán 1, thông tin được cung cấp bao gồm bản đồ kích thước 21 × 21, trong đó giá trị 0 là ô đi được và 1 là vật cản, cùng vị trí hiện tại của hai agent và số bước đi hiện tại.

Lưu ý rằng có sự khác biệt về tốc độ di chuyển giữa hai loại tác nhân:

Pacman có thể di chuyển thẳng tối đa 2 ô trong một bước nhưng tốc độ này chỉ áp dụng cho các nước đi thẳng hoàn toàn, còn nếu tác nhân thực hiện rẽ hướng thì chỉ được di chuyển 1 ô tại mỗi bước, tức là phải tách thành 2 bước tại 2 điểm thời gian liên tiếp nhau.
Ghost: Chỉ được di chuyển 1 ô mỗi bước.

Cả hai agent đều nhận được thông tin trạng thái giống nhau và đưa ra quyết định đồng thời. Điều kiện thắng cuộc được quy định như sau:

Pacman thắng nếu khoảng cách Manhattan giữa Pacman và Ghost xuống dưới 2, tức là Pacman và Ghost hoặc gặp nhau tại cùng một ô hoặc đứng cạnh nhau.
Ghost thắng nếu đạt đến giới hạn số bước đi tối đa, thường là 200, mà chưa bị Pacman bắt.

Dựa trên kết quả trận đấu, tỷ lệ thắng được tính theo công thức:

\text{Ty le thang}_{\text{Pacman}} = \frac{\text{So tran Pacman thang}}{\text{Tong so tran Pacman}} \qquad \text{Ty le thang}_{\text{Ghost}} = \frac{\text{So tran Ghost thang}}{\text{Tong so tran Ghost}}

(1)

Mã nguồn sẽ được cung cấp dưới dạng pacman.zip trong thư mục Google Drive, với cấu trúc thư mục như sau, sinh viên vui lòng ĐỌC KỸ mã nguồn mẫu và mã của đấu trường để cài đặt thích hợp:

Arena/
├── src/                          # Mã nguồn Framework (KHÔNG chỉnh sửa)
│   ├── environment.py            # Môi trường game
│   ├── agent_interface.py        # Interface cơ sở cho các agent
│   ├── arena.py                  # Bộ điều phối chính
│   └── visualizer.py             # Bộ hiển thị trên terminal
└── submissions/                  # Không gian làm việc của sinh viên
    ├── example_student/          # Tham khảo mẫu
    │   └── agent.py
    ├── <student_id>/             # Mã số sinh viên (ví dụ: 23456789)
    │   ├── agent.py              # File cài đặt của sinh viên
    │   └── STUDENT_GUIDE.md      # Hướng dẫn chi tiết
    └── run_game.sh               # Script chạy nhanh

Mã nguồn có tính năng sương mù để che lại thông tin bản đồ khi vượt ra một khoảng cách nhất định, tuy nhiên chúng ta sẽ KHÔNG dùng tính năng đó trong bài tập này. Tại mỗi bước, agent của sinh viên phải trả về một hành động theo định dạng sau:

class PacmanAgent(BasePacmanAgent):
    def step(self, map_state, my_pos, enemy_pos, step_number):
        """
        Input:
            map_state: numpy array 2D (0: ô trống, 1: tường)
            my_pos: (row, col) vị trí của bản thân
            enemy_pos: (row, col) vị trí của đối thủ (hoặc None)
            step_number: số thứ tự bước đi hiện tại
        Output:
            Move enum: Di chuyển 1 bước (vd: Move.UP)
            Tuple (Move, int): Di chuyển nhiều bước (vd: (Move.UP, 2))
        """
        # Cài đặt thuật toán tìm kiếm tại đây
        return Move.UP  # hoặc (Move.UP, 2)


class GhostAgent(BaseGhostAgent):
    def step(self, map_state, my_pos, enemy_pos, step_number):
        # Ghost chỉ được trả về Move (chỉ di chuyển 1 bước)
        return Move.UP

Các thuật toán tìm kiếm đối kháng được khuyến nghị gồm: Minimax, Monte Carlo, Alpha-beta Pruning, Expectiminimax.

3. Giải đấu¶

Mỗi sinh viên sẽ tham gia cả hai vai trò là Pacman và Ghost, thi đấu vòng tròn với tất cả các sinh viên còn lại. Kết quả được ghi nhận theo bảng ví dụ Bảng 1 dưới đây.

Pacman \ Ghost	SV 1	SV 2	SV 3	SV 4	...
SV 1	–	0	1	0	...
SV 2	1	–	0	0	...
SV 3	0	1	–	1	...
SV 4	1	1	0	–	...

Trong đó, giá trị 0 biểu thị Pacman thắng, giá trị 1 biểu thị Ghost thắng.

Dựa trên Bảng 1, ví dụ cách tính tỷ lệ thắng cho Sinh viên 1 như sau:

Trong vai trò Pacman, Sinh viên 1 thắng 1 trên 3 trận nên tỷ lệ thắng $\text{Ty le thang}_{\text{Pacman}} = 33.3\%$ .
Trong vai trò Ghost, Sinh viên 1 thắng 2 trên 3 trận nên tỷ lệ thắng $\text{Ty le thang}_{\text{Ghost}} = 66.6\%$ .

Xếp hạng của sinh viên sẽ ưu tiên dựa trên tỷ lệ thắng. Nếu các sinh viên có cùng tỷ lệ thắng, hệ thống sẽ sử dụng chỉ số phụ là số bước trung bình trong mỗi ván đấu để phân định thứ hạng.

Tiêu chí chấm điểm cho từng sinh viên được quy định như sau:

Tiêu chí	Điểm số
Mức độ hoàn thiện thuật toán, chạy được mà không bị lỗi hoặc quá thời gian/bộ nhớ	3
Thứ hạng trong đợt nộp bài sơ bộ	Tối đa 3
Thứ hạng trong đợt nộp bài cuối cùng	Tối đa 4

4. Nộp bài¶

Mỗi sinh viên nộp một tập tin nén duy nhất lên Moodle: một thư mục được đặt tên là mã số sinh viên ví dụ 23456789, chứa tập tin agent.py cùng các tập tin Python phụ trợ khác, nén thành <MSSV>.zip, ví dụ 23456789.zip. Tác nhân nộp lên được phép sử dụng các tập tin khác nằm trong cùng thư mục nộp bài.

Lưu ý: Bài nộp trễ sẽ không được chấp nhận dưới mọi hình thức.

Lịch trình nộp bài được quy định cụ thể như sau:

Thời gian	Hoạt động
Đầu tuần 1	Công bố bài tập
Đầu tuần 2	Nộp bài sơ bộ
Đầu tuần 3	Công bố bảng xếp hạng sơ bộ
Đầu tuần 4	Nộp bài cuối cùng
Cuối kỳ	Công bố điểm số cuối cùng

Lưu ý quan trọng về mã nguồn: mã nguồn của đợt nộp bài sơ bộ sẽ được công bố công khai cho các sinh viên khác trong lớp tham khảo. Do đó, sinh viên cần chủ động cải tiến và nâng cấp thuật toán của mình cho đợt nộp bài cuối cùng để đảm bảo tính cạnh tranh.

5. Các lưu ý khác¶

Sinh viên cần đặc biệt chú ý các vấn đề sau:

Đây là bài tập CÁ NHÂN. Mỗi sinh viên tự hoàn thành bài tập độc lập.
Bài tập có hai đợt nộp bài. Chỉ những sinh viên đã nộp bài trong đợt sơ bộ mới được phép nộp tiếp đợt cuối cùng.
Sinh viên phải đảm bảo tác nhân trả về hành động trong vòng tối đa 1 giây, bộ nhớ tối đa của tác nhân cho phép là 128 MB.
Phần cứng dùng để chạy là một Google Colab CPU instance, cấu hình cố định nhằm đảm bảo môi trường ổn định và tái lập kết quả tốt nhất. Các thư viện được phép đã được cài sẵn trên môi trường này, sinh viên không cần nộp kèm requirements.txt.
Ngoài các thư viện mặc định của Python, sinh viên được phép sử dụng thêm các thư viện sau: numpy, pandas, scikit-learn, scipy, gurobi. Ngoài danh sách trên, sinh viên không được sử dụng các thư viện ngoài khác.
Các công cụ AI không bị cấm, tuy nhiên sinh viên cần sử dụng một cách có trách nhiệm. Phụ trách thảo luận có quyền phỏng vấn vấn đáp để kiểm tra mức độ hiểu bài của sinh viên.
Mọi hành vi sao chép, gian lận sẽ dẫn đến điểm 0 cho toàn bộ môn học.

Hết.