Playing the SOS Game Using Feasible Greedy Strategy
DOI:
https://doi.org/10.21512/commit.v14i1.6167Keywords:
SOS Game, Feasible Greedy Agent, Greedy Strategy, Game TreeAbstract
The research aims to make an intelligent agent that can compete against the human player. In this research, the feasible greedy strategy is proposed to make an intelligent agent by checking all possible solutions in the limited tree levels to find effective movement. Several matches are conducted to evaluate the performance of the feasible greedy agent. The board size for the evaluation consists of 33, 44, 55, 66, 77, and 88 squares. From the result, the feasible greedy agent never loses against the random agent and the pure greedy agent. In 3 3 squares match, the agent can compensate against the human player, so the game always ends with a draw. In 44, 55, 66, 77, and 88 squares matches, the feasible greedy agent slightly outplays the human player.
Plum Analytics
References
T. S. Ferguson, Game theory. Los Angeles: Mathematics Department, UCLA, 2014.
R. J. Gould, Mathematics in games, sports, and gambling: The games people play. Boca Raton: CRC Press, 2015.
E. K. Donkoh, R. Davis, E. D. Owusu-Ansah, E. A. Antwi, and M. Mensah, “Application of combinatorial techniques to the Ghanaian boardgame Zaminamina draft,” European Journal of Pure and Applied Mathematics, vol. 12, no. 1, pp. 159–175, 2019.
D. Keiser and B. McGee, Patterns - Literature, arts, and science. Prufrock Press Inc., 2008.
B. E. Aydin, H. Hagedooren, M. M. Rutten, J. Delsman, G. H. Oude Essink, N. van de Giesen, and E. Abraham, “A greedy algorithm for optimal sensor placement to estimate salinity in polder networks,” Water, vol. 11, no. 5, pp. 1–17, 2019.
Z. Dong, N. Liu, and R. Rojas-Cessa, “Greedy scheduling of tasks with time constraints for energy-efficient cloud-computing data centers,” Journal of Cloud Computing, vol. 4, no. 1, pp. 1–14, 2015.
C. Yang, T. Zheng, Z. Zhao, X. He, X. Zhang, X. Xiao, and J. Wang, “A greedy algorithm for detecting mutually exclusive patterns in cancer mutation data,” in International Work-Conference on Bioinformatics and Biomedical Engineering. Granada, Spain: Springer, May 8–10, 2019, pp. 154–165.
K. Lichy, M. Mazur, J. Stolarek, and P. Lipi´nski, “The use of heuristic algorithms: A case study of a card game,” Journal of Applied Computer Science, vol. 26, no. 2, pp. 107–116, 2018.
I. Toma, C. E. Alexandru, M. Dascalu, P. Dessus, and S. Trausan Matu, “Semantic Boggle: A game for vocabulary acquisition,” in European Conference on Technology Enhanced Learning. Tallinn, Estonia: Springer, Sept. 12–15, 2017, pp. 606–609.
E. Butler, E. Torlak, and Z. Popovi´c, “Synthesizing interpretable strategies for solving puzzle games,” in Proceedings of the 12th International Conference on the Foundations of Digital Games, Hyannis, MA, USA, Aug. 14–17, 2017, pp. 1–10.
R. Garg and D. P. Nayak, “Game of tic-tac-toe: Simulation using Min-Max algorithm,” International Journal of Advanced Research in Computer Science, vol. 8, no. 7, pp. 1074–1077, 2017.
P. Borovska and M. Lazarova, “Efficiency of parallel Minimax algorithm for game tree search,” in CompSysTech ’07: Proceedings of the 2007 international conference on Computer systems and technologies, University of Rousse, Bulgaria, June 14–15, 2007, pp. 1–6.
S. Jain and N. Khera, “An intelligent method forsolving tic-tac-toe problem,” in International Conference on Computing, Communication & Automation. Noida, India: IEEE, May 15–16, 2015, pp. 181–184.
S. Garg and D. Songara, “The winner decision model of tic tac toe game by using multi-tape turing machine,” in 2016 International Conference on Advances in Computing, Communications and Informatics (ICACCI). Jaipur, India: IEEE, Sept. 21–24, 2016, pp. 573–579.
S. Garg, D. Songara, and S. Maheshwari, “The winning strategy of tic tac toe game model by using theoretical computer science,” in 2017 International Conference on Computer, Communications and Electronics (Comptelix). Jaipur, India: IEEE, July 1–2, 2017, pp. 89–95.
D. Draskovic, M. Brzakovic, and B. Nikolic, “A comparison of machine leaming methods using a two player board game,” in IEEE EUROCON 2019-18th International Conference on Smart Technologies. Novi Sad, Serbia: IEEE, July 1–4, 2019, pp. 1–5.
Downloads
Published
Issue
Section
License
Authors who publish with this journal agree to the following terms:
a. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License - Share Alike that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
b. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
c. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
USER RIGHTS
All articles published Open Access will be immediately and permanently free for everyone to read and download. We are continuously working with our author communities to select the best choice of license options, currently being defined for this journal as follows: Creative Commons Attribution-Share Alike (CC BY-SA)
