戦術的観点からの  変形碁盤間の   類似度評価 佐藤 真史(早稲田大学).

Slides:



Advertisements
Similar presentations
コンピュータ囲碁における Root 並列化について 発表者 副島 佑介. 目次 研究背景 – 囲碁の難しさ – モンテカルロ木探索について – 並列化手法の先行研究 提案手法 – Root 並列化における合議制 実験結果 まとめ.
Advertisements

生物統計学・第 4 回 比べる準備をする 平均、分散、標準偏差、標準誤差、標準 化 2015 年 10 月 20 日 生命環境科学域 応用生命科学類 尾形 善之.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
リーダー 辻元健照 プログラム 北川泰士 アルゴリズム 水野雄太 ユーザー 松田邦久 プレゼン 戸所風士
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
人工知能概論 第4回 探索(3) ゲームの理論.
5路盤の完全解析の結果 論文名:Solving Go on Small Boards 著者: Eric C.D. van der Werf
ゲーム理論・ゲーム理論Ⅰ (第4回) 第3章 完全情報の展開形ゲーム
近畿大学理工学部情報学科 情報論理工学研究室 滝口 直
コンピュータ囲碁の仕組み ~ 将棋との違い ~
ゲーム理論・ゲーム理論Ⅰ (第6回) 第4章 戦略形ゲームの応用
四路の碁アプリ開発 情報論理工学研究所 高倉秀斗.
リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ  前田昂寛.
インタラクティブ・ゲーム制作 <プログラミングコース>
法と経済学(file 6) ゲーム理論2 今日の講義の目的 (1)展開型ゲームという考え方を理解する (2)後方帰納法の考え方を理解する
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
コンピュータ将棋におけるカーネル法を用いた静的評価関数の学習
クロスワードゲームの 作り方を学ぼう/やってみよう ‐ボードゲームの動作機構‐
初級ミクロ経済学 -ゲーム理論入門- 2014年12月15日 古川徹也 2014年12月15日 初級ミクロ経済学.
 Combinations(2)        古川 勇輔.
モンテカルロ法と囲碁・将棋ソフトの人知超え
単位 おねだり ☆オセロ おねだり隊☆D班.
碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学) .
近畿大学理工学部情報学科 情報論理研究室 井藤 雄太
最短路問題のための LMS(Levelwise Mesh Sparsification)
10.通信路符号化手法2 (誤り検出と誤り訂正符号)
モンテカルロ碁 電気通信大学 村松研究室 下川和也.
UCB+ 法を用いた Big Two AI の研究
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
京都大学 ○太田圭亮 川原純 伊藤大雄 堀山貴史
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
研究集会「組合せゲーム・パズル」,豊橋技術科学大学
~オセロゲーム~ アルゴリズムとそのプログラム
シャノンのスイッチングゲームにおけるペアリング戦略について
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
高速剰余算アルゴリズムとそのハードウェア実装についての研究
三角形や四角形ではない図形の 角の大きさの和を求めよう。.
情報論理工学 研究室 第10回 完全解析されたゲーム.
佐藤のゲーム とその仲間たち (完全可解ゲームの話) 関西学院大学  川中 宣明 数理科学研究センター談話会    2011年6月29日.
利用関係に基づく類似度を用いたJavaコンポーネント分類ツールの作成
二人零和不完全情報ゲームであるジャンケンにおけるゲームの洗練法
第Ⅱ部 協力ゲームの理論 第10章 コア 2008/07/01(火) ゲーム理論合宿.
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
BLACK JACKの作成 ブラックジャックのルール 概要 勝敗の判定 開発中の問題点 Aの扱いについて 配り直し(DEAL) 工夫した点
Internet広域分散協調サーチロボット の研究開発
配牌時の役満和了率 を考慮した麻雀AIの開発
G班メンバー リーダー 橋本望 SE 北本理紗と服部友哉 PPT作成 橋本望と山田侑加
京都大学大学院情報学研究科 宮川博光 伊藤大雄
近畿大学理工学部情報学科 情報論理研究室 松浦 美里
近畿大学理工学部情報学科 情報論理工学研究室 赤井 隆純
シューティングゲームにおける 未経験者と経験者の差異の解析
モンテカルロ法を用いた 立体四目並べの対戦プログラム
情報論理工学 研究室 第7回: 強い手の選択.
麻雀ゲームにおけるAIの開発    日高大地   近畿大学理工学部情報学科  
★C++/オブジェクト指向実践企画★ Othelloゲーム作成
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
数値解析ⅡーI ~オセロゲームのプログラム~
Othelloのプログラム 班長:佐々木 悠二 班員:石黒 護     井上 雄滋     齊藤 良裕     清水 裕亮.
F班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史
囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008.
数値解析Ⅱ ~五目並べのプログラミング~ C班.
近畿大学理工学部情報学科 情報論理工学研究室 段野健太
第28回世界コンピュータ将棋選手権アピール文章 作成:井本 康宏 作成日:2018/3/吉日
第Ⅰ部 非協力ゲームの理論 第6章 情報の価値 2008/07/01(火) ゲーム理論合宿 M2 渡辺美穂.
分割制限ニム 山崎浩一*、五十嵐善英*、塚村善弘 *群馬大学理工学部.
Othello G班         山崎 木下 山本 上手      .
情報論理工学 研究室 第8回: ミニマックス法.
人工知能概論 第4回 探索(3) ゲームの理論.
各種荷重を受ける 中空押出形成材の構造最適化
Presentation transcript:

