% !TEX encoding = UTF-8 Unicode
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	tani_resume.syt 使用例
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%#! platex resume.tex
\documentclass[a4paper]{jarticle}

\usepackage{tani_resume}
\alignbeforeskip -5mm
\alignafterskip -5mm
\eqnarraybeforeskip -5mm
\eqnarrayafterskip -5mm

\jptitle{UCT探索を用いた大貧民クライアント}
\etitle{}
\jpauthor{佐藤 友啓}
\eauthor{Tomohiro Sato}
\course{谷聖一　研究室}
\year{24}
\abstract{%
電気通信大学が主催するUECコンピュータ大貧民大会に参加することを目的として，大貧民クライアントプログラムを作成した．モンテカルロ法による乱数を使ったシミュレーションを基礎として，全合法手に対して決められた回数分シミュレーションするのではなく，シミュレーションの勝率が高く，かつ，シミュレーション回数が少ない合法手を優先的に選択するように，シミュレーション割り振り法をUCT探索によって実装した．

}

% 最終更新時刻の挿入
%\compheading

\begin{document}

% タイトルを表示させる
\maketitle

\begin{multicols}{2}

\section{はじめに}
\setcounter{page}{7}
１９５０年代より人工知能(AI)の研究が盛んに行われている．AIとはArtificial Intelligenceの略であり，コンピュータに人間と同様の知能を実現させようという試みである．近年AIはロボットやゲームなどの分野でも用いられている(\cite{AIrobo})．ゲームにおけるAIプログラムでは様々なアルゴリズムが提案されているが，その全てが必ずしも精度の高い解を出力するとは限らない．一般的に行動や状態に関する情報が全て与えられているゲームを完全情報ゲームと言う．例えば，オセロや将棋は完全情報ゲームである．AIプログラムを人間と戦わせることも盛んに行われており，将棋では２０１０年にAIプログラムが女流王将に勝利した実績(\cite{akara})がある．\\
　完全情報ゲームに対するAIプログラムでは最善手を判断するために評価関数が用いられている．評価関数とは局面の優劣を評価するために用いられ，その精度が高いほどAIプログラムの性能は向上する．
しかし精度の高い評価関数を作成するにはゲームに関する知識やその知識をプログラムとして表現する必要があり，良い評価関数の作成は困難であることが多い．このような問題に対応する手法にモンテカルロ法がある．モンテカルロ法とは乱数を用いたシミュレーション(プレイアウト)を複数回行い解を近似的に求める統計的な手法である(\cite{monte})．モンテカルロ法は評価関数を用いないため，様々なゲームに有効とされている．\\
　不完全情報多人数ゲームにおいても研究が行われている(\cite{1,2})．不完全情報ゲームとは，お互いの情報が不明なゲームであり，例えば７並べや麻雀，大貧民などが挙げられる．戦略を考えるのが困難な上，運の要素も大きいという特徴がある．完全情報ゲームで有効とされている戦略が不完全情報多人数ゲームに対しても有効かが議論されている．\\
　２００６年から電気通信大学ではUECコンピュータ大貧民大会(\cite{UEC})が毎年開かれている．UECコンピュータ大貧民大会ではサーバークライアントシステムが採用されている．サーバークライアントシステムとはクライアントはサーバーに処理を依頼して，サーバーはクライアントの依頼を受け結果を返信することである．この大会の場合，クライアントがカードを選択しサーバーに提出．サーバーは提出されたカードが正しいかどうかを判定して場の更新を行っている．\\
　今年度で７回目であるが，第４回からモンテカルロ法を使用したクライアントが成果を上げている．この大会に参加するにおいて谷聖一研究室に所属している松藤，長谷川と３人共同でクライアントを実装した．表１では実際にUECコンピュータ大貧民大会に出場した成績である．合計１０チームが参加しており，２ブロックに分かれて上位２チームと，両ブロックで得点が高い３位が決勝に行けるシステムになっている．結果は５位で予選敗退という結果に終わった．
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
	１位 & ２位 & ３位 & ４位 & ５位 \\ \hline
	1459 & 1276 & 1248 & 1009 & 1008 \\ \hline
