% !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{ＡＩプログラム大会向けのコード作成}
\etitle{}
\jpauthor{並木 彰浩}
\eauthor{Akihiro Namki}
\course{谷聖一　研究室}
\year{24}
\abstract{%
AIのゲームの応用について理解を深める事を目的とし，以下の２つを行った．1)情報処理学会が主催するSamurAI Codingに参加．2)コペンハーゲンIT大学の准教授Julian Togeliusが主催するMario AI ChampionshipでMarioAIを作成した．1)のsamurAICodingでは，Agent間の距離を最短歩数で距離を定義した距離１とｘ座標の差とｙ座標の差の和で距離を定義した距離２に基づくプログラムを実装した．2)のMario AI Championshipでは，敵と障害物をジャンプするMarioAIを実装した．}

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

\begin{document}

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

\begin{multicols}{2}
\setcounter{page}{11}
%こうやって2段組にします．

\section{はじめに}
背景: AI(Artificial Intelligence)は，人間と同等の知能を実現する事を目標とし，人間と同様な作業をコンピューターで模倣させるシステム(\cite{a})などと定義されている．人間と同等の知能とは判断，理解，推理，計算，学習など挙げれば切りがない．知能という言葉を踏まえた上でAIについて考察すると，車を製造する過程で使用されているロボットアームなどの産業用ロボットや，アラーム機能，デジタルカメラなどは果たしてAIと呼べるのだろうか.自律性からの視点でみればこれらはAIではない．しかし，ロボットアームは巧みに腕を動かし車を製造し，アラーム機能は時間の計算を行い，カメラは画像処理を行い風景を写す．人間の一部を模倣していると言え，AIと表現しても差し支えないのではないだろうか．つまりAIの厳密な定義は主観的となり，個人だけの定義が存在する.著者の考える定義は，人間と同等の知能を実現する事を目標とし，人間と同様の判断を部分的にコンピューターで模倣させるシステムである．AIの最終目標の一つは人間と同等の知能を実装する事にある.理想としては，「鉄腕アトム」や「ドラえもん」が挙げられる．近い将来，一人に一台付き添いロボットを所有する時代がやってくるかもしれない．ロボットを開発するという点でAIの歴史の出発点を考慮すれば，1923年にK.Kapekが“R.U.R. (Rossum's Universal Robots)”がロンドンで上演，初めてロボットという言葉が用いられた(\cite{b})．また,1956年にダートマス会議が開催され，AIの先駆者であるマッカシー，ミンスキー，サイモン，ニューウェルなどが参加した(\cite{c})．AI研究は意外にも新しい技術であり，約半世紀の歴史しか有さない．しかし．現代では数学，人類学，哲学，遺伝子学などの様々な分野でAIは応用され，現代社会の技術開発に寄与している．例えば，HondaのASIMOは歩行し，走り，ジャンプし，挨拶を交わす(\cite{d})．\\
\ \ AI開発の一環としてゲーム分野でもAIは応用され研究が進められている．１９９７年にはコンピューターチェスであるディープ\ ブルーが世界チャンピヨンであるガリル\ カスパロフと対戦し，互角に戦っている(\cite{e})．もちろんチェスだけではなく，様々なゲームにAIは組み込まれている．それによって表現できる人間らしい動作は，ゲームの娯楽性を高めてくれる．かく言う私も日々その娯楽を楽しむ一員であり，更に情報学科の学生であることがゲームAIに強く興味を抱かせた．\\
\ \ そこで，AIについて理解を深める為にSamurAI Codingに参加とMarioAIに挑戦することにした．本演習では，２つのゲームの応用をする1)SamurAI Codingについては，六角形のセルで敷き詰められた盤上に配置されるAgent間の距離を異なる２つの定義(最短歩数で定義した距離１，ｘ座標の差とｙ座標の差の和で距離を定義した距離２)に基づくプログラムを実装した．２つのプログラムをコスト(ソースコードを重さで表す概念)と距離計算の効果で比較して優劣を判定した．2)MarioAIについては大会の概要と，現段階でのMarioの動作について記述する．第２節にSamurAI Codingの概要，第３節に犬の戦略，第４節に実装，第５節に結果と考察，第６節ではMario AI Championshipを述べる．
\section{SamurAI Coding}
\subsection{大会の概要}
SamurAI Codingは2011年度から開催されている世界の学生を対象にしたプログラミング大会である．グリー株式会社がイベントスポンサーをし，2011年度は早稲田大学鷲崎研究室が主催した.2012年度には情報処理学会が継承して主催した．
\subsection{ゲームの詳細}
\subsubsection{開始（初期設定）}
\parindent = 0pt
\begin{description}
 \item[プレイ人数]\mbox{}\\
 ４チーム
 \item[盤面]\mbox{}\\
 行列３９$\times$(４１or４１)の六角形のセルが敷き詰めらている(if 奇数列４０ else ４１)
 \item[門(Gate)]\mbox{}\\
 上下対称左右左右対称に五個づつランダムに配置(合計２０個)
 \item[Agent]\mbox{}\\
 各チームに三人の侍と犬が用意される．初期配置はチームに対して上下左右対称(以後,侍と犬と表記)
