将棋ソフト れさぴょん(lesserpyon)をいじってみる

書籍

amazon 4777511103 amazon 477751241X

Linux (CentOS5) + gcc でコンパイルする

  • ファイルの中身の文字列をutf8にしておく
  • ln -s makefile.gcc Makefile

kyokumen.h:340: error: extra qualication ‘TsumeHash::’ on member ‘CalcHand’

$ make
gcc -D_GCC_ -c KomaMoves.cpp
kyokumen.h:340: error: extra qualification ‘TsumeHash::’ on member ‘CalcHand’
make: *** [KomaMoves.o] エラー 1

ヘッダーでメンバー関数をクラス名で修飾すると出る。gcc4.1から厳しくなったらしい。

diff -uNr lesserpyon.orig/kyokumen.h lesserpyon/kyokumen.h
--- lesserpyon.orig/kyokumen.h  2011-05-30 04:36:07.000000000 +0900
+++ lesserpyon/kyokumen.h       2011-05-30 04:41:19.000000000 +0900
@@ -337,7 +337,7 @@
        static uint64 HI_BIT_TBL[3];
        static TsumeVal *FindFirst(uint64 KyokumenHashVal);
        static TsumeVal *FindNext(TsumeVal* Now);
-       static uint64 TsumeHash::CalcHand(int Motigoma[]);
+       static uint64 CalcHand(int Motigoma[]);
 public:
        static void Clear();
        static void Add(uint64 KyokumenHashVal,uint64 HandHashVal,int Motigoma[],int mate,Te te);

漢字のバイト数を2固定で計算している部分がある

