はじめに
これは、手駒の優劣判定を現在のshogi686がどう処理しているかをありのまま説明するための記事。優れた判定方法について解説した記事ではない。最近、数学で証明をするようなカッチリした思考が苦手になってきたので、なんか間違ってたら教えてください。
持ち駒のデータ構造
持ち駒は先後64bitずつ計128bitで持っている。将棋の持ち駒は7種類なので、各駒の数をuint8_tで表しても1byte余る。32bitに収めるには各持ち駒のビット位置をテーブル引きするコストがかかるが、64bitあれば駒番号でアクセスできるため簡単高速である。
局面のハッシュ
局面のハッシュ値は、盤面のハッシュ値と手番側の持ち駒の和（xorではなくadd）としている。つまり、持ち駒のハッシュための乱数は使わない（少し高速化）。手番に関しては、持ち駒のデータ構造で余っていた1byteで後手側だけ特定のビットを立てればよい。手番側の持ち駒を足す操作は、手番がコンパイル時定数の状況（doMove内）で行うためコストが低い（先手番の持ち駒に固定しなかったのはこのため）（誤差レベルでしかないうえにCPUを選びそう）。
将棋の局面は盤面と手番と片方の手番側の持ち駒から一意に定まるため、この方法が成立する。ただし、このハッシュを駒落ちも含んだ定跡に使う場合、落とした駒なのか相手の持ち駒なのか判別できなくなる。よって、落とした駒に応じた乱数を加えるなどする必要がある（今どきそんなことする人いないだろうけど）。
盤面のハッシュはxorを使っているが、盤面のハッシュ値と持ち駒の更新は別々にやって最後に足すので、xorとaddの順番で値が違ってくるような心配はない。
足す相手が乱数なので、持ち駒の数そのものを使ってもハッシュ値の衝突は増えない（よね？）。
置換表でのデメリット
持ち駒を64bit全体に足しているため、ハッシュ値の一部のビットだけを使うときにデメリットがある。
局面のデータを置換表のどこに保存するかは、局面のハッシュ値の下位ビットで決める。しかし、持ち駒は64bit全体に散らばっているため、一部の持ち駒しか置換表エントリの位置に影響を及ぼさないということになってしまう。別にハッシュ値が被るわけではないが、持ち駒だけが違う局面の置換表での保存場所が被りやすくなり、有用な局面のデータが保存できなくなるケースが少しだけ増えそうなのだ。メリットとなるわずかな高速化は完全に吹き飛んでいると考えるが、実際のところはわからない。駒番号を変えたりPEXTを使ったりして緩和できるとも思うが、PEXTのコストが見合うかどうかもわからない。
ちなみに、手番は最下位ビットに入るようになっているので問題ない。大抵のソフトで、玉を除く成っていない駒の駒番号は1から7に割り当てられている。つまり、余るのは駒番号0の持ち駒に相当する部分（最下位バイト）になる。
手駒の優劣判定
さて、やっと本題。このハッシュを使うと、手番と盤面が同じであるような2局面のハッシュ値の差が、その2局面の持ち駒の差になる。盤面が同じなら盤面のハッシュ値も同じ（逆は必ずしも成り立たない）であり、引き算すれば相殺されて持ち駒の差だけが残るという寸法。
各持ち駒の数がuint8_tで7個並んでいるので、「4手前の局面と比べて先手の持ち歩が1枚増えただけ」という後手が絶対に避けるべき局面の場合、現在の先手の持ち駒から4手前の先手の持ち駒を引けば、「持ち駒に歩が1枚」を表す1bitだけが立った数値が得られる。手番のビットについては、千日手等の判定が手番が同じ局面同士でしか行わないので引き算すれば消える。
普通はこの判定を、持ち駒の数を格納するビットたち（例えば飛車なら0枚から2枚なので2bitぶん）の一つ上のビットを集めたマスクとのandで行う。これで繰り下がりがあったかどうかが判定できて、繰り下がりがあったなら減っている持ち駒があるから優越局面ではないとわかり、千日手でないうえに繰り下がりがないなら優越局面だとわかる。
しかし、この2局面のハッシュ値の差をとる方法では、同時に盤面のハッシュ値が一致するかどうかも判定しなくてはならない。よって、使用するマスクのゼロになっているビットを必要最小限まで減らす。駒が2枚増えることは検出したいので、各駒1bitでは足りない。各駒2bitと持ち駒7種で14bit。64bitのハッシュ値の差から14bitを除いた50bitに、立っているビットが一つもなければ盤面が同じであり優越局面であると判断する。
普通の方法と比べて、ハッシュが衝突する確率は16384倍くらいに上がったけど、元々（2の64乗分の1）が低い確率なのでそれほど問題ないと思う。以前は緩和策として、b & (b - 1)で立っているビット数が1以下であることを確認していたが、これだと「銀打ち同玉金打ち同玉で同一盤面」というビットが2か所立っているケースが漏れてしまう。金打ち2回なら、金2枚は0b10だから1bitしか立ってないのだけど。もっとも、ここは最後の確認であり速度はあまり必要ないので、単にpopcntして2より大きいものをはじけばいい気もする。
置換表でハッシュ衝突が頻繁に起こるのは、誕生日のパラドックスだから。千日手等の判定は16手遡っても7つの局面としか比較しないが、置換表を引くときは登録されている全局面から一致するハッシュ値を100%発見できる。コンピュータは1分で何億局面も読むので、64bitのハッシュを使っても長考すればどこかでは衝突する（最近は衝突する前提でもう少し短いハッシュを使う人が多いけど）。余談だが、保存場所を決める下位ビットを置換表に保存する必要はないので、技巧が32bitで浮かむ瀬が16bitだけどこれは25bit増とかで動いているのだ（置換表のサイズを2倍にすると1bit増える）。
ここは、特に大きなメリットはない。祖先ノードの、局面のハッシュ値だけを保存しておけば、盤面のハッシュ値や持ち駒が不要だというくらい。やねうら王のように、まず盤面のハッシュ値が同じかどうかで分岐してから千日手や手駒の優劣を判定したほうが速そうだ。
まとめ
ここに書いた中で役に立ちそうなアイデアは、持ち駒のデータ構造（手駒の優劣判定関係ないんかい！）。x64かつ持ち駒を置換表に入れない前提。
他は微妙。メリットが（あったとして）「わずかな高速化」しかないというのがいかにも味が悪い。自分はコードが簡単になるのでこういうのが好きなんだけど。
ソースコード抜粋
「各駒1枚ずつの値」は「3枚」の間違い。こういう、ソースを変えたのにコメントがそのままというコメントバグが多い。「先手の持ち駒が増えた」ってのも「手番側の」だよねえ。これはなぜそう書いたのか想像できない。手番側の持ち駒をハッシュに入れる手法なのに。
//千日手とか検出 const int k = Quiescence ? 4 : (depth < PlyToDepth(3)) ? 8 : 20;//遡る手数 for (int i = 4; i <= k; i += 2) { if (pos.forward(-i).key_ == 0) break; //(board_key_1 == board_key_2 を仮定すると) key1 - key2 == hand64_2 - hand64_1; const int64_t diff = pos.key_ - pos.forward(-i).key_; if (diff == 0) { //千日手 if (pos.continuous_check_[C] >= i) return -ScoreMate0Ply; if (pos.continuous_check_[OppositeColor(C)] >= i) return ScoreMate0Ply; return RespectFactor[1] * ColorToSign(C); } //board_key_が同じとは保証できないのでリスクがある(無視できるリスクだと思う) constexpr int64_t Mask = 0x0101010101010100 * 3;//Position::hand64_で各駒1枚ずつの値 const int64_t neg_diff = -diff; //-b == ~b + 1; ~b == -b - 1; popcnt(b) <= 1 ⇔ (b & (b - 1)) == 0 //if ((diff & ~Mask) == 0 && (diff & ~neg_diff) == 0) { if ((diff & ~Mask) == 0) { return ScoreMate0Ply;//先手の持ち駒が増えた } //if ((neg_diff & ~Mask) == 0 && (neg_diff & ~diff) == 0) { if ((neg_diff & ~Mask) == 0) { return -ScoreMate0Ply;//先手の持ち駒が減った } }
