Minimax

Minimax représente une partie comme un arbre de possibilités. Chaque branche est un coup et chaque niveau alterne entre un camp et l'autre. Un moteur d'échecs, c'est-à-dire un programme qui analyse des positions et sélectionne des coups, examine ses propres choix puis les meilleures réponses de l'adversaire. Son hypothèse centrale est prudente: il ne compte jamais sur une erreur de l'adversaire.

Aux niveaux où le moteur joue, l'algorithme conserve le résultat le plus favorable. Aux niveaux de l'adversaire, il conserve le résultat le moins favorable pour le moteur, car il suppose que l'adversaire résistera du mieux possible. Ces valeurs sont ensuite ramenées des positions futures vers la position actuelle. Les coups initiaux peuvent ainsi être comparés selon ce que chacun garantit face à la meilleure défense.

Une recherche pratique peut rarement examiner toute la partie. À sa limite de profondeur, elle emploie une fonction d'évaluation, formule qui estime quel camp a l'avantage. Un choix minimax à profondeur limitée n'est donc pas une preuve absolue: il dépend de la profondeur atteinte et de la précision de cette estimation. Il peut aussi subir l'effet d'horizon, lorsqu'une conséquence importante se trouve juste au-delà de la coupure.

Les moteurs rendent ce cadre efficace grâce à des techniques comme l'ordonnancement des coups, qui examine d'abord les choix prometteurs afin de rejeter plus vite les branches inutiles. D'autres systèmes, notamment la recherche arborescente Monte-Carlo, répartissent leur effort différemment tout en poursuivant le même objectif pratique: déterminer le coup qui mérite le plus de confiance.