リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ 09-037-0164　前田昂寛.

Presentation on theme: "リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ 09-037-0164　前田昂寛."— Presentation transcript:

1 リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ 　前田昂寛

2 目次 １：本研究の目的 ２：本研究で使用した評価関数 ３：序盤・中盤の評価関数 ４：終盤の評価関数 ５：本研究で用いたプログラム ６：実験
７：結論 ８：今後の課題 ９：参考文献

3 本研究の目的 ・一般的なリバーシプログラムは先読み数が少ない といった解析にあたっての問題がある
・本研究ではマルチスレッド処理によりリバーシプロ グラムが高速化できることを示す　　　

4 リバーシプログラムの現状 ・現状完全解析には至っていない ・強いプログラムにするために定石データベースを使用
　－Logistello： 　－Zebra: ・評価関数 　－必勝読み：最終局面で自分の勝敗を評価 　－着手可能手数：自分が打てるマスの数

5 強いリバーシプログラム ・Logistello －定石データベースを使用したプログラム －1997年、村上健八段に勝利
　－定石データベースを使用したプログラム 　－1997年、村上健八段に勝利 　－定石データベースに依存しているため、定石以外の　　 手を打たれた場合の動作は未知 ・Zebra 　－定石データベースと先読みを使ったプログラム 　－先読み数を変更できる 　－定石データベースである「book」を上書きで学ばせ　　 ることができる

6 ・定石とは一般的に有利になりやすいと言われるパター ン 兎定石後の5手目 虎定石後の5手目 牛定石後の5手目
　　兎定石後の5手目　　　　　　虎定石後の5手目　　　　　　牛定石後の5手目　　 a b c d e f g h 1 2 3 4 5 6 7 8 a b c d e f g h 1 2 3 4 5 6 7 8 a b c d e f g h 1 2 3 4 5 6 7 8

7 評価関数 ・リバーシにおける評価関数 (ex. ・山、ウィング、開放度、着手可能数、C打ち、X打ち判 定、確定石
・その他にも盤面評価値、直線性、中割り、引っ張り etc・・・ ・これらは先読みを加えることでより高度な評価が可能

8 本研究で使用した評価関数 ・序盤・中盤の評価関数 ・終盤の必勝読み ・終盤の完全読み

9 本研究で使用した 序盤・中盤の評価関数 ・着手可能手数、確定石 ・C打ち、X打ち判定 ・ウィング ・山
終盤 必勝読み 完全読み ・着手可能手数、確定石 ・C打ち、X打ち判定 ・ウィング ・山 ・開放度 　　※リバーシのアルゴリ ズム[1]より

10 着手可能手数、確定石 ・着手可能手数：着手可能手数では自分が打てる石が 多ければ多い程高評価である。これは、戦略が膨らむ からである
・確定石：ゲーム終了まで二度と裏返らない石のことをいう。確 定石は有利な局面を作るためには非常に重要で、角を取れば 有利に対戦を進められるという一般的見解はこの確定石である ことが大きな意味を持つ。周囲に空きマスがない状態で、連接 する石が裏返らない時になる。

11 ・角の隣と斜め隣の事を言う。一般的に不利と言われて いる場所である。
C打ち、X打ち ・角の隣と斜め隣の事を言う。一般的に不利と言われて いる場所である。

12 ・ウィングは一般的に不利な形と言われているマイナス 評価である

13 ・ウィングは一般的に不利な形と言われているマイナス 評価である

14 ・山とは一般的に有利な形と言われている。 左は山の形。右側は山の有利な例。次が黒番の時、白は必ず隅を取 れる

15 開放度 ・自分が打った手によって裏返る石の周辺8マスが空き マスかどうかを調べる → 相手の打てる場所を少なく する為、小さいほど高評価
・自分が打った手によって裏返る石の周辺8マスが空き マスかどうかを調べる　→　相手の打てる場所を少なく する為、小さいほど高評価 A= H=6+2=8 B= I =6 C= J =5 D=3+2=5 E=2+1+4=７ F=1 G=3　　　　　　　　　　　　　　　

16 ・必勝読み ・完全読み ※リバーシのアルゴリズム[1]より
本研究で使用した 終盤の評価関数 序盤・中盤の 評価関数 終盤 ・必勝読み ・完全読み ※リバーシのアルゴリズム[1]より 必勝読み 完全読み

17 必勝読み、完全読み ・終盤の評価関数の特徴 －終盤では単に勝敗や自分の取れる石の数が多い か少ないかを見ればよい
　－終盤では単に勝敗や自分の取れる石の数が多い か少ないかを見ればよい ・完全読み：color*(count(BLACK) – count(WHITE)) ・必勝読み：完全読みと違いWIN=1,LOSE=- 1,DRAW=0しか見ず石の数を無視するため、比較演算 子を用いる時に計算量を軽くできる

18 ・SSAI ・MSAI 本研究で用いたプログラム

19 SSAI 　 ・SSAI：本研究で用いたJava言語によるシングルスレッドプログラミングによるリバーシ 評価関数 決定 探索 評価 　　　　　　　　SSAI

20 SSAIの処理 ・クラスAIで探索処理 ・評価関数決定： ー序盤・中盤の評価関数 ー終盤の必勝読み －終盤の完全読み ・探索：
　 ・クラスAIで探索処理 ・評価関数決定： 　ー序盤・中盤の評価関数 　ー終盤の必勝読み 　－終盤の完全読み ・探索： 　ーα－β法による再起処理

21 ・MSAI：本研究に用いたJava言語によるマルチスレッド プログラミングによるリバーシ
評価関数 決定 探索 評価 MSAI

22 MSAIの処理 枝木一つに対し1スレッド ・クラスAIとクラスMultiAIで探索 ・評価関数決定： －序盤・中盤の評価関数
　－序盤・中盤の評価関数 　－終盤の必勝読み 　－終盤の完全読み ・探索： 　－α－β法による再起処理 　－候補手の分だけサブスレッド作成　 枝木一つに対し1スレッド

23 実験環境 実験内容 先読み設定数 Let'sNote,VT64の実験結果
　実験環境 　実験内容 　先読み設定数 Let'sNote,VT64の実験結果 実験

24 実験環境 ・Let'sNote： ープロセッサ：Intel Core2Duo L7800 ２コア ２GHｚ －メモリ（RAM)：２GB
　－OS：WindowsVista 　－Java実行環境：eclipse ・VT64: 　－プロセッサ：（AMD　Opteron 1.9GHz　12コア）*4 　－メモリ（RAM)：１２８GB 　－OS：CentOS 　－Java実行環境：ターミナル ４８コア

