ただスクラッチ開発なだけの将棋ソフトってそんなに偉いんですか？ 第二回
前回のあらすじ
コンピュータ将棋界隈の一部に存在するとても奇妙なフルスクラッチ信仰について紹介した。コンピュータ将棋界隈では、アイディア的独自性のないただフルスクラッチであるプログラムが偉く、ライブラリ勢を不愉快と思う人が一定数いたり、フルスクラッチを標榜しながらチェスソフトのコードを流用しているという、最早何がフルスクラッチなのか意味不明なソフトもある、と言った具合である。
そこでフルスクラッチのコンピュータ将棋ソフトがそんなに偉いのかを検証するため自分でルール通りに指せるだけのゴミのようなコンピュータ将棋プログラムを他のソースコードを見ないルールで９時間ほどかけて作ってみた。
ルール通りに将棋を指せるだけのゴミプログラムをコンピュータ将棋ソフトと言い張るのは憚られるため、今回はそのコンピュータ将棋ソフトをある程度強化するのが趣旨である。
前回からの改良点
今週末あまり時間が取れなさそうだったので、先週の日曜に動くものが完成したところから、平日夕飯を作って食べた後に時間を取って少しずつ改造した。
SEE
まず単純なアルファベータ５手読みだと６手後に駒が取られるような指し手が読めないため末端ノードの評価値がすごく怪しくなる。せめて最後の指し手から駒の取り合いだけは考えた評価値を出すためにStatic Exchange Evaluation(SEE)をチェスプログラミングwiki*1を斜め読みしながら実装してみた。
駒の利きを列挙しなきゃいけないので結構長くなる（まあコピペなので時間はかからないが。）実装したが、なんか駒をタダ捨てし始める。おかしい。
取って不利になる場合は取っちゃダメなんだ。（たとえば相手が最後に歩を動かしたあとに飛車で取るムーブは飛車が取られる場合やると損）max(0, see)とかすればいいのかな。
違うわ、それぞれの手番の人が取るか取らないか決定できるから、後ろからネガマックスするように書けばいいのか。
Transposition Table
PVを出力してないので、変な指し手を出力したところで何がなんだかわからない。というわけでPVを出力するためにTransposition Table（置換表）を実装しよう。
Transposition Tableを実装するためにはなんかハッシュが必要である。Zobrist Hashって奴だ。これを実装しないといけない。
そのためには局面のundoをできるようにしないといけない*2。結構メンドイ。
Transposition Tableは普通に開番地法のハッシュテーブルでいいでしょ。まあ面倒とは言ってもundoとZobrist Hashは愚直に書くだけ。undoもZobrist Hashもどっちもユニットテストできるからバグも入れないだろうし。
Quiescence Search
SEEだけ入れても評価値が全然ガタガタだ。Quiescence Search（静止探索とか邦訳されている）も入れないとだめか。
チェスプログラミングwikiを見ながら書く。駒を取る手を生成してあとは疑似コードほぼそのままでよし。
動きがメチャクチャになった…… depth = 0のときに-quiescence(-beta, -alpha)呼ぶのはおかしいだろ、符号が逆。直す。
てか探索部のデバッグくそめんどくせーな。ユニットテストができないから一回指してみるしかない。また飛車をタダ捨てする。quiescence(-beta, -alpha)にしてたわ。quiescence(alpha, beta)じゃんね。
まだ飛車をタダ捨てする。３手前から指すとタダ捨てして、直前から指すとしない。Transposition Tableがバグってるに違いない。あ、前回ベータカットした指し手の評価値をlower bound以外の値が必要なところで使っちゃったらそらこうなるか。
修正したら指し手がかなりまともになった。４手読み相手に何回か指したが大駒取られて１回負けた。
Quiescence SearchはSEEなんかよりずっとコードも短いのに凄い効果あるな。
第二回のまとめと今後の修正点
Quiescence Searchは簡単ですごい効果ある。今のところ３級くらいの強さ？
次は評価関数をまともにする。機械学習で適当に値をつけたら超適当に決めた駒割のみの現在の評価関数よりは流石にまともになるでしょう。とは言えやねうらお氏がひまうら王の評価関数を駒割から改善するのにすごく苦労してた*3から難しいのかもしれない。
あと５手読みの時点で遅すぎるからちょっと前向き枝刈りを入れたほうがよいのかも。ただ探索部デバッグしにくすぎるからな。
とりあえず、フルスクラッチ勢に対する見方が変わったかと言うと、相変わらず、フルスクラッチ、だから何？万年一次予選敗退のプログラムでもフルスクラッチだからって理由でマウント取れるの流石に意味わかんねーわ*4という感じ。
具体的出典を出すのは差し控えるが、フルスクラッチ勢の中には「ライブラリを使用した参加者の本音は『ライブラリがないと勝てない、ライブラリがないと楽ができなくなる』といった卑怯なものだ」といったわけのわからない非難をする向きもある。
仕事でエクセルのマクロを使うのはずるいレベルの話だ。そもそもプログラマが開発で楽をできないのは能力がないと見なされるし、大体そんなに人の作ったものを使うのがずるくて、無駄な苦労がしたいならC++言語のコンパイラから自作したらいいんじゃないですかね？そしてそもそもこの人はチェスソフトを流用した探索部を作っているのである。
おまけ
shogi686micro*5と対局させてみた。勝ったり負けたりのようだ。
# Generated by Shogidokoro
手合割：平手
先手：fs_shogi_with_qs
後手：shogi686micro
手数----指手---------消費時間--
1 ９六歩(97) (00:01 / 00:00:01)
2 ５二金(41) (00:01 / 00:00:01)
3 ９五歩(96) (00:01 / 00:00:02)
4 ６四歩(63) (00:01 / 00:00:02)
5 ９六香(99) (00:01 / 00:00:03)
6 ６五歩(64) (00:01 / 00:00:03)
7 ８六歩(87) (00:01 / 00:00:04)
8 ７二銀(71) (00:01 / 00:00:04)
9 ８五歩(86) (00:01 / 00:00:05)
10 ９二香(91) (00:01 / 00:00:05)
11 ７六歩(77) (00:01 / 00:00:06)
12 ８四歩(83) (00:01 / 00:00:06)
13 同 歩(85) (00:01 / 00:00:07)
14 同 飛(82) (00:01 / 00:00:07)
15 ７八金(69) (00:01 / 00:00:08)
16 ８六歩打 (00:01 / 00:00:08)
17 ８五歩打 (00:01 / 00:00:09)
18 同 飛(84) (00:01 / 00:00:09)
19 ７七金(78) (00:01 / 00:00:10)
20 ８七歩成(86) (00:01 / 00:00:10)
21 ９七桂(89) (00:01 / 00:00:11)
22 ８四飛(85) (00:01 / 00:00:11)
23 ８七金(77) (00:01 / 00:00:12)
24 同 飛成(84) (00:01 / 00:00:12)
25 ８二歩打 (00:01 / 00:00:13)
26 ９六龍(87) (00:01 / 00:00:13)
27 ８一歩成(82) (00:01 / 00:00:14)
28 ８四香打 (00:01 / 00:00:14)
29 ５五角(88) (00:01 / 00:00:15)
30 ９七龍(96) (00:01 / 00:00:15)
31 ８二と(81) (00:01 / 00:00:16)
32 ５四歩(53) (00:01 / 00:00:16)
33 ４六角(55) (00:01 / 00:00:17)
34 ９九龍(97) (00:01 / 00:00:17)
35 ５六歩(57) (00:01 / 00:00:18)
36 ８九香成(84) (00:01 / 00:00:18)
37 ７二と(82) (00:01 / 00:00:19)
38 同 金(61) (00:01 / 00:00:19)
39 ８四桂打 (00:02 / 00:00:21)
40 ８三金(72) (00:01 / 00:00:20)
41 ９二桂成(84) (00:01 / 00:00:22)
42 ７九成香(89) (00:01 / 00:00:21)
43 ８二銀打 (00:06 / 00:00:28)
44 ７八成香(79) (00:01 / 00:00:22)
45 ５八玉(59) (00:01 / 00:00:29)
46 ６九龍(99) (00:01 / 00:00:23)
47 ４八玉(58) (00:01 / 00:00:30)
48 ４五金打 (00:01 / 00:00:24)
49 ６四角(46) (00:01 / 00:00:31)
50 ５六金(45) (00:01 / 00:00:25)
51 ５九香打 (00:02 / 00:00:33)
52 ６八龍(69) (00:01 / 00:00:26)
53 ５八金(49) (00:01 / 00:00:34)
54 ５七銀打 (00:01 / 00:00:27)
55 ４九玉(48) (00:01 / 00:00:35)
56 ５八銀(57) (00:01 / 00:00:28)
57 同 飛(28) (00:01 / 00:00:36)
58 ５七桂打 (00:01 / 00:00:29)
59 ３八玉(49) (00:01 / 00:00:37)
60 ６七龍(68) (00:01 / 00:00:30)
61 ７三銀成(82) (00:01 / 00:00:38)
62 ５八龍(67) (00:01 / 00:00:31)
63 同 香(59) (00:01 / 00:00:39)
64 ６一飛打 (00:01 / 00:00:32)
65 ６二歩打 (00:02 / 00:00:41)
66 ４七金(56) (00:01 / 00:00:33)
67 同 玉(38) (00:01 / 00:00:42)
68 ６二金(52) (00:01 / 00:00:34)
69 ８三成銀(73) (00:04 / 00:00:46)
70 ４九桂成(57) (00:01 / 00:00:35)
71 ５四香(58) (00:04 / 00:00:50)
72 ５三歩打 (00:01 / 00:00:36)
73 ６三歩打 (00:06 / 00:00:56)
74 ５四歩(53) (00:01 / 00:00:37)
75 ６二歩成(63) (00:06 / 00:01:02)
76 同 飛(61) (00:01 / 00:00:38)
77 ５三銀打 (00:08 / 00:01:10)
78 ４四香打 (00:01 / 00:00:39)
79 ４六金打 (00:01 / 00:01:11)
80 同 香(44) (00:01 / 00:00:40)
81 同 角(64) (00:01 / 00:01:12)
82 ３九成桂(49) (00:01 / 00:00:41)
83 ６二銀(53) (00:06 / 00:01:18)
84 同 玉(51) (00:01 / 00:00:42)
85 ８二飛打 (00:08 / 00:01:26)
86 ５三玉(62) (00:01 / 00:00:43)
87 ５二金打 (00:04 / 00:01:30)
88 ６三玉(53) (00:01 / 00:00:44)
89 ７二飛成(82) (00:01 / 00:01:31)
90 投了 (00:01 / 00:00:45)
まで89手で先手の勝ち
*2:毎回愚直に計算してもいいかもしれないが……
*3:ひまうら王の実験結果その1 | やねうら王 公式サイト
*4:コンピュータ将棋界隈の「フルスクラッチ」なのでチェスソフトのコードを流用してたりする場合すらあることに注意。
*5:merom686開発者がなるべく単純なソースコードになるように書いた将棋プログラム。shogi686microの仕様 - merom686's blog
