日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

進化的アルゴリズムを基にした Hearthstone の
行動決定
櫻井 英司

長谷部 浩二Hearthstone はターン制のトレーディングカードゲームの一種で，隠れた情報やランダム性を含む不完全情報 2 人
対戦型のゲームである．Hearthstone は行動の選択肢の数が多く，また各ターンにおいて一連の行動を実行する必要があるため，行動空間が非常に大きくなりやすい．そのため，ゲーム木探索を基にした手法では，個々の行動を評価しながら探索するため，ターン終了までの最適な行動を見つけることが困難となることが多い．このような問題を解決するため，本研究は進化的アルゴリズムの一種である Rolling Horizon Evolutionary Algorithm（RHEA）
を基にした Hearthstone の行動決定手法を提案する．その基本的なアイデアは，各ターンの一連の行動を実行した
後の状態の評価に基づいた遺伝的操作を行い，評価値が最も高くなる最適な一連の行動を探索するというものである．本研究では，提案手法の有用性を評価するために，過去のコンペティションで上位の成績を収めたエージェントとの対戦を行った．その結果，扱いが難しいとされるデッキを使用した場合の勝率が約 60%以上となった．

（手番）を交代しながら進行し，自分の手番で手持ち

1 序論のデッキを使い，最終的に相手を体力を 0 にしたプレ

近年，人工知能の関連技術の発展に伴い，ゲームをイヤーが勝者となる．一般に，このようなトレーディプレイするコンピュータプログラムの研究開発が盛ん

ングカードゲームは，行動の選択肢が多く存在し，まに行われるようになった．特に最近では，ポーカーやた，自分のターン中に複数の行動を連続して実行する

麻雀，トレーディングカードゲームのような隠れた情

ことができるため，各行動を決定する際に探索する行

報や確率的な要素を含む不完全情報ゲームを対象と動空間が非常に大きくなりやすいという特徴がある．

した研究 [2] [10] に注目が集まっている．

このようなゲームを解くために，先行研究の多くHearthstone [1] はトレーディングカードゲームの[4] [13] [15] は木探索を基にした手法を用いている．し一種であり，ターン制の不完全情報 2 人対戦型ゲーム

かし，こうした手法は行動空間が非常に大きい場合，である．Hearthstone には 1000 種類以上のカードが十分に探索することができず，限られた時間内にター存在し，各プレイヤーはその中から一定の制限下で選ン終了までを見通した行動決定が困難な場合がある．

択された 30 枚のカードの束（デッキ）を持ち寄ってそこで，本研究では進化的アルゴリズムの一種である

プレイする．ゲームは 2 人のプレイヤー間でターン

Rolling Horizon Evolutionary Algorithm（RHEA）∗

Decision-making in Hearthstone based on Evolutionary Algorithm
This is an unrefereed paper. Copyrights belong to
the Authors.
Eiji Sakurai, 筑波大学大学院情報理工学位プログラム,
Master’s Program in Computer Science, Universityof Tsukuba.
Koji Hasebe, 筑波大学システム情報系, Faculty of Engineering, Information and Systems, University ofTsukuba.

[11] を基にした Hearthstone の行動決定手法を提案

する．RHEA は一定区間の一連の行動を持つ個体に対して，交叉や突然変異を加えて，評価値が最も高くなる最適な一連の行動を探索する．したがって，一連の行動を実行した後の状態の評価によって行動を決定するため，行動空間が非常に大きい環境においても有効な手法になると考えられる．

RHEA を Hearthstone に適用するために，提案手

法では元の RHEA に対して以下の 3 つの改良を加え

5 章では，提案手法である RHEA に基づく行動決定る．第 1 の改良は，元の RHEA では個々の行動に対手法について述べる．第 6 章では，提案手法の実験

して一様交叉を行うのに対して，提案手法では行動のによる評価について述べる．最後に，第 7 章では結種類毎で交換を行うというものである．第 2 の改良論と今後の課題について述べる．

は，元の RHEA ではランダムに変異させる行動を決め，その行動のみをランダムに変異させるのに対し

2 関連研究て，提案手法では該当の行動だけではなく，後続の行Hearthstone の対戦を対象とした行動決定手法の研動も勝利に近づきやすい行動に範囲を狭めた上でラ

究では，モンテカルロ木探索（MCTS）を基にした

ンダムに変異させるというものである．第 3 の改良手法が多く見られる．Choe らの研究 [4] では，抽象は，元の RHEA では最高の評価値を持つ個体の最初化とサンプリングによって探索木の広がりを抑制しの行動を実行するのに対して，提案手法では母集団のている．さらに，ニューラルネットワークを組み合わ個体から求められる期待値が最も高くなる最初の行

