Minimax

Minimax (còn gọi là minmax) là một phương pháp trong lý thuyết quyết định có mục đích là tối thiểu hóa (minimize) tổn thất vốn được dự tính có thể là "tối đa" (maximize). Có thể hiểu ngược lại là, nó nhằm tối đa hóa lợi ích vốn được dự tính là tối thiểu (maximin). Nó bắt nguồn từ trò chơi có tổng bằng không. Nó cũng được mở rộng cho nhiều trò chơi phức tạp hơn và giúp đưa ra các quyết định chung khi có sự hiện diện của sự không chắc chắn.

Một phiên bản của giải thuật áp dụng cho các trò chơi như tic-tac-toe, khi mà mỗi người chơi có thể thắng, thua, hoặc hòa. Nếu người chơi A có thể thắng trong 1 nước đi, thì "nước đi tốt nhất" chính là nước đi để dẫn đến kết quả thắng đó. Nếu người B biết rằng có một nước đi mà dẫn đến tình huống người A có thể thắng ngay ở nước đi tiếp theo, trong khi nước đi khác thì sẽ dẫn đến tình huống mà người chơi A chỉ có thể, tốt nhất, là hòa thì nước đi tốt nhất của người B chính là nước đi sau.

Ta sẽ nắm rõ, thế nào là một nước đi "tốt nhất". Giải thuật Minimax giúp tìm ra nước đi tốt nhất, bằng cách đi ngược từ cuối trò chơi trở về đầu. Tại mỗi bước, nó sẽ ước định rằng người A đang cố gắng tối đa hóa cơ hội thắng của A khi đến phiên anh ta, còn ở nước đi kế tiếp thì người chơi B cố gắng để tối thiểu hóa cơ hội thắng của người A (nghĩa là tối đa hóa cơ hội thắng của B).

Tiêu chuẩn Minimax trong lý thuyết quyết định thống kê

Trong lý thuyết quyết định thống kê cổ điển, ta có một đánh giá $\delta$ được dùng để đánh giá một tham số $\theta \in \Theta$ . Chúng ta cũng giả sử có một hàm rủi ro $R(\theta ,\delta )$ , thường được cho như là một tích phân của một hàm thua lỗ. Trong cấu trúc này, ${\tilde {\delta }}$ được gọi là minimax nếu như nó thỏa mãn

\sup _{\theta }R(\theta ,{\tilde {\delta }})=\inf _{\delta }\sup _{\theta }R(\theta ,\delta )

.

Một tiêu chuẩn khác trong lý thuyết quyết định là đánh giá Bayes với sự hiện diện của một phân bố cho trước $\Pi$ . Một đánh giá là Bayes nếu như nó làm tối thiểu rủi ro trung bình

\int _{\Theta }R(\theta ,\delta )\,d\Pi (\theta )

.

Giải thuật Minimax với các nước đi khác nhau

Một thuật toán minimax là một thuật toán đệ quy cho việc lựa chọn bước đi kế tiếp trong một trò chơi có hai người chơi. Một giá trị được gán cho mỗi vị trí hay một trạng thái của trò chơi. Giá trị này được tính toán bằng một hàm tính giá trị vị trí và nó cho biết độ tốt nếu như một người chơi đạt được đến đó. Người chơi sau đó đi một bước làm tối đa giá trị tối thiểu của vị trí là kết quả từ tập hợp những bước đi có thể của đối thủ. Nếu đó là phiên A sẽ đi, A sẽ cho một giá trị cho mỗi bước đi hợp pháp của anh ta.

Một phương pháp bố trí là gán cho một số vị trí thắng cho A như là +1 và cho B là −1. Điều này sẽ dẫn đến lý thuyết trò chơi tổ hợp được phát triển bởi John Horton Conway.

Một cách khác là sử dụng một quy định rằng nếu như kết quả của một bước đi là một chiến thắng lập tức cho A nó được gán dương vô hạn và, nếu như là một chiến thắng lập tức cho B, âm vô hạn. Giá trị cho A của bất kì nước đi nào khác là giá trị minimum của các giá trị kết quả từ mỗi bước trả lời có thể của B. (A được gọi là người chơi là cực đại và B gọi là người chơi làm cực tiểu), do vậy được gọi là thuật toán minimax. Thuật toán trên sẽ gán một giá trị dương hay âm vô hạn cho mỗi vị trí bởi vì giá trị của mỗi vị trí sẽ là giá trị của một số vị trí thắng hay thua nào đó. Thông thường nhìn chung điều này chỉ có thể xảy ra tại điểm cuối của những trò chơi phức tạp như cờ vua hay cờ vây, bởi vì về mặt tính toán ta không có khả năng tính xa đến mức kết thúc trò chơi, trừ khi là trò chơi sắp kết thúc, và các vị trí không đi khác nhau được cho các giá trị hữu hạn như là các đánh giá về mức độ tin tưởng là chúng sẽ dẫn đến chiến thắng cho người này hay người khác.

Điều này có thể được mở rộng nếu như chúng ta cung cấp một hàm đánh giá heuristic đưa ra các giá trị cho các vị trí trò chơi chưa phải là cuối cùng mà không xét tất cả mọi trường hợp theo sau một chuỗi đầy đủ. Chúng ta sau đó có thể giới hạn thuật toán minimax để chỉ xét một số nào đó các nước đi kế tiếp. Số này được gọi là "số bước kế tiếp", đo bằng "ply". Ví dụ, "Deep Blue" nhìn trước 12 ply.

