コンピュータオセロ ～人類を超えた知能～ Is2004er • 1997年ついにLogistelloが世界チャンピオン 村上7段を破る 1. オセロ大会 2. 基本のおさらい 3. プログラム 1. 評価関数 2. 探索ルーチン 3. ボード実装 4. 実演 1. オセロ大会 2. 基本のおさらい 3. プログラム 1. 評価関数 2. 探索ルーチン 3. ボード実装 4. 実演 オセロ大会 • 期間 – 昨年の夏 – ICPCのあと、実装力を補強するために開催 • 参加者 – IS2004er – 経験者リーグと初心者リーグ、のべ8人 オセロ大会・結果 • 1位: vsOtha（林崎） • 2位: Thell（藤田） • 3位: Neothec（大倉） • 4位: Oxelon（海野） 各参加者での実装上の違い 大会後もさらなる改良を目指したり 1. オセロ大会 2. 基本のおさらい 3. プログラム 1. 評価関数 2. 探索ルーチン 3. ボード実装 4. 実演 オセロのルール • 盤面 – 8x8の盤面（知ってますね） – 最初の配置は決まってますよ • 盤面箇所の基本用語 – ず（林崎） 基本的な仕組み • 完全情報二人零和ゲーム • ゲーム木探索＋評価関数 – 局面を深読み – 末端で評価関数によって評価値を与える – Min-Max原理 探索空間 • 完全探索できそうな気がしますが・・・ • 1020くらいと仮定 – ラスト30手が1010くらい • 1GHz、100clockで1局面を生成できるCPU が100万個で… 1０万年 ゲーム木探索 • ず（藤田） 強くするには • 高精度な評価関数 – 勝ち負けの予想が間違っていては、正しい比較 ができない • より深い手数を読む – 深く読んだ方が強くなることが知られている – 終盤なら完全探索も可能 • 深読みのためには・・・ – 不要な部分は探索しない枝刈り – 高速に探索できるような実装 1. オセロ大会 2. 基本のおさらい 3. プログラム 1. 評価関数 2. 探索ルーチン 3. ボード実装 4. 実演 プログラムの構成 • • • • 評価関数 探索ルーチンと枝刈り ボード実装戦略 終盤探索用の最適化 1. オセロ大会 2. 基本のおさらい 3. プログラム 1. 評価関数 2. 探索ルーチン 3. ボード実装 4. 実演 評価関数とは？ • 評価値 – 局面の善し悪しを数値化したもの • 評価関数 – 局面から評価値を計算する関数 – より有利な局面には高い数値、より不利な局面に は低い数値を与える • いかにして精度のよい評価関数を作るかが 課題！ 評価関数と歴史 • IAGO(’82) – 手動チューニングによる • BILL(’90) – 初めてパターン（後述）を利用 – 重みはハンドチューニング • Logistello - 1(’94) – パターンのみによる評価 – 統計＋ハンドチューニング • Logistello - 2(’97) – 線形回帰による全パラメータ自動学習 ハ ン ド チ ュ ー ニ ン グ か ら 統 計 手 法 へ 歴史的な2つの流れ • 統計手法 • パターン 統計手法 • ハンドチューニングから統計手法へ – コンピュータの性能向上にあわせるように、統計 手法へと移行 – 完全に統計のみで性能がでるのは例外的らしい • 将棋はハンドチューニング（らしいby激指） • Logistello(Michael Buro)の出現 – 統計手法とパターンによる石差予想 – 棋譜データから最終的な石差を予想する – これ以降、主流に パターン • 盤面表現は全部で38x8 – 大きすぎて扱いきれない • 盤面を小さな10マスくらいのパターンに分割 – ず（海野） – たとえば、横1列の並びかたを3進法で符号化 – |○● ●○● ○| 210212013126 – 310ならメモリに十分はいる Logistelloパターン • 盤面を以下のようなパターンに分割 勝率予想と石差予想 • 勝率予想 – 評価関数で勝率を予想 • Turtle • 石差予想 – 評価関数で石差を予想 • Logistello 石差予想とパターン • パターンから石差を予想 – 各パターンが石差に寄与しているという仮定 – その合計で石差を予想する • 棋譜データから学習 – 回帰計算 – 最急降下法 学習用棋譜 • 棋譜とは？ – 「初手から順に着手を記した対戦記録」 – (局面, 結果)のペアとしてみる – これを使ってある局面から結果を予想できないか • 学習には大量かつ精度の良い棋譜が必要 • 棋譜の精度は評価関数の精度に影響 • vsOtha（林崎） 50万棋譜計画 • オセロ大会終了後、棋譜を生成する計画が 持ち上がる • Logistelloの棋譜は意外とめちゃくちゃな手が 多い • 10手、20手、30手、40手目それぞれから初 めて、vsOtha vs Thell • 地下のクラスタで6ヶ月間 • 合計300万の精度の良い棋譜を得られた 1. オセロ大会 2. 基本のおさらい 3. プログラム 1. 評価関数 2. 探索ルーチン 3. ボード実装 4. 実演 探索ルーチン • 単純なMin-Max探索では探索空間が広すぎ る – より有効な枝刈り戦略が知られている • αβ枝刈り – Move ordering • NegaScout/PVS • Mtd(f) • 前向き枝刈り αβ枝刈り • 最も基本となる枝刈り戦略 • ず NegaScout/PVS Mtd(f) 探索アルゴリズムの比較 前向き枝刈り • （おーくら） Move ordering戦略 • 以上のようなαβ系枝刈りでは、先に有利な局面を探 索した方が効率よく枝刈りできる – 探索順を決定することをMove Orderingという • Move Orderingにも実行時間と効率のトレードオフ でいくつかの戦略が存在 • 評価関数 • 古典評価関数 • しない 評価関数によるMove Ordering • • • • 評価値を与えるための評価関数を使う 高い精度が得られることが期待できる 反面、他の手法よりも時間がかかる かかった時間に見合う枝刈りができるかがカ ギ 古典評価関数によるMove Ordering • 古典的な評価関数を利用する • 古典とは？ – たとえば、隅に置けるか否か、着手可能箇所が いくつあるかといったより単純な特徴から計算 – 各パターンを足しあわせる現代評価関数より軽 い • 枝刈り性能より計算速度を重視 Move Orderingしない • しないとは！？ • 最速であるかわりに枝刈り性能は著しく落ち る • これって戦略？ – 残り手数が少なくなると、枝刈りしても意味がない – 残り何手から「しない」のかが重要 Move Ordering戦略の比較 1. オセロ大会 2. 基本のおさらい 3. プログラム 1. 評価関数 2. 探索ルーチン 3. ボード実装 4. 実演 ボードは大事 • 最も実装に個性が出る • 実装方法によって探索速度に大きな差が生 まれる • ボードに必要な機能 – 着手（move）：石を置いて裏返す – 着手可能箇所数の数え上げ（mobility）：置ける 箇所をカウント – etc. ボード実装 • 様々なトレードオフ • 差分 vs コピー • 主な実装方針 – Naïve board – Bitboard – Index board • ほとんどのプログラムはこの3つに分類できる 差分 vs コピー • 探索時に着手前のボードに戻す必要 – 着手情報を差分としてとっておく – ボードのコピーをとっておく • どちらがいいか？ – 全部コピーするのはコストがかかる（か？） – 差分の方が容量は少ないが処理が煩雑（か？） • ボード実装との相性 Naïve Board • ボード盤面を整数の配列で表現 • char board[8][8]; • 一番簡単な実装 Bitboard • 石のある位置のビットを立てた2つの整数で 表現 • ず（うんの） Bitboardだと何がうれしいの？ • 着手可能箇所の列挙が高速 Index Board • インデックス – 各辺の石の並びを一意に符号化したもの – ず（藤田） • すべての辺のインデックス集合で表す – ず（藤田） Index Boardだと何がうれしいの？ • 評価関数が高速 – そもそも評価関数を高速にするための工夫 ボード実装の比較(1) • ひょう（林崎） ボード実装の比較(2) • グラフ（林崎） 終盤解析 • FFO – French Federation of Othello – Zebra(Gunnar Andersson)が自身の性能を自慢 する目的で広く公開されている、オセロの終盤解 析テストセット – 一番空きますの少ないFFO#40でも、20マス空き • Zebra – 現在最強のオセロプログラムの一つ – 終盤探索は最速 オセロ大会直後 • FFO#40 – FFO test setの中で最も簡単な盤面 • 圧倒的な速度差 – Zebra: 4.2sec – vsOtha: 10sec – Thell: 900sec – Oxelon: 一晩たっても終わらず 高速化の日々 • ボード実装の見直し • Move orderingの見直し • 置換表の見直し 日に日に速くなるが何かが足りない・・・ プログラミングの常識 • 似たような処理は一つの関数にまとめましょ う • 定数が違うだけの関数は作らないようにしま しょう 忘れてください • 特定の状況に依存しにくいようなソースを • ソースは簡潔に、保守しやすいように • 速度よりわかり安さ優先 オセロプログラミングの常識 • 似たような処理でも高速ならば個別に用意 • 可能な限り変数は定数に置き換えて展開す る • 8x8のボードサイズにべったり依存 • ソースは煩雑でも、速度優先 • わかりやすさより速度優先 いわゆる「暴挙」 探索における暴挙 • 空きマスが一つとわかれば、端からたどる必 要はない • 最後の1手は実際に裏返す必要はない • for文が消える、空所表がいらなくなる • こーど（） 着手における暴挙 • 引数を渡す代わりに、呼び出す関数をかえる – move(x, y); move[x][y](); – A1に打つ関数、A2に打つ関数、・・・を用意 – スクリプトorプリプロセッサで展開 • 着手箇所が特定されると何がうれしいのか？ – どちらの方向に何個調べればよいのか特定できる – bitboardの場合、チェックと書き換えが定数で行えるよう になって効果が大きい – 場所が固定されてもIndex boardでは効果が薄い 暴挙の効果 実演 • 誰か対戦したい人はいますか？
© Copyright 2024 ExpyDoc
