libshogi で将棋プログラムを作ろう (2)
前回の記事では libshogi のインストールと基本的な使い方について紹介しました．思ったより簡単と感じていただけたのではないでしょうか．今回は以下の内容について libshogi の使用方法をご紹介します．
- ライブラリの更新
- 特定の局面の解析
- 詰将棋を解く
- 持ち時間の管理
ライブラリの更新
libshogi は GitHub で公開しています．機能追加，改善，バグフィックスが行われていますので時々更新するようにしてください．更新は前回の git clone により作成された libshogi ディレクトリで行います．
$ git status
On branch master
Your branch is up-to-date with 'origin/master'.
nothing to commit, working tree clean
$ git fetch
$ git merge origin/master
$ vi Makefile
念のために Makefile を開きインストールオプションの設定が変わっていないか確認しておきましょう．
TARGET = /usr/local
HEADDIR = $(TARGET)/include/shogi/
LIBRDIR = $(TARGET)/lib64
LIBNAME = libshogi.so.0
BMI2 = n
TLS = n
コンパイルとインストールを行います．
$ make clean
$ make
...
$ su
# make install
エラーなどでうまくいかない場合は libshogi のディレクトリを一旦削除し git clone からやり直してください．
$ git clone https://github.com/makudenki/libshogi.git
$ cd libshogi
$ vi Makefile
ライブラリを入れ替えたら作成している将棋プログラムも再コンパイルしてください．
特定の局面の解析
将棋プログラムが，ある局面でどうしてそのような手を指したのか調べたいときがあります．これを libshogi でどのように行うのかについて説明します．
局面の抽出
将棋所を使うと特定の局面を CSA 形式のテキストとしてクリップボードにコピーすることができます．解析を行いたい局面まで手を進め，編集メニューから局面指定コピーを選択します．形式は CSA 形式を選びます．
これでクリップボードに局面がコピーされましたので，その内容をテキストファイルで shogiprogram と同じディレクトリに保存します．ここでは debug.csa という名前で保存しました．
debug.csa
N+Lesserkai 1.4.1
N-test
P1-KY * -GI * * * +KI+TO *
P2 * -HI * * -KI * * * *
P3-FU-FU-KE-FU * -FU+NG * +NY
P4 * * * * -FU-KA * * *
P5 * * * * * * -FU-OU *
P6 * * * * * +KE * * *
P7+FU+FU * +FU+FU+FU+FU * *
P8+OU * * * +KI * * -UM *
P9+KY * * * +KI * * -RY *
P+00GI00KE00FU
P-00GI00KE00KY00FU00FU00FU00FU
-
前回の三手読みを行うプログラムに，解析したい局面の CSA ファイルが指定されたら，その局面の指し手を考える機能を追加します．具体的には次のように shogiprogram を実行すると debug.csa ファイルの局面から探索を行い結果を表示するようにします．
$ ./shogiprogram debug.csa
他の部分は同じですので main() のみ掲載します．
main()
#include <CSAFile.h>
int main (int argc, char *argv[])
{
Vector<std::string> message;
bool debug = false;
// 実行時引数を確認
if (argc == 2) {
// デバッグモード
debug = true;
} else
if (argc != 4) {
std::cerr << "Usage : " << std::endl
<< argv[0] << " <User Name> <Password> <CSA Server>" << std::endl
<< argv[0] << " <CSA File>" << std::endl;
exit(EXIT_FAILURE);
}
// 将棋ライブラリ初期化
Shogi::initialize();
// 駒の価値を設定
Position::setValue (Value);
Position::handsValue(Hands);
// デバッグモード
if (debug) {
// 棋譜読み込み
CSAFile k(argv[1]);
Position p(k.summary());
// 候補手作成
Array<Move::Move, Move::Max> move;
p.genMove(move);
// 解析
size_t best;
if (move.vsize() > 1) {
if (p.turn() == Color::Black) {
best = searchMax(p, move);
} else {
best = searchMin(p, move);
}
} else {
best = 0;
}
// 結果表示
std::cout << p.string(move[best]) << std::endl
<< p << std::endl;
// 終了
exit(EXIT_SUCCESS);
}
// CSA サーバへ接続
CSAConnection csa(argv[3]);
csa.connect();
// CSA サーバにログイン
csa.login(argv[1], argv[2]);
// 対局待ち
CSASummary summary = csa.newGame();
// 対局受諾
csa.accept();
// 局面のインスタンスを作成
Position p(summary);
// メッセージ受信用
std::cout << p << std::endl;
// プログラムの手番を確認
Color::Color myturn = Position::myTurn(summary);
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 turnchk[] = {'+', '-'};
if (turnchk[myturn] == message[0][0]) {
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);
}
CSA ファイルを読み込むには CSAFile.h をインクルードしてください．
#include <CSAFile.h>
プログラムに局面を解析するデバッグモードを追加します．
// 実行時引数を確認
if (argc == 2) {
// デバッグモード
debug = true;
} else
if (argc != 4) {
std::cerr << "Usage : " << std::endl
<< argv[0] << " <User Name> <Password> <CSA Server>" << std::endl
<< argv[0] << " <CSA File>" << std::endl;
exit(EXIT_FAILURE);
}
実行時の引数が一つだった場合は，CSA ファイルが指定されたものと判断し，そのファイルから局面を作ります．CSA ファイルから局面を作るには CSAFile クラスを使います．コンストラクタへファイルパスを文字列で渡すと CSA ファイルに沿った対局情報 (SASummary) を内包するインスタンスが生成されます．Position クラスのコンストラクタへ CSASummary を渡して局面のインスタンスを生成します．指定されたファイルの読み込みに失敗した場合や，CSA ファイルの構文解析に失敗した場合は CSAFile クラスから例外がスローされます．
// デバッグモード
if (debug) {
// 棋譜読み込み
CSAFile k(argv[1]);
Position p(k.summary());
局面が用意できたら，対局の時と同様に，候補手の作成と探索を行い結果を表示します．
// 候補手作成
Array<Move::Move, Move::Max> move;
p.genMove(move);
// 解析
size_t best;
if (move.vsize() > 1) {
if (p.turn() == Color::Black) {
best = searchMax(p, move);
} else {
best = searchMin(p, move);
}
} else {
best = 0;
}
// 結果表示
std::cout << p.string(move[best]) << std::endl
<< p << std::endl;
// 終了
exit(EXIT_SUCCESS);
}
これで特定の局面を探索させることができるようになりました．あとは，必要に応じてプログラムの調べたい箇所で状態を表示するコードや assert() を入れることによりデバッグを行うことができます．
棋譜の読み込み
終局までの手順を含む CSA ファイルを読み込むこともできます．この機能は学習を行うときに必要となります．棋譜ファイルを読み込み初手から再現するプログラムは次のようになります．
Main.cpp
#include <iostream>
#include <Shogi.h>
#include <CSAFile.h>
using namespace game;
using namespace foundation;
int main (int argc, char *argv[])
{
// 実行時引数を確認
if (argc != 2) {
std::cerr << "Usage : " << argv[0]
<< " <CSA File>" << std::endl;
exit(EXIT_FAILURE);
}
// 将棋ライブラリ初期化
Shogi::initialize();
// 駒の価値を設定
Position::setValue (Evaluation::Value);
Position::handsValue(Evaluation::Hands);
// 棋譜読み込み
CSAFile k(argv[1]);
// 局面のインスタンスを生成
Position p(k.summary());
std::cout << p << std::endl;
// 棋譜を再現
for (auto m : k) {
p.move(m);
std::cout << m.move << std::endl
<< p << std::endl;
}
return 0;
}
CSA 形式の棋譜ファイルには対局開始時の局面と終局までの手順が含まれます．まずファイルパスから CSAFile のインスタンスを生成します．開始局面が省略された棋譜ファイルは平手の対局として読み込まれます．
// 棋譜読み込み
CSAFile k(argv[1]);
次に CSAFile に含まれる対局情報 (CSASummary) を Position のコンストラクタに渡し開始局面を生成します．
// 局面のインスタンスを生成
Position p(k.summary());
終局までの手順は CSAFile のイテレータにより for 文で一手ずつ再現することができます．
// 棋譜を再現
for (auto m : k) {
p.move(m);
std::cout << m.move << std::endl
<< p << std::endl;
}
詰将棋を解く
CSAFile と Position は片玉の局面にも対応しています．詰将棋を解くプログラムを作ってみましょう．将棋所で局面編集から詰将棋初期局面を選ぶと片玉の詰将棋を編集することができます．
編集後は局面編集終了し編集メニューから局面指定コピーを選択します．形式は CSA 形式を選びます．クリップボードに局面がコピーされましたので，テキストファイルとして shogiprogram と同じディレクトリに保存します．ここでは tsume1.csa という名前で保存しました．
tsume1.csa
N+
N-
P1 * * * -GI-OU-GI * * *
P2 * * * * * * * * *
P3 * * * * +TO * * * *
P4 * * * * * * * * *
P5 * * * * * * * * *
P6 * * * * * * * * +KA
P7 * * * * * * * * *
P8 * * * * * * * * *
P9 * * * * * * * * *
P+00GI
P-00HI00HI00KA00KI00KI00KI00KI00GI00KE00KE00KE00KE00KY00KY00KY00KY00FU00FU00FU00FU00FU00FU00FU00FU00FU00FU00FU00FU00FU00FU00FU00FU00FU
+
CSA 形式の詰将棋ファイルを読み込んで解くプログラムは次のようになります．
Main.cpp
#include <Shogi.h>
#include <CSAFile.h>
#include <Array.h>
using namespace foundation;
using namespace game;
/* ------------------------------ parameters ------------------------------- */
// 最大手数
static const int MaxDepth = 11;
/* ------------------------------------------------------------------------- */
/* --------------------------- global variables --------------------------- */
// 手順を記録する文字列の配列
static std::string _sequence[MaxDepth + 1];
/* ------------------------------------------------------------------------- */
/* -------------------------- function prototypes -------------------------- */
// 手順を記録する
static void recordMove (int, std::string);
// 手順を表示
static void showSequence (void);
// OR ノード探索
static bool searchOr (Position &, int);
// AND ノード探索
static bool searchAnd (Position &, int);
/* ------------------------------------------------------------------------- */
/**
* 手順を記録する
* @parm index 深さ
* @parm move 指し手文字列
*/
static void recordMove (int depth, std::string move)
{
_sequence[depth ] = move;
_sequence[depth + 1].erase();
}
/**
* 手順を表示する
*/
static void showSequence (void)
{
for (auto str : _sequence) {
if (str.size() == 0) {
break;
}
std::cout << str << " ";
}
std::cout << std::endl;
}
/**
* OR ノード探索
* @parm p 局面
* @parm depth 探索深さ
*/
static bool searchOr (Position &p, int dx)
{
// 探索末端
if (dx >= MaxDepth) {
return false;
}
// 王手生成
Array<Move::Move, Move::Max> m;
p.genChckB(m);
p.minorMove(m);
// 候補手数
int nmove = (int) m.vsize();
// 不詰み (王手がない)
if (nmove == 0) {
return false;
}
for (auto move : m) {
// 手順を記録
recordMove(dx, p.string(move));
// 局面を進める
auto back = p.move(move);
// AND 局面を探索
auto result = searchAnd(p, dx + 1);
// 局面を戻す
p.undo(back);
// 詰みを見つけた
if (result) {
return true;
}
}
return false;
}
/**
* AND ノード探索
* @parm p 局面
* @parm depth 探索深さ
*/
static bool searchAnd (Position &p, int dx)
{
// 探索末端
if (dx >= MaxDepth) {
return false;
}
// 王手に対する応手を生成
Array<Move::Move, Move::Max> m;
p.genMoveW(m);
p.minorMove(m);
// 候補手数
int nmove = (int) m.vsize();
// 詰み (応手がない)
if (nmove == 0) {
// 打ち歩詰めチェック
if (p.uchifuzume()) {
return false;
} else {
return true;
}
}
for (auto move : m) {
// 手順を記録
recordMove(dx, p.string(move));
// 局面を進める
auto back = p.move(move);
// OR 局面を探索
auto result = searchOr(p, dx + 1);
// 局面を戻す
p.undo(back);
// 不詰みを見つけた
if (! result) {
return false;
}
}
return true;
}
int main (int argc, char * argv[])
{
// 実行時引数を確認
if (argc != 2) {
std::cerr << "Usage : "
<< argv[0] << " <CSA File>" << std::endl;
exit(EXIT_FAILURE);
}
// 将棋ライブラリ初期化
Shogi::initialize();
// 駒の価値を設定
Position::setValue (Evaluation::Value);
Position::handsValue(Evaluation::Hands);
// 棋譜読み込み
CSAFile k(argv[1]);
// 局面のインスタンスを生成
Position p(k.summary());
std::cout << p << std::endl;
// 探索
auto result = searchOr(p, 0);
// 結果表示
if (! result) {
std::cout << "Fzumi!" << std::endl;
} else {
showSequence();
}
exit(EXIT_SUCCESS);
}
コンパイルして実行します．
$ make
$ ./shogiprogram tsume1.csa
Hash : 0x7f63929888371999 Hand: 0x30d45f7fe6181cb3 Board: 0x4fb7cde76e2f052a
Exchange: -8000
Hand : FU17 KY04 KE04 GI01 KA01 HI02 KI04
9 8 7 6 5 4 3 2 1
+----------------------------+
| GI OU GI | 1
| | 2
| TO | 3
| | 4
| | 5
| KA | 6
| | 7
| | 8
| | 9
+----------------------------+
Hand : GI01
+1652UM -6152GI +0062GI
結果は CSA 形式で表示されます．5二角成，同銀，6二銀打と詰め手順が示されました．プログラムを見てみましょう．棋譜ファイルの読み込みは CSAFile クラスを使用します．
// 棋譜読み込み
CSAFile k(argv[1]);
// 局面のインスタンスを生成
Position p(k.summary());
std::cout << p << std::endl;
局面が用意できたら攻め方が手番の局面を探索する searchOr() を呼び出します．
auto result = searchOr(p, 0);
詰将棋では攻め方と玉方の手を交互にシミュレートして詰みに至る手順を探索します．攻め方が手番の局面は，配下に「詰み」局面一つでもあれば「詰み」であると証明することができます．一方，玉方が手番の局面は，配下の局面が全て「詰み」でなければ「詰み」となりません．searchOr() は局面が詰みであれば true を返します．
searchOr()
static bool searchOr (Position &p, int dx)
{
// 探索末端
if (dx >= MaxDepth) {
return false;
}
// 王手生成
Array<Move::Move, Move::Max> m;
p.genChckB(m);
p.minorMove(m);
// 候補手数
int nmove = (int) m.vsize();
// 不詰み (王手がない)
if (nmove == 0) {
return false;
}
for (auto move : m) {
// 手順を記録
recordMove(dx, p.string(move));
// 局面を進める
auto back = p.move(move);
// AND 局面を探索
auto result = searchAnd(p, dx + 1);
// 局面を戻す
p.undo(back);
// 詰みを見つけた
if (result) {
return true;
}
}
return false;
}
プログラムでは探索の深さに上限を設けています．攻め方，玉方いずれの局面であっても，探索の上限に達したときは不詰み false を返します．
// 探索末端
if (dx >= MaxDepth) {
return false;
}
searchOr() では王手のみを生成し展開します．先手番で王手を生成するには genChckB() を呼び出します．創作された詰将棋では大駒の不成を趣向としたものがあるので直後に minorMove() を呼び出し，歩，大駒の不成も手として生成します．genChck() 系の指し手生成を行った直後の minorMove() は王手のみを生成します．
// 王手生成
Array<Move::Move, Move::Max> m;
p.genChckB(m);
p.minorMove(m);
王手がなければ不詰みなので false を返します．
// 候補手数
int nmove = (int) m.vsize();
// 不詰み (王手がない)
if (nmove == 0) {
return false;
}
王手があればそれぞれの手で局面を進めて，玉方の searchAnd() を呼び出します．searchAnd() から true が返ってきたら「詰み」なので true を返して終了します．
// 手順を記録
recordMove(dx, p.string(move));
// 局面を進める
auto back = p.move(move);
// AND 局面を探索
auto result = searchAnd(p, dx + 1);
// 局面を戻す
p.undo(back);
// 詰みを見つけた
if (result) {
return true;
}
玉方の局面を評価する searchAnd() は王手を回避する手を探索します．
searchAnd()
static bool searchAnd (Position &p, int dx)
{
// 探索末端
if (dx >= MaxDepth) {
return false;
}
// 王手に対する応手を生成
Array<Move::Move, Move::Max> m;
p.genMoveW(m);
p.minorMove(m);
// 候補手数
int nmove = (int) m.vsize();
// 詰み (応手がない)
if (nmove == 0) {
// 打ち歩詰めチェック
if (p.uchifuzume()) {
return false;
} else {
return true;
}
}
for (auto move : m) {
// 手順を記録
recordMove(dx, p.string(move));
// 局面を進める
auto back = p.move(move);
// OR 局面を探索
auto result = searchOr(p, dx + 1);
// 局面を戻す
p.undo(back);
// 不詰みを見つけた
if (! result) {
return false;
}
}
return true;
}
王手に対する応手を生成する以外は searchOr() とほとんど同じです．応手が無いときは詰みですが，直前の手が歩打ちの場合は攻め方の反則となります．libshogi では手生成時に打ち歩詰めのチェックを行いません．詰みの局面に遭遇した時点で直前の手が歩打ちだったかどうかを確認するためのメソッド bool uchifuzume() を用意しています．
// 王手に対する応手を生成
Array<Move::Move, Move::Max> m;
p.genMoveW(m);
p.minorMove(m);
// 候補手数
int nmove = (int) m.vsize();
// 詰み (応手がない)
if (nmove == 0) {
// 打ち歩詰めチェック
if (p.uchifuzume()) {
return false;
} else {
return true;
}
}
長手順の詰将棋を解くには，証明数，反証数という考え方を導入した手法が用いられます．証明数は，その局面が詰みであることを証明するために詰みであると証明しなければいけない最小の子局面数です．反証数は，その局面が不詰みであることを証明するために，不詰みであると証明しなければいけない最小の子局面数です．証明数，反証数を用いることにより子局面に優劣をつけることができるようになるので，最も有力な子局面を展開し探索を行います．証明数 (反証数) が次に有力な局面の証明数を上回ったら戻るということを繰り返しながら，少しずつ探索を深くしていきます．
証明数と反証数を使用したゲーム木探索については GAME-TREE SEARCH USING PROOF NUMBERS: THE FIRST TWENTY YEARS (金子,Winands, Müller,Saito) に詳しく書かれています．
ソースコードツリーの libshogi/example/dfpn に証明数と反証数を使った詰将棋プログラムの例を用意しました．コンパイルして実行してみましょう．libshogi ディレクトリへ移動します．
$ cd example/dfpn
$ make
将棋図巧第3番 (45 手詰め) を解かせてみましょう．
$ ./shogiprogram zuko03.csa
Hash Size : 384MiB
Hash : 0x375b21faa8b31a23 Hand: 0xfca3efb94ef51ef4 Board: 0xcbf8ce43e64604d7
Exchange: -2000
Hand : FU05 KY02 KE01 GI02 KI01
9 8 7 6 5 4 3 2 1
+----------------------------+
| FU KI TO | 1
| FU FU FU FU | 2
| KY FU KI GI RY | 3
| FU KA FU TO | 4
| FU KY | 5
| OU KE | 6
| | 7
| UM | 8
| HI | 9
+----------------------------+
Hand : FU02 KE02 GI01 KI01
Hash Utilization : 276439/16777233
pn = 0
dn = Inf
+0077GI -8695OU +0096KI -9594OU +0086KE -8986HI +9685KI -8685HI +0095FU
-9495OU +0096FU -9594OU +0086KE -8586HI +9695FU -9495OU +7786GI -9586OU
+0083HI -8676OU +8385RY -7666OU +8555RY -6655OU +7856UM -5564OU +5665UM
-6473OU +7483UM -7363OU +6574UM -6354OU +7465UM -5463OU +8374UM -6372OU
+0073FU -7261OU +6543UM -0052HI +4151TO -6151OU +3342GI -5161OU +4352UM
-5352KI +0051KI -5251KI +4251NG -6151OU +0041KI -5161OU +4151KI -6151OU
+0041HI
最短手順ではありませんが詰みであることが確認できました．
持ち時間の管理
指定した時間で探索を打ち切るには，メインスレッドが行う探索と並列に時間管理スレッドを起動しておき，指定した時間が経過したらそのスレッドに通知させるようにします．libshogi ではスレッドの生成，実行，結果の取得を行うための Thread<T,V> テンプレートクラスが用意されています．テンプレート変数の T はスレッドへの引数の型，V はスレッドからの戻り値の型です．スレッドから時間の経過を知らせるにはアトミック変数を使用します．
Main.cpp
#include <unistd.h>
#include <cstdlib>
#include <iostream>
#include <Shogi.h>
#include <Array.h>
#include <Atomic.h>
#include <Thread.h>
#include <CSAConnection.h>
#include <CSAFile.h>
using namespace game;
using namespace foundation;
using namespace Evaluation;
/* ------------------------------ parameters ------------------------------- */
/// 最大思考時間
static const time_t ThinkingTime = 10;
/* ------------------------------------------------------------------------- */
/* --------------------------- global variables --------------------------- */
/// 最大の探索深さ
static int _searchDepth = 10;
/// 静止探索に入る探索深さ
static int _stableDepth = 3;
/// 探索終了通知用セマフォ
template <typename T, typename V>
Semaphore Thread<T, V>::globalSync;
/// 探索終了通知用アトミック変数
static Atomic<int> _stopSearch(0);
/* ------------------------------------------------------------------------- */
/* -------------------------- 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);
/* ------------------------------------------------------------------------- */
// タイマースレッド
class threadTimer : public Thread<int, time_t>
{
public:
// 時計を見る間隔 [nsec]
static const long PollingInterval = 50000000L;
// タイマースレッドの優先度 (最高)
static const int Priority = -21;
threadTimer () :
Thread<int, time_t> ()
{
_itval.tv_sec = 0;
_itval.tv_nsec = PollingInterval;
}
void run (time_t t)
{
// 探索終了通知用アトミック変数をリセット
_stopSearch.set(0);
// スレッド起動
Thread<int, time_t>::run(t);
}
void stop (void)
{
_stopSearch.set(1);
}
private:
time_t _limit;
struct timespec _itval;
struct timespec _rmain;
int _thread (time_t t)
{
// 優先度設定
if (nice(Priority) == -1) {
perror("nice()");
}
// タイマー発動時間を計算
_limit = time(NULL) + t;
while (_limit > time(NULL)) {
_rmain = _itval;
while (nanosleep(&_rmain, &_rmain) == -1);
if (_stopSearch == 1) {
break;
}
}
// 探索終了通知用アトミック変数をセット
_stopSearch.set(1);
return 0;
}
};
/**
* 先手最善手を調べる
* @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 (_stopSearch == 1) {
return beta;
}
// 末端なので静止探索の結果を返す
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 (_stopSearch == 1) {
return alpha;
}
// 末端なので静止探索の結果を返す
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;
}
// 終了通知があるか
if (_stopSearch == 1) {
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;
}
// 終了通知があるか
if (_stopSearch == 1) {
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[])
{
Vector<std::string> message;
bool debug = false;
// 実行時引数を確認
if (argc == 2) {
// デバッグモード
debug = true;
} else
if (argc != 4) {
std::cerr << "Usage : " << std::endl
<< argv[0] << "<User Name> <Password> <CSA Server>" << std::endl
<< argv[0] << "<User Name> <CSA File>" << std::endl;
exit(EXIT_FAILURE);
}
// 将棋ライブラリ初期化
Shogi::initialize();
// 駒の価値を設定
Position::setValue (Value);
Position::handsValue(Hands);
// デバッグモード
if (debug) {
// 棋譜読み込み
CSAFile k(argv[1]);
Position p(k.summary());
// 候補手作成
Array<Move::Move, Move::Max> move;
p.genMove(move);
// 解析
size_t best;
if (move.vsize() > 1) {
if (p.turn() == Color::Black) {
best = searchMax(p, move);
} else {
best = searchMin(p, move);
}
} else {
best = 0;
}
// 結果表示
std::cout << p.string(move[best]) << std::endl
<< p << std::endl;
// 終了
exit(EXIT_SUCCESS);
}
// CSA サーバへ接続
CSAConnection csa(argv[3]);
csa.connect();
// CSA サーバにログイン
csa.login(argv[1], argv[2]);
// 対局待ち
CSASummary summary = csa.newGame();
// 対局受諾
csa.accept();
// 局面のインスタンスを作成
Position p(summary);
// メッセージ受信用
std::cout << p << std::endl;
// プログラムの手番を確認
Color::Color myturn = Position::myTurn(summary);
while (1) {
// プログラムの手番かどうか
if (p.turn() == myturn) {
// プログラムの手番
// 候補手作成
Array<Move::Move, Move::Max> move;
p.genMove(move);
// 詰み確認 - 指せる手がない場合は詰み
if (move.vsize() == 0) {
// 投了
csa.resign();
break;
}
// タイマースレッド起動
threadTimer timer;
timer.run(ThinkingTime);
// 探索の結果が最も良い手を選択する
//
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]);
// タイマースレッド終了
timer.stop();
timer.sync();
} else {
// 相手の手番
// 相手の手を待つ
csa.receive(message);
// 先頭文字が '+' '-' でないときは指し手ではない
if (message[0][0] != '+' && message[0][0] != '-') {
// 送信されてきたメッセージを表示
for (auto l : message) {
std::cout << l << std::endl;
}
break;
}
// プログラムの手はスキップ
const char turnchk[] = {'+', '-'};
if (turnchk[myturn] == message[0][0]) {
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);
}
スレッドは Thread<T,V> テンプレートクラスを継承したクラスとして定義します．
threadTimer
// タイマースレッド
class threadTimer : public Thread<int, time_t>
{
public:
// 時計を見る間隔 [nsec]
static const long PollingInterval = 50000000L;
// タイマースレッドの優先度 (最高)
static const int Priority = -21;
threadTimer () :
Thread<int, time_t> ()
{
_itval.tv_sec = 0;
_itval.tv_nsec = PollingInterval;
}
void run (time_t t)
{
// 探索終了通知用アトミック変数をリセット
_stopSearch.set(0);
// スレッド起動
Thread<int, time_t>::run(t);
}
void stop (void)
{
_stopSearch.set(1);
}
private:
time_t _limit;
struct timespec _itval;
struct timespec _rmain;
int _thread (time_t t)
{
// 優先度設定
if (nice(Priority) == -1) {
perror("nice()");
}
// タイマー発動時間を計算
_limit = time(NULL) + t;
while (_limit > time(NULL)) {
_rmain = _itval;
while (nanosleep(&_rmain, &_rmain) == -1);
if (_stopSearch == 1) {
break;
}
}
// 探索終了通知用アトミック変数をセット
_stopSearch.set(1);
return 0;
}
};
スレッドとして実行される関数は Thread<T,V> テンプレートクラスにおいて純粋仮想関数 V _thread(T) として定義されています．threadTimer を定義するときにテンプレート変数で指定した型の通り int _thread(time_t) でスレッド関数を定義します．
時間管理スレッドは探索を行うスレッドよりも高い優先度を持つ必要があります．そこで nice(Priority) で優先度を高くしています．Linux ではデフォルトの優先度が 0 で，高くするには root 権限が必要です．将棋プログラムを実行するために root 権限になりたくないという方もおられるかもしれません．マルチスレッド並列探索を行うのであれば探索スレッドの優先度を低くすることにより相対的に時間管理スレッドの優先度を高くすることができます．
また，時間管理スレッドは，停止可能でなければいけません．決まった間隔でシステムの時計を確認し，指定された時間が経過したら通知を行うという形態をとります．
// タイマー発動時間を計算
_limit = time(NULL) + t;
while (_limit > time(NULL)) {
_rmain = _itval;
while (nanosleep(&_rmain, &_rmain) == -1);
if (_stopSearch == 1) {
break;
}
}
時計を確認する間隔を小さくすればより細かい時間管理が可能となりますが，スレッドが消費する CPU 時間も多くなります．探索スレッドへの通知はアトミック変数をセットすることにより行います．
// 探索終了通知用アトミック変数をセット
_stopSearch.set(1);
探索スレッドでは _stopSearch の値が 1 になったら探索を強制終了します．サンプルプログラムでは先手番局面において $\beta$ 値，後手番局面において $\alpha$ 値を返すようにしています．
searchMax()
...
// 終了通知があるか
if (_stopSearch == 1) {
return beta;
}
...
searchMin()
...
// 終了通知があるか
if (_stopSearch == 1) {
return alpha;
}
...
静止探索では現局面での静的な評価値 (このプログラムでは駒の損得) を返すようにしています．
quiesMax()
...
// 終了通知があるか
if (_stopSearch == 1) {
return vmax;
}
...
quiesMin()
...
// 終了通知があるか
if (_stopSearch == 1) {
return vmin;
}
...
ここでは，スレッドクラスの使用方法と単純な時間管理の方法を紹介しました．しかし，単純に探索を強制終了すると即負けにつながるようなひどい手を選んでしまうことがあります．実用的には少しずつ探索を深くする反復深化を行うなどして，短い時間なりの品質を持った手を選択できるように工夫する必要があります．
おわりに
libshogi の使い方について，ライブラリのアップデート，特定局面の解析，時間管理の方法などについて紹介しました．次回以降の記事では次の内容についてライブラリの使い方を紹介できればと考えています．
- 置換表の実装
- 並列探索の実装
- 評価関数の実装
- ライブラリの退行テスト
ありがとうございました．