Thuật toán Minmax

[baotrung]

Thuật toán Minmax hay còn gọi là Minimax là một thuật toán dùng trong tìm kiếm có đối thủ. Cải tiến của thuật toán này là thuật toán cắt tỉa Alpha-Beta (Alpha - Beta Pruning) rất hay được sử dụng làm chiến lược cho tìm kiếm nước đi trong không gian tìm kiếm của trò chơi có tính chất đối kháng (vd cờ Tướng, cờ Vua, cờ caro... ). Nói một cách dễ hiểu, thì ý nghĩa của thuật toán này bạn có thể hiểu một cách đơn giản như sau: Giả sử bạn đang đánh cờ với máy, thì cả bàn cờ sẽ được biểu diễn trong một cái gọi là không gian trạng thái (KGTT) - bạn có thể hình dung KGTT chính là cách mà máy tính biểu diễn bàn cờ thực lên bộ nhớ máy tính. Với mỗi nước đi (mỗi thay đổi) sẽ làm cho KGTT của bàn cờ thay đổi thành một KGTT mới. Như vậy, đến nước đi của máy. Chiến lược tìm kiếm nước đi Minimax sẽ được sử dụng để làm sao tìm ra nước đi tốt nhất cho máy. Để có được nước đi tốt thì cần có một sự lượng giá tốt - là kết quả từ một hàm lượng giá (tức là cách đánh giá, như lúc mình tính ở trong đầu í == độ uyên thâm). Độ sâu (depth) là số nước mà máy sẽ tính trước. Như vậy giả sử với độ sâu là 4 thì sẽ tìm với tầm nhìn là 4 nước đi. Nút có kết quả lượng giá cao nhất ở mức gốc (mức 0) sẽ được chọn để đi (trong hình ở mức 0 chỉ có 1nút thôi, nên bạn hình dung là như vậy).


Mức 0, 2, 4 là lượt đi của máy - mức MAX (kết quả lượng giá càng lớn càng tốt).
Mức 1, 3 là lượt đi của người - mức MIN (kết quả lượng giá càng nhỏ càng tốt).

Có một cuốn ebook là quyển Trí tuệ nhân tạo của thầy Nguyễn Mạnh Tường (ĐHQGHN) có phần về tìm kiếm có đối thủ viết rất dễ hiểu về thuật toán này. Bạn có thể google rồi tải về. Bạn xem chi tiết trong đó sẽ hiểu. Lâu rồi nên mình giải thích lại thấy chập choạng quá, càng nói càng thấy bị rối lên !.

[baotrung]

Quá trình chơi cờ là quá trình Trắng và Đen thay phiên nhau đưa ra quyết định, thực hiện một trong số các nước đi hợp lệ. Trên cây trò chơi, quá trình đó sẽ tạo ra đường đi từ gốc tới lá. Giả sử tới một thời điểm nào đó, đường đi đã dẫn tới đỉnh u. Nếu u là đỉnh Trắng (Đen) thì Trắng (Đen) cần chọn đi tới một trong các đỉnh Đen (Trắng) v là con của u. Tại đỉnh Đen (Trắng) v mà Trắng (Đen) vừa chọn, Đen (Trắng) sẽ phải chọn đi tới một trong các đỉnh Trắng (Đen) w là con của v. Quá trình trên sẽ dừng lại khi đạt tới một đỉnh là lá của cây.

