11
13

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

コンピュータ将棋製作記 方針

Posted at

コンピュータ将棋製作記 方針(2015年1月24日)

ここまでで作ってきたのは以下の通り

  • 盤面の表現
  • 着手可能手の列挙
  • ランダム指し
  • CSA通信機能の搭載
  • floodgateでランダム指しを動作

この流れで行くと思考ルーチンの開発に行くべきだが、次のような懸念点がある

  • C言語で開発をしているためにコストが大きくかかっている
  • 最初のプロトタイプ開発で無駄が多く、テストがあるとはいえ潜在的なバグリスクが高い
  • floodgateを利用して開発をするのは非効率である
    • 30分に1回しかマッチングが行われず、開発サイクルが遅くなる
    • 本気でfloodgateで対戦している方の迷惑になる

ちょうど土曜日だし、これらの課題を解決することを考える

開発言語

ちょうど良いタイミングなので、C言語を放棄してPythonで作りなおす。Pythonを選んだ理由は

  • 一緒に作っている友人がPythonを選んでいる(エライ…)
  • Pythonにdeep learning系のライブラリがあり、将来的な利用を睨んでいる

といったところ。

スクリプト言語を使うメリットは、開発効率が大きい。文法や言語機能によるところもあるし、実際に使用するかどうかは別として外部ライブラリを使うことが出来るのもある。一方のデメリットとしては、速度が犠牲になることである。

コンピュータ将棋は現在Piece Centricな盤面評価が主流になっており、評価関数を微調整しつつ探索するノード数を増やすのが強さにそのまま繋がるコンピュータチェススタイルを踏襲している。その方法を突き詰めるとプロに勝てるレベルになることは証明されているので、強いコンピュータを作るなら有力な方法である。この方法を採る場合は、とにかく評価する盤面の数を増やすことが大切になり、速度を追求するのは重要だ。

一方で、今回自分が作ろうとしているのは、Square Centricな盤面評価である。チェスは盤面が狭く(8×8)、さらに全ての駒が長い利きを持っているので、ピースの方が重要になるのはよくわかる。一方で将棋は盤面のサイズが大きく、駒の利きはチェスに比べて小さい。将棋での攻勢・守勢は、駒一つ一つが攻撃・防御にどれだけの価値を持っているかではなく、駒を組み合わせた結果、盤面上での支配をどちらがどれだけ持っているかのイメージの方が近いのではないだろうか。

Board Representation: https://chessprogramming.wikispaces.com/Board+Representation

前に書いたように、世の中はPiece Centricが中心である。自分はSquare Centricという前例があまりない思考ルーチンを作ろうとしているので、いずれ思考ルーチンの実装で試行錯誤するのが重要になってくるのは明白だと考えている。その時に開発サイクルを短くするのは最終的なアルゴリズムの品質に大きく寄与することが期待される。

そして最終的にアルゴリズムがある程度確定したら、改めてC言語に移植すればいい。その時には盤面生成も最適化し、速度重視でチューンするようにすれば最終的に速度も期待できるエンジンの作成が出来るだろう(とはいえ、Piece Centricに比べて圧倒的に遅くなるであろうことは間違いない)

設計

データ構造の設計

データ構造は10x12 Boardを採用している(正確には11x13)

これとは別に、駒の場所のindexをそれぞれ持っておいても良いかもしれない。今は盤面9x9を毎回for文でチェックしているが明らかに無駄であるし、思考ルーチンを作るにあたって駒の場所のindexがあるのは便利そうである。

後、利きの盤面構造も持っておいていいのではないかと考えている。駒の利きは、全部で40個ある駒が1個動いたところでそんなに変わるものではない。差分だけ更新する形で実現出来ると思う。

そうすると、1マスが持つ情報は次のようなものだろうか

  • 駒があるかどうか:あるとしたらどの駒か
  • 利いている駒はどれか

本能的にビットに収めたくなり、駒の種類が40通りであれば64bitあれば入りそうだけど、今回はとりあえず開発効率を優先してこれらを抽象化して保存しておくことにする。

「盤面のその場所に利いている駒があるか」ではなくて、「その場所に利いている駒を全て保存」という形にしたい。Square Centricにする以上、そのマスの価値の判断を正確に出せるようにしたい。

「2回連続自分の駒を動かせるとした場合に、そのマスに利いている駒はどれか」という情報を保存しておきたい(1回何かの駒を動かした後の利きという意味)。これにより持ち駒の価値もある程度算出できるようになるだろう。

また駒ごとにどれだけのマスに利きをもっているかの情報を保存しておきたい。序盤では重要な判断基準になることが期待される。

プログラムの設計

現在の設計は、思いつくままに実装しているので大変汚い。要約すると次のような感じ

  • main.c: main関数で、他のファイルの機能を組み合わせてランダム指しプログラムを実装している
  • board.c: 盤面生成メイン。すべての着手可能手を作り出す機能の実装がメイン。そのために、各駒の利きのチェックなどの実装が入っている。
    • make_all_legal_moves: 持ち駒が打てる場所と、盤面上の駒の動かせる場所を列挙しチェックする
    • move: 実際に動かして、打ち歩詰めがないことを確認する
    • make_kiki_board: 盤面上で駒の利きのある場所を列挙する(王手チェック)
  • utility.c: 盤面の出力やSFENの評価などの関数を用意
  • tcp.c: floodgateと接続するためのTCP通信部を作っている

この中で、特にboard.cの設計が汚い。make_all_legal_moves関数とmake_kiki関数両方で別々に駒の利きを計算したりしている。コピペである。ここらへんの設計をしっかり作りたい。

動作確認

コンピュータ将棋のプログラムである以上、その動作確認は強さによってされるべきである。しかし残念ながら、私は将棋が大変に弱く、コンピュータの強さを判断できない。そして出来ることならば定量的に強さを計りたい。

最初考えていたのはfloodgateに登録して色々なコンピュータと対戦することだったが、いくつか問題があることがわかった。

  • floodgateは30分に1回しかマッチングが行われない
  • floodgateで対戦しているプログラムはあまり多くなく、弱いプログラムを投入すると強いプログラムを投入している人の迷惑になりかねない

というわけで、ローカルでチェックする仕組みを考えたい。

USI

The Universal Shogi Interface, draft 1: http://www.glaurungchess.com/shogi/usi.html

色々と批判は多いようだが、色々な将棋ソフトが対応しているプロトコルがこちら。チェスのUCIプロトコルに近い感じがする。標準入出力で対応出来るのが大きい。

XBoardSg: http://www.open-aurec.com:8080/wbforum/viewtopic.php?f=19&t=53274

Macだと、XBoardの拡張によって将棋エンジンをプレイさせることが出来るようにみえる。

将棋プログラムをUSI対応させることによって、将棋プログラムからCSAで出力させることも出来るようだ。Windows版だとプチ将棋が対応している。

プチ将棋: http://www.geocities.jp/shogi_depot/PetitShogi.htm

今のところ開発はMac上でやる予定だが、コンピュータ将棋の世界ではWindowsが一般的なようにもみえる。

今後の方針

以上を踏まえて、今後は次の方針でプログラムを開発する

  • Pythonで書きなおす
  • 速度は一旦犠牲にしても、Square Centricの情報を評価しやすい設計にする
  • USIに対応させ、XBoardなりのインターフェースで表示出来るようにする(CSAは一旦やめる)

とりあえずここらへんを来週の課題として取り組む予定

11
13
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
11
13

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?