地平線効果に関するメモ 7月14日 YSS資料 山下 宏

・5手1組の手損の打開。
先手の飛車が28にいる場合に、
▲24歩△同歩▲同飛△23歩▲26飛
といった手損する変化を避ける。
△23歩の後に、元いた位置に戻る▲28飛、や1手で行ける▲25飛、▲26飛を
読まない。（地平線効果の可能性が極めて高いため）
自陣から敵陣で成って戻る場合は別。

・ハッシュがあふれた場合に、エントリー（16箇所）にヒット回数を
　記録しておき、最低数と交換。(証明数詰で検証）

・飛車の威力で詰めろがかかっている場合に、飛先に歩を叩く手でも
　詰めろ探索を延長。
・王手をかけて最後に駒を取られると、類似ハッシュでは合駒で
　詰む場合に不詰。部分的に実際に探索。
・合駒は無駄合（仮想合）でも生じる。


・地平線効果

・広義の地平線効果。2手の交換によって局面の評価値が下がった場合。
--> 歩を叩いて取られるのは通常。
--> 遊び駒の金を打って飛車が逃げる。（ルートでのみ2手延長している）

・現状のYSSの対策。
歩を叩いて、それを同〜と取り、次の手が最善手になろうとしている場合に、
その手の探索を探索限界を+2して再度探索（2手延長）。


後手：ＩＳ将棋
後手の持駒：なし
  ９ ８ ７ ６ ５ ４ ３ ２ １
+---------------------------+
|v香v桂 ・ ・ ・ ・ 角 ・ ・|一
| ・v玉v金 ・ ・ ・ ・ ・ ・|二
| ・ ・v銀v歩v歩v金v桂v飛v香|三
|v歩v歩v歩 ・v銀 ・ ・v角v歩|四
| ・ ・ ・ 歩 ・v歩v歩v歩 ・|五
| 歩 ・ 歩 ・ 銀 ・ ・ ・ 歩|六
| 香 ・ 桂 金 歩 歩 歩 歩 ・|七
| ・ ・ ・ ・ 飛 金 玉 銀 香|八
| ・ ・ ・ ・ ・ ・ ・ 桂 ・|九
+---------------------------+
先手：COM1
先手の持駒：歩　

▲PASS△21飛▲13角成△同角 ・・・4手読みでの最善手順（末端取り合い評価なし）

▲83歩△同玉▲PASS  △PASS ---> ▲PASSは最善になるので延長される。
▲83歩△同玉▲PASS  △21飛▲13角成△同角 ---> この手順で無意味なことが判明

▲83歩△同玉▲13角成△同角 ---> ▲13角成は最善にならないので延長されない。


            ▲PASS  △21飛 ---> ▲PASS には△21飛、1手だけを読めばいいか？
                           ---> 直前の駒捨てによって最善手が変わるので危険。
                           ---> 駒交換が続く場合は未知の手が出てくる。


(2手の交換が無意味なもの、という証明をしたいから）
---> 歩を叩く手が有効な場合、2手深い完璧な値を求めてしまう。無駄。
---> 改良案。2手深く読む探索をNULL Windowで行う。High失敗した場合は
有効なので2手延長する前の値を採用。
---> 一度有効と判明した手は2度と2手延長しない。ハッシュに残っていればOK。
なければ、次の反復では+1手の延長、次々回の反復では必要なし？

---> 駒を捨てる手は最後に必ず読むようにすれば、２手前の最善応手手順が
そのまま反駁手順になる？


全幅探索プログラムでの実験

基準プログラム
「捨て駒なし」・・・部分的な駒交換で損な手は一切読まない。地平線効果０。

※だいたい平均、5〜6手の深さまで読める。1手1秒。Athlon 1.2GHz
(ハッシュ利用、多重反復深化、仮評価で上位8手ソート、最大256手まで生成)

                                      勝 負 引
「完全全幅」          - 「捨て駒なし」12-88-0
「残3で全幅」         - 「捨て駒なし」38-61-1
「残4で全幅」         - 「捨て駒なし」48-52-0
「残5で全幅」         - 「捨て駒なし」52-48-0
「残3で2手延」        - 「捨て駒なし」46-53-1
「残4で2手延」        - 「捨て駒なし」51-47-2
「残5で2手延」        - 「捨て駒なし」58-42-0
「残3で2手延NULL」    - 「捨て駒なし」51-48-1
「残4で2手延NULL」    - 「捨て駒なし」52-46-2
「残5で2手延NULL」    - 「捨て駒なし」65-34-1
「残3で2手延NULL有効」- 「捨て駒なし」54-45-1
「残4で2手延NULL有効」- 「捨て駒なし」66-34-0
「残5で2手延NULL有効」- 「捨て駒なし」72-28-0

残5   ・・・ 残り深さ５の時、捨てる手も全て読む。
2手延 ・・・ 捨てる手が有効な時、2手延長して確認する。
NULL  ・・・ 2手延長探索をNULL WINDOW探索で。
有効  ・・・ 有効と判明した捨てる手は2度と延長しない。

---> 欠陥があるかもしれないがNULL＋有効非延長は、効果があるか？
---> 駒打だと捨てる手の数が増えるので、あまり読まない「残5」が最強か？
---> 駒捨てが有効なのは最低でも3手の読みが必要。