コンピュータ将棋動画勢！

観るコン将（コンピュータ将棋観戦オンリー勢）から見たコンピュータ将棋の記述

Futility marginがdepthの線形でいい理由の補足

Hatena Blogで数式が書けるみたいなのでそのテストがしたいだけの記事。


Qhapaqの澤田さんのブログの記事Futility marginがdepthの線形でいい理由 - コンピュータ将棋 Qhapaqの導出から、Futility Pruningが成功する確率は、 Zを定数、 dを探索深さ、 \alphaをある定数、 Aを局面の平均分岐数として f(d) = (1 - Ze^{-\alpha^2 d})^{A^d}と書けるのだった。


この確率を dの関数とみてテイラー展開の1次の項までで近似する。
\displaystyle \begin{align} f'(d) &= \frac{\partial}{\partial d} \exp(A^d \log(1 - Z e^{-\alpha^2 d})) \\ &= \exp(A^d \log(1 - Z e^{-\alpha^2 d})) (\frac{Z \alpha^2 e^{-\alpha^2 d}}{1 - Z e^{-\alpha^2 d}} A^d + A^d \log(1 - Z e^{-\alpha^2 d}) \log A) \end{align}
したがって、
\displaystyle \begin{align} f'(0) &= (1 - Z)(\frac{Z \alpha^2}{1 - Z} + \log(1 - Z) \log A) \\ &= (Z \alpha^2 + (1 - Z) \log(1 - Z) \log A) \end{align}


ゆえに、
\displaystyle \begin{align} f(d) &\fallingdotseq f(0) + f'(0)d \\ &= (1-Z) + (Z\alpha^2 + (1 - Z) \log(1 - Z) \log A)d \end{align}
ここで 0 \lt Z \lt 1であることから \log(1 - Z) \lt 0
また A \gt 1であることから \log A \gt 0であることより、
\displaystyle \alpha = \sqrt{-\frac{(1 - Z) \log(1 - Z) \log A}{Z}}
とすれば dの1次の係数は 0となり、この確率は dが十分小さいとき深さによらず一定であることがわかる。

感想

全体をはてな記法にする必要があるのでやや慣れない。

てか微分しておいてなんだけど、そもそも澤田さんの導出って合ってるのだろうか。
\displaystyle \int_0^{\alpha d} e^{-x^2 / d}dx = \frac{\sqrt{\pi d}}{2} \mathrm{erfi}(\sqrt{\alpha} d)だけどこれが 1 - Ze^{-\alpha^2 d}の形にはならんやろ。ダウト。
（更にこれを A^d乗した式のテイラー展開の1次の項は kxの形になって kは \alpha, Aから決まる定数なのでゼロにはできない。）

ただスクラッチ開発なだけの将棋ソフトってそんなに偉いんですか？　第二回

前回のあらすじ

コンピュータ将棋界隈の一部に存在するとても奇妙なフルスクラッチ信仰について紹介した。コンピュータ将棋界隈では、アイディア的独自性のないただフルスクラッチであるプログラムが偉く、ライブラリ勢を不愉快と思う人が一定数いたり、フルスクラッチを標榜しながらチェスソフトのコードを流用しているという、最早何がフルスクラッチなのか意味不明なソフトもある、と言った具合である。

そこでフルスクラッチのコンピュータ将棋ソフトがそんなに偉いのかを検証するため自分でルール通りに指せるだけのゴミのようなコンピュータ将棋プログラムを他のソースコードを見ないルールで９時間ほどかけて作ってみた。

ルール通りに将棋を指せるだけのゴミプログラムをコンピュータ将棋ソフトと言い張るのは憚られるため、今回はそのコンピュータ将棋ソフトをある程度強化するのが趣旨である。

前回からの改良点

今週末あまり時間が取れなさそうだったので、先週の日曜に動くものが完成したところから、平日夕飯を作って食べた後に時間を取って少しずつ改造した。

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手で先手の勝ち

FSShogi vs shogi686micro

 

*1:Chessprogramming wiki

*2:毎回愚直に計算してもいいかもしれないが……

*3:ひまうら王の実験結果その1 | やねうら王 公式サイト