Giả sử Trắng cần tìm nước đi tại đỉnh u. Nước đi tối ưu cho Trắng là nước đi dần tới đỉnh con của v là đỉnh tốt nhất (cho Trắng) trong số các đỉnh con của u. Ta cần giả thiết rằng, đến lượt đối thủ chọn nước đi từ v, Đen cũng sẽ chọn nước đi tốt nhất cho anh ta. Như vậy, để chọn nước đi tối ưu cho Trắng tại đỉnh u, ta cần phải xác định giá trị các đỉnh của cây trò chơi gốc u. Giá trị của các đỉnh lá (ứng với các trạng thái kết thúc) là giá trị của hàm kết cuộc. Đỉnh có giá trị càng lớn càng tốt cho Trắng, đỉnh có giá trị càng nhỏ càng tốt cho Đen. Để xác định giá trị các đỉnh của cây trò chơi gốc u, ta đi từ mức thấp nhất lên gốc u. Giả sử v là đỉnh trong của cây và giá trị các đỉnh con của nó đã được xác định. Khi đó nếu v là đỉnh Trắng thì giá trị của nó được xác định là giá trị lớn nhất trong các giá trị của các đỉnh con. Còn nếu v là đỉnh Đen thì giá trị của nó là giá trị nhỏ nhất trong các giá trị của các đỉnh con.






Ví dụ: Xét cây trò chơi trong hình 4.3, gốc a là đỉnh Trắng. Giá trị của các đỉnh là số ghi cạnh mỗi đỉnh. Đỉnh i là Trắng, nên giá trị của nó là max(3,-2) = 3, đỉnh d là đỉnh Đen, nên giá trị của nó là min(2, 3, 4) = 2. Việc gán giá trị cho các đỉnh được thực hiện bởi các hàm đệ qui MaxVal và MinVal. Hàm MaxVal xác định giá trị cho các đỉnh Trắng, hàm MinVal xác định giá trị cho các đỉnh Đen.

function MaxVal(u);
begin
if u là đỉnh kết thúc then MaxVal(u) ¬ f(u)
else MaxVal(u) ¬ max{MinVal(v) | v là đỉnh con của u}
end;

function MinVal(u);
begin
if u là đỉnh kết thúc then MinVal(u) ¬ f(u)
else MinVal(u) ¬ min{MaxVal(v) | v là đỉnh con của u}
end;

Trong các hàm đệ quy trên, f(u) là giá trị của hàm kết cuộc tại đỉnh kết thúc u. Sau đây là thủ tục chọn nước đi cho trắng tại đỉnh u. Trong thủ tục Minimax(u,v), v là biến lưu lại trạng thái mà Trắng đã chọn đi tới từ u.

procedure Minimax(u, v);
begin
val ¬ -¥;
for mỗi w là đỉnh con của u do
if val <= MinVal(w) then
{val¬ MinVal(w);
v ¬ w}
end;

Thủ tục chọn nước đi như trên gọi là chiến lược Minimax, bởi vì Trắng đã chọ được nước đi dẫn tới đỉnh con có giá trị là max của các giá trị các đỉnh con, và Đen đáp lại bằng nước đi tới đỉnh có giá trị là min của các giá trị các đỉnh con.

Thuật toán Minimax là thuật toán tìm kiếm theo độ sâu, ở đây ta đã cài đặt thuật toán Minimax bởi các hàm đệ quy. Bạn đọc hãy viết thủ tục không đệ quy thực hiện thuật toán này.

Về mặt lí thuyết, chiến lược Minimax cho phép ta tìm được nước đi tối ưu cho Trắng. Song nó không thực tế, chúng ta sẽ không có đủ thời gian để tính được nước đi tối ưu. Bởi vì thuật toán Minimax đòi hỏi ta phải xem xét toàn bộ các đỉnh của cây trò chơi. Trong các trò chơi hay, cây trò chơi là cực kỳ lớn. Chẳng hạn, đối với cờ vua, chỉ tính đến độ sâu 40, thì cây trò chơi đã có khoảng 10¹²⁰ đỉnh! Nếu cây có độ cao m, và tại mỗi đỉnh có b nước đi thì độ phức tạp về thời gian của thuật toán Minimax là O(bm).

Để có thể tìm ra nhanh nước đi tốt (không phải là tối ưu) thay cho việc sử dụng hàm kết cuộc và xem xét tất cả các khả năng dẫn tới các trạng thái kết thúc, chúng ta sẽ sử dụng hàm đánh giá và chỉ xem xét một bộ phận của cây trò chơi.

