Trace-based multi-criteria preselection approach for decision making in interactive applications like video games

Trace-based multi-criteria preselection approach for decision making in interactive applications like video games

Hoang Nam Ho Mourad Rabah Samuel Nowakowski Pascal Estraillier 

Laboratoire L3i, Université de La Rochelle Avenue Michel Crépeau - 17042 La Rochelle Cedex 1 - France

LORIA, UMR 7503, Université de Lorraine Campus Scientifique, BP 239, Vandoeuvre-lès-Nancy, France

Corresponding Author Email:;;;
30 June 2017
| Citation



The decision making in games is essential to make them more automated and smart. A decision algorithm performs its calculations on the set of all the possible solutions. This increases the computation time and may become a combinatorial explosion problem if we have a huge solution space. To overcome this problem, we present our work on relevant solutions preselection before making a decision. We propose a two-steps strategy: i) the first step analyzes system’s traces (users past executions) to identify all the potential solutions; ii) the second step aims to estimate the relevance, called utility, of each of these potential solutions. We get a set of alternative solutions that can be used as an input to any decision algorithm. We illustrate our approach on the Tamagotchi game.


interactive adaptive system, traces, prediction, utility, multi-criteria decision making

1. Introduction
2. Positionnement des travaux
3. Système à base de traces
4. Approche de présélection des candidats multicritère à base de traces
5. Cas d’étude : jeu Tamagotchi
6. Conclusion

Behzadian M., Kazemzadeh R. B., Albadvi A., Aghdasi M. (2010). PROMETHEE: A comprehensive literature review on methodologies and applications. European Journal of Operational Research, vol. 200, no 1, p. 198–215.

Brun P., Beaudouin-Lafon M. (1995). A taxonomy and evaluation of formalisms for the specification of interactive systems. In Proceeding of 6th International Conference on Human-Computer Interaction, p. 197–212. Huddersfield, United Kingdom.

Burke R. (2007). HybridWeb Recommender Systems. In Brusilovsky, Peter and Kobsa, Alfred and Nejdl,Wolfgang (Ed.), The Adaptive Web: Methods and Strategies of Web Personalization, vol. 4321, p. 377–408. Berlin, Heidelberg, Springer-Verlag. 

Cheetham W. (2003). Global Grade Selector: A Recommender System for Supporting the Sale of Plastic Resin. In 5th International Conference on Case-Based Reasoning: Research and Development, p. 96–106. Norway, Springer-Verlag.

Cornuéjols A., Miclet L. (2011). Apprentissage artificiel: concepts et algorithmes. Editions Eyrolles.

Corrente S., Greco S., Słowi´nski R. (2013, octobre). Multiple Criteria Hierarchy Process with ELECTRE and PROMETHEE. Omega, vol. 41, no 5, p. 820–846.

Dang K. D., Pham P. T., Champagnat R., Rabah M. (2013). Linear logic validation and hierarchical modeling for interactive storytelling control. In D. Reidsma, H. Katayose, A. Nijholt (Eds.), Advances in Computer Entertainment: 10th International Conference, ACE 2013, vol. 8253, p. 524–527. Boekelo, The Netherlands,, Springer International Publishing.

Dill K., Mark D. (2010). Improving AI Decision Modeling Through Utility Theory (video content). In Game Developers Conference 2010. San Francisco, CA.

Dill K., Mark D. (2012). Embracing the Dark Art of Mathematical Modeling in AI (video content). In Game Developers Conference 2012. San Francisco, CA. Domingos P., Pazzani M. (1997). On the optimality of the simple Bayesian classifier underzero-one loss. Machine Learning, vol. 29, no 2-3, p. 103–130.

Doumat R., Egyed-Zsigmond E., Pinon J.-M. (2010). User Trace-Based Recommendation System for a Digital Archive. In Bichindaritz, Isabelle and Montani, Stefania (Ed.), International Conference on Case-Based Reasoning 2010, vol. 6176, p. 360–374. Alessandria, Italy, Springer-Verlag.

Evans R. (2009). AI Challenges in Sims 3 - Invited talk in The Fifth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment Conference. Palo Alto, California.

Guo Y., Hu J., Peng Y. (2011). Research on CBR system based on data mining. Applied Soft Computing, vol. 11, no 8, p. 5006–5014.

Hall M., Frank E., Holmes G., Pfahringer B., Reutemann P., Witten I. H. (2009). The WEKA Data Mining Software: An Update. ACM SIGKDD Explorations Newsletter, vol. 11, no 1, p. 10–18.

Hatami-Marbini A., Tavana M. (2011). An extension of the Electre I method for group decisionmaking under a fuzzy environment. Omega, vol. 39, no 4, p. 373–386.

Ho H. N. (2015). Décision multicritère à base de traces pour les applications interactives à exécution adaptative. Thèse de doctorat - Université de La Rochelle, France.

Ho H. N., Rabah M., Nowakowski S., Estraillier P. (2014, août). Trace-Based Weighting Approach for Multiple Criteria Decision Making. Journal of Software, vol. 9, no 8, p. 2180–2187.

