立体四目で学ぶゲームAI

立体四目と呼ばれるゲームにおいてAIを構築し、ゲームAIの仕組みを学びます

Transcript

1. 立体4目で学ぶ ゲームAI 辻野 貴大
2. 自己紹介 辻野 貴大 Takahiro Tsujino 東京大学工学部精密工学科(リンク) に現在在学中 北海道出身、好きな食べ物は ジンギスカン 日食なつこさんに最近ハマっている
3. 目次 ・立体四目とは？ ・開発について ・AIのアルゴリズム ・結果
4. 立体四目並べとは •概要: 平面で行う「五目並べ」を、四目の立体に した対戦型のゲーム •ルール: 交互に石を置いていき, 自分の色の石をた て、横、斜めに四つ並べたら勝利 •特徴: 立体的に視点を広がるため, 空間把握能力が 必要とされる. 戦略の立て方もかなり大事 平和工業(Heiwa Kougyou) 立体4目並べ 本体サイ ズ:10×10×8.5 : ビューティー
5. ゲームの分類 完全情報ゲーム 選択においてゲームの情報が全て 明らかになっている 不完全情報ゲーム 選択においてゲームの情報が全て 明らかになっていない 情報性の違い 利益性の違い ゼロサムゲーム 自分の利益が相手の不利益に直結 非ゼロサムゲーム 自分の利益が相手の不利益と 関係ない(協力可能) 確定 不確定(運ゲー) 確定 不確定 確定 不確定 確定 不確定 オセロ 立体四目 麻雀 立体四目は 「二人零和有限確定完全情報ゲーム」 ポーカー 人狼 •特徴: すごろく バックギャモン 遊戯王 交渉ゲーム 人生(？！) ? ? ・相手の最善手を前提としたアルゴリズムを 採用可能 ・ゲーム木が構築可能
6. 目次 ・立体四目とは？ ・開発について ・AIのアルゴリズム ・結果
7. 技術仕様 ①ユーザー ②ゲームサーバ ③AIサーバ •仕様 ・ゲームの状態(盤面、 勝敗)を管理 ・盤面から勝敗を判定 •仕様 ・ゲームの状態を描画 ・石を置く場所を指定する •仕様 ・盤面から最適な石 の置き場所を決定 以下３つから構成される
8. ゲームの流れ ①ユーザー ②ゲームサーバ ③AIサーバ 2. おいた場所を送信 4. 盤面情報を送信 1. UI画面にて置く場所を決定 3,7 . 盤面情報を更新、 勝敗がついているか判定 5. 送られてきた盤面情報を 元に最適解を算出 6. おいた場所を送信 8. 盤面情報をもとに画面を更新 Websocket API
9. ユーザー画面の構築 カメラの移動ボタン 選択カーソル: 石を置く場所を決定 •技術スタック ・Vue.js: 言わずもがな ・Three.js: 3D空間にて盤面を表示する ・Vuetify: レスポンシブ対応などが便利 ・axios: サーバーとwebsocket通信 •仕様 ゲーム実行中の画面(白はAI,黒はプレイヤー) AIの石 立ち上げと同時にゲームサーバとwebsocket 接続. 石を置く際に置いた場所についての jsonを送信
10. 目次 ・立体四目とは？ ・開発について ・AIのアルゴリズム ・結果
11. 盤面の評価値 •概要: AIが現在どれほど優勢かを以下のルールに基づいて盤面から算出 •ルール: ①自分の石(白色)が4つ揃っていれば(勝敗)+1000点, 相手なら-1000点 ②自分の石(白色)が3つ揃っていれば(リーチ)+100点, 相手なら-100点 •例: ①白石(AI)が4つ揃っている → +1000点 ②黒石(プレイヤー)が3つ揃っている → -100点 Total: 900点 AIの”有利さ”は900点として評価
12. ゲーム木探索 ・・・ 次のターン AIが配置可能場所について 16通り存在 例: 現在の盤面 評価値 -100 評価値 -300 評価値 +200 評価値 +100 次の次のターン プレイヤーが配置可能場所 16通り存在 評価値 -300 評価値 +100 評価値 +200 評価値 +100 ・・・ 現在のターン プレイヤーが石を置いた
13. mini-Max法 ・・・ 次のターン AIが配置可能場所について 16通り存在 例: 現在の盤面 評価値 -100 評価値 -300 評価値 +200 評価値 +100 次の次のターン プレイヤーが配置可能場所 16通り存在 評価値 -300 評価値 +100 評価値 +200 評価値 +100 ・・・ プレイヤーのターン 相手は最善手を打って 評価値が最小になる手を 打ってくることを想定 最小となるものが選択 現在のターン プレイヤーが石を置いた
14. mini-Max法 ・・・ 次のターン AIが配置可能場所について 16通り存在 例: 現在の盤面 評価値 -100 評価値 -300 評価値 +200 評価値 +100 次の次のターン プレイヤーが配置可能場所 16通り存在 → 最善手を選んでくること を考える 評価値 -300 現在のターン プレイヤーが石を置いた 評価値 +400 最小値を選択 評価値 -400 評価値 +100
15. mini-Max法 ・・・ 次のターン AIが配置可能場所について 16通り存在 例: 現在の盤面 評価値 -100 評価値 -300 評価値 +200 評価値 +100 次の次のターン プレイヤーが配置可能場所 16通り存在 → 最善手を選んでくること を考える 現在のターン プレイヤーが石を置いた 評価値 +400 最小値の中で最大 相手が最善の手を取ったとしても被害が最小 「Mini-Max法」に従ってAIを構築 ここを選ぶ
16. 目次 ・立体四目とは？ ・開発について ・AIのアルゴリズム ・結果
17. 結果 白熱した戦いののちAIの勝利・・ シンギュラリティが発生
18. 結果 白熱した戦いののちAIの勝利・・ 2手先読みのためリーチした場合必ず阻止してくる ダブルリーチで詰ませるしか勝ち目がない
19. 今後の検証 ・さらに深くゲーム木を探索する(α-β法)の実装でAI同士を対戦、精度評価 ・立体四目の勝利パターンの発見