Adversarial Search: Minimax, Alpha-Beta và giới hạn độ sâu

Trong mê cung, bức tường không nhìn thấy bạn rồi tự dịch chuyển để chặn đường. DFS, BFS hay A* chỉ cần hỏi: từ đây đi đâu thì tới đích.

Game hai người khác hẳn. Đối thủ cũng đang chọn nước, và đối thủ chọn nước làm kết quả của bạn xấu đi.

Đó là Adversarial Search: tìm kiếm khi có một phía chủ động đối kháng.

Ví dụ kinh điển trong CS50 AI là Tic-Tac-Toe. Trước khi tới bàn cờ 3×3, ta chơi một game nhỏ hơn để nhìn hết cây nước đi.

Ý tưởng trước: nước “trông ngon” có thể là bẫy

Giả sử hai người lần lượt lấy xu. Luật:

• Bàn có 4 đồng;
• Mỗi lượt được lấy 1 hoặc 2 đồng;
• Ai lấy đồng cuối cùng thì thắng.

Bạn đi trước. Lấy 2 đồng nghe có vẻ mạnh: còn 2, đối thủ chưa chắc thắng ngay. Nhưng đối thủ cũng được lấy 2. Đối thủ sẽ lấy hết 2 đồng còn lại và thắng.

Nước đi đúng, nếu đối thủ không sai, là lấy 1. Để lại 3 đồng. Từ 3 đồng, đối thủ dù lấy 1 hay 2 thì bạn cũng lấy hết phần còn lại và thắng.

Lấy 2  -> còn 2  -> đối thủ lấy 2  -> bạn thua
Lấy 1  -> còn 3  -> đối thủ buộc để lại 1 hoặc 2  -> bạn lấy hết  -> bạn thắng

Bài học:

Không chọn nước theo cảm giác ngay sau một lượt. Phải hỏi: đối thủ thông minh sẽ đáp lại thế nào, rồi kết cục cuối cùng là gì?

Đó là tinh thần của Minimax.

Game nhỏ: tính hết cây bằng tay

Gọi người đi trước là MAX (bạn), người đi sau là MIN (đối thủ). Điểm quy ước:

MAX thắng -> +1
MIN thắng -> -1

Cây nước đi từ 4 đồng:

Tính từ lá cây ngược lên. Ở mỗi node, người đang tới lượt chọn số có lợi cho họ.

MAX chọn lấy 1. Giá trị của thế cờ đầu là +1: với 4 đồng, người đi trước thắng nếu cả hai chơi tối ưu.

Chỗ “tối ưu” rất cụ thể: MIN luôn chọn nhánh có số nhỏ hơn; MAX luôn chọn nhánh có số lớn hơn. Ta không đoán tâm lý đối thủ. Ta giả định đối thủ cũng chơi đúng theo luật điểm này.

Mô hình game thành một Search Problem

Game xu chỉ có một con số (số đồng còn lại). Tic-Tac-Toe cần mô tả cả bàn cờ. CS50 AI dùng cùng một bộ thành phần như search thường, nhưng thay path cost bằng điểm kết thúc.

State

State là mô tả đủ để biết lượt này được đi những nước nào.

Với game xu, state có thể là số đồng còn lại:

state = 4

Với Tic-Tac-Toe, state phải là cả bàn. Một cách ghi đơn giản: list 9 ô, từ trái sang phải, trên xuống dưới. Dấu "." là ô trống.

# chỉ số:
# 0 1 2
# 3 4 5
# 6 7 8
board = [".", ".", ".", ".", ".", ".", ".", ".", "."]

board[0] là ô góc trên bên trái. board[4] là ô giữa.

Initial State

Bàn xu bắt đầu với 4 đồng. Bàn Tic-Tac-Toe bắt đầu trống, như list trên.

Player(s)

Cho biết lượt hiện tại là ai. Trong Tic-Tac-Toe, X đi trước. Khi số quân X bằng số quân O thì tới lượt X; khi X nhiều hơn O đúng một quân thì tới lượt O.

def player(board):
    # .count("X") = số lần ký tự "X" xuất hiện trong list
    x_count = board.count("X")
    o_count = board.count("O")

    if x_count == o_count:
        return "X"

    return "O"

Actions(s)

Tập nước đi hợp lệ.

Game xu:

def actions(coins):
    options = []

    if coins >= 1:
        options.append(1)
    if coins >= 2:
        options.append(2)

    return options

