Playing NES Tetris with No Piece Rotations
Resumo
Tetris is one of the highest-grossing video games in all history and, despite of its age, remains quite popular. One of its most acclaimed versions was released in 1989 for the Nintendo Entertainment System (NES) and is often referred to as NES Tetris. This particular version of the game has led to the creation of the Classic Tetris World Championship (CTWC), resulting in growing popularity and alternative modes of gameplay. In one of such variants, players aim to clear as many lines as possible, with an additional constraint: piece rotations are not allowed. In this work we build and evaluate agents to play this particular variant of the game based on different metrics that grade board configurations. The relative importance of metrics is determined with the Particle Swarm Optimization. Our best results match those of top performing human players, even though the metrics we employ were not specifically developed for this game variant.
Palavras-chave:
Tetris, NES Tetris, Heuristics, Metrics, PSO
Referências
Wikipedia Contributors, “Tetris Effect.” Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/wiki/Tetris Effect. Accessed: Jul. 10, 2021.
M. Birken, “Applying artificial intelligence to handicapping NES Tetris.” Meat Fighter, Aug. 17, 2019. https://meatfighter.com/handicappedtetris/. Accessed: Jul. 10, 2021.
J. Kennedy and R. Eberhart, “Particle swarm optimization.” in Proceedings of ICNN’95 - International Conference on Neural Networks, vol. 4, 1995, pp. 1942–1948.
D. Macdonald, “World Record Progression: NES Tetris No Piece Rotation.” Sep. 24, 2020. Accessed: Jul. 10, 2021. [Online Video]. Available: https://youtu.be/yHqIdICC5wQ.
Z. Bereczki, “NES Tetris no rotation lvl0 start 44 lines [World Record].” Jan. 07, 2021. Accessed: Jul. 10, 2021. [Online Video]. Available: https://youtu.be/4ua79-J4D5E.
F. Colin, “Tetris.” Colin Fahey. https://colinfahey.com/tetris/tetris.html. Acessed: Jul. 10, 2021.
S. Algorta and Ö. Simsek, “The game of tetris in machine learning,” pp. 1–7, 2019. [Online]. Available: http://arxiv.org/abs/1905.01652.
C. Thiery and B. Scherrer, “Improvements on learning tetris with cross entropy,” International Computer Games Association Journal, vol. 32, pp. 23 – 33, 2009.
N. Böhm, G. Kókai, and S. Mandl, “An evolutionary approach to tetris,” in The Sixth Metaheuristics International Conference, 2005, pp. 1–6.
J. Saelee, “First Ever Level 34 in NES Tetris.” (Feb. 16, 2020), Accessed: Jul. 10, 2021. [Online Video]. Available: https://youtu.be/rWMUYBinriw.
G. Da Col and E. C. Teppan, “Heuristic Search for Tetris: A Case Study.” in Intelligent Computing, K. Arai, R. Bhatia, and S. Kapoor, Eds. Cham: Springer International Publishing, 2019, pp. 410–423.
R. Poli, J. Kennedy, and T. Blackwell, “Particle swarm optimization: An overview,” Swarm Intelligence, vol. 1, pp. 33–54, 2007.
H. ling Chen, B. Yang, S. jing Wang, G. Wang, D. you Liu, H. zhong Li, and W. bin Liu, “Towards an optimal support vector machine classifier using a parallel particle swarm optimization strategy,” Applied Mathematics and Computation, vol. 239, pp. 180–197, 2014.
Nintaco. (2020). Michael Birken. Acessed: Jul. 10, 2021. [Online]. Available: https://nintaco.com/.
A. Wu, “No-Rotation Tetris AI.” 2020, Github: Adrien Wu, 2020. https://github.com/adrien1018/noro-tetris-ai. Accessed: Jul. 10, 2021.
M. Birken, “Applying artificial intelligence to handicapping NES Tetris.” Meat Fighter, Aug. 17, 2019. https://meatfighter.com/handicappedtetris/. Accessed: Jul. 10, 2021.
J. Kennedy and R. Eberhart, “Particle swarm optimization.” in Proceedings of ICNN’95 - International Conference on Neural Networks, vol. 4, 1995, pp. 1942–1948.
D. Macdonald, “World Record Progression: NES Tetris No Piece Rotation.” Sep. 24, 2020. Accessed: Jul. 10, 2021. [Online Video]. Available: https://youtu.be/yHqIdICC5wQ.
Z. Bereczki, “NES Tetris no rotation lvl0 start 44 lines [World Record].” Jan. 07, 2021. Accessed: Jul. 10, 2021. [Online Video]. Available: https://youtu.be/4ua79-J4D5E.
F. Colin, “Tetris.” Colin Fahey. https://colinfahey.com/tetris/tetris.html. Acessed: Jul. 10, 2021.
S. Algorta and Ö. Simsek, “The game of tetris in machine learning,” pp. 1–7, 2019. [Online]. Available: http://arxiv.org/abs/1905.01652.
C. Thiery and B. Scherrer, “Improvements on learning tetris with cross entropy,” International Computer Games Association Journal, vol. 32, pp. 23 – 33, 2009.
N. Böhm, G. Kókai, and S. Mandl, “An evolutionary approach to tetris,” in The Sixth Metaheuristics International Conference, 2005, pp. 1–6.
J. Saelee, “First Ever Level 34 in NES Tetris.” (Feb. 16, 2020), Accessed: Jul. 10, 2021. [Online Video]. Available: https://youtu.be/rWMUYBinriw.
G. Da Col and E. C. Teppan, “Heuristic Search for Tetris: A Case Study.” in Intelligent Computing, K. Arai, R. Bhatia, and S. Kapoor, Eds. Cham: Springer International Publishing, 2019, pp. 410–423.
R. Poli, J. Kennedy, and T. Blackwell, “Particle swarm optimization: An overview,” Swarm Intelligence, vol. 1, pp. 33–54, 2007.
H. ling Chen, B. Yang, S. jing Wang, G. Wang, D. you Liu, H. zhong Li, and W. bin Liu, “Towards an optimal support vector machine classifier using a parallel particle swarm optimization strategy,” Applied Mathematics and Computation, vol. 239, pp. 180–197, 2014.
Nintaco. (2020). Michael Birken. Acessed: Jul. 10, 2021. [Online]. Available: https://nintaco.com/.
A. Wu, “No-Rotation Tetris AI.” 2020, Github: Adrien Wu, 2020. https://github.com/adrien1018/noro-tetris-ai. Accessed: Jul. 10, 2021.
Publicado
18/10/2021
Como Citar
SOSTER, Adler A. L.; BIRKEN, Michael; A. JASKOWIAK, Pablo.
Playing NES Tetris with No Piece Rotations. In: TRILHA DE COMPUTAÇÃO – ARTIGOS CURTOS - SIMPÓSIO BRASILEIRO DE JOGOS E ENTRETENIMENTO DIGITAL (SBGAMES), 20. , 2021, Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 339-343.
DOI: https://doi.org/10.5753/sbgames_estendido.2021.19664.
