特許の出願を行いました。

18-8. 第1回ビネクラ杯を終えて ―僕の夏休み―

とある参加者がエッセイを提供してくださいましたので、許可をいただき、日記形式に編集させていただきました。

寄稿者:yakiyamaさん(50代・男性・管理職)

8/7

誘惑

主催者の Facebook 投稿でコンテストの開始は当初から知っていた。やりたいなと思ったが、お盆の週までは手を出せない。知ってる人の名前が、2名もランクインしている。

8/10

リハビリ
「夏休みのコーディング」出典: 映画「サマーウォーズ」

仕事用のサーバーは使うことができない。雑事用のレッツノートに Visual Studio Code を入れてみる。busybox64 も入れる。いろいろ試したが動作が今一つ。python、、、うーん、老兵は C でいきます。許してください。

Hello world! とかを書いてみる。簡単なコードは書けるが、fgets の引数忘れてるレベル。これはかなり大変なリハビリになりそう。

8/11

動的計画法

2点を端点とする直方体内のみを考えて、一方向の動的計画法。これはさすがにすぐ作れないと本業が教えられない。x, y, zの差分がプラスマイナス両方あるので、dx, dy, dz = {-1, +1}。ここは汎用的に書いておく。

トレースバックは、ポインタを残しておく方針に途中で変更。あとから探しなおす方が全体は速くなるのだが、安全志向で。

トレースバック中に同点の方向がある場合、3(後には6)方向をランダム選択をしていたが、乱数をあちこちに使うと、解析や再現性が面倒かと思ってしまい、特定の方向を優先する仕様に戻してしまった。あとで後悔したが、大きな性能差はないはず?

せっかく動的計画法なので、ノードの評価を細かく行うことにする。今回これが一つの売りなのだが、どの程度貢献していたのかは未確認。単に経路長だけじゃないと思う。重要なマス目。そうでもないマス目。

-penalty オプション

死んでいるノードでも、そこを通過する経路は10点減点。まだ可能性のあるノードをつぶしてLineにしてしまった場合には、想定されていた経路長が短いものをつぶした時ほど大きな減点に。-penalty オプションで短い経路長のノードへの減点率を調整。想定経路長と減点の関係はいろいろ試したが面倒なので線形で。

-expectation オプション

周囲6方向を囲まれてしまったら、そのノードは死亡。まだ生きているノード達の唯一の出口にあたるノードは少し重視。そこをつぶすことで命を絶たれるペアがいるのだから。毎ステップごとに、唯一の出口を残してくだせぇと各ノードが投票。そうは言っても道路工事は続くのだが、少しだけ減点を重くする。-expectation オプションで投票による減点の重みを調整。

自分は生きていても、相方が死亡したら即死亡。最初の定義により、死亡ノードは、塗りつぶされても最小コスト。死亡ノードは、唯一の出口の投票には加われない。

今にして思えば、6方向のうち、あと何方向残っているのかをスコア化しても良かった。しかし、じゃあ3歩離れたところが全部囲まれているのはどうなんだとか、言い出すとキリがない感じ。

泣いて馬謖を
「馬謖を斬る」出典:漫画「三国志」 横山光輝著

候補ペアには皆に残って欲しくて、すべての候補ペアに(愛)を持って大切に進めていたが、それで壁に当たると、後半からは

 
みんな早く死ねば良いのに
 

とも考え始める。なかなか難課題。

距離の定義をマンハッタン距離に加えて、ユークリッド距離も検討し、マンハッタン距離が同じでも、立方体に近い形状の候補のほうが、通しやすいだろうと考えたが、ユークリッド距離の利用法はやや不明。検討余地が残っている。ユークリッド距離が遠い2点は結びにくい。

この課題では、1本を通そうとすると、他の多くの候補の可能性を奪ってしまう。8000マスに4000ペアがあるなんて淘汰が過酷過ぎる。したがって、無理に通せばよいのではなく、コスト感覚が重要。余り迷惑をかけるくらいなら、他人に命を譲ってしまうべき。(愛)

threshold

threshold 以下の減点で済む候補しか実際には敷設を許可しないで、次の候補に可能性を譲ることにする。これは最後まで採用した。おそらくコスト意識を導入した点が、最大の売りかも知れない。

thresholdは、既に敷設した本数(残っているマスの数などにした方が適切だったと今にして思う)に応じて、甘くしていく。某コスト関数では、最初が -100 くらいで、最後は -500 前後まで許容。線形に落としたり色々したが、現状はいきなり切り替えている。

完全に行き詰った場合、まだ候補が残っていればthresholdを少しずつ甘くして何度も試す。-5000 くらいで投了する。

-regret オプションと断罪
「泣いて馬謖を斬れよ」出典:アニメ「日常」

