トレーディングカードゲームの論文を斜め読みしたメモ
前口上
IEEE COG 2019の中でゲームAIのコンペが開催されている。複数コンペがあり、Angry Birdのレベル生成、スト2的格ゲー、DeepMind hanabiなど色々。
その中でトレーディングカードゲームのコンペも開催されており、研究用の簡易カードゲームであるLegends of Code and Magic、本物のデジタルゲームを使ったHearthstoneがそれに当たる。Hearthstoneのページには先行研究の論文リストもまとまっており、面白そうなのでいくつか読んでみる。
前提
Legends of Code and MagicでもHearthstoneでもトレーディングカードゲームでは
複数あるカードからカードを選ぶ
作成したデッキを一番上手くプレイする
の2つのタスクがあり、それぞれ別の手法で最適化される。
1の中でもバリエーションがあり、Legends of Code and Magicはプレイ直前にランダムに制限されたカードから即席で選択する形式(=Shadowverseの2Pick)。Hearthstone AIコンペは事前用意されたデッキのプレイAIとデッキカスタムから行う2つのトラックがあるが、デッキカスタムの方は事前に十分に検討する時間がある前提で論文もそれに従っている。
論文
Evolutionary deckbuilding in hearthstone, 2016
デッキ生成の論文。MetastoneのAIエンジンを使ってμGPで進化的アルゴリズムにかける。一度プレイするだけだと確定性が低いので1つのデッキで15回施行。Tempo Stormというアメリカのeスポーツチームのとあるシーズンが使ったデッキをピックアップして比較。
2つのヒーロー(=クラス)について調べ人間のプロ作成のデッキを上回ったが、Metastone AIが人間のプレイでは強いデッキを上手くプレイすることができないoverfittingも見られた。生成されたデッキは明治的な条件を入れていないにも関わらず、同じカードを複数枚入れる傾向にあった。
Automated Playtesting in Collectible Card Games using Evolutionary Algorithms: a Case Study in HearthStone, 2018
同じ著者らによる論文。全てのHeroについて探索した他、進化的アルゴリズムを行う際にカードを似たコスト(+1/-1)で置換することにより計算をサボるSmart Mutationを提案している。
全てにおいて、人間のデッキを超えたものの、Smart Mutationは上手くいかないヒーローもあった。ただし、多くのヒーローで上手くいっており、効果の標準偏差も下がり進化的アルゴリズムが安定化した。
Helping AI to Play Hearthstone using Neural Networks, 2017
AAIA’17 Data Mining Challengeのwinning solution. とあるゲームの状態を与えられてプレイヤーが勝つかどうかの0/1をNeural Networkで予測する。今までにプレイしたカードとデッキの残り枚数は未知前提。
使用したネットワークは0-1でnormalizeしてCNNにかける。アンサンブルやチューニングの結果、Logistic回帰を上回ったが、AUCで0.01程度。
所感
デッキの選択をするAIを探す前提に与えられたデッキを上手くプレイできるAIが存在する前提があり、2つのタスクは関連している。両方とも計算量が増えるとダブルパンチで聞いてくるので計算量を減らす工夫が重要そう。プレイログベースにn-gramを使うアプローチの事例もあり、Card2Vecがワークしそうではある。
Future Work
コンペ参加してみるとか
