王手回避の順序
手を生成するときに、もし自玉に王手がかかっていたら王手回避を生成するんだけど、王手回避する手のオーダリングはどうすればいいんだろうか? そもそもそんなことは考えなくて良いのか? 王手回避は延長絡みでかなり時間を食うことがあるので、ここをうまくオーダリングできると効率化できる気がする、んだよな。
「人は駒得のみに生くるにあらず その4 - ひよこ将棋、はじめました。」では、王手回避手は特にオーダリングされていない。「YSS 7.0の技術解説」では、「王手を避ける手では、王手駒が取れる場合、その手を最初に読ませると効率がよい」とのことなので、逐次生成するときに考慮しているんだろう。れさぴょんの AntiCheck関数も 両王手回避→王手駒捕獲→玉移動→合駒の順に生成している。
問題が面倒臭いのは置換表の存在。王手延長等により置換表の値を使う場合、前回の探索深さが充分であったかどうかも問題になりそうな気がする。たまたまそのときの探索深さでは詰まなかっただけの値が置換表に乗っかっているかもしれない。PVと非PV局面の探索深さに差があるとなおさらだ。たまたま深さが足りなくて不詰みと判定された置換表を信じて、自玉の詰みを不詰みと誤認するのは、まずい気がする。
持ち駒が充分にあれば、只捨ての王手を続けることができる(穴熊等を除いて)ので、王手延長はかなりの長さに成り得る。無限に王手の延長を続けるわけにはいかない。sakurapyonのような遅いプログラム(とサーバー)ではなおさらだ。
- 置換表にない(初見)
- 生成順番だけで制御?
- Killer MovesやCounter Moveを見る?
- 置換表にあった
- 深さが充分である
- 延長の結果、今回の探索深さが前回を上回るかもしれない? (その結果詰むかもしれない)
- これ、真面目に再検索するのもあほらしい気がする、が…
- 深さが足りない
- でも、探索表にある手を先に試してみる価値はあるんじゃね?
- 特に、詰まない指し手が1手しかないなら、それを試すべき
- そもそも詰む局面を先にしらべるべき?
- それがわかれば苦労はしない。
- 深さが充分である
きっとこんなことは先人がとっくに考えているんだろうな。個体発生は系統発生を反復する。
メモ:
何か変だ
sakurapyonのレートが赤丸急上昇中!俺も凄いなーと思ったんだけど、何か変な気がする。
Hot Jupiterさん(名前かっこいい。系外巨大惑星だよね)とかKakinoki-Zさんとか、いまのsakurapyonの実力では一発すら入らなそうな相手に連続time up勝ちしています。garyuさんにも三連勝中。何が起こってるんだろ? Hot Jupiterさんは5時の回からtime upしてるっぽいので、何かトラブルかもしれません。ISPの回線絡みかな、もしかして。
そういえば、sakurapyonの勝率が時間によって変動するのでおかしいなと思ってたら、サーバーの cron が裏で重たいジョブを実行していた、なんてことも。いや、sakurapyon が間借りの身だから裏なんて言っちゃいかんか。
記念にレーティング画面を保存しておこう。二度とここまで上がらないかもしらんし。
王手回避 with Counter Move
問題: http://www.shogitown.com/school/judge/j-21.html
以前はこれすら解けなかったのは内緒だ。
置換表の手を1番目にした上で、カウンター手を2番目にしたときと、そうでないときの差を見てみた。
NPSが落ちてるけど、早めに反復深化が進んでいる。たぶん有効...なんだろうな。要検証。
そもそも2番目が良いの?ってのもありそう。置換表の手は1位で良いと思うんだけど。
王手回避 with COUNTER_MOVE
1. -431( 0): 1 ▲32龍(23)
1. 366( 2): 1 ▲34龍(23)
2. 83( 0): 3 ▲34龍(23)△58角打
2. 184( 23): 150 ▲41金打△41玉(31)
3. 403( 0): 1049 ▲41金打△41玉(31)▲21龍(23)
4. 296( 0): 3980 ▲41金打△41玉(31)▲21龍(23)△31金打
5. 73( 0): 14446 ▲41金打△41玉(31)▲21龍(23)△31金打▲11龍(21)
6. 160( 0): 100215 ▲41金打△41玉(31)▲21龍(23)△31金打▲11龍(21) △57角打
6. 822( 21): 325120 ▲24桂打△57角打▲88玉(79)△79角打▲79金(78) △79角成(57)
7. 749( 0): 496774 ▲24桂打△57角打▲88玉(79)△79角打▲79金(78) △79角成(57)▲79玉(88)
8. 1956( 0): 1749910 ▲24桂打△57角打▲88玉(79)△79角打▲98玉(88) △42玉(31)▲32龍(23)△53玉(42)
探索打ち切り: depthMax/iter/max=20/9/16, time=60.852秒, 3825864 nodes, 62871.359 nps
bestVal: 9. 1956 (1956): 3825864 ▲24桂打△57角打▲88玉(79)△79角打▲98玉(88) △42玉(31)▲32龍(23)△53玉(42)パス(00)
leafcount:19473519, nodecount=3825864, nullcount:3151225, nullcount2=2633379, futilitycount=9966067,9943998,
PVS 1.firstmove:1031147, 2.second-last:19114621, 3.re-search:0, 4.re-search-full:2364
matecount=0/0 (nan%),
王手回避 without COUNTER MOVE
1. -431( 0): 1 ▲32龍(23)
1. 366( 2): 1 ▲34龍(23)
2. 83( 0): 3 ▲34龍(23)△58角打
2. 184( 23): 150 ▲41金打△41玉(31)
3. 403( 0): 1047 ▲41金打△41玉(31)▲21龍(23)
4. 296( 0): 4317 ▲41金打△41玉(31)▲21龍(23)△31金打
5. 73( 0): 14479 ▲41金打△41玉(31)▲21龍(23)△31金打▲11龍(21)
6. 160( 0): 87005 ▲41金打△41玉(31)▲21龍(23)△31金打▲11龍(21) △57角打
7. -103( 0): 511362 ▲41金打△41玉(31)▲51歩成(52)△51銀(62)▲21龍(23) △31金(32)▲11龍(21)
7. 1779( 32): 1656535 ▲24桂打△42玉(31)▲32龍(23)△53玉(42)▲21龍(32) △92飛(82)▲51歩成(52)
8. 1956( 0): 2543809 ▲24桂打△57角打▲88玉(79)△79角打▲98玉(88) △42玉(31)▲32龍(23)△53玉(42)
探索打ち切り: depthMax/iter/max=20/9/17, time=60.852秒, 4489401 nodes, 73775.731 nps
bestVal: 9. 1956 (1956): 4489401 ▲24桂打△57角打▲88玉(79)△79角打▲98玉(88) △42玉(31)▲32龍(23)△53玉(42)パス(00)
leafcount:23452553, nodecount=4489401, nullcount:3753107, nullcount2=3099225, futilitycount=9797621,9772540,
PVS 1.firstmove:1208688, 2.second-last:22977734, 3.re-search:0, 4.re-search-full:2405
matecount=0/0 (nan%),