Strategies and first-absorption times in the random walk game

M. I. Krivonosov ; S. N. Tikhomirov

Izvestiya VUZ. Applied Nonlinear Dynamics, Tome 31 (2023) no. 3, pp. 334-350

Résumé

Purpose of this work is to determine the average time to reach the boundaries, as well as to identify the strategy in the game between two players, controlling point movements on the finite square lattice using an independent choice of strategies. One player wants to survive, i. e., to stay within the interior of the square, as long as possible, while his opponent wants to reach the absorbing boundary. A game starts from the center of the square and every next movement of the point is determined by independent strategy choices made by the players. The value of the game is the survival time that is the number of steps before the absorption happens. In addition we present series of experiments involving both human players and an autonomous agent (bot) and analysis of the survival time probability distributions. Methods. In this work, methods of the theory of absorbing Markov chains were used to analyze strategies and absorption times, as well as the Monte Carlo method to simulate trajectories. Additionally, a large-scale field experiment was conducted using the developed mobile application. Results. The players’ strategies are experimentally obtained for the cases of playing against an autonomous agent (bot), as well as human players against each other. A comparison with optimal strategies and a random walk is made: the difference between the experimental strategies and the optimal ones is shown, however, the resulting strategies show a much better result of games than a simple random walk. In addition, especially long-running games do not show the Markovian property in case of the simulation corresponding strategies. Conclusion. The sampled histograms indicate that the game-driven walks are more complex than a random walk on a finite lattice but it can be reproduced with a Markov Chain model

Détail

Keywords: random walk, markov chain, random walk game, mobile application, game experiment.