% !TEX encoding = UTF-8 Unicode
\documentclass[dvipdfm]{beamer}
\usepackage{multicol}
\usepackage{ascmac}
\usetheme{Madrid}
%\usetheme{Rochester}
\AtBeginDvi{\special{pdf:tounicode EUC-UCS2}}

%\setbeamertemplate{footline}[frame number]

\setbeamertemplate{navigation symbols}[]

%\usetheme{Madrid}
%\usepackage{fancybx}
%\usepackage{beamerthemeshadow}
%\usepackage{tani_resume}

%プレゼンの基本情報aaaasaさ
\title{UCT探索を用いた大貧民クライアント}
\date[卒業演習発表会]{}
\author{佐藤友啓}
\institute[谷 聖一研究室]{日本大学文理学部情報システム解析学科\\谷 聖一研究室}


%ここからスライドを入れてく
\begin{document}

%本文中で\section*{目次}を使えば自動的に目次が作られる

\frame{\titlepage}	%タイトルページ

%\section{目次}		%目次
\frame{
	\tableofcontents
}


%１ページ目

\section{はじめに}
\frame{
\frametitle{1\ \ \ はじめに}
\begin{multicols}{2}

近年，コンピュータゲームは\\年々発展してきている\\[1em]
完全情報２人ゲームである\\オセロや将棋などが有名\\[1em]
	\begin{itembox}[l]{完全情報ゲームとは}
全ての意思決定点において相手の駒や状況など情報が全て与えられているゲーム
\if0
$\Leftrightarrow$\ 不完全情報ゲーム
\fi
	\end{itembox}\\[1em]
	
	\begin{figure}[htbp]
	\begin{center}
	\includegraphics[width=3cm,angle=0,clip]{image.eps}
	\end{center}
	\end{figure}
	
	\begin{figure}[htbp]
	\begin{center}
	\includegraphics[width=3cm,angle=0,clip]{shougi.eps}
	\end{center}
	\end{figure}


\end{multicols}

\begin{center}
	\scriptsize{画像引用元\\http://uguisu.skr.jp/othello/}\\
	\scriptsize{http://matome.naver.jp/odai/2128989764455845801}
\end{center}
}


\frame{
	\frametitle{1\ \ \ コンピュータゲーム研究の歴史}
	\underline{完全情報２人ゲームの例}\\
	\begin{itemize}
	\if0
	\item チェッカー: 世界チャンピオンに勝利(1994)\\[1em]
	\fi
	\item オセロ 	  : 世界チャンピオンに勝利(1997)\\[1em]
	\item チェス 	  : 当時の世界チャンピオンのカスパロフに勝利(1997)\\[1em]
	\item 将棋     	  : 女流王将に勝利(2010)\\[1em]
	\item 囲碁     	  : 4子で男子プロに勝利(2012)\\[1em]
	\end{itemize}

	\begin{multicols}{2}
			\begin{figure}
			\begin{flushright}
			\includegraphics[width=1.5cm,angle=0,clip]{check.eps}
				\end{flushright}
			\end{figure}
			
			\begin{figure}
			\begin{center}
			\includegraphics[width=2cm,angle=0,clip]{tyes.eps}
			\end{center}
			\end{figure}

	\end{multicols}
	\begin{center}
	\scriptsize{画像引用元\\http://210.150.246.43/game.hp/checker/index/1.html\\
	http://aitiken22.blog54.fc2.com/blog-entry-145.html}
	\end{center}
}


\frame{
	\frametitle{1\ \ \ はじめに}
	\fbox{\textgt{しかし不完全情報多人数ゲームは？？}}\\[1em]
完全情報２人ゲームの戦略を不完全情報多人数ゲームに\\応用することができるの？？\\[1em]
本演習ではUECコンピュータ大貧民大会に参加することを目標として，不完全情報他人数ゲームにおける強いクライアントを実装した\\[1em]
\begin{multicols}{2}
	\begin{figure}[htbp]
	\begin{center}
	\includegraphics[width=4cm,angle=0,clip]{top.eps}
	\end{center}
	\end{figure}
	
	\if0
	\begin{figure}[htbp]
	\begin{center}
	\includegraphics[width=4cm,angle=0,clip]{bb.eps}
	\end{center}
	\end{figure}
	\fi
	\begin{itembox}[l]{不完全情報ゲームとは}
		意思決定点において相手の駒や状況などで不確定な要素があるゲーム(７並べや麻雀など)
	\end{itembox}\\[1em]

\end{multicols}
\begin{center}
	\scriptsize{画像引用元　http://uecda.nishino-lab.jp/2012/}
\end{center}
}

\frame{
	\frametitle{1\ \ \ はじめに}
	今回クライアントを実装するにおいて\\
	谷聖一研究室に所属している松藤・長谷川と３人共同で実装しました\\
	ある程度まで完成させた後，３人それぞれの演習へ分かれています\\[1em]
	→佐藤　　クライアントをさらに強化させていく\\
	→松藤　　大会に参加しての考察\\
	→長谷川　人間対パソコンを実現させるプログラムの作成\\[1em]
	まず大会概要と３人共同で開発したクライアントの説明をした後に\\
	私の演習について話をしていきます
		
}



\if0
\subsection{AIの難しさ}
\frame{
	\frametitle{1.2\ \ \ AI(Artificial Intelligence，人工知能)の難しさ}
	
	\begin{itembox}[l]{探索空間が大きい}
全探索しようものなら膨大な時間がかかる
	\end{itembox}\\[1em]
	
	\begin{itembox}[l]{評価関数を作るのが困難}
	局面ごとの最適手が必ず勝利に結びつくわけではない\\
	評価関数を作ること自体困難である
	\end{itembox}\\[2em]
	{\small (評価関数とはゲームの局面の状態を静的に評価し数値に変換する関数のこと)}

}
\fi

\section{UECコンピュータ大貧民大会2012とは}
\frame{
	\frametitle{2\ \ \ UECコンピュータ大貧民大会2012とは}
	2012年11月24日に電気通信大学で開催された\\大貧民のAI同士を戦わせる大会\\[1em]
	%毎年開催されていて今年で７回目
	{\color{red}無差別級}と{\color{red}ライト級}がある\\[1em]
	\begin{itemize}
	\item {\color{red}無差別級}\\
	機械学習的な手法を用いたりシミュレーションさせるクライアント\\[1em]

	\item {\color{red}ライト級}\\
	ヒューリスティック手法を用いたクライアント\\[2em]
	\end{itemize}
	
	{\scriptsize (ヒューリスティックとは正しい解を導くことができるか保証はないけれどある程度のレベルで正解に近い解を得ることができる．または精度は保証されないが回答に至るまでの時間が短い)}
}


\subsection{今回採用しているルール}
\frame{
	\frametitle{2.1\ \ \ 今回採用しているルール}
	\setlength{\columnseprule}{0.1mm}	%縦線を入れる
	\begin{multicols}{2}				%２段組にする
	\textgt{採用しているルール}\\
	\begin{itemize}
	\item 縛り\\[1em]
	\item ダイヤの３から試合開始\\[1em]
	\item スペードの３\\[1em]
	\item 自分以外パスの時，さらに自分が続けてだせる\\[1em]
	\item ８切り\\[1em]
	\item 革命(同じ数なら４枚以上，階段なら５枚以上)\\[1em]
	\item 試合開始直後の交換制度
	\end{itemize}
	\columnbreak					%右側に移る
	\textgt{採用していない代表的なルール}\\
	\begin{itemize}
	\item １１バック\\[1em]
	\item 都落ち\\[1em]
	\item あがり札に関する禁則\\[1em]
	\item 片しばり，階段しばり\\[3em]など
	\end{itemize}
	\end{multicols}
}

\if0
\subsection{大会で使用しているプログラム}
\frame{
	\frametitle{2.2\ \ \ 大会で使用しているプログラム}
	\begin{itemize}
	\item カードの配布や場の管理を行う{\color{red}サーバープログラム}\\[1em]
	\item プレイヤーに対応する{\color{red}クライアントプログラム}\\[1em]
	\item ５人のプレイヤーに対応する５つのクライアントプログラムを\\サーバープログラムに繋いで対戦を行う\\[1em]
	\item 上記のプログラムは大会サイトからダウンロード可能\\
	http://uecda.nishino-lab.jp/2012/\\[1em]
	\end{itemize}
}
\fi

\subsection{大会で使用しているプログラム}
\frame{
	\frametitle{2.2\ \ \ 大会で使用しているプログラム}
	\begin{center}
	サーバークライアントシステム
	\end{center}
	\begin{figure}[htbp]
	\includegraphics[width=7cm,angle=0,clip]{a3.eps}
	%\caption{picture of the opening remarks}
	%\label{fig2}
	\end{figure}
	\if0
	\item クライアントはサーバーに処理を依頼する．\\[1em]
	\item サーバーはクライアントの依頼を受け，結果を返信する．\\[2em]
	\fi
	今回の場合
	\begin{itemize}
	\item クライアントがカードを選択しサーバーに提出\\
	\item サーバーは提出されたカードが正しいかどうか判定\\
	\item 場の更新(縛りや革命など)       など\\
	\end{itemize}
		\begin{center}
	\scriptsize{画像引用元　http://entcog.c.ooco.jp/entcog/event/20120318/nishino.pdf}\\
	\end{center}

}

\subsection{プレイ画面}
\frame{
	\frametitle{2.3\ \ \ プレイ画面}
	\begin{figure}[htbp]
	\begin{center}
	\includegraphics[width=11cm,angle=0,clip]{aa.eps}
	%\caption{picture of the opening remarks}
	%\label{fig1}
	\end{center}
	\end{figure}
}

\frame{
	\frametitle{2.3\ \ \ プレイ画面}
	\begin{figure}[htbp]
	\begin{center}
	\includegraphics[width=11cm,angle=0,clip]{bb.eps}
	%\caption{picture of the opening remarks}
	%\label{fig2}
	\end{center}
	\end{figure}
}

\if0
\subsection{デフォルトクライアントの説明}
\frame{
	\frametitle{2.4\ \ \ デフォルトクライアントの説明}
	\ \ 最低限ゲームが動作するクライアントが大会から配布されている\\[1em]
	\begin{itemize}
	\item 小さい順でカードを出す(革命中なら逆順)\\[1em]
	\item 大富豪・富豪の時のカード交換も小さい順で\\いらないカードを出す\\[1em]
	\item 自分のターンからなら階段・枚数組・単体のカード枚数が多い順に出していく\\[1em]
	\item ジョーカーは積極的に使う\\
	(出せるカードがジョーカーしかない場合に必ず出される)
	\if0
	{\scriptsize \\[1em]\ 例：場に{\color{red}３が２枚($\diamondsuit$・$\heartsuit$)}あって自分の手札に\\\ {\color{red}４($\spadesuit$)}，{\color{red}５($\spadesuit$)}，{\color{red}５($\clubsuit$)}，{\color{red}ジョーカー}を持っていたら\\
	{\color{red}４とジョーカー}を出す}\\
	\fi
	
	\end{itemize}
	
}

\fi

\if0
	ルールに従って着手できる点(合法手)の数を，ゲームが終わるまでの手数だけ掛けると探索空間はとてつもなく大きくなる．特に囲碁などは盤面もでかく毎ターンの合法手の数は大きくなるので全探索しようものなら膨大な時間がかかってしまう．

	局面ごとの最適手が勝利に必ずしも結び付かない場合があるため．そのためその場の状況だけで判断する静的評価関数を作ることは困難．つまりある局面における良い手が多く存在し，正確な最適手を選ぶことができない．
\fi


%　　チェッカー　10の20〜30乗
%　　リバーシ　　10の28〜60乗
%　　チェス　　　10の50〜120乗
%　　将棋　　　　10の71〜220乗
%　　囲碁　　　　10の171〜360乗

\if0
\section{実際に作ったクライアントの戦略}
\frame{
	\frametitle{3\ \ \ 実際に作ったクライアントの戦略}
	\begin{itemize}
	\item プログラムで800回シミュレーションさせる\\(詳しくは後で説明)\\[1em]
	\item 残り手札１枚ならシミュレーションしないで提出する\\[1em]
	\item 必勝手順があればそれを活用する(詳しくは後で説明)\\
	{\scriptsize 例：８と５を持っていて自分のターンからなら８出して５を出すと必ず上がれる}\\[1em]
	\item 大富豪・富豪で手札交換する時，小さい順で枚数組を崩さない，かつ$\diamondsuit$３と８以外のカードを選ぶ\\[1em]
	
	\end{itemize}
}
\fi


\section{３人共同で実装したクライアントの戦略}

\frame{
	\frametitle{戦略の詳しい説明の前に用語説明}
	\begin{itemize}
	\item {\color{red}合法手}\\
	ある局面において場の状況から\\ルールに従って着手できる手\\[2em]
	\item {\color{red}プレイアウト(シミュレーション)}\\
	ある局面から，ゲームの終局までランダムに\\合法手を選び進むこと\\[2em]
	\item {\color{red}切り札}\\
	これを出せばみんな必ずパスしてくれるカード\\
	例: ８や，(革命していない時の)２の２枚出し\ \ など\\[2em]
	
	
	\end{itemize}
	以後こう呼ぶことにする

}

\frame{
	\frametitle{3\ \ \ ３人共同で実装したクライアントの戦略}
	ここから３人共同で実装したクライアントの説明をする
}

\subsection{必勝手順アルゴリズム}
\frame{
	\frametitle{3.1\ \ \ 必勝手順アルゴリズム}
	{\scriptsize 注：ジョーカーはすでに使われている\\
	\ \ \ \ \ 階段は考慮しないことを前提とする(時間がなかったので)}\\[1em]
	
	
	\begin{itembox}[l]{自分のターンから始まる場合}
	持っている手札の中で切り札以外のカードが１手以下であるならば
	必勝手順が存在する
	\end{itembox}\\[1em]
	
	\if0
	{\scriptsize 例 : 手札が{\color{red}４($\diamondsuit$)}，{\color{red}８($\diamondsuit$)}，{\color{red}８($\heartsuit$)}，{\color{red}２($\diamondsuit$)}，{\color{red}２($\heartsuit$)}　ならば
	{\color{red}２($\diamondsuit$)}・{\color{red}２($\heartsuit$)}の枚数組を\\出して{\color{red}８($\diamondsuit$)}，{\color{red}８($\heartsuit$)}の枚数組を出して{\color{red}４($\diamondsuit$)}を単体で出せば必ず上がる}\\[1em]
	\fi
	\begin{itembox}[l]{場にカードがあった場合}
	カードの上に切り札を出して残りの手札が「自分のターンから始まる場合」に該当するならば必勝手順が存在する
	\end{itembox}
	
}









\subsection{モンテカルロ法を用いた提出方法}
\frame{
	\frametitle{3.2\ \ \ モンテカルロ法を用いた提出方法}
	\textgt{{\Large モンテカルロ法のゲームへの応用}}\ \ \ (B.Br\"{u}gmann. 1993.)\\[2em]
	モンテカルロ法とは\\
	{\color{red}乱数を用いてシミュレーションを行う統計的な方法}\\[2em]
	ある局面の各合法手に対してプログラム内でプレイアウトする\\
	何回かプレイアウトして勝率を求め，\\[2em]
	最も勝率が高かった合法手を実際に選択する
}

\frame{
	\frametitle{3.2\ \ \ モンテカルロ法を用いた提出方法}
	モンテカルロ木探索の例(○×ゲーム)
	\begin{figure}[htbp]
	\begin{center}
	\includegraphics[width=5cm,angle=0,clip]{monte.eps}
	%\caption{picture of the opening remarks}
	%\label{fig2}
	\end{center}
	\end{figure}
	\scriptsize{画像引用元　http://repository.dl.itc.u-tokyo.ac.jp/dspace/bitstream/2261/25490/1/K-01865.pdf}

}

\frame{
	\frametitle{3.2\ \ \ モンテカルロ法を用いた提出方法}
	
	\begin{shadebox}
	合法手iを選択してプレイアウトを行った回数を$s_{i}$，\\
	プレイアウトによって得られた報酬(ポイント)の総和を$X_{i}$とする．この時の勝率$\overline{X_{i}}$は
	\begin{center}
	$\overline{X_{i}} = \displaystyle{\frac{X_{i}}{s_{i}}}$
	\end{center}
	によって与えられる．
	\end{shadebox}\vspace{0.3in}
	報酬の振り分け\\
	\begin{table}[htb]
	\begin{tabular}{|c|c|c|c|c|} \hline
	大富豪 &富豪 & 平民 & 貧民 & 大貧民 \\ \hline
	1 & 0.75 & 0.5 & 0.25 & 0 \\ \hline
	\end{tabular}
	\end{table}

}

\if0
\frame{
	\frametitle{3.2\ \ \ モンテカルロ法を用いた提出方法}
	%大貧民の場合，自分のターンになった時に\\毎回シミュレーションさせます．\\[1em]
	まず現在の場の状況から合法手を考える\\[1em]
	例：自分のターンから始まるとして手札に\\{\color{red}３($\spadesuit$)}，{\color{red}５($\heartsuit$)}，
	{\color{red}５($\diamondsuit$)}を持っていたら\\この場合{\color{red}３($\spadesuit$)}，{\color{red}５($\heartsuit$)}，
	{\color{red}５($\diamondsuit$)}，{\color{red}５の２枚出し($\heartsuit$・$\diamondsuit$)}の４つの合法手があることになる\\[1em]
	各合法手に対してプレイアウトを決められた回数分行い，\\それぞれ勝率を求める\\[1em]
	%相手の手札はわからないのでランダムに配る\\
	{\color{red}勝率が最も高いカードを実際に提出する}
}
\fi


\frame{
	\frametitle{3.2\ \ \ モンテカルロ法を用いた提出方法}
	\begin{figure}[htbp]
	\begin{center}
	\includegraphics[width=9.5cm,angle=0,clip]{gouhoute.eps}
	%\caption{picture of the opening remarks}
	%\label{fig2}
	\end{center}
	\end{figure}
	それぞれの合法手に対してその合法手を出したとして\\
	残りのゲームをプレイアウトする

}


\frame{
	\frametitle{3.2\ \ \ モンテカルロ法を用いた提出方法}
	プレイアウトする時の相手の提出方法は，\\[1em]
	\textgt{乱数を使ってランダムに配分，提出}をしている\\[1em]
	%ランダムを使う理由は相手はどんな手札，提出方法かまったくわからない，ランダムなら最善手をプレイアウトしてくれる確率が０以上になる，決められた提出方法に乗っ取るとそれ以外の戦略に応用できなくなる
	\begin{itembox}[l]{少しでも正確にするために以下の情報を取り入れた}
	\begin{itemize}
	\item 最初に行動した人には$\diamondsuit$の３を持たせる\\[1em]
	\item 自分が交換したカードはわかるのでその情報を使う\\[1em]
	\item 貧民・大貧民はジョーカーを持っていない\\
		大貧民は$\spadesuit$の２を持っていない\\(そういう仕様になっている)\\[1em]
	\end{itemize}
	\end{itembox}\\[1em]
	これ以外をランダムにした
}


\subsection{対戦}
\frame{
	\frametitle{3.3\ \ \ 対戦}
	下のグラフでは	下記の５つを対戦させたものである\\
	・モンテカルロ法を使ったクライアント(２位)\\
	・これから発表するUCT探索を加えたもの(１位)\\
	・デフォルトクライアントが３つ(３〜５位)\\
	\begin{figure}[htbp]
	\begin{center}
	\includegraphics[width=12cm,angle=0,clip]{a4.eps}
	%\caption{picture of the opening remarks}
	%\label{fig2}
	\end{center}
	\end{figure}

}



\subsection{結果発表}
\frame{
	\frametitle{3.4\ \ \ 結果発表}

	今回３人で共同で開発したクライアントは\\
	モンテカルロ法を使った提出方法までですが\\[1em]
	実際に大会で使用したクライアントはこの後紹介する\\
	UCB1アルゴリズムを採用したクライアントである

}


\frame{
	\frametitle{3.4\ \ \ 結果発表}
	大会の参加チームは全１０チーム\\[1em]
	予選と決勝がありそれぞれ400回ずつ高速対戦を行う\\[1em]
	予選は５チームずつの２ブロックに分かれての対戦\\[1em]
	\ \ \ ポイントの割り振り
	\begin{table}[htb]
	\begin{tabular}{|c|c|c|c|c|} \hline
	大富豪 &富豪 & 平民を & 貧民 & 大貧民 \\ \hline
	5 & 4 & 3 & 2 & 1 \\ \hline
	\end{tabular}
	\end{table}
	上位２チーム，そして両ブロックで得点が高かった\\平民が決勝に進める\\[2em]

	
	結果は...............
}

\frame{
	\frametitle{3.4\ \ \ 結果発表}
	\begin{center}
	努力実らず\ \ {\huge \textgt{惨敗！！！！！！}}\\[3em]
	\end{center}


	\setlength{\columnseprule}{0.1mm}	%縦線を入れる
	\begin{multicols}{2}				%２段組にする
	\textgt{Aブロック(点数一覧)}\\[1em]
	\begin{itemize}
	\item 1459\\[1em]
	\item 1276\\[1em]
	\item 1248\\[1em]
	\item 1009\\[1em]
	\item 1008\ \ \ \ \ ←
	\end{itemize}
	\columnbreak					%右側に移る
	\textgt{Bブロック(点数一覧)}\\[1em]
	\begin{itemize}
	\item 1452\\[1em]
	\item 1452\\[1em]
	\item 1428\\[1em]
	\item 837\\[1em]
	\item 831
	\end{itemize}
	\end{multicols}
}


\section{佐藤実装クライアント}
\frame{
	\frametitle{4\ \ \ 佐藤実装クライアント}
	以下佐藤が実装したクライアントの説明である
}


\subsection{採用手法の欠点}
\frame{
	\frametitle{4.1\ \ \ 採用手法の欠点}
	例えばジョーカーを持っているとすると合法手の数は増える\\[1em]
	{\color{red}3($\diamondsuit$)}と{\color{red}４($\diamondsuit$)}と{\color{red}ジョーカー}を持っている場合で考える\\[1em]
	\begin{itemize}
	\item 単体出しの場合\\
	{\color{red}3($\diamondsuit$)}，{\color{red}４($\diamondsuit$)}，{\color{red}ジョーカー}の３通り\\[1em]
	\item 枚数組の場合\\
	{\color{red}３($\diamondsuit$)}と{\color{red}ジョーカー($\heartsuit$と$\clubsuit$と$\spadesuit$の役割を１つ選ぶ)}，\\
	{\color{red}４($\diamondsuit$)}と{\color{red}ジョーカー($\heartsuit$と$\clubsuit$と$\spadesuit$のどれか)}の６通り\\[1em]
	\item 階段の場合\\
	{\color{red}３($\diamondsuit$)}と{\color{red}４($\diamondsuit$)}と{\color{red}ジョーカー}，\\
	{\color{red}ジョーカー}と{\color{red}３($\diamondsuit$)}と{\color{red}４($\diamondsuit$)}の２通り\\[1em]
	\end{itemize}
	合計１１通りも存在する
	
}

\frame{
	\frametitle{4.1\ \ \ 採用手法の欠点}

	ゲーム序盤ならば３０通り以上合法手が存在する可能性がある\\[1em]
	その度に決められた回数プレイアウトさせると処理時間は膨大\\[1em]
	しかしプレイアウト回数を減らすと弱くなってしまう\\[1em]
	実行時間は大会側から決められている\\[4em]
	
	→時間はかけたくないけど強いクライアントを作りたい
}

\subsection{UCT探索}
\frame{
	\frametitle{4.2\ \ \ UCT探索}
	\textgt{そこで登場するのが\\\ \ {\color{red}UCT探索！！}}\\[2em]
	
	\if0
	{\scriptsize \ \ \ \ これが登場する背景には多腕バンディット問題なるものがあるが\\
	\ \ \ \ 余計に長くなりそうなので省略}\\[1em]
	\fi
	各合法手に対して決められた回数分プレイアウトさせるのではなく\\[1em]
	\underline{決められた回数で旨く各合法手に割り振るもの！！}\\[1em]
	\underline{勝率が高く，プレイアウト数が少ない合法手に多く割り振る}\\[1em]

}

\subsubsection{UCB1アルゴリズム}
\frame{
	\frametitle{4.2.1\ \ \ UCB1アルゴリズム\\(P.Auer, N. Cesa-Bianchi, P.Fischer\ 2002)}
	\if0
	UCB     ... Upper Confidence Bound. 信頼上限
	   イメージとしては10台のスロットマシーンをそれぞれ何回か試して
            どの台を集中的に選ぶか，という感じ．あまり試していない台が選ばれやすい．
            多く試した台では勝率が高い台が選ばれやすい．
         UCT     ... Upper Confidence bound for Tree
            UCBを各深さで行う．最良優先のような探索になる．
          \fi
	合法手の選択はUCB(Upper Confidence Bound)値によって選択を行う\\[1em]
	\begin{shadebox}

	$\overline{X}_{i}$を合法手$i$の勝率，$s_{i}$を探索中に合法手iが選択された回数，
	$n$をその時までに行った総プレイアウト回数とする．\\
	合法手$i$のUCB値は以下のように定義される．
	\begin{center}
	$UCB(i)$ = $\overline{X}_{i}$ + $\sqrt{c{\displaystyle{\frac{\log{n}}{s_{i}}}}}$
	\end{center}
	\end{shadebox}\vspace{0.2in}
	UCB値が最も高い合法手をプレイアウトする\\[1em]
	UCB値の第１項により勝率の高い合法手\\
	第２項ではプレイアウト回数が少ないと値が大きくなる\\[1em]
	$c$はプレイアウト回数による影響の大きさを与える定数で(基本は$c=2$)
}

\frame{
	\frametitle{4.2.1\ \ \ UCB1アルゴリズム}	

{\Large UCT探索木の例}

	\begin{figure}
	\begin{center}
	\includegraphics[width=7cm,angle=0,clip]{uct.eps}
	\end{center}
	\end{figure}
	%\scriptsize{画像引用元\\http://www.logos.ic.i.u-tokyo.ac.jp/~miki/doc/master.pdf}\\[4em]
		\if0
	\fbox{１}　→　白の勝ち\\
	\fbox{０}　→　白の負け\\
	\fi
	{\Large ノードの数値は(獲得報酬/探索回数)}
}

\frame{
	\frametitle{4.2.1\ \ \ UCB1アルゴリズム}
	自分のターンから始まる時，800回目のプレイアウトを\\
	選択する時の情報を表示させた
	\begin{figure}
	\begin{center}
	\includegraphics[width=10.8cm,angle=0,clip]{ucbdebug.eps}
	\end{center}
	\end{figure}
}

\frame{
	\frametitle{4.2.2\ \ \ UCB1-Tuned(B. Bouzy and G. Chaslot.\ 2005)}
	
	以下大会後に取り入れた戦略である
}


\subsubsection{UCB1-Tuned}
\frame{
	\frametitle{4.2.2\ \ \ UCB1-Tuned(B. Bouzy and G. Chaslot.\ 2005)}
	UCB1アルゴリズムを改善したものである\fbox{	$UCB(i)$ = $\overline{X}_{i}$ + $\sqrt{c{\displaystyle{\frac{\log{n}}{s_{i}}}}}$}\\[1em]
	\begin{shadebox}	
	UCB1アルゴリズムでUCB値を求める際に使用した$c$を定数として与えるのではなく以下の式によって動的に与える．\\この時${\sigma_{i}^2}$は報酬の分散である．
	\begin{eqnarray}
	c = min(\frac{1}{4},V_{i})\nonumber\ \ ,\ \ \ \ \ \ 
	V_{i} = {\sigma_{i}^2} + \sqrt{{\frac{2\log{n}}{s_{i}}}}\nonumber
	\end{eqnarray}
	\end{shadebox}\vspace{0.2in}
この式では分散が考慮されるので，プレイアウトの回数が進むにつれ，\\極端に勝率の低い合法手がプレイアウトされる回数が減少する\\[1em]
	（分散とは平均値からのばらつき具合を数値化したもの）

}

\frame{
	\frametitle{4.2.2\ \ \ UCB1-Tuned(B. Bouzy and G. Chaslot.\ 2005)}
\fbox{$UCB(i) = \overline{X}_{i} + \sqrt{c{\displaystyle{\frac{\log{n}}{s_{i}}}}}$}
\fbox{
	$c = min(\frac{1}{4},V_{i})$\ \ ,\ \ \  
	$V_{i} = {\sigma_{i}^2} + \displaystyle{\sqrt{{\frac{2\log{n}}{s_{i}}}}}$ }\\[1em]

	分散の値が大きい時，言い換えると\\
	\begin{itembox}[l]{プレイアウトの結果が(１位，５位，３位)等バラけている時}
		$V_{i}$の値が上がり，$c$には$\frac{1}{4}$が入る
	\end{itembox}\\[1em]


	分散の値が小さくなるにつれ，言い換えると\\
	\begin{itembox}[l]{プレイアウトの結果が(５位，４位，５位)等収束していくほど}
		$V_{i}$の値が下がり，$c$の値も下がる → 従ってUCB値が減少する\\
		結果，極端に勝率の低い合法手のプレイアウトされる回数が減少する
	\end{itembox}\\[1em]
	
}



\if0
\subsubsection{Progressive Pruning}
\frame{
	\frametitle{3.4.3\ \ \ Progressive Pruning\ \ (B. Bouzy.2006)}
	
	{\color{red}勝率が取り得る値の区間を推定する}\\
	→選ばれる見込みの無い合法手のプレイアウトを行わない\\[1em]
	\begin{shadebox}
	$\overline{X}_{i}$を合法手iの勝率，$s_{i}$を探索中に合法手iが選択された回数，\\
	${\sigma_{i}}$を報酬の標準偏差とした時に，以下のようにそれぞれの合法手の勝率が取り得る値の区間を推定する．
	\begin{eqnarray}
	\overline{X}_{Li} = \overline{X}_{i} - r{\frac{\sigma_{i}}{\sqrt{s_{i}}}}\ \ ,\ \ \ \ \ 
	\overline{X}_{Ri} = \overline{X}_{i} + r{\frac{\sigma_{i}}{\sqrt{s_{i}}}}\nonumber\\\nonumber
	\end{eqnarray}
	ちなみに$r$は信頼係数である．
	\end{shadebox}\vspace{0.2in}


	$\overline{X}_{Li}$は合法手$i$の勝率がどの程度まで下がる可能性があるかを推定した値\\
	$\overline{X}_{Ri}$は合法手$i$の勝率がどの程度まで上がる可能性があるかを推定した値\\[1em]	
}

\frame{
	\frametitle{3.4.2\ \ \ Progressive Pruning}
	従って合法手$i$の勝率は$[\overline{X}_{Li}\ ,\ \overline{X}_{Ri} ]$となる可能性が高い\\[4em]
	一番高い勝率の合法手の$\overline{X}_{L}$と各合法手の$\overline{X}_{R}$を比べて\\[1em]
	後者の方が劣っている場合\\その合法手の勝率が高くなる見込みは低いのでプレイアウトを行わない
}

\frame{
	\frametitle{3.4.2\ \ \ Progressive Pruning}
	下の図はProgressive Pruningのイメージ図である
	\begin{figure}[htbp]
	\begin{center}
	\includegraphics[width=12.5cm,angle=0,clip]{kukan.eps}
	\end{center}
	\end{figure}
	\begin{center}
	\scriptsize{画像引用元\\https://dspace.jaist.ac.jp/dspace/bitstream/10119/9649/7/paper.pdf}
\end{center}
	
}

\fi

\section{おわりに}
\frame{
	\frametitle{5\ \ \ おわりに}

	大会では良い結果がでなかったものの，\\
	これらの手法が有効であると確認できた\\[2em]
	2011年度の優勝クライアントを検証した結果，\\
	UCT探索は既に実装されていることがわかった\\[2em]

	\if0	
	選ばれる見込みの無い合法手を求め探索を行わないようにするProgressive PruningやUCB1アルゴリズムを改良したUCB1-Tunedなど
	\fi
	大貧民に適用できる可能性があるアルゴリズムが他にも存在するので，それらを実装することが今後の課題である
}
%ここまで
\end{document}














