Minimax avec élagage alpha-bêta sur un véritable arbre de jeu, plus un solveur d’équilibres pour petits jeux sous forme normale : le jeu optimal contre un adversaire, et contre un joueur rationnel.
Deux volets complémentaires du raisonnement stratégique dans un même code. Le premier est un moteur complet de recherche adverse : minimax sur un arbre de jeu, élagage alpha-bêta, limitation de profondeur et fonction d’évaluation heuristique, instrumenté pour rapporter combien de nœuds l’élagage supprime réellement, afin que le lecteur observe le gain au lieu qu’on le lui affirme. Le second est un solveur pour petits jeux sous forme normale, qui trouve les équilibres en stratégies pures et mixtes, appliqué aux cas classiques - dilemme du prisonnier, pile ou face, jeux de coordination - où l’équilibre et l’issue collectivement préférable divergent. Ensemble, ils couvrent les deux régimes que distinguent les articles : le jeu strictement opposé, où minimax suffit, et le jeu partiellement aligné, où il ne suffit plus. L’implémentation est en cours et aucun dépôt source n’a encore été publié.
How a program plays a game against an opponent who is trying to beat it: the minimax value, why alpha-beta pruning reaches the same answer while examining fewer nodes, and a game tree pruned move by move.
Strategic reasoning when players are not strictly opposed: dominant strategies, the prisoner's dilemma worked from its payoff matrix, Nash equilibrium, Pareto optimality, and why equilibrium and efficiency can conflict.