MVPA and GA Comparison for State Space Optimization at Classic Tetris Game Agent Problem

  • Hendrawan Armanto 3Computer Science Department, Institut Sains dan Teknologi Terpadu Surabaya
  • Ronal Dwi Putra Computer Science Department, Institut Sains dan Teknologi Terpadu Surabaya
  • C. Pickerling Computer Science Department, Institut Sains dan Teknologi Terpadu Surabaya
https://doi.org/10.25139/inform.v7i1.4457
Abstract views: 175 , PDF downloads: 154
Keywords: Tetris, Artificial Intelligence, GA, Most Valuable Player Algorithm

Abstract

Tetris is one of those games that looks simple and easy to play. Although it seems simple, this game requires strategy and continuous practice to get the best score. This is also what makes Tetris often used as research material, especially research in artificial intelligence. These various studies have been carried out. Starting from applying state-space to reinforcement learning, one of the biggest obstacles of these studies is time. It takes a long to train artificial intelligence to play like a Tetris game expert. Seeing this, in this study,  apply the Genetic Algorithms (GA) and the most valuable player (MVPA) algorithm to optimize state-space training so that artificial intelligence (agents) can play like an expert. The optimization means in this research is to find the best weight in the state space with the minimum possible training time to play Tetris with the highest possible value. The experiment results show that GAs and MVPA are very effective in optimizing the state space in the Tetris game. The MVPA algorithm is also faster in finding solutions. The resulting state space weight can also get a higher value than the GA (MVPA value is 249 million, while the GA value is 68 million).

References

[1] D. Ackerman, The Tetris Effect: The Cold War Battle for the World's Most Addictive Game. Oneworld Publications, 2016.
[2] W. Books, Summary, and Analysis of The Tetris Effect: The Game that Hypnotized the World: Based on the Book by Dan Ackerman. Worth Books, 2017.
[3] E. D. Demaine, S. Hohenberger, and D. Liben-Nowell, "Tetris is Hard, Even to Approximate," Oct. 2002.
[4] S. Asif et al., "Tetris are NP-hard even with $O(1)$ rows or columns," Sep. 2020.
[5] G. Moore, Tetris Puzzles. Portable Press, 2019.
[6] B. Brown, Tetris: The Games People Play. First Second, 2016.
[7] V. Gabillon, M. Ghavamzadeh, and B. Scherrer, "Approximate Dynamic Programming Finally Perform Well in the Game of Tetris," in NIPS, 2013, pp. 1754–1762.
[8] G. Hendriks, "The effect of state representation in reinforcement learning applied to Tetris," University of Groningen, 2020.
[9] N. Bohm, G. Kokai, and S. Mandl, "MIC2005: The Sixth Metaheuristics International Conference - An Evolutionary Approach to Tetris," 2005.
[10] A. Boumaza, "On the evolution of artificial Tetris players," in The IEEE Symposium on Computational Intelligence and Games, Sep. 2009, pp. 387–393, [Online]. Available: https://hal.archives-ouvertes.fr/hal-00397045.
[11] S. Phon-Amnuaisuk, "Evolving and Discovering Tetris Gameplay Strategies," Procedia Comput. Sci., vol. 60, pp. 458–467, 2015, doi: 10.1016/j.procs.2015.08.167.
[12] S. Algorta and Ö. Şimşek, “The Game of Tetris in Machine Learning,” May 2019.
[13] A. Boumaza, "How to design good Tetris players," 2013. [Online]. Available: https://hal.inria.fr/hal-00926213.
[14] Ii Romero, M. Romero, L. Tomes, J. P. Yusiong, and T. Yusiong, "Tetris Agent Optimization Using Harmony Search Algorithm," Int. J. Comput. Sci. Issues, vol. 8, Nov. 2011.
[15] K. F. Man, K. S. Tang, and S. Kwong, "GAs: concepts and applications [in engineering design]," IEEE Trans. Ind. Electron., vol. 43, no. 5, pp. 519–534, 1996, doi: 10.1109/41.538609.
[16] R. R. L. Haldurai T. Madhubala, "A Study on GA and its Applications," Int. J. Comput. Sci. Eng., vol. 4, no. 10, pp. 139–143, Nov. 2016, [Online]. Available: https://www.ijcseonline.org/full_paper_view.php?paper_id=1092.
[17] S. M. Elsayed, R. A. Sarker, and D. L. Essam, "A new GA for solving optimization problems," Eng. Appl. Artif. Intell., vol. 27, pp. 57–69, Jan. 2014, doi: 10.1016/j.engappai.2013.09.013.
[18] H. R. E. H. Bouchekara, "Most Valuable Player Algorithm: a novel optimization algorithm inspired from sport," Oper. Res., vol. 20, no. 1, pp. 139–195, Mar. 2020, doi: 10.1007/s12351-017-0320-y.
[19] I. Pervez, I. Shams, S. Mekhilef, A. Sarwar, M. Tariq, and B. Alamri, "Most Valuable Player Algorithm based Maximum Power Point Tracking for a Partially Shaded PV Generation System," IEEE Trans. Sustain. Energy, vol. 12, no. 4, pp. 1876–1890, 2021, doi: 10.1109/TSTE.2021.3069262.
[20] S. Shanmugapriya and D. Maharajan, "Most Valuable Player Algorithm Based State Estimation for Energy Systems," Distrib. Gener. Altern. Energy J., Apr. 2021, doi: 10.13052/dgaej2156-3306.3543.
[21] H. R. E.-H. Bouchekara, A. Orlandi, M. Al-Qdah, and F. de Paulis, "Notice of Retraction: Most Valuable Player Algorithm for Circular Antenna Arrays Optimization to Maximum Sidelobe Levels Reduction," IEEE Trans. Electromagn. Compatibility., vol. 60, no. 6, pp. 1655–1661, 2018, doi: 10.1109/TEMC.2018.2800774.
Published
2022-01-24
How to Cite
Armanto, H., Ronal Dwi Putra, & C. Pickerling. (2022). MVPA and GA Comparison for State Space Optimization at Classic Tetris Game Agent Problem. Inform : Jurnal Ilmiah Bidang Teknologi Informasi Dan Komunikasi, 7(1), 73-80. https://doi.org/10.25139/inform.v7i1.4457
Issue
Vol. 7 No. 1 (2022)
Section
Articles

Copyright (c) 2022 Hendrawan Armanto, Ronal Dwi Putra, C. Pickerling

Creative Commons License

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

Authors who publish with Inform: Jurnal Ilmiah Bidang Teknologi Informasi dan Komunikasi agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. 

  2. 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.

  3. 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.