近畿大学理工学部情報学科 情報論理研究室 松浦 美里

Slides:



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

Othello Let us cling together. メンバー 班長 杉本友宏 プログラマー 京谷貴平 アルゴリズム 佐野祐之 パワーポイント 菊澤遼平 発表 川本敏和.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
ハノイグラフの生成と最短経路の導出 東京電機大学 理工学部 村田和也 松浦昭洋
MPIを用いたグラフの並列計算 情報論理工学研究室 藤本 涼一.
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
人工知能概論 第4回 探索(3) ゲームの理論.
5路盤の完全解析の結果 論文名:Solving Go on Small Boards 著者: Eric C.D. van der Werf
リレーショナル・データベース データベース論 第10回.
ML 演習 第 8 回 2007/07/17 飯塚 大輔, 後藤 哲志, 前田 俊行
近畿大学理工学部情報学科 情報論理工学研究室 滝口 直
コンピュータ囲碁の仕組み ~ 将棋との違い ~
四路の碁アプリ開発 情報論理工学研究所 高倉秀斗.
研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻.
リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ  前田昂寛.
アルゴリズムとデータ構造 2012年7月23日
インタラクティブ・ゲーム制作 <プログラミングコース>
15パズルの解法について 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ  大石 貴弘.
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
コンピュータ将棋におけるカーネル法を用いた静的評価関数の学習
モンテカルロ法と囲碁・将棋ソフトの人知超え
アルゴリズムとデータ構造 2011年7月14日
単位 おねだり ☆オセロ おねだり隊☆D班.
碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学) .
近畿大学理工学部情報学科 情報論理研究室 井藤 雄太
モンテカルロ碁 電気通信大学 村松研究室 下川和也.
UCB+ 法を用いた Big Two AI の研究
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
研究集会「組合せゲーム・パズル」,豊橋技術科学大学
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
MPIを用いた最適な分散処理 情報論理工学研究室 角 仁志
正規分布における ベーテ近似の解析解と数値解 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
Bridge It と Connections の 必勝法について
情報論理工学 研究室 第10回 完全解析されたゲーム.
1. MC/UCT アルゴリズムの 並列化に伴う挙動の変化 2. 探索木共有型並列と マスタスレーブ型並列 ― プラットフォームとの関係 ―
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(NlogN)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似法
WebGIS開発 総合政策学部2年 飯塚直 2004年10月14日 厳網林研究会.
テトリスにおけるAI の開発 情報論理工学研究室 13— 川原 翔太.
二人零和不完全情報ゲームであるジャンケンにおけるゲームの洗練法
リーダー 亀山奈央 プレゼンター 橘貴志 アルゴリズム 古森愛美 プログラマー 中島宏基 パワーポイント 公文ゆい
強化学習を用いたバックギャモンプレイヤーの生成 TD-Gammon
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
G班メンバー リーダー 橋本望 SE 北本理紗と服部友哉 PPT作成 橋本望と山田侑加
Bridge It と Connections の 必勝法について
三次元チェスアプリケーションの開発 およびUIの機能向上
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
近畿大学理工学部情報学科 情報論理工学研究室 赤井 隆純
不確実データベースからの 負の相関ルールの抽出
モンテカルロ法を用いた 立体四目並べの対戦プログラム
情報論理工学 研究室 第7回: 強い手の選択.
3次元Nクイーン問題の 解の存在の検証 07-1-037-0106 前波 大貴 情報論理工学研究室 宜しくお願いします。
理工学部情報学科 情報論理研究室 野中章宏 2016年2月5日
研究背景と目的 局面対による学習の高速化 学習器の説明 今後 大規模な強化学習技術の実証と応用 一方で、 強化学習手法の台頭
麻雀ゲームにおけるAIの開発    日高大地   近畿大学理工学部情報学科  
★C++/オブジェクト指向実践企画★ Othelloゲーム作成
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
数値解析ⅡーI ~オセロゲームのプログラム~
リレーショナル・データベース J2EE I (データベース論) 第2回 /
F班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史
囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008.
理工学部情報学科 情報論理工学研究室 延山 周平
数値解析Ⅱ ~五目並べのプログラミング~ C班.
近畿大学理工学部情報学科 情報論理工学研究室 段野健太
MPIを用いた並列処理計算 情報論理工学研究室 金久 英之
戦術的観点からの  変形碁盤間の   類似度評価 佐藤 真史(早稲田大学).
情報論理工学 研究室 第8回: ミニマックス法.
回帰テストにおける実行系列の差分の効率的な検出手法
人工知能概論 第4回 探索(3) ゲームの理論.
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
Presentation transcript:

