Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Go で始める将棋 AI

mururu
April 23, 2022

Go で始める将棋 AI

Go Conference 2022 Spring

mururu

April 23, 2022
Tweet

More Decks by mururu

Other Decks in Programming

Transcript

  1. Copyright Kanmu, Inc. All right reserved. 2 伊藤 友気 CTO

    at Kanmu, Inc. @mururu @mururururu 自己紹介
  2. Copyright Kanmu, Inc. All right reserved. 5 今日のゴール 将棋 AI

    / 将棋ソフトの基本的な仕組みを知り、 実際に Go で実装して対戦できるようになること
  3. Copyright Kanmu, Inc. All right reserved. 6 Go で将棋 AI

    を作るとは gshogi の紹介 思考エンジンを育てる 1 2 3 アジェンダ
  4. Copyright Kanmu, Inc. All right reserved. そもそも将棋とは ? 7 0

    • 1対1で行うボードゲーム • 動きが異なる8種類の駒を交互 に動かして相手の王様を動け なくしたら勝ち
  5. Copyright Kanmu, Inc. All right reserved. 将棋ソフトの基本的なアーキテクチャ 9 1 テキストを入れたり。テキストを入れたり。テキストを入れた

    り。テキストを入れたり。テキストを入れたり。テキストを入 れたり。テキストを入れたり。テキストを入れたり。 GUI 思考エンジン 通信
  6. Copyright Kanmu, Inc. All right reserved. 将棋ソフトの基本的なアーキテクチャ 10 1 テキストを入れたり。テキストを入

    れたり。テキストを入れたり。テキ ストを入れたり。テキストを入れた り。テキストを入れたり。テキスト を入れたり。テキストを入れたり。 GUI 思考エンジン • 盤面を表示したりユーザーが操 作する GUI と、手を探す思考 エンジンは別のソフトウェアとし て実装されている • これにより独立して開発し組み 合わせて使用することができる • それらが USI というプロトコル で通信しながら対局を進める 通信
  7. Copyright Kanmu, Inc. All right reserved. Go で将棋 AI を作るとは

    11 1 テキストを入れたり。テキストを入れたり。テキストを入れた り。テキストを入れたり。テキストを入れたり。テキストを入 れたり。テキストを入れたり。テキストを入れたり。 GUI 思考エンジン 通信
  8. Copyright Kanmu, Inc. All right reserved. 12 1 Go で将棋

    AI を作るとは GUI 思考エンジン 通信 これらを実装する
  9. Copyright Kanmu, Inc. All right reserved. USI プロトコル 13 1

    • GUIソフトと思考エンジンが通信をするための双方向かつ非同期 なプロトコル • 標準入出力を使ってやり取りする • GUIソフトが盤面のデータを送り、思考エンジンが最善手を返 す、というのが基本の動作
  10. Copyright Kanmu, Inc. All right reserved. USI プロトコル - 例

    14 1 GUI 思考エンジン position sfen lnsgkgsnl/9/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LN SGKGSNL w - 1 moves 5a6b 7g7f 3a3b go bestmove 8c8d 思考
  11. Copyright Kanmu, Inc. All right reserved. 思考エンジン 15 1 •

    将棋のルールを実装する ◦ 細かな将棋のルールを正しく実装していかなければならない • 外部のプログラムとのインターフェースを実装する ◦ 今回は USI • 与えられた盤面に対し次に指すべき手を探す ◦ この精度が将棋の強さ
  12. Copyright Kanmu, Inc. All right reserved. 思考エンジン 16 1 •

    将棋のルールを実装する ◦ 細かい将棋のルールを正しく実装していかなければならない • 外部のプログラムとのインターフェースを実装する ◦ 今回は USI • 与えられた盤面に対し次に指すべき手を探す ◦ この精度が将棋の強さ ◦ これだけに集中したい
  13. Copyright Kanmu, Inc. All right reserved. gshogi 18 2 •

    https://github.com/mururu/gshogi • 合法手の生成などができる Go の将棋ライブラリ • python-shogi をベースにしている (Thanks!) • USIプロトコル(の一部)を実装しており、思考エンジンのロジック を実装すればすぐさま GUI ソフトを介して対戦ができる • パフォーマンスは全く気にしていない
  14. Copyright Kanmu, Inc. All right reserved. gshogi - 例 19

    2 これを go build して生 成されたバイナリを、GUI ソフトから指定すればそ のまま対戦できる
  15. Copyright Kanmu, Inc. All right reserved. ランダム 21 3 •

    次に指すべき手の選択として一番素朴 • 可能な手の中からランダムに一つ選ぶ
  16. Copyright Kanmu, Inc. All right reserved. 駒の損得を考える 1 23 3

    • 「駒を多く持っている方が有利そうである」という直感に従ってみ る • 可能な手の中で、指した後に駒が多くなりそうなものの中からラ ンダムに一つ選ぶ
  17. Copyright Kanmu, Inc. All right reserved. 駒の損得を考える 2 25 3

    • 「より強い 駒を多く持っている方が有利そうである」と制限を強く してみる • 駒の種類ごとにポイントを割り振り、可能な手の中で、指した後 の合計ポイントが最も多くなりそうなものの中からランダムに一 つ選ぶ
  18. Copyright Kanmu, Inc. All right reserved. より強くするには - 評価関数の精度 27

    3 • ある局面がどれくらい良いか=勝ちやすいかを示す指標を評価 値とよび、それを求める関数を評価関数という • 今回の例だと「駒の数」「駒のポイントの合計」が評価値であり、 それらを計算するロジック(countPiece, calculatePoint)が評価 関数である • より高度な将棋の知識を用いたり、大量の棋譜を学習させるな どして評価関数の精度を高めることが可能
  19. Copyright Kanmu, Inc. All right reserved. より強くするには - より先の局面まで考慮する 28

    3 • 今回の例では可能な指し手を打った直後の局面のみを考えてい たが、その次の局面で逆転されるかもしれないと考えると、さら に先の局面を考慮にいれたほうがより良く評価できるはず ◦ より深い木構造を辿りながら評価をする • 最終的に決着がつく局面まで探索はなかなかできないのでパ フォーマンスが大事になる
  20. Copyright Kanmu, Inc. All right reserved. 29 まとめ • 自作の将棋AI/将棋ソフトと対戦するために必要なソフトウェアの

    概要を説明し、Go でその実装を簡単に行うための gshogi を紹 介した • 思考エンジンに関する最もベーシックなアイデアを解説し、 gshogi を用いた実装を紹介した