thresholdに到達しない候補は殺していたが、すこしマージンを準備して「敷設しないが後のために殺さず取っておく」オプションも設計した(-regret オプション)。ある程度のregretを確保。

これらの(愛)政策をかなり追求したが、けっきょく、合格点を取れないものは保留ではなく、断罪した方が良いと考え直す。(ここで自分の商売との類似性をいろいろ考えたが自己規制)

thresholdをうまく設計すべきで、regretマージンを確保するなど評価側の甘えだ、偽善だ、だめだこんな哲学はと思い始める。疲れてくると、(愛)風味は減ってくるのである。

-gekokujo オプション

候補選択において、与える影響を詳細に評価する「先読み」方式も実装したが、計算が遅くてしょうがないので、基本的には単純に距離が近い候補から優先検討。同距離なら、ランダムに選択。

ここに波乱を導入する -gekokujo(下剋上)というオプションを作っていたが、名称のダサさに心が耐えかねて、ソースから全部消してしまう。試みとしては面白かったのだが。候補群をqsortするためのルーチンをあれこれの版で検討。

ホルス神の域

上記をだいたい行った段階で(嘘です。いくつもの細かい修正は後で行いました)、夏休み1日目でとりあえずホルス神の最低レベルにはなれたが、そこからの微修正による上達は、1アイデア追加して5点、10点という歩み。1日目は本当に集中して遊ぶことができた。

8/14

ヒマラヤ級

2日目からが、なかなかスコアが伸びないのでつらかった。490~500領域、500~510領域、510~520領域は、ちいさな差に見えていたのだが、まるで世界が違うように認識。まるで3000m級、5000m級、7000m級の山々。富士山とヒマラヤは違うのね。このままの実装では500どまりだ。sakamotoさんの502にも到達しない。いったい1位のリアン神は、どこまで登っているというのか。

この時点で、1位はriantkbさん(525点)、2位はsakamotoさん(502点)でした。

え、セミナーあるやん

上記が楽しくて、つい後回しにしておいたが、2点を結ぶ直方体ではなくて盤面全体を自由に通る方法を作成。じわじわ水が染みだすようなアプローチで6方向。盤面変化しなくなるまでループを回す。書いてみたら簡単。後になって、ビネクラ杯のページを見ると、最初から2次元、3次元でこの方向を誘導してた事を知る。ていうか、コンテストに誘導するようにセミナーしてるんじゃん。どれだけ丁寧なんだビネクラ社。がーん、迷路の話は別課題と思ってた。なぜ先にこれをやらない俺。

結果オーライ

ところが、最初からこれをやるより、「直方体のDPでダメだった時だけ」、これを発動するほうが性能が良いことがわかった。まずは3方向で進み、ダメだったら出発点から6方向を発動。理由がいまいちわかっていないが、結果オーライということで、DPを最初に起動し、その盤面から回り込み経路を追加計算。

最初に自分が得意なDPで書いたことが結果的に良かった気が。評価関数の設計に凝ることに1日目を費やしたのが楽しかった。

万策尽きて
「万策尽きた」出典:アニメ「SHIROBAKO」

万策尽きて、ガチャを回す。思っていたより、、楽しい。候補をqsortするとき、マンハッタン距離が等しい経路候補間では乱数で上下関係を決めている。このランダム性がかなり影響する。

しかし、なにしろ手元のリソースがレッツノート1台なのでな・・・あ、でもdual coreって偉大なのですね。仕事しながらでも大丈夫だ。ビデオ見ながらでも計算できるのだ。とりあえずスコアは520台までは伸びたので、暫定2位にはなれる。ガチャは少し恥ずかしいけれど、ランダムネスは探索の王道だな。

酸素マスク

520より上は酸素マスクなしではきつい。525を叩き出したリアン神は遠い。「523と525では違うのだよ!」

50万コア並列とか研究してた私が、どうして1コアでガチャするのか。自分の人生を見つめ直した方がいいよ(心の声)。実践が伴ってない。

終末

全体を木探索に変更した版も作成。たとえばスコア523まで進むことができたものから、522に戻って残る有力候補を全回し、それがだめなら521に戻って・・・しかし、すこし戻っただけでは出口は見つからない様子だ。

このペースのバックトラックでは、出口への分岐が500前後にある、と仮定して推測すると・・・

 
太陽系の終末が見える
 

というか、私の夏休みが確実に終末する。太陽系が死んでも計算継続したいが、夏休みが終わるので、諦める。

そっとバックトラック用のコード全部のディレクトリを閉じる。しかし、ビネクラ社も木探索推しだったように思うが、他の人々は木探索で書いているんだろうか。自分のバグだろうかと思い悩む。(レッツノートでなく、仕事用のスパコンを使えばよいかなと思うが、実は最近ほとんど使ったことない(秘)。しかも業務外利用。)

