Predicting Cards Using a Fuzzy Multiset Clustering of Decks
Tóm tắt
Search-based agents have shown to perform well in many game-based applications. In the context of partially-observable scenarios agent’s require the state to be fully determinized. Especially in case of collectible cards games, the sheer number of decks constructed by players hinder an agent to reliably estimate the game’s current state, and therefore, renders the search ineffective. In this paper, we propose the use of a (fuzzy) multiset representation to describe frequently played decks. Extracted deck prototypes have shown to match human expert labels well and seem to serve as an efficient abstraction of the deck space. We further show that such deck prototypes allow the agent to predict upcoming cards with high accuracy, therefore, allowing more accurate sampling procedures for search-based agents.
Tài liệu tham khảo
Blizzard Entertainment, Hearthstone webpage, 2019. https://playhearthstone.com
Statista Inc., Number of hearthstone: heroes of warcraft players worldwide as of November 2018 (in millions), 2019. https://www.statista.com/statistics/323239/number-gamers-hearthstone-heroes-warcraft-worldwide/
Hearthstone Top Decks, Hearthstone beginner’s guide 2018 – guides, tips, and tricks for new players!, 2019. https://www.hearthstonetopdecks.com/hearthstone-beginners-guide-2017-guides-tips-tricks-new-players/
A. Dockhorn, S. Mostaghim, Introducing the hearthstone-ai competition, CoRR, abs/1906.04238, 2019.
J.S.B. Choe, J.K. Kim, Enhancing monte carlo tree search for playing hearthstone, in IEEE Conference on Computatonal Intelligence, London, UK, 2019,
A. Dockhorn, M. Frick, U. Akkaya, R. Kruse, Predicting opponent moves for improving hearthstone AI, in: J. Medina, M. Ojeda-Aciego, J.L. Verdegay, D.A. Pelta, I.P. Cabrera, B. Bouchon-Meunier, R.R. Yager (Eds.), 17th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, IPMU 2018, Springer International Publishing, Cham, Switzerland, 2018, pp. 621–632.
J. Long, N.R. Sturtevant, M. Buro, T. Furtak, Understanding the success of perfect information monte carlo sampling in game tree search, in Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, (2010), pp. 134–140.
D. Whitehouse, E. Powley, P. Cowling, Determinization and information set monte carlo tree search for the card game dou di zhu, in Proceedings of the 2011 IEEE Conference on Computational Intelligence and Games (CIG’11), IEEE, Seoul, South Korea, 2011, pp. 87–94.
A. Santos, P.A. Santos, F.S. Melo, Monte carlo tree search experiments in hearthstone, in 2017 IEEE Conference on Computational Intelligence and Games (CIG), IEEE, New York, NY, USA, 2017.
P. García-Sánchez, A. Tonda, A.J. Fernández-Leiva, C. Cotta, Optimizing hearthstone agents using an evolutionary algorithm, Knowl. Based Syst. 188 (2020), 105032.
S. Sievers, M. Helmert, A doppelkopf player based on UCT, in: S. Hölldobler, R. Peñaloza, S. Rudolph (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9324, Springer, Cham, Switzerland, 2015, pp. 151–165.
A. Dockhorn, C. Doell, M. Hewelt, R. Kruse, A decision heuristic for Monte Carlo tree search doppelkopf agents, in 2017 IEEE Symposium Series on Computational Intelligence (SSCI), IEEE, Honolulu, HI, USA, 2017, pp. 1–8.
E. Bursztein, I am a legend: hacking hearthstone using statistical learning methods, in 2016 IEEE Conference on Computational Intelligence and Games (CIG), IEEE, Santorini, Greece, 2016, pp. 1–8.
A. Dockhorn, T. Schwensfeier, R. Kruse, Fuzzy multiset clustering for metagame analysis, in Proceedings of the 2019 Conference of the International Fuzzy Systems Association and the European Society for Fuzzy Logic and Technology (EUSFLAT 2019), Atlantis Press, Paris, France, 2019.
S. Miyamoto, Fuzzy multisets and their generalizations, in: C. Calude, G. Puaun, G. Rozenberg, A. Salomaa (Eds.), Multiset Processing, Mathematical, Computer Science, and Molecular Computing Points of View [Workshop on Multiset Processing, WMP 2000, Curtea de Arges, Romania, August 21–25, 2000], vol. 2235 of Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, Germany, 2000, pp. 225–236.
R.R. Yager, On the theory of bags, Int. J. Gen. Syst. 13 (1986), 23–37.
C.C. Aggarwal, C.K. Reddy, Data Clustering: Algorithms and Applications, CRC Press, Boca Raton, FL, USA, 2013.
M.R. Berthold, C. Borgelt, F. Höppner, F. Klawonn, Guide to Intelligent Data Analysis. Texts in Computer Science, Springer, London, UK, 2010.
C. Borgelt, R. Kruse, Agglomerative fuzzy clustering, in: M. Ferraro et al. (Eds.), International Conference on Soft Methods in Probability and Statistics, Springer, Cham, Switzerland, 2016, pp. 69–77.
R. Kruse, C. Borgelt, C. Braune, S. Mostaghim, M. Steinbrecher, Computational Intelligence, Texts in Computer Science, second ed., Springer, London, UK, 2016.
K. Honda, S. Miyamoto, H. Ichihashi, Hidetomo Ichihashi. Algorithms for Fuzzy Clustering: Methods in C-Means Clustering with Applications, Studies in Fuzziness and Soft Computing 229, first ed., Springer-Verlag, Berlin, Heidelberg, Germany, 2008,
J.B. MacQueen, Some methods for classification and analysis of multivariate observations, in 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, California, USA, 1967, vol. 1, pp. 281–297. https://projecteuclid.org/euclid.bsmsp/1200512992
R. Sibson, SLINK: an optimally efficient algorithm for the single-link cluster method, Comput. J. 16 (1973), 30–34.
D. Defays, An efficient algorithm for a complete link method, Comput. J. 20 (1977), 364–366.
M. Ester, H.P. Kriegel, J. Sander, X. Xu, A density-based algorithm for discovering clusters in large spatial databases with noise, in Second International Conference on Knowledge Discovery and Data Mining (KDD-96), Portland, Oregon, USA, 1996, pp. 226–231.,
M. Levandowsky, D. Winter, Distance between sets, Nature. 234 (1971), 34–35.
A. Dockhorn, Project files and supporting material, 2020. https://github.com/ADockhorn/StateDeterminizationExperiments
HearthSim, HSReplay.net, 2019. https://hsreplay.net/decks/
A. Rosenberg, J. Hirschberg, V-measure: aconditional entropy-based external cluster evaluation measure, Comput. Linguistics. 1 (2007), 410–420.
A. Dockhorn, C. Braune, R. Kruse, An alternating optimization approach based on hierarchical adaptations of DBSCAN, in 2015 IEEE Symposium Series on Computational Intelligence, IEEE, Cape Town, South Africa, 2015, pp. 749–755.