Minimax

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.

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.