コンピュータ大貧民の研究報告を読む。③（特集：相手手札推定の有効性）

大貧民は、将棋や囲碁などと異なって、
多人数で、しかも非開示の情報がある中で行われるゲームだ。
これを多人数不完全情報ゲームという。

そんなゲームを優位に戦うためにぱっと思いつくのが、
「相手の手札を推測できてしまえば攻略できてしまうんではないか」
というところで、
実際大貧民の研究を眺めてみると、この手札推定について言及した論文が結構あるのでざっくりと読んでいきたい。
（あまりにざっくりとまとめているため、くれぐれも原論文をご参照ください。）

ちなみに大会ではsnowlが手札推定の技術を導入しており、多くの研究がsnowlを使って実験を行っている。

○大貧民における相手手札推定
（西野順二、西野哲朗、2011年）
snowlの手札推定機能を有り・無しと分けたクライアントや、
snowlが強いクライアントの棋譜から手札推定パラメータを学習しているところ、当時の基準クライアントから学習したクライアント
を用意し、それぞれ基準クライアントなどと対戦させた結果から、手札推定の効果について考察する。

・手札推定の効果はあまり大きくない。
・手札推定は、学習に使った棋譜の元クライアントに対して有利に働く。ただ汎用的な「強さ」には繋がらないこともある（強いクライアントを学習したsnowlは繋がっていた）。
・「必要であるのは正確な推定ではなく、有利な着手決定を導く探索を実現するのに役立つ推定である」「シミュレーション確度をあげる効果が重要である」
・手札推定が全く必要のない局面も存在する。
http://id.nii.ac.jp/1001/00077349/

○多人数不完全情報ゲームのモンテカルロ木探索における推定の効果
（西野順二、西野哲朗、2011年）
[内容]
上の論文の考察を深めている。

・不完全情報が合法手数に比べて非常に大きい場合は、推定や評価値が正解とは異なっても、最適手を選択することはままある。
（「状態の推定と最適手の関係は緩やか」であり、大貧民もそのようなゲームである）
・ならば正確な推定をするよりも、正解の手を与える状態を生成できることが重要。
（「推定器にかける計算時間をより多い種類の状態の生成とモンテカルロ木探索にかけた方が良いかもしれない」）
http://id.nii.ac.jp/1001/00078748/

○大貧民において不完全情報性がモンテカルロ法によるプレイヤに与える影響の調査
（地曳隆将、松崎公紀、2012年）
モンテカルロ法プレイヤとモンテカルロ木探索プレイヤによって、「大貧民における次の１手問題」に対して、評価値の収束の仕方を分析している。
（ここで相手手札についてはすべて開示されている）
・モンテカルロ法プレイヤは4000回程度のプレイアウトで収束したが、モンテカルロ木探索プレイヤは収束しない。

また、すべて開示した場合の木探索プレイヤの評価値を正解とみなし、
相手手札の開示環境を変化させたモンテカルロ法プレイヤの評価値・手の一致を比較することで分析もしている。
・序盤は弱いカードの情報が有用であり、終盤は手札全体を推定しなければ意味がない。
・手札が完全にわかっても残存枚数の多い序盤は最善手の推定は難しく、逆に終盤はわからなくてもしやすい。
・合法手数が少ないからといって最善手の判定がしやすくなるわけではない。
http://id.nii.ac.jp/1001/00082813/

○大貧民における偶然手番感度
（西野順二、西野哲朗、2013年）
サイコロなどによる偶然によって局面が選択されることを「偶然手番」といい、これがゲームに与える影響度を「偶然手番感度」と定義。
大貧民の縮小版である「単貧民」（単体のみが合法手）に対して、ゲーム木の完全探索を行い、偶然手番感度を調査。
また大貧民においてもsnowlを用いて偶然手番感度の低さを検証している。

