\documentclass[a4paper]{jarticle}
\usepackage{tani_resume}
\usepackage{epstopdf}
\usepackage{graphicx}
\usepackage{ascmac}
\alignbeforeskip -5mm
\alignafterskip -5mm
\eqnarraybeforeskip -5mm
\eqnarrayafterskip -5mm

\jptitle{ゲームAIプログラミング大会用コード作成}
\etitle{}
\jpauthor{新井 悠太}
\eauthor{Yuta Arai}
\course{谷聖一研究室}
\year{25}

\abstract{
人工知能(Artificial Intelligence, AI)やそこから派生した技術は，幅広い分野に応用されている．そこで，若い世代の人材育成を目的としたAIプログラミングコンテストが開催されている.そのようなコンテストの１つである，SamurAI Codingのコード作成し，またマリオAIのコードを試作した.
}
\compheading
\begin{document}
\maketitle
\begin{multicols}{2}
\setcounter{page}{25}

\section{はじめに}

知能とは実際の目標を達成する能力の一部であり，判断，理解，推理，計算，学習など様々なものがある．人工知能(Artificial Intelligence, AI)とは簡単に言うと，コンピューターに知的な活動をさせることを目的とする研究と技術のことである．しかし，この知的な活動とは何か，知能があるかとはどのようなことか自体に大きな問題あり，立場により人工知能の定義も異なっている．

人間の知的な活動をモデル化すると科学的側面と工学的側面があると考えられる(\cite{ai-basic})．
\begin{description}
\item[科学的側面] 人間がどのように問題を解決しているのか，人間のやり方に沿ったモデルを構築し，コンピュータ・シミュレーション等を行うことによって知識の原理，人間の思考過程を解明しようという側面．
\item[工学的側面] 人間がどのようにやっているかということには拘らず，とにかくその「知識を必要とすると思われる問題」を解明できる知的情報処理システムを実現しようという側面．
\end{description}

注意として，この２つの側面は明確には区別されていない．現在では後者の研究がより広く進んでおり，人工知能から派生して独立した分野になった，自然言語処理，パターン認識，エージェント学習，データマイニングなどがある．ゲームAIについても工学的側面の知的情報処理を中心とした研究となっている．

報告者は，ゲームAIについて理解を深めることを目的に SamurAI Coding というゲームAIプログラミングコンテストに挑戦した. SamurAI Coding(\cite{samurai})では主にエージェントの行き先を決定する priorityMove 関数を作成し，それを中心にプログラムを作成した.稿では SamurAI Coding の予選，決勝の時の戦略，またそれがどのように有効であったかと，敵チームの戦略，その対応について述べる.又マリオAI(\cite{marioai})についても試作した．

\section{SamurAI Coding 2013について}
\subsection{概要}
SamurAI Codingは2011年度に早稲田大学鷲崎研究室が開催し，2012年度からは情報処理学会が継承して開催している.大会のウェブによると若い世代から将来第一線の研究者や開発者になりうる，また世界市場を舞台に活躍できる人材を育てることを目的とした大規模な国際的なコンテストである.また今年は東京大学大学院情報理工学系研究科が決勝で共催し，GREE株式会社がイベントスポンサー，その他ゴールドスポンサー，協賛，後援の方々が支援している(\cite{samurai})．

ゲームシステムは簡単に説明すると，六角形のセルが敷き詰められた盤面をそれぞれ侍エージェントと犬エージェントが１ターンに１回行動し，領土を広げてポイントを競うゲームである．昨年とゲームシステムはあまり変わらないが，プログラム記述方法が変更されたため，昨年度のプログラムソースをそのまま引き継げない．昨年度については，"samurai"言語というオリジナル言語でWeb上で動作していた．今年度は，"Gunbai Script 2013"言語というオリジナル言語で実行スクリプトによりc++に変換後，g++で実行オブジェクトを生成し，そのオブジェクトを実行しログが出力する．そのログをJavaで作成されたビジュアライザでゲーム画面表示できる．
\subsection{ルール ( Rule )}
\subsubsection{ゲーム進行}
\begin{description}
	\item[チーム数]\mbox{}\\予選 : 国内 : 24チーム ， 海外 : 4チーム\\決勝 : 国内 : 10チーム ， 海外 : 2チーム
	\item[ラウンド数]\mbox{}\\各チーム20ラウンド
	\item[１ラウンドのターン数]\mbox{}\\最大300ターン
	\item[エージェントの行動]\mbox{}\\ターン毎に全てのエージェントが０〜５までの行き先に移動\\また行動しないが選択可能
