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
Abstract views: 161 , PDF downloads: 131
Keywords: Tetris, Artificial Intelligence, GA, Most Valuable Player Algorithm


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


[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:
[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:
[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:
[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.
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.