リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ 09-037-0164 前田昂寛
目次 1:本研究の目的 2:本研究で使用した評価関数 3:序盤・中盤の評価関数 4:終盤の評価関数 5:本研究で用いたプログラム 6:実験 7:結論 8:今後の課題 9:参考文献
本研究の目的 ・一般的なリバーシプログラムは先読み数が少ない といった解析にあたっての問題がある ・本研究ではマルチスレッド処理によりリバーシプロ グラムが高速化できることを示す
リバーシプログラムの現状 ・現状完全解析には至っていない ・強いプログラムにするために定石データベースを使用 -Logistello:https://skatgame.net/mburo/log.html -Zebra:http://radagast.se/othello/ ・評価関数 -必勝読み:最終局面で自分の勝敗を評価 -着手可能手数:自分が打てるマスの数
強いリバーシプログラム ・Logistello -定石データベースを使用したプログラム -1997年、村上健八段に勝利 -定石データベースを使用したプログラム -1997年、村上健八段に勝利 -定石データベースに依存しているため、定石以外の 手を打たれた場合の動作は未知 ・Zebra -定石データベースと先読みを使ったプログラム -先読み数を変更できる -定石データベースである「book」を上書きで学ばせ ることができる
・定石とは一般的に有利になりやすいと言われるパター ン 兎定石後の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
評価関数 ・リバーシにおける評価関数 (ex. ・山、ウィング、開放度、着手可能数、C打ち、X打ち判 定、確定石 ・その他にも盤面評価値、直線性、中割り、引っ張り etc・・・ ・これらは先読みを加えることでより高度な評価が可能
本研究で使用した評価関数 ・序盤・中盤の評価関数 ・終盤の必勝読み ・終盤の完全読み
本研究で使用した 序盤・中盤の評価関数 ・着手可能手数、確定石 ・C打ち、X打ち判定 ・ウィング ・山 終盤 必勝読み 完全読み ・着手可能手数、確定石 ・C打ち、X打ち判定 ・ウィング ・山 ・開放度 ※リバーシのアルゴリ ズム[1]より
着手可能手数、確定石 ・着手可能手数:着手可能手数では自分が打てる石が 多ければ多い程高評価である。これは、戦略が膨らむ からである ・確定石:ゲーム終了まで二度と裏返らない石のことをいう。確 定石は有利な局面を作るためには非常に重要で、角を取れば 有利に対戦を進められるという一般的見解はこの確定石である ことが大きな意味を持つ。周囲に空きマスがない状態で、連接 する石が裏返らない時になる。
・角の隣と斜め隣の事を言う。一般的に不利と言われて いる場所である。 C打ち、X打ち ・角の隣と斜め隣の事を言う。一般的に不利と言われて いる場所である。
・ウィングは一般的に不利な形と言われているマイナス 評価である
・ウィングは一般的に不利な形と言われているマイナス 評価である
・山とは一般的に有利な形と言われている。 左は山の形。右側は山の有利な例。次が黒番の時、白は必ず隅を取 れる
開放度 ・自分が打った手によって裏返る石の周辺8マスが空き マスかどうかを調べる → 相手の打てる場所を少なく する為、小さいほど高評価 ・自分が打った手によって裏返る石の周辺8マスが空き マスかどうかを調べる → 相手の打てる場所を少なく する為、小さいほど高評価 A=3 H=6+2=8 B=3 I =6 C=3 J =5 D=3+2=5 E=2+1+4=7 F=1 G=3
・必勝読み ・完全読み ※リバーシのアルゴリズム[1]より 本研究で使用した 終盤の評価関数 序盤・中盤の 評価関数 終盤 ・必勝読み ・完全読み ※リバーシのアルゴリズム[1]より 必勝読み 完全読み
必勝読み、完全読み ・終盤の評価関数の特徴 -終盤では単に勝敗や自分の取れる石の数が多い か少ないかを見ればよい -終盤では単に勝敗や自分の取れる石の数が多い か少ないかを見ればよい ・完全読み:color*(count(BLACK) – count(WHITE)) ・必勝読み:完全読みと違いWIN=1,LOSE=- 1,DRAW=0しか見ず石の数を無視するため、比較演算 子を用いる時に計算量を軽くできる
・SSAI ・MSAI 本研究で用いたプログラム
SSAI ・SSAI:本研究で用いたJava言語によるシングルスレッドプログラミングによるリバーシ 評価関数 決定 探索 評価 SSAI
SSAIの処理 ・クラスAIで探索処理 ・評価関数決定: ー序盤・中盤の評価関数 ー終盤の必勝読み -終盤の完全読み ・探索: ・クラスAIで探索処理 ・評価関数決定: ー序盤・中盤の評価関数 ー終盤の必勝読み -終盤の完全読み ・探索: ーα-β法による再起処理
・MSAI:本研究に用いたJava言語によるマルチスレッド プログラミングによるリバーシ 評価関数 決定 探索 評価 MSAI
MSAIの処理 枝木一つに対し1スレッド ・クラスAIとクラスMultiAIで探索 ・評価関数決定: -序盤・中盤の評価関数 -序盤・中盤の評価関数 -終盤の必勝読み -終盤の完全読み ・探索: -α-β法による再起処理 -候補手の分だけサブスレッド作成 枝木一つに対し1スレッド
実験環境 実験内容 先読み設定数 Let'sNote,VT64の実験結果 実験環境 実験内容 先読み設定数 Let'sNote,VT64の実験結果 実験
実験環境 ・Let'sNote: ープロセッサ:Intel Core2Duo L7800 2コア 2GHz -メモリ(RAM):2GB -OS:WindowsVista -Java実行環境:eclipse ・VT64: -プロセッサ:(AMD Opteron 1.9GHz 12コア)*4 -メモリ(RAM):128GB -OS:CentOS -Java実行環境:ターミナル 48コア
実験内容 ・対戦方法:SSAI,MSAIをランダムなAIと実験環境下で 先攻、後攻分けて対戦させる ・実行:ある先読み設定数で100回実行 ・処理時間の見方:ある先読み設定数で100回実行し た時の合計実行時間を見る
先読み設定数 ・
Let'sNote実験結果(勝敗) 後攻 先攻
VT64実験結果(勝敗) 後攻 先攻
SSAIの実験結果 VT64 ※処理時間は秒 Let'sNote
MSAIの実験結果 VT64 ※処理時間は秒 Let'sNote
VT64とLet'sNoteによる実験 ・MSAIで見た時、先の実験ではLet'sNoteとVT64は処 理時間に差がでなかった ・eclipseによりJavaプログラムが高速動作していた可 能性があることから、MSAIに限定してターミナルによる 実験を行う。 ・後攻先攻の差がほとんど見られないので後攻に限定
先読み設定数 ・
VT64とLet'sNoteによる実験 ※処理時間は秒
結論 ・マルチスレッドプログラミングにより、探索による処理 時間を大幅に短縮することができた ・eclipseを使用することにより、Let'sNoteの様なコア数 の少ない計算機でもマルチコアコンピュータに勝る結果 を出すことが可能となった
今後の課題 処理時間を大幅に短縮したので、より複雑な評価 関数を導入する必要がある。 そうなった時、探索に並び評価に多大な時間を要 することが予測されるため、評価関数の並列化が 今後の課題である。
参考文献 [1]Seal Software ,リバーシのアルゴリズム,工学社,2003 [2]結城浩,Java言語で学ぶデザインパターン入門[マルチスレッド 編],SoftBankCreative,2006 [3]日本オセロ連盟,http://www.othello.gr.jp/beginner/s_01.html,オ セロ講座,初心者,2002 [4]大筆豊,オセロプログラムの評価関数の改善について,情報処理 学会研究報告2004-GI-11 ,p.15-p.20,2004