JAIST Repository
https://dspace.jaist.ac.jp/

Title

二人不完全情報ゲーム『ガイスター』におけるCFRおよび利得評価関数を用いた混合戦略AIの研究

Author(s)川上, 直人; 池田, 心Citation

情報処理学会第45回GI研究発表会, 2021‑3

Issue Date

2021‑03‑05

Type

Conference Paper

Text version

publisher

URL

http://hdl.handle.net/10119/18209

Rights社団法人 情報処理学会, 川上直人, 池田心, 情報処理学会第45回GI研究会, 2021. ここに掲載した著作物の利用に関する注意 本著作物の著作権は情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。Notice for the use of this material:
The copyright of this material is retained by
the Information Processing Society of Japan(IPSJ). This material is published on thisweb site with the agreement of the author (s)and the IPSJ. Please be complied with
Copyright Law of Japan and the Code of Ethicsof the IPSJ if any users wish to reproduce,
make derivative work, distribute or makeavailable to the public any part or whole
thereof. All Rights Reserved, Copyright (C)Information Processing Society of Japan.

Description

情報処理学会第45回GI研究発表会, 2021‑3, オン
ライン開催

Japan Advanced Institute of Science and Technology

Vol.2021-GI-45 No.4
2021/3/5

情報処理学会研究報告
IPSJ SIG Technical Report

二人不完全情報ゲーム『ガイスター』における CFR および利得評価関数を用いた混合戦略 AI の研究
川上 直人1,a)

池田 心1,b)

概要：近年，囲碁や将棋などの完全情報ゲームだけでなく，麻雀，ポーカーといった不完全情報ゲーム
において，トッププレイヤの実力を上回る AI が報告されている．Head’s up limit porker では 2015 年にナッシュ均衡に近い解が得られた．一方，駒移動型の二人零和不完全情報ゲーム「ガイスター」では，3× 2 盤・短手数の場合を除き，プログラムが人間の実力を上回るなどの成果が報告されていない．特に，

GAT2020 杯ガイスター AI 大会で優勝した「紫駒 AI」は，初期配置以外に確率的な行動が無く，戦略を知っている相手には弱い．例えば，紫駒 AI は青駒をめったに相手駒に隣接させず，赤駒をよく隣接させる特徴がある．そのため，隣接させてきた場合には赤駒だろうという推測が容易にできてしまう．そこで本稿では 4 × 4 盤ガイスターにおいて，確率的な行動を取らせるために CFR を用いる．ただし，CFR の計算量を抑えるために数手で木の展開をやめ，未決着なリーフノードにおいて利得評価をおこなう関数を設計する．本稿では，紫駒 AI とそれに付け込む AI を含む 4 種類のベンチマークプレイヤとの対戦実験により，提案手法による AI2 種類の性能評価をおこなった．結果，ベンチマーク同士の対戦では，どの AI についても勝率 15%を下回る苦手な相手が存在した一方で，提案手法では最も苦手な対戦相手に対して勝率24%, 19%を挙げた．

A study on mixed strategy AI using CFR and gain evaluation functionsin the two-player imperfect information game ”Geister”
Naoto Kawakami1,a)

1. はじめに

Kokolo Ikeda1,b)

され，一部のゲームで大きな成果を挙げた Counterfactual

Regret minimization (CFR)[2] である．有名な例として，

近年，囲碁や将棋など完全情報ゲームの人工知能（AI)2015 年には，CFR の性能をさらに高めた CFR+[3] によは，トッププレイヤの実力を上回るなど大きな成果を挙げ

り，ヘッズアップリミットホールデムポーカーにおいてている．2015 年には，モンテカルロ木探索と深層学習を組ナッシュ均衡に近い戦略が計算された [4]．もう 1 つのア

み合わせた囲碁 AI『AlphaGo[1]』が，プロ囲碁棋士にハンプローチとして，深層強化学習が挙げられる．2019 年にはディキャップなしで初めて勝利し，世間から注目を集めた．

深層学習を用いた麻雀 AI『Suphx[5]』が天鳳十段を達成し完全情報ゲームが大きな成果を挙げている一方，ポーた．一方，『ガイスター』などまだ十分強いコンピュータプ