せて状態の評価精度を向上させる研究 [13] [15] [14] が動を実行するというものである．

行われている．また，相手が直前に使用したカードか本研究では，提案手法の性能を評価するために，

ら手札を推定する研究 [3] を発展させて，相手のデッHearthstone AI Competition [7] で好成績を収めたい

キを推定して MCTS の探索の質を向上させる研究 [5]

くつかのプログラムと提案手法のプログラムを対戦も行われている．

させる実験を行なった．その結果，扱いが難しいデッ

一方，General Video Game AI（GVGAI）と呼ばキを使用した場合，いずれも約 60%以上の勝率で勝れるフレームワークに RHEA を適用した研究では，ち越した．また，探索によって状態評価を行ったター

過去の探索情報を活用しようとする提案が多く見らン終了時の状態数を比較した結果，提案手法は他の手れる．GVGAI とはスペースインベーダーやパズル

法と比べて約 2.7 倍以上の状態を評価していた．したゲームといった比較的簡単なゲームを扱うフレーム

がって，提案手法はターン終了時まで見通した行動決ワークである．このようなゲームを対象とした Perez

定が可能なため，他の手法よりも強力であったと考えらの研究 [12] では，今まで生成した各個体の一連のられる．また，RHEA に対する改良の効果を評価す

行動と評価値の探索情報を，木構造にして保持するるために，改良を加えていない元の RHEA との対戦ことを提案している．Gaina らの研究 [8] では，突然を行った．その結果，提案手法による突然変異と行動

変異の範囲を制限させることや探索情報を再利用す決定方法を用いた場合の勝率が最も高く，約 56%とることを提案している．また，RHEA をターン制ス

なった．

トラテジーゲームに適用させた研究 [9] では，個々の以上の実験の結果から，本研究の提案手法は扱い

行動決定を行うのではなく，一連の行動計画を立てが難しいデッキに対しては有用性が確認できた．特にて，最後までそれを実行する Online Evolutionary

突然変異と行動決定方法については効果的であるこ

Planning（OEP）という手法が提案されている．さとが確認できた．一方で，扱いが簡単なデッキに対しらに，RHEA をリアルタイムストラテジーゲームにては期待された効果が得られなかった．これは，扱い適用させた研究 [6] では，RHEA を行動空間の探索にが難しいデッキに合わせた遺伝的操作によって探索を使うのではなく，行動の抽象化を行ったスクリプト空行っており，他のデッキには適していなかったためで間の探索に使用している．いずれも MCTS に基づくあると考えられる．

手法と比較されており，探索空間が大きい場合は特に本論文の構成は以下の通りである．第 2 章では，良い性能を示している．

Hearthstone と RHEA の関連研究について述べる．

MCTS は選択肢が多い環境の場合，制限時間内に第 3 章では，Hearthstone の概要について簡単に述べターン終了までの最適な一連の行動を見つけることる．第 4 章では，RHEA の概要について述べる．第が困難となる場合がある．一方，RHEA は一連の行

動を実行した後の状態のみを評価するため，選択肢がコストをマナというリソースから支払う必要がある多い環境でもターン終了までを見通して行動を決定（マナの詳細については後述する）．

できる可能性がある．また，評価する状態の数を大幅• ミニオン：手札から使うことで盤面に召喚するに削減できるため，評価にかかる時間も削減できる．

（カードを盤面に置く）ことができる．また，盤

しかし，RHEA を Hearthstone に適用するには以下

面に自分の他のミニオンがいる場合，位置を指定の 3 つの課題がある．

できる．ミニオンは体力と攻撃力という値を持• 一連の行動を遺伝的操作によって変異させた際，実行不可能な行動が生成されてしまう．

ち，盤面にあるミニオンの体力が 0 になると盤面から除かれる．また，盤面にあるミニオンは攻• 各個体の評価に時間がかかってしまう場合，制撃することが可能であり，攻撃を実行するとミニ

限時間内に最適な一連の行動を見つけることがオンが持つ攻撃力の値だけ対象にダメージを与困難になる．

える．

• ランダム性が含まれる環境の場合，最良個体の• スペル：手札から使うことでカードの持つ効果持つ行動が必ずしも実行できるとは限らない．

を使うことができる．例えば，「デッキからカー

したがって本研究では，実行不可能な行動の生成のドを１枚引く」という効果を持つカードを使用し抑制を行い，評価済みの状態の再利用によって個体のた場合，コストを支払ってデッキからカードを１評価の高速化を行う．また，ランダム性を含む行動の枚引き，手札に加えることができる．

