Tạo AI đơn giản cho game rắn với BFS

Trong bài hướng dẫn trước, trituenhantao.io đã hướng dẫn các bạn lập trình game rắn với pygame. Lần này, ta hãy cùng nhau tạo ra một AI đơn giản với trò chơi này. Trước khi đọc tiếp bài này, xin lưu ý đây là bài viết tương đối nâng cao dành cho các bạn đã có nền tảng lập trình và cấu trúc dữ liệu và giải thuật. Ngoài ra, bạn nên dành thời gian hoàn thành bài Hướng dẫn lập trình game Rắn với thư viện pygame trước khi đọc tiếp. Nó bao gồm những hướng dẫn về cách cấu hình, cài đặt môi trường cũng như những giải thích cơ bản để chúng ta có thể lập trình game rắn với python.

Chiến lược chung

BFS là thuật toán tìm kiếm theo chiều rộng nổi tiếng trong lý thuyết đồ thị. Thuật toán này sẽ duyệt từ nút gốc và loang dần đến các nút có độ sâu tăng dần. Nó là một thuật toán đơn giản giúp chúng ta tìm được đường đi ngắn nhất giữa hai ô trong ma trận. AI của chúng ta sẽ được xây dựng dựa trên thuật toán này.

Với BFS, ta có thể dễ dàng tìm được đường đi ngắn nhất giữa đầu con rắn và thức ăn. Khi mới bắt đầu trò chơi, đó là tất cả những gì ta cần, nhưng khi con rắn ngày một dài ra, nó cần phải có năng lực điều khiển thân của mình để tránh trường hợp “cái thân làm tội cái đầu”. Chúng ta có thể trang bị năng lực này cho con rắn thông qua một nhận xét quan trọng: Miễn là tồn tại đường đi từ đầu rắn đến đuôi rắn, về cơ bản con rắn có thể đi tiếp.

Khởi tạo các mảng lưu trạng thái

Đầu tiên, chúng ta viết hàm khởi tạo các mảng phục vụ cho việc duyệt BFS và tìm đường đi phù hợp cho con rắn. Trong chương trình này, chúng ta sử dụng hai tập hợp mảng đại diện cho đường đi thực sự của rắn và đường đi thử nghiệm của nó.

HEIGHT = 10 # Chiều cao cửa sổ
WIDTH = 15 # Chiều rộng cửa sổ
FIELD_SIZE = HEIGHT * WIDTH # Kích thước ma trận trò chơi
HEAD = 0 # Chỉ số đầu rắn
SNAKE_BLOCK = 20 # Kích thước thân rắn
SNAKE_SPEED = 200 # Tốc độ
ERR = -2333 # Hằng số đại diện cho lỗi

FONT_STYLE = pygame.font.SysFont("bahnschrift", 12)
SCORE_FONT = pygame.font.SysFont("comicsansms", 20)

def initial_game():
    global board, snake, snake_size, tmpboard, tmpsnake, tmpsnake_size, food,best_move
    board = [0] * FIELD_SIZE #[0,0,0,……]
    snake = [0] * (FIELD_SIZE+1)
    snake[HEAD] = 1*WIDTH+1
    snake_size = 1

    tmpboard = [0] * FIELD_SIZE
    tmpsnake = [0] * (FIELD_SIZE+1)
    tmpsnake[HEAD] = 1*WIDTH+1
    tmpsnake_size = 1

    food = 4 * WIDTH + 7
    best_move = ERR

Sau khi khai báo các mảng lưu giá trị, chúng ta cần thiết lập giá trị ban đầu cho chúng. Thức ăn sẽ được gán giá trị nhỏ nhất (0), các ô chưa được duyệt sẽ được gán trạng thái lớn hơn tổng số ô tồn tại trong ma trận (UNDEFINED), và các ô thuộc thân rắn sẽ nhận gia trị bằng 2 lần các ô chưa được duyệt (2*UNDEFINED). Điều này sẽ giúp cho chương trình phân biệt được đâu là ô chứa đường đi (các ô có trạng thái nhỏ hơn UNDEFINED)