*4:コンピュータ将棋界隈の「フルスクラッチ」なのでチェスソフトのコードを流用してたりする場合すらあることに注意。

*5:merom686開発者がなるべく単純なソースコードになるように書いた将棋プログラム。shogi686microの仕様 - merom686's blog

ただスクラッチ開発なだけの将棋ソフトってそんなに偉いんですか？

コンピュータ将棋界隈の一部には紛うことなく一つの信仰が存在する。

それがスクラッチ開発信仰*1である。

世界コンピュータ将棋選手権には近年フロムスクラッチ表彰が導入された*2し、第28回世界コンピュータ将棋選手権ではライブラリ使用の参加者とライブラリ不使用の参加者に一悶着あった*3ことからも、スクラッチ開発信仰が存在することは明らかである。

 

フルスクラッチ/フロムスクラッチ開発って何？

一般的には既存のパッケージを用いない開発をスクラッチ開発、あるいはフルスクラッチで開発するなどというのだが、コンピュータ将棋界隈における「フルスクラッチ」あるいは「フロムスクラッチ」と呼称される開発方式は少々趣が異なるようである。

Stockfishという超強豪のオープンソースチェスエンジンの構造をほぼそのまま流用し、せいぜいそこに駒打ちの処理を書き、駒の種類、指し手生成、ビッドボード、プロトコルと評価関数を将棋用にしたくらいのプログラム*4、さらに言えばStockfishのコメントがそのまま残っていたりするレベルの将棋ソフトがコンピュータ将棋界隈ではフルスクラッチになるのである。Stockfishをベースとしたソフトウェアのアピール文書に「フルスクラッチ」と書かれていたりするし、実際にそれらのソフトがフロムスクラッチ表彰を受けていたりするので、間違いない。

つまりコンピュータ将棋界隈におけるフルスクラッチとは、他の将棋ソフトをコピペしてないですよ、くらいの意味である。上にも書いたとおりチェスソフトのコピペはOKである。

もちろん、チェスエンジンのコードの流用もせずに書き上げられた将棋プログラムも存在するし、そちらのほうが多数派でもある。

フルスクラッチ至上主義

そしてこの「フルスクラッチ」*5こそが至高であると考えるコンピュータ将棋参加者が一定数存在し、ライブラリ使用の参加者が「ライブラリを使わないでコードを書くのは面倒」と発言しただけで、ライブラリ不使用の参加者が「正気を疑う。その程度のやる気しかない人に選手権に参加されるのは不愉快」と強い怒りを顕にしたこともある。

これを受けてコンピュータ将棋界隈でフルスクラッチ論争が巻き起こり、フルスクラッチを他人に強要するのはよくないけど、フルスクラッチ開発はとっても難しいしとっても偉い！誇りに思っていいことだ！という結論に落ち着いたようだった。

ただフルスクラッチなだけのソフトの何が偉いんですか？

しかし私は思うのである。スクラッチ開発は著作権やライセンスの問題に対応するため、あるいは教育的目的のために行うといった、ただの開発手法の一つであって、そこに偉いも何もないだろうと。

おまけにである。多くのフルスクラッチの将棋プログラムには何一つアイディア的な新規性がないのである。既存の将棋プログラムの手法のうち一部のこれこれを自分でがんばって（ボナンザややねうら王から性能を大幅に低下させて）実装しましたといった具合に。完全に新規性・独自性とただの苦労を履き違えているようにしか見えない。

フルスクラッチを標榜するソフトの多くが、「本当にただフルスクラッチなだけ」*6のソフトである。

そもそもが、ただルール通り指せるだけの将棋ソフトを作るだけのことがそんなに難しいなどということがあるだろうか？ *7

ただフルスクラッチなだけの将棋ソフトを作ることがそんなに難しいんですか？

というわけで、ただのフルスクラッチなだけの将棋ソフトを実際に自分で作ってみて、その難しさを体感してみることにした。以下時系列順に考えたこと、やったことを雑にまとめる。

ルール

将棋所*8で投了までルール通り指せるプログラムを作る。できれば少しだけ思考させる。

他の将棋・チェスプログラムのソースコードを見ない、使わない。ブログなどはソースコードが書かれた部分を見るのは禁止。手法を解説した部分はOK。