25 実験内容 ・対戦方法：SSAI,MSAIをランダムなAIと実験環境下で 先攻、後攻分けて対戦させる ・実行：ある先読み設定数で１００回実行
・処理時間の見方：ある先読み設定数で１００回実行し た時の合計実行時間を見る

26 先読み設定数 ・

27 Let'sNote実験結果（勝敗） 後攻 先攻

28 VT64実験結果（勝敗） 後攻 先攻

29 SSAIの実験結果 VT64 ※処理時間は秒 Let'sNote

30 MSAIの実験結果 VT64 ※処理時間は秒 Let'sNote

31 VT64とLet'sNoteによる実験 ・MSAIで見た時、先の実験ではLet'sNoteとVT64は処 理時間に差がでなかった
・eclipseによりJavaプログラムが高速動作していた可 能性があることから、MSAIに限定してターミナルによる 実験を行う。 ・後攻先攻の差がほとんど見られないので後攻に限定

32 先読み設定数 ・

33 VT64とLet'sNoteによる実験 ※処理時間は秒

34 結論 ・マルチスレッドプログラミングにより、探索による処理 時間を大幅に短縮することができた
・eclipseを使用することにより、Let'sNoteの様なコア数 の少ない計算機でもマルチコアコンピュータに勝る結果 を出すことが可能となった

35 今後の課題 処理時間を大幅に短縮したので、より複雑な評価 関数を導入する必要がある。
そうなった時、探索に並び評価に多大な時間を要 することが予測されるため、評価関数の並列化が 今後の課題である。

36 参考文献 [1]Seal Software ,リバーシのアルゴリズム,工学社,2003
[2]結城浩,Java言語で学ぶデザインパターン入門[マルチスレッド 編],SoftBankCreative,2006 [3]日本オセロ連盟, セロ講座,初心者,2002 [4]大筆豊,オセロプログラムの評価関数の改善について,情報処理 学会研究報告2004-GI-11 ,p.15-p.20,2004