カーや麻雀といった不完全情報ゲームの AI も注目され，レイヤが報告されていないゲームもある．

大きな進歩を遂げている．不完全情報ゲームは，ゲームのガイスター [6] は青駒，赤駒をチェスのように取り合う，状態を完全には観測できないため，ゲーム木探索をおこな

二人零和確定不完全情報ゲームである．このゲームの面白

うのが困難である．アプローチの 1 つは，2008 年に提案

い点は，まだ取っていない相手駒の色を観測できない点で

1

a)
b)

北陸先端科学技術大学院大学
Japan Advanced Institute of Science and Technology
keimahatokusyu@gmail.com
kokolo@jaist.ac.jpⓒ 2021 Information Processing Society of Japanあり，相手駒の色をそれまでの動きから推測したり，逆に推測されにくい動きをすることが重要である．ガイスター

AI の研究は発展途上である．例えば紫駒 AI[9] と呼ばれる

1

Vol.2021-GI-45 No.4
2021/3/5

情報処理学会研究報告
IPSJ SIG Technical Report

手法は，2020 年の AI 大会で優勝しているが，駒の動きに法則性があり，行動から状態を推定されやすい．具体的には，相手駒に隣接させる駒はほとんど赤駒であり，これを知られてしまうと簡単に負けてしまう．また，短い手数制
限を加えた 3 × 2 盤のガイスターでは，確率的な行動戦略が分析されているが [13]，終局まで展開したゲーム木を考えているため，計算量が大きい．
本稿では，4 × 4 盤のガイスターにおいて，ガイスターを表現するゲーム木を数手先までしか展開しないことで，現実的な時間で確率的行動を取らせる方法を提案する．本稿では，ゲーム木のリーフノードに対して期待利得を推測するヒューリスティックな評価値を与える．評価値の与え方には様々なバリエーションが考えられるが，本稿では 2 つの方法を試みる．まず，未決着なリーフノードを引き分けと評価する方法を試す．次に，完全情報なガイスターについて真の勝敗を計算し，リーフノードが持つ完全情報盤面

図 1

ガイスター初期配置例を評価する方法を試みる．なお，本内容は第一著者の修士論文研究 [15] の一部である．

2 章ではガイスターのルールについて述べる．3 章ではガイスターの先行研究を紹介する．4 章では先行研究の課となる．なお赤駒は盤外へ脱出できない．
ガイスターでは次の 3 条件のいずれかを満たしたプレイ
ヤが勝利となる．

題について述べ，5 章では提案手法を紹介する．6 章では• 相手の青駒を全て取る

提案手法の事前準備として完全情報局面の勝敗計算をおこ• 自分の赤駒を全て取らせる

なう．7 章では対戦実験をおこない性能などを評価する．8• 自分の青駒を 1 つでも脱出させる（ゴールに移動して章では本稿の総括をおこない今後の方針について述べる．

2. ガイスターについてから，もう 1 手番必要）

3. ガイスターの先行研究

ガイスター（Geister）[6] は，2 種の駒を用いて遊ぶ二人

ガイスターの AI プレイヤについて，完全情報ゲーム

零和確定不完全情報ゲームである．ドイツのゲームデザイの手法を応用した研究が報告されている．三塩・小谷は，ナーであるアレックス・ランドルフ氏によって考案され，モンテカルロ法を不完全情報ゲームに応用し，さらにプ

1982 年，ドイツ年間ゲーム大賞にノミネートされた．ガイ

レイアウト回数の改善をおこなう手法として Using Past

スターの大きな特徴として，まだ取っていない相手駒の色

Playout(UPP) を提案した [7]．結果，改善前のモンテカルを観測できないことが挙げられる．相手駒の色は，それまロ法に対し，勝率 55%を達成した．佐藤は，強化学習を用

での動きなどから推測する必要がある．

い，さらに短い必勝手を見落さないよう必勝手の検出をおガイスターでは，6 × 6 のマスからなる 36 マスの盤面こなった [8]．具体的には，相手駒を「取ったら赤，脱出を用いる．最初，各プレイヤは青駒，赤駒を 4 個ずつ，自時は青に変化する駒（紫駒）」とみなすことで，最悪の状