append thêm một phần tử vào cuối list, giống stack ở bài DFS.

Tic-Tac-Toe: mọi ô đang là ".".

def actions(board):
    options = []

    for index in range(9):
        if board[index] == ".":
            options.append(index)

    return options

range(9) sinh các số 0, 1, ..., 8. Vòng for lần lượt lấy từng chỉ số ô.

Result(s, a)

Trả về state mới sau nước a. Không sửa state cũ tại chỗ; tạo bản sao rồi đổi.

def result(board, index):
    # list(board) tạo một list mới, cùng nội dung
    new_board = list(board)
    new_board[index] = player(board)
    return new_board

Nếu sửa board trực tiếp, các nhánh search sẽ làm bẩn lẫn nhau: một nước thử sẽ còn nằm trên bàn khi ta thử nước khác.

Terminal(s)

Game đã kết thúc chưa? Tic-Tac-Toe kết thúc khi X thắng, O thắng, hoặc hết ô (hòa).

Game xu kết thúc khi không còn đồng nào. Người vừa lấy đồng cuối đã thắng; người đáng lẽ phải đi lúc coins == 0 không còn nước.

Utility(s)

Gán một con số cho terminal state. Quy ước phổ biến khi X là MAX:

Không cần sợ công thức. Nó chỉ là bảng điểm:

X thắng -> +1
Hòa     ->  0
O thắng -> -1

Ta gọi:

• MAX: muốn giá trị càng lớn càng tốt;
• MIN: muốn giá trị càng nhỏ càng tốt.

Trong Tic-Tac-Toe, X là MAX, O là MIN. Trong game xu, người đi trước là MAX.

Utility là điểm thật khi ván đã xong. Nó không phải ước lượng giữa ván. Ước lượng giữa ván sẽ xuất hiện ở evaluation function phía dưới.

Game Tree với số bất kỳ: nhìn rõ min rồi max

Game xu chỉ có +1 và -1, dễ theo dõi luật nhưng hơi khó thấy “chọn số lớn / số nhỏ”. Để nhìn nguyên lý, dùng một cây điểm giả. Đây là ví dụ minh họa, không phải điểm Tic-Tac-Toe.

MAX được chọn một trong ba hộp A, B, C. MIN sẽ chọn một phiếu điểm bên trong hộp đó.

Hộp A: 4 hoặc 6
Hộp B: 3 hoặc 9
Hộp C: 5 hoặc 1

Nếu MAX chỉ nhìn số lớn nhất trong mỗi hộp, hộp B có 9 trông hấp dẫn nhất. MIN không để MAX ăn 9. MIN sẽ chọn phiếu nhỏ hơn trong hộp B, tức 3.

Tính từ dưới lên, giống bảng xu:

A -> min(4, 6) = 4
B -> min(3, 9) = 3
C -> min(5, 1) = 1

MAX biết MIN sẽ làm vậy, nên MAX chọn hộp có số còn lại lớn nhất:

MAX chọn A. Được đảm bảo 4 nếu MIN chơi tối ưu. Hộp B với 9 chỉ là cái bẫy.

Vì sao gọi là Minimax?

MAX muốn maximize kết quả.

Nhưng khi đánh giá một nước của mình, MAX giả định MIN sẽ minimize kết quả đó.

Nói bằng tình huống hộp:

MAX chọn hộp sao cho, sau khi MIN đã lấy phiếu nhỏ nhất trong hộp, số còn lại vẫn lớn nhất có thể.

Minimax là recursion: hỏi tầng dưới rồi trả lời tầng trên

Cách tính tay là đi từ lá lên. Code làm ngược chiều nhìn: bắt đầu từ state hiện tại, hỏi từng state con, con lại hỏi cháu, đến terminal thì có điểm, điểm được trả ngược lên.

Ở node MAX:

1. thử mỗi action;
2. sau action đó tới lượt MIN;
3. hỏi MIN, với các nước của MIN, giá trị thấp nhất MIN có thể ép là bao nhiêu;
4. MAX chọn action cho giá trị lớn nhất trong các câu trả lời đó.

Ở node MIN thì ngược lại: gọi MAX cho từng con, rồi lấy số nhỏ nhất.

MAX-VALUE

Đọc ký hiệu:

• $V_{max}(s)$: giá trị của state s khi tới lượt MAX;
• $\max_{a\in Actions(s)}$: xét mọi nước hợp lệ, giữ nước cho số lớn nhất;
• $Result(s,a)$: bàn cờ sau nước a;
• $V_{min}(\ldots)$: state đó được chấm theo cách MIN sẽ chơi.

Bằng lời, trong tình huống đang xét:

Điểm của một thế cờ khi tới lượt MAX = điểm tốt nhất MAX ép được, sau khi đã tính nước đáp trả bất lợi nhất của MIN.

MIN-VALUE

Với cây hộp, $V_{min}(A)=\min(4,6)=4$, rồi $V_{max}$ ở nút gốc bằng $\max(4,3,1)=4$. Công thức chỉ viết lại đúng phép tính tay.

Khi s là terminal, không còn action. Giá trị là utility(s). Đó là điểm dừng của recursion.

Pseudocode

Hai hàm gọi lẫn nhau. Trong pseudocode chưa cần cú pháp Python. Chỉ cần một mốc nhỏ hơn mọi điểm thật và một mốc lớn hơn mọi điểm thật.

MAX-VALUE(state):
    nếu state là terminal:
        return utility(state)

    value = -infinity

    với mỗi action hợp lệ:
        child = result(state, action)
        value = max(value, MIN-VALUE(child))

    return value

MIN-VALUE(state):
    nếu state là terminal:
        return utility(state)

    value = +infinity

    với mỗi action hợp lệ:
        child = result(state, action)
        value = min(value, MAX-VALUE(child))

    return value

-infinity dùng để lần max đầu tiên luôn thắng: mọi điểm thật đều lớn hơn mốc này. +infinity làm ngược lại cho min.

Code Python: game xu chạy được

Đoạn này đủ để in ra nước đi của MAX từ 4 đồng. Đọc từng dòng; chưa cần thuộc cú pháp.

def actions(coins):
    options = []
    if coins >= 1:
        options.append(1)
    if coins >= 2:
        options.append(2)
    return options


def result(coins, take):
    return coins - take


def terminal(coins):
    # không còn đồng: người vừa lấy đồng cuối đã thắng
    return coins == 0

Hai hàm điểm. Chúng gọi lẫn nhau. Đó là recursion: hàm giải state hiện tại bằng cách gọi hàm cho state nhỏ hơn (ít đồng hơn).

def max_value(coins):
    if terminal(coins):
        # tới lượt MAX nhưng hết đồng: MAX không lấy được đồng cuối
        return -1

    value = float("-inf")  # mốc nhỏ hơn mọi điểm thật

    for take in actions(coins):
        child = result(coins, take)
        score = min_value(child)
        value = max(value, score)

    return value


def min_value(coins):
    if terminal(coins):
        return 1

    value = float("inf")  # mốc lớn hơn mọi điểm thật

    for take in actions(coins):
        child = result(coins, take)
        score = max_value(child)
        value = min(value, score)

    return value

Vì sao max_value trả -1 khi coins == 0? Vì hàm này chỉ chạy khi tới lượt MAX. Hết đồng lúc đó nghĩa là MIN vừa lấy đồng cuối. Ngược lại, khi MAX vừa lấy hết, code gọi min_value(0) và hàm đó trả +1.

Vài điểm Python:

• def khai báo hàm; tên hàm rồi (tham số).
• float("-inf") và float("inf") là âm vô cực và dương vô cực. Dùng làm mốc khởi tạo, không phải điểm game.
• for take in actions(coins): lần lượt gán take bằng từng phần tử của list [1], [2], hoặc [1, 2].
• max(a, b) trả về số lớn hơn; min(a, b) trả về số nhỏ hơn.
• return đưa kết quả ra cho chỗ đã gọi hàm.

Chọn nước, không chỉ chấm điểm:

def best_action_for_max(coins):
    best_take = None
    best_score = float("-inf")

    for take in actions(coins):
        score = min_value(result(coins, take))

        if score > best_score:
            best_score = score
            best_take = take

    return best_take

None nghĩa là “chưa chọn gì”. Sau vòng lặp, best_take là nước 1 hoặc 2.

Thử:

print(best_action_for_max(4))  # 1
print(max_value(4))            # 1  tức +1, MAX thắng

Recursion chạy như thế nào?

Gọi max_value(4) không tính hết trong một bước. Nó đợi min_value(3) và min_value(2). Mỗi hàm đó lại đợi max_value sâu hơn, đến khi coins == 0.

