Dynamics Difficulty Adjusment Metode Evolutionary MCTS with Flexible Search Horizon pada Multi-Action Adversarial Games untuk Penyesuaian Tingkat Permainan

Authors

  • Andhika Evantia Irawan Program Studi Informatika
  • Liliana Liliana Program Studi Informatika
  • Hans Juwiantho Program Studi Informatika

Keywords:

Edukasi, Oceanarium, Rekreasi, Ruang, Sistem

Abstract

Dynamic Difficulty Adjustment (DDA) is a method that modifies AI behavior to suit the player's abilities. So far, research on DDA in Monte Carlo Tree Search has been able to provide an appropriate level of challenge. However, the advantages of MCTS in finding solutions to long-term strategies have not been maximally implemented because so far it is only used in 2D real-time fighting games, which are short-term strategy game.

This study combines DDA with evolutionary monte carlo tree search with flexible horizon (FH-EMCTS). FH-EMCTS is combination of vanilla MCTS with an Evolutionary algorithm. This method increases the length of the search space to certain extent. Giving DDA to FH-EMCTS is done by changing the way of selecting actions and assessing each node.

The result of this research is that AI agents that use FH-EMCTS with DDA can be implemented into multi-action adversarial game and can provide balanced level of difficulty to other AI agents and humans. Based on the results of survey of AI agents against humans, it shows that the most fun and realistic AI agents are not the AI agents who have the best ability of winning percentage but AI agents who have win rate of around 50%.

References

[1] Afergan, D., Peck, E.M., Solovey, E.T., Jenkins, A., Hincks, S.W., Brown, E.T., Chang, R. and Jacob, R.J.K. 2014. Dynamic difficulty using brain metrics of workload. Conference on Human Factors in Computing Systems - Proceedings. (2014), 3797–3806. DOI:https://doi.org/10.1145/2556288.2557230.

[2] Alexander, J.T., Sear, J. and Oikonomou, A. 2013. An investigation of the effects of game difficulty on player enjoyment. Entertainment Computing. 4, 1 (2013), 53–62. DOI:https://doi.org/10.1016/j.entcom.2012.09.001.

[3] Andrade, K.D.O., Pasqual, T.B., Caurin, G.A.P. and Crocomo, M.K. 2016. Dynamic difficulty adjustment with Evolutionary Algorithm in games for rehabilitation robotics. 2016 IEEE International Conference on Serious Games and Applications for Health, SeGAH 2016. (2016). DOI:https://doi.org/10.1109/SeGAH.2016.7586277.

[4] Ang, D. and Mitchell, A. 2017. Comparing effects of dynamic difficulty adjustment systems on video game experience. CHI PLAY 2017 - Proceedings of the Annual Symposium on Computer-Human Interaction in Play. (2017), 317–327. DOI:https://doi.org/10.1145/3116595.3116623.

[5] Aponte, M.-V., Levieux, G. and Natkin, S. 2011. Difficulty in videogames. (2011), 1. DOI:https://doi.org/10.1145/2071423.2071484.

[6] Baier, H. and Cowling, P.I. 2018. Evolutionary MCTS for Multi-Action Adversarial Games. IEEE Conference on Computatonal Intelligence and Games, CIG. 2018-Augus, (2018), 1–8. DOI:https://doi.org/10.1109/CIG.2018.8490403.

[7] Baier, H. and Cowling, P.I. 2018. Evolutionary MCTS with flexible search horizon. Proceedings of the 14th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2018. Aiide (2018), 2–8.

[8] Chen, J. 2007. Flow in games (and everything else). Communications of the ACM. 50, 4 (2007), 31–34. DOI:https://doi.org/10.1145/1232743.1232769.

[9] Colwell, A.M. and Glavin, F.G. 2017. Colwell’s castle defence: A custom game using dynamic difficulty adjustment to increase player enjoyment. CEUR Workshop Proceedings. 2086, (2017), 275–282.

[10] Constant, T. and Levieux, G. 2019. Dynamic difficulty adjustment impact on players’ confidence. Conference on Human Factors in Computing Systems - Proceedings. (2019), 1–12. DOI:https://doi.org/10.1145/3290605.3300693.

[11] Cowley, B., Charles, D., Black, M. and Hickey, R. 2008. Toward an understanding of flow in video games. Computers in Entertainment. 6, 2 (2008), 1–27. DOI:https://doi.org/10.1145/1371216.1371223.

[12] Demediuk, S., Tamassia, M., Li, X. and Raffe, W.L. 2019. Challenging AI: Evaluating the Effect of MCTS-Driven Dynamic Difficulty Adjustment on Player Enjoyment. ACM International Conference Proceeding Series. (2019). DOI:https://doi.org/10.1145/3290688.3290748.

[13] Demediuk, S., Tamassia, M., Raffe, W.L., Zambetta, F., Li, X. and Mueller, F. 2017. Monte Carlo tree search based algorithms for dynamic difficulty adjustment. 2017 IEEE Conference on Computational Intelligence and Games, CIG 2017. (2017), 53–59. DOI:https://doi.org/10.1109/CIG.2017.8080415.

[14] Gerling, K.M., Miller, M., Mandryk, R.L., Birk, M. and Smeddinck, J. 2014. Effects of skill balancing for physical abilities on player performance, experience and self-esteemin exergames. Conference on Human Factors in Computing Systems - Proceedings. (2014), 2201–2210. DOI:https://doi.org/10.1145/2556288.2556963.

[15] Hao, Y., He, S., Wang, J., Liu, X., Yang, J. and Huang, W. 2010. Dynamic difficulty adjustment of game AI by MCTS for the game Pac-Man. Proceedings - 2010 6th International Conference on Natural Computation, ICNC 2010. 8, Icnc (2010), 3918–3922. DOI:https://doi.org/10.1109/ICNC.2010.5584761.

[16] Hunicke, R. 2005. The case for dynamic difficulty adjustment in games. ACM International Conference Proceeding Series. 265, (2005), 429–433. DOI:https://doi.org/10.1145/1178477.1178573.

[17] Hunicke, R. and Chapman, V. 2004. AI for dynamic difficulty adjustment in games. AAAI Workshop - Technical Report. WS-04-04, January 2004 (2004), 91–96.

[18] Justesen, N., Mahlmann, T., Risi, S. and Togelius, J. 2017. IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES Playing Multi-Action Adversarial Games: Online Evolutionary Planning versus Tree Search. (2017), 1–10.

[19] Lucas, S.M. and Kendall, G. 2006. Evolutionary computation and games. IEEE Computational Intelligence Magazine. 1, 1 (2006), 10–18. DOI:https://doi.org/10.1109/MCI.2006.1597057.

[20] Risi, S. and Togelius, J. 2015. Neuroevolution in games: State of the art and open challenges. IEEE Transactions on Computational Intelligence and AI in Games. PP, 99 (2015), 1–19. DOI:https://doi.org/10.1109/TCIAIG.2015.2494596.

Downloads

Published

2021-04-10

Issue

Section

Articles