事前準備

名前を決める。フロムスクラッチだから適当にFSshogiに。

将棋所と将棋エンジンの通信プロトコルがわからないといけない。「将棋所　プロトコル」でググるとUSIという名前であることがわかる。

USIでググるとQiitaの記事が見つかる。将棋の局面はsfenという形式で読むらしいことがわかる。

実装（一日目）

夕方から始める。

まずは駒の定義が必要だから書く。名前を決める。sfen形式が歩をpawn、香車をlance、桂馬をknight、銀をsilver、金をgold、飛車をrook、角をbishop、王をkingとしてるから安直にそれにする。成りとかもある。駒を成らせるpromotion関数とかも書く。

つぎに局面のクラスを書かねばならない。盤は9x9の配列で持つ。先手後手の手駒を持つ。

そしたら試しにsfen文字列をプログラムに読み込んで局面に変換して、そのまま局面をsfen文字列に再変換して出力させてみる。動く。正しく同じものが再出力されている。

そしたら次に将棋の指し手を作る。ルールはどんな感じだっけ？駒を動かした後で王手になっていてはダメ。一段目の歩、香車がいたらダメ。二段目に桂馬がいたらダメ。あとなんかあるっけ？とりあえずそれで書く。駒を動かす関数も必要なので書く。

初期局面から指し手を生成してみる。30通り。駒の動きはあってそう。一局面で将棋の指し手って最大何手あるんだ？「将棋　合法手　最大」などでググると593らしい。合法手が最大になる局面で合法手を生成してみる。なんか合わない。

sfenの読み方をミスってた。Qiitaの記事だと持ち駒の表記が"駒の種類+枚数"と書いてあるが別の解説記事だと"枚数+駒の種類"じゃん。直す。593通りと出た。

ここらで夕飯を作る時間になったので終了。夕飯後は別の用事。

実装（二日目朝）

朝から開始。

昨日二歩と打ち歩詰めを忘れてたことに気づいたので追加。

別のQiitaの記事いわく合法手593手の局面から2手進めると105677通りになるらしい。合わない。初期局面から三手進めると25470通りになるらしい。合わない。半分くらいになる。

先手30C2通り*後手30通りで13000くらいになると思うんだが。どうやらこの数え方は合流して同一局面数になるものを一つと数えず、それぞれ別に数えていそう。そう書くと一致。

初期局面から5手まで進めると19861490通り。一致。最多局面から2手進めると105677通り。一致。3手進めると53393368通りで一致。指し手生成は大体あってんだろうからこの辺にする。

千日手は今回は実装しなくていいや。

 

この辺で３時間くらい経ち昼過ぎになったのでしばらく外出。帰宅して再開。

実装（二日目夕方）

次にプロトコル部分を書く。

usiだとかisreadyだとかそんなコマンドがあるらしいので実装していく。今回のところoptionとかはガン無視でよし。ルール通り指せればよい。

で、まずは指し手はなし。即投了するようにする。

将棋所で読ませると対局開始できた。歩をついただけで相手が即投了し先手の勝ち。

次に合法手からランダムに一個選ぶようにして対局。相手がきふわらべのような手を指してくる。

途中で対局が止まる。出力ミスってたようなので直す。

また対局が途中で止まる。エンジンに止まった局面のsfenを食わせてデバッグしてみる。持ち駒を打つと落ちるようだ。

Qiitaの記事のsfenフォーマットの持ち駒を打つ場合の説明が間違ってる。先手の場合駒を大文字、後手の場合小文字で書きますとかあるが、別の解説だと常に大文字とある。このQiitaの記事間違い多いな！！

それを直すと投了まで普通に指せた。

 

ランダムに指し手を選ぶものをルール通り指す将棋プログラムと言い張るのはさすがにイヤなので思考部を少しだけまともにする。

評価関数を作る。歩は100点、飛車は1200点みたいにすごく適当に点数をつける。持ち駒になったらちょっと点数を高くしておく。できた。

そしたら探索。枝刈りはベータカットだけの単純なアルファベータ探索を書けばよい。

