nips nips2011 nips2011-218 nips2011-218-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Olana Missura, Thomas Gärtner
Abstract: Motivated by applications in electronic games as well as teaching systems, we investigate the problem of dynamic difficulty adjustment. The task here is to repeatedly find a game difficulty setting that is neither ‘too easy’ and bores the player, nor ‘too difficult’ and overburdens the player. The contributions of this paper are (i) the formulation of difficulty adjustment as an online learning problem on partially ordered sets, (ii) an exponential update algorithm for dynamic difficulty adjustment, (iii) a bound on the number of wrong difficulty settings relative to the best static setting chosen in hindsight, and (iv) an empirical investigation of the algorithm when playing against adversaries. 1
[1] J. Abernethy, E. Hazan, and A. Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. 2008.
[2] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. Foundations of Computer Science, Annual IEEE Symposium on, 0:322, 1995.
[3] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
[4] N. Cesa-Bianchi, Y. Mansour, and G. Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66:321–352, 2007. 10.1007/s10994-006-5001-7.
[5] D. Charles and M. Black. Dynamic player modeling: A framework for player-centered digital games. In Proc. of the International Conference on Computer Games: Artificial Intelligence, Design and Education, pages 29–35, 2004.
[6] V. Dani and T. P. Hayes. Robbing the bandit: less regret in online geometric optimization against an adaptive adversary. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, SODA ’06, pages 937–943, New York, NY, USA, 2006. ACM.
[7] G. Danzi, A. H. P. Santana, A. W. B. Furtado, A. R. Gouveia, A. Leit˜ o, and G. L. Ramalho. a Online adaptation of computer games agents: A reinforcement learning approach. II Workshop de Jogos e Entretenimento Digital, pages 105–112, 2003.
[8] T. G¨ rtner and G. C. Garriga. The cost of learning directed cuts. In Proceedings of the 18th a European Conference on Machine Learning, 2007.
[9] R. Herbrich, T. Minka, and T. Graepel. Trueskilltm : A bayesian skill rating system. In NIPS, pages 569–576, 2006.
[10] R. Hunicke and V. Chapman. AI for dynamic difficulty adjustment in games. Proceedings of the Challenges in Game AI Workshop, Nineteenth National Conference on Artificial Intelligence, 2004.
[11] H. McMahan and A. Blum. Online geometric optimization in the bandit setting against an adaptive adversary. In J. Shawe-Taylor and Y. Singer, editors, Learning Theory, volume 3120 of Lecture Notes in Computer Science, pages 109–123. Springer Berlin / Heidelberg, 2004.
[12] O. Missura and T. G¨ rtner. Player Modeling for Intelligent Difficulty Adjustment. In Discovery a Science, pages 197–211. Springer, 2009.
[13] J. Togelius, R. Nardi, and S. Lucas. Making racing fun through player modeling and track evolution. In SAB’06 Workshop on Adaptive Approaches for Optimizing Player Satisfaction in Computer and Physical Games, pages 61–70, 2006.
[14] G. Yannakakis and M. Maragoudakis. Player Modeling Impact on Player’s Entertainment in Computer Games. Lecture notes in computer science, 3538:74, 2005. 9