タグ

2022年6月2日のブックマーク (1件)

  • 難解作品が解ける詰め将棋エンジン KomoringHeights v0.5.0 を公開した

    合流検出の実装はかなり複雑だ。詰将棋探索では探索中の局面を置換表(メモリ)に保存する必要があるのだが、合流検出のためにはこれを増やす必要がある。具体的には、v0.4.1 では 1 局面あたりの置換表エントリサイズは 32 byte であったのに対し、v0.5.0 では親局面のポインタ(12 byte)と合流フラグ(8 byte)を追加で持たせているため、サイズが 56 byte(1.5倍)に膨れ上がっている2。 さらに、合流検出のアルゴリズム自体もそれほど単純ではない。合流の可能性がある局面を見つけるたびに、再帰的に局面をさかのぼって合流検出のフラグを立てに行く必要がある。1回の計算量は大したことがないが、長時間探索する場合は無視できない計算量になりうる。 これらの理由から、合流検出を実装したことでNPS(単位時間あたりの探索局面数)がかなり低下する……はずだった。しかし、置換表のデータ構

    難解作品が解ける詰め将棋エンジン KomoringHeights v0.5.0 を公開した