対応として累積させた探索情報による評価値の平均に基づいて行動決定を行う．

• ウェポン：ヒーローに装備させることができる．
ウェポンを装備したヒーローはウェポンの持つ攻撃力を獲得し，攻撃することが可能となる．ま3 Hearthstone の概要

た，ウェポンには攻撃する度に減少する耐久度とHearthstone には，デッキの構築と対戦の 2 つのいう値があり，耐久度が 0 になるとウェポンは除フェーズが存在する．対戦の前に各プレイヤーが使いかれる．

たいカードを一定の制限の下で 30 枚束ねてデッキを構築し，勝利条件である対戦相手のヒーローの体力

3. 2 対戦の進め方

値を 0 にするために，各々のデッキを使ってお互いに対戦は各ヒーローの体力が 30 から始まり，最初のターンを交代しながら，対戦を進めていく．

ターン開始時にお互いに構築したデッキからカードを引いて手札を 4 枚にし，後攻にはコインと呼ばれる

3. 1 デッキの構築

特殊なカードを追加して手札を 5 枚にする．その後，デッキの構築では，まずプレイヤーはヒーローと呼先攻と後攻でターンを交代しながら相手のヒーロー

ばれる自身のキャラクターを 10 種類のヒーローの中の体力が 0 になるまで繰り返す．

から選択する．ヒーロー毎に固有の効果であるヒー

自分のターンの進め方としては，まずターン開始時

ローパワーを持ち，使用できるカードが制限され，そにデッキからランダムに 1 枚を手札に加え，マナの上の中から使いたいカードを 30 枚束ねることでデッキ

限値が 1 増加する．マナはターンが経過するにつれが完成する．そのため，デッキに含まれるカードにて，上限値が 10 になるまで増加する．その後，マナ

よって，行動空間の広がり方やゲーム終了までにかかを支払ってカードの使用や，盤面にミニオンが存在する時間，扱う難しさなどが異なることから，多種多様る場合は攻撃など，複数の行動を実行することができな戦い方を持つデッキが存在する．

る．例として手札から「カード A を召喚」し，盤面Hearthstone で使われるカードには，大きく分けてにある「カード B で相手のヒーローを攻撃」，「ター

以下に示す 3 種類のカードが存在する．またカードンエンド」という 3 つの行動を順番に実行する場合にはコストがあり，手札からカードを使う場合，そのを以下に記す．

1. 手札からカード A が持つコストを支払って，盤面にカード A を召喚する．この時，召喚された



$

%

&

'

"

(

)

*

+

"

,

-

.

/

"



$

%

&

'



(

)

*

+



,

-

.

/





0

1

2

3



(

)

*

+



,

-

.

/



+



(

1

*

3



&

/



4

5

6

7



カード A は手札から無くなる．

2. 盤面にあるカード B が持つ攻撃力の値だけ相手のヒーローの体力の値を減少させる．

3. 自分のターンを終了し，相手のターンへ交代





する．
また，ゲームの状態には観測可能な情報と隠れた情報がある．観測可能な情報は，手札やデッキの枚数と自分の手札のカード，盤面のカード，お互いのヒー

)

2



突然変異

ઐጎ
0

最良個体
図1

,

-

4

実⾏



RHEA による最適化の手順

ローの体力と攻撃力，マナなどとなっている．隠れたりに一連の行動を持ち，一連の行動を実行した後の状情報は，相手の手札とデッキの中身や自分のデッキの態の評価値が個体の評価値となる．評価値の高い個体

カードの順序となっている．そのため，各プレイヤーが持つ一連の行動に対して，交叉や突然変異といったは観測可能な情報から隠れた情報を推定しながら，対遺伝的操作を繰り返して最適化を行う．RHEA によ

戦を進めていくことになる．

る最適化の手順を図 1 に示す．なお，図中の番号は以以上が，Hearthstone における対戦の進め方の概

下の説明におけるステップの番号に対応している．

要である．ここで行動空間の大きさについて述べる．

1. ランダムに一連の行動を実行し，複数の個体をHearthstone ではカードを使用する際に対象を選択する必要がある．対象とはカードを召喚する位置やカー
ド自身，ヒーローを指す．まず，対戦の序盤の場合を考える．一般に対戦の序盤では実行可能なカードと対象も非常に少ない傾向がある．例えば，実行可能な生成し初期集団を形成する．

2. 各個体の評価を行う．この評価値は一連の行動を実行した後の状態の評価となる．

3. トーナメント選択やエリート選択などによって評価の高い個体を選択する．

