sakurapyon’s blog

sakurapyon’s blog

sakurapyon_dti 続き

DTIServersMan@VPSの話の続き。

置換表を増やして 1.6GB ほど使う状態で走らせていますが、いまのところプロセスがkillされることもなく順調に動いています。

46719 XXXX      19   0 1595m 1.5g 161m R 40.0 76.5   2:22.49 csamain

置換表増やしてもレーティングはほとんど変わらないようなので、それはそれで問題かもしれない

sakurapyon_dti

価格の安いDTIServersMan@VPSを試しています。
CPUが遅いので NPS は さくらのVPS 2Gの1/3-1/4ぐらいです。値段も1/3なのでこんなもんでしょうか。

初期局面のNPS比較。
sakurapyonは並列探索してないのでCPU個数は無関係。NPS差は単純にCPU速度差だと思う。

vps業者 NPS(k/s) 読み深さ CPU 利用可能メモリ 価格/月
DTI ServersMan 102 15 2 保障1GB(最大2GB) 490円
さくら2G 355 17 3 2GB(+swap) 1480円

DTI 490円はメモリが少ないのでハッシュや詰みキャッシュのサイズも減らしています。
それでレーティング差が100なら上出来? もしかして、メモリを有効に使えてないのかな??

静止探索内で嘘必至が見つかった場合はどうすればいいのか?


静止探索に突入した時点で、取る手・成る手だけでは自玉が詰んでしまう場合がある。

先手は持ち駒が豊富なので詰めに行けば先手勝ちの局面。

上のような局面で静止探索に入ると、先手は1三歩成しかない→5八桂成5八金打ちまでの一手詰み。
こうなってしまうのは静止探索だから仕方ないんだけど、このときどう処理するのが正しいのだろうか?

  • もう一手反復進化が進めば解決するので放置
    • 一瞬後手勝ちの評価値がPVに出てくるのが気持ち悪い
    • 返す値を詰みの値にしていいのか?
  • 静止探索で詰みが来たら通常探索を延長する?
  • 詰むときは全手生成する?
    • 以前、これ試したらめっちゃ遅くなった

同じ問題を1年以上悩んでいるかも…

sakurapyon改良点

相変わらず不詰みは遅いので まだまだ改良しないといけないんだけど、とりあえずメモしておく。

移動一手詰を先に調べるようにした

いままでは打一手詰を先に調べて移動一手詰を後から調べてましたが*1、順序を逆にしました。

その結果、持ち駒が多種類あるのに打一手詰では詰まない&移動一手では詰む問題が高速に!.......だけではなくて。

媛No.1〜4はこれだけでも少し高速になりますが、そもそも不詰の問題のコストは一緒です。
一手詰は何のためにあるのか2にも書いたけど、そもそも大半の局面は一手詰では不詰みなので、不詰みの処理を速くすることが大事だし、速ければもっとあちこちから呼び出せる)。

移動一手詰で得られた情報を打一手詰に流用

打一手詰は桂馬を除いては利きのあるところにしか打てません。そうでないと玉で取られますから。
いままでは打つタイミングで利きを調べていました(利きがあった情報は流用していたけど)。

ところで、sakurapyonの移動一手詰は玉への近傍直接王手しか考えていません。そのため移動一手詰では、玉の近くに移動できるかどうかを必ず調べています。その情報をメモしておいて打一手で流用すれば処理を省けます。
(成れない角が玉頭に来る場合など、玉近傍に移動はできるけど王手にならない場合があり、ムダですがついでに調べてしまいます)

また、この利きは直接利きと間接利きを分けて保存しておきます。間接利きは種別や方向別に細かく分けた方が便利そうだけど、まだ そこまでは手をつけていません。

  • 移動王手がかかるのは 利きが重複して2つ以上ある(X-ray含む)なので、先にに利きを全部調べた方が速くなったりするのかな?

打一手詰のときに直接利き・間接利き情報を使う。

移動王手のときに玉周辺の情報は調べましたので、これを打一手詰で流用します。

  • そもそも玉周辺にまったく利きが無い場合は打一手を調べるまでもない(桂馬を除く)
  • 利きのあるところだけ王手できる
  • 直接利きのあるところには玉は逃げられない
  • 逃げられる場所(利きが無く、自駒でもない場所)があり、王手駒の利きがそこに及ばないときは不詰み
    • 逃げられる場所が1箇所でもあれば桂馬では詰まない

打った駒から得られた情報を流用する

持ち駒が多い場合は特に有効。

  • xに駒を打った結果 yの間接利きが止まり 不詰みとなる場合は、yに利きが及ばない駒をxに打っても不詰みである。
  • xに打った駒が取られて不詰みになる場合は、何をxに打っても詰まない