Bảng call gần với code:

Cùng một cặp hàm dùng được cho Tic-Tac-Toe. Chỉ cần đổi actions, result, terminal, utility. Phần min/max không đổi.

Phiên bản tổng quát, đúng skeleton CS50:

def max_value(state):
    if terminal(state):
        return utility(state)

    value = float("-inf")

    for action in actions(state):
        child = result(state, action)
        value = max(value, min_value(child))

    return value


def min_value(state):
    if terminal(state):
        return utility(state)

    value = float("inf")

    for action in actions(state):
        child = result(state, action)
        value = min(value, max_value(child))

    return value

Minimax giả định điều gì?

Minimax chuẩn giả định:

• game có hai phía đối kháng, không đồng minh;
• hai bên thấy cùng một state (thông tin đầy đủ);
• cả hai chơi tối ưu theo đúng utility đã định nghĩa;
• ta mô hình hóa được actions, result, terminal.

Nếu đối thủ chơi ngẫu nhiên, chơi rất kém, hoặc không nhìn thấy bàn cờ, kết luận Minimax không còn là dự báo hành vi thật. Nó vẫn là lựa chọn an toàn theo nghĩa: nước đi không thua nếu đối thủ đột nhiên chơi đúng.

Đó là giới hạn của mô hình, không phải lỗi triển khai.

Vấn đề: game tree quá lớn

Tic-Tac-Toe còn nhỏ, máy tính duyệt được. Chess thì không.

Nếu mỗi state có khoảng b nước, và ta nhìn trước d lượt, số lá cây cỡ $b^{d}$. Không cần nhớ ký hiệu. Chỉ cần thấy tốc độ nhân:

10 lựa chọn mỗi lượt
Depth 1 -> 10
Depth 2 -> 100
Depth 3 -> 1,000
Depth 6 -> 1,000,000

Minimax thuần túy duyệt gần như cả cây. Với game lớn, hết thời gian trước khi tới terminal.

Hai ý trong CS50 AI:

1. Alpha-Beta Pruning — bỏ nhánh đã biết là không đổi quyết định;
2. Depth-Limited Minimax — chỉ nhìn trước một số lượt, rồi dùng evaluation function.

Cần nắm cả hai ý. Phần sâu hơn: thứ tự xét nước quyết định số nhánh cắt được; evaluation function quyết định chất lượng khi không search hết.

Alpha-Beta Pruning: không tính thứ không đổi được quyết định

Quay lại cây hộp. MAX đã xem hộp A và biết được 4.

Tới hộp B. MIN lật phiếu đầu: 3.

MIN luôn chọn phiếu nhỏ nhất, nên điểm cuối của hộp B không thể lớn hơn 3. Dù phiếu còn lại là 9 hay 100, MIN sẽ không đưa số đó cho MAX nếu đã có 3. Nếu phiếu còn lại là -50, hộp B càng tệ cho MAX.

MAX đã có hộp A = 4. Hộp B ≤ 3. MAX sẽ không chọn B. Không cần lật phiếu 9.

Cắt nhánh như vậy gọi là prune.

Tính tay có cắt

Xét trái sang phải, MAX rồi MIN.

Kết quả giống Minimax đủ. Máy đã bỏ một lá.

Alpha và Beta là gì?

Hai mốc trên đường đang đi:

• alpha: kết quả tốt nhất (lớn nhất) mà MAX đã đảm bảo được;
• beta: kết quả tốt nhất với MIN, tức số nhỏ nhất MIN đã đảm bảo được.

Đầu root: MAX chưa đảm bảo gì, MIN chưa đảm bảo gì:

alpha = -infinity
beta  = +infinity

Sau khi A trả về 4, MAX cập nhật alpha = 4. Khi MIN ở B thấy 3, MIN cập nhật beta = 3.

Khi:

alpha >= beta

cửa sổ còn lại đóng. Phía trên đã có lựa chọn không kém hơn mọi thứ nhánh này còn có thể đưa ra. Phần còn lại của nhánh có thể prune.

Đọc hai lớp:

1. Kỹ thuật: cắt khi cận dưới của MAX đã không nhỏ hơn cận trên của MIN.
2. Tình huống hộp: MAX đã có 4, nhánh này không thể vượt 3, hết việc phải tính.

Pseudocode