５手読みとかで。あ、遅すぎてだめだ……４手読みで*9大体５秒以内に指す。

 

というわけで完成。何度か指してみても普通に動く。

足掛け二日、総作業時間は９時間くらいか。

まとめ

合法手生成が面倒だった。通信プロトコルの嘘解説記事のせいで少しデバッグに時間がかかった。手間なだけで何が難しいのか理解できなかった。ただフルスクラッチなだけの将棋プログラムの何が偉いのか一切理解できなかった。*10なので、来週の週末にでも自分に勝てるくらいまでには強くしてみる。初段くらいあれば十分か。

私事だが自宅で使ってるマシンが古すぎてVisual Studioさえカクついてまともに動かなかったので全部テキストエディタでコード書いた。いい加減買い換えるべき。

おまけ

ランダムプレイヤーのFSshogiと深さ４*11アルファベータ探索のFSshogiを対局させてみた。

# Generated by Shogidokoro
手合割：平手
先手：fs_shogi_random
後手：fs_shogi_depth4
手数----指手---------消費時間--
   1 ９六歩(97)    (00:01 / 00:00:01)
   2 ９二香(91)    (00:01 / 00:00:01)
   3 ９七角(88)    (00:01 / 00:00:02)
   4 ６二銀(71)    (00:01 / 00:00:02)
   5 ９五歩(96)    (00:01 / 00:00:03)
   6 ７一金(61)    (00:01 / 00:00:03)
   7 ８六角(97)    (00:01 / 00:00:04)
   8 ５二金(41)    (00:01 / 00:00:04)
   9 ７五角(86)    (00:01 / 00:00:05)
  10 ２四歩(23)    (00:01 / 00:00:05)
  11 ６六角(75)    (00:01 / 00:00:06)
  12 １二香(11)    (00:01 / 00:00:06)
  13 ８六歩(87)    (00:01 / 00:00:07)
  14 １四歩(13)    (00:01 / 00:00:07)
  15 ８五歩(86)    (00:01 / 00:00:08)
  16 ４二玉(51)    (00:01 / 00:00:08)
  17 ７五角(66)    (00:01 / 00:00:09)
  18 ９四歩(93)    (00:01 / 00:00:09)
  19 同　歩(95)    (00:01 / 00:00:10)
  20 同　香(92)    (00:01 / 00:00:10)
  21 同　香(99)    (00:04 / 00:00:14)
  22 ４四歩(43)    (00:01 / 00:00:11)
  23 ９三香成(94)  (00:02 / 00:00:16)
  24 １三香(12)    (00:01 / 00:00:12)
  25 ８二成香(93)  (00:01 / 00:00:17)
  26 ３二銀(31)    (00:01 / 00:00:13)
  27 ８一成香(82)  (00:04 / 00:00:21)
  28 ９一歩打      (00:01 / 00:00:14)
  29 １二飛打      (00:07 / 00:00:28)
  30 ３一角(22)    (00:01 / 00:00:15)
  31 ９一成香(81)  (00:03 / 00:00:31)
  32 ８二金(71)    (00:01 / 00:00:16)
  33 ２三桂打      (00:08 / 00:00:39)
  34 ８四歩(83)    (00:01 / 00:00:17)
  35 ３一桂成(23)  (00:02 / 00:00:41)
  36 ３四歩(33)    (00:01 / 00:00:18)
  37 ３二飛成(12)  (00:05 / 00:00:46)
  38 ５一玉(42)    (00:01 / 00:00:19)
  39 ４一龍(32)    (00:08 / 00:00:54)
  40 投了          (00:01 / 00:00:20)
まで39手で先手の勝ち

投了図

アルファベータ版がきちんと相手玉を詰ませて終了。

*1:一般的な用語としては、スクラッチ開発とは既存のパッケージ等を使用せずにソフトウェアを開発することである。ただしコンピュータ将棋界隈では少し意味が異なるようである。後述。

*2:第29回世界コンピュータ将棋選手権より。ただし第29回では「ライブラリ不使用者表彰」であった。

*3:twitterやブログ等を観測すればわかるのだが、具体的出典を出すのは差し控えたい。

*4:一番実装が重い探索部は微調整だけがなされほぼそのまま流用される。スレッド周りや時間制御もほぼ流用である。