\end{description}
\subsubsection{ラウンド開始 ( 初期状態 )}
\begin{description}
	\item[１ラウンドのプレイ人数]\mbox{}\\赤，緑，青，黄の４チーム
	\item[１チームのエージェント数]\mbox{}\\侍エージェント : 3人\\犬エージェント : 1匹
	\item[盤面 ( Board ) ]\mbox{}\\正六角形のタイルが敷き詰められる．\\行 : ２５〜３５行から毎ラウンド設定\\列 : ２５〜３５列から毎ラウンド設定
	\item[門( Gate )]\mbox{}\\上下左右対称に２個づつランダムにゲートが配置
	\item[エージェントの初期配置]\mbox{}\\エージェントに不平等が生じないように，上下左右対称にランダムに配置
\end{description}
\begin{center}
	\includegraphics[bb=0 0 862 697,width=7cm]{img/2_1.png}\\
	\figurename{2.2.1　スクリーンショット (初期状態)}
\end{center}
\begin{center}
	\includegraphics[bb=0 0 295 298,width=7cm]{img/2_2.png}\\
	\figurename{　スクリーンショット (進行方向)}
\end{center}
\begin{description}
	\item[侍エージェントの移動(役割)]\mbox{}\\足跡を増やす．（既に足跡がある場合は上書き）
\end{description}
\begin{center}
	\includegraphics[bb=0 0 298 227,width=7cm]{img/2_2_1.png}\\
	\figurename{2.2.2(1)　スクリーンショット (侍エージェントの移動)}
\end{center}
\begin{description}
	\item[犬エージェントの移動(役割)]\mbox{}\\他のエージェントの動きを妨害する．\\下の図2.2.2(2)は黄色の矢印は移動可能だが，黒い点線の矢印は移動出来ない．
\end{description}
\begin{center}
	\includegraphics[bb=0 0 222 142,width=7cm]{img/2_2_2.png}\\
	\figurename{2.2.2(2)　スクリーンショット (犬エージェントの役割)}
\end{center}
\begin{description}
	\item[フリーズ状態]\mbox{}\\エージェントが特定の位置に動こうとしたときに発生． 発生した後のエージェントは１ターン動けなくなる．フリーズしたあとに -1 をリターンすると再度行動が可能となる．
\end{description}
\begin{itembox}[l]{}
	\begin{itemize}
		\item 他のAgentとの衝突\\
			他のエージェントがいた位置に行こうとするとフリーズ\\
			他のエージェントと移動先が同じ場合お互いにフリーズ
		\item 壁に衝突
		\item 敵の犬エージェントの周囲１マスに移動しようとするとフリーズ．ただし，侍エージェント，犬エージェントの順番で動く
	\end{itemize}
\end{itembox}

\begin{description}
	\item[大直列交換]\mbox{}\\1匹以上の犬エージェントと3人以上の侍エージェントが一直線上に並んだとき大直列交換が行われる．一番外側同士，内側同士の位置がスワップされる．
\end{description}
\begin{center}
	\includegraphics[bb=0 0 433 630,width=8cm]{img/2_2_3.png}\\
	\figurename{2.2.2(3)　スクリーンショット (大直列交換前)}
\end{center}
\begin{center}
	\includegraphics[bb=0 0 399 622,width=6cm]{img/2_2_4.png}\\
	\figurename{2.2.2(4)　スクリーンショット (大直列交換後)}
\end{center}
\begin{description}
	\item[包囲]\mbox{}\\領土を自分の色で囲った場合，囲った陣地がすべて自分の色になる．またその中にいるエージェントはポイントを増やせない．
\end{description}
\begin{center}
	\includegraphics[bb=0 0 210 369,width=6cm]{img/2_2_5.png}\\
	\figurename{2.2.2(4)　スクリーンショット (包囲)}
\end{center}
\subsubsection{ラウンド終了}
\begin{itemize}
	\item 大陸横断\\盤面の上辺下辺，または右辺左辺が自分のチームの色で繋がることを大陸横断という．大陸横断をしてさらに他のチームよりも占領地が多い場合，即座に試合が終了する．他のチームは占領地が多い順番に順位が決定する．
	\item 大陸占領\\ゲーム終了時に，占領地が多い順に順位が決定する．
\end{itemize}


\subsubsection{コスト}
プログラム処理にはコストが設けられている．条件式，繰り返し文，変数，配列，定数，演算子を使うごとに１づつコストがたまり，関数を作ると使うたびに中身の２倍コストがかかってしまう．合計１００万コストが上限になっており，それを超えた場合プログラムは動かない．

