人は駒得のみに生くるにあらず
「駒得のみでもトップの将棋ソフトと500点差ぐらいにはなるよ」ということを某所で聞いたので、やってみました。
もちろん「駒得のみでも」というのは、前提としてトップソフトから評価関数だけを駒得のみのものに差し替えたときであって、すなわち「指し手生成などはギリギリまでチューンして、なおかつ、Bonanzaなどでされている各種枝刈りの技法を適用すれば」ということだと思うのですが、ここでは、枝刈りなし！置換表なし！静止探索なし！男は黙ってαβ！という男っぷり。
しかし、せめて指し手生成ぐらいは最速のもので試してみたかったので、某氏からパクってきた拝借してきた、世界最速の指し手生成ルーチンとやらで試してみました。
対戦相手はLesserkaiです。Lesserkaiは4手読みで、駒得に加えて簡単な位置評価をしているようです。2駒関係と言っていいかも知れません。
こちらは、純粋なαβ法です。それ以上の何もしていません。以下にソースを載せておきます。
いずれオープンソースにしようと鋭意開発中の「ひよこ将棋フレームワーク」を用いており、以下のソースは擬似コードでも何でもなく、αβ探索だけならば以下のように30行程度書くだけで将棋所で遊べる将棋ソフトが出来てしまうという、なかなか優れもののフレームワークです。
// 駒得だけの評価関数でどこまで強くなるのかのテスト
struct MyShogi : public USIListener
{
virtual void OnProgramName() { printf("HiyokoShogi 0.0.1"); }
virtual void OnAuthorName() { printf("hiyoko-chan"); }
virtual Tree* GetTree() { return &fw.trees[0]; }
virtual Move OnThink()
{
// 試しにαβ探索を実装してみよう。
PV[0] = MOVE_NA;
AlphaBetaSearch(GetTree(),-score_bound , +score_bound , 7); // 7手
return PV[0];
}
// αβ探索。depth = 探索残り深さ
// 現在の探索深さ自体は、tree->plyに入っている。
static Score AlphaBetaSearch(Tree* RESTRICT tree , Score alpha,Score beta,Ply depth)
{
if (depth == 0)
{
tree->node_searched++; // 探索ノード数を加算
return TURN == black ? tree->board.material : - tree->board.material; // 現在の駒割
}
GenMoveAll(tree);
Move* pMove = MOVE_LAST;
Move* pEnd = MOVE_CURRENT;
for( ; pMove != pEnd ; ++pMove)
{
Move move = *pMove;
if (MakeMove::make_move_pin_check(tree,move))
continue;
// 空き王手を食らった == 非合法手
// なので、局面を進めずに次の手に。
tree->inc_ply(); // 手番反転、指し手生成バッファを次の深さに。
Score score = -AlphaBetaSearch(tree, -beta , -alpha , depth - 1);
tree->dec_ply(); // inc_plyの逆操作。
MakeMove::unmake_move(tree,move);
if ( score > alpha)
{
alpha = score;
PV[tree->ply] = move; // これがbest move..のはず..
}
if ( alpha >= beta )
return alpha; // alpha cut
}
return alpha;
}
// ベストな指し手(読み筋)
static Move PV[PLY_MAX];
MyShogi(HiyokoShogiFramework& f) : fw(f) {}
private:
HiyokoShogiFramework& fw;
};
void hiyoko_main(HiyokoShogiFramework& fw)
{
MyShogi shogi(fw);
fw.usi.main(&shogi);
}ちなみに駒の価値についてはBonanza 6.0の定数を使用させていただきました。
さて…衝撃の対戦結果なのですが…こちらの探索深さ5手ですとボロ負け。
こちらは思考時間制御はしておらず、こちらの思考時間はLesserkaiの2倍ぐらい使っています。
しかし探索速度は、序盤で5Mnps、終盤で15Mnps〜20Mnps程度出ています。一瞬、自分の目を疑いましたが。
シングルスレッドで、MacBook Airでこれだけ出るとは、さすが世界最速の指し手生成ルーチンと言わざるを得ません。終盤でnpsが上がるのはこの指し手生成ルーチンはgen_drop(駒打ち)の生成が大変速いのが影響しているのでしょう。
もう少し探索深さを深くしても現実的な時間で思考できそうでしたので、探索深さを7手にしてみました。
しかし終盤ではみるみるうちに時間を使い果たし(駒打ちがあるので探索深さ固定だと調べるノード数が序盤より多くなる)、気がつけばLesserkaiの20倍ぐらい時間を消費しています。探索速度30倍×20倍=600倍!!
以下図の局面のあと、Lesserkaiを56桂〜同金以下の即詰みに討ちとりました。
評価関数が駒得のみで、純粋αβで、それ以上の枝刈りもせず、置換表も静止探索も何もなくとも600倍探索すればLesserkaiと互角になるのだということが今回の調査でわかりました。(誰も知りたくもない？)
以下に棋譜を掲載しておきます。
せっかくなので、次回は、もう少し枝刈りを頑張ってみます。置換表なしでももう少し枝刈りを頑張れば、A級リーグ指し手一号(FPGAを使用したコンピューター将棋)と同等(探索速度と枝刈りの手法において)程度にはなるはずですので、レーティングで言うとR1500程度になると期待していいのだと思います…が…果たしてどうなのでしょうか。
誰も期待もしていない駒得のみの評価関数の将棋ソフト「ひよこ将棋」の進化はまだまだ続く!!
# KIF形式棋譜ファイル
# Generated by Shogidokoro
手合割：平手
先手：Lesserkai 1.3.3
後手：HiyokoShogi 0.0.1
手数----指手---------消費時間--
1 ７六歩(77) (00:01 / 00:00:01)
2 ９四歩(93) (00:01 / 00:00:01)
3 ７八金(69) (00:01 / 00:00:02)
4 ８四歩(83) (00:01 / 00:00:02)
5 ６八銀(79) (00:01 / 00:00:03)
6 ５四歩(53) (00:01 / 00:00:03)
7 ７七銀(68) (00:01 / 00:00:04)
8 ７四歩(73) (00:01 / 00:00:04)
9 ６八玉(59) (00:01 / 00:00:05)
10 ７三桂(81) (00:01 / 00:00:05)
11 ８六歩(87) (00:01 / 00:00:06)
12 ３四歩(33) (00:01 / 00:00:06)
13 ５八金(49) (00:01 / 00:00:07)
14 ８五歩(84) (00:02 / 00:00:08)
15 同 歩(86) (00:01 / 00:00:08)
16 同 飛(82) (00:03 / 00:00:11)
17 ９六歩(97) (00:01 / 00:00:09)
18 ６五桂(73) (00:55 / 00:01:06)
19 ６六銀(77) (00:01 / 00:00:10)
20 ８七歩打 (00:17 / 00:01:23)
21 ９七角(88) (00:01 / 00:00:11)
22 ９五歩(94) (00:02 / 00:01:25)
23 ８六歩打 (00:01 / 00:00:12)
24 ９六歩(95) (00:01 / 00:01:26)
25 ８五歩(86) (00:01 / 00:00:13)
26 ９七歩成(96) (00:01 / 00:01:27)
27 ５三飛打 (00:01 / 00:00:14)
28 ５二金(61) (00:01 / 00:01:28)
29 ５四飛成(53) (00:01 / 00:00:15)
30 ８八歩成(87) (00:02 / 00:01:30)
31 同 金(78) (00:01 / 00:00:16)
32 ５七桂成(65) (00:03 / 00:01:33)
33 同 龍(54) (00:01 / 00:00:17)
34 ８八と(97) (00:01 / 00:01:34)
35 ９一香成(99) (00:01 / 00:00:18)
36 ７九角打 (00:57 / 00:02:31)
37 ５九玉(68) (00:01 / 00:00:19)
38 ５七角成(79) (00:08 / 00:02:39)
39 同 銀(66) (00:02 / 00:00:21)
40 ８九と(88) (00:28 / 00:03:07)
41 ７三角打 (00:02 / 00:00:23)
42 ６二銀(71) (00:13 / 00:03:20)
43 ４六角成(73) (00:02 / 00:00:25)
44 ７九飛打 (01:35 / 00:04:55)
45 ６九桂打 (00:01 / 00:00:26)
46 ７七桂打 (00:52 / 00:05:47)
47 ４八玉(59) (00:01 / 00:00:27)
48 ６九飛成(79) (00:13 / 00:06:00)
49 ３八銀(39) (00:01 / 00:00:28)
50 ５五金打 (02:54 / 00:08:54)
51 ５三歩打 (00:01 / 00:00:29)
52 ４六金(55) (00:02 / 00:08:56)
53 ５二歩成(53) (00:01 / 00:00:30)
54 同 玉(51) (00:05 / 00:09:01)
55 ５四香打 (00:01 / 00:00:31)
56 ６一玉(52) (00:03 / 00:09:04)
57 ５二金打 (00:01 / 00:00:32)
58 同 金(41) (00:01 / 00:09:05)
59 同 香成(54) (00:01 / 00:00:33)
60 同 玉(61) (00:05 / 00:09:10)
61 ５九金打 (00:01 / 00:00:34)
62 ５七金(46) (01:04 / 00:10:14)
63 同 金(58) (00:01 / 00:00:35)
64 ５六桂打 (02:45 / 00:12:59)