--- lesserpyon.orig/kyokumen.cpp        2011-05-30 04:36:07.000000000 +0900
+++ lesserpyon/kyokumen.cpp     2011-05-30 05:28:20.000000000 +0900
@@ -825,7 +825,7 @@
        for (x = EHI; x >=EFU; x--) {
                if (Hand[x] > 1) {
                        y = 1;
-                       fprintf(fp,"%s%2.2s", komaStr2[x], "一二三四五六七八九101112131415161718"+2*Hand[x]-2);
+                       fprintf(fp,"%s%2.2s", komaStr2[x], "1 2 3 4 5 6 7 8 9101112131415161718"+2*Hand[x]-2);
                } else if (Hand[x] == 1) {
                        y = 1;
                        fprintf(fp,"%s", komaStr2[x]);
@@ -843,7 +843,7 @@
                for(x=9;x>=1;x--) {
                        fprintf(fp,komaStr[ban[x*16+y]]);
                }
-               fprintf(fp,"|%2.2s","一二三四五六七八九" + y*2-2);
+               fprintf(fp,"|%3.3s","一二三四五六七八九" + y*3-3);
                fprintf(fp,"\n");
        }
        fprintf(fp,"+---------------------------+\n");
@@ -852,7 +852,7 @@
        for (x = SHI; x >= SFU; x--) {
                if (Hand[x] > 1) {
                        y = 1;
-                       fprintf(fp,"%s%2.2s", komaStr2[x], "一二三四五六七八九101112131415161718"+2*Hand[x]-2);
+                       fprintf(fp,"%s%2.2s", komaStr2[x], "1 2 3 4 5 6 7 8 9101112131415161718"+2*Hand[x]-2);
                } else if (Hand[x] == 1) {
                        y = 1;
                        fprintf(fp,"%s", komaStr2[x]);

盤面表示をKifu for Windowsに貼れる形式にする(空白を・で表す)

--- ../lesserpyon.orig/KomaMoves.cpp    2011-05-30 04:36:07.000000000 +0900
+++ KomaMoves.cpp       2011-07-19 12:30:42.000000000 +0900
@@ -194,7 +194,7 @@

 // 駒を盤面に表示するための文字列
 char *komaStr[]={
-"   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ",
+" ・","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ",
 "   "," 歩"," 香"," 桂"," 銀"," 金"," 角"," 飛"," 王"," と"," 杏"," 圭"," 全"," 金"," 馬"," 龍",
 "   ","v歩","v香","v桂","v銀","v金","v角","v飛","v王","vと","v杏","v圭","v全","v金","v馬","v龍",
 " 壁","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ","   ",

LAN対戦時処理が変

この部分、ss=3 と代入するつもりではないはず。

--- lesserpyon/main.cpp 2011-10-28 08:05:43.000000000 +0900
+++ sakurapyon/main.cpp 2011-10-28 07:57:36.000000000 +0900
@@ -595,7 +595,7 @@
                                        if (strcmp(buf,"%TORYO")==0) {
                                                te=Te(0);
                                        } else {
                                                if (ss<2) continue;
                                                if (from

読みの深さ

main.cpp:278 あたりの depthMax=5。最大はMAX_DEPTHの32。 手元のCPUだとdepthMax=7のときは終盤で1手30秒を超える。

定跡ファイル

うさぴょんの配布バイナリの public.bin を shogi のあるディレクトリにコピーする。これを行わないと、初手から考える。

先人の知恵

参考資料

バグらしきもの

  • kyokumen.cppのCheckMate関数で詰みがある場合に、どちらの手番であるかをチェックしていない。
@@ -2483,8 +2485,10 @@
        }
        TsumeVal *p;
        if ((p=TsumeHash::DomSearchCheckMate(KyokumenHashVal,Hand+SorE))!=NULL) {
- te=p->te;
- return 1; //詰んだ
+               if(!te.IsNull()&&(te.koma&SorE)&&IsLegalMove(SorE,te)) {
+                       te=p->te;
+                       return 1; //詰んだ
+               }
        }
        int valmax = -1;
        for (int i = 0; i < teNum; i++) {

高速化

  • kyokymen.cpp kyokumen::Move が遅い
    • ジャンプテーブル(CanMove,CanJump)をbit演算で処理
    • 利きの更新にループを使わないで駒別に展開する
    • Teクラスの変数を64bitにパックする
class Te {
public:
        uint64  T;
          :
        inline unsigned char    to(void)        const   { return (((T)&0x000000ff)); }
        inline unsigned char    to(char t)      { T=(T&0xffffffffffffff00)|(t&0x000000ff); }
        inline unsigned char    from(void)      const{ return (((T)&0x0000ff00)>>8); }
        inline unsigned char    from(char f)    { T=(T&0xffffffffffff00ff)|((f&0x000000ff)<<8); }
        inline KomaInf  koma(void)      const{ return (((T)&0x007f0000)>>16); }
        inline void     koma(char k)    { T=(T&0xffffffffff80ffff)|((k&0x0000007f)<<16); }
        inline KomaInf  capture(void)   const{ return (((T)&0x7f000000)>>24); }
        inline void     capture(char c) { T=(T&0xffffffff80ffffff)|((c&0x0000007f)<<24); }
        inline unsigned char    promote(void)   const{ return (((T)&0x80000000)>>31); }
        inline void             promote(int p)  {
                if(p)   T|=0x80000000;
                else    T&=~(uint64)0x080000000;
        }
        inline int              value(void)     const{ return (((T)&0x0ffffffff00000000)>>32); }
        inline void             value(int v)    { T=(T&0x000000000ffffffff)|((uint64)v<<32); }
- 利きの更新をしない、ハッシュ値を得るためだけのMoveを別に作る
  • 手生成も遅い
    • 特に王手生成は全ての手を作ってから王手のみを残している
    • 王手だけでも別処理にするといい
    • 成れる歩は必ず成るなど、手抜きをして読みの対象となる手を減らす。

細かい高速化

  • Kyokumen::Move で利きの更新と駒移動、ハッシュの更新を同時に行ってる

    • 利きの更新は要らない場合がある (EvalMin/Maxの中から呼ぶとき)
    • ハッシュの更新も要らない場合がある (EvalMin/Maxの中から呼ぶとき)
  • CountControlS/Eの値が0か非0かだけ必要な場合がある

  • CanMove, CanJump, CanPromoteはbit演算にできる (1UL<<komaとbit and)

手生成

  • MakeLegalMovesで不成も生成してるのを止めると少し強くなる
    • 飛不成とか角不成は詰将棋ならともかく通常は使わない手
    • 上位30手のなかにこれが含まれていると、その分読む手が減る

強くするために

  • EvaluateTe で良さそうな手を選別し、Evaluateで評価している
    • EvaluateTeが明らかに悪い手を落としているという前提
      • Probe Cutっぽい仕組み
    • むやみに全幅検索すると、変な手を指す(と金増殖も含めて)
    • 深く読むためにEvaluateは軽く作られている
      • 全幅化するためには、このへんの役割分担をどうするか
      • Evaluateが重くなると深く読めなくなる。結構シビア。
    • EvaluateTeの中でEvaluateを呼んでいるので、なおさらEvaluateは軽くないといけない
  • デフォルトでは30手ずつ読んでいる
    • 深さは5だが偶数手読んだほうがいいはず。今時のCPUなら深さ6は読める。7は無理。
    • 取り合いなど、ある条件に合致すると深く読む。20数手になることもある
    • 深く読む結果タイムアウトになる場合がある。かといって浅くすると明らかに弱くなる。
      • 必至がかかっている局面など、何をやっても悪くなるところで深く読むのは無駄
  • 6手では読みが浅すぎる。8手は読ませたいが現状の仕組みでは厳しい。
    • floodgate投入を考えて1手10秒程度使えるとすると、読める局面数は10万程度
    • 速度が100倍にならないと8手読むのはムリ
  • 深さ1,2でだけMate(詰将棋)を読んでいるので、先の局面でトン死したりする。
    • れさぴょんのMateは遅いので深い局面で読ませるのは無理

int Kyokumen::Eval(const int pos)

  • 静的評価の際の駒の取り合いの評価は、現在の(盤面上の)駒の価値の少ないものから取り合いすると仮定しているが正しいか?

    • 成駒が含まれる・取り合い後に成れる場合に問題になりそう
      • 例: 攻め方が桂馬とと金の場合、と金を先に使った方がいいはず
      • 最後に残る駒がと金になるか成桂(orただの桂馬)になるか
  • 下記盤面を先手手番でEvalすると、▲2六銀で歩得と評価する

    • この場合は▲2六飛でも大したことないけど、先読みしないとまずいことがわからない
    • Super SOMAはこの辺も考慮してるっぽい
持ち駒:なし
  9 8 7 6 5 4 3 2 1
+---------------------------+
|v香v桂 ・ ・ 銀 ・v金v桂v香|一
| ・v王v飛 ・ ・ ・v歩 ・ ・|二
| ・v銀 ・v金 ・ 馬 ・ ・ ・|三
|v歩 ・v歩 ・ ・ ・ ・ ・v歩|四
| ・v歩 ・ ・v角 ・ ・ ・ ・|五
| ・ ・ 歩 ・v歩 ・ 歩v歩 歩|六
| 歩 歩 銀 ・ 歩 歩 銀 ・ ・|七
| ・ ・ 王 金 金 ・ ・ 飛 ・|八
| 香 桂 ・ ・ ・ ・ ・ 桂 香|九
+---------------------------+
持ち駒:歩四

リンク

amazon 4777511103 amazon 477751241X