読者です 読者をやめる 読者になる 読者になる

大貧民の棋譜について

機械学習とかにあたって棋譜は重要だが、コンピュータ大貧民には決まった棋譜の形式などはないのである。
ということでサンプルを作ってみた。
いかがでせう。

TEFUDA
0 2 0 S3 S4 SX SA S2 D5 D9 DA C3 CK 
1 4 1 H4 HQ HA D6 D7 C5 C7 C9 CA C2 
2 0 2 S5 H5 H6 H7 HJ HK DX DQ D2 C4 CX 
3 1 3 S6 S7 S8 SJ SQ SK H3 H8 DK CJ CQ 
4 3 4 S9 H9 HX H2 D3 D4 D8 DJ C6 C8 JR
CHANGE
1 2 HA C2 
4 3 JR 
2 1 S5 C4 
3 4 H3 
HISTORY
4H3D3 0SADA 1PS 2D2C2 3PS 4PS 0PS 2PS 2H5H6H7 3SJSQSK 4PS 0PS 1PS 2PS 3PS 3s5S6S7S8 3H8 3CJ 4H2 0PS 1PS 2PS 3PS 4PS 4D8C8 4S9H9 0PS 1PS 2DXCX 3PS 4PS 2PS 2HJ 3CQ 4PS 0CK 1CA 2PS 3PS 0PS 1PS 1H4C4 2PS 3PS 4PS 0PS 1S5C5 1D7C7 1PS 1D6 2DQ 3DK 4PS 0PS 1PS 2PS 2HK 4PS 0S2 1PS 2PS 0PS 0S3C3 1PS 2PS 4PS 0PS 0S4 1C9 2HA 4PS 0PS 1PS 1HQ 4PS 0PS 0D5 4C6 0D9 4HX 0PS 4DJ 4PS 4D4 
MIBUN
0 4
1 2
2 1
3 0
4 3

手札は交換前の手札を挙げている。
[プレイヤー番号] [身分] [席順] [手札内容]
が一行ずつ。

交換は
[差し出し元] [受け取り人] [交換カード]
が一行ずつ。

ゲーム履歴は最初のプレイヤーから役を列挙している。
役は
[プレイヤー番号][スート][ランク]
で1セットである。
1枚のカードはいずれも2文字で表記されている。
パスはPS、ジョーカー単騎はJR、ジョーカーを他カードの代わりで使うときはスートを小文字にしてわけている。

試合後の身分は、履歴を見ればわかることだが。付けるなら1行で
[プレイヤー0の身分] [プレイヤー1の身分] ...
とかとするのもよいかもしれない。

https://github.com/koganie/uecda_server/:uecda_server棋譜を吐かせられるようにはしている。これ、画面描画の機能はつけるつもりはないのだが、棋譜の形式が定まれば棋譜の再生なども可能となる。
実際の大会の棋譜とかも残せることができれば、ウェブ上でどんな激戦が行われているのか、後で簡単に確認することができたり、なんてことも期待できる。
はたまた棋譜の形式と、任意の形式へのコンバートができれば、
簡単に学習データセットに変換することができるのだ?

ともかくこれは試作。
ご意見等ござればよろしく願いたい。

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

「方策勾配法による局面評価関数とシミュレーション方策の学習」の中で教師有り学習についても提案されている。この研究報告は数式が難しそうで読める気がしない(クズ)が、この手法が最近、コンピュータ大貧民に持ち込まれ、一定の成果を上げている。 これはコンピュータ大貧民大会(UECda)に二年連続で優勝してテレビにも出演した大渡氏による(すごい)。詳細は研究報告「方策勾配を用いた教師有り学習によるコンピュータ大貧民の方策関数の学習とモンテカルロシミュレーションへの利用」を読まれたい。(コメント欄に修正版リンクを張っていただいたので参照のこと。)

この学習においては次のような誤差関数を最小化することで、評価関数のパラメータをチューニングするようだ。 数式の意味とかは研究報告を参照として、ここから更新式を導出するまでをとりあえず追ってみたい。

 \displaystyle
L(\pi_* , \pi_\theta ) = \sum_{b\in A}\pi_*(s,b) \ln\left(\frac{\pi_*(s,b)}{\pi_\theta(s,b)}\right)

\pi_*が決定的とは、局面 sでの教師の行動が xのとき

 \displaystyle
\pi_*(s,x) = 1

が成り立つということなので( b=x以外では0となる)

 \displaystyle
\begin{align}
L(\pi_* , \pi_\theta ) &=& \sum_{b\in A}\pi_*(s,b) \ln\left(\frac{\pi_*(s,b)}{\pi_\theta(s,b)}\right) \\
&=&  \pi_*(s,x) \ln\left(\frac{\pi_*(s,x)}{\pi_\theta(s,x)}\right) \\
&=&
\ln\left(\frac{1}{\pi_\theta(s,x)}\right) \\
&=&
-\ln(\pi_\theta(s,x))
\end{align}

で、これが(3)式である。

(4)式の更新式は、この式を\thetaによって偏微分することで得られる。

 \displaystyle
\begin{align}
\frac{\partial L(\pi_* , \pi_\theta )}{\partial \theta} &=& 
-\frac{\partial }{\partial \theta} \ln(\pi_\theta(s,x))\\
&=& 
-\frac{\partial }{\partial \theta} \ln\left(\frac{\exp^{\phi (s,x)\cdot \theta /T}}{\sum_{b\in A}\exp^{\phi (s,b)\cdot \theta /T}}\right)\\
&=& 
-\frac{\partial}{\partial \theta}\ln(\exp^{\phi(s,x)\cdot \theta /T})+\frac{\partial}{\partial \theta}\ln\left(\sum_{b\in A}\exp^{\phi(s,b)\cdot \theta /T} \right) \\
\end{align}

