Cela permet de programmer des algorithmes d’exploration de l’arbre d’un jeu, par exemple pour identifier une stratégie optimale pour l’un des joueurs. Partant d’une position donnée, c’est-à-dire d’un sommet de l’arbre, on peut en effet dérouler toutes les suites possibles pour la partie en cours, en parcourant entièrement ou partiellement les branches de l’arbre qui partent de ce sommet. Cela permet de juger dans quelle direction il est préférable d’emmener la partie, pour le joueur dont c’est le tour. C’est en réalité exactement ce que font les joueurs de bon niveau aux échecs ou à d’autres jeux de ce type, et ce procédé est facilement automatisable pour pouvoir être mené par un ordinateur en exploitant une importante puissance de calcul.
Ce genre de raisonnement est à la base d’un algorithme très célèbre, appelé «MiniMax» (ou parfois «MinMax»), qui permet de déterminer si une position donnée dans un jeu est «gagnante» pour l’un des joueurs – c’est-à-dire si quels que soient les choix de jeu de son adversaire par la suite, ce joueur peut forcément réagir d’une manière qui, en définitive, lui assurera la victoire. Cependant, il n’est pas toujours possible d’exploiter directement cet algorithme, car les arbres de certains jeux sont tellement grands que même les ordinateurs les plus puissants ne parviennent pas à les parcourir en entier en un temps raisonnable !
Revenons à Oxo et à notre question d’origine: comment s’assurer de ce que notre intuition nous indique: si les 2 joueurs jouent bien, la partie s’achèvera nécessairement sur un match nul. En parcourant toutes les branches de l’arbre depuis l’origine, on constate pourtant que certaines parties s’achèvent par la victoire de l’un ou l’autre des joueurs. Mais dans ces parties, il existe en fait forcément une position où le joueur perdant aurait pu prendre une autre décision, orienter la partie vers une autre branche qui, elle, aurait abouti à un match nul. Les arbres sont formels: dans ce jeu, si l’on joue bien, on ne perd pas. À vous de jouer !