*5:コンピュータ将棋界隈における独自の定義のほうであることに注意。

*6:場合によってはチェスソフトのコードを多くコピペしフルスクラッチですらない。

*7:反則負けを連発し、ルール通りに指すことそれすらもできないソフトも多く存在する。

*8:将棋エンジンを登録して指せるGUIのアプリケーション。

*9:後から気づいたが探索の一番外側を数えてなかったので５手読みだった。

*10:将棋を指すプログラムを書いて動くのが楽しいというのはわかるが。

*11:後から気づいたが実は深さ５だった。

【連載】あなたの知らない将棋ソフトたち　第三回　芝浦将棋とその仲間たち

本連載の第一回では「きふわらべ」、第二回では「うさぴょん」とそれぞれひとつのソフトに焦点を当て、その紹介記事を書いたのですが、今回は趣向を変えてコンピュータ将棋界における一大派閥である、芝浦将棋ファミリーを紹介したいと思います。


コンピュータ将棋界におけるファミリー

コンピュータ将棋界においてファミリーと言うと、ボナンザチルドレン、あるいはやねうら王チルドレンといったソフトを思い浮かべる方がいるかもしれません。

「ボナンザ」*1、「やねうら王」*2はともにオープンソースのソフトウェアであり、公開時にトップクラスの強さを持っていたことから、これらを利用した多数の将棋ソフトが誕生しました。ボナンザを利用したソフトとしては、なんと単純に複数のボナンザの指し手の多数決を取るだけで強くなったという「文殊」*3や、ボナンザを超高効率でクラスタ化した、当時引退棋士であった米長邦雄氏に勝利した「ボンクラーズ」*4などがあります。

やねうら王は現状世界最強のオープンソース将棋ソフトであるため、これをベースとしたソフトは枚挙にいとまがなく、「Kristallweizen」*5、人間やソフトの既存の棋譜を全く使わずとも自己対戦だけで最強レベルの将棋ソフトを作れるほどの効率のよい学習方法*6を導入した「elmo」*7、ボナンザ以来長らくコンピュータ将棋のスタンダードであった三駒関係の評価関数を刷新したNNUEを導入した*8「たぬき」*9、等々、さまざまな工夫がやねうら王チルドレンによってコンピュータ将棋に持ち込まれ、なおかつそれらが棋力向上につながることが証明されました。

これらは言わばソースコードを元にした繋がりをもつファミリーと言えるでしょう。ところが、コンピュータ将棋界には師弟関係を元にした、もう一つのファミリーがあるのです。それが「芝浦将棋」とその仲間たちです。

芝浦将棋

「芝浦将棋」は、芝浦工業大学工学部情報工学科の五十嵐治一教授*10と教授の研究室の学生たちによって開発された将棋ソフトです。第20回世界コンピュータ将棋選手権で世界コンピュータ将棋選手権に初出場し、それ以来毎年その代の学生たちが自分たちの芝浦将棋を開発して世界コンピュータ将棋選手権に出場しています。

芝浦将棋は毎年主要開発者や開発方針が変わっているため、その特色を一言で纏めることは難しいのですが、大まかに言って強化学習の手法を取り入れていること、そして評価関数バイナリ等、なんらかの部分でボナンザをベースにしていることがほぼ毎年共通しています。ボナンザをベースとしているのは、芝浦将棋が学生の卒業研究であり、完成された将棋ソフトであるボナンザが研究の新しいアイディアを上乗せしやすいため、そして強化学習の手法を取り入れているのは指導教官である五十嵐教授の研究テーマが強化学習分野であるためだと思われます。

芝浦将棋の迷走発展

芝浦将棋は第23回コンピュータ将棋選手権からその名を「芝浦将棋Jr.」と変えて出場しています。はじめは強化学習の手法の将棋における応用を模索していた芝浦将棋ですが、将棋ソフト開発の魔力に取りつかれてしまったのか開発に関わる学生の数を増やし、強化学習を棚上げしてなんとデータ構造や探索部の独自実装*11へと踏み切ります。