Hàm đánh giá

Hàm đánh giá eval ứng với mỗi trạng thái u của trò chơi với một giá trị số eval(u), giá trị này là sự đánh giá “độ lợi thế” của trạng thái u. Trạng thái u càng thuận lợi cho Trắng thì eval(u) là số dương càng lớn; u càng thuận lợi cho Đen thì eval(u) là số âm càng nhỏ; eval(u) » 0 đối với trạng thái không lợi thế cho ai cả.

Chất lượng của chương trình chơi cờ phụ thuộc rất nhiều vào hàm đánh giá. Nếu hàm đánh giá cho ta sự đánh giá không chính xác về các trạng thái, nó có thể hướng dẫn ta đi tới trạng thái được xem là tốt, nhưng thực tế lại rất bất lợi cho ta. Thiết kế một hàm đánh giá tốt là một việc khó, đòi hỏi ta phải quan tâm đến nhiều nhân tố: các quân còn lại của hai bên, sự bố trí của các quân đó, ... ở đây có sự mâu thuẫn giữa độ chính xác của hàm đánh giá và thời gian tính của nó. Hàm đánh giá chính xác sẽ đòi hỏi rất nhiều thời gian tính toán, mà người chơi lại bị giới hạn bởi thời gian phải đưa ra nước đi.

Ví dụ 1: Sau đây ta đưa ra một cách xây dựng hàm đánh giá đơn giản cho cờ vua. Mỗi loại quân được gán một giá trị số phù hợp với “sức mạnh” của nó. Chẳng hạn, mỗi tốt Trắng (Đen) được cho 1 (-1), mã hoặc tượng Trắng (Đen) được cho 3 (-3), xe Trắng (Đen) được cho 5 (-5) và hoàng hậu Trắng (Đen) được cho 9 (-9). Lấy tổng giá trị của tất cả các quân trong một trạng thái, ta sẽ được giá trị đánh giá của trạng thái đó. Hàm đánh giá như thế được gọi là hàm tuyến tính có trọng số, vì nó có thể biểu diễn dưới
dạng:
s₁w₁
+s₂w₂+. . .
+snwn.

Trong đó, wi là giá trị mỗi loại quân, còn si là số quân loại đó. Trong cách đánh giá này, ta đã không tính đến sự bố trí của các quân, các mối tương quan giữa chúng.

Ví dụ 2: Bây giờ ta đưa ra một cách đánh giá các trạng thái trong trò chơi Dodgem. Mỗi quân Trắng ở một vị trí trên bàn cờ được cho một giá trị tương ứng trong bảng bên trái hình 4.4. Còn mỗi quân Đen ở một vị trí sẽ được cho một giá trị tương ứng trong bảng bên phải hình 4.4:





Ngoài ra, nếu quân Trắng cản trực tiếp một quân Đen, nó được thêm 40 điểm, nếu cản gián tiếp nó được thêm 30 điểm (Xem hình 4.5). Tương tự, nếu quân Đen cản trực tiếp quân Trắng nó được thêm -40 điểm, còn cản gián tiếp nó được thêm -30 điểm.





Áp dụng các qui tắc trên, ta tính được giá trị của trạng thái ở bên trái hình 4.6 là 75, giá trị của trạng thái bên phải hình vẽ là -5. Trong cánh đánh giá trên, ta đã xét đến vị trí của các quân và mối tương quan giữa các quân.





Một cách đơn giản để hạn chế không gian tìm kiếm là, khi cần xác định nước đi cho Trắng tại u, ta chỉ xem xét cây trò chơi gốc u tới độ cao h nào đó. Áp dụng thủ tục Minimax cho cây trò chơi gốc u, độ cao h và sử dụng giá trị của hàm đánh giá cho các lá của cây đó, chúng ta sẽ tìm được nước đi tốt cho Trắng tại u.