Thuật toán này có thể được nghĩ như là khám phá các node của một cây trò chơi. Số cắt xén hiệu quả của một cây là trung bình của số các con của mỗi nốt (i.e., trung bình của các nước đi hợp pháp trong một vị trí). Số lượng các nodes được khám phá thường là tăng theo hàm mũ với số lượng ply (nó sẽ nhỏ hơn hàm mũ nếu đánh giá các nước đi bắt buộc hay là các bước lặp lại). Số lượng các nodes cần khám phá cho việc phân tích một trò chơi do đó gần bằng số cắt xét nâng lên luỹ thừa số ply. Do vậy là không thể phân tích trò chơi ví dụ như cờ vua một cách hoàn toàn chỉ bằng thuật toán minimax.

Sự trình diễn của thuật toán minimax ngây thơ có thể được cải tiến đáng kể, mà không ảnh hưởng đến kết quả, bằng cách sử dụng cắt xén alpha-beta. Các phương pháp cắt xén heuristic khác cũng có thể được sử dụng, nhưng không phải tất cả chúng bảo đảm sẽ cho kết quả giống nhau như là tìm kiếm không cắt xén.

Định lý Minimax với các bước đi liên tiếp

Trong ví dụ sau đây của một trò chơi tổng bằng 0, khi A và B đi các bước cùng một lúc, minh họa thuật toán minimax. Nếu như mỗi người chơi có 3 chọn lựa và ma trận lợi cho A là:

	B chọn B1	B chọn B2	B chọn B3
A chọn A1	+3	-2	+2
A chọn A2	-1	0	+4
A chọn A3	-4	-3	+1

và B có ma trận lợi như nhau nhưng ngược dấu (i.e. nếu các lựa chọn là A1 và B1 thì B trả 3 cho A) sau đó lựa chọn minimax đơn giản cho A là A2 bởi vì kết quả xấu nhất là sau khi phải trả 1, trong khi lựa chọn minimax đơn giản cho B là B2 bởi vì kết quả xấu nhất là sau đó không phải trả gì cả. Tuy vậy, lời giải này là không ổn định, bởi vì nếu B tin rằng A sẽ chọn A2 thì B sẽ chọn B1 để thắng 1; sau đó nếu A tin rằng B sẽ chọn B1 thì A sẽ chọn A1 để thắng 3; và sau đó B sẽ chọn B2; và cuối cùng cả hai người chơi sẽ nhận ra sự khó khăn của việc chọn lựa. Do đó một chiến lược ổn định hơn là cần thiết.

Một số chọn lựa bị thống trị bởi những người khác và có thể bị loại bỏ: A sẽ không chọn A3 bởi vì hoặc A1 hay A2 sẽ sinh ra một kết quả tốt hơn, bất kể là B chọn gì; B sẽ không chọn B3 bởi vì B2 sẽ sinh ra kết quả tốt hơn, bất kể là A chọn cái gì.

A có thể tránh việc phải trả số lượng dự định (expected payment) hơn 1/3 bằng cách chọn A1 với xác suất 1/6 và A2 với xác suất 5/6, bất kể là B đã chọn gì. B có thể tính chắc phần lợi dự định (expected gain) ít nhất 1/3 bằng cách sử dụng một chiến thuật ngẫu nhiên của việc chọn B1 với xác suất 1/3 và B2 với xác suất 2/3, bất kể là A chọn gì. Những chiến lược minimax hỗn hợp bây giờ là ổn định và không thể nào cải tiến nữa.

John von Neumann chứng minh định lý Minimax vào năm 1928, phát biểu rằng những chiến lược như vậy luôn luôn tồn tại trong những trò chơi tổng bằng không cho hai người chơi và có thể tìm ra bằng cách giải một tập hợp các phương trình trong cùng một lúc.

Minimax khi gặp sự không chắc chắn

Lý thuyết minimax đã được mở rộng ra các quyết định khi mà không có người chơi khác, nhưng các hậu quả của các quyết định dựa trên những sự kiện không biết trước. Chẳng hạn, quyết định tương lai phát đạt của một mỏ khoáng chất kèm theo đuôi một giá phải trả nếu như không có khoáng sản ở nơi muốn thăm dò, nhưng sẽ đem lại mối lợi lớn nếu có. Một tiếp cận là đối xử việc này như một trò chơi chống với Tự nhiên, và sử dụng một suy nghĩa giống như là luật Murphy, theo một tiếp cận làm tối thiểu các tổn thất dự định cực đại (maximum expected loss), sử dụng các kỹ thuật giống như trong những trò chơi hai người với tổng bằng không.

Thêm vào đó, các cây expectiminimax đã được phát triển, cho những trò chơi trong đó sự ngẫu nhiên (ví dụ, thảy xúc xắc) là một yếu tố.

Minimax trong các trò chơi tổng-khác-không

Nếu trò chơi có tổng khác không theo nghĩa các mối lợi giữa các người chơi, rõ ràng là các chiến lược không tối ưu có thể phát triển. Ví dụ trong song đề tù nhân, chiến lược minimax cho từng tù nhân là thú tội mặc dù họ sẽ có lợi hơn nếu cả hai đều chối bỏ tội của họ. Do vậy, trong các trò chơi tổng khác không chiến lược tốt nhất không phải là minimax mà là Tit for Tat.

Xem thêm

Tham khảo

Liên kết ngoài

The Minimax Theorem