残念ながらこれらの独自実装は失敗に終わり、第23回世界コンピュータ将棋選手権はバグによる反則負けで全敗を喫し一次予選敗退となります*12。

その後もしばらく強化学習には手をつけず、芝浦将棋Jr.はDIY精神を発揮し独自実装の将棋プログラムを作ることにこだわりつづけます*13。

芝浦将棋Softmax

第27回コンピュータ将棋選手権からは芝浦将棋Jr.に加えて「芝浦将棋Softmax」が登場します。芝浦将棋Softmaxは同じく五十嵐教授と五十嵐研究室の学生により書かれたプログラムであり、他のほぼすべての将棋ソフトがαβ探索をする中でモンテカルロ探索を取り入れた画期的な将棋ソフト*14であり、探索部以外はボナンザをベースにすればいいのに前年度までの芝浦将棋Jrをベースとしています。

そして芝浦将棋Softmaxは、なんと芝浦将棋Jr.が一次予選敗退する中で二次予選へと駒を進めます。*15

受け継がれる五十嵐教授の教え

長年コンピュータ将棋に取り組み続けた五十嵐研究室ですが、五十嵐教授の指導が優れていて学生たちが楽しく研究に取り組める環境にあったためか、学生が卒業後も趣味で将棋プログラムの開発を続けることがありました。

その一つが、第21回コンピュータ将棋選手権に出場した芝浦将棋の開発者である山本一将氏の開発した「ひまわり」*16です。ひまわりは強化学習の手法を取り入れており、「既存の棋譜を使わずに強い将棋プログラムを作る」という五十嵐教授のテーマを受け継いでいることがうかがえます。

もう一つが森岡祐一氏の開発した「GA将」*17です。GA将が登場したのは芝浦将棋よりも前なのですが、開発者である森岡氏は強化学習に関する五十嵐教授との共著論文も執筆されており、GA将も強化学習の手法を取り入れた将棋ソフトとなっています。なお、惜しくも近年は森岡氏は世界コンピュータ将棋選手権への出場を引退されてしまっているようです。*18

社会人が仕事をしながら将棋ソフトの開発を趣味で続けることは、並大抵の苦労ではなく、よほどの情熱がなければできないことであることは間違いありません。五十嵐教授は今年、芝浦工業大学を退官されました。ですが、長年続けてきたコンピュータ将棋ソフトの開発、そしてその思いは、これらのソフトを見ればわかる通り、後継者らに間違いなく受け継がれているのだと思います。

願わくは芝浦将棋、そして芝浦将棋ファミリーが、これからも世界コンピュータ将棋選手権を盛り上げつづけてくれる存在であらんことを。

*1:開発者は保木邦仁氏。第16回、第23回世界コンピュータ将棋選手権優勝。

*2:開発者はやねうらおこと磯崎元洋氏。第29回コンピュータ将棋選手権優勝。

*3:開発者は小幡拓弥氏ら。第19回世界コンピュータ将棋選手権第三位。

*4:開発者は伊藤英紀氏。第21回世界コンピュータ将棋選手権優勝。後継のPuella αはオープンソースだったが、実装が難解で伊藤氏の優れたクラスタ方式は他の誰にも真似ができず惜しくも歴史に埋もれてしまった。

*5:開発者は芝世弐氏ら。第28回世界コンピュータ将棋選手権優勝、他準優勝等多数。他の将棋ソフトも多数ライブラリとして使用。

*6:elmo自体が他ソフトの棋譜を学習に使用していないという訳ではない。

*7:開発者は瀧澤誠氏。第27回世界コンピュータ将棋選手権優勝等。

*8:那須悠氏により第28回世界コンピュータ将棋選手権より導入された。

*9:開発者は野田久順氏ら。世界コンピュータ将棋選手権決勝出場多数。ただし初年度は平岡拓也氏によるAperyをベースとしていた。

*10:今年退官されたそうです。

*11:ただし探索の手法的にはすべてボナンザにある手法をなぞったようなもので、いわゆるDIYである。

*12:学生らの卒論は大丈夫だったのだろうか……

*13:学生らの卒論は本当に大丈夫だったのだろうか……