陣 8 マスに自由な組み合わせで初期配置する．初期配置を況を想定できるようにした．結果，モンテカルロプレイヤ

おこなった盤面例を図 1 に示す．本稿では，マスの座標をに勝ち越し，ランダム AI には勝率約 70%を達成した．川a-f，1-6 の組み合わせで表現する，先手から見て，左上を上・橋本は，佐藤の研究 [8] で用いられた「紫駒」をゲー

a1，右上を f1，左下を a6，右下を f6 とする．先手自陣はム木探索に応用し，「紫駒 AI」を提案した [9]．紫駒 AI は，b5, e6 を対角線とする長方形領域，後手自陣は b1, e2 を対GPW2017 杯ガイスター大会優勝 AI に圧勝し，GPW2018

角線とする長方形領域である．
ゲームは交互着手により進行する．手番プレイヤは自分

杯ガイスター AI 大会では準優勝，GAT2020 杯ガイスター

AI 大会では優勝した．

の駒を 1 つ選び，上下左右 4 マスのいずれかに動かす．自

確率的な行動戦略を立てるアプローチとしては，CFR[2]駒があるマスには移動できないが，移動先に相手駒があれをベースとした研究が報告されている．Chen Chen, To-ばそれを取り，色を観測できる．図 1 の矢印が書かれたマ

moyuki Kaneko は，Chance-sampled CFR[11] および Pure

スはゴールを表しており，先手は a1, f1，後手は a6, f6 をCFR[12] を 3 × 2 盤のガイスターに適用し，戦略の分析，計

ゴールとする．ゴールに自分の青駒が置かれている場合，算時間の比較をおこなった [13]．文献 [13] では，2〜20 手

次のターンにその駒を盤外へ脱出させることができ，勝利の手数制限を加えた 3 × 2 盤のガイスターについて，ナッⓒ 2021 Information Processing Society of Japan2

Vol.2021-GI-45 No.4
2021/3/5

情報処理学会研究報告
IPSJ SIG Technical Report

シュ均衡を近似的に求めた．しかし，ゲーム木を全て展開しているため計算量が大きく，より大きなガイスターを扱うことは難しい．そこで同著者らは，深層学習の技術を

CFR に取り入れた手法 Deep CFR により，6 × 6 盤ガイス
ターの AI を開発した [14]．結果，ランダムプレイヤに勝率 70%〜85%と学習には成功したものの，実験時間内では十分に学習が進まなかった．具体的には川上・橋本の研究で開発された深さ 1 の PurpleAI に対して，履歴を考慮しない AI プレイヤでは勝率 38%，履歴を考慮する AI プレ
イヤでは勝率 34%となった．

4. 先行研究の課題
2020 年のガイスター AI 大会で優勝した紫駒 AI[9] は，駒の移動に法則性があり，それを知った相手には簡単に負けてしまう課題がある．紫駒 AI に限らず，確定的な行動をおこなうプレイヤは，どのような局面でどのような行動を取るかを対戦相手に完全に熟知された場合，行動から状態を絞り込まれるなど，付け込まれる余地が生まれやすい．

図 2

素朴なゲーム木（終局まで展開）

本研究では，確率的行動を取ることで，付け入る余地を減らすことを試みる．ガイスターは二人零和不完全情報
ゲームであるため，最も苦手な相手に対する勝率を最大化する戦略は，ナッシュ均衡に従う戦略となる．そのため，究極的にはナッシュ均衡を求めることがゴールとなる．
ガイスターはゲーム木によって表現することができる
ため，ゲーム木を生成し，CFR[2] などを適用することでナッシュ均衡を求めることができる．ガイスターを表現するゲーム木の概念を図 2 に示す．図 2 は，先手初期配置，
後手初期配置，先手駒移動，後手駒移動…の方法を木構造で表したものであり，各ノードには状態が書かれている．
特に，深さ 2 以降のノードは完全情報な局面を持つ．完全情報ゲームと大きく異なる点は，情報集合と呼ばれる，手番プレイヤにとって区別できないノードのグループが存在する点である．ガイスターにおける情報集合は，まだ取っていない相手駒の色組み合わせのみが異なるノード同士であり，同じ情報集合に属するノードでは同じ行動戦略を立てる必要がある．例えば，図 2 の緑破線は情報集合の一例
である．結ばれた 2 局面は先手番にとって互いに区別できないため，異なる行動戦略を立てることができない．

