極小反例を探す長いジャーニーが終わった

UNDOには大分てこずったが,なんとか落ち着いたようだ.極小反例サンプルは307点まで縮小することができたが,サンプル生成中にスタックオーバーフローが発生する.スタックオーバーフローが発生する時点はまだ特定できていないが,極小反例307.ZELから開始すると,単点削除検査を24回繰り返したところで発生することは確実なので,シューティングは時間の問題と思われる.障害はUNDOBASE::CommandEnd sc=478の後に発生しているので,まず,ここで停止してみよう.⇒i=20から開始してもスタックオーバーフローが起きる.多分,i=24から一発で再現できると思うのでやってみる.⇒再現する.

障害はカード@233をFAMILYTREE::DeleteCardDataで削除→ UNDOBASE::CommandEndの出口→ TopologicalSortを実行で起きている.TRIBEBOX::StackTribeGene→ TRIBEBOX::CompleteTribeBox→ HorizontalSegmentで起きる.⇒TightenUpLooseで起きているようだ.⇒MAXIMALGRAPH::tightenUpLoose→ TightenLowerBoxのようだ.⇒どうも,かなり筋の悪い障害だ.障害の発生する時点が刻々と変化してしまう.エラートラップにも落ちないようになって,最後はスタックオーバーフローも発生せず,Access violationで終了になってしまった.⇒NAMEBOX::TightenLowerBoxでGP例外が発生している.

どうも,このTightenLowerBoxで循環が発生しているように思われる.⇒以下のような三つ巴の再入呼び出しが実行されている.

MAXIMALGRAPH::IsMargBoxFixed→ MAXIMALGRAPH::IsNameBoxFixed→ NAMEBOX::TightenLowerBox→ MAXIMALGRAPH::IsMargBoxFixed

また,IsNameBoxFixedは自分自身を再帰的に呼び出しているが,この呼出では深いネストは発生していないように思われる.⇒いや,入っている.むしろこれが原因かもしれない.基本的にこれらの呼び出しは垂直に下降する方向に進むようなフローになっているはずなので,循環するというのはかなり奇妙だ.再入経路にはいろいろなパターンがある.

TightenLowerBox→ IsMargBoxFixed→ TightenLooseBox→ TightenUpLoose→ CheckMaximalCompaction→ MaximalCompaction→ TightenUpLoose→ TightenLowerBox→

これは,かなり無茶な仕掛けと言ってよいのではないだろうか?⇒MAXIMALGRAPH::TightenUpLooseの中からTRIBEBOX::CheckMaximalCompactionを呼び出すという動作を抑制するようにした.⇒これで問題は解けてしまった.すでに問題は解決しているので,この件に関してはもはや「極小反例サンプル」というものも存在しない.⇒試しに,CollatzTest 3000-4619.ZELを開いてみよう.これはコラッツ検証テストが出力した4619点サンプルだ.⇒問題なく開けた(と言ってもループカウント43でギリギリだが).計算完了までに2分近く掛かっている.

image

長いジャーニーになったが,収穫は大きい.UNDOを見直す機会が得られたこと,また古い年老いた蛇をついに捕らえることができたことなど…この不良はバグというよりは,設計ミスと呼ぶべきだろう.今回確立された「極小反例サンプル抽出の自動化」という技法は応用が効くので,今後のシューティングの決め手になるだろう.実際,今回は「極小反例サンプル」に到達する以前の段階で,不良をあぶり出すことができた.数千点というような大規模なサンプルで起きている障害をこれまでのような方法で追いかけていてもおそらく埒が明かなかったのではないかと思う.4600点から300点くらいまで縮小できれば自ずと見えてくるものがある.⇒リリース版を起こしておこう.「Version 2.2.2.008 Release 2022-04-26」とした.

インストールしようとしたら,また,何か分からないことを言い始めた.確かにどこかで見た記憶はあるが,通常は発生しない…

image

アンインストールしようとしても,同じメッセージが出てくる.⇒2.2.2.003.msiの場所を探してアンインストールした.コラッツ木生成ツール→VerifyでTest count:5000を指定して,Open Zelkova Treeで開くことができた.生成されたサンプルは7925点で,現在設定されている最大カード数=8192=0x2000のほぼ上限に近い.とりあえず,このくらいまでできればよいのではないかと思う.

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA