vsOtha version 13.06
2004/08/13
xhl
vsOtha version 13.06
•
•
•
•
•
I 概要
II 探索アルゴリズム
III 評価関数
IV その他
V パフォーマンス
I 概要
•
•
•
•
目次
プログラム構成
ステージ
文献等
目次
• 探索アルゴリズム
–
–
–
–
–
α-β法
Move Ordering
置換表(Transposition Table)
反復深化法(Iterative Deepening)
ProbCutによる前向き枝刈り
• 評価関数
– 狐Original
– 狐General
プログラム構成
• 主に探索部と評価関数部で構成。
• 両者は分離されている。
• 盤の実装などは“一応”切り離されているのでオ
セロ以外にも対応できる。
• 実質C言語。
評価函数のみC++でクラス化されている。
– 某氏「(拡張子を見て)あ、xhl氏がC++書いてる」
私「拡張子が.cppなだけのCだったりして……」
• 機械生成、不使用コードも入れて15000行程度?
ステージ
• オセロの60手を4手×15のステージに分割。
stage 0 ～ stage 14。
• 評価函数他、便利なのでいろいろ使っている。
文献等
• ProbCutと狐系評価関数についてはBuro氏の論
文を、置換表についてはオセ7のソースコードを、
またネット上の諸情報を反復深化法その他につ
いて参考にした。
• 終盤探索速度を上げるのは楽しいですね。(時間
食うと空しくもなるが……)
II 探索アルゴリズム
• ゲームを通じて共通の探索ルーチン。
パラメータを変化させることで序中盤～終盤に対
応。
• α-β法
• Move Ordering
• 置換表(Transposition Table)
• 反復深化法(Iterative Deepening)
• ProbCutによる前向き枝刈り
• 終盤解析
Move Ordering - 概要
• 「良さそうな手」から先読みすることによってα-βを
効率化する手法。
Move Ordering - 実装
• 古典的評価関数による評価値によりソート。
また、置換表にある盤面を優先して探索。
• a = (隅にある自石の数) - (隅にある相手石の数)
b = (Xにある自石の数) - (Xにある相手石の数)
c = 相手の着手可能数
• 序中盤: 評価値 = 50a - 10b - c
• 終盤 : 評価値 = 2a - b - 3c
Move Ordering - 実装
• 終盤を分けることで終盤完全読みが40%くらい?
高速化。
• 終盤(空きが17ヶ所以下)は速さ優先探索
(Fastest-First Heuristic)の変種。
• 純粋な速さ優先探索にすると探索が遅くなる盤
面が存在したため、平均的に速くなるよう a, b の
項を入れて補正を図った。
Move Ordering - 実装
• Move Orderingにはある程度のオーバーヘッドが
かかる。
→ゲーム木全体で実行すると遅くなる。
• ゲーム木の下の方ではオーバーヘッドに見合う
だけの高速化が見込めないので、Move
Orderingをある深さ(depth_MO)より上に限定した。
Transposition Table - 概要
• 既に探索したことのある局面をハッシュなどに保
持し、同じ盤面が再度出現した場合に再度探索
せずに済ませる手法。
Transposition Table - 実装
• 盤面と共に、評価値の最大値・最小値、及び
Move Orderingで使用するための評価値を格納。
• 盤面は16バイトに圧縮して格納。
• 最大値・最小値から判断して、確実にαorβカット
される場合には即カットできる。
• 実装には普通のChained Hashを使用した。
Transposition Table - 実装
• Move Ordering同様、ゲーム木の全てで置換表
を有効にすると遅くなり、また膨大なメモリが必要
になる。
→置換表に登録する盤面を、ある深さ
(depth_TT)より上に限定。
Transposition Table - 実装
• おまけ: 2つめの置換表
Chained Hashよりも高速で動作する置換表を、
depth_TTより下でdepth_TT2(<depth_TT)より上
の領域で動作させる。
• 具体的には開番地法のハッシュにし、衝突が起
きた場合には古い要素に新しい要素を上書きす
る。(別に律儀に全ての盤面を保持しなくてもよい
ので。Full-Associative Cache?)
Iterative Deepening - 概要
• まず4手読みして、次に5手読み、6手読み……と
順々に探索を深くしていく手法。
• 置換表と組み合せて使うことで効果的に。
n手読む→置換表のエントリにn手読みの時の評
価値を格納→n+1手読む時のMove Orderingに
その評価値を利用。
Move Ordering同様、よさげな手から順に読むこ
とを助ける。
• 探索時間制限を設けることが容易。
パラメータ
• パラメータを換えてn局面平均で速度を出して実
験的に決定した。
• 序中盤: depth_MO = depth_TT = 3
• 終盤:
• depth
depth_MO depth_TT
• 1～7
MO無し
置換表無し
• 8～13
7～9
置換表無し
• 14～25 9～11
10～11
パラメータ
• 時間制限:
stageごとに分割。順に
2[sec], 5, 10, 20, 20, 20, 10, 10, 5, 5, 完全読み
効果
•
完全18手読み 完全20手読み 中盤10手読み(stage 5)
•
64.55sec/132.42M
511.02sec/30.63M
• MO 2.46sec/ 4.65M 23.53sec/43.84M 34.02sec/ 1.76M
• TT 2.06sec/ 3.73M 17.84sec/31.09M 30.45sec/ 1.49M
• ID 1.20sec/ 1.75M 8.18sec/12.11M 11.78sec/ 0.62M
• 置換表(TT)は導入時はかなり効果大だった(3倍くらいとか)はずなの
だが……?
ProbCut - 概要
• M. Buro氏による前向き枝刈り手法。
• d > d’ (d = 8, d’ = 4 とか)
• d手先読みした場合の評価値vと
d’手先読みした場合の評価値v’とには、
単純な線形相関がある(Buro氏の論文及び
vsOthaの場合はそうだった)。
• →v’からvを予測できる。
• →d手先読みする場合にまずd’手先読みし、αβ
の範囲外になりそうだったらカットする。
ProbCut - 概要
• 利点及び欠点(前向き枝狩り共通)
– 利点: 探索が高速になる。
– 欠点: 切ってはいけない枝を刈ることもあるので結果
はやや不正確。
• 欠点をそれを上回る利点でカバーできるか。
ProbCut - 実装
• 必要なパラメータ: a, b, σ
vの予測値 = v’ * a + b
vの予測誤差(標準偏差) = σ
• ゲームステージ依存、思考ルーチン依存。
• 棋譜から2,000局面取り出して、d手先読みの評
価値とd’手先読みの評価値を算出し、回帰分析
によりa, b, σを算出。
ProbCut - 効果
•
•
•
•
•
•
Stage
3
5
7
9
11
SpeedUp
1.91
2.08
2.52
1.84
1.33
SameMove
100%
98%
94%
98%
100%
SameValue
98%
92%
86%
98%
98%
• Buro論文みたいに「6.6倍」などにはならなかった。
終盤解析 - 概要
• 例えば20手完全読みの場合、狐ルーチンとかで
10手ぐらい反復深化法で読んでから20手完全読
みを行う。
終盤解析 - 高速化
• 1. Leaf数を少なくするか。
• 2. 速度(Leaf/sec)を上げるか。→単純最適化
終盤解析 - Leaf削減
• アルゴリズムでSignificant/Importantなのは
• Move Ordering ← 並び替え方法の改良
• 置換表(メモリを大量に使って25手とか読むとか
なり効く)
• 反復深化法(最初の反復深化の良し悪しでその
後の完全読みのLeaf数に影響する)
←良い評価函数。
精度が上がるとLeaf数は下がる
終盤解析 - Leaf削減
• パラメータ評価による改善
• 小技いろいろ
• 最終的にはいくつかの局面or棋譜の10個盤面平
均とかで速度/Leaf数を出して評価することに。
終盤解析 - 単純最適化
• 後述。
III 評価関数
• 狐Original
• 狐General
狐Original
• Buro氏の論文
“Experiments with Multi-ProbCut and a New
High-Quality Evaluation Function for Othello”
を参考にして作ったルーチン。
• 英語が分からなかったことと、線形ではどうして
も良い値が出なかったことから、パターンを流用
してニューラルネットワーク(3層パーセプトロン)
にした。
狐Original
• 中間ユニット8個の3層パーセプトロン。
• ロジスティック函数使用。
• 入力:
–
–
–
–
–
着手可能数
空きの数の偶奇
石差
隅、Xなどにある石の数
パターン(LOGISTELLOと同じ) : 出現回数を値とする
• hori/vert 2-4, diag4-8, edge+2X, corner 2*5, corner 3*3
狐Original
• 学習
– 誤差逆伝播アルゴリズム。
– 浮動小数点で学習してその後整数に変換。
– NECのFTPサイトにあった棋譜
ftp://ftp.nj.nec.com/pub/igord/IOS/archive/??E4.gam.bz
のうち、最後まで指された約31万を用いた。
狐General
• 狐Originalの後継ルーチン。
• 基本は狐Originalと同じ。いろいろ整理したので
狐Originalよりプログラマにとっては扱いやすい。
←強さとは無関係。
• 学習法を工夫することで、棋譜が無くても一応動
作できる。(棋譜ありに比べると劣るらしいが)
←今回は無関係。
• 入力に微変更あり。
狐General
• 棋譜データの修正←今回のメイン
– 実は棋譜データの終盤解析をすると結構間違った手
を打っている。
(2個空きで間違えて負けた棋譜なんてのもあった)
– 棋譜データの目的は、完全読みできないような中盤の
局面に対して「この局面は××石勝ちです」というでき
るだけ正確なデータを提供することにあると考えた。
– 各棋譜の終盤20手ぐらいを終盤解析して正確な石差
を算出し、その石差を用いて学習。
– 時間不足(CPUもプログラマも)のため、やや手を抜く。
狐General - 誤差の改善
狐General - 決定係数の改善
狐General - 勝率の改善
• 5分制限、()内はProbCutの有無。
• 狐(無) vs 狐Org(無) 12勝0分4敗 +146
• 狐(有) vs 狐Org(無) 13勝1分2敗 +118
IV その他の実装
• 盤の実装
• 地道な最適化
• 終盤解析のとてもこまごましたこと
盤の実装
• 8×8 = 64バイトの配列。
0 = 黒, 1 = 白, 2 = 空き。
• 石を打つ場合には盤面をコピー。
• 石を打つルーチン、着手可能数を数えるルーチ
ンは展開してある。
ex) switch( pos ){
case a1: if( a2が相手 and
(a3が自分 or (a3が相手 and (a4が...
地道な最適化
• プログラマの時間を食うのであまり意味が無い
気もするがついやってしまった最適化。
– 要らない条件分岐類を剥ぎ取る。+10%。
– 空きマスのlistを保持し、先読み時にはそのリスト内の
マスについてのみループを回して処理。+30%。
– 最終1手～3手読みのループを展開。+25%。
– その他いろいろ単純最適化。+60%。
V パフォーマンス
• 探索速度(Leaf per sec)
• 5分制限時の先読み手数
• 終盤完全読み能力
探索速度(Leaf per sec)
• Celeron 2.6GHzで測定。学科ノートでも同程度。
• 序中盤(狐ルーチンの速度) : 50KLeaf/sec
• 終盤完全 : 1500KLeaf/sec
先読み手数
終盤完全読み能力
•
•
•
•
•
棋譜から10局面選んで平均を取った。
depth
sec
Mleaf
18
1.13
1.75
20
7.89
12.14
24
168.70
283.56
© Copyright 2024 ExpyDoc