図 3

評価値を与えたゲーム木（深さ 4 まで展開する例）

先行研究では，短い手数制限を加えた 3 × 2 盤のガイス

ノードの良し悪し（期待利得）を推測する評価値を与える

ターについてナッシュ均衡を求めた [13]．しかし，終局ま方法を提案する．このような限定的なゲーム木を生成するで展開したゲーム木を扱うため計算量が大きく，それ以上ことで，現実的な時間で，現局面に対する確率的な行動を大きなサイズのガイスターについては現実的な計算量で行得ることが期待できる．図 3 に，提案手法の概念を示す．

動を求めることができない．

図 2 と比べると，3 手先以降（深さ 5 以上）のノード展開

5. 提案手法
5.1 アルゴリズムの概要をおこなわず，深さ 4 のノードに評価値を与えているところが異なる．図 3 は，完全情報なガイスターの勝敗を評価値とした例であり，どのリーフノードが持つ盤面も先手が本研究では，ゲーム木展開における計算量の問題を解決

後手青駒を取り勝利することから勝率 1.0 と推測している．

するため，ゲーム木を数手先までしか展開せず，リーフ

具体的な手順を以下に示す．ただし，駒の初期配置につⓒ 2021 Information Processing Society of Japan3

Vol.2021-GI-45 No.4
2021/3/5

情報処理学会研究報告
IPSJ SIG Technical Report

いては単純なランダムでおこなう．リーフノードへの具体

表 1

勝敗と局面数（先手目線）
全局面数
71,001,840

的な評価値の与え方は次節で述べる．

勝ち局面数49,821,729

負け局面数

17,051,259

引き分け局面数

4,128,852( 1 ) 現局面（過去の着手を含まない）について，先手の駒色，後手の駒色をそれぞれ隠した局面 S を生成する．

( 2 ) S をルートノードとし，ある深さまで展開したゲーム
木を生成する．自分は深さ偶数手番とする．

( 3 ) リーフノードについて，評価値を与え，これを利得の代わりとする．

( 4 ) 生成したゲーム木において，CFR をおこない，混合戦
略（各ノードに対する確率的行動）を計算する．

( 5 ) 現局面と対応するノードを参照し，確率的なアクションを取る．現局面に対応するノードとしては，深さ 2のノード（初期配置が終わった直後の局面を持つ）であって，現局面と自分の色配置が一致するものを任意に取る．

5.2 リーフノードの利得評価関数
未決着なリーフノードについて，どのくらいの利得を期待できるかを評価するため，利得評価関数を設計する．最も素朴な評価は，未終局なら引き分け扱いとする方法だ

図 4

最長勝ち局面 (47 手)

図 5

最長負け局面 (48 手)が，ゲーム序盤ではリーフノードの多くが未決着となるため，行動の良し悪しを評価することができない．実際には，
リーフノードは完全情報な局面を持つので，その局面を評価することで，単に引き分けを返すよりも高い精度でリー
フノードの良し悪しを評価できるのではないかと考えられる．そこで本稿では，各リーフノードについて，そのリー
フノードが持つ完全情報局面の評価をおこなう．評価には様々な方法が考えられるが，本研究では，リーフノードが持つ完全情報盤面から完全情報なガイスターをプレイした
際の真の勝敗を求め，その勝敗を評価値として用いる．
本稿では，後退解析を用いて，互いに勝ちを目指して最善を尽くした場合の勝敗分を記録したデータベースを生成する．後退解析は，勝敗が決定した局面から手を戻していき，戻した局面の勝敗を決定していく手法である．相手に負け局面を渡すことができる局面は勝ち，どのように手を進めても相手に勝ち局面を渡してしまう局面は負けとなり，る局面のうち片方のみを保存するなど，空間計算量につい最後まで勝敗が確定しなかった局面は引き分けとなる．こて基本的な改善をおこなっている．

れは，相手の勝ちを阻止できる一方で相手に負け局面を渡すこともできないためである．

6. 完全情報局面の勝敗計算

