隨著這幾年電競遊戲的崛起，爐石戰記這款卡牌遊戲也跟著越來越流行，其中牌組的組建一直是遊戲論壇中人們時常討論的主題，玩家會將自己組的牌組放上論壇讓其他玩家評斷牌組強度和修正建議，但決定牌組強度的因素非常複雜且不易觀察，原因是爐石戰記是一款非常強調組合、搭配的遊戲，一張卡牌所能帶來的效益往往不是單卡質量所能決定，即便是職業選手，也時常低估或高估卡牌或牌組的強度，對於新手玩家在選用卡牌時更是困難，若我們能提供一個系統協助評估牌組的強度，將能大幅降低遊戲門檻。
過去在遊戲或運動競賽預測的研究中，主要都是針對隊伍、牌組等較大的單位擷取特徵，但我們認為針對更小的單位，例如：卡牌、球員、玩家擷取特徵，可以更接近問題的基本面，並提高模型的泛化能力。為此，本研究將提出一個結合一維卷積神經網路與注意力模型的系統；我們先以人工初步擷取卡牌特徵，接著將卡牌的一些基本屬性以向量表示之，再對卡牌特徵進行一維卷積，以此擷取整副牌組的特徵，再以注意力模型對其進行特徵編碼，最後以此編碼後的特徵執行勝率的預測。我們不僅提出了一個全新的觀點解決遊戲結果預測的問題，同時也製作了一個很有效但在過去沒有人使用過的特徵，我們將其稱為CFDF來自卡牌頻率(Card Frequency, CF)乘上牌組頻率(Deck Frequency, DF)，此特徵能同時考量目標牌組中的卡牌使用情況和每一張卡牌在其他牌組中的使用情況。我們以此特徵取代了其他研究重點使用的CF特徵並取得更好的成績。資料集是使用資料探勘比賽的平台(Advances in Artificial Intelligence and Applications, AAIA) 於2018年舉辦的比賽所提供的對戰記錄，預測目標為一牌組的勝率，其評量標準是採取均方根差(Root Mean Square Error, RMSE)，例用我們所提的牌组勝率預測系統得到的成績為RMSE=5.48，優於比賽中的排行榜第一名。
雖然CF和CFDF這種特徵是最簡單且最有效的，但此特徵會使得牌组勝率預測系統在使用上彈性降低，因為該遊戲會定期更新卡池，移除或新增卡牌會導致舊的系統不適用於新的卡池，必須在每一次更新卡池後，重新訓練一個牌组勝率預測系統，我們也針對遊戲結果預測的問題，提出了一個不需要CF特徵的預測系統，並得到RMSE=6.18的成績，在前述比賽中可以排到第十名。另外，我們所提出的注意力模型中含有一個注意力圖(Attention map)，可透過觀察此注意力圖挖掘優秀的卡牌組合，甚至是擷取卡組的核心卡牌，如此也可協助新手玩家更快速地理解遊戲，使得牌组勝率預測系統的用途更加廣泛。除此之外，我們相信此系統的框架也可以延伸應用在其他的遊戲比賽、球賽預測任務上，再者，我們相信若能與專家合作，對卡牌、玩家甚至是球員進行分析，重新定義一些特徵，應能讓預測系統的表現再更上一層樓。

With the rise of e-sports games in recent years, Hearthstone has become more and more popular. Players will upload decks built by them on the forum and discuss deck strength and correction actions with other players. However, the factors that determine the deck strength are very complicated. Hearthstone pays great attention to both the combination of cards and matching of cards effects. Benefits that cards can bring to the decks are not just determined by the value of a single card. Even professional players often underestimate or overestimate card strength and deck strength. It is even more difficult for rookies to choose cards when building decks. If we can provide a win rate predicting system to help evaluate the deck strength, the entry barrier of Hearthstone can be lowered.
In the past, researches in game prediction mainly aimed at extracting features for larger units such as teams and decks, but we believe that extracting features for smaller units such as cards and players can solve the win rate predicting problem better and make the win rate predicting system more general. For the above purpose, this thesis proposes a 1-D convolutional neural network and attention model to deal with win rate predicting problems. We first extract some attributes of cards manually and express them as a vector. Then perform 1-D convolution on card vectors and further encode convolution results with an attention model. Finally, use such embedding as a deck vector to predict the win rate.
Not only we propose a new point of view for game prediction tasks, but we also produce an effective feature by multiplying Card Frequency (CF) with Deck Frequency (DF). This is called CFDF that no one has ever used before. We employ the CFDF to replace the CF, and achieve better prediction results. The data set was provided by the data mining competition platform of Advances in Artificial Intelligence and Applications (AAIA) in 2018. The prediction target is the win rate of a deck. The evaluation standard is based on the Root Mean Square Error (RMSE). The experimental result shows that our win rate predicting system achieve RMSE= 5.48, which is better than the 1st in the competition.
Although CF and CFDF features are simple and effective, they will make the predicting system less flexible, because Hearthstone will periodically update the card pool by removing old cards and adding new cards. This will cause the old predicting system is not applicable to the new game environment. Hence, the predicting system must be retrained every time after environment updating. To deal with this problem, we also propose a predicting system that does not require CF or CFDF features, and get RMSE=6.18 that is ranked the 10th in the competition. Additionally, we can extract the attention maps from the attention model. It can be used to mine out good card combinations, and even extract the core cards of the deck according to the attention scores, which can also help players understand this game and making the predicting system more versatile. And we believe that the framework of our system can also be extended to other game prediction tasks. Besides, we are convinced that if we can cooperate with experts to analyze cards as well as players to define some implicit features, the performance of our predicting system should be further improved.

