颁辞诲别惫蝉5.0勉强会
- 1. CODEVS 勉強会 CODEVS 入門編 ? はじめてのAI ? チームラボ 林 輝大
- 2. 自己绍介
- 3. 自己绍介 氏名：林 輝大 出身：長野県（長野高専専攻科卒） 職歴：チームラボ新卒4年目 役職：エンジニア レコメンデーションチーム（パッケージ導入 / 分析） CODEVS / CodeRunner のチームラボ内プロジェクトマネージメント
- 4. はじめに
- 5. この勉強会を楽しむための諸注意 初心者向けのAI作成指南コンテンツ 既に経験のある方は裏でAI作ったり、バトルしまくってもらって構いません 演説者（林）は、AI作成初心者であることを理解する この勉強会を行うために勉強しました AI作成の心得がない立場で、詳しい方々にアドバイスを貰った内容をまとめてます 下記のコンパイルおよび実行環境があること Java または C / C++（無くても勉強会参加には問題ありません！）
- 6. 本日の流れ
- 8. 颁翱顿贰痴厂とは？
- 9. 颁翱顿贰痴厂とは？ ゲームAIの強さを競う プログラミングコンテスト リクルート様と共催 登録者数1,000人 年1回開催の長期間コンテスト 予選：1ヶ月 決勝：予選終了１週間後、 オンサイトで1日開催 コンテストの題材はゲーム！ CODEVS 3.0 爆弾ゲーム CODEVS 4.0 戦略ゲーム
- 10. 颁翱顿贰痴厂とは？
- 11. 颁翱顿贰痴厂に参加してみよう！
- 12. その前に… 現在コンテストは開催しておりません 次のコンテスト（CODEVS 5.0）は来年頭を予定しています 過去のコンテストのゲームで遊んだり、対戦は出来ます CODEVS 3.0、CODEVS 4.0のみ CODEVS、CODEVS 2.0 のゲームの復刻は現在検討中 今回の勉強会はCODEVS 3.0で説明しやすいから ルールが理解しやすいから（ボンバーマンと聞いてルールが想像できますか？）
- 17. 善は急げ 早速サンプルコードを落としてみましょう！ 公式サイトにアクセス！（https://codevs.jp/） ログイン > アーカイブ > CODE VS 4.0 開催ゲーム ここ！ 一緒にやってみましょう ここ！
- 19. サンプルコードを動かしてみよう！ $ javac SampleAI.java $ g++ sampleAI.cpp -o sampleAI Javaサンプルコードのコンパイル C++サンプルコードのコンパイル 一緒にやってみましょう
- 23. 休憩 …
- 25. 础滨作成指南（基础知识编）
- 29. 基礎知識 ゲーム木探索 盤面の状態を評価関数で数値化し、よりより状態になる手をゲーム木から探索すること 探索方法はゲームの内容に左右されない 手法は様々で、得意不得意とする分野がある mini-max法 α-β法 モンテカルロ法 ビームサーチ etc ... 3 7 5 2 6 9 1 4 8 3 2 1 3
- 32. ゲーム木とは… ゲーム木（ゲームき、英: game tree）は、組合せゲーム理論において、ゲームの 盤面を有向グラフのノードで、手をエッジで表したものである。完全ゲーム木と は、ゲームの最初から指せる全ての手を含んだゲーム木である。 ―― Wikipedia より
- 33. ゲーム木とは… ゲームの状態をツリー状に表現したもの 節点（ノード）はゲームの状態を表している 枝の数はプレイヤーが取れる行動だけ存在する CODEVS3.0だと… ノードはゲーム盤の状況となる 次のゲーム盤の状態は（4方向+動かない） ×（爆弾置く or 置かない） ^（キャラクター数：2） = (5 × 2) ^ 2 = 100通りある
- 40. ゲーム木探索（尘颈苍颈-尘补虫法） 3 7 5 2 6 9 1 4 8 3 2 1 自分の手番 自分の手番 相手の手番 他の枝も探索する 他の枝も探索する
- 41. ゲーム木探索（尘颈苍颈-尘补虫法） 3 7 5 2 6 9 1 4 8 3 2 1 3 自分の手番 自分の手番 相手の手番 分岐先の最大値を取る （自分にとって良い手）
- 43. ゲーム木探索（α-β法） アルファ?ベータ法（— ほう、alpha-beta pruning）は完全情報ゲームにおける 探索アルゴリズムの1つである。基本的にミニマックス法と同じであり、同じ計 算結果が得られるが、ゲーム木において、計算しなくても同じ計算結果になる部 分を枝刈りしている。 ―― Wikipedia より
- 44. ゲーム木探索（α-β法） 3 7 5 2 6 9 1 4 8 自分の手番 自分の手番 相手の手番 mini-max法で紹介した ゲーム木と同じ
- 45. ゲーム木探索（α-β法） 3 7 5 2 6 9 1 4 8 自分の手番 自分の手番 相手の手番 ここまでは同じように 探索する
- 46. ゲーム木探索（α-β法） 3 7 5 2 6 9 1 4 8 3 自分の手番 自分の手番 相手の手番 最小値をいれる
- 47. ゲーム木探索（α-β法） 3 7 5 2 6 9 1 4 8 3 自分の手番 自分の手番 相手の手番 ここを探索
- 48. ゲーム木探索（α-β法） 3 7 5 2 6 9 1 4 8 3 自分の手番 自分の手番 相手の手番 比較すると探索した結果の方が 評価が低い ? 自分の手番では採用されない ? これ以上探索しなくてよい！
- 49. ゲーム木探索（α-β法） 3 7 5 2 6 9 1 4 8 3 2 自分の手番 自分の手番 相手の手番 これを入れる ここは探索しない
- 50. ゲーム木探索（α-β法） 3 7 5 2 6 9 1 4 8 3 2 自分の手番 自分の手番 相手の手番相手の手番中の最大評価と比較 小さい！
- 51. ゲーム木探索（α-β法） 3 7 5 2 6 9 1 4 8 3 2 1 3 自分の手番 自分の手番 相手の手番 あとは同じ
- 52. ゲーム木探索（α-β法） 3 7 5 2 6 9 1 4 8 3 2 1 3 自分の手番 自分の手番 相手の手番 4回分探索しなくて済んだ！ でも結果はmini-max法と同じ
- 54. ゲーム木探索（モンテカルロ法） モンテカルロ法 (モンテカルロほう、Monte Carlo method, MC) とはシミュレーシ ョンや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き 回る様子を探るためにスタニスワフ?ウラムが考案しジョン?フォン?ノイマン により命名された手法。カジノで有名な国家モナコ公国の4つの地区（カルテ ィ）の1つであるモンテカルロから名付けられた。ランダム法とも呼ばれる。 ―― Wikipedia より
- 57. ゲーム木探索（モンテカルロ法） 良い状態である確率 3 / 9 = 0.333... 良い状態である確率 4 / 9 = 0.444... 良い状態である確率 6 / 9 = 0.666... この手が良さそう！
- 62. CODEVS 3.0のサンプルコードを見返す サンプルコードのアルゴリズムは下記の通り 全く攻撃してこない敵に、近づき、倒すことを目指し、以下のアルゴリズムで行動する。 0. 簡単のため、自キャラ2体を同じマスに重ねて、以後同じ行動をさせる。 1. 移動できるマスのうち、敵に最も近いマスに移動する。 2. (1)で移動したマスに着いたら、魔法陣を設置する。 3. 魔法の発動に巻き込まれない場所まで移動する。 4. (1)に戻る。 シミュレーターを使用していないルールベースのAI つまり相手の行動を予測したりできない ゲーム木探索もできない 完璧なルールを作りあげることはむずかしい
- 63. ルールベースのAIは弱いのか？ ルールベースのAIだから弱いわけではない ルールベースじゃないとまともに動かないゲームもある CODEVS 3.0 ではゲーム木探索が強いだけ CODEVS 4.0はルールベースのAIが多い 次の盤面の状態が多く、ゲーム木を簡単には探索できないため ユニット毎の目的がはっきりしているため、ルールに落としやすい （生産ユニットは資源集め、戦闘ユニットは城攻め） 戦略がAIの強さを左右する 【CODEVS 4.0 ルール】 ● 資源を集めて、施設を立てて、戦士を生産して、相手の城を攻め落とそう ● ユニットは全部で4種類（生産ユニット1種類、戦闘ユニット3種類） ● 建物は3種類（村、拠点、城） ● ユニットがとれる行動は移動 ● 建物が取れる行動はユニットの生産
- 64. AI作成ポイント 盤面の状態がどれだけあるかを把握し、AI作成の指針を決める 状態が極めて多い → ルールベースなAI 状態がある程度限られる → ゲーム木探索を用いたAI ゲーム木探索を用いる場合 計算量を減らす工夫をする（既存の手法があるので探して使う） ゲームの性質によって探索方法を変える 対戦相手が居ない場合 → ビームサーチ、焼きなましなど 対戦相手が居る場合 → mini-max法、α-β法、モンテカルロ法など
- 65. 础滨作成指南（実践编）
- 67. 诸事情で割爱…
- 68. 最后に动画を见かえしてみましょう
Editor's Notes
- 途中で文字が小さい所は声に出して説明する
- 煽り过ぎかなぁ…
- 知识を得た上で动画を见直して见ましょう