勝 敗 数 の 結 果 を 表 1 に 示 す ．表 1 に 示 す よ う に ，71,001,840 局面のうち，先手勝ちは 49,821,729 局面，先手負けは 17,051,259 局面，引き分けは 4,128,852 局面となった．また，最長勝ち局面は図 4 の局面となり 47 手勝

本稿の利得評価関数を用いるための事前準備として，完ち，最長負け局面は図 5 の局面となり 48 手負けとなった．

全情報なガイスターにおける真の勝敗を計算した．具体的

さらに，勝ち局面数と手数の関係は表 2，負け局面数と手には，4 × 4 盤，各プレイヤの青赤が 2 個以下の完全情報局

数の関係は表 3 のようになり，手数が大きくなるごとに局面を対象とし，後退解析をおこなった．実行環境として，面数が少なくなることを確認した．

Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz のシングル
スレッドを用いたところ，実行時間は 311.9 秒，メモリ使
用量は 8124.4[MB] となった．ただし，左右反転で一致すⓒ 2021 Information Processing Society of Japan

7. 対戦実験
提案手法の性能を評価するため，ベンチマークプレイヤ

4Vol.2021-GI-45 No.4
2021/3/5

情報処理学会研究報告
IPSJ SIG Technical Report
表 2

表 3

手数と負け局面数
2 7,514,602• 猪突猛進1

手数と勝ち局面数
21,405,186

3

13,300,150

43,239,989

5

4,188,579

6

1,690,200

72,643,147

8

957,9029

1,993,674

10

846,053が最小の青駒を選ぶ．複数あれば，最も上段，それ

11

1,661,412

12691,214でも複数あれば，最も左列にある駒を選ぶ．

13

1,312,694

14

581,617– ゴールへなるべく近づけるように移動する．移動方

15

1,020,795

16

465,892

向が複数考えられるときは，上方向にゴールがある

17

762,84918

351,644

として，左，右，上，下の順で優先し，移動方向を選19548,51520

255,988

ぶ．ただし本実験の設定では，下が選ばれる状況は

21

386,89722

177,50223

258,26824

114,14225

153,386

26

71,67527

88,87928

44,96929

50,57530

25,19631

26,11532

12,96833

12,31934

5,893• 紫駒 AI

35

5,096

36

2,458

– 相手駒を「取ったら赤，脱出時は青に変化する駒（紫

37

2,085

38

920

39

736

40

286

駒）」とみなし，深さ 5 の MinMax 法をおこなう．

41

264

42

108

43

80

44

28

からどれだけ離れているか」の 2 つから作る．

45

24

46

11

– 詰みを検出できるなどの強みがあり，GPW2018 杯準

47

4

48

2

優勝 AI，GAT2020 杯優勝 AI にもこの手法が用いら– 1 つの青駒をひたすらゴールへ近づける．取られたら別の青駒で同じことをする．

– 具体的には近い方のゴールまでのマンハッタン距離発生しない．

– もし，選んだ青駒がゴールにある場合は，その駒を脱出させる．

– 基本的には，近づけた駒を取らない相手に強く，近づけた駒を積極的に取る相手に弱い．

– 評価関数は文献 [9] と同様，
「青の個数」「駒がゴール

れた．
を用意し対戦実験をおこなう．対戦実験では，対戦相手が敵対的に戦略を選ぶ状況における付け込まれにくさの指標– 一方，赤ばかり相手駒に隣接させるなど，色を簡単に推定できるような動き方をする．

として，最も苦手な対戦相手に対する勝率（最小勝率）に• アンチ紫焦点を当てる．また，推定のされやすさなどを分析するた– 紫駒 AI の弱点を突くプレイヤ．

め，駒の移動に関する統計量を取る．さらに，勝敗の内訳– 紫駒 AI が最初に突っ込ませる駒はほとんど赤だろうなどを調べ，どのような方法で勝利・敗北しているかを考察する．

という仮説を基に設計する．