\end{tabular}
\\表１:予選Aブロックでの戦い
\end{center}
　この大会では１手当たりの制限時間が設けられているため，限られた時間の中でより良質な手を導きだすことがクライアントに要求される．一方，佐藤・松藤・長谷川３人共同で開発したモンテカルロ法クライアントは，制限時間内で良質な解を得るのに十分な回数プレイアウトを実行できなかった．そこで，探索空間が大きくなることを防ぎ，かつ効率的にプレイアウトをさせる手法としてUCT(Upper bound Confidence for Tree)探索を用いてUECコンピュータ大貧民大会クライアントを実装した． \\
　本演習では完全情報２人ゲームでは有効とされているモンテカルロ法を不完全情報多人数ゲームに応用させ，UCT探索を用いてのプレイアウトの効率化する．UECコンピュータ大貧民大会に出場することを目標として不完全情報多人数ゲームにおける強いクライアントを開発することを目標にした．\\
%\section{大会で採用されているプログラム}
　本論文は以下のような構成になっている．２節では作成したクライアントについて述べる．３節では作成したクライアントを用いて実験を行う．４節では今後の課題について述べる．



\section{作成クライアント}
本節では完全情報ゲームで採用さている代表的な手法を説明する．



\subsection{モンテカルロ法}
大貧民におけるモンテカルロ法(\cite{monte})とは，ある局面の全合法手に対して決められた回数プログラム内でプレイアウトして勝率を求め，最も勝率が高かった合法手を実際に選択する手法である．合法手$i$を選択してプレイアウトを行った回数を$s_{i}$，プレイアウトによって得られた報酬(ポイント)の和を$X_{i}$をとする．この時の勝率$\overline{X}_{i}$は
\begin{center}
$\overline{X}_{i} = \displaystyle{\frac{X_{i}}{s_{i}}}$
\end{center}
によって与えられる．本演習で作成したクライアントでは，報酬を表２のように定めた．
%表の挿入
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
	大富豪 &富豪 & 平民を & 貧民 & 大貧民 \\ \hline
	1 & 0.75 & 0.5 & 0.25 & 0 \\ \hline
\end{tabular}\\
表２:プレイアウトの報酬の割り振り
\end{center}
　プレイアウトでは現在の局面からゲームの終わりまでランダムに合法手を選ぶことで局面の展開を行い手札もランダムに配分した．この時貧民や大貧民はジョーカーを持っていないこと，交換したカードは仕様によりわかっているため，それら以外をランダムに配分した．またプレイアウト中の合法手の選択を３回に２回の確率で大会側が配布しているデフォルトクライアントの提出方法に従い，残った確率ではランダムに提出する．これは少しでもゲームの流れに近づけるためである．しかしこの方法では，合法手の数が増加するとプレイアウト回数も増加して処理時間が長くなるという問題が生じる．この問題を改善するためにUCT探索を適用する．

\subsection{UCT探索}
本小節ではモンテカルロ法に多腕バンディット問題のアルゴリズムを利用したUCT探索(\cite{UCT})について説明する．

\subsubsection{多腕バンディット問題}
多腕バンディット問題(\cite{bandit})とは，多くの腕を持つスロットマシンをプレイするギャンブラーに基づく機械学習問題である．\\
　スロットマシンをプレイすると，ギャンブラーは各腕のある確率分布に基づいた報酬を得ることができる．ギャンブラーはスロットマシンを繰り返しプレイして，その報酬の合計を最大化することを目的とする．ギャンブラーはスロットマシンに関する知識を持たず，プレイを繰り返すことで報酬を高く得られる腕を見つけ出し，集中的にプレイすることができるようになるとされている．\\
　多腕バンディット問題は，既に得られている知識に基づいて報酬を最大化することと，他の腕をプレイして，その腕に関する知識を増やすこととのバランスを取る問題であり，強化学習では「収穫と探検のジレンマ」として知られている．\\
　モンテカルロ法の場合に当てはめると，それぞれの合法手を多腕バンディット問題におけるそれぞれの腕として，プレイアウトの勝敗の結果が得られる報酬となる．

\subsubsection{UCT探索}
UCT探索ではプレイアウトを行う合法手に制御を与え，結果的に選択されそうな手に対して多くのプレイアウト回数を行う手法である．この制御のために多腕バンディット問題に対する解法として用いられているUCB1アルゴリズム(\cite{UCB1})を利用しており，合法手の選択はUCB(Upper Confidence Bound，信頼上限)値によって選択を行う．$\overline{X}_{i}$を合法手$i$の勝率，$s_{i}$を探索中に合法手$i$が選択された回数，$n$をその時までに行った総プレイアウト回数とする．合法手$i$のUCB値は以下のように定義される．
	\begin{equation}
	\mathrm{UCB}(i) = \overline{X}_{i} + \sqrt{c{\displaystyle{\frac{\log{n}}{s_{i}}}}}\nonumber
	\end{equation}
　UCB値が最も高い合法手を探索(プレイアウト)する．UCB値の第１項により勝率の高い合法手を，第２項により探索回数の少なさを数値で表し，探索回数が少ないほど選択されやすくする．第１項，第２項により勝率が高く探索回数が少ない合法手が選択されやすくなる．cは探索回数による影響の大きさを与える定数で$c＝２$とした．また制作したプログラムの処理上，合計探索回数を８００回にすることにした．