第1項は自然対数なので簡単に計算ができて

 \displaystyle
\begin{align}
-\frac{\partial}{\partial \theta}\ln(\exp^{\phi(s,x)\cdot \theta /T}) &=& -\frac{\partial}{\partial \theta}\frac{\phi(s,x)\cdot \theta}{T} \\
&=&
-\frac{\phi(s,x)}{T}
\end{align}

第2項は少し複雑になるが、同じようにできて、最後に\piの式が現れるので置き換えられる。

 \displaystyle
\begin{align}
\frac{\partial}{\partial \theta}\ln\left(\sum_{b\in A}\exp^{\phi(s,b)\cdot \theta /T}\right)
&=&
\frac{ \frac{\partial}{\partial \theta}\sum_{b\in A}\exp^{\phi(s,b)\cdot \theta /T} }{\left(\sum_{b\in A}\exp^{\phi(s,b)\cdot \theta /T}\right)} \\
&=&
\frac{ \sum_{b\in A} \frac{\phi(s,b)}{T} \exp^{\phi(s,b)\cdot \theta /T} }{\left(\sum_{b\in A}\exp^{\phi(s,b)\cdot \theta /T}\right)} \\
&=&
\sum_{b\in A} \frac{\phi(s,b)}{T}\pi(s,b)
\end{align}

それで結局

 \displaystyle
\begin{align}
\frac{\partial L(\pi_* , \pi_\theta )}{\partial \theta} &=& 
-\frac{\partial }{\partial \theta} \ln(\pi_\theta(s,x))\\
&=& 
-\frac{\phi(s,x)}{T} + \sum_{b\in A} \frac{\phi(s,b)}{T}\pi(s,b) \\
&=&
-\frac{1}{T} \left( \phi(s,x) - \sum_{b\in A} \phi(s,b) \pi(s,b) \right)
\end{align}

となって更新式が得られる。 これに学習係数をかけて、実際には更新を行っているようだ。

参考文献

  1. 五十嵐治一,森岡祐一,山本一将, 方策勾配法による局面評価関数とシミュレーション方策の学習, 研究報告ゲーム情報学 (GI), 2013-GI-30(6), 1-8, 2013.
  2. 大渡勝己, 田中哲朗, 方策勾配を用いた教師有り学習によるコンピュータ大貧民の方策関数の学習とモンテカルロシミュレーションへの利用, 研究報告ゲーム情報学(GI), 2016-GI-35(10), 1-8, 2016.
  3. 2の訂正版

UECdaの大貧民クライアントと簡易的に対戦するプログラム


コンピュータ大貧民大会UECdaが毎年開催されており、大貧民をプレイする人工知能のレベルも年々向上している。そんなので、自分でもプレイして強さを実感したい、というところで、簡易的な人手のプレイ用クライアントを作った。

本当はGUIとかのほうが見やすいしやっていて面白いのだろうが、そういうのはプログラミングの得意な人がやるべきである。

ソースコードここで公開している。 ダウンロードしたらmakeすれば、/binフォルダに実行ファイルができる。 公式サイトを参考に、サーバと、対戦したいクライアントを4つ起動して、残り1つでこのクライアントを起動させれば対戦ができる。なお、バックグラウンドで(最後に&をつけて)実行すると、入力待ちのたびに停止状態になって面倒くさいので、フォアグラウンドで実行させると良い。

f:id:koganie:20161113002703p:plain

公式サイトのサーバを起動させたとき、対戦画面はこんな感じ。

f:id:koganie:20161113002808p:plain

試合が進めば

f:id:koganie:20161113002823p:plain

コンソールに状況が実況される。

f:id:koganie:20161113002840p:plain

自分の番になると、その時々の提出手の選択を求められる。

1行の見方は、一番左から、
そのターンのプレイヤー番号、場札の役、(プレイヤーiがパスをしているか プレイヤーiの手札の残り数) => そのターンで提出された札
となっている。
自分のターンとなると
[HANDS] 自分の手札の札
から、現在の盤面で提出可能な合法手が番号並びで表示される。

もしスペードの9を出したければ 0 と入力してエンターを押せばよい。パスなら p と入力する。これはパスしかできない局面でも入力しなければいけない。

1枚のカードの表現は2文字で成り立っており、左の文字がスート、右の文字がランクとなっている。スートはSHDCの4つ、ランクは3,4,5,6,7,8,9,X,J,Q,K,A,2となっている。ジョーカーを階段とかと混ぜる場合は、スートが小文字で表現されている。単体出しだったらJRとか表示されたような気がする。

ちなみに入力待ちのときに c と入力すると、すでに提出されたカードと自分の手札のカードに1がついたカード、つまりまだ相手が持っているカードを確認することができる。

本当は自分もクライアントをつくって大会に参加したかったのだが、遅々として進まず断念した。このプログラムも思い付きでやったものなので、変なバグ等多々あると思われる。なにか不具合あったら教えてくれたら直すかもしれません。

人間対大貧民クライアントでは、2015年度優勝クライアントが、NEWSの手越くんをぼこぼこにするという番組がありまして、それはそれは痛快なものがありました。自分も、強いプログラム、作ってみたいものです。