– 自駒に初めて隣接した相手駒を赤とみなし，ゲーム終了まで絶対取らないようにする．それ以外の駒は，7.1 実験方法
4 × 4 盤のガイスターについて対戦実験をおこない，勝敗などを調査する．まずベンチマークプレイヤ同士の総当たり戦をおこない，勝敗数などを分析する．その後，提案手法とベンチマークプレイヤを戦わせ，最も苦手な対戦相取っても良い駒（青）とみなす．

– 自駒に隣接してくるまでは，紫駒 AI と同様の意思決定をおこなう．

– 深さ 5 の MinMax 法により完全情報なガイスターを探索し，手を決定する．

手に対する勝率（最小勝率）の分析をおこなう．各組み合– 評価関数には，「青駒の個数差」「駒がゴールからどわせでは，先手後手がそれぞれ 50 回ずつ現れるようにし，

れだけ離れているか」の 2 つを用いる．相手の青駒

100 試合おこなう．初期配置は手前の一段（先手は a4-d4，数を考慮すること以外は紫駒 AI と同様である．自分

後手は a1-d1）におこない，どのプログラムもランダムにの青駒を保持したい，相手の青駒（とみなした駒）を選択する．なお，無限にゲームが終わらないのを防ぐた

取りたい，ゴールへ駒を近づけたいという観点から

め，200 手で決着がつかない場合は引き分けとする．ベン設計する．

チマークプレイヤとしては『ランダム』『猪突猛進』『紫駒

AI』『アンチ紫』を実装する．それぞれ以下の内容である．
• ランダム– 合法手のなかからランダムに選択し，行動する– 基本的には，赤ばかり近づける相手に強く，青ばか
り近づける相手に弱い．
また，提案手法におけるプログラム名と利得評価関数の対応を次のようにする．

– ただし，1 手で脱出可能なときは脱出をおこなう• CFR-A，未終局のリーフノードを引き分けと評価する．

– 攻めも守りも貧弱なため，弱い• CFR-B，リーフノードが持つ完全情報局面について真ⓒ 2021 Information Processing Society of Japan5

Vol.2021-GI-45 No.4
2021/3/5

情報処理学会研究報告
IPSJ SIG Technical Reportの勝敗を求め，評価値とする．
提案手法において，ゲーム木の展開深さは 5 とする．深
さ 0，1 では色配置の列挙をおこなっているため，駒移動に関する木の展開は 3 手までおこなうことになる．CFR のイテレーション数は 1000 とする．

7.2 実験結果

表 4
横軸が相手

ベンチマークプレイヤとの対戦結果（勝-敗-分)
ランダム

ランダム

猪突猛進

紫駒 AI

アンチ紫

最小勝率 [%]

9-91-010-90-030-70-090-100-0

92-8-0012-85-3

13.5

猪突猛進

91-9-0

紫駒 AI

90-10-0アンチ紫70-30-0

8-92-085-12-3

CFR-A

78-22-0

36-64-0

24-76-0

43-57-0

24

CFR-B

78-22-0

71-29-0

20-80-0

19-81-0

19

紫駒 AI の勝敗内訳
ランダム
猪突猛進

アンチ紫

100-0-0

8

ベンチマークプレイヤとの対戦結果を表 4 に示す．表 4
表 5の最小勝率は，最も苦手な対戦相手に対する勝率を表して
いる．

青取り勝ち

11

67

0

ると，いずれについても最小勝率 15%を下回る苦手な相

赤取り負け

0

0

0

赤取らせ勝ち58

33

2

手が存在することが分かる．特に表 4 の紫駒 AI は，ラン青取られ負け00

60

ダム相手に勝率 90%，猪突猛進には勝率 100%と大きく勝

脱出勝ち

21

0

10

ち越した一方で，アンチ紫には勝率 13.5%と大きく負け越

脱出負け

10

0

25

まず，4 つのベンチマークプレイヤの最小勝率に着目すした．紫駒 AI の勝敗内訳は表 5 のようになり，アンチ紫に対しては 6 割の試合で青を全て取られ負けている．紫駒

表 6

AI は相手駒に隣接させる駒がほとんど赤という特徴があるため，アンチ紫には多くの試合で赤を見破られ，見破られた駒以外を積極的に取られてしまったのではないかと考

1 試合あたりの隣接回数
赤
青

紫駒 AI

3.61

0.23

CFR-A

2.06

1.37

CFR-B

2.35