近畿大学理工学部情報学科 情報論理研究室 09-1-037-0171 松浦 美里 ニップの並列化 近畿大学理工学部情報学科 情報論理研究室 09-1-037-0171 松浦 美里

目次 ニップとは 二人零和有限確定完全情報ゲーム 並列計算 ニップAI 実験結果 考察 結論および今後の課題 参考文献

ニップとは? 二人零和有限確定完全情報ゲーム 円形のリバーシ リバーシよりも終盤での逆転が起こり易い

二人零和有限確定完全情報ゲームの完全解析 総局面数 ニップ・・・ 1024通り リバーシ・・・1028通り 6x6リバーシ・・・1017 通り   →16対20で後手勝利    (Joel Feinstein, Amenor Wins World 6x6 Championships!,(1993))

二人零和有限確定完全情報ゲームに対する手法 先読みと局面の評価値  →数手先の局面を先読みし, 先読み後の局面の評価値によりどの手を打つか決定する  →先読み手数を多くすると処理に膨大な時間がかかる  定石データベース・対戦データベース  →定石をデータベース化し,各局面で有効な定石があればそれに従って打つ  →データベースに無い局面が出てきたとき,学習が足りないときにはこの手法は使えない

並列計算 指数関数的に増えていく局面の評価計算を複数のプロセッサに配分 並列計算の使用例 Ex)新薬の開発,気象現象の解明…etc 3

ニップAI 評価関数 → 評価値マップと相手の選択肢の数 評価値マップ 相手の選択肢の数による評価 30 -10 -2 3 相手の選択肢の数  → 評価値マップと相手の選択肢の数        評価値マップ      相手の選択肢の数による評価 30 -10 -2 3 相手の選択肢の数 評価値 1000 1 100 2 50 3 20 4以上

ニップAI 評価関数の計算例 候補手5の評価値は・・・ 30-10-2+0+0+0+3+3=24 30 -10 -2 3 ・盤面の評価値 ニップAI 評価関数の計算例 相手の選択肢の数 評価値 1000 1 100 2 50 3 20 4以上 1 2 3 候補手5の評価値は・・・ ・盤面の評価値 30-10-2+0+0+0+3+3=24 ・相手の選択肢の数 白の候補手が3つなので20 ・合計 24+20=44 4 8 5 7 6

実験結果 ランダム,既存のニップAIに対しても六割以上の勝率 ランダムには先手のほうが勝率が高い 対戦 先手勝ち 後手勝ち 引き分け AI対ランダム 75 25 ランダム対AI 38 62 AI対既存のAI 67 33 既存のAI対AI 32 68 既存のニップAI OpenNip(オープンニップ) プロジェクト,の「CPU(中)」 http://sourceforge.jp/projects/opennip/

実験結果 評価関数の重みを変更 相手の選択肢の数 評価値 1000 1 500 2 100 3 50 4 10 5以上 相手の選択肢の数 1000 1 500 2 100 3 50 4 10 5以上 相手の選択肢の数 評価値 1000 1 100 2 50 3 20 4以上

実験結果 ランダムに対しての勝率は先手後手ともに上がった 既存のAIに対しての勝率は後手が一割下がった 対戦 先手勝ち 後手勝ち 引き分け AI対ランダム 81 19 ランダム対AI 31 69 AI対既存のAI 64 36 既存のAI対AI 42 58 既存のニップAI OpenNip(オープンニップ) プロジェクト,の「CPU(中)」 http://sourceforge.jp/projects/opennip/