*14:強いとは言っていない。またやねうらお氏がより洗練されたモンテカルロ将棋を2011年頃すでに開発していた。また同年、激指を開発した東大近山研究室のメンバーによって書かれた論文から、2011年にはすでに彼らもモンテカルロ将棋の実験をしていたことがわかる。

*15:棋力で芝浦将棋Softmaxが勝っていたと結論を出すことは早計である。一次予選はまともに動かないプログラムも多数あり、勝敗が対戦相手次第となる面があるため。

*16:第23回コンピュータ将棋選手権に初出場。その後も断続的に世界コンピュータ将棋選手権や将棋電王トーナメントに出場を続ける。

*17:第16回コンピュータ将棋選手権初出場。その後もしばらく断続的に世界コンピュータ将棋選手権に出場を続ける。

*18:背景には森岡氏が非フルスクラッチの将棋ソフトに並々ならぬ敵意を持っていることがある模様。

df-pnの完璧な実装が公開されていた話

前回オープンソースで公開されてるミクロコスモスの解けるdf-pnの実装がないとか書いちゃったけど、あった。ごめんなさい。

GPS将棋についてた。しかも完璧な実装。（東大の金子先生がほぼ一人で書いたらしい。たぶんdf-pnのバリエーションも実装されてて、全部入れると詰将棋だけで1万行くらいある……）

 

多分df-pn+というdf-pnを更に効率化したアルゴリズム（末端ノードで固定深さの探索を行って、証明数・反証数の推定値を得る）をベースに、詰将棋ソルバ定番の優越関係・証明駒・GHI検出の完璧なやつ（kishimoto-mueller）・ループ検出・Small TreeGCを全部実装している。まあソースコードは関数名をちらっと見たくらいで、読んでないんで間違ってたらごめんなさい。

 

ミクロコスモスが5000万ノードの探索で解けるらしい……（脊尾詰のアルゴリズムだと5億ノードくらい探索する？）

 

詳しくはCiNii 論文 -  新規節点で固定深さの探索を行うdf-pnの拡張←これを読んでね。

 

ミクロコスモスを解きたい人向け

優越関係・証明駒はやらないと探索ノードが爆発するので必須。優越関係を生かすため、玉方の合駒の応手は玉に近い順にソートして試すこと。

GHI対策はちゃんとやらないと図巧一番すら解けない。長井論文のGHI対策は不備が指摘されているので注意。（詳しくはA solution to the GHI problem for depth-first proof-number search - ScienceDirect←この論文読んでね）最小距離法もダメ。

ミクロコスモスだけを解くぶんにはループ検出・合流検出は必須ではない。ミクロコスモスだと探索時間がせいぜい２倍くらいになるだけっぽい。

固定深さの探索はミクロコスモスを解くだけなら要らない。

GCはほぼ必須。実装によるが5億ノードで20GBくらいはハッシュを使うので、64GBくらいメモリがあれば要らないかも。GCの実装は超簡単なのでやって損はない。

 

なのはは何でミクロコスモス解けないんだろう？多分GHI対策を最小距離法でやってるせいとかだと思うが。

 

やねうら王最新ビルドの詰将棋エンジンがバグっている

明らかな不詰めを詰みと言い張って不正な手順を出力しますね。

後手玉裸玉で先手持ち駒金一枚のみで詰みと言い張ります。

 

原因

駒打ちのときここで手駒を減らす処理をしています。

以前はMATE_ENGINEではEVAL_MATERIALをdefineしてそれがUSE_FV_VARをdefineしていてこの処理が実行されていました。

ですが、FV_VARを削除するときにこれらの定数がdefineされなくなり、MATE_ENGINEで手駒を減らす処理が実行されなくなったが原因のようです。

 

【12/12追記】

同じようにプリプロセッサ定数の定義の問題でking_sqの更新もバグっている。

コンピュータ将棋界隈のソフトが誰もミクロコスモスを解けない話

ミクロコスモスという詰将棋の作品がある。橋本孝治氏により1986年に発表された、史上最長の1525手詰めの詰将棋である。*1

 

コンピュータ将棋黎明期では、まともに指し将棋の指せるプログラムよりも詰将棋を解くプログラムのほうがずっと先に実用化されたと言われている。

