IA: Comment se faire battre par sa propre création
Lorsque j’ai rejoint Marmelab, comme tous les nouveaux arrivants, j’ai eu le droit à un processus d’intégration agile (voir cet article pour plus de détails sur l'intégration). Avec mon partenaire d’intégration, Antoine, nous avons planché sur le jeu Abalone.
Dans cet article, je vais décrire la démarche que nous avons appliquée lors du dernier sprint. Celui-ci consistait à développer un algorithme capable de jouer à Abalone. Pour que l’intégration soit une réussite, notre algorithme devait réussir à battre l’ensemble des développeurs de Marmelab, un sacré challenge donc !
Règles du jeu
Commençons par un rapide rappel des règles de ce jeu de billes. Le but est de placer 6 billes de l’adversaire en dehors du plateau. Durant un tour, il y a plusieurs déplacements possibles :
- Déplacer une bille dans une case adjacente libre
- Déplacer un groupe de 2 ou 3 billes alignées en avant ou en arrière dans le sens de l’alignement
- Déplacer latéralement un groupe de 2 ou 3 billes alignées si toutes les cases adjacentes sont libres
Pour pousser les billes de l’adversaire lors d’un déplacement en ligne, il faut obligatoirement être en supériorité numérique par rapport à l’adversaire.
Évaluer un état de jeu
Afin que notre algorithme puisse définir quel est la meilleure action possible, la première chose à faire est de pouvoir évaluer si un état de jeu est favorable ou non. Pour cela, nous nous sommes appuyés sur quelques heuristiques.
Distance au centre
D’abord, si nos billes sont concentrées au centre du plateau, il sera plus difficile pour l’adversaire de les sortir du jeu. Une première manière d’évaluer un état de jeu est donc de calculer la distance des billes par rapport au centre et d’en faire la moyenne. Plus la moyenne sera petite, plus les billes seront proches du centre.
Par exemple, on peut comparer les moyennes calculées pour les deux états de jeux ci-dessous. Le chiffre dans chaque case évalue la distance de cette case au centre.
Densité des billes
Une autre manière de définir si un plateau de jeu donné est favorable ou non est de définir le taux de densité des billes. En effet, plus nos billes sont regroupées, plus nous aurons de possibilité d’être en supériorité numérique pour pousser des billes de l’adversaire.
Pour chaque bille, nous calculons la moyenne des distances avec toutes les autres billes de la même couleur, puis nous calculons la moyenne des moyennes précédemment calculées.
Par exemple, on peut comparer les moyennes calculées pour les deux états de jeux ci-dessous.
Score total
Après avoir défini les deux heuristiques présentées ci-dessus, il faut les combiner pour déterminer un score global pour un état de jeu. Pour également prendre en compte le positionnement des billes de l’adversaire, nous pouvons y intégrer le calcul de la distance au centre et de densité appliqués aux billes de l’adversaire.
Après réflexion, il semble également judicieux d’intégrer le nombre de billes sorties afin d’avoir un meilleur score lorsque nous avons peu de nos billes sorties et beaucoup de billes de l’adversaire sorties.
Pour obtenir le score global, nous combinons les différentes données en les pondérant avec des facteurs que nous ajusterons ensuite lors des tests.
Est-ce que cette approche assez simple suffit pour programmer une IA passable ? Il n'y a qu'une seule façon de le savoir : essayons !
Modéliser le plateau de jeu
La principale difficulté pour calculer la distance entre une bille et le centre provient de la forme du plateau d’Abalone qui est hexagonale.
Pour simplifier, il est possible de le modéliser sous forme d’un tableau en 2 dimensions, un tableau "étiré" et dont les "coins" sont vides :
Avec cette modélisation de plateau, nous pouvons écrire une fonction utilitaire permettant de calculer la distance entre deux positions du plateau :
export const distanceBetween = (start: Coordinate, end: Coordinate): number => {
return Math.max(
Math.abs(start.x - end.x),
Math.abs(start.y - end.y),
Math.abs(start.x - end.x + start.y - end.y),
);
};Calcul de la moyenne des distances au centre
Pour appliquer la première heuristique, il faut maintenant parcourir le plateau de jeu pour déterminer la distance au centre de chacune des billes du joueur et retourner la moyenne :
/**
* Computes an advantage score for the given player preferring positions close to center board node.
* @returns advantage score (the lower the better)
*/
export const computeCenterScore = (
gameBoard: Board,
player: Player,
): number => {
const boardLength = gameBoard.length;
const center: Coordinate = {
x: Math.floor(boardLength / 2),
y: Math.floor(boardLength / 2),
};
let sumScore = 0;
let marbleCounter = 0;
for (let i = 0; i < boardLength; i++) {
for (let j = 0; j < boardLength; j++) {
if (gameBoard[i][j] === player) {
const currentNode: Coordinate = { x: j, y: i };
const marbleScore = distanceBetween(currentNode, center);
sumScore += marbleScore;
marbleCounter++;
}
}
}
return sumScore / marbleCounter;
};Calcul de la moyenne de la distance entre les billes
Pour la seconde heuristique, nous pouvons de nouveau parcourir le plateau et, pour chaque bille, réutiliser notre fonction permettant de calculer la distance entre deux billes :
/**
* Computes an advantage score for the given player preferring marble grouped patterns to spread ones.
* @returns advantage score (the lower the better)
*/
export const computeDensityScore = (
gameBoard: Board,
player: Player,
graph?: Graph,
): number => {
if (!graph) graph = createGraphFromBoard(gameBoard);
const { nodes } = graph;
const len = gameBoard.length;
const nodesProps: GraphNode[] = Object.values(nodes);
const nodesPropsLen = nodesProps.length;
let sumScore = 0;
let marbleCounter = 0;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
if (gameBoard[i][j] === player) {
const currentNode: Coordinate = { x: j, y: i };
let distantMarbleCounter = 0;
let marbleSum = 0;
for (let k = 0; k < nodesPropsLen; ++k) {
const node = nodesProps[k];
if (
node.value === player &&
!(node.x === j && node.y === i)
) {
distantMarbleCounter++;
marbleSum += distanceBetween(currentNode, node);
}
}
const marbleScore = marbleSum / distantMarbleCounter;
sumScore += marbleScore;
marbleCounter++;
}
}
}
return sumScore / marbleCounter;
};Calcul du score d'une configuration donnée
Le score global est donc relativement simple : c'est une combinaison linéaire des scores des deux heuristiques pour l'un et l'autre joueur, ainsi que du nombre de billes expulsées :
export const getScore = (state: GameState, player: Player): number => {
const opponent = player === PLAYER_1 ? PLAYER_2 : PLAYER_1;
const playerCenterScore = computeCenterScore(state.board, player);
const opponentCenterScore = computeCenterScore(state.board, opponent);
const playerDensityScore = computeDensityScore(
state.board,
player,
state.graph,
);
const opponentDensityScore = computeDensityScore(
state.board,
opponent,
state.graph,
);
const playerMarblesOut = state[`player${player}MarblesOut`];
const opponentMarblesOut = state[`player${opponent}MarblesOut`];
const score =
OPPONENT_CENTER_SCORE_FACTOR * opponentCenterScore +
OPPONENT_DENSITY_SCORE_FACTOR * opponentDensityScore +
OPPONENT_MARBLE_SCORE_FACTOR * opponentMarblesOut -
PLAYER_CENTER_SCORE_FACTOR * playerCenterScore -
PLAYER_DENSITY_SCORE_FACTOR * playerDensityScore -
PLAYER_MARBLE_SCORE_FACTOR * playerMarblesOut;
return score;
};Quel score donner aux constantes ci-dessus ? On peut commencer par leur donner une valeur aléatoire et ajuster en fonction du style de jeu constaté. Nous en reparlerons un peu plus loin.
L'algorithme Minimax
Pour déterminer le meilleur coup possible en prenant en compte les mouvements que va réaliser l’adversaire, nous avons implémenté l’algorithme Minimax. Cet algorithme parcourt l’arbre des possibilités de jeu pour chaque tour en maximisant le score du joueur et en minimisant le score de l’adversaire :
const minmax = (
node: MovementNode,
gameState: GameState,
currentPlayer: Player,
maximizing: boolean,
curentDepth: number,
maxDepth: number,
): MovementNode => {
if (curentDepth >= maxDepth) {
evaluatedNodes++;
node.score = getScore(gameState, currentPlayer);
return node;
}
let limitScore = maximizing
? Number.NEGATIVE_INFINITY
: Number.POSITIVE_INFINITY;
let limitNode: MovementNode = {
score: limitScore,
direction: null,
subject: null,
};
const movements: Movement[] = getMovements(
gameState.board,
currentPlayer,
false,
gameState.graph,
);
const movementsLen = movements.length;
for (let i = 0; i < movementsLen; ++i) {
const movement: Movement = movements[i];
const { direction, subject } = movement;
const childNode: MovementNode = {
score: null,
direction,
subject,
} as MovementNode;
minmax(
childNode,
getNextState(gameState, movement),
getOpponent(currentPlayer),
!maximizing,
curentDepth + 1,
maxDepth,
);
if (maximizing) {
if (childNode.score > limitScore) {
limitScore = childNode.score;
limitNode = childNode;
}
} else {
if (childNode.score < limitScore) {
limitScore = childNode.score;
limitNode = childNode;
}
}
}
node.score = limitNode.score;
return limitNode;
};Élagage alpha-bêta
En appliquant cet algorithme au jeu d’Abalone, nous faisons rapidement face à un problème de performance. En effet, pour une situation de jeu donnée, le nombre de mouvements possibles est important. Le nombre de noeuds à évaluer par l’algorithme augmente donc de manière exponentielle lorsqu’on descend dans l’arbre.
Par exemple, pour la situation de jeu visible ci-dessous, nous avons déjà 75 mouvements possibles :
On peut voir ci-dessous qu’en passant d’une exploration de l’arbre du niveau 2 au niveau 3, on passe également de 5813 noeuds explorés en environ 1,5 secondes à 436647 noeuds évalués en plus d’une minute.
Pour réduire le nombre de noeuds évalués, il existe une stratégie appelé l’élagage alpha-bêta. Concrètement, il s’agit de ne pas descendre en profondeur sur les noeuds dont on sait déjà que leurs enfants ne feront pas partie des résultats optimaux. Cela donne la modification ci-dessous de notre algorithme minmax :
const minmax = (
node: MovementNode,
gameState: GameState,
currentPlayer: Player,
alpha: number,
beta: number,
maximizing: boolean,
curentDepth: number,
maxDepth: number,
): MovementNode => {
if (curentDepth >= maxDepth) {
evaluatedNodes++;
node.score = getScore(gameState, currentPlayer);
return node;
}
let limitScore: number = maximizing
? Number.NEGATIVE_INFINITY
: Number.POSITIVE_INFINITY;
let limitNode: MovementNode = {
score: limitScore,
direction: null,
subject: null,
};
const movements: Movement[] = getMovements(
gameState.board,
currentPlayer,
false,
gameState.graph,
);
const movementsLen: number = movements.length;
for (let i: number = 0; i < movementsLen; ++i) {
const movement: Movement = movements[i];
const { direction, subject } = movement;
const childNode: MovementNode = {
score: null,
direction,
subject,
} as MovementNode;
minmax(
childNode,
getNextState(gameState, movement),
getOpponent(currentPlayer),
alpha,
beta,
!maximizing,
curentDepth + 1,
maxDepth,
);
if (maximizing) {
if (childNode.score > limitScore) {
limitScore = childNode.score;
limitNode = childNode;
}
if (childNode.score > alpha) alpha = childNode.score;
} else {
if (childNode.score < limitScore) {
limitScore = childNode.score;
limitNode = childNode;
}
if (childNode.score < beta) beta = childNode.score;
}
if (beta <= alpha) break;
}
node.score = limitNode.score;
return limitNode;
};On peut voir ci-dessous la différence pour le niveau 3 puisque notre algorithme évalue maintenant 27139 noeuds en environ 7 secondes pour arriver au même résultat.
Optimisation des paramètres
Maintenant que nous avons un algorithme permettant de calculer le meilleur coup dans un temps raisonnable, n’oublions pas notre objectif initial de créer une IA imbattable ! Pour cela, il faut trouver les paramètres optimaux de notre fonction d’évaluation.
Pour nous faciliter la tâche, nous avons développé un petit script permettant de se faire affronter pendant un certain nombre d’itérations deux IA dont une avec des facteurs générés aléatoirement et l’autre avec les facteurs vainqueurs des dernières itérations.
Après 100 itérations, ce sont les facteurs visibles ci-dessous qui ont gagné la dernière partie. Nous les avons donc implémenté dans notre IA.
Cela correspond à une stratégie plutôt défensive puisque l'IA va privilégier les coups qui lui permettent de ne pas perdre de billes et d'avoir une densité de billes la plus élevée possible tout en cherchant à éloigner son adversaire du centre.
On peut voir dans le screencast ci-dessous qu'elle perd certaines occasions de sortir des billes de son adversaire pour ne pas éparpiller ses billes. En revanche, il est quasiment impossible de réussir à faire sortir une bille de l'IA.
Conclusion
Ces 5 semaines d'intégration ont été très intenses et m'ont notamment permis de découvrir de nouvelles méthodes de travail. Nous savions dès le début que l'objectif final était de créer une IA qui saurait jouer, mais n'avions aucune idée du chemin à suivre pour y arriver.
Finalement, en y allant progressivement par différentes étapes et en appliquant les principes de la méthode agile utilisée chez Marmelab, nous avons réussi à atteindre notre objectif qui semblait pourtant inatteignable au début. Grâce à une présence constante de nos "coaches" technique et produit, et à un travail en binôme efficace, nous avons créé un programme plus fort que nous.
Pour aller plus loin, le code source du projet est disponible sur GitHub.