カードが 3 枚あり，対象が 1 つ存在する場合，3 通り

4. 選択された個体に遺伝的操作を行う．交叉では，の選択肢が存在する．一度使用したカードは除かれる

一様交叉により 2 個体間の行動をランダムに入ため，次の選択肢は 2 通りとなり，1 ターンの行動空れ替えを行う．突然変異では変異点をランダムに間は最大で 6 となる．次に，対戦の終盤の場合を考決めて，ランダムに行動を選択する．これによえる．一般に対戦の終盤では，実行可能なカードと対り，新しい一連の行動を持つ個体が生成される．

象が多い傾向がある．例えば，実行可能なカードが 9

5. 生成された新しい個体に対して評価を行う．

枚あり，対象が 6 つ存在する場合，54 通りの選択肢

6. 制限時間になるまでステップ 2 からステップ 5が存在することになる．一度使用したカードは除かれるため，次の選択肢は最大 48 通りとなる．このようにして 1 ターンの間に 4 つの行動が実行できる場合，行動空間の大きさは最大で 3.9 × 10 となる．実際に6は不均衡なゲーム木となるため，行動空間はもっと小さくなる．

を繰り返す．

7. 行動決定の際には，評価値が最高の個体が持つ最初の行動を選択する．

8. 次の状態へ遷移し，ステップ 1 から次の行動である 2 番目の行動を探索する．
このように RHEA は一連の行動を実行した後の状態のみの評価に基づいて探索が行われるため，行動空

4 RHEA の概要

間が非常に大きい場合でも一連の行動を見通した行RHEA [11] は進化的アルゴリズムの一種であり，リ動決定ができる可能性が高いと考えられる．

アルタイムで状態が遷移するゲームにおいて木探索に代わる行動決定手法である．各個体は遺伝子の代わ

஡
$

%

&

৕
'

(

*

&

$

)

*

(

$

%

'

)

$ ⼀連の⾏動の⻑さが⻑くなるように変異

੪भ଻৬

