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