深層強化学習を駆使してカタン最強プレイヤー達に挑んでいく。

Article

2019.3.16

みなさまは、現在、ハマっているゲームはございますでしょうか。

今、私のスプラトゥーン2の総プレイ時間は1500時間ほどとなりますが、
よく、「その時間を英語の勉強にでも、あてていたらペラペラになってたね」というお言葉をいただきます。
よろしいですか。

やらないから。絶対1500時間あってもやらないから。やれないから。
だって、スプラトゥーン2をやる前から、その時間はあったはずですから。
英語の勉強をやっていたのに、スプラトゥーン2をやり始めたことで、その時間が減ったのならわかりますが、
なぜ、もともとやっていなかったことが急に出てくるのでしょう。

つまり、私のゲームプレイ時間は、他の何かに当てることができる時間ではなく、
日常では味わいづらいエキサイティングな瞬間を感じるための、もうどうしようもなく必要とする時間であって、
いわば、ぼーっとスマホをいじっているだけの時間の上位互換となります。

そのような詭弁を懐にしまいながら、
ゲームのせいで激減した読書時間の結果としての積み本を
苦虫を噛み潰したような顔で横目に見ながら、
今日もコントローラーを握っています。

さて、今回は、ビデオゲームではなく、
世界的に大ヒットしているボードゲーム「カタン」を題材として、
データサイエンティストである筆者が深層強化学習を駆使して
最強ゲーマーたちに勝負を挑んでいった記録を記します。

[目次]
(1)カタンとは。交渉と陣取りが織りなす最強ボードゲーム
 (2)カタン最強ゲーマーの紹介
 (3)深層強化学習を駆使したカタン最強のアルゴリズム
 (4)都内でカタンを遊べる最強のお店
 (5)火花が飛び散る最強の勝負

| (1)カタンとは。交渉と陣取りが織りなす最強ボードゲーム

カタンとは、1995年にドイツで開発・発売された3、4人プレイ用のボードゲームとなります。
プレイヤーは、開拓者となって、サイコロの出た目に応じて、資源を取り合い、
カタン島に、道や開拓地を作っていきながら、ポイントを稼ぎます。
最終的に、いちばん早く10ポイントとなったプレイヤーが勝利となります。

このゲームは、ドイツ年間ゲーム大賞、ドイツゲーム大賞1位、はじめ、
世界中で様々な賞を受賞しており、世界中で2000万個以上販売の大ヒットとなっております。

大まかなゲームの手順は下記となります。

1) 島にエリアと番号を配置する。エリアには、森、畑、鉱山などがありそれぞれもらえる資源が異なる。
2) プレイヤーの初期開拓地と道をエリア沿いに置く。
3) 以降、各プレイヤーがサイコロを振って以下を繰り返す。
　- サイコロの出た目と同じ番号のエリアに沿った場所に開拓地があるプレイヤーは資源を受け取る。
　- 資源を消費することで、道（木材1個、レンガ1個）、開拓地（木材１個、レンガ１個、小麦１個、羊毛１個）などを建設できる。
　- 建設に足りない資源は他のプレイヤーと交渉して、交換できる。
　- 資源を消費して、発展カードという特別な効果(ポイントゲット、道をひけるもの、など)を発揮するカードをひくことができる。
　- 資源を消費して、開拓地を都市に発展させるとポイントゲット、および次回以降、該当エリアの資源が2倍もらえる。
4) 開拓地を建設すると1ポイントゲット、発展カードの勝利ポイントで1ポイントゲット、
　　最も長いつながった道(最長交易路)を建設したプレイヤーは2ポイントゲット、などを経て、
　　いちばん早く10ポイント獲得したプレイヤー勝利。

初期は、道や開拓地を作ることを通して領土を広げていくこと、
中盤からは、どのような手段でいかに早くポイントを稼ぐことを目指すかが重要となります。
（カードでポイント狙うか、開拓地、都市化でポイント狙うか、など）

| (2)カタン最強ゲーマーの紹介

カタンについて説明したところで、今回カタンを一緒に遊んでくれるメンバーを紹介します。

1人目は、
ラーメン、プロレス、アイドル好きの
ダイレクトマーケティングの天才、
ダイナマイトまことさんです。

カタン歴は浅いものの、おそろしく興味の守備範囲が広いアプリ廃人であり、
最近はiphoneのカタンアプリを常時立ち上げております。
電話やメール、LNEやFacebookチャットで連絡がとれないときでも、
アプリでカタン島にいくと、会うことができます。

2人目は、
こよなくゲームを愛するマルチゲーマーであり、
スプラトゥーン2のブキトッププレイヤー、
socha(そちゃ)さんです。

これまたカタン歴は浅いものの、
スプラトゥーン2はXP2500超え＆ブキトップ、
テトリス99はランキング1位獲得常連、
マリオカート非公式大会準優勝、という、
花京院と遊戯王と両さんを足し合わせて、毒味を抜いたようなゲームマスターです。

そして、3人目は、私、mirandora（ミランドラ）。
データサイエンティストYouTuberであり、
いまはスプラトゥーン2に、ハマっておりますが、
どちらかというとRPGが好きなタイプではあります。
ゲーム中の独り言が多いので、そもそも対面タイプのゲームは不向きです。

この3人は飲み仲間でありまして、
飲む前には、必ずボードゲームカフェに寄って遊んでいるのです。