MAX(state, alpha, beta):
    nếu terminal: return utility

    value = -infinity
    for child:
        value = max(value, MIN(child, alpha, beta))
        alpha = max(alpha, value)

        nếu alpha >= beta:
            break  # prune

    return value

MIN đối xứng: cập nhật beta = min(beta, value), rồi cùng điều kiện alpha >= beta thì dừng.

Python cùng ý, thêm hai tham số. break thoát vòng for ngay, không xét action còn lại.

def max_value(state, alpha, beta):
    if terminal(state):
        return utility(state)

    value = float("-inf")

    for action in actions(state):
        child = result(state, action)
        value = max(value, min_value(child, alpha, beta))
        alpha = max(alpha, value)

        if alpha >= beta:
            break

    return value

Không cần thuộc code. Cần nhớ: cùng kết quả Minimax, thêm hai mốc và một lệnh dừng sớm.

Alpha-Beta có đổi kết quả Minimax không?

Không, nếu triển khai đúng và duyệt cùng không gian nước đi.

Nó chỉ bỏ những nhánh đã chứng minh được là không thể làm thay đổi lựa chọn tối ưu ở phía trên.

kết quả Minimax == kết quả Alpha-Beta
số node Alpha-Beta xét  <=  số node Minimax xét

Hiệu quả phụ thuộc thứ tự xét action. Nếu hộp A (nước tốt, 4) được xét trước, alpha lên sớm, hộp B bị cắt. Nếu ta lỡ xét hộp C trước (1), alpha chỉ là 1, khi vào hộp B thấy 3 thì 1 >= ? chưa cắt được phiếu 9; phải lật cả 9 rồi mới biết min(3,9)=3.

Gợi ý thực dụng: thử nước “trông mạnh” trước — nước ăn quân, nước chiếu, nước vào giữa bàn Tic-Tac-Toe — để bound tốt tới sớm. Thứ tự không đổi tính đúng; nó đổi số nhánh cắt được.

Với cây cân và thứ tự tốt, số lá cần xem có thể gần bậc căn của Minimax đủ. Đó là lý do Alpha-Beta đủ dùng cho nhiều game nhỏ, nhưng vẫn chưa cứu được Chess nếu đòi search tới terminal.

Depth-Limited Minimax

Nếu cây quá lớn, đặt trần độ sâu.

Ply là một lượt của một người. MAX đi một nước = 1 ply. MIN đáp = ply thứ hai. “Nhìn trước 4 ply” nghĩa là 2 nước mỗi bên, không phải 4 ván.

Tại điểm dừng, state thường chưa terminal. Không có thắng/thua/hòa thật, nên không gọi utility. Ta cần một hàm khác: evaluation function.

Evaluation Function

Evaluation ước lượng state hiện tại đang nghiêng về MAX hay MIN.

Ví dụ minh họa cho cờ vua, chỉ tính quân trên bàn (material):

Hậu (Queen)   = 9
Xe (Rook)     = 5
Tượng (Bishop)= 3
Mã (Knight)   = 3
Tốt (Pawn)    = 1

Một evaluation cực thô:

score = tổng quân MAX - tổng quân MIN

• score dương lớn: material đang nghiêng MAX;
• score âm: nghiêng MIN.

Đây là ước lượng, không phải kết quả ván. MAX có thể hơn một tốt nhưng sắp bị chiếu hết. Evaluation thật còn xét vị trí quân, an toàn vua, số nước hợp lệ (mobility), cấu trúc tốt, và nhiều đặc trưng khác.

Tic-Tac-Toe nếu bị ép dừng sớm, một evaluation thô: đếm số hàng/cột/chéo X vẫn có thể hoàn thành, trừ số đường tương ứng của O. Đường đã bị đối thủ chặn thì không đếm.

Điểm cốt lõi:

Utility chấm kết quả thật ở terminal. Evaluation đoán chất lượng state khi ta cố ý dừng trước terminal.

Depth-limited Minimax chạy như Minimax, nhưng khi depth == limit thì return evaluation(state) thay vì gọi tiếp.

Hệ quả: nhìn nông có thể bỏ lỡ đòn ở đúng ply liền sau trần. Đó là lý do engine cờ vừa tăng depth vừa mài evaluation, chứ không chỉ tin một trong hai.

Utility và Evaluation đừng nhầm

Minimax có phải “AI biết trước tương lai” không?

