Minimax

Minimax biểu diễn ván cờ như một cây khả năng. Mỗi nhánh là một nước đi và mỗi tầng luân phiên giữa hai bên. Một máy cờ, tức chương trình phân tích thế cờ và chọn nước đi, xem xét các lựa chọn của mình rồi đến những lời đáp mạnh nhất của đối thủ. Giả định cốt lõi rất thận trọng: nó không dựa vào việc đối thủ sẽ mắc sai lầm.

Ở các tầng máy cờ đến lượt, thuật toán giữ kết quả có lợi nhất. Ở các tầng của đối thủ, nó giữ kết quả bất lợi nhất cho máy cờ, vì giả định đối thủ sẽ kháng cự tối ưu. Sau đó các giá trị được truyền ngược từ thế cờ tương lai về thế hiện tại. Nhờ vậy, các nước đầu tiên được so sánh theo kết quả mà mỗi nước có thể bảo đảm trước phòng thủ tốt nhất.

Một tìm kiếm thực tế hiếm khi có thể xét toàn bộ ván cờ. Tại giới hạn độ sâu, nó dùng một hàm đánh giá, tức công thức ước tính bên nào tốt hơn. Vì vậy, lựa chọn minimax có giới hạn độ sâu không phải chứng minh tuyệt đối: nó phụ thuộc vào tìm kiếm đã đi bao xa và ước lượng chính xác đến mức nào. Nó cũng có thể chịu hiệu ứng chân trời, khi một hệ quả quan trọng nằm ngay ngoài điểm cắt.

Máy cờ làm khung này hiệu quả bằng các kỹ thuật như sắp thứ tự nước đi, xem các lựa chọn hứa hẹn trước để loại sớm nhánh không liên quan. Những hệ thống khác, gồm tìm kiếm cây Monte Carlo, phân bổ công sức theo cách khác nhưng cùng theo đuổi mục tiêu thực tế: xác định nước đi đáng tin cậy nhất.