libshogi で将棋プログラムを作ろう (1)
コンピュータ将棋AdventCalendar 2016 23 人目の tsoftware ですよろしくお願いします．このような機会を設けてくださった平岡さんに感謝いたします．この記事では，初めて将棋プログラムを作る方向けに，libshogi を使った将棋プログラムの開発方法をご紹介します．
libshogi の紹介
libshogi とは
libshogi は将棋プログラムを作るための道具を提供するライブラリです．第24回世界コンピュータ将棋選手権から libshogi を使った将棋プログラムが libshogi の名前で出場しています．コンピュータ将棋選手権におけるカツ丼将棋さんとの将棋は，正式に記録が残る将棋の対局としてはおそらく初めてのステイルメイトということになっています．
ステイルメイトになったのは一手詰めが読めないなど libshogi の弱さが原因です．でも選手権の libshogi が弱いのは libshogi 上で動いている将棋プログラムが弱いのであってライブラリ libshogi の責任ではありません (多分)
libshogi は将棋盤のデータ構造や合法手生成など基本的な機能のみを提供します．将棋の戦略はその上で動作する将棋プログラムが担うことになるので，作り方次第で強くも弱くもなります．
開発者
開発は香川高専詫間キャンパス藤井研究室と tsoftware で行っています．将棋を教材に人工知能の学習ができたら楽しいのではないかということで libshogi と将棋プログラムによる学習教材の共同開発を始めました．全く関係ありませんが，藤井つながりで，メンバー全員が振り飛車党で藤井猛九段のファンです．
開発の動機
藤井研究室では将棋を素材に，学生が探索などのプログラミング手法について学習しています．この学習において問題となったのが将棋の対局をプログラムで表現することの難しさでした．ソースコードが公開されている数多くの著名な将棋プログラムはどれも英知の結晶であり，丹念に読むことにより素晴らしい知見を得ることができます．一方でそれらは人を超えることを目標に磨き抜かれてきたプログラムですので簡単には理解できません．そこで C++ の基本的な文法を知っている学生が短期間で将棋プログラムを書き始めるところまで到達できることを目標に学習用の将棋ライブラリを開発しました．
特徴
libshogi は x64 環境で動作します．内部では 縦型ビットボード を使用しています．利きテーブルのインデックス計算には PEXT 命令を使用しています．少し遅くなりますが PEXT 命令をサポートしていない (BMI2 をサポートしていない) 型番の CPU でも動作します．
libshogi は Boost や STL など他のライブラリを使用せずに実装しています．リストや配列などの基本的なデータ構造も含まれているので libshogi だけで将棋プログラムを作成できます．全ての機能が一つのライブラリで完結していることのメリットはデバッグのしやすさです．将棋プログラムに問題があっても，セグメンテーション違反などは往々にしてリストや配列の中で発生します．基本的なデータ構造も含めて一つのライブラリで完結していれば問題の全体像を把握することが容易になります．また，性能の土台となる部分をコンピュータ将棋用に最適化する余地があるというのもメリットです．
libshogi が提供するもの
図-1 に libshogi の階層モデルを示します．最も重要なのは，探索，定跡，学習などの戦略を司る部分です．libshogi を使用して開発行う場合，この部分を自作の将棋プログラムとして作ることになります．libshogi は網掛けされた機能のみを提供します．foundation 層では，アトミック操作，ロック，スレッド，リスト，などの基本データ構造と操作，game 層では，ルール通り指すための将棋機能，外部プログラムとの通信機能などを提供します．
図-1
ライセンス
libshogi は LGPL で公開しています．シェアードライブラリとしてダイナミックリンクして使用いただく限りは，将棋プログラム本体のソースコードを開示する必要はありません．ライブラリ本体に加えた変更だけフィードバックしてください．libshogi には SIMD-oriented Fast Mersenne Twister (SFMT) のソースコードが含まれています．このソフトウェアのライセンスについては SFMT のディレクトリにある LICENSE.txt を参照してください．
libshogi のインストール
libshogi のインストールは簡単です．ここでは Fedora 25 Server に最小構成の開発環境を構築する方法を紹介します．
動作環境
- x64
- Berkeley ソケットインターフェースをサポートする POSIX システム (Linux など)
- gcc 5.1 もしくはそれ以上 (c++14 のサポート)
libshogi は Fedora 25，Ubuntu 16.04，Linux Mint 18 で動作することを確認しています．新しく開発環境を構築するのであれば，エディタなどの基本的な道具が初めからインストールされている Linux Mint 18 がおすすめです．Fedora 25 Server を最小構成でインストールし，gcc-c++，make，ctags，vim をインストールすれば短時間に開発環境を作ることもできます．テストしていませんが FreeBSD など他の POSIX システムでも動作するはずです．
Fedora 25 のインストール
Fedora 25 で最小限の開発環境を構築してみましょう．Fedora のインストール CD/DVD の ISO イメージはFedora Server のダウンロードページ から入手することができます．ネットワークが使用できる環境であればネットインストールイメージが簡便です．
インストーラが起動したら Install Fedora 25 を選びます．
言語を選択します．
ソフトウェアの選択(S) を最小限のインストールにします．
**インストール先 (D)を開いて確認と完了を行うとインストールの開始(B)**を押すことができるようになります．インストール先ディスクにあるデータは全て失われますので注意してください．
インストールが行われている間に**ROOT パスワードの設定 (R)と一般ユーザの作成 (U)**を行います．
インストール終了までおよそ 15 分程度です．完了したら**再起動(R)**のボタンを押します．
ここから先はコンソール端末での作業となります．Windows からリモート接続するのであれば Tera Term がおすすめです．以下のように root でログインし IP アドレスを確認した上で接続してください．
libshogi のインストール
libshogi のビルドに必要なのは gcc-c++，make，ctags です．またソースコードの取得に git が必要です．これ以外にインストールしておくと便利なものとして，gdb，wget，vim， screen などがあります．Windows とファイルを共有してプログラムの編集を行うのであれば samba もあると良いでしょう．root 権限でそれらのソフトウェアを追加インストールします．
# dnf -y remove vim-minimal
# dnf -y install git gcc-c++ make ctags gdb vim screen samba ftp wget openssh-clients
次に libshogi をインストールします．一般ユーザで作業を行います．GitHub からリポジトリをクローンしたら libshogi ディレクトリにある Makefile を開いてみましょう．
$ git clone https://github.com/makudenki/libshogi.git
$ cd libshogi
$ vi Makefile
ここではいくつかのインストールオプションを設定できます．
TARGET = /usr/local
HEADDIR = $(TARGET)/include/shogi/
LIBRDIR = $(TARGET)/lib64
LIBNAME = libshogi.so.0
BMI2 = n
TLS = n
TARGET には libshogi をインストールするディレクトリトップのパスを指定します．デフォルトでは /usr/local/ に設定されています．HEADDIR にはヘッダファイルが置かれるディレクトリを指定します．LIBDIR にはライブラリファイルが置かれるディレクトリを指定します．
もし使用しているプロセッサが BMI2 をサポートしているのであれば PEXT 命令を使用することにより性能が向上します．以下のコマンドを実行した結果 flags : ... bmi2 ... の表示があればプロセッサが BMI2 をサポートしています．
$ cat /proc/cpuinfo | grep bmi2
flags : ..... bmi2 .....
PEXT 命令を使用するようにするには Makefile のオプションを以下のように指定します．
BMI2 = y
libshogi では局面を表現するクラス Position が頻繁にコピーされることを想定していません．もしコピーのコストが無視できない場合は，コンテクストを保存する部分 (コンテクストキャッシュ) を Thread Local Storage (TLS) にすることもできます．これにより Position のフットプリントが半分程度になります．ただし TLS にすると読み書きの度にアドレスの確認が行われるため効率が落ちます．コピーのコストとのトレードオフをよく検討した上で使用してください．TLS を使用するには Makefile のオプションを以下のように指定します．
TLS = y
ソースコードをコンパイルするには make を実行します．
$ make
インストールは root 権限で make install を実行します．
# make install
これで libshogi を使用して将棋プログラムを開発する環境が整いました．
libshogi を使用した将棋プログラムの作成
libshogi を使用した将棋プログラム作成してみましょう．
初手7六歩
プログラムを作るためのディレクトリを作成します．作成したディレクトリに Makefile のひな形 libshogi/example/Makefile をコピーします．この Makefile は Main.cpp から shogiprogram という名前のバイナリをビルドするよう設定されています．
$ cd
$ pwd
/home/XXXXXX
$ ls
libshogi
$ mkdir shogiprogram
$ cd shogiprogram
$ cp ../libshogi/example/Makefile .
$ vim Makefile
Makefile は libshogi 本体をビルドしたときと同じ設定にしてください．
TARGET = /usr/local
HEADDIR = $(TARGET)/include/shogi/
LIBRDIR = $(TARGET)/lib64
LIBNAME = libshogi.so.0
BMI2 = n
TLS = n
それではプログラムを書いてみましょう．shogiprogram ディレクトリの中で Main.cpp というプログラムを以下のように作成します．
#include <iostream>
#include <Shogi.h>
using namespace game;
int main (void)
{
// ライブラリ初期化
Shogi::initialize();
// 駒の価値を設定
Position::setValue (Evaluation::Value);
Position::handsValue(Evaluation::Hands);
// 局面のインスタンスを作成
Position p;
// 平手初期局面にする
p.init();
// 局面を表示
std::cout << p << std::endl;
// 指し手 7六歩を作成
Move::Move m = Move::move(Square::SQ77, Square::SQ76);
// 7六 歩を指す
p.move(m);
// 再び局面を表示
std::cout << p << std::endl;
return 0;
}
まず make によりプログラムをコンパイルします．環境変数 LD_LIBRARY_PATH にシェアードライブラリの場所を指定して実行します．同じシェルセッションを使い続けるのであれば次回から環境変数を設定する必要はありません．
$ make
$ export LD_LIBRARY_PATH=/usr/local/lib64
$ ./shogiprogram
LD_LIBRARY_PATH を指定するのが面倒なときは root 権限で /etc/ld.so.conf ファイルに /usr/local/lib64 を追記すれば都度指定しなくても実行できるようになります．コマンドを間違えないよう注意してください．
# echo '/usr/local/lib64' >> /etc/ld.so.conf
# ldconfig
プログラムの説明をします．libshogi の将棋に関する機能を使用するには Shogi.h をインクルードします．Shogi に関連する様々なデータや機能は名前空間 game:: 上で定義されています．他の将棋ライブラリと共用するようなことがなければ名前が衝突することはないので using namespace game; としましょう．
#include <iostream>
#include <Shogi.h>
using namespace game;
最初にライブラリの初期化が必要です．これによりハッシュキーを作成するための乱数テーブルや利きテーブルが初期化されます．
// ライブラリ初期化
Shogi::initialize();
次に駒の価値を設定します．デフォルトの駒価値が libshogi/lib/shogi/Evaluation.h に定義されています．
/// Value of the pieces on board
static const Eval Value[Piece::Pieces] = {
// EMP BFU BKY BKE BGI BKA BHI BKI
0, 100, 200, 300, 400, 800, 1000, 500,
// BOU BTO BNY BNK BNG BUM BRY
0, 500, 500, 500, 500, 1300, 1500, 0,
// WFU WKY WKE WGI WKA WHI WKI
0, -100, -200, -300, -400, -800,-1000, -500,
// WOU WTO WNY WNK WNG WUM WRY
0, -500, -500, -500, -500,-1300,-1500, 0
};
/// Number of pieces
/// Value of the pieces in hands
static const Eval Hands[Piece::Depth + 1][Piece::Kind] = {
// EMP FU KY KE GI KA HI KI
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 100, 200, 300, 400, 800, 1000, 500},
{ 0, 200, 400, 600, 800, 1600, 2000, 1000},
{ 0, 300, 600, 900, 1200, 0, 0, 1500},
{ 0, 400, 800, 1200, 1600, 0, 0, 2000},
{ 0, 500, 0, 0, 0, 0, 0, 0},
{ 0, 600, 0, 0, 0, 0, 0, 0},
{ 0, 700, 0, 0, 0, 0, 0, 0},
{ 0, 800, 0, 0, 0, 0, 0, 0},
{ 0, 900, 0, 0, 0, 0, 0, 0},
{ 0, 1000, 0, 0, 0, 0, 0, 0},
{ 0, 1100, 0, 0, 0, 0, 0, 0},
{ 0, 1200, 0, 0, 0, 0, 0, 0},
{ 0, 1300, 0, 0, 0, 0, 0, 0},
{ 0, 1400, 0, 0, 0, 0, 0, 0},
{ 0, 1500, 0, 0, 0, 0, 0, 0},
{ 0, 1600, 0, 0, 0, 0, 0, 0},
{ 0, 1700, 0, 0, 0, 0, 0, 0},
{ 0, 1800, 0, 0, 0, 0, 0, 0}
};
これをそのまま使うのであれば，
// 駒の価値を設定
Position::setValue (Evaluation::Value);
Position::handsValue(Evaluation::Hands);
と指定してください．オリジナルの駒の価値を設定する場合は同じサイズの配列を setValue() メソッドと handsValue() メソッドに渡してください．駒の価値は全体を通して一回設定するだけで良いです．
局面を表現するクラスは Position です．init() メソッドを呼ぶと平手初期局面になります．
// 局面のインスタンスを作成
Position p;
// 平手初期局面にする
p.init();
// 局面を表示
std::cout << p << std::endl;
Position は iostream をサポートしているのでそのまま std::cout に出力することができます．
表示で Hash は局面のハッシュキー，Hand は持ち駒のハッシュキー，Board は盤面のハッシュキーです．盤面のハッシュキーによって局面を 64 bit 値で識別します．Exchange は駒の損得 (駒割り) です．盤上の駒は黄色が後手，緑が先手です．Hand には持ち駒と枚数が表示されます．
指し手を表現するために Move::Move という列挙型が libshogi/lib/shogi/Move.h に定義されています．やねうら王 の実装を参考に 16 bit で手を表現するようにしています．
/**
* Move
* is 16 bit-value expressed as the followings;
*
* MSB LSB
* 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
* +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
* | | | | |
* | | | Square moved from | Square moved to |
* | | | | |
* +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
* | |
* | +--- indicator for dropping moves.
* |
* +------- Indicator for promoting moves.
*
* YaneuraOu combines this with 16 bits evaluation value to 32 bits
* value. This makes it easy for CPU to line the values in its cache.
*
*/
enum Move : uint32_t {
/// Void move
None = 0,
/// Dropping move
Drop = 1 << 14,
/// Promoting move
Promote = 1 << PromotionShift
};
盤上の位置は Square::Square 型で表現します．例えば 7六 の地点は Square::SQ76，7七の地点は Square::SQ77 となります．初手 7六歩は SQ77 から SQ76 への移動ですので，
// 指し手 7六歩を作成
Move::Move m = Move::move(Square::SQ77, Square::SQ76);
のように手を生成します．ここまで見て気づかれたかと思いますが，libshogi ではほとんどの型が固有の名前空間を持っています．頻繁に使う名前空間は using namespace で省略すると良いでしょう．手を局面に反映させるには move() メソッドを使います．
// 7六 歩を指す
p.move(m);
もう一度表示すると 7六歩が指された局面が表示されます．
思ったより簡単ですね．
初めての対局
初めての対局はランダムな指し手で自己対戦するプログラムを作成してみましょう．プログラムを次のように変更します．
#include <cstdlib>
#include <iostream>
#include <Shogi.h>
#include <Array.h>
using namespace game;
using namespace foundation;
int main (void)
{
// 初期化
Shogi::initialize();
// 駒の価値を設定
Position::setValue (Evaluation::Value);
Position::handsValue(Evaluation::Hands);
// 局面のインスタンスを作成
Position p;
// 平手初期局面にする
p.init();
// 対戦
while (1) {
// 指し手生成
Array<Move::Move, Move::Max> move;
p.genMove(move);
// 手が無かったら詰み
if (move.vsize() == 0) {
break;
}
// ランダムに手を選ぶ
int choice = rand() % (int)move.vsize();
// 手を表示
std::cout << p.string(move[choice]) << std::endl;
// 着手
p.move(move[choice]);
// 局面を表示
std::cout << p << std::endl;
}
return 0;
}
実行してみましょう．環境変数 LD_LIBRARY_PATH は毎回設定する必要はありません．新しいシェルを開いたときに一回だけ export してください．
$ make
$ export LD_LIBRARY_PATH=/usr/local/lib64 # 毎回必要ではない
$ ./shogiprogram
ランダムに指すと決着がつかないのではと心配になります．しかし乱数を初期化してもほとんどの場合 1 秒以内に決着がつきます．プログラムを見てみましょう．
#include <cstdlib>
#include <iostream>
#include <Shogi.h>
#include <Array.h>
using namespace game;
using namespace foundation;
今回は Position が生成した手を受け取るための Array を使用します．Array は固定長配列のテンプレートクラスです．Array<型, 要素数> のように使います．手を書き込むため型は Move::Move，要素数は libshogi/lib/shogi/Move.h に定義されている Move::Max = 539 を指定します．
// 指し手生成
Array<Move::Move, Move::Max> move;
p.genMove(move);
Position は内部で手番を管理していて genMove() メソッドは現局面の合法手を生成します．Position が生成する手の種類は次の通りです．
| メソッド | 手番 | 打ち歩詰め | Pin |
|---|---|---|---|
| genMove() | × | ○ | |
| genMoveB() | 先手 | × | ○ |
| genMoveW() | 後手 | × | ○ |
| minorMove() | × | ○ | |
| genFast() | × | × | |
| genFastB() | 先手 | × | × |
| genFastW() | 後手 | × | × |
| genCapt() | × | × | |
| genCaptB() | 先手 | × | × |
| genCaptW() | 後手 | × | × |
| genChck() | × | ○ | |
| genChckB() | 先手 | × | ○ |
| genChckW() | 後手 | × | ○ |
| genCFst() | × | × | |
| genCFstB() | 先手 | × | × |
| genCFstW() | 後手 | × | × |
genMove() 系のメソッドは Pin を考慮した合法手を生成します．歩，角，飛の不成は生成しません．歩，角，飛の不成は別に minorMove() を呼び出せば取得することができます．genMoveB() は先手の手，genMoveW() は後手の手を生成します．Position の指し手生成は手番に最適化されています．探索など手番が分かっているコンテクストから呼び出す場合はこれらのメソッドを使った方が早くなります．
genFast() 系のメソッドは Pin を考慮しません．したがって生成された手には自殺手が含まれます．genCapt() 系のメソッドも Pin を考慮しません．genCapt() は駒を取る手，王手を回避する手のみを生成します．
genChck() 系のメソッドは Pin を考慮した王手，または自玉に王手がかかっている場合は王手を回避する手を生成します．
genCFst() 系のメソッドは Pin を考慮せずに王手を生成します．王手を回避する手は生成しません．genCFst() は genCapt() と一緒に使用されることを想定しています．静止探索において genCapt() に続けて genCFst() を呼び出せば，駒を取る手だけではなく，genCapt() によって生成された手に含まれない王手も探索の対象となります．
Intel Core i3-6100 CPU @ 3.70GHz シングルスレッドで計測すると genMove() は指し手生成祭り局面で 1.00 M回/秒，genFast() は 1.25 M回/秒程度です．
いずれのメソッドも打ち歩詰めのチェックは行いません．
生成された手は Array に格納されます．genMove() に加えて，歩，角，飛の不成が必要な場合は，続けて minorMove() 呼び出すことにより追加されます．
// 指し手生成
Array<Move::Move, Move::Max> move;
p.genMove(move);
p.minorMove(move);
Array に含まれる意味のある値を持つ要素の数は vsize() メソッドで取得できます．プログラムでは move に手が生成されています．したがって move.vsize() == 0 の場合，指し手がない状態 (詰み) となります．
// 手が無かったら詰み
if (move.vsize() == 0) {
break;
}
ランダムに手を選び着手します．n 番目の Array 要素にアクセスする場合は [] 演算子を使います．
// ランダムに手を選ぶ
int choice = rand() % (int)move.vsize();
// 着手
p.move(move[choice]);
自作将棋プログラムとの初めての対局
次は自作将棋プログラムと対局してみましょう．libshogi は CSA プロトコルをサポートしています．CSA プロトコルで将棋所に接続して対局します．将棋所は素晴らしいプログラムです．このようなソフトを提供してくれている作者様に感謝します．将棋所の使い方を参考にダウンロードと展開まで行ってください．
CSA 通信機能を備えたプログラムは以下のようになります．
#include <cstdlib>
#include <iostream>
#include <Shogi.h>
#include <Array.h>
#include <CSAConnection.h>
using namespace game;
using namespace foundation;
int main (int argc, char * argv[])
{
// コマンド実行時の引数確認
if (argc != 4) {
std::cerr << "Usage : "
<< argv[0]
<< " <User Name> <Password> <CSA Server>"
<< std::endl;
exit(EXIT_FAILURE);
}
// 初期化
Shogi::initialize();
// 駒の価値を設定
Position::setValue (Evaluation::Value);
Position::handsValue(Evaluation::Hands);
// CSA サーバに接続
CSAConnection csa(argv[3]);
csa.connect();
// CSA サーバにログイン
csa.login(argv[1], argv[2]);
// 対局待ち
auto summary = csa.newGame();
// 対局受諾
csa.accept();
// 局面のインスタンスを作成
Position p(summary);
// プログラムの手番を確認
auto myturn = Position::myTurn(summary);
// メッセージ受信用
Vector<std::string> message;
// 対戦
while (1) {
if (p.turn() == myturn) {
// プログラムの手番
// 指し手生成
Array<Move::Move, Move::Max> move;
p.genMove(move);
// 手が無かったら詰み
if (move.vsize() == 0) {
// 投了
csa.resign();
break;
}
// ランダムに手を選ぶ
int choice = rand() % (int)move.vsize();
// 指し手送信
csa.send(p.string(move[choice]));
// 局面を進める
p.move(move[choice]);
} else {
// 相手の手番
// 相手の手を待つ
csa.receive(message);
// 送信されてきた手の先頭文字が '+' '-' でないときは指し手ではない
if (message[0][0] != '+' && message[0][0] != '-') {
// 送信されてきたメッセージを表示
for (auto l : message) {
std::cout << l << std::endl;
}
break;
}
// プログラムの手 (エコー) は無視
const char turchk[] = {'+', '-'};
if (message[0][0] == turchk[myturn]) {
// 2 行目に相手の手が入る場合もある
if (message.size() == 2) {
message[0] = message[1];
} else {
continue;
}
}
// 相手の手を表示
std::cout << message[0] << std::endl;
// 局面を進める
p.move(message[0]);
}
// 局面を表示
std::cout << p << std::endl;
}
// メッセージを全て受信
while (csa.message()) {
csa.receive(message);
if (message.vsize() == 0) {
break;
}
for (auto l : message) {
std::cout << l << std::endl;
}
}
// 棋譜ファイルの書き込み
csa.write("kifu.csa");
// ログアウト
csa.logout();
// 通信終了
csa.close();
exit(EXIT_SUCCESS);
}
コンパイルできたら将棋所を開いて 対局(G) から 1 対 1 通信対局を選択します．こちら側の対局者は 人間 を選び OK を押してください．
接続待ちダイアログに表示されるアドレスに接続します．ダイアログに表示されている IP アドレスをコマンド実行時の 3 番目の引数として指定してください．
$ ./shogiprogram test test 192.168.2.129
何回か対局してみてください．プログラムはランダムに指し手を選択するので当然弱いです．それでも王手をかければ逃げてくれます．全く無機質な相手ではないという印象を持たれたのではないでしょうか．
プログラムを見ていきましょう．CSA 通信をするために CSAConnection.h をインクルードします．
#include <cstdlib>
#include <iostream>
#include <Shogi.h>
#include <Array.h>
#include <CSAConnection.h>
using namespace game;
using namespace foundation;
プログラム実行時にコマンド引数として，サーバへログインするためのユーザ名，パスワード，サーバアドレスを指定します．サーバアドレスはホスト名もしくは IP アドレスで指定します．最初にコマンド実行時の引数を見てこれらが指定されているか確認します．
// コマンド実行時の引数確認
if (argc != 4) {
std::cerr << "Usage : "
<< argv[0]
<< " <User Name> <Password> <CSA Server>"
<< std::endl;
exit(EXIT_FAILURE);
}
CSA プロトコルによる通信は CSAConnection クラスのインスタンスを生成して行います．インスタンス作成時にサーバアドレスを渡します．インスタンスが生成されたら最初に connect() でサーバへ接続します．次に login() でログインします．ログイン後 newGame() を呼ぶとサーバから対戦の条件 (対局相手の名前，持ち時間など) が通知されます．その条件で良ければ accept() します．通信エラーなどがあった場合は CSAConnection クラスから例外がスローされます．今回のプログラムについてはエラー処理を書く必要はありません．
// CSA サーバに接続
CSAConnection csa(argv[3]);
csa.connect();
// CSA サーバにログイン
csa.login(argv[1], argv[2]);
// 対局待ち
auto summary = csa.newGame();
// 対局受諾
csa.accept();
newGame() の戻り値が対局の条件となります．これを Position のコンストラクタに渡せば，対局条件に沿った局面のインスタンスが生成されます．またこちらの手番は Position::myTurn() により確認することができます．
// 局面のインスタンスを作成
Position p(summary);
// プログラムの手番を確認
auto myturn = Position::myTurn(summary);
メッセージを受信するために std::string の配列を用意します．Vector は可変長配列のテンプレートクラスです．CSA サーバから送られてくるメッセージは複数行となることがあるので，std::string の可変長配列にメッセージを受信します．Vector の要素にメッセージが一行づつ格納されていきます．
// メッセージ受信用
Vector<std::string> message;
ここまで来たら対局開始です．プログラムの手番ではランダムに指し手を選択し send() で送信，相手の手番には receive() で相手の手を待ちます．Position で現在の手番を調べるには turn() メソッドを使います．
// 対戦
while (1) {
if (p.turn() == myturn) {
// プログラムの手番
// 指し手生成
Array<Move::Move, Move::Max> move;
p.genMove(move);
手が無かった時は詰みですので CSAConnection の resign() メソッドで投了します．
// 手が無かったら詰み
if (move.vsize() == 0) {
// 投了
csa.resign();
break;
}
指せる手があった場合はその中からランダムに選び送信します．Position の string() メソッドを使うと Move::Move を CSA プロトコル形式の指し手文字列に変換してくれます．CSA サーバへ手を送信するのと同時に局面も進めておきます．
int choice = rand() % (int)move.vsize();
// 指し手送信
csa.send(p.string(move[choice]));
// 局面を進める
p.move(move[choice]);
次は相手の手番です．相手の手番にはサーバから指し手が送られてくるのを待ちます．
} else {
// 相手の手番
// 相手の手を待つ
csa.receive(message);
CSA サーバからは指し手以外のメッセージが送られてくることもあります．例えば千日手が成立したときには #SENNICHITE というメッセージが送られてきます．メッセージの最初の文字が + か - の時は指し手です．それ以外では対局が終わるもしくは中断するイベントが発生したということなので対局を終了します．
// 送信されてきた手の先頭文字が '+' '-' でないときは指し手ではない
if (message[0][0] != '+' && message[0][0] != '-') {
// 送信されてきたメッセージを表示
for (auto l : message) {
std::cout << l << std::endl;
}
break;
}
CSA サーバはプログラムが送信した手を消費時間の情報を付加してエコーバックします．この消費時間の情報は持ち時間の管理に使います．このプログラムでは簡単のため無視しましょう．コンピュータ同士の対戦では短い時間で手が進むことがあります．このような時に CSAConnection の receive() メソッドがエコーバックと同時に相手の手を渡してくることがあります．2 行目がある場合はそれを相手の手として処理します．
// プログラムの手 (エコー) は無視
const char turchk[] = {'+', '-'};
if (message[0][0] == turchk[myturn]) {
// 2 行目に相手の手が入る場合もある
if (message.size() == 2) {
message[0] = message[1];
} else {
continue;
}
}
Position はサーバから送られてきた指し手文字列 (std::string) でも move() できます (実際は CSAMove として処理されます) 相手から送信されてきた手を表示して局面を進めます．そして再びプログラムの手番に戻ります．
// 相手の手を表示
std::cout << message[0] << std::endl;
// 局面を進める
p.move(message[0]);
最後に対局の終了処理です．まず，サーバから未受信のメッセージがあれば全て受信しwrite() で棋譜ファイルを生成します．次にlogout()，close() メソッドで通信を終了します．
// メッセージを全て受信
while (csa.message()) {
csa.receive(message);
if (message.vsize() == 0) {
break;
}
for (auto l : message) {
std::cout << l << std::endl;
}
}
// 棋譜ファイルの書き込み
csa.write("kifu.csa");
// ログアウト
csa.logout();
// 通信終了
csa.close();
floodgate への接続も CSA プロトコルを使います．ユーザ名，パスワードの規則については floodgate のページを参照してください．
$ ./shogiprogram libshogi_corei3 floodgate-300-10F,test1 wdoor.c.u-tokyo.ac.jp # 接続例
これは将来自作の将棋プログラムを作ったときのための例として挙げました．このランダムプレーヤで floodgate には接続しないでください．
プログラムに駒の損得を考えた手を指させる
ランダムな指し手だとさすがに弱いので少しだけ考えるようにプログラムを改良したいと思います．具体的には駒の取り合いが生じる局面ではできるだけ駒得するような手を選ぶようにプログラムを変更します．
将棋プログラムでは数値で駒の損得を判断できるように駒に点数を与えます．libshogi/lib/shogi/Evaluation.h には駒ごとの点数が定義されています．例えば歩は 100 点，飛車は 1000 点といった具合です．実際に手を指す前に自分がこう指したら相手がこう応じるというのをシミュレーションして最終的に駒得する手順を選びます．このような先読み (探索) をミニマックス法 と言います．駒の点数を決めたことにより局面ごとに駒の損得を数値として表すことができるようになりました．これを局面の評価値とします．後手の駒にはマイナスの値を与えておき，評価値が 0 の場合は互角，プラスの値になると先手が駒得，マイナスの値になると後手が駒得と判断します．玉を取られるとどんなに駒得していても負けですので，先手玉の価値は $+\infty$ 後手玉の価値は $-\infty$ になります．
理屈の上では最後まで探索することにより最終的に相手の玉を取る手を選ぶことができます．しかし，現実の局面変化は膨大な数になるので，最後まで読み切ることはできません．ある程度まで探索した局面の評価値をもって指し手を決断します．
実際の探索にはミニマックス法を改良したアルファ・ベータ法を用います．アルファ・ベータ法はミニマックス法よりも少ない探索数で同じ結果を得ることができます．
#include <cstdlib>
#include <iostream>
#include <Shogi.h>
#include <Array.h>
#include <CSAConnection.h>
using namespace game;
using namespace foundation;
using namespace Evaluation;
/* --------------------------- global variables --------------------------- */
/// 最大の探索深さ
static int _searchDepth = 10;
/* ------------------------------------------------------------------------- */
/* -------------------------- function prototypes -------------------------- */
/// 探索
static size_t searchMax (Position &, Array<Move::Move, Move::Max> &);
static size_t searchMin (Position &, Array<Move::Move, Move::Max> &);
static Eval quiesMax (Position &, Eval alpha, Eval beta, int depth);
static Eval quiesMin (Position &, Eval alpha, Eval beta, int depth);
/* ------------------------------------------------------------------------- */
/**
* 先手最善手を調べる
* @parm p 局面
* @parm m 候補手
* @return 最善手のインデックス
*/
static size_t searchMax (Position &p, Array<Move::Move, Move::Max> &m)
{
size_t idx = 0;
Eval alpha = -Infinity;
Eval beta = Infinity;
for (size_t i = 0; i < m.vsize(); ++i) {
// 局面を進める
auto back = p.move(m[i]);
// 後手局面を探索
auto value = quiesMin(p, alpha, beta, 0);
// 局面を戻す
p.undo(back);
// beta カット
if (value >= beta ) {
std::cout << "* " << value << " "
<< p.string(m[i]) << std::endl;
return i;
}
// 下限を更新
if (value > alpha) {
alpha = value;
idx = i;
std::cout << " " << value << " "
<< p.string(m[i]) << std::endl;
}
}
return idx;
}
/**
* 後手最善手を調べる
* @parm p 局面
* @parm m 候補手
* @return 最善手のインデックス
*/
static size_t searchMin (Position &p, Array<Move::Move, Move::Max> &m)
{
size_t idx = 0;
Eval alpha = -Infinity;
Eval beta = Infinity;
for (size_t i = 0; i < m.vsize(); ++i) {
// 局面を進める
auto back = p.move(m[i]);
// 先手局面を探索
auto value = quiesMax(p, alpha, beta, 0);
// 局面を戻す
p.undo(back);
// alpha カット
if (value <= alpha) {
std::cout << "* " << value << " "
<< p.string(m[i]) << std::endl;
return i;
}
// 上限を更新
if (value < beta ) {
beta = value;
idx = i;
std::cout << " " << value << " "
<< p.string(m[i]) << std::endl;
}
}
return idx;
}
/**
* 先手番局面の静的な評価値を探索により決定する (Max)
* @parm p 局面
* @parm alpha 下限値
* @parm beta 上限値
* @parm depth 探索の深さ
* @return 評価値
*/
static Eval quiesMax (Position &p, Eval alpha, Eval beta, int depth)
{
// 評価値の初期値は静的評価値
// 上限が現在の静的評価値以下の場合探索しない
Eval vmax = p.eval();
// beta カット (standpat)
if (beta <= vmax) {
return beta;
}
// 末端なので静的評価値を返す
if (depth > _searchDepth) {
return vmax;
}
// 先手番で駒を取る手、王手を回避する手のみを生成 (ほぼ合法手)
// 該当する手がなかった場合は静的評価値がこの局面の評価値となる
Array<Move::Move, Move::Max> m;
p.genCaptB(m);
for (auto move : m) {
// 玉を取る手か
if (p.dustyB(move)) {
vmax = Infinity;
break;
}
// 局面を進める
auto back = p.move(move);
// 後手番で静止探索
auto value = quiesMin(p, max(vmax, alpha), beta, depth + 1);
// 局面を戻す
p.undo(back);
// beta カット
if (value >= beta) {
return beta;
}
// 下限更新か
if (value > vmax) {
vmax = value;
}
}
return vmax;
}
/**
* 後手番局面の静的な評価値を探索により決定する (Min)
* @parm p 局面
* @parm alpha 下限値
* @parm beta 上限値
* @parm depth 探索の深さ
* @return 評価値
*/
static Eval quiesMin (Position &p, Eval alpha, Eval beta, int depth)
{
// 評価値の初期値は静的評価値
// 下限が現在の静的評価値以上の場合探索しない
Eval vmin = p.eval();
// alpha カット (standpat)
if (alpha >= vmin) {
return alpha;
}
// 末端なので静的評価値を返す
if (depth > _searchDepth) {
return vmin;
}
// 後手番で駒を取る手、王手を回避する手のみを生成 (ほぼ合法手)
// 該当する手がなかった場合は静的評価値がこの局面の評価値となる
Array<Move::Move, Move::Max> m;
p.genCaptW(m);
for (auto move : m) {
// 玉を取る手か
if (p.dustyW(move)) {
vmin = -Infinity;
break;
}
// 局面を進める
auto back = p.move(move);
// 先手番で静止探索
auto value = quiesMax(p, alpha, min(vmin, beta), depth + 1);
// 局面を戻す
p.undo(back);
// alpha カット
if (value <= alpha) {
return alpha;
}
// 上限更新か
if (value < vmin) {
vmin = value;
}
}
return vmin;
}
int main (int argc, char * argv[])
{
// コマンド実行時の引数確認
if (argc != 4) {
std::cerr << "Usage : "
<< argv[0]
<< "<User Name> <Password> <CSA Server>"
<< std::endl;
exit(EXIT_FAILURE);
}
// 初期化
Shogi::initialize();
// 駒の価値を設定
Position::setValue (Evaluation::Value);
Position::handsValue(Evaluation::Hands);
// CSA サーバに接続
CSAConnection csa(argv[3]);
csa.connect();
// CSA サーバにログイン
csa.login(argv[1], argv[2]);
// 対局待ち
auto summary = csa.newGame();
// 対局受諾
csa.accept();
// 局面のインスタンスを作成
Position p(summary);
// プログラムの手番を確認
auto myturn = Position::myTurn(summary);
// メッセージ受信用
Vector<std::string> message;
// 対戦
while (1) {
if (p.turn() == myturn) {
// プログラムの手番
// 指し手生成
Array<Move::Move, Move::Max> move;
p.genMove(move);
// 手が無かったら詰み
if (move.vsize() == 0) {
// 投了
csa.resign();
break;
}
// 探索の結果が最も良い手を選択する
size_t best;
if (move.vsize() > 1) {
if (myturn == Color::Black) {
best = searchMax(p, move);
} else {
best = searchMin(p, move);
}
} else {
// 手がひとつだけしかなかった場合はその手を指すしかない
best = 0;
}
// 指し手送信
csa.send(p.string(move[best]));
// 局面を進める
p.move(move[best]);
} else {
// 相手の手番
// 相手の手を待つ
csa.receive(message);
// 送信されてきた手の先頭文字が '+' '-' でないときは指し手ではない
if (message[0][0] != '+' && message[0][0] != '-') {
// 送信されてきたメッセージを表示
for (auto l : message) {
std::cout << l << std::endl;
}
break;
}
// プログラム手番の指し手 (エコー) は無視
const char turchk[] = {'+', '-'};
if (message[0][0] == turchk[myturn]) {
// 2 行目に相手の手が入る場合もある
if (message.size() == 2) {
message[0] = message[1];
} else {
continue;
}
}
// 相手の手を表示
std::cout << message[0] << std::endl;
// 局面を進める
p.move(message[0]);
}
// 局面を表示
std::cout << p << std::endl;
}
// メッセージを全て受信
while (csa.message()) {
csa.receive(message);
if (message.vsize() == 0) {
break;
}
for (auto l : message) {
std::cout << l << std::endl;
}
}
// 棋譜ファイルの書き込み
csa.write("kifu.csa");
// ログアウト
csa.logout();
// 通信終了
csa.close();
exit(EXIT_SUCCESS);
}
コンパイルして将棋所で対局してみましょう．ランダムな指し手のときよりは強くなったのではないでしょうか．駒がただでとられるような手は指さないようになったはずです．
main() はほとんど変更がありません．ランダムに指し手を決定していた部分を探索に置き換えています．もし指せる手の数が 1 の場合は探索するまでもないのでその手を選びます．それ以外は探索の結果が最も良い手を選びます．手番は Color::Color で表現され Color::Black = 0 が先手，Color::White = 1 が後手です．
// 探索の結果が最も良い手を選択する
size_t best;
if (move.vsize() > 1) {
if (myturn == Color::Black) {
best = searchMax(p, move);
} else {
best = searchMin(p, move);
}
} else {
// 手がひとつだけしかなかった場合はその手を指すしかない
best = 0;
}
先手番局面では評価値が最大になる手を探索します．後手番局面では評価値が最小になる手を探索します．アルファ・ベータ法ではミニマックス法によって得られるであろう評価値の範囲を決めて探索を行います．探索を繰り返すに従いこの範囲は狭まっていきます．範囲の下限値のことを$\alpha$，上限値のことを$\beta$と呼びます．$\alpha$の初期値は $-\infty$，$\beta$の初期値は $+\infty$ です．先手番局面では評価値が最大になる手を探しているので，ある局面の評価値が現在の$\alpha$を上回ることが分かった場合，範囲の下限がその評価値に更新されます．後手番局面では評価値が最小になる手を探しているので，ある局面の評価値が現在の$\beta$を下回ることが分かった場合，範囲の上限がその評価値に更新されます．先手，後手の局面は交互に現れるので，先手番局面で評価値が現在の$\beta$以上となることが明らかになった時点で，その局面に至る手は，ひとつ前の後手番局面において選択されないことになります．これを$\beta$カットと呼びその局面はそれ以上探索する必要がなくなります．後手番局面でも，現在の$\alpha$以下になることが明らかになった時点で，その局面に至る手は，ひとつ前の先手番局面において選択されないことになります．これを$\alpha$カットと呼びその局面はそれ以上探索する必要がなくなります．
/**
* 先手最善手を調べる
* @parm p 局面
* @parm m 候補手
* @return 最善手のインデックス
*/
static size_t searchMax (Position &p, Array<Move::Move, Move::Max> &m)
{
size_t idx = 0;
Eval alpha = -Infinity;
Eval beta = Infinity;
for (size_t i = 0; i < m.vsize(); ++i) {
// 局面を進める
auto back = p.move(m[i]);
// 後手局面を探索
auto value = quiesMin(p, alpha, beta, 0);
// 局面を戻す
p.undo(back);
// beta カット
if (value >= beta ) {
std::cout << "* " << value << " "
<< p.string(m[i]) << std::endl;
return i;
}
// 下限を更新
if (value > alpha) {
alpha = value;
idx = i;
std::cout << " " << value << " "
<< p.string(m[i]) << std::endl;
}
}
return idx;
}
searchMax() ではひとつだけ手を進めて後手の局面を探索する quiesMin() を呼び出します．Position による探索は先手番では次のようになります．
// 局面を進める
auto back = p.move(m[i]);
// 後手局面を探索
auto value = quiesMin(p, alpha, beta, 0);
// 局面を戻す
p.undo(back);
後手番では次のようになります．
// 局面を進める
auto back = p.move(m[i]);
// 先手局面を探索
auto value = quiesMax(p, alpha, beta, 0);
// 局面を戻す
p.undo(back);
局面を進める move() メソッドは局面を戻すのに必要な情報を返します．具体的には指した手が Move::Move 型で返ってくるのですが 上位 16 bit に取った駒が記録されています．これを undo() メソッドに渡すと move() で進めた局面を戻すことができます．
今回は駒がぶつかるときの取り合いの損得だけを評価しています．つまり genCapt() によって生成した手についてのみ探索しています．このような探索を静止探索と呼びます．ある位置に利いている駒の数が同じ場合，先に取り始めた方が損をします．したがって静止探索ではパスをしても良いこととします．
/**
* 先手番局面の静的な評価値を探索により決定する (Max)
* @parm p 局面
* @parm alpha 下限値
* @parm beta 上限値
* @parm depth 探索の深さ
* @return 評価値
*/
static Eval quiesMax (Position &p, Eval alpha, Eval beta, int depth)
{
// 評価値の初期値は静的評価値
// 上限が現在の静的評価値以下の場合探索しない
Eval vmax = p.eval();
// beta カット (standpat)
if (beta <= vmax) {
return beta;
}
// 末端なので静的評価値を返す
if (depth > _searchDepth) {
return vmax;
}
// 先手番で駒を取る手、王手を回避する手のみを生成 (ほぼ合法手)
// 該当する手がなかった場合は静的評価値がこの局面の評価値となる
Array<Move::Move, Move::Max> m;
p.genCaptB(m);
for (auto move : m) {
// 玉を取る手か
if (p.dustyB(move)) {
vmax = Infinity;
break;
}
// 局面を進める
auto back = p.move(move);
// 後手番で静止探索
auto value = quiesMin(p, max(vmax, alpha), beta, depth + 1);
// 局面を戻す
p.undo(back);
// beta カット
if (value >= beta) {
return beta;
}
// 下限更新か
if (value > vmax) {
vmax = value;
}
}
return vmax;
}
genCapt() は Pin を処理していないので生成される手に自殺手が含まれることがあります．局面を進めると玉を取る手が現れるのでこれを探索で排除します．手が玉を取るかどうかは Position クラスの dusty() メソッドにより調べることができます．玉を取る手は先手局面では $+\infty$ 後手局面では $-\infty$ と評価します．
// 玉を取る手か
if (p.dustyB(move)) {
vmax = Infinity;
break;
}
三手だけ読んでみる
駒の取り合いだけの評価ではランダムよりはましですがまだまだ弱いです．これに三手の読みを加えてみましょう．プログラムとしては静止探索とほとんど変わりません．探索する手の生成を genFast() に置き換えるだけです．三手読んだ末端で静止探索を呼び出してその局面の評価値とします．
#include <cstdlib>
#include <iostream>
#include <Shogi.h>
#include <Array.h>
#include <CSAConnection.h>
using namespace game;
using namespace foundation;
using namespace Evaluation;
/* --------------------------- global variables --------------------------- */
/// 最大の探索深さ
static int _searchDepth = 10;
/// 静止探索に入る探索深さ
static int _stableDepth = 3;
/* ------------------------------------------------------------------------- */
/* -------------------------- function prototypes -------------------------- */
/// 探索
static size_t searchMax (Position &, Array<Move::Move, Move::Max> &);
static size_t searchMin (Position &, Array<Move::Move, Move::Max> &);
static Eval searchMax (Position &, Eval alpha, Eval beta, int depth);
static Eval searchMin (Position &, Eval alpha, Eval beta, int depth);
static Eval quiesMax (Position &, Eval alpha, Eval beta, int depth);
static Eval quiesMin (Position &, Eval alpha, Eval beta, int depth);
/* ------------------------------------------------------------------------- */
/**
* 先手最善手を調べる
* @parm p 局面
* @parm m 候補手
* @return 最善手のインデックス
*/
static size_t searchMax (Position &p, Array<Move::Move, Move::Max> &m)
{
size_t idx = 0;
Eval alpha = -Infinity;
Eval beta = Infinity;
for (size_t i = 0; i < m.vsize(); ++i) {
// 局面を進める
auto back = p.move(m[i]);
// 後手局面を探索
auto value = searchMin(p, alpha, beta, 1);
// 局面を戻す
p.undo(back);
// beta カット
if (value >= beta ) {
std::cout << "* " << value << " "
<< p.string(m[i]) << std::endl;
return i;
}
// 下限を更新
if (value > alpha) {
alpha = value;
idx = i;
std::cout << " " << value << " "
<< p.string(m[i]) << std::endl;
}
}
return idx;
}
/**
* 後手最善手を調べる
* @parm p 局面
* @parm m 候補手
* @return 最善手のインデックス
*/
static size_t searchMin (Position &p, Array<Move::Move, Move::Max> &m)
{
size_t idx = 0;
Eval alpha = -Infinity;
Eval beta = Infinity;
for (size_t i = 0; i < m.vsize(); ++i) {
// 局面を進める
auto back = p.move(m[i]);
// 先手局面を探索
auto value = searchMax(p, alpha, beta, 1);
// 局面を戻す
p.undo(back);
// alpha カット
if (value <= alpha) {
std::cout << "* " << value << " "
<< p.string(m[i]) << std::endl;
return i;
}
// 上限を更新
if (value < beta ) {
beta = value;
idx = i;
std::cout << " " << value << " "
<< p.string(m[i]) << std::endl;
}
}
return idx;
}
/**
* 先手番局面の評価値を探索により決定する (Max)
* @parm p 局面
* @parm alpha 下限値
* @parm beta 上限値
* @parm depth 探索の深さ
* @return 評価値
*/
static Eval searchMax (Position &p, Eval alpha, Eval beta, int depth)
{
// 評価値の初期値
Eval vmax = -Infinity;
// 末端なので静止探索の結果を返す
if (depth > _stableDepth) {
return quiesMax(p, alpha, beta, depth);
}
// 先手番の候補手 (ほぼ合法手) を生成
// 該当する手がなかった場合は詰み (-Infinity)
Array<Move::Move, Move::Max> m;
p.genFastB(m);
for (auto move : m) {
// 玉を取る手か
if (p.dustyB(move)) {
vmax = Infinity;
break;
}
// 局面を進める
auto back = p.move(move);
// 後手番で探索
auto value = searchMin(p, max(vmax, alpha), beta, depth + 1);
// 局面を戻す
p.undo(back);
// beta カット
if (value >= beta) {
return beta;
}
// 下限更新か
if (value > vmax ) {
vmax = value;
}
}
return vmax;
}
/**
* 後手番局面の評価値を探索により決定する (Min)
* @parm p 局面
* @parm alpha 下限値
* @parm beta 上限値
* @parm depth 探索の深さ
* @return 評価値
*/
static Eval searchMin (Position &p, Eval alpha, Eval beta, int depth)
{
// 評価値の初期値
Eval vmin = Infinity;
// 末端なので静止探索の結果を返す
if (depth > _stableDepth) {
return quiesMin(p, alpha, beta, depth);
}
// 後手番の候補手 (ほぼ合法手) を生成
// 該当する手がなかった場合は詰み (Infinity)
Array<Move::Move, Move::Max> m;
p.genFastW(m);
for (auto move : m) {
// 玉を取る手か
if (p.dustyW(move)) {
vmin = -Infinity;
break;
}
// 局面を進める
auto back = p.move(move);
// 先手番で探索
auto value = searchMax(p, alpha, min(vmin, beta), depth + 1);
// 局面を戻す
p.undo(back);
// alpha カット
if (value <= alpha) {
return alpha;
}
// 上限更新か
if (value < vmin ) {
vmin = value;
}
}
return vmin;
}
/**
* 先手番局面の静的な評価値を探索により決定する (Max)
* @parm p 局面
* @parm alpha 下限値
* @parm beta 上限値
* @parm depth 探索の深さ
* @return 評価値
*/
static Eval quiesMax (Position &p, Eval alpha, Eval beta, int depth)
{
// 評価値の初期値は静的評価値
// 上限が現在の静的評価値以下の場合探索しない
Eval vmax = p.eval();
// beta カット (standpat)
if (beta <= vmax) {
return beta;
}
// 末端なので静的評価値を返す
if (depth > _searchDepth) {
return vmax;
}
// 先手番で駒を取る手、玉手を回避する手のみを生成 (ほぼ合法手)
// 該当する手がなかった場合は静的評価値がこの局面の評価値となる
Array<Move::Move, Move::Max> m;
p.genCaptB(m);
for (auto move : m) {
// 玉を取る手か
if (p.dustyB(move)) {
vmax = Infinity;
break;
}
// 局面を進める
auto back = p.move(move);
// 後手番で静止探索
auto value = quiesMin(p, max(vmax, alpha), beta, depth + 1);
// 局面を戻す
p.undo(back);
// beta カット
if (value >= beta) {
return beta;
}
// 下限更新か
if (value > vmax) {
vmax = value;
}
}
return vmax;
}
/**
* 後手番局面の静的な評価値を探索により決定する (Min)
* @parm p 局面
* @parm alpha 下限値
* @parm beta 上限値
* @parm depth 探索の深さ
* @return 評価値
*/
static Eval quiesMin (Position &p, Eval alpha, Eval beta, int depth)
{
// 評価値の初期値は静的評価値
// 下限が現在の静的評価値以上の場合探索しない
Eval vmin = p.eval();
// alpha カット (standpat)
if (alpha >= vmin) {
return alpha;
}
// 末端なので静的評価値を返す
if (depth > _searchDepth) {
return vmin;
}
// 後手番で駒を取る手、玉手を回避する手のみを生成 (ほぼ合法手)
// 該当する手がなかった場合は静的評価値がこの局面の評価値となる
Array<Move::Move, Move::Max> m;
p.genCaptW(m);
for (auto move : m) {
// 玉を取る手か
if (p.dustyW(move)) {
vmin = -Infinity;
break;
}
// 局面を進める
auto back = p.move(move);
// 先手番で静止探索
auto value = quiesMax(p, alpha, min(vmin, beta), depth + 1);
// 局面を戻す
p.undo(back);
// alpha カット
if (value <= alpha) {
return alpha;
}
// 上限更新か
if (value < vmin) {
vmin = value;
}
}
return vmin;
}
int main (int argc, char * argv[])
{
// コマンド実行時の引数確認
if (argc != 4) {
std::cerr << "Usage : "
<< argv[0]
<< "<User Name> <Password> <CSA Server>"
<< std::endl;
exit(EXIT_FAILURE);
}
// 初期化
Shogi::initialize();
// 駒の価値を設定
Position::setValue (Evaluation::Value);
Position::handsValue(Evaluation::Hands);
// CSA サーバに接続
CSAConnection csa(argv[3]);
csa.connect();
// CSA サーバにログイン
csa.login(argv[1], argv[2]);
// 対局待ち
auto summary = csa.newGame();
// 対局受諾
csa.accept();
// 局面のインスタンスを作成
Position p(summary);
// プログラムの手番を確認
auto myturn = Position::myTurn(summary);
// メッセージ受信用
Vector<std::string> message;
// 対戦
while (1) {
if (p.turn() == myturn) {
// プログラムの手番
// 指し手生成
Array<Move::Move, Move::Max> move;
p.genMove(move);
// 手が無かったら詰み
if (move.vsize() == 0) {
// 投了
csa.resign();
break;
}
// 探索の結果が最も良い手を選択する
size_t best;
if (move.vsize() > 1) {
if (myturn == Color::Black) {
best = searchMax(p, move);
} else {
best = searchMin(p, move);
}
} else {
// 手がひとつだけしかなかった場合はその手を指すしかない
best = 0;
}
// 指し手送信
csa.send(p.string(move[best]));
// 局面を進める
p.move(move[best]);
} else {
// 相手の手番
// 相手の手を待つ
csa.receive(message);
// 送信されてきた手の先頭文字が '+' '-' でないときは指し手ではない
if (message[0][0] != '+' && message[0][0] != '-') {
// 送信されてきたメッセージを表示
for (auto l : message) {
std::cout << l << std::endl;
}
break;
}
// プログラム手番の指し手 (エコー) は無視
const char turchk[] = {'+', '-'};
if (message[0][0] == turchk[myturn]) {
// 2 行目に相手の手が入る場合もある
if (message.size() == 2) {
message[0] = message[1];
} else {
continue;
}
}
// 相手の手を表示
std::cout << message[0] << std::endl;
// 局面を進める
p.move(message[0]);
}
// 局面を表示
std::cout << p << std::endl;
}
// メッセージを全て受信
while (csa.message()) {
csa.receive(message);
if (message.vsize() == 0) {
break;
}
for (auto l : message) {
std::cout << l << std::endl;
}
}
// 棋譜ファイルの書き込み
csa.write("kifu.csa");
// ログアウト
csa.logout();
// 通信終了
csa.close();
exit(EXIT_SUCCESS);
}
静止探索のみのときよりさらに強くなったのではないでしょうか．ただ指すまでに時間がかかるようにもなりました．アルファ・ベータ法はいかに早く評価値の範囲を狭めることができるかが効率化の鍵となります．そのためにはより良い評価値が得られる手から調べる必要があります．また駒の損得だけの評価よりも正確に局面を評価できるようになったら，より良い評価値が得られる局面に至るであろう手に絞って探索を行うこともできます．
まとめ
今回は Fedora 25 に最小構成で将棋プログラムを開発する環境を構築しました．そしてライブラリの基本的な使い方から出発して，最後は 3 手読むプログラムまで作成しました．次回は，特定の局面の解析，時間管理，置換表，並列探索，評価関数，ライブラリの退行テストについて投稿します．
謝辞
コンピュータ将棋に関する情報やソフトウェアを公開してくださっている全ての方々に感謝いたします．libshogi の開発にあたり lesserpyon，Bonanza，Apery，やねうら王のソースコードから多くのことを学ばせていただきました．lesserpyon3 のおかげで合法手生成のクロスチェックができました．また，コンピュータ将棋選手権では何人かの開発者の方からライブラリ作成について暖かい応援の言葉をいただきました．公式対局初のステイルメイトはカツ丼将棋さん無しには成しえなかったと思います．
あらためて皆様に感謝いたします．