\subsubsection{UCB1-Tuned}
UCB1-Tuned(\cite{UCB1-Tuned})はUCB1アルゴリズムを改善したものである．UCB1アルゴリズムでUCB値を求める際に使用した$c$を定数として与えるのではなく以下の式によって動的に与える．この時${\sigma_{i}^2}$は報酬の分散である．\\
	\begin{eqnarray}
	V_{i} = {\sigma_{i}^2} + \sqrt{{\displaystyle{\frac{2\log{n}}{s_{i}}}}}\nonumber\\
	c = min(\displaystyle{\frac{1}{4},V_{i}})\nonumber
	\end{eqnarray}

この式を与えることにより分散が考慮され，探索が進んだ時に極端に勝率の低い合法手が探索される回数が減少する．

\subsubsection{Progressive Pruning}
Progressive\ Pruningとは(\cite{propru})勝率と報酬の標準偏差から勝率が取り得る値の区間を推定する．その結果，選ばれる見込みの無い合法手を求め，探索を行わないことでモンテカルロ探索の効率を改善する．
合法手$i$の勝率を$\overline{X}_{i}$，報酬の標準偏差を${\sigma_{i}}$，プレイアウト回数を$s_{i}$とした時に，区間推定を用いて以下のようにそれぞれの合法手の勝率が取り得る値の区間を求める．\\
	\begin{eqnarray}
	\overline{X}_{Li} = \overline{X}_{i} - r{\frac{{\sigma_{i}}}{\sqrt{s_{i}}}}\nonumber\\
	\overline{X}_{Ri} = \overline{X}_{i} + r{\frac{{\sigma_{i}}}{\sqrt{s_{i}}}}\nonumber
	\end{eqnarray}
	
$\overline{X}_{Li}$では合法手$i$がどの程度まで勝率が下がる可能性があるかを推定した値であり，$\overline{X}_{Ri}$では合法手$i$がどの程度まで上がる可能性があるかを推定した値である．つまり合法手$i$の勝率は$[\overline{X}_{Li},\overline{X}_{Ri}]$となる可能性が高い．ここで$r$は信頼係数である．合法手$i$と$j$が存在して，$\overline{X}_{Ri}＜\overline{X}_{Lj}$である場合，合法手$i$の勝率が合法手$j$の勝率より高くなる可能性は低い，よって合法手$i$が選択させる可能性は低いために，これ以上探索しても探索結果に影響を与える可能性は低く，枝狩りすることができる．しかし今回制作したクライアントにこの戦略を加えても強くはならなかった．理由としてプレイアウト回数が足らない，UCB1アルゴリズムとの相性の関係性，プログラムに問題があることが考えられる．

\subsection{必勝手順アルゴリズム}
ゲームAIプログラムを作成するにおいて最も強い戦略とは全探索することである．しかし全探索には膨大な時間を要するため，制限時間内での探索は困難である．一方，大貧民では特定の状況の中では必ず上がれる手順が存在し，それを容易に実装することができる．特定の状況とは以下のことを言う．ある局面において自分のターンから始まる場合，持っている手札の中で切り札以外のカードが１手以下ならば必勝手順が存在する．ここで切り札とはそのカードを出せば他のプレイヤーが必ずパスになるカードのことを指す．また場に他プレイヤーのカードが存在した場合，そのカードの上に切り札を提出し，残りの手札が上記の「自分のターンから始まる場合」に当てはまるならば必勝手順が存在する．\\
　この戦略を用いることでプレイアウトをする必要がなくなるために時間が短縮され，特定の状況の中で必ず上がることができる．



\section{実験}
作成したクライアントが強くなるか，試合回数を４００回として実験する．対戦相手は第５回優勝クライアントであるsnowl(\cite{snowl})と大会側から配布されているデフォルトのクライアントを２つ採用する．デフォルトのクライアントとは最低限ゲームが動作するクライアントであり，カードを小さい順に提出するクライアントである．デフォルトのクライアント以外のクライアントの実行時間は全て統一して実験を行った．１試合毎に貰えるポイントの割り振りは表３の通りである．\\
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
	大富豪 &富豪 & 平民 & 貧民 & 大貧民 \\ \hline
	5 & 4 & 3 & 2 & 1 \\ \hline
\end{tabular}
\\表３:報酬の割り振り
\end{center}
　表４では必勝手順の有無を対戦させた．
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
	snowl & 必勝有 & 必勝無 & def & def \\ \hline
	1544 & 1387 & 1323 & 914 & 832 \\ \hline