[1] A. Janusz, “Toward an intelligent HS deck advisor: Lessons learned from AAIA’18 data mining competition,” in Proceedings of the Federated Conference on Computer Science and Information Systems, Poznań, Poland, vol. 15, pp. 189-192, 2018.
[2] Q. So, “Client case study: Applying machine learning to NBA predictions,” 2019. [Online]. Available: https://blog.oursky.com/2019/11/26/machine-learning-applications-nba-predictions/. [Accessed Jun. 22, 2020].
[3] C. S. Valero, “Predicting win-loss outcomes in MLB regular season games–a comparative study using data mining methods,” International Journal of Computer Science in Sport, vol. 15, no. 2, pp. 91-112, 2016.
[4] D. Prasetio, “Predicting football match results with logistic regression,” in Proceedings of the International Conference On Advanced Informatics: Concepts, Theory And Application, Penang, Malaysian, pp. 1-5, 2016.
[5] S. Samba, “Football result prediction by deep learning algorithms,” M. S. Thesis, Department of cognitive science and artificial intellegnece school of humanites and degital sciences, University of Tilburg, Tilburg, Nederland, 2019.
[6] R. P. Bunker and F. Thabtah, “A machine learning framework for sport result prediction,” Journal of Applied Computing and Informatics, vol. 15, no. 1, pp. 27-33, 2019.
[7] D. Lowd and P. Domingos, “Naive Bayes models for probability estimation,” in Proceedings of the 22nd International Conference on Machine Learning, New York, New York, pp. 529-536, 2005.
[8] T. Chen and C. Guestrin, “Xgboost: A scalable tree boosting system,” in Proceedings of the 22nd Acm Sigkdd International Conference on Knowledge Discovery and Data Mining, San Francisco, California, pp. 785-794, 2016.
[9] L. Breiman, “Random forests,” Journal of Machine Learning, vol. 45, no. 1, pp. 5-32, 2001.
[10] A. McCabe and J. Trevathan, “Artificial intelligence in sports prediction,” in Proceedings of the Fifth International Conference on Information Technology: New Generations, Las Vegas, Nevada, pp. 1194-1197, 2008.
[11] G. Fialho, A. Manhães, and J. P. Teixeira, “Predicting sports results with artificial intelligence– a proposal framework for soccer games,” Journal of Procedia Computer Science, vol. 164, pp. 131-136, 2019.
[12] V. J. Hodge et al., “Win prediction in multi-player esports: Live professional match prediction,” To appear in Journal of IEEE Transactions on Games, 2019.
[13] Q. H. Vu et al., “Predicting win rates of Hearthstone decks: Models and features that won AAIA'2018 data mining challenge,” in Proceedings of the Federated Conference on Computer Science and Information Systems, Poznań, Poland, vol. 15, pp. 197-200, 2018.
[14] R. Polikar, “Ensemble Learning,” in Ensemble Machine Learning: Methods and Applications, C. Zhang and Y. Ma. Boston, MA: Springer, 2012.
[15] A. Sztyber and A. Witkowski, “Predicting winrate of Hearthstone decks using their archetypes,” in Proceedings of the Federated Conference on Computer Science and Information Systems, Poznań, Poland, vol. 15, pp. 193-196, 2018.
[16] J. Jakubik, “A neural network approach to hearthstone win rate prediction,” in Proceedings of the Federated Conference on Computer Science and Information Systems, Poznań, Poland, vol. 15, pp. 185-188, 2018.
[17] L. Cen et al., “Regression networks for robust win rates predictions of AI gaming bots,” in Proceedings of the Federated Conference on Computer Science and Information Systems, Poznań, Poland, vol. 15, pp. 181-184, 2018.
[18] G.-B. Huang, Q.-Y. Zhu, and C.-K. Siew, “Extreme learning machine: A new learning scheme of feedforward neural networks,” in Proceedings of the IEEE International Joint Conference on Neural Networks, Budapest, Hungary, vol. 2, pp. 985-990, 2004.
[19] Wikipedia contributors.,　“Tf–idf,” 2020. [Online]. Available: https://en.wikipedia. org/w/index.php?title=Tf%E2%80%93idf&oldid=962443067. [Accessed Jun. 22, 2020].
[20] omgvamp, “Hearthstone API,” [Online]. Available: https://rapidapi.com/ omgvamp/api/hearthstone. [Accessed Jun. 24, 2020].
[21] S. Kiranyaz et al., “1-D convolutional neural networks and applications: A survey,” arXiv preprint arXiv:1905.03554, 2019.
[22] O. Levy and Y. Goldberg, “Neural word embedding as implicit matrix factorization,” in Proceedings of the Advances in Neural Information Processing Systems, Montreal, Quebec, Canada, pp. 2177-2185, 2014.
[23] J. Pennington, R. Socher, and C. D. Manning, “Glove: Global vectors for word representation,” in Proceedings of the Conference on Empirical Methods in Natural Language Processing, Doha, Qatar, pp. 1532-1543, 2014.
[24] A. Vaswani et al., “Attention is all you need,” in Proceedings of the Advances in Neural Information Processing Systems, Long Beach, California, pp. 5998-6008, 2017.
[25] T. Mikolov et al., “Extensions of recurrent neural network language model,” in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, Prague, Czech Republic, pp. 5528-5531, 2011.