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

Presentation on theme: "近畿大学理工学部情報学科 情報論理研究室 松浦 美里"— Presentation transcript:

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

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

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

4

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

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

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

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

9 ニップＡＩ 評価関数の計算例 候補手５の評価値は・・・ 30-10-2+0+0+0+3+3=24 30 -10 -2 3 ・盤面の評価値
ニップＡＩ 評価関数の計算例 相手の選択肢の数 評価値 1000 1 100 2 50 3 20 4以上 １ ２ ３ 候補手５の評価値は・・・ ・盤面の評価値 =24 ・相手の選択肢の数 白の候補手が３つなので20 ・合計 24+20=44 ４ ８ ５ ７ ６

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

11 実験結果 評価関数の重みを変更 相手の選択肢の数 評価値 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以上

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

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

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

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

16 参考文献 結城浩：Java 言語で学ぶデザインパターン入門【マルチスレッド編】, ソフトバンククリエイティブ(2006)
Seal Software：リバーシのアルゴリズム, 工学社(2007) OpenNip(オープンニップ) プロジェクト, Janos Wagner and Istvan Virag, Solving renju, ICGA Journal, Vol.24, No.1, pp (2001), 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 (2007). Joel Feinstein, Amenor Wins World 6x6 Championships!, Forty billion noted under the tree (July 1993), pp.6-8, British Othello Federation's newsletter, (1993), 清慎一, 川嶋俊：探索プログラムによる四路盤囲碁の解, 情報処理学会研究報告, GI 2000(98), pp (2000), 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 (2003).

17 参考文献 北尾まどか, 藤田麻衣子, どうぶつしょうぎねっと, (2010), http://dobutsushogi.net/
田中哲郎,「どうぶつしょうぎ」 の完全解析, 情報処理学会研究報告Vol.2009-GI-22 No.3, pp.1-8(2009), 美添一樹, 山下宏, 松原仁 : コンピュータ囲碁―モンテカルロ法の理論と実践―, 共立出版, (2012). Nipp - アブストラクトゲーム博物館,　　　　　　　　　　　　　　　 　　　 最強オセロ「WZebra」　 MasterReversi Home Page　　 14th 世界コンピュータチェス選手権　 「63年かかる分子動力学計算を2週間で」富士通の超並列サーバ　　　　　 地球シミュレーター 第1回並列ゼミ 並列処理概論 - 知的システムデザイン研究室,