しかし3人全員が初めてやるボードゲームでも、
毎度毎度、私が2人に惨敗する日々が続いておりました。
いつも帰りの地下鉄の中では、
「屈辱っ…!圧倒的屈辱っ…!!己のクズのような思考力っ…!!努力で覆すことのできない絶対的な壁っ…!!」
と、ひとり、カイジのように慟哭(どうこく)しておりました。

そして、ついに、先月、深層強化学習を駆使してカタンでリベンジをすることを
2人に宣戦布告したのでした。（ざわ…ざわ…）

| (3)深層強化学習を駆使したカタン最強のアルゴリズム

カタンは、サイコロを2つ出した合計の目の数と同じ目のマスに沿った場所に開拓地があるプレイヤーが、
そのマスのエリア（森林、畑、など）に応じて、資源をもらうことができるため、
マップの目とエリア特性に応じて、どこを最初の開拓地として選択するか、
という初手が非常に重要となります。

たとえば、下記の状態の場合、
白色の開拓地のプレイヤーは、
サイコロの目が合計3の場合：羊1
サイコロの目が合計5の場合：麦1
サイコロの目が合計8の場合：羊1
を得ることができます。

よって、まずシンプルに、
・2つのサイコロの合計の目が、どの数が出やすいか
・上記サイコロの目の出やすさによって、各開拓地候補が、各資源を得られる期待値、
を算出することにします。

[各エリアの数字の目の出やすさのヒートマップ]

[上記マップのポイントごとの得られる資源の期待値一覧 ※一部抜粋]

次に上記を参考にして、初期配置となる2つの開拓地を選んで入力すると、
初期ステータスから、どのような手を選択すると、どのような状態に遷移していくか、を算出するプログラムを書いていきます。

[各ターンにおいて、選択した手における状態遷移 ※一部抜粋]

最後に、上記ステータス変化を、膨大な数の取りうる手で試行したあと、
もっとも少ないターン数で10ポイントとなる可能性の高い手順をアウトプットするプログラムを作ります。

[もっとも少ないターン数でゴールする可能性の高い手順 ※一部抜粋]

なお、最適な手を探索する過程は深層強化学習を用いております。（いずれ、作成したプログラムも公開するかもしれません）

深層強化学習の実装は、下記書籍を参考にしました。

以上、簡単ではありますが、今回用いるプログラムの紹介となります。
この武器を手に、最強ゲーマーたちに挑んでいきましょう。

| (4)都内でカタンを遊べる最強のお店

都内にはいくつかボードゲームを遊べるスポットがあるのだと思いますが、
私たちが愛用しているのは、JERRY JERRY CAFEとなります。

カタン以外にも、世界中の多数のボードゲームがあり、
誰もやったことがないものの簡単なルールのゲーム(しかし奥が深い)もあるため、
ゲームの練度に関わらずに楽しむことができます。
※ときどき、全く理解できないゲームを手にしてしまうときもありますが。

この日は、雨の降る中、
駅から10分ほど歩き、表通りから住宅街に少し入りかけたところにある、お店に参戦しました。

それではいよいよ、ゲームを始めていきましょう。

| (5)火花が飛び散る最強の勝負

まずはマップの情報を入力し、どこのポイントに開拓地を置くべきかを算出します。

さて、最強の初期ポジションがわかったところで、
算出された計算結果は、、、84ターン後、私はこのゲームを勝利している！

、、、と言いたいところですが、いきなり、つまづきます。
なんと、計算結果で最適と算出されたポイントを、sochaくんに獲られてしまいました。
さすが、花京院のような男。恐ろしいぜ。

[『ジョジョの奇妙な冒険第3部』花京院 vs ダービー・ザ・プレイヤーより]

初期配置を入力しなおして、
再度、最適な手を計算しなおします。
まだだ、、まだ勝つ手は存在する、！

しかし、その後も、幾度となく、計算結果で出された手を、
sochaくんに妨害されます。
そう、このプログラムの欠点は、
他のプレイヤーの手を予測仕切れないところにあります。

なんとか、次点の手を打っては再計算するものの、
徐々に最善手のパターンからは遠のいていきます。

そして、この男も黙ってはおりません。
ダイナマイトまこと「この離れた場所に道をまたいで開拓地を作ることは可能かな?」
socha「あり得ないです。できません。」
ダイナマイトまこと「それでは、ここに開拓地を作るために必要な障害は何かあるかな?」
socha「ありすぎてびっくりします。」

ダイナマイトまこと「ぬぅ…。お前たちは俺の心を点火（イグニッション）させてしまったようだぜ…。
とくと味わうがよい、”羊がため”！！」
socha、mirandora「な、なにぃッ、、！！”羊がため”…だとッ、、!?」

羊がためとは、上記のように、羊の資源をもらえる牧草地に開拓地を固めた上に、
さらに羊2つを消費して、好きな資源と交換できる「港」がついている状態となります。
もし開拓地の1つを都市に発展させると、2倍の資源がもらえますので、計4つの羊を手にすることができます。
つまり、2つのサイコロの合計値が「3」となれば、好きな資源2つを得ることができるという状態です。
ちなみに、3となる確率は約6%(2/36)であり、非常に低い確率です。
※なお、ここまで詳細に解説した上で恐縮ですが、
　「羊がため」というカタン用語はありません。ダイナマイトまことさんの造語です。

まずい、sochaくんの、クレバーな戦略と、
ダイナマイトまことさんの、クレイジーな戦略によって、
再計算が追いつかないッ…!

そして、、

※黄色:sochaくん、白色:ダイナマイトまことさん、黒色:mirandora