競技プログラマー向け将棋AI開発入門 - nodchipのTopCoder日記 - TopCoder部 http://topcoder.g.hatena.ne.jp/nodchip/20151224/1450969207
スマホ版やねうら＋elmo公開
http://shogidroid.siganus.com/engines.html
競技プログラマー向け将棋AI開発入門 - nodchipのTopCoder日記 - TopCoder部
http://topcoder.g.hatena.ne.jp/nodchip/20151224/14509692072015-12-24
■ 競技プログラマー向け将棋AI開発入門 
はじめに
この記事はCompetitive Programming Advent Calendar 2015 25日目の記事として書かれたものです。
内容は競技プログラミング経験者であるnodchipが将棋のAIの開発を通して得た知識と経験をまとめたものです。
まずは動かしてみましょう
一から将棋プログラムを作るのは難しいと思います。まずは既存の将棋AIを動かしてみて、どんな感じなのか感覚を掴んでみましょう。無料で手に入る主な将棋AIは以下の通りです。
- Bonanza - The Computer Shogi Program http://www.geocities.jp/bonanza_shogi/
- GPSshogi - PukiWiki http://gps.tanaka.ecc.u-tokyo.ac.jp/gpsshogi/
- Apery http://hiraokatakuya.github.io/apery/
- nodchip/tanuki-bin https://github.com/nodchip/tanuki-bin
- 上記のソフトをnodchipが改造した物です。
これらのソフトはUSI(Universal Shogi Interface)プロトコルに対応した将棋AIです。
ネット上にはUSIプロトコルに対応したVisualizerがいくつか公開されています。nodchipはVisualizerとして『将棋所』を使用しています。
- 将棋GUIソフト「将棋所」のページ http://www.geocities.jp/shogidokoro/
将棋AIを適切なフォルダに解凍したあと、将棋所→対局→エンジン管理から登録し、対局→対局で対局することができます。AI同士を対戦させるのも良いですし、AIに挑んでボッコボコにされるのも良いかもしれません。
ソースコードをコンパイルしてみましょう
次にソースコードをダウンロードしてコンパイルしてみましょう。Windowsの場合はVisual Studio 2015 Community EditionやMinGW-w64+MSYS、Linuxの場合はgccがあればコンパイルすることができると思います。
tanuki-の場合
- ソースコードをgithubよりcloneしてくる
- Visual Studio 2015 Community Editionをインストールする
- tanuki-/tanuki-.slnを開く
- ビルドボタンを押す
これだけです。
将棋ソフトのコンポーネント
- 盤面データ構造
- 局面の状況を保持するデータ構造。強いソフトはBitBoardを用いた高速・省メモリなデータ構造を使っていることが多い。BitBoardについては後述。
- 指し手生成
- ある局面が与えられた時に、手番のプレイヤーが指すことができる合法手を列挙するルーチン。これが高速だと単位時間に読める局面が多くなる。一方、実際に指されそうな手から生成したほうが、ゲーム木探索で枝刈りが多く起こるようになり、探索効率が上がる。高速化と指し手の生成手順は、多分トレード・オフの関係にあると思う。
- 盤面評価
- 盤面探索
- ゲーム木を探索していくルーチン。
- 置換表
- 定跡データベース
- USIプロトコル
ゲームAI独特のアルゴリズムを覚えましょう
コンピューター将棋では競技プログラミング界隈であまり目にしないアルゴリズムが多いです。以下にそれらの一部を挙げます。
- Minimax
- 局面を評価する関数が与えられ、自分と相手プレイヤーがある局面からN手先の評価値を互いに最大化しようとした時、自分の評価値を高めるにはどの手を打てばよいかを求めるアルゴリズム。
- https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95
- http://www.geocities.jp/m_hiroi/light/pyalgo24.html
- https://chessprogramming.wikispaces.com/Minimax
- Negamax
- Alpha-Beta
- 探索の途中、それまでの評価値の最大値以下or最小値以上の値が出現した時に枝刈りする手法。Minimaxに比べ探索局面数を大幅に減らすことができる。
- 探索する評価値の範囲の下限をalpha値、上限をbeta値と言う
- https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%83%95%E3%82%A1%E3%83%BB%E3%83%99%E3%83%BC%E3%82%BF%E6%B3%95
- http://www.geocities.jp/m_hiroi/light/pyalgo24.html
- https://chessprogramming.wikispaces.com/Alpha-Beta
- Nega alpha
- Fail-Soft Alpha-Beta
- Alpha-betaの書き方の一つ。枝刈りをするときにbetaの値以上になった評価値を返すようにしておく。beta値を返すのはFail-Hard Alpha-betaと呼ばれている。
- https://ja.wikipedia.org/wiki/Negascout
- http://www.geocities.jp/m_hiroi/light/pyalgo25.html
- https://chessprogramming.wikispaces.com/Alpha-Beta
- Null Window Search
- Negascout
- Alpha-beta探索であるノードを探索する際、探索窓を(alpha,alpha+1)として探索して、alphaの値を超えそうなときだけ正しい探索窓を使って探索するようにする。探索盤面数がそこそこ減る。
- https://ja.wikipedia.org/wiki/Negascout
- http://www.geocities.jp/m_hiroi/light/pyalgo25.html
- Principal Variation Search
- Negascoutと同時期に生まれた類似品。こちらのほうがよく使われている。Principal Variation(PV)は最善と考えられる読み筋のこと。
- https://ja.wikipedia.org/wiki/Negascout
- https://chessprogramming.wikispaces.com/Principal+Variation+Search
- Principal Variation Splitting
- Depth First Search (DFS)
- 言わずと知れた深さ優先探索
- Breadth First Search (BFS)
- こちらも言わずと知れた幅優先探索
- Iterative Deepning
- 反復深化法
- 深さ1まで、深さ2までDFS、深さ3までDFS、・・・と1手ずつ深さの上限を増やしながらDFSを行うこと。
- コンピューター将棋ではDFSではなく、枝刈り付き探索を用いる
- それぞれの深さ制限での探索をイテレーションと言う。
- 思考時間が制限されている場合、時間が来るまで深さを増やしながら探索を繰り返す。
- ひとつ前のイテレーションのPVを次のイテレーションで最初に探索すると、探索局面数が減る場合がある。これは、ひとつ前のイテレーションのPVが次のイテレーションのPVの近似とみなすことができ、alpha/betaの値が早めに狭まるため。
- https://ja.wikipedia.org/wiki/%E5%8F%8D%E5%BE%A9%E6%B7%B1%E5%8C%96%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2
- http://www.geocities.jp/m_hiroi/light/pyalgo26.html
- https://chessprogramming.wikispaces.com/Iterative+Deepening
- Lazy SMP
- 並列化手法の一つ。
- メインスレッドは深さ1の探索、深さ2、深さ3、・・・と通常の反復深化法を行う。
- ヘルパースレッドはメインスレッドと平行して、メインスレッドより大きい深さで投機的に探索を行う。
- 各スレッドの探索結果は置換表(後述)に保存しておく。
- ヘルパースレッドが探索の結果を置換表にメモするので、メインスレッドの探索がキャッシュヒットしやすくなり、結果的に探索が早く終わるのだと思う。
- 実際に返す手はメインスレッド/ヘルパースレッドの探索結果の中で一番良い物。
- http://www.talkchess.com/forum/viewtopic.php?t=55188
- http://www.talkchess.com/forum/viewtopic.php?t=55170&start=11
- Transposition Table
- 置換表と呼ばれる
- ゲーム木の各ノードの探索結果のキャッシュ・メモ。
- キーは盤面のZobristハッシュ(後述)、探索の深さ、探索窓の上限/下限などの組み合わせ。
- https://ja.wikipedia.org/wiki/MTD-f
- http://www.geocities.jp/m_hiroi/light/pyalgo26.html
- https://chessprogramming.wikispaces.com/Transposition+Table
- http://yaneuraou.yaneu.com/2015/12/17/%E9%80%A3%E8%BC%89%E3%82%84%E3%81%AD%E3%81%86%E3%82%89%E7%8E%8Bmini%E3%81%A7%E9%81%8A%E3%81%BC%E3%81%86%EF%BC%818%E6%97%A5%E7%9B%AE/
- Zobristハッシュ
- 局面のハッシュ値を計算するための方法の一つ。
- ある駒があるマスに置かれているという状態/手駒一つ/手番等に対してランダムな値を割り当てる。
- ある局面のハッシュは、その局面に存在する全ての状態の値のxorや和で表す。
- コンピューター将棋の場合は和を使うことが多いらしい。これは手駒のハッシュ値の計算がしやすくなるため。
- https://en.wikipedia.org/wiki/Zobrist_hashing
- https://chessprogramming.wikispaces.com/Zobrist+Hashing
- http://yaneuraou.yaneu.com/2015/12/16/%E9%80%A3%E8%BC%89%E3%82%84%E3%81%AD%E3%81%86%E3%82%89%E7%8E%8Bmini%E3%81%A7%E9%81%8A%E3%81%BC%E3%81%86%EF%BC%817%E6%97%A5%E7%9B%AE/
- Aspiration Window
- Razoring
- 探索中、局面の評価値がAlpha値以下だった場合は枝刈りするというもの。亜種がいっぱいあるらしい。
- https://chessprogramming.wikispaces.com/Razoring
- Futility pruning
- ゲーム木の末端付近のノードで、これ以上Alpha値が上がりそうにないノードを枝刈りするというもの。これも亜種がいっぱいあるらしい。
- https://chessprogramming.wikispaces.com/Futility+pruning
- Null Move Pruning
- 1回パスしてもbetaカットが起こるほど評価値が高い場合は枝刈り。って書いてるけどちゃんと理解していない。
- https://chessprogramming.wikispaces.com/Null+Move+Pruning
- Quiescence Search
- ゲーム木探索の終端ノードにおいて、駒の取り合いだけ追加で探索して、数手先で即負けたりしないよう調べること。水平線効果を抑えられるらしい。
- https://chessprogramming.wikispaces.com/Quiescence+Search
- Static Exchange Evaluation
- あるマスでのコマの取り合いが終わったあとの評価値を計算すること。
- https://chessprogramming.wikispaces.com/Static+Exchange+Evaluation
- ProbCut
- 浅く探索したときの評価値が悪すぎるノードを枝刈りすること。
- https://chessprogramming.wikispaces.com/ProbCut
- Late Move Reductions
- Fail-lowしたノード付近のノードは探索する深さを浅くするというもの。
- https://chessprogramming.wikispaces.com/Late+Move+Reductions
- ボナンザメソッド
- 全幅探索
- BitBoard
- 盤面の状況をビット列を使って表現するデータ構造。コマが置かれているマスに相当するビットを1、それ以外を0とする。駒の種類数だけビット列を用意してあげる必要がある。xhl_kogitsuneさんの天使の階段ビットベクトル解法を思い出すのは私だけだろうか？
- https://chessprogramming.wikispaces.com/Bitboards
- 3駒関係
- KPP次元下げ
- KPA次元下げ
改造してみましょう
気になったところを改造してみましょう。プロファイラを使ってホットスポットを特定し、定数倍の高速化をかけるもよいでしょう。探索ルーチンの枝刈りパラメーターを調整するのも良いでしょう。機械学習ルーチンにナウなヤングにバカウケの最先端の学習アルゴリズムを導入するのも良いと思います。
例えばtanuki-がAperyに対して施した改造は以下のとおりです。
- 定石データベースを変更し、インターネット上で入手可能なプロの棋譜約4万局と、floodgate上の対戦の中でレーティングがGPSXeon 12コア以上のAIが含まれた対戦の棋譜から作成しなおしました。
- 定跡選択ルーチンを変更し、データベース作成時は指し手の評価は行わず、本番中に軽い探索を行い、定跡データベースから選択するようにしました。
- 盤面評価関数のうちKKPをVGATHERDD命令を使って計算するようにしました。
- volatile変数をstd::atomic<>へ変更しました。
- static const変数をconstexprへ変更しました。
- 置換表のEntrySizeを1に変更しました。
- 置換表・評価値キャッシュの使用率・ヒット率・破棄率を出力できるようにしました。
- コンパイラをclang-3.7に変更しました。
- Aspiration Window Searchのwindowの広げ方をStockfish6のものに近づけました。
- 思考時間を変更し、序盤を短め、中盤を長めにしています。
- KPPの重みを保持する3次元配列に適当なパディングを入れました。
自己対戦をしてみましょう
将棋所には自己対戦機能が実装されています。これを使って、昔のプログラムに比べて今のプログラムがどれくらい強くなったか確認してみましょう。
まず「対局」→「エンジン管理」から対戦させたいAIを登録します。次に「対局」→「対局」から先手と後手のAIを選択しましょう。残りのオプションをお好みで設定したら自己対戦開始です。おすすめの設定は以下のとおりです。
- 手数が256手に達したら引き分けにする
- 時間切れを切れ負けにする オン
- 連続対局 オン
- 連続対局数 9999
- 自動棋譜保存 オン
対局数が少ないとランダム要素のせいで誤差が大きくなり、どれくらい強くなったのか正確に測ることができません。以下は「コンピュータ囲碁 ―モンテカルロ法の理論と実践―」に書かれている、対戦数と有意差の関係です。
| 試合数 | 有意に強くなったといえる勝率(95%) | 有意に強くなったといえる勝率(99%) |
| 10 | 8勝2敗 | 9勝1敗 |
| 20 | 14勝6敗 | 16勝4敗 |
| 50 | 31勝19敗 | 34勝16敗 |
| 100 | 59勝41敗 | 62勝38敗 |
| 200 | 112勝88敗 | 117勝83敗 |
| 500 | 269勝231敗 | 277勝223敗 |
| 1000 | 527勝473敗 | 537勝463敗 |
他のAIと対戦させてみましょう
AIが十分に強くなったらネット上で他のAIと対戦させてみましょう。コンピュータ将棋対局場「floodgate」は日本で最も有名なコンピューター将棋ソフト同士の対局場の一つです。プロ棋士の一部も棋譜を参考にしているとのことです。
将棋所からfloodgateに参戦するためには「対局」→「サーバ通信対局(floodgate)」から対戦させたいAIを選び、ログイン名にランキングに表示されるAI名、パスワードに任意の文字列を入力してOKボタンを押せばよいです。
大会に出場してみましょう
現在定期的に開催されている大会は以下のとおりです。
世界コンピュータ将棋選手権は毎年5月のゴールデンウィークに開催されるイベントです。世界と名前が付いている通り、海外からの参加者もいます。
電王トーナメントは株式外社ドワンゴが主催するイベントで、不定期で開催されています。第3回電王トーナメントでは、優勝するとプロ棋士の代表と対戦することができました。
まとめ
競技プログラミング経験者nodchipが将棋のAIの開発を行った経験を元に、将棋のAIの開発に必要な雑多な知識をまとめました。あまりまとまっていない記事で恐縮です…。
この記事を呼んで将棋のAIの開発を始めてくださる競技プログラマーが一人でも増えたら幸いです。
リンク
- chessprogramming - home https://chessprogramming.wikispaces.com/
- コンピュータ将棋の知識 http://misakirara.s296.xrea.com/misaki/words.html
- official-stockfish/Stockfish https://github.com/official-stockfish/Stockfish
- HiraokaTakuya/apery https://github.com/HiraokaTakuya/apery
- nodchip/apery https://github.com/nodchip/apery
- 将棋GUIソフト「将棋所」のページ http://www.geocities.jp/shogidokoro/index.html
- コンピュータ将棋対局場 http://wdoor.c.u-tokyo.ac.jp/shogi/
最後に
これにて競技プログラミングアドベントカレンダー2015は終了となります。それでは良いお年を。
posted by yoji at 9:31 午後
0 Comments:
コメントを投稿
<< Home