進捗報告 その6

「提出手比較による大貧民プレイスタイル解析」からは、
モンテカルロ法クライアントのプレイにもなんらかの特徴(プレイスタイル)はある
ということはわかるんですが、
あくまで比較するだけなので、何割違うとかしか言えない。
どんな特徴がある、というところまではなかなか言えないのが難しいところです。
(論文中では、「行動を限定させたクライアント」と比較することで特徴を見つけてはいます)

(なのでそういうのは
 決定木を用いた大貧民プログラムの分析に関する研究
 が参考になりそうですが、これを読むには課金が必要なのでまた今度。)

ある局面で何を提出したか、というデータから
なんやかんやでクライアントごとに分類するというのはなんとなくうまくいきます。
自分も実験したりしました。
大貧民プログラムのn-gram統計による特徴抽出とクラスタ分析
【実験】大貧民クライアントを分類できるか? - koganie’s blog
けれど、これはこれで「特徴」が人のわかる形には表れてこない。
というか、そんなものが人にわかるのなら、わざわざモンテカルロ法に頼らずともよかろう。
ただ、分類できるのに、
・何が違いとして生じるのか
・何が強さに繋がっているか
がわからないのはなんだかさびしい。

まあ、提出手比較用の環境を作ってから、これなにに使うんだ…と。

・・・

次の図は、kou2×5の試合中、
1つのkou2に対してParty,default,beersong,snowl,Glicineの提出手を受け取り、比較させたグラフ。
横軸は自分の手札枚数。
簡単な必勝手探索は行っており、当該局面はのぞいている。
f:id:koganie:20180114230408p:plain

ほんとうは、Party-defaultなど、5体それぞれの一致率も求めているのだが、
まとめるのがめんどうなので、kou2とだけをグラフにした。

同じライト級クライアントのPartyとの一致率の高さが目立っているが、
序盤、モンテカルロ法クライアントのGlicineとの一致率が高い。
終盤以外は、6割程度の一致率をみている。

同様のことをkou2にかえてsnowlにしてみる。
f:id:koganie:20180114232148p:plain

正直、みてもあんまり面白くない^^

やっぱりモンテカルロ法クライアントはそれぞれの手が一致する傾向にあるようで、
これが分類がうまくいく要因なのかもしれない。
ただ、これで「分類ができた!」って本当に言えるのかね。
「正解の手」をそれだけライト級クライアントよりも多くモンテカルロ法クライアントが見つけている、
理想の行動に近い、というだけで、
それがクライアントの特徴を使って分類できたと、いえるのだろうか。
まあ、そういう行動に現れる特徴が、プレイスタイルと言えるのかもしれないけれど。。。

こんどは全カードの未提出の札の枚数毎に一致率を求めたもの。
(試合は10000試合しかやっていないので、枚数の極端に多い・少ない局面は登場数が少ない。)

これはなんか、面白い。
f:id:koganie:20180114232733p:plain

序盤・中盤・終盤で、クッキリとsnowlとの提出手一致率が違っている。
と思ったが、これは単純に、序盤と終盤でsnowlの行動が甘い、ということなんだろうか。

kou2との一致率も出してみると、今度はわりと平坦なグラフだ。
(縦軸の範囲が少し違うけど)
f:id:koganie:20180114233042p:plain
序盤・中盤・終盤という区切り(が本当にあるのかもわからんが)に関わらず、
概ね同じような行動を取っているらしい。
この中ではdefaultが最も単純な行動をしているが、終盤になるほど手の一致率が高くなっていく。
「いかに序盤をうまく乗り切るか」が大事、という感じか(そりゃそうだろ)。

いちおう、デフォルトとのデータも取ってみた。
f:id:koganie:20180115001637p:plain
f:id:koganie:20180115001652p:plain

対戦クライアントによって、現れる局面の特徴も変わってしまうので、
それぞれのグラフを比較するのは難しいことには注意。

日記 全国握手会

ぼくははじめて全国握手会というのに行ってきました。乃木坂さんです。

ミニライブは早くいかないといい席は取れないというので、
じゃあそこまでしなくていいかあということでお昼頃現地到着で
握手会の入場待機列に並び始めたのですが、
13時開場なのに、
そっから2時間くらい待たされるんですね。
しかも入ってからもメンバーの列でさらに1時間くらい待つわけです。
待ってる最中雨降ってくるし。
なんて過酷なんでしょう。

ぼくは齋藤飛鳥さん目当てだったのですが、
たどり着くころには腰がすごく痛くてへろへろでした。