0.69

える．また，アンチ紫は猪突猛進に大敗し，猪突猛進は紫駒 AI に大敗している．

ていることが分かった．これは，相手の赤が 2 駒から 1 駒

一方，表 4 において，CFR-A，CFR-B のベンチマークに減るときのリスクを評価関数内で十分評価できていない

プレイヤに対する最小勝率に着目すると，CFR-A では最ことが理由ではないかと考える．また，CFR-B はアンチ

小勝率が 24%，CFR-B では最小勝率が 19%となり，どの紫にも弱い．表 9 について，アンチ紫に対する「赤取られベンチマークプレイヤよりも最小勝率が大きいことが確認

勝ち」「青取られ負け」の数を比較すると，CFR-B は赤取できた．

られ勝ちが 8%，青取られ負けの方が 32%と，青取られ負

また，駒移動に関する統計量を紫駒 AI, CFR-A, CFR-B
について計測した．まず，相手駒と隣接させる移動をおこけも目立っていた．よって，青駒を取られるリスクについても過小評価していると考えられる．

なった回数を青，赤ごとに計測した．ただし，相手駒を取提案手法の CFR-B は，完全情報局面の評価をおこなっる場合は計測の対象外とした．結果，1 試合あたりの隣接

たにもかかわらず，CFR-A と比べ，最小勝率が低く，紫駒

回数は表 6 のようになった．表 6 より，紫駒 AI は赤ばかAI，アンチ紫どちらにも付け込まれていることが分かる．

り隣接させている一方で，提案手法の CFR-A, CFR-B は

これは，リーフノードが持つ局面を別々に評価することで，紫駒 AI と比べて青もよく隣接させていることを確認でき

本来区別できないはずの局面で異なる手順を指せると仮定た．次に，相手駒が自駒に隣接した直後，その駒を取った

してしまい，適切な評価値をつけられないことが原因と考割合を計測した．結果，表 7 のようになった．相手赤 1 個えられる．例えば，図 6 において，2 つの末端局面は先手のとき，紫駒 AI は隣接してきた駒を絶対に取らないのに番にとって互いに区別できないため，本来であれば異なる

対し，CFR-A, CFR-B ではたまに駒を取っていることを手順を指すことができず，（即座に）勝ちを確信できないは確認できた．よって，相手の赤が残り 1 個の場合において，ずの局面である．しかし，それぞれの局面を独立に考える

簡単に脱出されにくくなったと考える．

と，それぞれ後手の青を取ることで先手必勝となる．よっ

最小勝率，駒移動に関する統計量の結果から，提案手法て，CFR-B の評価関数ではどちらも先手必勝と判断しての CFR-A, CFR-B は紫駒 AI と比べると対戦相手に付けしまうことになる．これは過大評価となっており，このよ

込まれにくくなったと考えられる．しかし残念ながら，提うな適切でない評価が頻発することで，CFR-B は上手く

案手法は全てのベンチマークプレイヤに勝ち越すことはでいかなかったと考えている．

きなかった．その敗因を探るため，勝敗条件の内訳を取り，敗北条件を分析した．勝敗条件の内訳を表 8, 9 に示す．ま8. おわりにず，CFR-A, CFR-B は紫駒 AI に負け越しているが，いず

本稿では，二人零和不完全情報ゲーム『ガイスター』におれも赤を全て取ってしまい敗北した試合が半分以上を占めいて，対戦相手に付け込まれる余地を減らすため，確率的ⓒ 2021 Information Processing Society of Japan

6

Vol.2021-GI-45 No.4
2021/3/5

情報処理学会研究報告
IPSJ SIG Technical Report
表 7

隣接してきた駒を取った割合
全体
相手赤 1 個

紫駒 AI

0.20

0

CFR-A

0.21

0.11

CFR-B

0.33

0.20

がら全てのベンチマーク AI に勝ち越すことはできなかったが，確率的な着手によって付け込まれる余地を減らすことには成功したと考えられる．
今後の方針として，過去の着手を考慮することが挙げられる．本研究の手法においては，過去の着手を用いず，現

表 8

CFR-A の勝敗内訳
紫駒 AI
アンチ紫

