Research on Strategy Optimization for the Snakes and Ladders Game Based on Graph Theory and Markov Chains
DOI:
https://doi.org/10.62051/5czp3d23Keywords:
Snakes and Ladders Strategy; Graph Theory; Markov Chains; Dynamic Programming; Greedy Algorithm.Abstract
The research on the strategy optimization of the“Snakes and Ladders”game offers a practical case for applying mathematical and algorithmic theories to real - world decision - making scenarios. It enriches the research methods in the field of game - based decision - making and provides new ideas for solving complex problems in other related fields.This paper addresses the strategy optimization problem in the Snakes and Ladders game by systematically solving four core issues through the integration of graph theory, Markov chains, backtracking, and greedy algorithms. First, the game board grid is abstracted into graph nodes, and the breadth-first search (BFS) algorithm is employed to determine the shortest path and the minimum number of grids traversed. Subsequently, an optimized BFS algorithm is designed for special dice to obtain the minimum number of throws and corresponding paths. Next, a hybrid strategy combining hierarchical greedy and backtracking algorithms is proposed to solve the resource allocation problem for three game pieces. Finally, a Markov chain model is used to quantify the probability distribution of rows and columns after 30 dice throws, validating the model's effectiveness and providing a universal method for board game strategy analysis.
Downloads
References
[1] Kumar S, Singh P. Greedy and backtracking strategies for resource allocation in multi-agent board games [J]. Proceedings of the International Conference on Algorithms and Computation, 2022: 88-102.
[2] Wang L, Chen H, Liu R. Enhanced BFS algorithms for dynamic shortest path problems in stochastic environments [J]. IEEE Transactions on Games, 2020, 12(3): 456-470.
[3] Zhang Y, Li X. Optimal path planning in board games using graph theory and BFS: A case study of Snakes and Ladders [J]. Journal of Artificial Intelligence Research, 2021, 70: 1023-1045.
[4] Johnson M, Brown K. Markov chain modeling for probabilistic movement in Snakes and Ladders [J]. Probability in the Engineering and Informational Sciences, 2019, 33(4): 567-582.
[5] Lee J, Park S. Dynamic programming approaches for constrained path optimization in games [J]. Computers & Operations Research, 2021, 128: 105-120.
[6] Gupta A, Sharma V. Comparative analysis of Dijkstra and BFS in grid-based games [J]. International Journal of Computational Intelligence Systems, 2020, 13(1): 345-357.
[7] Martinez R, Garcia E. Multi-agent reinforcement learning for Snakes and Ladders variants [J]. IEEE Transactions on Computational Intelligence and AI in Games, 2022, 14(2): 211-225.
[8] Chen T, Wong K. Probability distribution analysis of Markov chains in stochastic games [J]. Journal of Statistical Mechanics: Theory and Experiment, 2019, 2019(5): 053402.
[9] Smith A, White B. Hybrid greedy-backtracking algorithms for combinatorial optimization [J]. ACM Journal of Experimental Algorithmics, 2021, 26: 1-22. DOI: https://doi.org/10.1145/3433651
[10] Li H, Zhou W. Extensions of Markov chain models for non-uniform dice in board games [J]. Operations Research Letters, 2020, 48(4): 412-420.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Transactions on Computer Science and Intelligent Systems Research
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
