Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2015-12-24

競技プログラマー向け将棋AI開発入門 00:00 競技プログラマー向け将棋AI開発入門 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 競技プログラマー向け将棋AI開発入門 - nodchipのTopCoder日記 競技プログラマー向け将棋AI開発入門 - nodchipのTopCoder日記 のブックマークコメント

はじめに

この記事はCompetitive Programming Advent Calendar 2015 25日目の記事として書かれたものです。

内容は競技プログラミング経験者であるnodchipが将棋AIの開発を通して得た知識と経験をまとめたものです。

まずは動かしてみましょう

f:id:nodchip:20151224235618p:image

一から将棋プログラムを作るのは難しいと思います。まずは既存の将棋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-の場合

  1. ソースコードgithubよりcloneしてくる
  2. Visual Studio 2015 Community Editionをインストールする
  3. tanuki-/tanuki-.slnを開く
  4. ビルドボタンを押す

これだけです。

将棋ソフトのコンポーネント

将棋AIは主に以下のコンポーネントに分かれています。

  • 盤面データ構造
    • 局面の状況を保持するデータ構造。強いソフトはBitBoardを用いた高速・省メモリなデータ構造を使っていることが多い。BitBoardについては後述。
  • 指し手生成
    • ある局面が与えられた時に、手番のプレイヤーが指すことができる合法手を列挙するルーチン。これが高速だと単位時間に読める局面が多くなる。一方、実際に指されそうな手から生成したほうが、ゲーム木探索で枝刈りが多く起こるようになり、探索効率が上がる。高速化と指し手の生成手順は、多分トレード・オフの関係にあると思う。
  • 盤面評価
    • ある局面が与えられた時に、先手後手のどちらが有利なのか数値評価するルーチン。これが高速だと単位時間に読める局面が多くなる。一方、より正確な数値評価ができたほうが強くなる。これもきっとトレードオフの関係にあると思う。
  • 盤面探索
    • ゲーム木を探索していくルーチン。
  • 置換表
  • 定跡データベース
  • USIプロトコル
    • GUI通信をするための部分。標準入出力にテキストを流していくだけの簡単なお仕事。競技プログラミングで入出力に慣れていれば単なる実装ゲー。ただしI/Oのflushは忘れずに。

ゲームAI独特のアルゴリズムを覚えましょう

コンピュータ将棋では競技プログラミング界隈であまり目にしないアルゴリズムが多いです。以下にそれらの一部を挙げます。

改造してみましょう

気になったところを改造してみましょう。プロファイラを使ってホットスポットを特定し、定数倍の高速化をかけるもよいでしょう。探索ルーチンの枝刈りパラメーターを調整するのも良いでしょう。機械学習ルーチンにナウなヤングにバカウケ最先端の学習アルゴリズムを導入するのも良いと思います。

例えば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%)
108勝2敗9勝1敗
2014勝6敗16勝4敗
5031勝19敗34勝16敗
10059勝41敗62勝38敗
200112勝88敗117勝83敗
500269勝231敗277勝223敗
1000527勝473敗537勝463敗

他のAIと対戦させてみましょう

AIが十分に強くなったらネット上で他のAIと対戦させてみましょう。コンピュータ将棋対局場「floodgate」は日本で最も有名なコンピュータ将棋ソフト同士の対局場の一つです。プロ棋士の一部も棋譜を参考にしているとのことです。

将棋所からfloodgateに参戦するためには「対局」→「サーバ通信対局(floodgate)」から対戦させたいAIを選び、ログイン名にランキングに表示されるAI名、パスワードに任意の文字列を入力してOKボタンを押せばよいです。

大会に出場してみましょう

現在定期的に開催されている大会は以下のとおりです。

世界コンピュータ将棋選手権は毎年5月のゴールデンウィークに開催されるイベントです。世界と名前が付いている通り、海外からの参加者もいます。

電王トーナメントは株式外社ドワンゴが主催するイベントで、不定期で開催されています。第3回電王トーナメントでは、優勝するとプロ棋士の代表と対戦することができました。

まとめ

競技プログラミング経験者nodchipが将棋AIの開発を行った経験を元に、将棋AIの開発に必要な雑多な知識をまとめました。あまりまとまっていない記事で恐縮です…。

この記事を呼んで将棋AIの開発を始めてくださる競技プログラマーが一人でも増えたら幸いです。

リンク

最後に

これにて競技プログラミングアドベントカレンダー2015は終了となります。それでは良いお年を。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20151224
 |