FOOD = 0 # Trạng thái của thức ăn
UNDEFINED = (HEIGHT + 1) * (WIDTH + 1) # Trạng thái của các ô chưa được duyệt
SNAKE = 2 * UNDEFINED # Trạng thái của các ô thuộc thân rắn

def board_reset(psnake, psize, pboard):
    for i in range(FIELD_SIZE):
        if i == food:
            pboard[i] = FOOD
        elif is_cell_free(i, psize, psnake): 
            pboard[i] = UNDEFINED
        else:
            pboard[i] = SNAKE

Cài đặt BFS

Ta viết hàm board_BFS để triển khai thuật toán BFS trên ma trận trò chơi và lưu lại trạng thái duyệt của từng ô. Đây là thông tin quan trọng để con rắn có thể chọn được đường đi phù hợp. Ô chứa thức ăn sẽ là nút gốc, trong trường hợp tồn tại đường đi từ nút gốc đến ô ứng với đầu rắn, mỗi ô được gán giá trị là khoảng cách ngắn nhất tới nút gốc.

LEFT = -1 # Trái
RIGHT = 1 # Phải
UP = -WIDTH # Trên
DOWN = WIDTH # Dưới
MOV = [LEFT, RIGHT, UP, DOWN] # Các hướng di chuyển của rắn


def board_BFS(pfood, psnake, pboard):
    queue = []
    queue.append(pfood)
    inqueue = [0] * FIELD_SIZE
    found = False
    while len(queue)!=0: 
        idx = int(queue.pop(0))
        if inqueue[idx] == 1: 
            continue
        inqueue[idx] = 1
        for i in range(4):
            if is_move_possible(idx, MOV[i]):
                if idx + MOV[i] == psnake[HEAD]:
                    found = True
                if pboard[idx+MOV[i]] < SNAKE: 
                    if pboard[idx+MOV[i]] > pboard[idx]+1:
                        pboard[idx+MOV[i]] = pboard[idx] + 1
                    if inqueue[idx+MOV[i]] == 0:
                        queue.append(idx+MOV[i])
    return found

Duyệt đường đi thử nghiệm và kiểm tra đuôi

Ta viết hàm virtual_shortest_move để đưa con rắn tới vị trí thức ăn mà BFS tìm ra. Tại vị trí đó, ta kiểm tra xem có tồn tại đường đi từ đầu con rắn tới đuôi của nó hay không. Đây là hàm quan trọng để thực hiện nhận xét mà ta có được ở đầu bài viết.

def virtual_shortest_move():
    global snake, board, snake_size, tmpsnake, tmpboard, tmpsnake_size, food
    tmpsnake_size = snake_size
    tmpsnake = snake[:] 
    tmpboard = board[:] 
    board_reset(tmpsnake, tmpsnake_size, tmpboard)
    
    food_eated = False
    while not food_eated:
        board_BFS(food, tmpsnake, tmpboard)    
        move = choose_shortest_safe_move(tmpsnake, tmpboard)
        shift_array(tmpsnake, tmpsnake_size)
        tmpsnake[HEAD] += move 
        if tmpsnake[HEAD] == food:
            tmpsnake_size += 1
            board_reset(tmpsnake, tmpsnake_size, tmpboard)
            tmpboard[food] = SNAKE
            food_eated = True
        else:
            tmpboard[tmpsnake[HEAD]] = SNAKE
            tmpboard[tmpsnake[tmpsnake_size]] = UNDEFINED

Và hàm để kiểm tra đuôi:

def is_tail_reachable(): 
    global tmpboard, tmpsnake, food, tmpsnake_size
    tmpboard[tmpsnake[tmpsnake_size-1]] = FOOD 
    tmpboard[food] = SNAKE 
    result = board_BFS(tmpsnake[tmpsnake_size-1], tmpsnake, tmpboard) 
    for i in range(4): 
        if is_move_possible(tmpsnake[HEAD], MOV[i]) and tmpsnake[HEAD]+MOV[i]==tmpsnake[tmpsnake_size-1] and tmpsnake_size>3:
            result = False
    return result