(

%

&

(

$

(

︓召喚・使⽤・⾏動

︓召喚・使⽤・⾏動

︓攻撃

︓攻撃

︓ターンエンド

︓⼊れ替え対象

︓ターンエンド

&

'

)

(

% ঐॼ॑৸थ
଎ાघॊेअप変異
$

%

&

*

+

(

& 完全にランダムに変異

︓変異の対象
図2

%

)

交叉
図3

&

*

'

(

突然変異

5 RHEA に基づく行動決定手法
本研究で提案する手法は，Hearthstone の行動決定

突然変異は，以下の 3 つのメソッドによって行わを RHEA によって行う．Hearthstone における一連れる．これらは，選択できる行動が残っている場合，の行動とはターンエンドを選択するまでの行動を指ターンエンドを行うよりも何らかの行動を実行した

す．そのため，個体の評価はターン終了時の状態を評方が良いという考えに基づいている．

価したものとなる．状態の評価はプレイアウトによっ• 一連の行動の長さを長くするメソッドて行う．遺伝的操作では，母集団に対してエリート選• マナを消費するようにするメソッド

択を行い，選ばれた各個体に対して交叉と突然変異を• ランダムメソッド

行う．行動決定の際には，生成した個体による探索情図 3 は，これらの 3 つのメソッドを用いた突然変異報を基にして，評価値の平均が最大となる最初の行動によって，個体が生成される例である．図 3 の（A）を選択する．これらをターンエンドしか選択できなくの一連の行動の長さが長くなる変異では，親個体の一なるまで繰り返し実行する．

連の行動のある位置から，ターンエンドしか選択できなくなるまで，ランダムに行動を追加する．図 3 の

5. 1 遺伝的操作と行動決定（B）のマナを全て消費するようにする変異では，召図 2 は交叉によって個体が生成される例である．交喚や使用に該当する行動をランダムに選択して追加

叉では 2 個体間の行動の種類毎で入れ替えを行うた

し，最後にターンエンドを追加する．図 3 の（C）のめ，評価の高い 2 個体を母集団の中からランダムに変異では，あまり行動しないことが最適である可能

選択する．図 2 の親個体のように，2 個体の行動を種性を考慮して，完全にランダムに変異させる．本研究

類毎に分類し，同じ種類の行動同士を順番を変えずにでは，この 3 つのメソッドを 3:3:4 の割合で設定して入れ替える．このような交叉を行う理由は，召喚と使いる．

用はマナを消費する行動であり，選択はこれらの行動

行動決定では，元の RHEA は最良個体が持つ一連に依存して発生する行動であるため，これらの行動をの行動の最初の行動を選択するが，Hearthstone では

個別に入れ替えてしまうと，実行不可能な行動となる以降の行動が実行できない場合があるため，必ずしも場合があるためである．同様の理由で，攻撃も順番を最適とは限らない．これに対処するために，母集団の入れ替えずにまとめて入れ替えを行う．ターンエンド

全個体の一連の行動による評価値から平均を求めて，については，必ず一連の行動の最後とする．しかし，期待値が最も高い最初の行動を選択して実行する．

他の行動においても後続の行動に影響を与えることがあるため，実行不可能な行動が生成されてしまうことがある．その場合，代わりにランダムな一連の行動を持つ新しい個体を生成する．

5. 2 個体の評価方法
個体を評価するためには，一連の行動を実行した
後の状態を評価する必要がある．そのため，その状態

からゲーム終了までをランダムにプレイすることを

表1

繰り返し，勝率をその状態の評価値とするプレイア

設定項目

値

設定項目

値

ウトを行う．また，相手の行動をシミュレートする必母集団のサイズ

20

エリート率

0.5

要があるため，相手のデッキや手札を決定する必要が

交叉の確率

0.3

決定するゲーム数20ある．本研究では，観測可能な情報である相手のヒー突然変異の確率0.7

プレイアウト数

20

提案手法の各種パラメータの設定

ローの種類から，相手のデッキに含まれるカードをランダムに決定し，相手の手札は生成したデッキから実戦による勝率を測定した（第 6.7 節）．

際の手札の枚数に合うように取り出して決定してい提案手法の各種パラメータの設定を表 1 に示す．実る．具体的には，隠れた情報を決定したゲームを 20

験環境として，Hearthstone AI Competition で使用個生成し，各ゲームに対して 20 回ずつのプレイアウ

される Sabberstone [7] を使用した．また，使用するトを行い，勝率を評価値としている．

デッキは選択肢が多くなりやすく，扱いが難しいとさ

また，Hearthstone は膨大な状態空間を持つが，れる CubeWarlock とした [13]．対戦回数は各手番でカードの順序を無視できる場合が多く存在する．この100 回ずつ行い，1 つの行動決定の制限時間は 3 秒と性質を利用して，カードの位置関係と相手の持つカーした．

ド情報を除くことで，ゲームの状態の抽象化を行う．
この抽象化した状態とその評価値を表形式で保存する

6. 2 性能評価のための対戦相手ことで，類似した状態の評価の際にプレイアウトせず性能を評価するために使用した対戦相手についてに評価が可能になるため，個体の評価が高速になる．

簡単に説明する．名前の先頭に PO が加えられたものは，状態の評価方法として第 5.2 節で示した評価方

6 実験による評価
6. 1 実験の目的と設定

法と同様のものを使用している．

• Greedy/PO+Greedy：簡単な状態評価関数

提案手法の有用性を評価するために，先行研究で提によって，選択肢にある行動を実行した後の状態

案されたプログラムとの対戦による比較実験を行なっの評価を行い，その評価値が最大となる行動を選た．
（なお，比較のために使用したプログラムの概要

択するプログラムである．

については第 6.2 節で説明する．
）また，RHEA に対• DynamicLookAhead(DLA)/PO+DLA：

する改良の効果を評価するため，改良を施さない元の深さを動的に制限した深さ優先探索によって行動

RHEA との対戦による比較実験を行った．

を探索する．比較的簡単な状態評価関数により，具体的には，以下の 5 つの実験を行った．まず，各行動が評価される．Hearthstone AI Compe-

ゲームの状態の評価方法の改良の効果を確認するた

tition 2020 の Premade Deck 部門で 1 位となっ

め，評価時間の計測を行った（第 6.3 節）．次に，遺たプログラムである．

伝的操作の改良による効果を評価するため，改良を• AlvaroMCTS/PO+AlvaroMCTS：最適化

施していない元の RHEA との対戦による勝率を測定を行なった評価関数に基づいた UCB 値によってした（第 6.4 節）．さらに，提案手法の有効性を評価

反復的に探索する手法である．Hearthstone AI

するために，Hearthstone AI Competition で提出さCompetition 2019 の Premade Deck 部門で 2 位れた従来手法との対戦による勝率を測定した（第 6.5となったプログラムである．

節）．また，提案手法のターン終了時の状態までの探• Monte Carlo Graph Search(MCGS) [4]：

索効率を確認するため，評価したターン終了時の状態

状態の抽象化とサンプリング，枝刈りによって数の比較を行った（第 6.6 節）．最後に，異なるデッ

MCTS の探索木の広がりを抑制し，相手の行動をキを用いた場合での提案手法の有効性を評価するたランダムと仮定することで，自分のターン終了以

めに，異なる 2 つのデッキを用いて従来手法との対降も探索することを可能としている．HearthstoneAI Competition 2019 の User Created Deck 部
門で 1 位となったプログラムである．

• Vanilla MCTS：提案手法との探索部分の比較のために実装した一般的な MCTS に基づくプロ
グラムである．評価方法は第 5.2 節で示した 評
価方法と同様である．

• Vanilla RHEA：提案手法による改良部分の比較のために実装した一般的な RHEA に基づくプ
ログラムである．交叉と突然変異が失敗した場
合，ランダムな一連の行動で作り変えるようにしている．行動決定方法は，最高の評価値を持つ

図4

Vanilla RHEA に対する各手法の勝率

個体の最初の行動を選択する．評価方法は第 5.2
節で示した評価方法と同様である．

場合による大きな差は見られない．これは，前の世代の評価の高い個体に対して遺伝的操作を行っている

6. 3 評価時間の計測ため，進化の回数が多いほど同じ個体が多く生まれ提案手法による個体の評価にかかる時間を計測しやすく，個体の評価値の平均に基づいた行動選択と，た．その結果，プレイアウトにかかる時間の平均は最大値に基づいた行動選択では差が生まれにくいた

122.06ms であり，抽象化した状態の比較にかかる時めだと考えられる．また，選択肢が非常に多い場合，間の平均は 0.013ms であった．そのため，このゲー

進化の回数が少なくなることで，母集団の個体が全てムの性質上類似した状態の評価が多くなりやすいこ

異なることがあるため，AVG と BEST による行動のとから，個体の評価時間を大幅に短縮できると考えら選択が一致する．このことから，この 2 つの行動決れる．

定方法では差が生まれにくいと考えられる．
一方，交叉に VC を用いた場合と PC を用いた場

6. 4 改良部分の性能評価

合とで比較すると，VC を用いた方が勝率が約 2%ほ改良を施していない元の Vanilla RHEA と提案手

ど高い．これは，実行不可能な一連の行動を抑える法とで改良部分の性能の評価を行った．その結果を図PC よりも，一様交叉を行う VC の方が探索範囲が広4 に示す．ここで，各手法の構成要素となるアルゴリ

いためだと考えられる．なぜなら，VC による交叉のズムの組み合わせは，以下の略記法を用いて示されて失敗率は PC と比べて約 10%ほど高く，実行不可能いる．

な行動が生成された場合，ランダムな一連の行動に• PC：提案手法による交叉

よって新しい個体を生成するためである．この理由か• PM：提案手法による突然変異

ら，VC の方が勝率が僅かに高くなるという結果に繋• VC：一様交叉

がったと考えられる．また，この理由は交叉を行わず• VM：一箇所のみの突然変異に突然変異のみを用いた PM+AVG の勝率が高い理• AVG：評価値の平均が最高となる行動を選択

由にもなっている．

• BEST：評価値が最高となる行動を選択

また，突然変異に PM を用いている場合は，VM

実験の結果，PC+PM+AVG が提案手法の勝率とを用いた場合と比べて勝率が約 5%から 10%ほど高いなっており，Vanilla RHEA に対して勝率が約 53%

傾向が見られる．これは，VM による突然変異では実となった．また，VC+PM+AVG と PM+AVG の勝

行不可能な行動が生成されない限り，個体の持つ一連率が約 56%と最も高い結果となった．

の行動の長さが変わらないため，評価の高い一連の行

行動決定方法の比較では，AVG と BEST を用いた動が生成されにくいからである．

図5

各対戦相手に対する提案手法の勝率以上の結果から，少なくとも CubeWarlock という

図6

初めて評価したターン終了時の状態の個数

デッキを扱う上では，一定の確率で一連の行動の長さが長くなるような変異が有効であると考えられる．

幅優先探索のような挙動になる．これにより，各ノードの評価値は次のノードの評価値の平均となるため，

6. 5 提案手法の性能評価

性能が低下したと考えられる．

各対戦相手に対する提案手法の勝率を図 5 に示す．

また，今回の実験において MCGS については，制縦軸は各対戦相手であり，横軸は提案手法の勝率であ限時間内に行動を選択できない場合が多く，その場合る．改良を施していない元の対戦相手に対する勝率はにはランダムな行動を実行するため，十分な性能を発

青色，第 5.2 節で示した評価方法に改良した相手に対揮できていない．

する勝率は水色で表している．提案手法は改良を行なっていない対戦相手に対しては約 75%以上の勝率

6. 6 初めて評価したターン終了時の状態数の比較

で勝ち越していることが分かる．また，評価方法とし提案手法による探索効率を比較するために，従来手て個別の静的な状態評価関数を用いているため，評価法との初めて評価したターン終了時の状態数の比較

方法で性能が変わる可能性がある．そのため，評価方を行った結果を図 6 に示す．このグラフの縦軸は初め法を 5.2 節と同様の評価方法に改良した相手に対してて評価したターン終了時の状態数を表し，横軸はゲー実験を行った．その結果，改良した対戦相手に対してムのターン数を表す．勝敗による状態数の増減を小さも約 60%以上の勝率で勝ち越していることが分かる．

くするために，対戦相手は Greedy で固定した．提案

対戦相手の手法の評価方法を第 5.2 節で示した方法

手法はターン終了時の状態の評価しか行わないため，に変更した結果，ほとんどの手法において性能が高全てのターンにおいて，最も多くのターン終了時のくなった．このことから，プレイアウトによるゲーム

状態を評価していることが分かる．他の手法では，制の状態評価方法は適している可能性がある．一方で，限時間内にターン終了時の状態まで到達することがPO+AlvaroMCTS は元の AlvaroMCTS よりも性能難しいため，評価できたターン終了時の状態数が少が低下している．これは，状態の評価方法を時間のかないことが分かる．特に 8 ターン目の場合，提案手

かるプレイアウトに変更したことで，反復回数が大法は 61 個のターン終了時の状態を評価したのに対し幅に減少したためだと考えられる．AlvaroMCTS でて，他の手法は最大 23 個と約 2.7 倍以上の差が確認

は，ノードを展開する際に訪問回数の閾値を設定しできる．これは，提案手法が常にターン終了時の状態ておらず，評価済みのノードに到達した時，すぐに展

評価に基づいた行動決定をしているのに対し，他の手開して次のノードの評価が行われる．そのため，評法はターン終了時まで探索しきれずに，途中の状態評

価の低いノードの展開を先送りにすることができず，価に基づいて行動決定しているためだと考えられる．

が約 40%であり，負け越していることが分かる．これは，提案手法が有利な状況の時に，誤った行動決定によって不利になってしまう傾向が Vanilla MCTS
よりも多く見られたことから，提案手法による遺伝的操作では効率的に探索することができず，最適な一連の行動を見つけることができていないためだと考えられる．
図7

ZooWarlock と MidrangeJadeShaman を用いた時の各対戦相手に対する提案手法の勝率

7 結論と今後の課題
本研究では，進化的アルゴリズムの一種である

つまり，他の手法はターン終了までを見通した行動決

RHEA を基にした Hearthstone の行動決定手法を提定を行えていないため，提案手法の方が強力であった

案した．RHEA による行動決定を Hearthstone に適と考えられる．

用するために 3 つの改良を施した．具体的には，個体

一方で，Vanilla MCTS は比較した手法の中では強力であった．これは，ターン終了時の状態を評価しの評価時間を削減と実行不可能な行動の生成の抑制，
ランダム性を考慮した行動決定方法である．

なくとも，有望な行動に対して深く探索を行うため，提案手法の性能を評価するために，Hearthstone に最適に近い行動を見つけることができているからだ

おいて実験を行った結果，扱いが難しいデッキを用いと考えられる．しかし，有望な行動と判断されなかった場合，提案手法は従来の木探索手法に対して，60%た行動が最適な行動だったという場合に対応できない

以上の勝率で勝ち越したが，扱いが簡単なデッキを用ことから，提案手法の方が僅かに強力であるという結いた場合，良い性能を示すことができなかった．この果に繋がったと考えられる．

結果から，提案手法は扱いが難しいデッキにおいて有効な手法であると考えられる．そのため，デッキ毎に6. 7 異なるデッキでの性能評価

遺伝的操作を調整するなどの改善の余地があると考

これまでの実験で使用したデッキである CubeWar-

えられる．

lock の他に，ZooWarlock と MidrangeJadeShaman

今後の課題としては，デッキ毎に適した遺伝的操作と呼ばれるデッキを用いて第 6.3 節と同様の実験を行や行動決定方法を考える必要がある．また，提案手なった．この 2 つのデッキは比較的単純で扱いやすい

法は探索情報をほとんど活用していない．そのため，デッキであることから，従来の木探索手法と相性が良

RHEA の研究 [12] [8] で提案された木構造による探索

いと考えられる．これらのデッキを用いた時の各対戦情報の保持と活用を行いたいと考えている．この木構

相手に対する提案手法の勝率を図 7 に示す．

造を取り入れることにより，評価値が高くなりやすい

図 7 から，PO+AlvaroMCTS を除く他の手法に対方向に突然変異の範囲を絞ることや，初期集団の生成して勝率が 50%前後という結果となった．これは，手の際に偏りを持たせることが可能となるため，探索性

番によってゲームの状況が序盤から有利になることが能が向上することが期待される．また，抽象化のアイあり，ゲーム終了までその状況が覆らないことがある

デアを組み合わせた有向非巡回グラフの構造に拡張からだと考えられる．つまり，ゲーム毎に有利な手番することも検討している．

と不利な手番が存在するため，勝率が 50%に近づいたと考えられる．このような状況下で，提案手法の方

参 考 文 献が PO+Greedy と PO+DLA より，誤った行動決定[ 1 ] Blizzard Entertainment, Hearthstone webpage, https://playhearthstone.com, accessed on
07.29.2022.

が少なかったため僅かに勝率が高い結果となった．
一方で，提案手法は Vanilla MCTS に対して勝率[ 2 ] N. Brown. and T. Sandholm, ”Superhuman AI
for multiplayer poker,” Science, Vol. 365, No. 6456,
pp. 885–890, 2019
[ 3 ] C. B. Browne, E. Powley, D. Whitehouse, S. N.
Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener,
D. Perez, S. Samothrakis, and S. Colton ”A surveyof monte carlo tree search methods,” IEEE Transactions on Computational Intelligence and AI ingames, Vol. 4, No. 1, pp. 1–43, 2012.
[ 4 ] J. S. B. Choe, and J. K. Kim, ”Enhancing montecarlo tree search for playing hearthstone,” 2019
IEEE Conference on Games (CoG), IEEE, pp. 1–7,
2019.
[ 5 ] A. Dockhorn, M. Frick, U. Akkaya, and R.
Kruse, ”Predicting opponent moves for improving
hearthstone ai,” International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, Springer, pp.
621–632, 2018.
[ 6 ] A. Dockhorn, J. Hurtado-Grueso, D. Jeurissen,
L. Xu, and D. Perez-Liebana, ”Portfolio search andoptimization for general strategy game-playing,”
2021 IEEE Congress on Evolutionary Computation(CEC), IEEE, pp. 2085–2092, 2021.
[ 7 ] A. Dockhorn. and S. Mostaghim, ”Introducing the Hearthstone-AI Competition,” CoRR, Vol.
abs/1906.04238(2019).
[ 8 ] R. D. Gaina, S. Devlin, S. M. Lucas, and D.
Perez-Liebana, ”Rolling horizon evolutionary algorithms for general video game playing,” IEEE
Transactions on Games, Vol. 14, No. 2, pp. 232–242,
2021.
[ 9 ] N. Justesen, T. Mahlmann, and J. Togelius,”Online evolution for multi-action adversarial
games,” European Conference on the Applications of Evolutionary Computation, Springer, pp.
590–603, 2016.
[10] J. Li, S. Koyamada, Q. Ye, G. Liu, C. Wang, R.
Yang, L. Zhao, T. Qin, T. Y. Liu, and H. W. Hon,
”Suphx: Mastering mahjong with deep reinforcement learning,” arXiv preprint arXiv:2003.13590,
2020.
[11] D. Perez, S. Samothrakis, S. Lucas, and P.
Rohlfshagen, ”Rolling horizon evolution versus tree
search for navigation in single-player real-time
games,” Proceedings of the 15th annual conference on Genetic and evolutionary computation, pp.
351–358, 2013.
[12] D. Perez Liebana, J. Dieskau, M. Hunermund,
S. Mostaghim, and S. Lucas, ”Open loop searchfor general video game playing,” Proceedings of the2015 Annual Conference on Genetic and Evolutionary Computation, pp. 337–344, 2015.
[13] M. Swiechowski, T. Tajmajer, and A. Janusz,”Improving hearthstone ai by combining mcts andsupervised learning algorithms,” 2018 IEEE Conference on Computational Intelligence and Games(CIG), IEEE, pp. 1–8, 2018.
[14] D. Wang, and T. S. Moh, ”Hearthstone AI:
Oops to well played,” Proceedings of the 2019 ACM
Southeast Conference, pp. 149–154, 2019.
[15] S. Zhang and M. Buro, ”Improving hearthstone
AI by learning high-level rollout policies and bucketing chance node events,” 2017 IEEE Conference
on Computational Intelligence and Games (CIG),
IEEE, pp. 309–316, 2017.