2017/04/15 by Sylvain Delattre, Delattre, Sylvain, Nicolas Fournier +1 · 1 citation
Computer Science · Economics, Econometrics and Finance · Mathematics · #60J80 #68T20 #91A05 #Artificial Intelligence in Games #FOS: Mathematics #Probability (math.PR) #Probability and Statistical Research #Sports Analytics and Performance
paper · pdf · doi:10.48550/arxiv.1704.04612
openalex publication_date 2017/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a deterministic game with alternate moves and complete\ninformation, of which the issue is always the victory of one of the two\nopponents. We assume that this game is the realization of a random model\nenjoying some independence properties. We consider algorithms in the spirit of\nMonte-Carlo Tree Search, to estimate at best the minimax value of a given\nposition: it consists in simulating, successively, n well-chosen matches,\nstarting from this position. We build an algorithm, which is optimal, step by\nstep, in some sense: once the n first matches are simulated, the algorithm\ndecides from the statistics furnished by the n first matches (and the a\npriori we have on the game) how to simulate the (n+1)-th match in such a way\nthat the increase of information concerning the minimax value of the position\nunder study is maximal. This algorithm is remarkably quick. We prove that our\nstep by step optimal algorithm is not globally optimal and that it always\nconverges in a finite number of steps, even if the a priori we have on the game\nis completely irrelevant. We finally test our algorithm, against MCTS, on\nPearl's game and, with a very simple and universal a priori, on the games\nConnect Four and some variants. The numerical results are rather disappointing.\nWe however exhibit some situations in which our algorithm seems efficient.\n