挫折心

深い挫折心を抱えながら、盤面評価のパラメータの感度解析やら、最適設定の探索を少々。どのアイデアも、入れないよりは入れたほうが「わずかに」良いだけで、パラメータを変えても明確なピークが見当たらない。せっかくコードしたのにと思いながら、テキトーな値に設定。仕事ならもっと丁寧に探索するのだろうが(たぶん嘘)。

こういう作業をwindowsでする苦痛。MacBookと一緒に開発環境を手放し、長い年月、プログラミングから離れていたことを、ほろ苦く認識する。お気持ち程度、速度最適化をして、また一晩レッツノートでガチャ。

「どんどん処刑してみた」
「ルイ16世の処刑」出典:Wikipedia「ギロチン」

この頃は心がすさんできたのか、(愛)ではダメだと考え始める。まず経路長が長そうな(例:>20)候補は、開始直後に全員処刑。経路なんてものは、長さ15以下の若手だけで固めれば良いのだ。

経路長が15以下は前途有望な候補であるが、経路長15~20は、たまに仲間に加えてやる程度でほとんどは捨てるのである。そこでどんどん処刑してみたが(悪)、あまりよくならない。何にもならないこの肥満のおっさんらがなぜ必要というのだ。これら中年込みでパラメータ調整をしてしまったためか。中年以上みんな居なくなれば良いと思ったのだが、どいつが善玉かを予測するのは困難なので、生かしておくしかないのか。thresholdの設計が難しい。中距離の善玉だけを残す方法は?

-kill_rate オプション「全員処刑だ」

-kill_rate オプションで、このあたりのおっさんノードをランダムに初期処刑することにする。だいたい5%を間引きして、95%は残しておくような(なまぬるい愛)のほうが良いかと考えた。中年を大量に殺しても改善はしないが、いくつか殺しておくと、「あのオヤジさえいなければ俺たちの道が閉ざされなかった」ようなケースが救われるのではないかと思うので。そう思わざるを得ないほど、中距離を通すコストは高いのだ。あいかわらず経路長20を越えるトンデモ候補は全員初期処刑。こいつらを無理して入れても、スコアは1しか伸びないので。座席は若い人に譲りましょう。

これでスコア523前後までは連発する。ラッキーなことに525も見つかった。休み中でも仕事は滝のように流入してくるし、もうリタイアするかも知れないので、とりあえず525を投稿した。(この頃は525は貴重だった)

yakiyamaさんが525点を提出しました。(暫定同率1位)

8/18

憧れの先生

もう夏休みの時間は残り少ないし、映画も10本くらいしか見られていないものの、まだ微かに、忘れていたはずの自尊心がうずく。

 
あのね、おじさん、若い頃は組み合わせ最適化が好きだったの
 

あのね、ホップフィールドという憧れの先生とお友達になってね。それでね…
 

(あれ、どこにいくのかな、怖がらなくていいのに。)

-checkpoint オプション、-warp オプション

木探索の考え方を根本的に変えてみる。前回の深さ優先全解探索の単なる改良ではなく。ガチャで、525とか524点まで行けた時の、490, 500, 510, 515, 520などの節目節目の内部状態全部をファイルに吐き出せる -checkpoint(チェックポイント)オプションを製作。それらのポイントから別の乱数seedに切り替えてリスタートできる-warp オプションも作成。warp後は、乱数によって候補選択において長さの順序を越えられる可能性を高くする。ここからは運命が変わらないと面白くないから。

単独1位となる527点

これで525、526、527などが連発。トップのリアン神(525点)の技術レベルにやっと追いついた。(でもあちらは問題発表後に3日以内くらいで投稿している。こんな醜い試行錯誤はしていないだろう。どんな綺麗なコードだ。国際レベルのレッドコーダーって、本当にしゅごい。)

riantkbさんは8/2時点で525点を提出していました。日本でも10本の指に入るレッドコーダー(要出典)。

「うるさい、暑い」
「サーバーを氷で冷やす」出典: 映画「サマーウォーズ」

これでガチャをまわせば、530くらいは出そうなのだが、、どうやらあまり簡単ではなさそうで、527で足踏みしている。すごく古いノートも持ち出して、各dualコアで2台同時に回す。このノートは2011年製、あの大震災の直後に買ったものだが、ハードウェア不調でしまってあった。

数年前の製品だからか、ハード不調だからか4倍くらい遅い、それはまだしも、すごい発熱である。。本当はどちらも4スレッドずつだけど、新ノートは3並列、故障している旧ノートは2並列でまわしてみる。

古いほうのレッツノートの下に鉄製のフライパンを置き、間にアルミホイルで端がギザギザの放熱板を簡易製作してみる。うるさい、暑い。冷房がきかない小部屋でやる作業じゃない。どこかでみた風景。『サマーウォーズ』か・・・。東京は信州上田よりも暑い。