局面のみを入力としていたが，過去の着手を用いることでさらなる性能の向上が期待できる．例えば，脱出しなかっ

青取り勝ち

4

0

た駒をそれ以降のターン赤とみなすことができれば，試合

赤取り負け

56

13

を有利に運ぶことができる．今後の方針として，過去の着

赤取らせ勝ち036

青取られ負け331

手を用いた手法を考えたい．

脱出勝ち

20

7

脱出負け

17

13

参考文献
[1]

表 9

CFR-B の勝敗内訳
紫駒 AI
アンチ紫

青取り勝ち

2

0
41

赤取り負け

64

赤取らせ勝ち0

8

青取られ負け

3

32

脱出勝ち

18

11

脱出負け

13

8

[2]

[3]
[4]
[5]

[6]
[7]

[8]
[9]

[10]

[11]

[12]

[13]
図 6

CFR-B が上手くいかないケース[14]

行動を取る AI を開発した．現実的な時間で確率的行動を計算するため，数手先までしかゲーム木を展開せず，リー
フノードに評価値を与える手法を提案した．4 × 4 盤のガイスターについて，4 種類のベンチマーク AI との対戦実験をおこなった結果，ベンチマーク AI 同士の対戦ではどの[15]

Silver, D. et al.: Mastering the Game of Go without
Human Knowledge, Nature 550, pp.354-359 (2017).
Zinkevich, M., Johanson, M., Bowling, M. and Piccione,
C. Regret Minimization in Games with Incomplete Information, Advances in Neural Information Processing
Systems 20, pp.1729-1736 (2008).
Tammelin, O.: Solving Large Imperfect Information
Games Using CFR+, arXiv:1407.5042 (2014).
Bowling, M. et al.: Heads-up limit hold’em porker issolved, Science Vol. 347, Issue 6218, pp.145-149 (2015).
Li, J. et al.: Suphx: Mastering Mahjong with
Deep Reinforcement Learning, Artiﬁcial Intelligence,arXiv:2003.13590v2, pp.1-28 (2020).
ガ イ ス タ ー ．[
http://www.mobiusgames.co.jp/Gester.htm ]．（アクセス：2021/02/09）．
三塩 武徳，小谷 善行：ゲームの不完全情報推定アルゴリ
ズム UPP とそのガイスターへの応用，情報処理学会研究
報告，Vol.2014-GI-31, No.4, pp.1-6 (2014).
佐藤 佑史：ガイスターにおける自己対戦による行動価値関数の学習，電気通信大学学術機関リポジトリ (2015).
川上 直人, 橋本 剛：完全情報ゲームの探索を用いたガイ
スター AI の研究，第 23 回ゲームプログラミングワーク
ショップ，pp.35-42 (2018).
木村 勇太, 伊藤 毅志：深層強化学習を用いたガイスター
AI の構築，第 24 回ゲームプログラミングワークショッ
プ，pp.130-135 (2019).
Neller, T. W. and Lanctot, M. An Introduction to Counterfactual Regret Minimization, Proceedings of ModelAI Assignments, The Fourth Symposium on Educational
Advances in Artiﬁcial Intelligence (EAAI 2013) (2013).
Gibson, R.: Regret Minimization in Games and theDevelopment of Champion Multiplayer Computer PokerPlaying Agents, PhD Thesis, University of Alberta(2014).
Chen Chen and Tomoyuki Kaneko. Counterfactual Regret Minimization for the Board Game Geister, 第 23 回
ゲームプログラミングワークショップ, pp.137-144 (2018).
Chen Chen and Tomoyuki Kaneko. Utilizing History
Information in Acquiring Strategies for Board Game
Geister by Deep Counterfactual Regret Minimization,
第 24 回ゲームプログラミングワークショップ, pp.20-27(2019).
川上 直人：完全情報ゲームの評価値を用いた二人零和不完全情報ゲーム『ガイスター』における混合戦略 AI の研究，JAIST 学術研究成果リポジトリに公開予定

AI についても勝率 15%を下回る苦手な相手が存在した一方で，提案手法 2 種とベンチマーク AI の対戦では，最も苦手な相手に対しても 19%，24%の勝率となった．残念なⓒ 2021 Information Processing Society of Japan

7