・全札12枚の単貧民の多くの場面で偶然手番は０、すなわち「未知の状況の実現確率を意識せずに着手が決まることが分かった」
・snowlの手札推定機能を切り、その分の計算時間をプレイアウト回数に充てることでsnowlを強化できた。このため大貧民でも偶然手番感度は高くない。
・同一のプレイアウト回数では手札推定は効果があった（プレイアウト回数の削減は可能となった）。
・推定の正確さではなく、「シミュレーション確度をあげる効果が重要」
・重要な局面集合の発見方法が今後の課題。
http://id.nii.ac.jp/1001/00090383/

○コンピュータ大貧民における手札推定の有効性について
（吉原大夢、大久保誠也、2013年）
snowlの手札推定の能力を調査。
snowlの手札推定の成功率を0%、50%（弱・強）、100%に変化させて、勝ち点がどうなるか調査。

・通常のsnowlは33%くらい手札推定を成功させており、特に弱いカードのほうが成功率が高い。
・最も強かったのは弱いカードを50%成功させた場合で、100%成功させたのは最も弱かった。
（弱いカードを推定したほうが、モンテカルロ木が広く展開するから？と考察）
・より詳細な場合分けや提出手の比較が今後の課題。
http://id.nii.ac.jp/1001/00092709/

○コンピュータ大貧民でのモンテカルロ法における相手手札推定率と勝率との関係
（平嶋遼馬、鈴木徹也、2014年）
snowlを任意の手札推定成功率にできる環境を整え、
プレイアウト回数を数パターンにわけた相手プレイヤと対戦させ結果を調査。
また、手札推定成功率を分けた場合の、手の評価値の差を分析。

・手札推定成功率が70%を超えると、相手が強くても有意差が生じ、snowlより7%得点を多く取った。
・完全な手札推定になるほど評価値の分散が大きくなる。
・ゲーム中盤に評価値の分散が大きくなるため、手札推定は中盤に影響が大きい。
http://id.nii.ac.jp/1001/00104834/

○大貧民における出現頻度と提出手役履歴を用いた相手手札推定
（柳澤佑介、松崎公紀、2015年）
大貧民のゲームの特性を利用した、乱数を用いた３種類の手札推定手法と、
局面をいくつかの特徴で分類した上で、既存クライアントの試合での各分類局面での
役の登場確率を反映させた手札推定手法を提案。

・提案手法によりプレイアウト回数の削減が可能である。
・推定に用いたプレイヤとの対戦では弱くなってしまった。
（手札推定の一致率が高くなかったから、と著者ら考察）
・盤面での分類手法やプレイアウトへの連動が今後の課題。
http://id.nii.ac.jp/1001/00113636/

○方策勾配を用いた教師有り学習によるコンピュータ大貧民の方策関数の学習とモンテカルロシミュレーションへの利用
（大渡勝己、田中哲朗、2016年）
基本的なアルゴリズムの中の１つとして手札推定手法を提案しており、強さに効果があるとしている。
数パターンの手札配置を生成し、方策関数に従って行動するという仮定のもと尤度を計算し、高いものだけを用いるというもの。
（論文の主題ではないため、手札推定に重点を置いた分析を行っているわけではないが、方策関数を利用した手札推定手法といえる）
http://id.nii.ac.jp/1001/00157945/

・・・と、こんなところだろうか。

意外にも、手札推定というのは、たいして役に立たない技術ということが実験結果から得られている。
特に、手札を完全に推定できてしまうと逆に弱くなってしまう、というのは、
なんとも奇妙に思える事象である。
（上に関しては
http://flute.u-shizuoka-ken.ac.jp/~s-okubo/txt/fig/gi30.pdf
で訂正されており、実際は手札を完全に推定できたほうが強い。手札推定率と得点に線形の関係がある、としている）

西野順二氏のいう「シミュレーション確度をあげる効果が重要」ということで、
もちろん手札推定もその効果を多かれ少なかれ持つのであって、完全に無駄な技術というわけではない。
が、あまりに計算時間をどっぷり費やして正確さを求めても、それは徒労になりそうだ。

そこで柳澤佑介氏の、軽量の手札推定手法であったり、
大渡勝己氏の、重量ではあるが良い手札集合を得る手法であったり、
いくつかアプローチが登場しているようである。

モンテカルロ法プレイヤの強さは一体どこからきているのだろうと改めて不思議に思う。