Ho H. N., Rabah M., Nowakowski S., Estraillier P. (2015). Application of trace-based subjective logic to user preferences modeling. In 20th International Conferences on Logic for Programming, Artificial Intelligence and Reasoning (short papers), vol. 35, p. 94–105.

Ho H. N., Rabah M., Nowakowski S., Estraillier P. (2016). Toward a Trace-Based PROMETHEE II Method to answer ” What can teachers do? ” in Online Distance Learning Applications. In 13th International Conference on Intelligent Tutoring Systems, p. 480–484. Zagreb, Croatia.

Jeuxvidé (2008). Les Sims passent les 100 millions.

J.Hand D., Yu K. (2001). Idiot’s Bayes - not so stupid after all? International Statistical Review, vol. 69, no 3, p. 385–398.

Karol A., Nebel B., Stanton C., Williams M.-A. (2004). Case based game play in the robocup four-legged league part i the theoretical model. In D. Polani, B. Browning, A. Bonarini,

K. Yoshida (Eds.), RoboCup 2003: Robot Soccer World Cup VII, vol. 3020, p. 739–747. Berlin, Heidelberg, Springer Berlin Heidelberg.

Köksalan M., Wallenius J., Zionts S. (2011). Multiple criteria decision making: From early history to the 21st century. World Scientific.

Laflaquière J., Settouti L. S., Prié Y., Mille A. (2006). Trace-Based Framework for Experience Management and Engineering. In Proceedings of the 10th International Conference on Knowledge-Based Intelligent Information and Engineering Systems - Volume Part I, p. 1171–1178. Bournemouth, UK, Springer-Verlag.

Mark D. (2016). Intrisic Algorithm - IA on AI. Marling C., Tomko M., Gillen M., Alex D., Chelberg D. (2003). Case-based reasoning for planning and world modeling in the robocup small sized league. In IJCAI Workshop on Issues in Designing Physical Agents for Dynamic Real-Time Environments: World Modeling, Planning, Learning, and Communicating, p. 29–36. Acapulco, Mexico.

Ontañón S., Ram A. (2011). Case-based reasoning and user-generated artificial intelligence for real-time strategy games. In P. A. González-Calero, M. A. Gómez-Martín (Eds.), Artificial Intelligence for Computer Games, p. 103–124. New York, NY, Springer New York.

Pham P. T., Rabah M., Estraillier P. (2015). A situation-based multi-agent architecture for handling misunderstandings in interactions. Applied Mathematics and Computer Science, vol. 25, no 3, p. 439–454.

Podinovski V. V. (2014). Decision making under uncertainty with unknown utility function and rank-ordered probabilities. European Journal of Operational Research, vol. 239, no 2, p. 537–541.

Riesbeck C., Schank R. (2013). Inside case-based reasoning. Taylor & Francis. Ros R., Arcos J. L., Mantaras R. Lopez de, Veloso M. (2009). A Case-based Approach for Coordinated Action Selection in Robot Soccer. Artificial Intelligence., vol. 173, no 9-10, p. 1014–1039.

Russell S. J., Norvig P. (2010). Artificial Intelligence: A Modern Approach. Prentice Hall. Settouti L. S., Prié Y., Cram D., Champin P.-A., Mille A. (2009). A Trace-Based Framework for supporting Digital Object Memories. In 1st International Workshop on Digital Object Memories (DOMe’09) in the 5th International Conference on Intelligent Environments (IE09), p. 39–44. Barcelona, Spain.

Sutton R. S., Barto A. G. (2012). Introduction to reinforcement learning (2e éd.). MIT Press.

Sánchez-Pelegrín R., Gómez-Martín M. A., Díaz-Agudo B. (2005). A CBR module for a strategy videogame. In 1st Workshop on Computer Gaming and Simulation Environments, at 6th International Conference on Case-Based Reasoning (ICCBR), p. 217–226. Chicago, USA.

Taillandier P., Stinckwich S. (2011). Using the PROMETHEE multi-criteria decision making method to define new exploration strategies for rescue robots. In IEEE International Workshop on Safety, Security, and Rescue Robotics, p. 193–202. Kyoto, Japan.

Tan P.-N., Steinbach M., Kumar V. (2006). Introduction to data mining. Wesley, Pearson Addison.

Triantaphyllou E., Shu B., Sanchez S. N., Ray T. (1998). Multi-Criteria Decision Making : An Operations Research Approach. Encyclopedia of Electrical and Electronics Engineering, vol. 15, p. 175–186.

Vapnik V. (2000). The Nature of Statistical Learning Theory. New York, Springer-Verlag New York.

Watkins C. J. C. H., Dayan P. (1992). Q-learning. Machine Learning, vol. 8, no 3-4, p. 279–292.

Wu X., Kumar V., Ross Quinlan J., Ghosh J., Yang Q., Motoda H. et al. (2007). Top 10 Algorithms in Data Mining. Knowledge and Information Systems, vol. 14, no 1, p. 1–37.