近畿大学理工学部情報学科 情報論理研究室 09-1-037-214 井藤 雄太 ニップの並列化 近畿大学理工学部情報学科 情報論理研究室 09-1-037-214 井藤 雄太
目次 ニップとは 二人零和有限確定完全情報ゲーム 並列計算 ニップＡＩ 実験結果 考察 結論および今後の課題 参考文献
ニップとは？ 二人零和有限確定完全情報ゲーム 円形のリバーシ リバーシよりも終盤での逆転が起こり易い
二人零和有限確定完全情報ゲーム 零和・・・プレイヤーの利得の合計が常に０になること 有限・・・プレイヤーの指し手の組み合わせ数が有限であ 確定・・・ランダム性が無いこと 完全情報ゲーム・・・各プレイヤーが自分の手番に相手の 手も含め,過去,現在の情報を全て知 ることができるゲーム
二人零和有限確定完全情報ゲームの完全解析 総局面数 ニップ・・・ 1024通り リバーシ・・・1028通り 6x6リバーシ・・・1017 通り →１６対２０で後手勝利 (Joel Feinstein, Amenor Wins World 6x6 Championships!,(1993))
二人零和有限確定完全情報ゲームの完全解析 総局面数 ニップ・・・ 1024通り 24 ×348 ×2=2,552,526,178,459,920,315,627,552 リバーシ・・・1028通り 6x6リバーシ・・・1017 通り →１６対２０で後手勝利 (Joel Feinstein, Amenor Wins World 6x6 Championships!,(1993))
二人零和有限確定完全情報ゲームに対する手法 先読みと局面の評価値 →数手先の局面を先読みし, 先読み後の局面の評価値によりどの手を打つか決定する →先読み手数を多くすると処理に膨大な時間がかかる 定石データベース・対戦データベース →定石をデータベース化し,各局面で有効な定石があればそれに従って打つ →データベースに無い局面が出てきたとき,学習が足りないときにはこの手法は使えない
並列計算 指数関数的に増えていく局面の評価計算を複数のプロセッサに配分 並列計算の使用例 Ex)新薬の開発,気象現象の解明…etc ３
ニップＡＩ 評価関数 → 評価値マップと相手の選択肢の数 評価値マップ 相手の選択肢の数による評価 20 -5 -2 3 相手の選択肢の数 → 評価値マップと相手の選択肢の数 評価値マップ 相手の選択肢の数による評価 20 -5 -2 3 相手の選択肢の数 評価値 100 1 20 2 10 3以上
ニップＡＩ 評価関数の計算例 候補手５の評価値は・・・ 20-5-2+0+0+0+3+3=19 20 -5 -2 3 ・盤面の評価値 ニップＡＩ 評価関数の計算例 相手の選択肢の数 評価値 100 1 20 2 10 3以上 １ ２ 候補手５の評価値は・・・ ・盤面の評価値 20-5-2+0+0+0+3+3=19 ・相手の選択肢の数 白の候補手が３つ以上なので0 ・合計 19+0=19 ３ ４ ８ ５ ７ ６
実験結果 ランダムＡＩ同士だと白が黒の２倍勝利 →後手有利？ 先読み数を増やしても勝率に変化がない
実験結果 評価関数の重みを変更 相手の選択肢の数 評価値 1000 1 200 2 50 3 10 4以上 相手の選択肢の数 評価値 100 1000 1 200 2 50 3 10 4以上 相手の選択肢の数 評価値 100 1 20 2 10 3以上
実験結果 評価値の重みを変更しても変化がない →選択肢の数は重要ではない？ →評価関数の計算に問題がある？
考察 ＡＩが期待したほど強くなかった →評価値の計算に問題がある？ →評価マップに問題はなかったか？ オープンニッププロジェクト →評価値の計算に問題がある？ →評価マップに問題はなかったか？ オープンニッププロジェクト http://sourceforge.jp/projects/opennip/ のOpenNip.ver2.2の「CPU(中)」との対戦成績
考察 ＡＩが期待したほど強くなかった →それぞれの候補手による評価値を毎回加算していた 最終的な盤面の評価値が低い方が選ばれてしまう １０ －１００ 合計－３０ ２０ －１０ ０ －３０ －４０ 合計－８０ 最終的な盤面の評価 最終的な盤面の評価値が低い方が選ばれてしまう
考察 ＡＩが期待したほど強くなかった →ゲーム終盤で逆転されるのを防ぐ 最後には逆転されてしまうのに評価値が高くなってしまう 評価値の計算は自分の手番での候補手から算出する ・終盤は必勝読みに切り替える ・評価関数を変更する ・終盤は評価値の計算方法を変更する
結論および今後の課題 →終盤は必勝読みに切り替える →評価関数を変更する →終盤は評価値の計算方法を変更する ニップの評価マップにおいて,外周を重視すればある程度は強くなったものの,決定的に強くなったわけではない 先読みをしているにもかかわらず勝率が期待したほどあがらなかった 途中まで優勢であっても最後に外周を全てひっくり返され,逆転されることがある →終盤は必勝読みに切り替える →評価関数を変更する →終盤は評価値の計算方法を変更する
結論および今後の課題 評価関数では相手の選択肢の数はさほど重要ではない可能性がある →検証が必要 →検証が必要 本研究において最終目標としていた並列化についてはできていない →評価関数の改善と共に必要
参考文献 結城 浩：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週間で」富士通の超並列サーバ hhttp://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