リバーシの並列化

09-037-0164 前田昂寛
1:本研究の目的
2:本研究で使用した評価関数
3:序盤・中盤の評価関数
4:終盤の評価関数
5:本研究で用いたプログラム
6:実験
7:結論
8:今後の課題
9:参考文献
・一般的なリバーシプログラムは先読み数が少ない
といった解析にあたっての問題がある
・本研究ではマルチスレッド処理によりリバーシプロ
グラムが高速化できることを示す
・現状完全解析には至っていない
・強いプログラムにするために定石データベースを使用
-Logistello:https://skatgame.net/mburo/log.html
-Zebra:http://radagast.se/othello/
・評価関数
-必勝読み:最終局面で自分の勝敗を評価
-着手可能手数:自分が打てるマスの数
・序盤・中盤の評価関数
・終盤の必勝読み
・終盤の完全読み
序盤・中盤の
評価関数
終盤
必勝読み
完全読み
・着手可能手数、確定石
・C打ち、X打ち判定
・ウィング
・山
・開放度
ズム[1]より
※リバーシのアルゴリ
・着手可能手数:着手可能手数では自分が打てる石が
多ければ多い程高評価である。これは、戦略が膨らむ
からである
・確定石:ゲーム終了まで二度と裏返らない石のことをいう。確
定石は有利な局面を作るためには非常に重要で、角を取れば
有利に対戦を進められるという一般的見解はこの確定石である
ことが大きな意味を持つ。周囲に空きマスがない状態で、連接
する石が裏返らない時になる。
・角の隣と斜め隣の事を言う。一般的に不利と言われて
いる場所である。
・ウィングは一般的に不利な形と言われているマイナス
評価である
・ウィングは一般的に不利な形と言われているマイナス
評価である
・山とは一般的に有利な形と言われている。
左は山の形。右側は山の有利な例。次が黒番の時、白は必ず隅を取
れる
・自分が打った手によって裏返る石の周辺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
終盤
序盤・中盤の
評価関数
・必勝読み
・完全読み
必勝読み
完全読み
・終盤の評価関数の特徴
-終盤では単に勝敗や自分の取れる石の数が多い
か少ないかを見ればよい
・完全読み:color*(count(BLACK) – count(WHITE))
・必勝読み:完全読みと違いWIN=1,LOSE=1,DRAW=0しか見ず石の数を無視するため、比較演算
子を用いる時に計算量を軽くできる
・SSAI
・MSAI
・SSAI:本研究で用いたJava言語によるシングルスレッドプ
ログラミングによるリバーシ
評価関数
決定
探索
評価
SSAI
・クラスAIで探索処理
・評価関数決定:
ー序盤・中盤の評価関数
ー終盤の必勝読み
-終盤の完全読み
・探索:
ーα-β法による再起処理
・MSAI:本研究に用いたJava言語によるマルチスレッド
プログラミングによるリバーシ
評価関数
決定
探索
評価
MSAI
・クラスAIとクラスMultiAIで探索
・評価関数決定:
-序盤・中盤の評価関数
-終盤の必勝読み
-終盤の完全読み
・探索:
-α-β法による再起処理
-候補手の分だけサブスレッド作成
枝木一つに対し1スレッド
実験環境
実験内容
先読み設定数
Let'sNote,VT64の実験結果
・Let'sNote:
ープロセッサ:Intel Core2Duo L7800 2コア 2GHz
-メモリ(RAM):2GB
-OS:WindowsVista
-Java実行環境:eclipse
48コア
・VT64:
-プロセッサ:(AMD Opteron 1.9GHz 12コア)*4
-メモリ(RAM):128GB
-OS:CentOS
・対戦方法:SSAI,MSAIをランダムなAIと実験環境下で
先攻、後攻分けて対戦させる
・実行:ある先読み設定数で100回実行
・処理時間の見方:ある先読み設定数で100回実行し
た時の合計実行時間を見る
・
VT64
※処理時間は秒
Let'sNote
VT64
※処理時間は秒
Let'sNote
・MSAIで見た時、先の実験ではLet'sNoteとVT64は処
理時間に差がでなかった
・eclipseによりJavaプログラムが高速動作していた可
能性があることから、MSAIに限定してターミナルによる
実験を行う。
・
※処理時間は秒
・マルチスレッドプログラミングにより、探索による処理
時間を大幅に短縮することができた
・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