捕獲先読み講座　　レベル３　　探索空間を絞る　　(2000-08-27)

レベル２まで達成できれば、次に挑戦するのはレベル３です。しかし、レベル３を
達成しないでレベル４以上のことをやろうとするのは無謀です。

縦形探索では
  追う側と逃げる側がまるで協調するかのように長手順を展開したり、同一局面を
  繰り返すことがあります。
  同一局面を２度読みしないようにする必要がありますがそれよりも絞り込みのほ
  うがとりあえず重要のようです。

これらに対する対策は
  同一局面を２度読みしないようにするにはハッシュを使うなどします。
  長手順を展開させない方法としては
    有効そうな枝から調べること。
    意味のない枝は調べないこと。
    調べる深さを制限すること。

第１にトライすべきことは調べる深さを制限してしまうことです。
例えば、無制限に読ませる方式だと正解が３手の深さにあっても、その枝を調べる
チャンスがこなかったりする。しかし、５手の深さに制限すると、正解ではない枝
はことごとく５手で打ち切られ、短手数で正解の枝に到達します。

ただし、シチョウという特殊な状況は良く発生するので、制限手数に達してもシチ
ョウ条件になっている限り探索を延長したほうが良いです。他にも延長するべき条
件はあるのですが、ここでは置いておきます。

第２には有効そうな枝から調べることでありますが、これはなかなか奥が深く、簡
単なことから実装していくべきであろうと思われます。

【逃げの基本】

   空き３点の場合

       ┼      ダメが２つ増えるかもしれない。１石取るよりも優先かな。
     ┼◆●    
       ┼      

   空き２点・追う石１点の場合

       ○      ダメが１つ増えるかもしれない。ダメ２連のアタリ以上かな。
     ┼◆●    
       ┼      

   空き１点・追う石２点の場合

       ○      ダメは減るかもしれない。周囲の石が取れない場合は最後にまわ
     ○◆●    してよいかもしれない。
       ┼      

   空き０点・追う石３点の場合

       ○      周囲の石が取れない場合はダメが１つ減ります。着手禁止ですら
     ○◆●    ありえます。これも最後にまわすべきです。
       ○      

   空き２点・逃げ石１点の場合

       ●      異なる連の連結の場合、ダメが増えるかもしれない。
     ┼◆●    連同士の共有するダメも考慮に入れる必要があります。
       ┼      

   空き１点・逃げ石２点の場合

       ●      
     ●◆●    
       ┼      

   空き０点・逃げ石３点の場合

       ●      
     ●◆●    
       ●      

   空き１点・追う石１点・逃げ石１点の場合

       ●      
     ○◆●    
       ┼      

   追う石２点・逃げ石１点の場合

       ●      
     ○◆●    
       ○      

   追う石１点・逃げ石２点の場合

       ●      
     ○◆●    
       ●      

【逃げ候補「パス」】

  群レベルの捕獲探索があれば、連レベルの捕獲探索では不必要かもしれないです
  が逃げる候補にパスを入れておくとわざわざ自滅するような手順を省くことがで
  きます。

   ＡＢＣＤＥＦＧＨＪＫＬＭＮＯＰＱＲＳＴ  
 01┏┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┓  
 02┠┼┼┼●●●●●●●┼┼┼┼┼┼┼┨  
 03┠┼┼┼●◇◇◇◇◇●┼┼┼┼┼┼┼┨  
 04┠┼┼・●◇┼◇┼◇●┼┼┼┼・┼┼┨  
 05┠┼┼┼●◇◇◇◇◇●┼┼┼┼┼┼┼┨  
 06┠┼┼┼●●Ａ●●●●┼┼┼┼┼┼┼┨  
 07┠┼┼┼┼●●●┼┼┼┼┼┼┼┼┼┼┨  

  黒Ａときたとき、白はパスをすれば「取れない」となりますが、逃げる候補にパ
  スがないと、すべての逃げる手で「取られる」となり、黒から「取れる」と判定
  されることになります。とすると、黒Ａの評価値は高い事になってしまいます。

【中央へ逃げる優先】

  ノビる手が２個所ある場合、中央へノビると枝刈りが早くなる傾向があります。
  辺へノビると延々と読んでしまいます。
  たとえ辺へノビる手がアテる手を兼ねていても、中央へノビた方が包囲網をたや
  すく突破できることが多くて、その先少しぐらい深く読むことになっても、それ
  だけで済んでしまうために、全体として読む局面数が激減することになるようで
  す。

  トル手やアテる手などで同順位に扱っていたものも中央に近いほうから並び替え
  ると読む局面数が減る傾向にあります。

  正確に言えば、「広い方」へ逃げるということでありますが、これはレベルが高
  いです。

【追う候補の並び替え】

  捕獲連のダメ詰めは追う基本です。
  その候補点に逃げる側の石を置いてみたときの捕獲連のダメが大きくなるほうか
  ら並べ直します。

 ┼┼┼┼┼┼   追う側が黒とする
 ┼┼●●┼┼   白をＡに置いてみた場合、ダメは４
 ┼●○Ｂ┼┼   白をＢに置いてみた場合、ダメは２
 ┼●Ａ●┼┼   捕獲連の呼吸点に限定すると、追う候補の優先順位は
 ┼┼○┼┼┼     黒Ａ ＞ 黒Ｂ
 ┼┼┼┼┼┼

第３には、意味のない枝は調べないことでありますが、厳密には難しいようです。
勝手な判定をしたほうが実践的には有用性が高くなりますが、致命的な読み間違い
をすることもでてきます。

   ○●○┼┼  Ａの地点にほうり込んだら   ○●○┼┼   ○●○┼┼
   ●○Ａ○┼  白のダメが詰まっていない   ●○○○┼   ●○○○┼
   ●Ｂ┼┼┼  ので無意味                 ●●○┼┼   ●●┼┼┼
   ┼●┼┼┼  または不利が明らか         ┼●┼┼┼   ┼●┼┼┼

   ○●○┼┼  Ａの地点にほうり込んだら   ○●○┼┼   ○●○┼┼
   ●○Ａ○┼  白のダメが詰まっているの   ●○○○┼   ●○○○┼
   ●Ｂ┼┼┼  で意味があるかもしれない   ●●○┼┼   ●●┼┼┼
   ┼●●┼┼                             ┼●●┼┼   ┼●●┼┼

死活や攻め合いなどではまた違った様相を呈するので油断が出来ません。