Analysis of Game Tree Search Algorithms Using Minimax Algorithm and Alpha-Beta Pruning
DOI:
https://doi.org/10.32628/CSEIT1228644Keywords:
Minimax algorithm, Alpha-beta pruning, Two-Player games, Game Theory, Game Tree Search Algorithms.Abstract
An important topic of research in computer systems is the optimization of finding the optimum course of action based on different variables, such as the environment's state, the system's goal, etc. The building of the entire state search space, also known as the minimax algorithm, can result from any search algorithm's attempt to find the best feasible solution from among all known possibilities. The recursive backtracking algorithm known as Minimax is used to select the next action in a game of strategy for two players. The algorithm works well because it anticipates that your adversary will play well as well. However, as the tree's depth increases, we observe that minimax frequently investigates repetitive and unlikely situations. We'll also take a look at the minimax extension known as alpha-beta pruning, which prohibits us from considering states that won't be chosen. We will also examine a number of established techniques for resolving two-player games, such as adversarial search and other machine learning-based techniques.
References
- Pranav G., Satvik M., Neeta P. “Realization of Game Tree Search Algorithms on FPGA: A Comparative Study”, 2019 International Conference on Issues and Challenges in Intelligent Computing Techniques (ICICT), 2019, pp. 1-3.
- Shubhendra P. S., M. Sridevi. “Comparative study of performance of parallel alpha Beta Pruning for different architectures” 2019 IEEE 9th International Conference on Advanced Computing (IACC), 2019, pp. 115-119.
- Maciej Świechowski, Konrad Godlewski, Bartosz Sawicki, Jacek Mańdziuk. “Monte Carlo Tree Search: a review of recent modifcations and applications” Artif Intell Rev (2022) 10462-022-10228.
- S. Ariyurek, A. Betin-Can and E. Surer, "Enhancing the Monte Carlo Tree Search Algorithm for Video Game Testing," 2020 IEEE Conference on Games (CoG), 2020, pp. 25-32.
Downloads
Published
Issue
Section
License
Copyright (c) IJSRCSEIT

This work is licensed under a Creative Commons Attribution 4.0 International License.