\subsubsection{前年度と今年度のルールの違い}
盤面の大きさが固定からランダムに．エージェントの初期位置がランダムに．犬エージェントは侍エージェントの進行の妨害のみ．前年度のルール捕縛（隣接している相手をずっと動けない状態にする）はできない．前年度は大陸横断したら即座に試合終了だったが，今年度は大陸横断してポイントが一番高い場合即座に試合終了に変更された．

\section{SamurAI Coding : 戦略}
\subsection{侍エージェントの動き方の方針}
昨年のルールから侍エージェントの動きの方針は基本的には２通りある．１つ目は，序盤で一気に大陸横断を狙う方法．２つ目は，相手の邪魔をしつつ自分の領土を広げ大陸占領を狙う方法である．去年は大陸横断をしたチームが即座に勝利できたため、大陸横断優先のチームが多かった．今年は大陸横断をしたチームのポイントが一位にならなければいけないため，今年は大陸占領を狙う方針を採用した．これは大陸占領をすることで大陸横断優先のチームよりもポイントが多く稼げるため，ラウンド毎の順位が高くなりやすいからである．
\subsection{フリーズ状態をなくす関数を作成}
去年の先輩のプログラムでは侍エージェントと侍エージェントが重なるときにフリーズ状態で動かない状態になってしまうことがあった．
\begin{center}
	\includegraphics[bb=0 0 995 537,width=8cm]{img/3_1.png}\\
	\figurename{3.2　スクリーンショット (昨年度侍エージェントの反省点)}
\end{center}
今年の目標は，まずフリーズ状態が起こらないように行き先を決定するpriorityMove関数を作成した．まずフリーズ状態について説明する．フリーズ状態になるときはルールの所で説明した通り壁との衝突，他のエージェントとの衝突，敵チームの犬エージェントの周囲に移動しようとしたときにフリーズ状態が発生する．フリーズ状態になると次のターンは必ず動けなくなりそのエージェントの配列に-1を返さない限り動くことはできない．そのため，この状態になったときに１ターン無駄になってしまう．それを避けるためにpriorityMove関数が必要となる．priorityMove関数はエージェントの番号と優先的に移動したい行き先0から5までを引数に入れると，ほぼ確実に移動できる位置を返す関数である．

以下，priorityMove関数のアルゴリズムである．\\
\begin{itembox}[l]{priorityMove関数 アルゴリズム}
	\begin{enumerate}
		\item 行き先のポイントを付ける ret[6] という配列を用意する．
		\item 初期化 ret[6]の全ての要素に1を入れる．
		\item 行き先が壁ならば ret[i] = 0
		\item 壁でない所を見て自分の色ならば ret[i] = 3
		\item 行き先に他のエージェントが存在するならば ret[i] = 0
		\item 行き先のタイルが他のエージェントと隣接している場合 ret[i] = ret[i] * 2
		\item 行き先のタイルが他のチームの犬エージェントと隣接している場合 ret[i] = 0
		\item ret配列の要素をk = 1..7 まで探索し，最小の値の所を優先的に返す．
	\end{enumerate}
\end{itembox}

\subsection{侍エージェントの動き}
六角形を描き，包囲して大量にポイントを獲得する．包囲の成功は他チームのエージェントの動きによって左右されやすいが，成功した場合多くの領土を占領でき，上位になりやすくなる．
\begin{center}
	\includegraphics[bb=0 0 357 258,width=7cm]{img/3_2.png}\\
	\figurename{3.3(1)　スクリーンショット (六角形を描く)}
\end{center}
\begin{center}
	\includegraphics[bb=0 0 355 254,width=7cm]{img/3_3.png}\\
	\figurename{3.3(2)　スクリーンショット (六角形を描く)}
\end{center}
一人の侍エージェントは端についたら周りを動き大陸横断を狙う．
\begin{center}
	\includegraphics[bb=0 0 319 257,width=7cm]{img/3_4.png}\\
	\figurename{3.3(3)　スクリーンショット (壁の周りを動く)}
\end{center}
\subsection{犬エージェントの動き}
最短距離にいる敵エージェントを追跡する．
\begin{center}
	\includegraphics[bb=0 0 252 199,width=6cm]{img/3_5.png}\\
	\figurename{3.3(4)　スクリーンショット (犬エージェントの動き)}
\end{center}

\section{SamurAI Coding : 予選の結果，考察}
２４チーム中７位になり予選突破した．予選を通過出来るのは国内上位１０チーム，海外上位２チームである．フリーズ状態にならない関数，六角形を描くという作戦はある程度有用であった．４位以下のチームでは一番ポイントが高いため，大陸横断はあまり出来なかったが平均順位が高かったと推測出来る．
\begin{center}
	\includegraphics[bb=0 0 441 488,width=6cm]{img/4_1_1.png}\\
	\figurename{4.1(1)　スクリーンショット (予選の結果)}
