マラソンマッチにおける精神論
この記事は、
Competitive Programming Advent Calendar 2014 - PARTAKE
の、マラソン版の12/4の記事です。
技術的な要素は少ないので、技術的なものを求めている人は、他の記事を見に行きましょう！
今日担当だって気づいたのが前日午後９時で、１時間書けずに書いてるので、内容に粗があるのは許してください・・・。
この記事を読む上で、まず解ってて欲しいこと
そもそもマラソンマッチとは何か？
TopCoderにおける、Marathon Match部門の事を指します。
2週間で、どれだけ良い解を出力するプログラムが書けるかを競います。
今回は精神論なので、もっと
どんな問題が出るの？
最適化問題だったり機械学習問題だったり。めんどいからググってください。いくらでも出ます。過去記事にもいくらでもあります。
これは誰向けの記事なの？
自分向けです。自戒です。他の人が勝手に読んでもいいです。ただ自分向けなので言い方が厳しいです。雑です。許してね。
ということで、ここから本題。
マラソンマッチに一番必要なのは「根気」である
自分の立場で言っていいのか怪しいですが、正直な事を言います。
マラソンマッチで必要なのは、「根気」です。「根性」です。これさえあれば、ある程度は闘えます。
０、まず最初にするべきこと
最初にするべきなのは、「正の点数の取れるプログラムを作成すること」です。
これをすることで、「とりあえず今自分はどういう問題を解いているのか」を確認することが出来ます。
出来れば、「全ての要素を使ったプログラムで正の点数を取る」ことをお勧めします。例えば、とりあえず"return 50"とか書いて点数が取れちゃう場合もありますが、適当に貪欲とかを使って、全ての要素を使って書くことをお勧めします。
１、そもそもどうやってスコアを伸ばすのか？
スコアを伸ばすために必要なのは、「前のプログラムより良いプログラムを作成する」ことです。
それには2つのパターンがあります。
- 前のプログラムを、少し書き足したり、変更したりして、良いプログラムに変更する。
- 前のプログラムを無視して、全く新しいプログラムを作る
さて、前者と後者ですが、たまには後者が必要なこともあります。しかし、基本的には前者だけで問題ありません。世界１位じゃないとやだ！Psyhoに勝ちたい！というのであれば別ですが、目標地点が自分程度（現在レーティング世界５位か６位？）で良ければ、変更だけで大丈夫です。
基本的には、前者の方が、圧倒的に必要なエネルギーが小さいです。後者は物凄いエネルギーが必要です。前者の改善をちょっとずつ、根気よく繰り返す。これこそが必勝法です。前者を繰り返すことのみを考えましょう！
もちろん、状況によっては、改善が３００行とかになる可能性もあります。でもその時ってプログラム自体が１０００行くらいになってるので、やっぱり最初から書くのよりは楽だよね！
２、人は、どうしてスコアを更新できなくなってしまうのか？
凄くシンプルに考えましょう。
山登り法というアルゴリズムがあります。マラソンマッチ必須テクニックと言われているアルゴリズムです。（僕は少しこの言われ方に危機感を感じていますが、それはまた別の話。）
山登り法っていうのは、こんな感じで、今いる場所が赤い丸だとしたときに、ランダムに適当に動かしてみて、評価を調べるアルゴリズムです。
こんな感じで良い感じに評価の高い場所を見つけたら、そこに移動する、という感じに、どんどん良い解を探していく、みたいなアルゴリズムです。
マラソンマッチにおける、アルゴリズムの改善、というのは、これに近いです。
「この部分を改良しよう！」と、プログラムを書き足す、書き換える行為が、この場合の矢印になります。そして、プログラムを提出してスコアを調べ、良くなってたら採用、悪くなってたらボツにします。まさに山登り法ですね？
もちろん、良くなるプログラムを組もうと思って組んでるわけなので、実際はこんなランダム遷移よりも良くなる可能性が高いです。ですが、よくならない場合もたびたびあります。よって、山登り法と大差ありません。
さて、ここで、山登り法で、凄く良い解に辿り着けないパターンを紹介しましょう。
まず１つ目、山を登りきれなかったパターンです。
すぐ近くに山の頂上があるのに、そこに辿り着けなかったパターン。
このパターンには、２種類の原因があります。
- 矢印を出す（プログラムを書く）本数が足りなかった
- 有効な向きに矢印が出せなかった
１つ目は、「こう改善しよう！」というのを試しきれなかったパターンです。根性が足りないですね。
コンテストが終わったら、「もうやりたいことはやり終わった」と言えるレベルでないと、コンテストに参加したとは言えません。ここで躓いている人は論外です。
２つ目は、上の図を見てもピンとこないかもしれませんが、十分に起こり得ます。さっきの図であれば、適当に矢印をぽんぽん作りまくれば良いですが、この場合の矢印というのはプログラムの改善案なので、そんな出せるものでもないし、適当に作れるものでもありません。
ってことで、ここが肝です。一番大切です。ここについては次の項で話します。
さて、その話をする前に、山登りで上手くいかないもう１つのパターンを紹介します。
はい、こんなパターンです。山登りで改善していった時に、右の様な小さな山を登り切ってしまい、左の大きな山に辿り着けない、ということが、一般的な山登り法においてはありえます。
ですが、基本的に、マラソンマッチについて、このパターンはないと思って大丈夫です。もちろん、「大きな変更」を加えることはありますが、「今の方針を捨てないといけない」というパターンは基本的にないと思って良いです。余計な事を考えてる暇があったら色々試しましょう。
ちなみに、「大きな変更」には、貪欲法を使っているのをビームサーチにする、とか、ビームサーチっぽくしてたけど評価関数を流用して焼きなましっぽく書く、とか、そういうのもあります。ゆるふわ視点が大切です。今回は関係ないけどさ、これないとマラソンマッチは死ぬし、これがマラソンマッチで一番技術的に大切なことだと思うんだけど、みんな型にはめるの大好きだから、やれビームサーチだの、やれ焼きなましだの言うんだよね。そんなん最初覚えないでいいっつーの。最適化に必要なのは、「出来たものをちょっとだけ変える」とか、「出来るだけ小さい単位で構成していく」とかで、そこの一つの実装方法としてビームサーチやら焼きなましがあるだけなんだから、それに固執させるのは絶対良くないと思うんだよね。まぁそれで強い人が出てきちゃってるからきっとそれでもいいんだよね。うん。なんか気に食わないけど。
３、どのようにスコアを伸ばせば良いか？
さて、大切な要素です。
偉い人は言いました。「適当に思いついたものを実装していくだけでは、良い成果は出せない。きちんと問題を分析して正しいものを組まなければならない。」と。ぶっちゃけそんなことはありません。つーかそれだけやってても勝てません。
いや、なんつーか、確かに、プログラムを組む前に、問題の分析ってある程度しないといけないんですよ。今年のCODE RUNNERのFinalや、ICFPC2013みたいに、「総プレイ時間内でのアクション回数に限りがある」という状態では、「とりあえずプログラムを組んでみる」って絶対にしてはいけない行動なんだけど、そうじゃない限りは、プログラムを組むってのはすっげー重要なんですよ。
だって、所詮人間の頭なんて限界があるわけで、頭の中で考えてたらこうだったけど、実際プログラムを動かして結果を見てみたら、そんなことはなくてこんな感じだったー、ってなるから、「最初３日間くらいは考えるだけに留める」とかは、大体ロクなことにならない、というのが個人的な印象です。それで良いスコアを出せるのは一部の変態だけです。
ってことで、なんか思いついてたらとにかく手を動かせ。そうしないと何も始まらない。
ここで大切な事が出ました。「とりあえず動かすことで見えてくるものがある」と言いました。
これって、ただ動かすだけで見えるものでしょうか？いいえ、見えません。無理です。スコアの上下だけ見て新しい事をひらめくのはただのエスパーです。
ってことで、実行結果を分析しないといけないんですね。幸い、TopCoderはビジュアライザがついてる問題が多いです。これをじっくり眺めているだけで、気づけるものはむっちゃ多いです。
ただまぁ、それだけだと足りない場合が多いです。「最終結果」じゃなくて「途中経過」が欲しいことも多いですし、途中経過って言うのはTopCoderのビジュアライザには渡されていないことも多いです。ターン制のゲームなんかは途中経過が見えますが、そうじゃないゲームも多いのです。
例えば、最近流行りのビームサーチを例にしましょう。「ビームサーチで200ターンのゲームをする、幅は10000」とかあったとするじゃないですか。これ、「100ターン時点で、50ターン時点の親となるノードは何種類残ってるか」とか、多分みんな調べてないじゃないですか。
そういうの調べれば、「途中でどれくらい偏ってるか」とか、「どれくらい同じノードの情報で埋め尽くされちゃってるか」とかわかるじゃないですか。それをやれば、例えばchokudaiサーチに切り替えたら良さそうとか、もっと別の変則ビームサーチだったり、微妙に焼きなまし混ぜたりとか、色んなバリエーション試せるじゃないですか。
こんなんビジュアライズするまでもなく、ちょっとコード書いてデバッガで見るなりprintfで出力してみるなりすれば、すぐに解ります。でもみんな調べてないわけですよ。こういう、「とりあえず今どう動いているか調べてみよう」みたいな気概が大切なんです。ぶっちゃけ、こういうの１個１個やっていくの、超めんどくさいです。めんどくさいけど、「こうなってるといいな」って予想して、「こうなってない」みたいな状態を見つけることこそが、プログラムの改善に繋がるわけですよ。そこら辺手抜いちゃいけない。手抜いちゃいけないけど超根性いる。でも頑張らないとだめ。
なんというか、やるべきことがすっごい多い。最初の「1000行も書かないといけないよう」なんて序の口で、スコアが止まってからが本番。スコアが止まったら、「じゃあなんで自分のプログラムは１位じゃないのか」「なんでこのプログラムはこの程度のスコアしか出せないのか」ってちょっと突き放してみて、徹底的に「ここがおかしい」「ここがだめ」ってのを洗い出す。この作業の根性こそが、マラソンマッチの本質だと思うわけですよ。
研究とかの根性とは結構違うのかな。研究は大きい所、根本的なところを改善していくのに対して、マラソンマッチっていうのは、もっとなんかこういう地味なところをひたすら見ていって、地味なヒューリスティックを加えて改善してく。こんなん論文になんてなるわけないんだけど、スコアの差、性能の差に表れるってのは、自分の今までの結果見て貰えばわかるよね。まぁその根性がなかったから今年負けたわけだし。
ちなみに、「スコアの上下」だけでもかなり良いデータが得られます。
まず、スコアが期待通り上がった場合。良かったですね。あなたの仮説が正しいことが示されました。終わり。こっちはどうでもいいです。
んじゃ、スコアが上がらなかった場合。こっちはどうでしょう。さっきの例だと、「スコアが上がらなかったら捨てる」と言いました。まぁこれだと勝てません。
プログラムを組むときは、「これなら上がるかな？」って思って組むはずです。「これやっても意味ないんだろうなー」と思って組むのは結構アホです。（もやもやするときは組んでもいいんだけど）
ってことは、「これを実装してスコアが上がると思った理由」ってのがそれなりにあるはずです。それであれば、「自分はこう思っていたのに、そうならなかった」って発見がこの時点であるわけですね。もうこの時点で十分な収穫なんですよ。
じゃあ何か、っていうと、２パターンがあるわけです。
- 「こう思っていた」自体が嘘だった。それが悪い要素だったり、反対向きだったりした。
- 「こう思っていた」は正しかったのだけど、それよりもっと大きい「こうなってはいけない」要素が存在した。
まぁ前者の時は、「これは嘘だったから、意識しないで良い」って思えるし、運が良ければパラメータ反転させるだけでスコア上がったりします。こっちはそんなに嬉しくない。
後者の場合は凄い嬉しい。スコアに直接影響を与える要素ってのは見つかると嬉しい。ここを今度は改善すれば良い。
ってことで、なんかダメでも調べるものってたくさんあるんですよ。だったら、徹底的に調べないとダメなんですよ。これはもう、実行結果眺めたり、実行途中の様子眺めたり、とりあえず色々吐かせてみたり、ビジュアライズしてみたり、もう根性ですよ。良くなると思ったのに悪かったらなんか悪い事やったんだから、それを探す。探すのにまぁ有効な手法はビジュアライズとかデバッガ使うとか色々あるし、そこら辺の技術は多分他の人が書いてくれるけど、基本は「めんどくさがらずにしっかりやる」って根性です。ここさえあればスコアを上げ続けられるわけです。
手法だけ覚えてもしゃーないんです。とにかく自分で生のデータを見る。生のデータが良くわからんなら、どうやって可視化するか考える。別に「可視化」「ビジュアライズ」って、絵として表示しろって意味じゃないんですよ。普段プログラム動かしてて見えてない部分とか、そういうのを何らかの形で見えるようにしろって話なんですよ。すっげー泥臭い部分なわけですよ。
もちろんプログラムだけじゃなくって、根本的なやり方があかんと思ったら、そもそもどうやるのが良いのかとかを、手で動かして実験するプログラム作ってみるのも良いし、構成するようなゲームだったら、サイズ合わせて印刷して手でやってみても良い。そういうことしないと何にも始まらないよね。
まとめ
ぶっちゃけ、マラソンマッチって、凄く泥臭いものだと思ってます。研究的な価値もあんまりないです。
でも、自分の書いたプログラムの性能は誇れるし、概略を話したら単純なアルゴリズムでも、他の人には早々作れないものになっている自信はあります。
まぁ、根性だけで勝てるもんでもないです。Algorithm部門でイエローくらいはないと、自分と戦うのは難しいと思います。でも、根性で結構どうにかなるのもマラソンマッチです。
知識的に得られるものも少ないです。「○○法が使えるようになったぞ！」みたいな、そういう喜びを得たい人は、多分Algorithm部門の方が向いてると思います。
ただまぁ、実力がつかないわけじゃないです。「良いやり方」だけ覚えるスマートな学習法もあるけど、「何をやってみたらダメだった」「何をやってみたらよかった」っていう、色んな泥臭い手法を自分で試して、自分で使いこなせるようになる、っていうのが、マラソンマッチだと思うし、これって本当に色んなジャンルで使えるものだと思います。
まぁ、長くやってるとセンス的なものもつくけどね。「こうしないと絶対ダメ」「これは絶対やっちゃダメ」みたいなの。これつくとスタートダッシュ出来てかっこいい。おすすめ。
まぁ、そんなものでも良かったら、ぜひぜひ参加してみてくださいな。楽しさは保証しますし、色んな実力もつけれるんじゃないかな、と思います。
あー、かきたいこと久々に書いた。終わりです！他の記事は多分ちゃんとした具体的な手法とか書かれているはずなので、ぜひぜひ見て言ってくださいな！