Để con rắn có thể đuổi theo đuôi của nó, ta sử dụng thủ thuật hoàn đổi trạng thái của ô chứa thức ăn với trạng thái của ô chứa đuôi rắn và duyệt BFS. Sau khi hoán đổi, BFS sẽ tìm đường đi ngắn nhất đến vị trí của đuôi mà không duyệt qua ô chứa thức ăn.

def follow_tail():
    global tmpboard, tmpsnake, food, tmpsnake_size
    tmpsnake_size = snake_size
    tmpsnake = snake[:]
    board_reset(tmpsnake, tmpsnake_size, tmpboard) 
    tmpboard[tmpsnake[tmpsnake_size-1]] = FOOD
    tmpboard[food] = SNAKE
    board_BFS(tmpsnake[tmpsnake_size-1], tmpsnake, tmpboard) 
    tmpboard[tmpsnake[tmpsnake_size-1]] = SNAKE 
    return choose_longest_safe_move(tmpsnake, tmpboard) 

Các hàm tìm đường đi ngắn nhất và dài nhất

Dựa trên kết quả của BFS, ta có thể tìm được đường đi ngắn nhất và dài nhất. Khi con rắn đuổi theo thức ăn, nó cần đường đi ngắn nhất, khi nó đuổi theo cái đuôi của chính nó, nó nên chọn đường đi dài nhất (trong số các đường đi ngắn nhất) để có thêm không gian để có thể ở lại game lâu hơn.

 def choose_shortest_safe_move(psnake, pboard):
    best_move = ERR
    min = SNAKE
    for i in range(4):
        if is_move_possible(psnake[HEAD], MOV[i]) and pboard[psnake[HEAD]+MOV[i]]<min:
            min = pboard[psnake[HEAD]+MOV[i]]
            best_move = MOV[i]
    return best_move
    
def choose_longest_safe_move(psnake, pboard):
    best_move = ERR
    max = -1
    for i in range(4):
        if is_move_possible(psnake[HEAD], MOV[i]) and pboard[psnake[HEAD]+MOV[i]]<UNDEFINED and pboard[psnake[HEAD]+MOV[i]]>max:
            max = pboard[psnake[HEAD]+MOV[i]]
            best_move = MOV[i]
    return best_move

Hoàn thiện code

Bước tiếp theo, chúng ta cần hoàn thiện các hàm hiển thị và hỗ trợ để chương trình có thể hoạt động được. Với phiên bản trong bài hướng dẫn trước, ở mỗi vòng lặp của gameLoop chúng ta cho con rắn tiến theo hướng hiện tại và đổi hướng mỗi khi phím được ấn. Trong phiên bản này, tại mỗi vòng lặp, chương trình phải tự tìm ra ô tối ưu để đi tiếp. Ý tưởng chính như sau:

if board_BFS(food, snake, board): # nếu tồn tại đường đi
    best_move  = find_safe_way() # tìm đường đi an toàn tốt nhất
else:
    best_move = follow_tail() # nếu không, thử đuổi theo đuôi
if best_move == ERR: # nếu không thể đuổi theo đuôi
    best_move = any_possible_move() # đi ngẫu nhiên một ô hợp lệ
            
if best_move != ERR: 
    make_move(best_move)
else:
    game_close = True

Dựa trên những ý tưởng của bài hướng dẫn này, bạn có thể tự hoàn thiện code game của chính mình. Ngoài ra bạn có thể tải file hoàn chỉnh snake_bfs.py để đối chiếu và so sánh. Để trang bị thêm kiến thức, chúng tôi xin gợi ý bạn đăng ký nhận tài liệu python miễn phí tại đây.

Nếu bạn thấy bài viết hữu ích, hãy chia sẻ cho mọi người. Chúc các bạn thành công!