齋藤飛鳥さん、ちっちゃくて本当にそこにいるんだかよくわかりませんでした。
なんだか疲れと緊張でよくわからなくなっていたと思うのです。
齋藤飛鳥さん眠そうでした。
・・・かわいい。

なんというか握手会には思ったより体力を使うので、
そっちはあきらめてミニライブと物販で楽しむというのも
結構ありなのかなと思いました。

あとポスター交換とか写真交換とか、
フリーマーケット的なスペースができてて、
にぎわっててこれも見てるだけでしたが面白かったです。
「握手券と交換」、とかって出てるんですが、
あんな夕方になって握手券ゲットして使い道があるんでしょうか。

以上、にわかファン的な感想でした。

握手してもらったので
これを糧に頑張ろうと思いました。

コンピュータ大貧民の研究報告を読む。④

「提出手比較による大貧民プレイスタイル解析」
は、同一局面に対して何を提出するか、を比較することで、
プレイスタイルの違いを明らかにすることを目的とした研究。
http://id.nii.ac.jp/1001/00082814/

研究報告の中での実験環境としては、
ある一つのクライアントを中継サーバとして、中継サーバに比較したいクライアントを2つ接続。
2つのうち片方のみの提出手を本サーバに通知する一方で、
提出手を比較していく、という手法を取っている。

実験に使用しているのは
fumiya(MC法)
fumiyaの改良版であるsnowl
・snowlの改良版であるcrow
・公式サイト配布のdefault
の4種である。

詳細は研究報告を参照いただきたいが、例えば、
・snowlは「しばり」を多用する。
・snowlは空場で階段を出せるときに階段を出すため、defaultと一致率が高くなる。
・snowlはペアや階段役を崩してでも、弱いカードから提出する傾向がある。
といったプレイスタイルの分析に成功している。

この研究の中でも、今後の課題として、
・細かな場合分けによる提出手の傾向分析
・より詳細な解析による要所や定石を明らかにする
ことがあげられている。

自分も、ここに少し挑戦してみたい。

ということで、自作大貧民サーバに手を加えて、
比較クライアントが参加できるようなものに改造した。
サーバにゲーム履歴を出力させるのと同時に、
比較クライアントたちの提出手も出力させていく。

f:id:koganie:20180107013041p:plain
(試合はkou2×5で比較用に5つクライアントに提出手をもらって出力している様子。番号があっていないが、kou2の1つがC5を出したところ、defaultはSHD-7のペアを、PartyがD3を、…と出力されている。毎回手札が変わるとクライアント側でなんか変な挙動を起こしそうなので、固定のkou2と比較をずっとしている。そもそも、「提出したはずの手がゲームに反映されない」状況が続いても、ちゃんと動いているのか不安がある。)

履歴と突き合せれば、ゲームの局面がわかるので
どんな状況で一致傾向にあるのか、あるいは
手が異なってくるのか、なども分析できそう。

でも要所や定石とは、どうやって分析すればいいのかな。
手札の似てる・似てないみたいのが分からないといけないだろか。

とりまえず、簡単にできそうなところから実験をやってみたい。

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

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

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

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

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

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


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

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


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

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

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

・全札12枚の単貧民の多くの場面で偶然手番は0、すなわち「未知の状況の実現確率を意識せずに着手が決まることが分かった」
・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年)
大貧民のゲームの特性を利用した、乱数を用いた3種類の手札推定手法と、
局面をいくつかの特徴で分類した上で、既存クライアントの試合での各分類局面での
役の登場確率を反映させた手札推定手法を提案。

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

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


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

意外にも、手札推定というのは、たいして役に立たない技術ということが実験結果から得られている。
特に、手札を完全に推定できてしまうと逆に弱くなってしまう、というのは、
なんとも奇妙に思える事象である。

(上に関しては
http://flute.u-shizuoka-ken.ac.jp/~s-okubo/txt/fig/gi30.pdf
で訂正されており、実際は手札を完全に推定できたほうが強い。手札推定率と得点に線形の関係がある、としている)

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

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

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

【実験】大貧民クライアントを分類できるか?

大貧民はとかく、プレイスタイルがよくわからない問題があります。
これは、試合を見ていても、
何が強さにつながっているのか、よくわからないということでもあります。

そんなこんなで大貧民AIはクライアントの特徴なんかの研究って
(知る限りでは)あまりないのだと思っています。