考察 AIは六割ほどの勝率 →ゲーム終盤で逆転されるのを防ぐ 最後には逆転されてしまうのに評価値が高くなってしまう 評価値の計算は自分の手番での候補手から算出する ・終盤は必勝読みに切り替える ・評価関数を変更する ・終盤は評価値の計算方法を変更する

結論および今後の課題 →終盤は必勝読みに切り替える →評価関数を変更する →終盤は評価値の計算方法を変更する ニップの評価マップにおいて,外周を重視すればある程度は強くなったものの,決定的に強くなったわけではない 先読みをしているので六割ほどの勝率で勝ち越した 途中まで優勢であっても最後に外周を全てひっくり返され,逆転されることがある →終盤は必勝読みに切り替える →評価関数を変更する   →終盤は評価値の計算方法を変更する

結論および今後の課題 評価関数では相手の選択肢の数はさほど重要ではない可能性がある →検証が必要  →検証が必要 本研究において最終目標としていた並列化についてはできていない  →評価関数の改善と共に必要

参考文献 結城浩:Java 言語で学ぶデザインパターン入門【マルチスレッド編】, ソフトバンククリエイティブ(2006) Seal Software:リバーシのアルゴリズム, 工学社(2007) OpenNip(オープンニップ) プロジェクト, http://sourceforge.jp/projects/opennip/ Janos Wagner and Istvan Virag, Solving renju, ICGA Journal, Vol.24, No.1, pp.30-35 (2001), http://www.sze.hu/~gtakacs/download/wagnervirag_2001.pdf Jonathan Schaeffer, Neil Burch, Yngvi Bjorsson, Akihiro Kishimoto, Martin Muller, Robert Lake, Paul Lu, and Steve Suphen, Checkers is solved, Science Vol.317, No,5844, pp.1518-1522 (2007). http://www.sciencemag.org/content/317/5844/1518.full.pdf Joel Feinstein, Amenor Wins World 6x6 Championships!, Forty billion noted under the tree (July 1993), pp.6-8, British Othello Federation's newsletter, (1993), http://www.britishothello.org.uk/fbnall.pdf 清慎一, 川嶋俊:探索プログラムによる四路盤囲碁の解, 情報処理学会研究報告, GI 2000(98), pp.69--76 (2000), http://id.nii.ac.jp/1001/00058633/ Eric C.D. van der Welf, H.Jaap van den Herik, and Jos W.H.M.Uiterwijk, Solving Go on Small Boards, ICGA Journal, Vol.26, No.2, pp.92-107 (2003).

参考文献 北尾まどか, 藤田麻衣子, どうぶつしょうぎねっと, (2010), http://dobutsushogi.net/ 田中哲郎,「どうぶつしょうぎ」 の完全解析, 情報処理学会研究報告Vol.2009-GI-22 No.3, pp.1-8(2009), http://id.nii.ac.jp/1001/00062415/ 美添一樹, 山下宏, 松原仁 : コンピュータ囲碁―モンテカルロ法の理論と実践―, 共立出版, (2012). Nipp - アブストラクトゲーム博物館,                   http://www.nakajim.net/index.php?Nipp 最強オセロ「WZebra」 http://homepage3.nifty.com/akky-han/100529.html MasterReversi Home Page   http://homepage2.nifty.com/t_ishii/mr/index.html 14th 世界コンピュータチェス選手権 http://www.grappa.univ-lille3.fr/icga/tournament.php?id=16&lang=3 「63年かかる分子動力学計算を2週間で」富士通の超並列サーバ      http://www.atmarkit.co.jp/news/200311/06/fujitsu.html 地球シミュレーター http://www.jamstec.go.jp/es/jp/index.html 第1回並列ゼミ 並列処理概論 - 知的システムデザイン研究室, http://mikilab.doshisha.ac.jp/dia/seminar/2000/parallel_1.pdf