Không. Nó mô phỏng các nhánh hợp lệ theo model rồi chọn nhánh tối ưu trong model đó.

Chất lượng phụ thuộc:

• state / actions / result có đúng luật không;
• search sâu bao nhiêu;
• evaluation (nếu có) có bắt được đặc trưng quan trọng không;
• thời gian và bộ nhớ;
• giả định đối thủ chơi tối ưu theo đúng utility.

Đây là một mẫu xuyên suốt AI: duyệt không gian khả năng, chấm từng khả năng, chọn hành động. Search mê cung chấm bằng path cost. Search game chấm bằng utility hoặc evaluation.

So sánh nhanh với search đã học

Alpha-Beta không thay hàng Minimax trong bảng. Nó là cách tính nhanh hơn cùng một giá trị.

Khi nào dùng gì, ở mức nhập môn:

• Game nhỏ, cần nước đúng theo utility: Minimax, thêm Alpha-Beta nếu muốn ít node hơn.
• Game lớn, không duyệt hết: depth limit + evaluation; Alpha-Beta vẫn dùng được bên trong cửa sổ đó.
• Mê cung, bản đồ, puzzle một người chơi: không dùng Minimax. Quay lại BFS / A*.

Những lỗi thường gặp

“MAX luôn là mình, MIN luôn là đối thủ”

Chỉ đúng theo cách ta gán utility. Nếu O là phía ta đang điều khiển và utility vẫn +1 khi X thắng, thì tới lượt O ta đang ở node MIN. Đổi vai được, miễn định nghĩa nhất quán.

“Alpha-Beta chọn nước khác Minimax”

Không. Nó tối ưu quá trình tính. Sai sót cập nhật alpha/beta mới làm lệch kết quả.

“Evaluation chính là utility”

Không. Utility khi đã biết thắng/thua/hòa. Evaluation khi chưa tới đó.

“Minimax đoán người thật sẽ đi nước nào”

Minimax giả định đối thủ tối ưu. Người thật có thể sai. Thuật toán vẫn chọn nước không thua nếu đối thủ bỗng chơi đúng. Nó không mô hình “hay quên” hay “thích đi góc”.

Sửa board tại chỗ trong result

Mọi nhánh sẽ dùng chung một list. Nước thử ở nhánh A còn đó khi đánh giá nhánh B. Luôn tạo bàn mới, như list(board) ở trên.

Tóm tắt

• Minimax: MAX lấy lớn nhất, MIN lấy nhỏ nhất, tính từ lá lên hoặc recursion từ gốc xuống;
• recursion dừng ở terminal, trả utility;
• Alpha-Beta: cùng kết quả, cắt nhánh khi alpha >= beta;
• thứ tự nước đi đổi tốc độ cắt, không đổi giá trị đúng;
• Depth-Limited: dừng trước terminal;
• Evaluation: ước lượng state tại điểm dừng.

Tự kiểm tra

1. Search trong game khác path finding ở chỗ nào? Ai đang chọn action?
2. Với 4 đồng, lấy 1 hoặc 2, ai lấy đồng cuối thắng: vì sao MAX phải lấy 1 chứ không lấy 2?
3. Actions(s), Result(s,a), Terminal(s) của Tic-Tac-Toe là gì, nói bằng bàn cờ chứ không bằng tên hàm?
4. Nếu X là MAX, tại sao X chọn max còn O chọn min? Câu trả lời phải dính với bảng +1 / 0 / -1.
5. Recursion Minimax dừng ở đâu? Trả về gì tại điểm đó?
6. Trên cây hộp A=4,6, B=3,9, C=5,1, Alpha-Beta cắt phiếu nào nếu xét A rồi B rồi C? Cắt xong giá trị gốc có đổi không?
7. Vì sao đổi thứ tự hộp có thể làm Alpha-Beta cắt ít hơn, dù nước chọn vẫn giống?
8. Utility và evaluation khác nhau chỗ nào? Chess 4 ply dùng cái nào tại node lá của cửa sổ search?
9. Minimax có đang dự đoán một người chơi hay quên không? Nó đang giả định gì?

Bài tiếp theo không thêm thuật toán mới. Nó buộc các lựa chọn DFS, BFS, A* và Minimax vào cùng một bản đồ quyết định: gặp bài mới thì hỏi đang search loại gì, trước khi viết code.

Bản tiếng Anh đang soạn.