Morpion Invincible - 2/6 - La modélisation du jeu

Lien vers le repo du projet : https://github.com/vohorgeez/Morpion-invincible

Avant même d'imaginer la moindre ligne d'intelligence artificielle, il faut répondre à une question banale en apparence : comment représenter un jeu dans la mémoire d'un ordinateur ?

C'est bien simple : on ne peut pas parler d'algorithme sans d'abord répondre à cette question fondamentale.

Représenter l'espace de jeu

Un plateau de morpion, c'est un grille 3x3 - soit 9 cases. La tentation naturelle, c'est la matrice :

[[0, 1, 2],
[3, 4, 5],
[6, 7, 8]]

Visuellement intuitif. Mais elle a tendance à compliquer le reste : en effet, accéder à une case demande deux indices, parcourir la grille demande deux boucles imbriquées, et passer le plateau en paramètre devient vite verbeux.

La liste plate est plus simple :

board = [" ", " ", " ", " ", " ", " ", " ", " ", " "]
#         0    1    2    3    4    5    6    7    8

Une seule dimension, un seul indice. Et les patterns de victoire ? De simples triplets d'indices que l'on regroupe au même endroit :

WIN_PATTERNS = [
	[0, 1, 2], [3, 4, 5], [6, 7, 8],	# lignes
	[0, 3, 6], [1, 4, 7], [2, 5, 8],	# colonnes
	[0, 4, 8], [2, 4, 6]				# diagonales
]

Lisible, direct, facile à tester.

Les données constantes plutôt que des chaînes magiques

On pourrait écrire `"X"` et `"O"` partout dans le code. Ce n'est pas vraiment une bonne pratique : on ne se met pas à l'abri des fautes de frappes, et on pleure si un jour on veut changer de symbole. Même s'il y a fort peu de risque que cela arrive, autant prendre de bonnes habitudes.

HUMAN = "O"
AI = "X"
EMPTY = " "

Trois constantes. Maintenant, le code parle de lui-même, et changer de représentation interne ne demande qu'une seule modification.

Les règles métier

Un jeu, c'est un état + des transitions. Les transitions, ce sont les règles.

Coup valide

def is_valid_move(board, index):
	return board[index]

Coups disponibles

def get_available_moves(board):
	return [i for i in range(9) if board[i] == EMPTY]

Victoire

def has_won(board, player):
	return any(
		all(board[i] == player for i in pattern)
		for pattern in WIN_PATTERNS
	)

Plateau plein

def is_full(board):
	return EMPTY not in board

Etat terminal (la composition des deux)

def is_terminal(board):
	return has_won(board, HUMAN) or has_won(board, AI) or is_full(board)

`is_terminal()` est la fonction clé. C'est elle que l'algorithme appellera à chaque noeud de son arbre de décision - mais ça c'est le sujet du prochain article.

Et voilà

On a traduit un jeu de société en structures de données manipulables. Pas de magie : une liste, des constantes, cinq fonctions.

C'est cette base qui rend le reste possible. Un minimax sans modèle propre, c'est un colosse aux pieds d'argile (quel sens de la formule).