Tìm kiếm đối kháng (minimax)
Khi tác tử không còn một mình trong thế giới mà phải đối mặt với một đối thủ thông minh đang tối ưu hóa ngược lại mục tiêu của ta, ta cần một họ thuật toán mới: tìm kiếm đối kháng, mà cốt lõi là minimax.
Ý tưởng cốt lõi
Trong các chương trước, tác tử là người chơi duy nhất: nó lập kế hoạch mà không lo ai cản đường. Nhưng nhiều bài toán quan trọng có hai tác tử cạnh tranh, nơi kết quả tốt cho bên này là kết quả xấu cho bên kia. Hai người chơi cờ vua, hai bên đấu giá, hai xe tự hành tranh một ô đỗ: tất cả đều là tìm kiếm đối kháng.
Chương này giới hạn ở lớp trò chơi có các tính chất sau:
- Hai người chơi, gọi là MAX (tác tử của ta) và MIN (đối thủ).
- Lượt luân phiên: hai bên đi xen kẽ, không đồng thời.
- Quan sát hoàn toàn: cả hai bên thấy đầy đủ trạng thái. Cờ vua, cờ vây, Tic-Tac-Toe thuộc nhóm này. Poker thì không, vì giấu bài.
- Tất định: mỗi hành động cho kết quả xác định. Backgammon không tất định vì có xúc xắc, ta sẽ xử lý ở mục expectimax.
- Tổng bằng không: một bên thắng đúng bằng bên kia thua. Hàm tiện ích thường nhận giá trị
+1,0,-1ứng với thắng, hòa, thua.
Điểm tế nhị quan trọng nhất: khi nói MAX chơi tối ưu, ta ngầm hiểu là tối ưu trong giả định MIN cũng chơi tối ưu. Minimax là phòng thủ chống lại trường hợp xấu nhất do một kẻ thù thông minh gây ra, chứ không phải khai thác cơ hội khi đối thủ chơi tệ.
Thử ngay: minimax và cắt tỉa alpha-beta trên cây ba tầng
Dưới đây là một cây trò chơi ba tầng: MAX chọn ở gốc, MIN chọn ở tầng giữa, mỗi lá là điểm số của một ván đã kết thúc. Minimax thuần đọc hết mọi lá. Cắt tỉa alpha-beta thì vừa đọc vừa giữ hai mốc, alpha là điểm tốt nhất MAX đã chắc chắn có và beta là điểm tốt nhất MIN đã chắc chắn có, rồi bỏ luôn một nhánh khi hai mốc đó cho thấy nhánh ấy không thể đổi kết quả. Bấm nút Sau để duyệt lần lượt từng lá, theo dõi alpha và beta thay đổi, và chú ý lúc nhánh b bị cắt ngay ở lá đầu tiên còn nhánh c thì phải đọc hết cả ba lá.
Chú ý một điểm cốt lõi khi bấm qua các bước: những lá bị đánh dấu đã cắt không hề được đọc, vậy mà giá trị trả về ở gốc vẫn đúng bằng 3 như minimax thuần. Đó là toàn bộ tinh thần của cắt tỉa: bỏ nhánh chứ không đổi kết quả.
Hình thức hóa trò chơi
Một trò chơi hai người tổng bằng không gồm sáu thành phần:
- Trạng thái khởi đầu
s0. - Hàm người đến lượt
Player(s), trả về MAX hoặc MIN. - Hàm hành động khả dụng
Actions(s). - Hàm chuyển trạng thái
T(s, a), cho trạng thái mới sau khi đi nướca. - Kiểm tra kết thúc
Terminal(s), trả về đúng hoặc sai. - Hàm tiện ích
Utility(s)trên các trạng thái kết thúc: giá trị số mà MAX thu được. Vì tổng bằng không, MIN thu được số đối của giá trị này.
So với bài toán tìm kiếm thông thường, khác biệt là: không có một trạng thái đích duy nhất mà có nhiều trạng thái kết thúc với giá trị khác nhau; có hai người chơi với mục tiêu ngược nhau; và không có chi phí từng bước, chỉ có tiện ích cuối cùng.
Cây trò chơi
Cây trò chơi có gốc là s0. Mỗi nút trong là một trạng thái chưa kết thúc; các con của nó là những trạng thái sinh ra bởi từng hành động khả dụng. Lá là các trạng thái kết thúc, gắn nhãn bằng giá trị Utility.
Cây trò chơi nhỏ có thể duyệt toàn bộ: Tic-Tac-Toe có khoảng vài trăm nghìn lá, một máy tính hiện đại duyệt trong vài mili giây. Nhưng cờ vua có cây cỡ 10^120 và cờ vây cỡ 10^360, hoàn toàn không thể duyệt hết, đó là lý do ta cần các kỹ thuật cắt tỉa và hàm lượng giá ở phần sau.
Con số bùng nổ dễ gây ngợp nên đáng hình dung cụ thể. Với hệ số phân nhánh b bằng 35 như cờ vua, nhìn trước một nước sinh ra 35 trạng thái, nhìn trước hai nước là 35*35 tức hơn một nghìn, ba nước đã hơn bốn vạn, và tới sáu nước con số đã gần hai tỉ. Mỗi tầng sâu thêm lại nhân với 35 lần nữa, nên chỉ vài chục tầng là vượt quá khả năng tính toán của mọi máy móc. Gốc rễ của sự bùng nổ này là tính nhân lên theo cấp số nhân: mỗi nước đi của ta lại mở ra một loạt phản ứng của đối thủ, mỗi phản ứng đó lại mở ra loạt nước tiếp theo của ta. Vì vậy mọi kỹ thuật trong chương, từ cắt tỉa tới cắt sâu giới hạn, đều nhắm vào một mục tiêu duy nhất là tránh phải sờ tới từng nhánh của cái cây khổng lồ đó.
Hãy hình dung một cây ba tầng nhỏ. Tại gốc, MAX chọn một trong ba hành động a, b, c. Mỗi hành động dẫn tới một nút mà MIN phải chọn trong hai hành động. Tầng cuối là các lá có giá trị tiện ích nhìn từ MAX.
Thuật toán minimax
Giá trị minimax của một nút được định nghĩa đệ quy:
- Nếu nút là lá, giá trị minimax bằng
Utilitycủa lá. - Nếu nút là của MAX, giá trị minimax bằng giá trị lớn nhất trong các con.
- Nếu nút là của MIN, giá trị minimax bằng giá trị nhỏ nhất trong các con.
Trực giác: tại nút MAX, ta giả định MAX chọn hành động dẫn tới giá trị lớn nhất; tại nút MIN, MIN chọn giá trị nhỏ nhất. Giá trị truyền từ lá lên dần tới gốc. Lời chơi tối ưu của MAX tại gốc chính là hành động dẫn tới con có giá trị minimax lớn nhất.
Bảng sau tóm tắt quy tắc tại mỗi loại nút:
| Loại nút | Quy tắc gộp giá trị con | Giá trị khởi tạo trước vòng lặp |
|---|---|---|
| MAX | lấy max các con | âm vô cùng |
| MIN | lấy min các con | dương vô cùng |
| Lá (kết thúc) | trả về Utility | không áp dụng |
Về độ phức tạp, gọi b là hệ số phân nhánh trung bình và m là độ sâu cây:
- Thời gian: cỡ
b^m, đây là rào cản lớn. - Bộ nhớ: cỡ
b*mvới bản đệ quy duyệt theo chiều sâu, rất tiết kiệm. - Đầy đủ và tối ưu: có, nếu cây hữu hạn và đối thủ chơi tối ưu.
Với cờ vua, b khoảng 35 và m khoảng 80, nên b^m lớn hơn cả số nguyên tử trong vũ trụ quan sát được. Vì vậy minimax thuần chỉ dùng được cho trò chơi rất nhỏ như Tic-Tac-Toe. Một kết quả thú vị: minimax áp dụng cho toàn cây Tic-Tac-Toe cho giá trị 0, nghĩa là nếu cả hai bên chơi tối ưu thì luôn hòa.
Cắt tỉa alpha-beta
Minimax phải duyệt toàn bộ cây, nhưng có một quan sát then chốt: ta không cần duyệt nhánh mà giá trị của nó không thể ảnh hưởng tới quyết định cuối cùng.
Ví dụ trong cây ba tầng: giả sử nhánh a đã cho giá trị 3. Khi xét nhánh b, nếu lá đầu tiên của b là 2, thì MIN tại b chắc chắn cho ra giá trị không lớn hơn 2. Vì MAX ở gốc đã có lựa chọn a bằng 3, mọi giá trị không lớn hơn 2 ở b đều không thể tốt hơn. Do đó ta khỏi cần xét các lá còn lại của b, đó là một lần cắt.
Để tổng quát hóa, ta duy trì hai giá trị trong suốt quá trình duyệt:
- alpha: giá trị tốt nhất cho MAX mà MAX đã đảm bảo được trên đường đi từ gốc. Khởi đầu là âm vô cùng và chỉ tăng.
- beta: giá trị tốt nhất cho MIN mà MIN đã đảm bảo được trên đường đi từ gốc. Khởi đầu là dương vô cùng và chỉ giảm.
Điều kiện cắt: bất cứ khi nào alpha lớn hơn hoặc bằng beta, thuật toán có thể dừng duyệt phần cây con còn lại của nút hiện tại.
Điểm quan trọng: alpha-beta trả về đúng cùng giá trị minimax như thuật toán gốc, chỉ duyệt ít nút hơn nên nhanh hơn, không hề thay đổi kết quả. Hiệu quả phụ thuộc thứ tự duyệt: với thứ tự ngẫu nhiên vẫn cỡ b^m, trung bình cỡ b^(3m/4), còn với thứ tự hoàn hảo (xét nước tốt nhất trước) đạt cỡ b^(m/2). Trường hợp tốt nhất này cho phép duyệt sâu gấp đôi trong cùng thời gian, đó là khác biệt giữa người chơi mới và người chơi giỏi.
Vì sao thứ tự duyệt lại quyết định hiệu quả đến vậy? Cắt tỉa chỉ xảy ra khi ta đã có sẵn một cận đủ tốt để loại bỏ nhánh khác. Nếu tình cờ xét nước đi mạnh nhất trước, cận alpha tăng nhanh và hầu hết các nhánh yếu phía sau bị cắt ngay từ lá đầu tiên. Ngược lại nếu xét nước yếu trước, ta phải duyệt gần hết mới tình cờ gặp nước mạnh, và gần như không cắt được gì. Vì thế các cỗ máy chơi cờ thực tế bỏ nhiều công vào sắp thứ tự nước đi trước khi duyệt: ưu tiên nước ăn quân, nước từng chứng tỏ tốt ở một lần duyệt nông hơn, hay nước được một bảng tra gợi ý. Cần nhắc lại rằng dù thứ tự tốt hay tệ, kết quả cuối cùng của alpha-beta vẫn y hệt minimax thuần; thứ tự chỉ đổi số nút phải duyệt chứ tuyệt nhiên không đổi nước đi được chọn, bởi nhánh bị cắt luôn là nhánh đã chứng minh được là không thể tốt hơn lựa chọn hiện có.
Có người nghĩ minimax sẽ chơi kém khi gặp đối thủ yếu, vì nó luôn giả định đối thủ chơi tối ưu. Thực ra giả định đó chỉ khiến minimax phòng thủ theo trường hợp xấu nhất: nó bảo đảm kết quả không tệ hơn giá trị minimax dù đối thủ có giỏi đến đâu. Khi đối thủ đi một nước dở, trạng thái mới thường có giá trị minimax cao hơn cho ta, nên minimax vẫn hưởng lợi và tận dụng sai lầm đó ở những lượt sau. Nó không chủ động gài bẫy để dụ đối thủ mắc lỗi, nhưng cũng không hề bỏ lỡ món quà khi lỗi đã xảy ra.
Hàm lượng giá và cắt sâu giới hạn
Ngay cả alpha-beta tốt nhất vẫn cỡ b^(m/2), với cờ vua vẫn không khả thi để duyệt tới lá. Giải pháp thực dụng là không duyệt tới lá: dừng ở một độ sâu giới hạn d, rồi dùng một hàm lượng giá Eval(s) để ước lượng giá trị minimax của trạng thái mà không cần duyệt tiếp.
Một hàm lượng giá tốt cần ba tính chất:
- Trùng với
Utilitytại trạng thái kết thúc. - Đánh giá nhanh, nhanh hơn nhiều so với duyệt con cháu.
- Tương quan tốt với cơ hội thắng: trạng thái có
Evalcao hơn thực sự dễ thắng hơn.
Cách phổ biến nhất là tổ hợp tuyến tính các đặc trưng: Eval(s) = w1*f1(s) + w2*f2(s) + ... + wk*fk(s), trong đó mỗi fi là một đặc trưng số (số quân, kiểm soát trung tâm, an toàn vua) và wi là trọng số tinh chỉnh tay hoặc học từ dữ liệu. Với cờ vua, một hàm cổ điển gán trọng số hậu 9, xe 5, tượng 3, mã 3, tốt 1, rồi lấy hiệu giữa hai bên.
Cắt sâu giới hạn sinh ra hiện tượng đường chân trời: thuật toán đẩy một mất mát không tránh khỏi ra ngoài tầm nhìn bằng các nước trì hoãn vô nghĩa, khiến nó tưởng đã tránh được. Kỹ thuật quiescence search giảm hiện tượng này: tại độ sâu giới hạn, nếu trạng thái chưa yên tĩnh (sắp có nước ăn quân hay chiếu) thì duyệt thêm vài tầng cho tới khi yên tĩnh rồi mới gọi Eval.
Expectimax: trò chơi có yếu tố ngẫu nhiên
Backgammon và các trò chơi xúc xắc có thêm một loại nút mới: nút cơ hội. Tại nút này không người chơi nào chọn hành động, mà tự nhiên chọn theo một phân phối xác suất đã biết. Giá trị expectimax giống minimax tại nút MAX và MIN, nhưng tại nút cơ hội ta lấy kỳ vọng, tức trung bình có trọng số theo xác suất, thay vì max hay min.
Một điểm tế nhị: trong minimax thuần, ta có thể nhân thang đo tiện ích tùy ý mà quyết định không đổi. Nhưng trong expectimax, thang đo quan trọng. Xét hai hành động:
a1: chắc chắn được+100.a2: 50% được+200, 50% được0.
Kỳ vọng của cả hai đều bằng 100, nên ngang nhau. Nhưng nếu đổi +200 thành +1000, kỳ vọng của a2 thành 500 và expectimax sẽ chọn a2. Vậy thang tiện ích phải phản ánh đúng mức ưa thích thực sự của người chơi, không thể co giãn tùy ý.
Về cắt tỉa: tại nút cơ hội với c kết quả, expectimax phải duyệt tất cả vì không thể bỏ qua bằng cắt. Alpha-beta vẫn áp dụng cho nút MAX và MIN nhưng không cho nút cơ hội.
Mã nguồn Python
# vi du: minimax tren mot cay tro choi nho
# moi nut la dict: {"player": "MAX"/"MIN", "children": [...]} hoac la (la) la mot so
def minimax(node):
# truong hop co so: nut la la mot gia tri tien ich
if isinstance(node, (int, float)):
return node
values = [minimax(child) for child in node["children"]]
if node["player"] == "MAX":
return max(values)
else: # MIN
return min(values)
# cay vi du 3 tang trong bai: goc MAX -> 3 nut MIN -> cac la
tree = {
"player": "MAX",
"children": [
{"player": "MIN", "children": [3, 12, 8]}, # nhanh a
{"player": "MIN", "children": [2, 4, 6]}, # nhanh b
{"player": "MIN", "children": [14, 5, 2]}, # nhanh c
],
}
print(minimax(tree)) # in ra 3: gia tri minimax cua goc
Phiên bản có cắt tỉa alpha-beta cho đúng cùng kết quả nhưng bỏ qua các nhánh vô ích:
# alpha-beta: tra ve dung gia tri minimax nhung duyet it nut hon
INF = float("inf")
def alpha_beta(node, alpha, beta):
if isinstance(node, (int, float)):
return node
if node["player"] == "MAX":
value = -INF
for child in node["children"]:
value = max(value, alpha_beta(child, alpha, beta))
if value >= beta: # cat beta: MIN o tren se khong cho phep
return value
alpha = max(alpha, value)
return value
else: # MIN
value = INF
for child in node["children"]:
value = min(value, alpha_beta(child, alpha, beta))
if value <= alpha: # cat alpha: MAX o tren da co lua chon tot hon
return value
beta = min(beta, value)
return value
print(alpha_beta(tree, -INF, INF)) # cung in ra 3
# expectimax: them nut "CHANCE" lay ky vong theo xac suat
# nut chance: {"player": "CHANCE", "children": [(prob, child), ...]}
def expectimax(node):
if isinstance(node, (int, float)):
return node
if node["player"] == "MAX":
return max(expectimax(c) for c in node["children"])
if node["player"] == "MIN":
return min(expectimax(c) for c in node["children"])
# CHANCE: trung binh co trong so theo xac suat
return sum(prob * expectimax(child) for prob, child in node["children"])
chance_tree = {
"player": "MAX",
"children": [
{"player": "CHANCE", "children": [(0.5, 200), (0.5, 0)]}, # a2: ky vong 100
100, # a1: chac chan 100
],
}
print(expectimax(chance_tree)) # 100: hai hanh dong ngang nhau o thang nay
Bài tập thực hành
Bài tập 1: tính tay giá trị minimax
Cho cây ba tầng: gốc là nút MAX, có ba con MIN. Con MIN thứ nhất có các lá 3, 12, 8; con thứ hai có 2, 4, 6; con thứ ba có 14, 5, 2. Hãy tính giá trị minimax của từng nút MIN, rồi của gốc, và cho biết MAX nên chọn nhánh nào.
Gợi ý
Mỗi nút MIN lấy giá trị nhỏ nhất trong các lá con của nó, cho ra 3, 2, 2. Gốc MAX lấy giá trị lớn nhất trong ba số đó, bằng 3. Vậy MAX chọn nhánh thứ nhất.
Bài tập 2: tìm các nhánh bị alpha-beta cắt
Vẫn dùng cây ở bài tập 1, duyệt các con từ trái sang phải. Sau khi xác định nhánh thứ nhất cho giá trị 3, hãy cho biết nhánh thứ hai bị cắt ở lá nào, và vì sao nhánh thứ ba lại phải duyệt hết cả ba lá mà không cắt được lá nào.
Gợi ý
Tại nhánh thứ hai, lá đầu tiên là 2. Vì alpha đang bằng 3 mà giá trị nút MIN đã không thể lớn hơn 2, điều kiện cắt (giá trị nút MIN nhỏ hơn hoặc bằng alpha) thỏa mãn ngay, nên ta cắt và bỏ qua 4 và 6. Nhánh thứ ba thì khác: hai lá đầu là 14 rồi 5 đều lớn hơn alpha bằng 3 nên chưa cắt được, phải duyệt tiếp tới lá thứ ba là 2 mới biết nút MIN này bằng 2. Vì 2 là lá cuối, nhánh thứ ba phải duyệt hết cả ba lá mà không cắt được lá nào. Đây chính là minh họa alpha-beta chỉ cắt bớt được khi thứ tự duyệt thuận lợi.
Bài tập 3: vì sao thang tiện ích quan trọng với expectimax
Cho một nút MAX có hai lựa chọn: lựa chọn A chắc chắn cho +100; lựa chọn B là nút cơ hội cho +300 với xác suất 0.5 và 0 với xác suất 0.5. Hãy tính giá trị expectimax của mỗi lựa chọn và giải thích vì sao trong minimax thuần kết quả có thể khác.
Gợi ý
Kỳ vọng của B là 0.5*300 + 0.5*0 = 150, lớn hơn 100 của A, nên expectimax chọn B. Trong minimax thuần không có nút cơ hội nên ta không lấy kỳ vọng được; nếu cố quy về max/min thì việc co giãn thang giá trị sẽ không đổi quyết định, khác hẳn expectimax nơi thang đo trực tiếp ảnh hưởng lựa chọn.
Tự kiểm tra
Alpha-beta có thay đổi nước đi mà minimax chọn không?
Không. Alpha-beta trả về đúng cùng giá trị minimax và cùng lời chơi tối ưu, nó chỉ duyệt ít nút hơn nên chạy nhanh hơn. Hiệu quả cắt tỉa phụ thuộc thứ tự duyệt nhưng kết quả cuối cùng luôn giống minimax.
Vì sao không thể cắt tỉa tại nút cơ hội như tại nút MAX hay MIN?
Tại nút MAX và MIN, một con đủ tốt hoặc đủ tệ là có thể kết luận và bỏ qua phần còn lại. Nhưng giá trị nút cơ hội là kỳ vọng trên tất cả kết quả, nên bỏ qua bất kỳ kết quả nào cũng làm sai trung bình. Do đó expectimax phải duyệt mọi nhánh của nút cơ hội, trừ các biến thể đặc biệt khi đã biết cận trên và cận dưới của tiện ích.
Câu hỏi tự kiểm
- 1Tại một nút MIN, giá trị minimax được tính thế nào từ các con?
- 2Cắt tỉa alpha-beta ảnh hưởng thế nào so với minimax thuần?
- 3Với thứ tự duyệt hoàn hảo (xét nước tốt nhất trước), độ phức tạp thời gian của alpha-beta đạt cỡ nào?
- 4Vì sao không thể cắt tỉa tại nút cơ hội trong expectimax?
Tìm kiếm đối kháng giải các trò chơi hai người tổng bằng không bằng cách lan giá trị từ lá lên gốc của cây trò chơi: nút MAX lấy max, nút MIN lấy min. Minimax tối ưu nhưng tốn cỡ b^m thời gian. Cắt tỉa alpha-beta cho đúng kết quả mà nhanh hơn, tốt nhất đạt cỡ b^(m/2). Khi cây quá lớn, ta cắt ở độ sâu giới hạn và dùng hàm lượng giá để ước lượng. Với trò chơi có yếu tố ngẫu nhiên, expectimax thay phép max/min tại nút cơ hội bằng kỳ vọng theo xác suất, và khi đó thang đo tiện ích trở nên quan trọng.