コンピュータが詰将棋の解図能力で人間を超えた*2のも随分昔の話で、脊尾昌宏氏によるプログラム「脊尾詰」*3によって、このミクロコスモスも1997年に解かれ、余詰や不詰のない完全作であることが示された。

 

脊尾氏のプログラムに使用されたアルゴリズムは論文として公開されており、またそのアルゴリズムを発展・効率化させたdf-pnアルゴリズムを長井歩氏が考案し*4、これもアルゴリズムが論文として公開されており、様々な将棋ソフトが終盤用詰めルーチンとして実装している。*5

 

論文だけでは再現できない詰将棋アルゴリズム

ところがである。このdf-pnアルゴリズム、数十手の詰将棋を解く分には一瞬なのであるが、数百手の超難解詰将棋を解こうとすると、論文のアルゴリズム概略からでは実装を再現できないのである。

 

世界コンピュータ将棋選手権常連の川端一之氏による「なのは」は、対局機能だけではなく、詰将棋の解図ルーチンにも莫大な労力を割いた将棋ソフトである。

なのはのdf-pnを実装した詰将棋部分だけを取り出したソフトは、「なのは詰め」として氏のwebサイトでも公開されている。

そんななのはでも未だにミクロコスモスの解図には至っていない。

 

詰将棋ルーチンに挑戦したのはなのはだけではない。やねうら王チルドレンの一つであり、三駒関係に代わる現在最強の評価関数であるNNUE関数を生み出した「tanuki」チームの一人である野田久順氏、同じくやねうら王チルドレンの一つである「Qhapaq」の開発者である澤田亮人氏らがやねうら王に詰将棋ルーチンを組み込んだときも、ミクロコスモスを解くことはできなかった。

 

実際に超長手順の詰将棋を解くには、df-pnに、論文では詳細に解説されていない

  • 詰将棋専用のGC（ガベージコレクション。メモリ不足になったときに、重要度の低いメモリ領域を破棄する）
  • 手駒の優越関係（持ち駒が金、金、桂で詰むなら、ここに歩が加わっても詰む、といった関係。）
  • 証明駒、反証駒（持ち駒のうち詰めに必要な駒だけを取り出してハッシュに保存する。反証駒は不詰めに必要な最小の駒。優越関係と組み合わせる。）
  • 千日手の問題の回避
  • 局面に合流があった場合の証明数、反証数のダブルカウントの扱い

等を正しく実装する必要がある*6。が、これらを完璧に実装できた人は現在の将棋ソフト開発者たちの中にまだいないのである*7。詰将棋ルーチンは現代において製法の失われた、ダマスカス鋼、あるいは古刀のような存在となっているのだ。*8

 

ミクロコスモスを解くエンジンがオープンソースとなる日は来るか？

コンピュータ将棋がオープンソースになり、優秀な頭脳が活発に議論を重ねる中でも、未だに最長の詰将棋を解ける20年以上前のソフトウェアが再現できないというのは興味深いことである。

このミッシングリンクの謎が解けるのは、果たしていつか。それはコンピュータ将棋開発者たちの間で詰将棋ブームがおこった時に違いないが、今はみんなディープラーニングに夢中であり、それはまだ当分先の話でありそうだ。

*1:このミクロコスモスの記録は2020年12月現在もなお破られていない。

*2:とは言え、公開されている将棋ソフトが未だに解けない超長編の詰将棋も未だにいくつか存在する。

*3:現在フリーウェアとして公開されている。

*4:これによって超長手数の詰将棋作品が全て解けたと論文中にはあるが、プログラムは非公開である。

*5:たとえばBonanza、GPS将棋、なのは、やねうら王等。

*6:千日手の問題や局面の合流は厳密なアルゴリズムを実装することはたぶん不可能で、何らかのヒューリスティックスを用いねばならない？

*7:いたらコメントで教えて教えてくれると嬉しいです。でもいたらみんな実装を参考にしてミクロコスモスをとっくに解いてると思うので、いないはず……手元のたぬき詰めはHash16GBで1時間解かせて答えが出なかった。

*8:しかも脊尾氏が使用したのは初代Pentiumのマシン……今のマシンの1/100か1/1000くらいの処理能力か。