Minimax

Minimax merepresentasikan permainan sebagai pohon kemungkinan. Setiap cabang adalah langkah dan setiap tingkat bergantian antara satu pihak dan pihak lain. Mesin catur, yaitu program yang menganalisis posisi dan memilih langkah, mempertimbangkan pilihannya sendiri lalu jawaban terkuat lawan. Asumsi utamanya bersifat hati-hati: algoritma ini tidak pernah mengandalkan lawan melakukan kesalahan.

Pada tingkat tempat mesin melangkah, algoritma mempertahankan hasil yang paling menguntungkan. Pada tingkat lawan, algoritma mempertahankan hasil yang paling tidak menguntungkan bagi mesin karena lawan dianggap melawan sebaik mungkin. Nilai-nilai tersebut kemudian dibawa mundur dari posisi masa depan ke posisi saat ini. Karena itu, langkah awal dapat dibandingkan berdasarkan hasil yang dapat dijamin masing-masing terhadap pertahanan terbaik.

Pencarian praktis hampir tidak pernah dapat memeriksa seluruh partai. Pada batas kedalamannya, pencarian menggunakan fungsi evaluasi, yaitu formula yang memperkirakan pihak mana yang lebih baik. Karena itu, pilihan minimax dengan kedalaman terbatas bukan bukti mutlak: hasilnya bergantung pada seberapa jauh pencarian berjalan dan seberapa akurat perkiraan tersebut. Minimax juga dapat mengalami efek horizon, ketika konsekuensi penting berada tepat di luar batas.

Mesin membuat kerangka ini efisien dengan teknik seperti pengurutan langkah, yang memeriksa pilihan menjanjikan lebih dahulu agar cabang tidak relevan dapat ditolak lebih cepat. Sistem lain, termasuk pencarian pohon Monte Carlo, membagikan upaya secara berbeda sambil mengejar tujuan praktis yang sama: mengenali langkah yang paling layak dipercaya.