戦術的観点からの  変形碁盤間の   類似度評価 佐藤 真史(早稲田大学)

研究目標 1.異なるゲーム同士の比較、差異や類似点の解析 2.あるゲームで得た(戦術、戦略などに関する)知識の他ゲームへの流用。 例えば、 「麻雀」と「ポーカー」はどれくらい似ているか 「5五将棋」、「どうぶつ将棋」の経験は「将棋」に活かせるか  といった類の話 本発表で行った実験:碁盤のトーラス性とサイズ変更の比較

目次 そもそも何を比較すればよいか 最終的には勝ち負けが重要 比較可能なゲームの条件は 同一プレイヤーの存在 比較に必要な情報は何か プレイヤーの性格の差 今回実験するゲーム 盤の形が異なる囲碁 汎用的プレイヤー 戦術写像プレイヤー 結果と考察 まとめ

最終的に重要なのは勝敗、勝ち方 問題提起1:似ているゲームとは 直感的に似ている例: 麻雀とポーカー 手札、手牌を交換して揃えていく 将棋とチェス 盤上の駒を動かして王を取る オセロ、五目並べ、○×ゲーム 直線的に置いていく HEXとカタン ボードが六角形で構成される 最終的に重要なのは勝敗、勝ち方 戦術、戦略的に似ている例: 完全情報、非完全情報 確率と相手の行動どちらが重要か 序盤や中盤、終盤といった概念があるか 「機を見る」ような判断が必要か 得点制か一発KOか 利得最大か0,1の判定か

問題提起2:誰にとって似ているか 多少弱くてもいいので、癖のあるプレイヤーの方が ゲームの特徴の影響を受けやすいはず 知識を流用する = 「同一人物」が、ゲームAをプレイ後に、ゲームBをプレイする状況を想定  Deep Blueに将棋を指させて、Bonanzaに囲碁を打たせて、Alpha GoにチェスをPlayさせる  簡単なゲームでの練習を経て、高度なゲームに挑戦する 流用可能なプレイヤーの例:(単純な)モンテカルロ、モンテカルロ木探索プレイヤー  そもそも知識を使っていない。(可能な選択と次の状況、勝敗のルールを知っているだけ)   =>「先手の勝率」などが出るだけ。ゲームの特徴とは言えない。 多少弱くてもいいので、癖のあるプレイヤーの方が ゲームの特徴の影響を受けやすいはず

プレイヤー1人1人を 特徴量としてゲームを評価 提案する評価方法のイメージ ゲームA ゲームB 2ゲーム間の距離 プレイヤーG プレイヤーH プレイヤーM 強 強 プレイヤー1人1人を 特徴量としてゲームを評価 0+1+0 強 弱 =1 弱 弱 …

今回用いるゲーム:変形碁とは 四角くない碁盤での囲碁 シンプルグラフなら平面でなくてもOK 「空いているところに打て」て、「囲まれたら取られる」という基本ルールは同じ 正方形の碁盤と比べると、共通して使える戦術、全く使えない戦術がある。  例:三角碁盤はコウが生じない、六角碁盤は容易にシチョウになる、トーラスは隅が無い等 参考文献:格子型碁盤と特殊な碁盤での有効着手の相違性の解析[佐藤、穴田、堤2016]

囲碁の簡単な説明 1.交互に自分の石を好きなところに置いていく。 2.ネットワークを切断すると自分の得点。 9路盤

囲碁の簡単な説明 1.交互に自分の石を好きなところに置いていく。 2.ネットワークを切断すると自分の得点。 3.囲われると取られる。

囲碁の簡単な説明 1.交互に自分の石を好きなところに置いていく。 2.ネットワークを切断すると自分の得点。 3.囲われると取られる。 ポイント:囲う=ネットワークの切断

クセのあるプレイヤーモデルの定義 プレイヤー =局面に応じて一つの着手を選ぶ一つの「写像」 プレイヤー =局面に応じて一つの着手を選ぶ一つの「写像」 確率的プレイヤー =特定の条件を満たした交点に「打ちやすい」傾向 すなわち、  「交点に与える条件」から、プレイヤーを生成する。