\end{description}
\begin{center}
\includegraphics[width=8cm]{samuraisyoki.eps}\\
\figurename{：初期配置}
\end{center}
\subsubsection{進行}
\parindent = 0pt
\begin{description}
 \item[ラウンド数]\mbox{}\\
 試合毎に回数変化(１０００〜２０００)
 \item[プログラムの読み込み]\mbox{}\\
 ラウンド毎にソースが読まれる
 \item[Agentの行動]\mbox{}\\
 ラウンド毎に全てのAgentは６方向に１マス移動，または待機が可能
\end{description}
\begin{center}
\includegraphics[width=8cm]{sinkou.eps}\\
\figurename{：ラウンド\ プログラムの読み込み\ Agentの行動 }
\end{center}
\begin{description}
 \item[侍の移動(役割)]\mbox{}\\
 足跡を残す
 \item[犬の移動(役割)]\mbox{}\\
 ６マス以内に侍を入れない(足跡は残らない)
\end{description}
\begin{center}
\includegraphics[width=8cm]{samuraifoot.eps}\\
\figurename{：侍の役割}
\end{center}
\begin{center}
\includegraphics[width=8cm]{samuraiinu.eps}\\
\figurename{：犬の役割}
\end{center}
Agentのフリーズ状態：行動不可(待機で解除)\\
\begin{itemize}
 \item 他のAgentとの衝突
 \item 壁に衝突
 \item 犬の脅威側から侍を捕縛
\end{itemize}
\begin{center}
\includegraphics[width=4cm,height=4cm]{samuraifreez.eps}\\
\figurename{：フリーズ状態}
\end{center}
\subsubsection{終了（勝利条件）}
\parindent = 0pt
\begin{description}
 \item[大陸横断]\mbox{}\\
 ステージの上辺下辺，または右辺左辺に足跡を繋げた場合に即座に勝利(赤チームが勝利)
 \begin{center}
\includegraphics[width=8cm]{samuraioudan.eps}\\
\figurename{：大陸横断}
\end{center}
 \item[大陸占領]\mbox{}\\
 ラウンド終了時，最も足跡で占領したチームが勝利(黄色チームが勝利)
 \begin{center}
\includegraphics[width=8cm]{samuraisenryou.eps}\\
\figurename{：大陸占領}
\end{center}
\end{description}
\subsection{特別ルール}
\parindent = 0pt
\begin{description}
 \item[cyzygy]\mbox{}\\
 斜線に４以上のAgentが並んだ場合，対応した位置交換が発生(if 奇数列：中心にいるAgentは変化無し)
 \item[cyzygy発生不能期間]\mbox{}\\
 最初の１０R or cyzygyが発生してから３R
 \begin{center}
\includegraphics[width=8cm]{samuraisyzygy.eps}\\
\figurename{：syzygy}
\end{center}
 \item[包囲]\mbox{}\\
 足跡がセルを囲んだ場合、全て占領
 \begin{center}
\includegraphics[width=8cm]{samuraihoui.eps}\\
\figurename{：包囲}
\end{center}
 \item[門(Gate)]\mbox{}\\
 対称の門にAgentがワープ可能
 \begin{center}
\includegraphics[width=8cm]{samuraigate.eps}\\
\figurename{：門(Gate)の役割}
\end{center}
\item[コスト制約]\mbox{}\\
全体で使えるコスト：２０００(Agent４人で２０００コスト共有)\\
実行されると１コストが加算される文：条件式（if）,繰り返し文（while），変数，配列，定数，演算子\\
例)\\
a = []...(3)\\
b = 0...(3)\\
wihle b != 3...(4)\\
 if b != 1...(4)\\
  a[b] = b...(5)\\
 endif
 b = b+1...(5)\\
