はじめに
この記事はCompetitive Programming Advent Calendar 2015 25日目の記事として書かれたものです。
内容は競技プログラミング経験者であるnodchipが将棋のAIの開発を通して得た知識と経験をまとめたものです。
まずは動かしてみましょう
一から将棋プログラムを作るのは難しいと思います。まずは既存の将棋AIを動かしてみて、どんな感じなのか感覚を掴んでみましょう。無料で手に入る主な将棋AIは以下の通りです。
これらのソフトはUSI(Universal Shogi Interface)プロトコルに対応した将棋AIです。
ネット上にはUSIプロトコルに対応したVisualizerがいくつか公開されています。nodchipはVisualizerとして『将棋所』を使用しています。
将棋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を開く
- ビルドボタンを押す
これだけです。
将棋のAIは主に以下のコンポーネントに分かれています。
- 盤面データ構造
- 局面の状況を保持するデータ構造。強いソフトはBitBoardを用いた高速・省メモリなデータ構造を使っていることが多い。BitBoardについては後述。
- 指し手生成
- ある局面が与えられた時に、手番のプレイヤーが指すことができる合法手を列挙するルーチン。これが高速だと単位時間に読める局面が多くなる。一方、実際に指されそうな手から生成したほうが、ゲーム木探索で枝刈りが多く起こるようになり、探索効率が上がる。高速化と指し手の生成手順は、多分トレード・オフの関係にあると思う。
- 盤面評価
- ある局面が与えられた時に、先手後手のどちらが有利なのか数値評価するルーチン。これが高速だと単位時間に読める局面が多くなる。一方、より正確な数値評価ができたほうが強くなる。これもきっとトレードオフの関係にあると思う。
- 盤面探索
- 置換表
- 定跡データベース
- USIプロトコル
- GUIと通信をするための部分。標準入出力にテキストを流していくだけの簡単なお仕事。競技プログラミングで入出力に慣れていれば単なる実装ゲー。ただしI/Oのflushは忘れずに。
コンピューター将棋では競技プログラミング界隈であまり目にしないアルゴリズムが多いです。以下にそれらの一部を挙げます。
- Minimax
- Negamax
- Alpha-Beta
- Nega alpha
- Fail-Soft Alpha-Beta
- Null Window Search
- Negascout
- Principal Variation Search
- Principal Variation Splitting
- Depth First Search (DFS)
- Breadth First Search (BFS)
- Iterative Deepning
- Lazy SMP
- Transposition Table
- Zobristハッシュ
- Aspiration Window
- Razoring
- Futility pruning
- Null Move Pruning
- Quiescence Search
- Static Exchange Evaluation
- ProbCut
- Late Move Reductions
- ボナンザメソッド
- 全幅探索
- BitBoard
- 3駒関係
- 局面評価のための特徴量の一つ
- Bonanzaが導入したことで有名
- 玉の位置+他のコマ1つの種類と位置+さらに他のコマ1つの種類と位置のtuple等を特徴量とする。
- 上記の特徴量はKPP(King-Piece-Piece)と呼ばれる
- 昔のAperyはs16 KPP[81][1548][1548] に重みを保存していた。81は盤のマス目の数。1548は駒の種類と位置+手駒の枚数。
- NHKの某ドキュメンタリー番組では『勝利の三角形』と呼んでいたが、分かるような分からないような…。
- KPP次元下げ
- Bonanzaメソッドの学習結果に汎化能力を持たせるための手法の一つ。
- KPP以外に3駒の相対位置等も特徴量に加えて機械学習をし、これらを後からKPPに加える。
- 評価値の計算では絶対KPPの配列のみを使えば良い。
- 通常のKPPは絶対KPP、相対位置の特徴量は相対KPPと呼ばれている。
- 機械学習の次元削減とは違う意味だと思う。多分。
- KPA次元下げ
- Bonanzaメソッドの学習結果にさらに汎化能力を持たせるための手法の一つ。
- KPP次元下げに加え、同じ利きを持つ仮想的な駒を考え、これらの駒の配置も特徴量に加えて機械学習すること。
- 角の頭に歩を打つのも香車を打つのも似たような意味になる場合があるので、これらはひとくくりにまとめて学習しましょうというノリらしい。
改造してみましょう
気になったところを改造してみましょう。プロファイラを使ってホットスポットを特定し、定数倍の高速化をかけるもよいでしょう。探索ルーチンの枝刈りパラメーターを調整するのも良いでしょう。機械学習ルーチンにナウなヤングにバカウケの最先端の学習アルゴリズムを導入するのも良いと思います。
例えばtanuki-がAperyに対して施した改造は以下のとおりです。
- 定石データベースを変更し、インターネット上で入手可能なプロの棋譜約4万局と、floodgate上の対戦の中でレーティングがGPS Xeon 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の開発を始めてくださる競技プログラマーが一人でも増えたら幸いです。
リンク
最後に
これにて競技プログラミングアドベントカレンダー2015は終了となります。それでは良いお年を。