大貧民の方策関数を作る研究がありました。
コンピュータ大貧民の研究報告を読む - koganie’s blog
この研究の中で、既存クライアントの手を模倣する方策関数も作っている。
もしかしたら、これというのは、
既存クライアントの特徴を数値化している、と言えるんではないでしょうか。
これを使えば、似てるクライアント、みたいな分類ができるんではないでしょうか。
と、ふと思いました。

ということでやってみました。
学習データは20000試合ぶん、20回の学習です。
(学習に関してはこれらや学習項目を含めて、ぜんぜんチューニングできていません)
エントリークライアントはUECda公式サイトからダウンロードした以下10個です。
・beersong ・default ・elefunt ・Glicine ・jn16 ・kou2 ・kowl ・Party ・res.kou2 ・snowl
(使用させていただきました)
UECda-2017 コンピュータ大貧民大会


各クライアントの自己対戦棋譜から学習してできた
10通りの方策のベクトルをRに読み込ませて、樹形図を出力させてみます。
距離はユークリッド、併合方法は最長距離法です。

f:id:koganie:20171220000342j:plain

なんとなあく、右下にモンテカルロ系クライアントが集まっているような気もしますが…
いや、これってもしかして、
学習の具合によって、ベクトルの数値も大きく差がでちゃうんじゃないでしょうか?
ということで、各方策ベクトルを正規化してからやってみました。
(なんという適当さ!)

f:id:koganie:20171220000811j:plain

いい感じの樹になったように見えます。
やはりなんとなあく、は似たようなグループでまとまっているような気はしますが。
ただ、特にkou2とres.kou2って名前からして似たクライアントっぽい感じがしますが、
樹形図でみると全然違う位置に属しています。

ちなみに手の一致率を簡単に見てみると、
kou2-res.kou2 99.35%
kou2-kowl 88.6%
kou2-Glicine 68.0%
kou2-beersong 63%
kou2-snowl 61.2%
くらいになって、やっぱりres.kou2とは似たクライアント、
と出るべきではあるのです。

……なら方策ベクトルつかわず一致率で分析すりゃいいじゃねえか。

kowlとres.kou2のデータ入れ替わっちゃってないかと不安になるような結果でしたが、
たぶん大丈夫です。

進捗報告 その5

前回の大貧民関連投稿が「143日前」とかなっていてすごい。
その間、さぼっていました。

でもまた最近ぼちぼちと再開してみました。
必勝手探索はめちゃめちゃバグがあったり、
学習の手違いのもとになりそうなところは直したり、
そんなこんなで試しに学習させてみましたら、
kou2には負けますが、デフォルトには安定して勝てるようになりました。

f:id:koganie:20171207221323p:plain

もう少し学習の調整、学習項目の選定、もろもろうまくやれば
なんとなあくは強くなりそうなところまで来ました。
ようやくスタートラインな感じです。

結局、必勝手探索は「残りの役で場を流し切れるか」という
単純なものしか実装していませんが、
これまでのものがまったくもって強さを発揮できなかったのは
やはり役提出のソースがどうにも学習と合致していなかったようなのでした。
ひどく面倒なソースコードの作り方をしているので、
実はもっとあるのかなあとも思ってはいます。

調子に乗っていろいろ棋譜を採取しようと思ったら
UECda-2013優勝のbeersongが当方のcygwin環境ではコンパイルできませんでした。
手っ取り早くafterfesta.h内のinlineを除去してコンパイルしてしまいましたが、
なんかうまい方法があるんでしょうか。

優勝クライアント以外も
http://www.tnlab.inf.uec.ac.jp/daihinmin/2017/participants.html
にまとまってはいますけども、
公開はされないんでしょうかね。

もうちょっと実験をしてみたいと思います。

NPB各チームのイロレーティング2017(最終回)

koganie.hatenablog.com

もう飽きちゃったんですが、この際最後までやります。
シーズン終わっちゃいましたね。
楽天もCSでなかなか面白い戦いをしてくれました。

まずセリーグです。
f:id:koganie:20171026224019p:plain

前回落ち込んでいた広島が最後は盛り返しました。
まあ、CSは負けましたけどね。

次はパリーグです。
f:id:koganie:20171026224126p:plain

楽天は最後までぐずついていました。
でもCSは西武に勝ったし、
ソフトバンクにも2勝しましたからね。

はあ。

こんな数字を出してなにが楽しいんでしょうか。
なにか見て楽しいことがあるんでしょうか。
なんで僕はこんなことをやっているんでしょうか。


ちなみに最終的にソフトバンクが1586.94。
DeNAが1539.31という結果でした。



日本シリーズどっちかなああ(無関心)