\end{tabular}
\\表４:必勝手順の有無で対戦させた結果
\end{center}
　表５ではUCT探索の有無で対戦させた．
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
	snowl & UCT有 & UCT無 & def & def \\ \hline
	1529 & 1349 & 1277 & 935 & 910 \\ \hline
\end{tabular}
\\表５:UCT探索の有無で対戦させた結果
\end{center}
　表６ではプレイアウトの回数を変更して対戦させた．
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
	snowl & 5000回 & 800回 & def & def \\ \hline
	1552 & 1443 & 1321 & 844 & 840 \\ \hline
\end{tabular}
\\表６:プレイアウト回数を変えて対戦させた結果
\end{center}
　表７ではUCB1アルゴリズムとUCB1アルゴリズムを改善したUCB1-Tunedを対戦させた．
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
	snowl & UCB1-Tuned & UCB1 & def & def \\ \hline
	1506 & 1429 & 1396 & 870 & 799 \\ \hline
\end{tabular}
\\表７:UCB1-TunedとUCB1を対戦させた結果
\end{center}

表４から，必勝手順が有効である結果になった．しかしポイントの差が小さいのでプレイアウトの精度が高いことが考えられる．表５ではUCT探索の有効性が見受けられる．表６では勝率が探索回数に依存していることがわかる．snowlに勝てないのは，プレイアウトの精度がsnowlの方が高いこと，根本的な問題として作成したクライアントにバグが存在する可能性がある．表７よりUCB1-Tunedが強くなることがわかるが，差が小さいので思った以上の結果を残すことができなかった．
\section{おわりに}
本演習では，モンテカルロ法によるプレイアウト中の手や手札をランダム選択することに加えて，知り得る情報を考慮した選択手法を提案し，プレイアウト割り振り法をUCT探索に基づいて実装した．製作中での試行ではsnowlには及ばないものの，得点を向上することができ，これらの手法が有効であると確認できた．しかし2011年に開催された第７回優勝クライアントを検証した結果，UCT探索とUCB1-Tunedは既に実装されていることがわかった．
今後の課題は，制作したクライアントにバグが存在するか見直すこと．またその他に不完全情報多人数ゲームで有効なアルゴリズムを実装することが課題である．








\end{multicols}


\begin{thebibliography}{3}%参考文献({2}：2つ参考文献があるという意味)

\bibitem{AIrobo}
日本ロボット学会. http://www.rsj.or.jp/. アクセス日2013.02.2 20:00.


\bibitem{akara}
清水女流王将 VS あから2010, http://blog.livedoor.jp/hana180sx/archives/51628748.html, アクセス日2013.01.21 18:00.

\bibitem{monte}
B.Br\"{u}gmann. Monte Carlo Go. Technical report, Physics Department, Syracuse University, 1993.


\bibitem{1}
J. Sch\"{a}fer, M. Buro, and K. Hartmann. The UCT Algorithm Applied to Games with Imperfect Informaiton. Diploma thesis. Otto-von-Guericke-Universit\"{a}t Magdeburg, 2008.

\bibitem{2}
N.R. Strurtevant. An Analysis of UCT in Multi-player Games. Proceedings of the 6th inter-national conference on Computers ad Games, pp. 37-49, 2008.

\bibitem{UEC}
電気通信大学, UECコンピュータ大貧民大会, 
http://uecda.nishino-lab.jp/,  2006年$\sim$． 


\bibitem{UCT}
L. Kocsis, C. Szepesv\"{a}ri. Bandit based monte-carlo planning. In Enropean Conference on Machine Learning, pp. 282 - 293, 2006.

\bibitem{bandit}
B.Bouzy and T.Cazenave. Computer go: An AI oriented survey. Artificial Intelle-gence, 132(1): 39-103, 2001. 


\bibitem{UCB1}
P.Auer, N. Cesa-Bianchi, P.Fischer. Finite-time analysis of the multiarmed bandit problem. machine Learning, 47 (2/3), pp. 235 - 256, 2002.

\bibitem{UCB1-Tuned}
B. Bouzy and G. Chaslot. Bayesian generation and integration of k-nearest-neighbor patterns for 19x19 go. In G. Kendall and Simon Lucas, editors, IEEE 2005 Sympo-sium on Computational.

\bibitem{propru}
B.Bouzy.Move-Pruning Techniques for Monte-Carlo Go.CG 2005 LNCS,vol.4250,pp.104-119,SpringerHeidelberg,2006.

 \bibitem{snowl}
須藤\ 弥,成澤\ 和志,篠原\ 歩, UECコンピュータ大貧民大会向けクライアント「snowl」の開発, 
http://uecda.nishino-lab.jp/sympo/images/Suto.pdf,  2007年. 




\end{thebibliography}%参考文献終わり

\end{document}