endwhile\\
実行コスト\ (５５コスト)\\
\item[関数]\mbox{}\\
組み込み関数：情報を取得する為に既存で用意されている関数\\
独自関数：独自で定義する関数(中身のコストは２倍)
\end{description}
\section{犬の戦略}
大陸横断を狙うSamurai0から，一番近い敵のAgentに突撃させる．
\begin{center}
\includegraphics[width=8cm]{inusenryaku.eps}\\
\figurename{：犬の戦略}
\end{center}
\subsection{大陸横断を狙う理由}
\begin{description}
 \item[Gateの存在]\mbox{}\\ 
反対側にワープする門は大陸横断を達成するのに効果的
 \item[コスト制限]\mbox{}\\
 ２０００コストを４人で共有するとなると時間がかる長期戦になる大陸占領よりも，短期決戦である大陸横断を採用
\end{description}
\end{multicols}
\section{実装}
\subsection{実装環境}
ブラウザGoogle Chromeを使用しWeb上で動作を確認
\begin{center}
\includegraphics[width=8cm]{samuraigengo.eps}\\
\figurename{：ソースコードを読み込むWebページ}
\end{center}
\subsection{実装方法}
一番近い敵を探索するのに，二つの距離を定義\\
Targetの座標：(tx,ty)\\
Samurai0の座標：(sx,sy)\\
D(Distance) = 0\\
\fbox{距離１：最短歩数で定義}
\[
 K1=\begin{cases}
  K2(sy)& (|ty-sy|\%2=1)\\
  K5(tx,sx,ty,sy)& (otherwise)
 \end{cases}
\]
\[
 K2(sy)=\begin{cases}
  K3&(sy\%2=0)\\
  K4&(otherwise)
 \end{cases}
\]
\[
 K3(tx,sx,ty,sy)=\begin{cases}
  K5(tx,sx,ty,sy-1),D+1&(tx<sx\&\&ty<sy)\\
  K5(tx,sx,ty,sy+1),D+1&(tx<sx\&\&ty>sy)\\
  K5(tx,sx+1,ty,sy-1),D+1&(tx>sx\&\&ty<sy)\\
  K5(tx,sx+1,ty,sy+1),D+1&(tx>tx\&\&ty>sy)\\
 \end{cases}
\]
\[
 K4(tx,sx,ty,sy)=\begin{cases}
  K5(tx,sx-1,ty,sy-1),D+1&(tx<sx\&\&ty<sy)\\
  K5(tx,sx-1,ty,sy+1),D+1&(tx<sx\&\&ty>sy)\\
  K5(tx,sx,ty,sy-1),D+1&(tx>sx\&\&ty<sy)\\
  K5(tx,sx,ty,sy+1),D+1&(tx>tx\&\&ty>sy)\\
 \end{cases}
\]
\[
 K5(tx,sx,ty,sy)=\begin{cases}
  K7(tx,sx,ty,sy)&(tx=ty||sx=sy)\\
  K6(tx,sx,ty,sy)&(otherwise)
 \end{cases}
\]
\[
 K6(tx,sx,ty,sy)=\begin{cases}
  K5(tx,sx-1,ty,sy-2),D+2&(tx<sx\&\&ty<sy)\\
  K5(tx,sx-1,ty,sy+2),D+2&(tx<sx\&\&ty>sy)\\
  K5(tx,sx+1,ty,sy-2),D+2&(tx>sx\&\&ty<sy)\\
  K5(tx,sx+1,ty,sy+2),D+2&(tx>sx\&\&ty>sy)\\
 \end{cases}
\]
\[
 K7(tx,sx,ty,sy)=\begin{cases}
  K11(D)&(tx=ty\&\&sx=sy)\\
  K8(tx,sx,ty,sy)&(otherwise)
 \end{cases}
\]
\[
 K8(tx,sx,ty,sy)=\begin{cases}
  K9(tx,sx,ty,sy)&(sy\%2=1)\\
  K10(tx,sx,ty,sy)&(otherwise)
 \end{cases}
\]
\[
 K9(tx,sx,ty,sy)=\begin{cases}
  K7(tx,sx-1,ty,sy),D+1&(tx<sx\&\&ty=sy)\\
  K7(tx,sx,ty,sy-1),D+1&(tx>sx\&\&ty<sy)\\
  K7(tx,sx+1,ty,sy),D+1&(tx>sx\&\&ty=sy)\\
  K7(tx,sx,ty,sy+1),D+1&(tx>sx\&\&ty>sy)\\
 \end{cases}
\]
\[
 K10(tx,sx,ty,sy)=\begin{cases}
  K7(tx,sx-1,ty,sy),D+1&(tx<sx\&\&ty=sy)\\
  K7(tx,sx,ty,sy-1),D+1&(tx<sx\&\&ty<sy)\\
  K7(tx,sx+1,ty,sy),D+1&(tx>sx\&\&ty=sy)\\
  K7(tx,sx,ty,sy+1),D+1&(tx<sx\&\&ty>sy)\\
 \end{cases}
\]
\[
 K11(D)=\begin{cases}
  D
 \end{cases}
\]
メリット：正確に距離を計算可能\\
デメリット：コストが膨大
\begin{multicols}{2}
\fbox{距離２：ｘ座標の差とｙ座標の差の和で定義}
\end{multicols}
D=｜(tx-sx)｜+｜(ty-sy)｜\\
メリット：コストが安価\\
デメリット：最短ステップ数との誤差
\begin{multicols}{2}
\subsection{検証}
\subsubsection{距離１で探索と距離２で探索とのコスト差}
\begin{description}
 \item[１Agent分のコスト差]\mbox{}\\
 距離２よりも距離１が３０コスト多い
 \item[全体のAgent分のコスト差]\mbox{}\\
 (１６)− 自軍(４)=１２\\
 ３０$\times$１２= ３６０\\