守備駒移動による開き王手の確認

  • そもそも開き王手にならない場合は高速に調べられる
    • 玉の斜め方向に角、縦横に飛車、前方に香車がいるかは低コストで調べられる。まったくいなければ開き王手にはならない
      • この情報は流用できるので、最初に一度だけ調べておく
  • 守備駒に間接利きが及んでいなければ開き王手にはならない
    • 事前にPin駒がわかってればもっと楽ですが、今のつくりだと難しいかな...

でもやっぱり遅い

王手がかかる手がたくさんある不詰み局面が遅いですね。媛No.7は特に遅い。

王手候補が多い上に詰まない理由がバラバラなために 情報の使いまわしが利かないのが遅い理由かな...
移動一手が移動先の利きを毎回チェックしてるのも理由だろうなあ。なんとかしたい。

*1:簡単な打一手詰めから先に作ったし、参考にした Bonanza v6.0 もそうなっていたので 深く考えていなかった。

媛さんの問題が参考になった

書いていただいた問題を元にsakurapyonを改良してみたのでメモ。

sakurapyonはどれぐらい遅かったのか?

今も決して速くはないけど、前よりは...

以下速度比較。単位はM回/秒。

問題 媛さん sakurapyon 〃 改良後 なのは1手 〃 3手 詰み有無 備考
No.1 8.07 1.19 2.76 11.9 1.4 有り 銀成詰み・持ち駒全種
No.2 8.27 1.77 3.88 16.0 0.49 有り 桂成詰み・持ち駒全種
No.3 10.35 2.31 4.97 7.4 0.44 有り 龍移動・持ち駒全種
No.4 7.98 1.47 4.18 5.7 1.32 有り 龍移動・利きが延長される・飛車以外全部
No.5 4.89 0.99 5.75 5.8 0.22 有り 角成・隠れた利きがでてくる・持ち駒全種
No.6 7.77 2.14 2.70 7.4 0.32 不詰 どうしても利きが届かない場所がある・持ち駒全種
No.7 4.05 0.65 1.07 4.4 0.74 不詰 打つことで利きが遮られて詰まない・持ち駒全種
No.8 4.05 1.30 1.70 7.3 0.25 不詰 移動することで利きが遮られる・持ち駒なし
No.9 6.90 1.10 1.92 8.7 0.77 不詰 利きが遮られる・持ち駒なし
初期 15.84 12.10 12.18 18.5 1.78 不詰 平手初期画面
祭り 13.83 2.71 3.34 15.1 0.21 不詰 指し手生成祭り
  • なのは一手詰めはNo.1-5は解けないとのこと
  • クマ将棋は300万/秒出るらしい。
  • sakurapyonはvpsで動いているので有効精度は2桁未満だと思いますが、参考まで

sakurapyonで改良した部分は次のエントリで。

難しい

何が原因なのかさっぱりわからん....

gcc バージョン 4.8.0 20130320 (Red Hat 4.8.0-0.18) (GCC)

#include        <stdint.h>
#include        <smmintrin.h>

typedef uint32_t        u32;

#define foreach_BitScan(b,var,proc)                             \
        {                                                               \
                u32     t;                                              \
                t = _mm_extract_epi32((b).mm, 0);                       \
                while(t){                                               \
                        var=__builtin_ctz(t);                           \
                        t&=(t-1);                                       \
                        proc;                                           \
                }                                                       \
                t = _mm_extract_epi32((b).mm, 1);                       \
                while(t){                                               \
                        var=__builtin_ctz(t)+27;                        \
                        t&=(t-1);                                       \
                        proc;                                           \
                }                                                       \
                t = _mm_extract_epi32((b).mm, 2);                       \
                while(t){                                               \
                        var=__builtin_ctz(t)+54;                        \
                        t&=(t-1);                                       \
                        proc;                                           \
                }                                                       \
        }
//
//
template        <int y>int x() { return y; }
template        <int y,int yy>int xx() { return yy; }

class   BitBoard {
public:
                union {
                        u32             bb[4];
                        __m128i         mm;
                } __attribute__ ((aligned));
};

main()
{
        BitBoard        a;
        int             b;

        foreach_BitScan(a,b,{
                x<1>();                 // ok
        });
        foreach_BitScan(a,b,{
                (xx<1,1>());            // ok
        });
        foreach_BitScan(a,b,{
                xx<1,1>();              // compile error
        });
}
g++ -m64 -msse4.2  b.cpp
b.cpp:54:3: エラー: マクロ "foreach_BitScan" に引数が 4 渡されましたが、3 しか受け取りません
  });
   ^
b.cpp: 関数 ‘int main()’ 内:
b.cpp:52:2: エラー: ‘foreach_BitScan’ was not declared in this scope
  foreach_BitScan(a,b,{
  ^