戦術写像 =白石に隣接する黒石 戦術写像: 局面から交点の部分集合への写像 演算を木型に組み合わせて構成される 利点: 組み合わせ方を変えることで全く異なる写像になる 計算過程が「読める」 ●戦術写像の例 共通部分 隣接 黒石 白石 =白石に隣接する黒石 使用する演算 2項演算:共通部分、和集合、差集合、... 1項演算:補集合、隣接交点、息、n以上隣接している、... 0項演算:黒石、白石、空点、アタリ、直前の着手、...

戦術写像の計算過程 共通部分 隣接 黒石 白石 局面

戦術写像プレイヤー 候補が複数ある場合、候補の中から一つランダムに選んで打つ。

戦術写像プレイヤー 候補が複数ある場合、候補の中から一つランダムに選んで打つ。 候補が1つの場合は、当然、そこに打つ。

戦術写像プレイヤー 候補が複数ある場合、候補の中から一つランダムに選んで打つ。 候補が1つの場合は、当然、そこに打つ。 候補が一つもない場合(ただし打てる場所はある場合)、  全体からランダムに選んで打つ。

プレイヤーの用意の仕方 演算をランダムに組み合わせる。その際、木の大きさに上限(9)を設定 (根から一定距離離れたら、0項演算のみを追加) 用意した戦術写像数:2000 ただし全ては用いず、9路盤において対ランダムプレイヤーの勝率上位30個を採用 選出した30プレイヤー同士を先後変えて各100戦行い、 「先手時の勝率」「後手時の敗北率」及び「先手時の勝率ー後手時の敗北率」を計算

上位30 ランダムと同程度のプレイヤー わざと悪い手を打つプレイヤー

今回用いた変形碁盤 9路盤 6路盤 9路トーラス 6路トーラス

各碁盤の特徴量 各プレイヤーの先手勝率(%) 9路盤 65 67 62 64 52 75 48 66 59 72 51 50 46 29 54 37 36 55 41 9路T 56 57 47 58 80 69 82 71 83 70 6路盤 68 73 42 43 61 30 6路T 77 76 78 81 60 各写像の(先手勝率ー後手敗北率)(%) 9路盤 18 23 11 25 22 -40 21 20 40 -43 13 19 -4 33 -41 14 -16 -31 3 -61 -2 -37 -1 9路T -6 -3 -25 -13 -7 -10 12 8 2 38 16 10 6路盤 26 -42 -39 34 -47 30 17 24 -5 1 -11 -9 -55 -27 -8 -52 6路T -15 9 -21 7 15 31 5

6路トーラス 6路盤 9路トーラス 9路盤

9路盤 6路盤 6路盤トーラス

トーラスで強い 9路盤 6路盤 正方盤で強い 別観点で打つタイプ 6路盤トーラス

結果 追加実験:19路盤くらい大きくなったら、隅からの影響が減って トーラスっぽくなるのではないか? ほとんどのプレイヤーが、  「6路盤、9路盤」⇔「6路トーラス、9路トーラス」間で大きく成績が異なる。 9路盤での成績が良いものを選出した30プレイヤーだが、9路盤での勝率も結構違う。相性? 追加実験:19路盤くらい大きくなったら、隅からの影響が減って        トーラスっぽくなるのではないか? 19路盤でも同様に各プレイヤー同士で、(時間の関係上)10戦ずつ行って勝率、敗北率を計算

碁盤間の差異の評価 19路盤:6路盤、9路盤よりも、トーラスに近い 9路トーラス 6路盤 6路トーラス 19路盤 9路盤 32.7 10.7 碁盤間距離(A,B)= プレイヤー Aでの勝率敗北率差-Bでの勝率敗北率差 碁盤間距離 9路トーラス 6路盤 6路トーラス 19路盤 9路盤 32.7 10.7 30.7 23.3 34.0 6.4 16.5 31.4 27.2 17.7 19路盤:6路盤、9路盤よりも、トーラスに近い

まとめ 簡単ではあるが、ゲーム同士の類似度の評価を行えた。 19路盤が、9路盤よりも9路トーラスに近いという結果が得られた。   →9路盤で練習するよりも9路トーラスで練習する方が有効? プレイヤーの生成、選出方法や類似度の定義をもう少し理論的なものに改良していく予定

1242 P4 InvF B1 1250 F0 EM 1453 P0 AND SUB NOT D0 Q0 HIT P2 1792 P3 Q3 1974 A0 Q4 MV 264 Q1 D1 274 OR P1 WH BL 1306 A1 Q2 RG0 1696 94 RG1 204 306 F 998 P4 P0 RG0 1060 NOT D1 Q3 F MV 1387 Q4 P1 F0 BL 1605 OR Q1 Q0 B1 1702 P2 1850 WH 1938 A0 1988 Q2 AND SUB HIT EM 1886 1190 604 A1 747 P3 1170

1734 InvF WH 1924 Q1 Q4 P0 138 P4 OR A1 HIT Q2 AND F EM P1 B1 752 NOT SUB 1901 F0