\end{description}
\subsubsection{犬の追跡プログラムのコストを足した場合の平均}
\begin{description}
 \item[犬の追跡プログラムコスト]\mbox{}\\ 
 １００コスト
 \item[距離１での探索の場合]\mbox{}\\
 １００＋７６０＝８６０コスト
  \item[距離２で探索の場合]\mbox{}\\
１００＋４００＝５００コスト
\end{description}
\subsubsection{採用した距離}
距離１を採用
\section{結果と考察}
\begin{description}
 \item[考察]\mbox{}\\ 
 追跡は予想通りに動作したと思われるが，距離２でもコストがかかりすぎてしまった．（４００〜５００コスト）
 \item[結果]\mbox{}\\
 ２０チーム中１７位
  \item[今後の課題]\mbox{}\\
コスト削減を目指して、他にコストを回せるようにする
\end{description}
\section{marioAI}
\subsection{大会の概要}
Mario AI ChampionshipはペンハーゲンIT大学の准教授Julian Togeliusが主催する大会である．公式ページからダウンロードが可能であるMario AI Benchmark source packageでゲームを動かし，Java言語でMarioをプログラムから操作させる，大会は４つの競技で設けられ，参加者を得点で競わせる．
\begin{center}
\includegraphics[width=8cm]{marioship.eps}\\
\figurename{：Mario\ AI\ Championship}
\end{center}
\subsection{競技}
\begin{description}
 \item[GamePlayTrack(推論型)]\mbox{}\\ 
 MarioAIを一度動かして,得点を競う．
 \item[LearningTrack(学習型)]]\mbox{}\\
 MarioAIを何度か動かして学習させ，規定回数内で得点を競う．
 \item[LevelGenerationTrack(ステージ生成)]\mbox{}\\
 ステージ生成に関して得点を競う．
  \item[TuringTestTrack(人間味あるAI)]]\mbox{}\\
  どれだけ人間の動作に近いMarioAIかを競う．
\end{description}
\subsection{挑戦した推論型のルール}
\begin{itemize}
 \item 敵を倒した数
 \item コインを取得した数
 \item ゴールまでの時間
\end{itemize}
以上の３つでスコアを算出
\subsection{現在の実装したMarioAI}
壁と敵をジャンプで避けるプログラムを作成
\begin{center}
\includegraphics[width=8cm]{mariojump.eps}\\
\figurename{：MarioJUMP!}
\end{center}
\subsection{問題点}
\begin{itemize}
 \item 穴を検知する事ができない
 \item 上から降ってくる敵，または着地硬直後の敵と接触
\end{itemize}
\subsection{今後の課題}
\begin{itemize}
 \item 穴を越える
 \item 敵を避けるから，倒すへ
 \item 目の前ではなく，その先を見る
 \item コインを取得
\end{itemize}

\end{multicols}%2段落の文章の終わり

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

\bibitem{a}http://e-words.jp/w/AI.htm，(参照\ 2012-01-27)
\bibitem{b}http://www.ai-gakkai.or.jp/whatsai/AIhistory.html，(参照\ 2012-01-27)
\bibitem{c}著者 荒屋真二 タイトル 人工知能概論 ，(参照\ 2012-02-11)
\bibitem{d}http://www.honda.co.jp/ASIMO，(参照\ 2012-02-03)
\bibitem{e}http://www.ne.jp/asahi/box/kuro/report/deepblue.htm，(参照\ 2012-02-21)

\end{thebibliography}


\end{document}