\end{center}
\begin{center}
	\includegraphics[bb=0 0 962 630,width=7cm]{img/4_1_2.png}\\
	\figurename{4.1(2)　スクリーンショット (予選のグラフ)}
\end{center}
\subsection{決勝へのプログラム改良}
予選で提出したプログラムではある条件になるとフリーズが発生してポイントを稼げなかった．それを直しさらにフリーズ状態にならないプログラムにする．

予選のプログラムでは行き先がゲートの場合，ゲートの向こうにエージェントが存在した場合フリーズ状態が発生していた．ゲートの向こう側にエージェントが存在するかどうかを識別するプログラムを追加し，エージェントがいた場合は進行を変えるようにした．

\begin{center}
	\includegraphics[bb=0 0 371 698,width=6cm]{img/4_1.png}\\
	\figurename{4.1(1)　スクリーンショット (ゲートの先を見る)}
\end{center}

ある条件で味方の侍エージェントが同じ座標に進もうとするためフリーズ状態が発生していた．これを防ぐため，一度フリーズ状態になった行き先を再度選択しないようにした．

\begin{center}
	\includegraphics[bb=0 0 203 165,width=5cm]{img/4_2.png}\\
	\figurename{4.1(2)　スクリーンショット (同進行方向の変更)}
\end{center}

\section{SamurAI Coding : 決勝の結果，考察}
決勝の結果は１０位中６位となり一応世界６位という結果を収めた．他のチームとの対戦を見るのは決勝だけなので，このとき初めて様々な戦略を見る事ができた．
\begin{center}
	\includegraphics[bb=0 0 549 441,width=7cm]{img/5_1.png}\\
	\figurename{5(1)　スクリーンショット (決勝の結果)}
\end{center}
\begin{center}
	\includegraphics[bb=0 0 916 612,width=7cm]{img/5_2.png}\\
	\figurename{5(2)　スクリーンショット (決勝のグラフ)}
\end{center}
\subsection{3位のチームのプログラム解析}
３位のチームのプログラムはバグで動かないことが多かったため，それが無ければ１位と互角に渡り合えるプログラムになったであると対戦を見て思った．主に近い距離にある自分の色に評価（ポイント）を付けてそこを繋げて包囲を狙う．評価する所が無い場合はランダムな動きをする．
\subsection{2位のチームのプログラム解析}
２位のチームはまず小さな円を描きポイントを稼いで大陸横断を妨害する．そのあと，3人の侍エージェントが画面より右側を限定してポイントを稼ぎ大陸横断を目指す．画面右側にエージェントがあまり存在しない場合，大量に包囲してポイントを稼ぎ，大陸横断をしていた．
\subsection{1位のチームのプログラム解析}
自分のポイントがトップのときに最短で大陸横断を狙う．渦巻き型でポイントを増やし敵エージェントが妨害しようとしたときに包囲してポイントを増やす．そのあと大陸横断を狙う．１位のチームはラウンドが進み強いチームと対戦するときには他のチームに邪魔されてポイントを稼げていなかったが，大陸横断をするスピードは一番最速だった．
\subsection{今回の反省点}
自分のチームのポイントが一番多くなったら大陸横断を目指すプログラムに変更すべきであった．犬エージェントはもう少し敵エージェントを妨害するプログラムにするべきだった．評価関数を使ったプログラムを作成したかった．

\section{終わりに}
稿ではSamurAI Codingにおけるルールから戦略などを細かく説明してきたが，より強いAIを作成するにはヒューリスティック関数（評価関数）を使えばよりAIとしての知識が深まるのではないだろうか．また予選を通過すると１年間情報処理学会の無料で会員になれること，またエクスカーションが開かれグリー株式会社や株式会社 Preferred Infrastructureなどに企業訪問が出来る．本年はMarioAIの大会は開催されたか分からないが，プログラムを試作した．ゲームAIに興味がある人は是非やっておくべきだ．
\end{multicols}
%%%%% 参考文献 %%%%%
\begin{thebibliography}{5}

\bibitem{ai-basic} 著者 : 太原 育夫 , タイトル : 新人工知能の基礎知識
\bibitem{samurai} SamurAI Coding 2013. http://samuraicoding.info/, (参照 2014-02-10)
\bibitem{marioai} marioAI google code. https://code.google.com/p/marioai/, (参照 2014-02-10)
\bibitem{ipsj} 情報処理学会 http://www.ipsj.or.jp/index.html, (参照 2014-02-10)
\bibitem{ai-gakkai} 人工知能学会 http://www.ai-gakkai.or.jp/ (参照 2014-02-10)

\end{thebibliography}
\end{document}