yakiyamaさんより提供

あれだけ貴重だと思っていたスコア527は百回くらい出てきた。異なる解が含まれていることは、経路長を分析するプログラムで確認。少しずつ改良すると、少しずつ伸びる。。

人生をやり直すなら何歳から?

木探索をするとき、深さ優先や幅優先で全解網羅するのではなく、良かった「個体」の「少し若い時」をコピーして配って、そこからガチャを回し、その中で親を越えた「個体」の「少し若い時」を配り、、という半遺伝的アルゴリズムが作れるぞと思った(既知か?)。510とかになった老体を配っても別解が見つからない。490とか、480とかの壮年時代の盤面を配るのがよさそうだ。若い時の暗中模索をさせる必要はないが、少なくとも壮年からの展開には個性が必要だ。これを自動化したらいろいろ汎用性がある。(最適化好きだったのに)

しかしあいかわらず、527より上にいかない。少なくとも450くらいからやり直すとよさそうだ。450から人生やりなおしても、527に到達できることはわかった。430からだと525しかまだ到達しない、少し若過ぎるか試行が足りない。計算の早さも勘案すると、480からの人生再チャレンジにして、せこく1点アップの528を狙うくらいしか、最後の一日では困難か。

「どのくらい若い時」からやり直すか、それを試行錯誤するのも、並列で探索させ、うまく行きそうな盤面とその年齢を遺伝子として他の計算ノードに配るような自動システムを作ればよいのだが。これは、GAとはちょっとだけ流儀は違うけれど遺伝的な枠組みに近い。

夏の終わり

やればできるのだが。夏は暑い。体力がない。

 
夏休みが終わる。
 

某夏祭りの手伝いで徹夜明けだし、そろそろ仕事がチョモランマ。月曜から4日連続講演。県関係者、財務省幹部、大臣視察、市役所。なんで完全に独立なはずの予定が4日連続になるのか?っていうと、霞が関や市役所の連中には、8月の来週がきっと格別暇な週なのだ。

 
夕方になってしまった。夏の終わりのト短調。
 

リタイア宣言

なお私はyakiyamaで525をお送りしており、手元に527はありますが、おそらくそれをお送りしたら、この週末でコンテストから離れます。

おかげさまで楽しい1週間(途中2日は所用で抜けましたが)でした。リアン神は近くにいる若手で、私の527を見たら、もしかしたらさらに素晴らしいスコアを再投稿されるかも知れませんが、これから競プロの大会?で忙しい時期だと伺っていましたので、どうなるかは判りません。(もちろん、本件についてプレイヤー間の相互連絡は一切しておりません。)

yakiyamaさんが527点を提出しました。(暫定1位)

8/19

フラグは回収される

riantkbさんが533点を提出しました。(暫定1位)

8/21

スリップストリーム?

yakiyamaさんが530点を提出しました。(暫定2位)

8/31

夏休みの宿題

白砂の海岸で砂遊びをしていたら、ビネクラ杯でやり残したアイデアをふっと思い出してしまい、宿で実装したところ少しだけスコアが伸びました。あるマス目を残してくれと周囲が投票するときに、じわじわと埋まり始めた頃合いから、弱めに投票ができるように段階化したような感じです。

いかんせん砂浜でノートブックは使えないのと、ワガママな家族の専属運転手をしていたため、ガチャ時間が足りないのが残念ですが、ギリギリで夏休みの宿題をやるとこういうことになります。日焼けがひどくて、イブプロフェンを大目に服用してしまったので、若干、ラリ気味でございます。

「去りゆく古代エジプトの王」出典:アニメ「遊☆戯☆王」

yakiyamaさんが537点を提出しました。(暫定1位)

僕の夏休み

コンテストでは、他人を蹴落として勝ちたいならば、最終日に自分の最良解をいきなり投稿すれば良いことですが、途中で暫定解を送ることが許されているために、他のライバルの方々の努力を感じることができ、自分も発奮できました。

このように途中で暫定解を公開するというやり方は、競技性よりも、オープン性を重視した良いやり方だと思いました。一方、幅広い参加者層があるでしょうから、あまりにも高いスコア(525は驚愕しました・・)を見て、それが参加者にどういう影響を与えるかというのはあるのかも知れません。

おっしゃる通り、8/2に500点超えが提出され、暫定ランキングに反映すべきか迷いました。いずれにせよ、ご参加ありがとうございました!

xtxtxさんの記事もどうぞ

第1回ビネクラ杯でスコア517を取る方法(Cythonの布教も兼ねて) - Qiita
# ビネクラ杯について こちらのリンクでご確認ください(ビネクラ社の皆様。楽しませていただきました!ありがとうございました)。

タイトルとURLをコピーしました