Dans ce sujet, nous proposons de programmer l'algorithme du minimax, qui permet à un programme informatique de jouer à un jeu à deux joueurs (comme les échecs, othello, puissance 4 etc.)

Le principe de cet algorithme est d'examiner toutes les possibilités de jeux, jusqu'à une certaine profondeur (un certain nombre de coups à l'avance), afin de choisir le meilleur coup. Nous allons prendre l'exemple du programme puissance 4, relativement simple, sans être trivial.

À chaque tour, chaque joueur peut jouer dans une des sept colonnes (ou moins, si certaines colonnes sont remplies). Le premier à aligner 4 pions verticalement, horizontalement ou en diagonale gagne. Supposons que l'ordinateur est le joueur A, et l'humain le joueur B. C'est au joueur A de jouer, et il examine les 7 positions qu'il peut atteindre, il les note et choisit la mieux notée. Pour noter chacune des 7 situations, il envisage chacun des 7 coups possibles de B dans chacune des 7 situations. Il sait que B jouera le mieux possible, donc la note de chaque situation qui se présente à A sera la plus petite des 7 notes affextées aux situations qui se présentent à B. Examiner un coup supplémentaire en avant multiplie par 7 le nombre de situations examinées.