競技プログラミングを終わらせる人々への指摘、頑張っている人々へのアドバイス

はじめに

競技プログラミングに関連する、以下の記事が話題にあがりました。

nuc氏1つ目の記事
nuc.hatenadiary.org

chokudai氏の記事
chokudai.hatenablog.com

nuc氏2つ目の記事
nuc.hatenadiary.org

nuc氏は、元Googleのエンジニアで面接も担当されていました。現在は某医大の特別特命准教授の方で、2007年頃に東大で競技プログラミングをされていた方のようです(氏名も役職も上記の記事のリンク先で公表されています)。nuc氏の記事は、競技プログラミングに対して「我々の目的の一つは、我々が始めてしまった競技プログラミングを我々が終わらせることです。」といった強い主張が多く、これらの記事の反応をみたのですが、

  • 競技プログラミングをしている方々が、nuc氏の主張で不安になり、特に若い世代で、競技プログラミングをやめようとしているケース
  • 競技プログラミングを知らない方々で、nuc氏の主張を鵜呑みにして、 競技プログラミングを誤解しているケース

等を見かけました。そういうわけで、なんらかのフォローをしたほうが良いと思い、この記事を書きました。

フォローの内容は以下のようになっています。

  • 第1章 競技プログラミングは変質したのか?
  • 第2章 競技プログラミングは変質して、悪影響を与えたのか?
  • 第3章 競技プログラミングをがんばっている皆さんへのアドバイス

付録以下の内容は今回のフォローとは関係ないのですが、一連の記事の読者の中で混乱していた方も見受けられたので、その辺を整理したものです。ほとんどの方は興味ない内容だと思うので、飛ばされても結構です。

  • 付録1章 nuc氏の議論方法の問題点
  • 付録2章 nuc氏のグループは、競技プログラミングを生み出したのか?
  • 付録3章 残る疑問

ちなみにnuc氏の記事の内容に全て反対しているというわけではありません。

  • 「競技プログラミングだけやっていても、Googleの入社面接の対策は不十分」という主張。これは、chokudai氏・nuc氏、元記事のリンク先で登場したLillian氏、全員同じです。
  • おすすめの本

のあたりは正しいと思っております。

第1章 競技プログラミングは変質したのか?

nuc氏は記事の中でこのように述べています。

我々の目的の一つは、我々が始めてしまった競技プログラミングを我々が終わらせることです。

競技プログラミングは変質し、その悪影響は看過できない所まで来てしまったと思います。競技プログラミングを始めた人たちができていたことが、その少し下の世代ではみるみるできなくなっていったと思われます。少なくとも、競技プログラミングの関係者がここまで Google に通らないことはありませんでした。

そして、2007年に競技プログラミングの名前が付きます。つまり「競技プログラミング」が広まり変質したというのは AtCoder ができる2012年より前の話をしています。

「悪影響は看過できない」は断定まではしていませんが結構強めの主張だと思います。でも、そもそも悪影響を与えるような変質があったのでしょうか。これを見ていきたいと思います。

短期コンテスト

まず、昔の競技プログラミングのほうが必要な能力が鍛えられていた例がいろいろあげられていましたが、トピックごとに検討してみました。

1・打ち込むのが大変なアルゴリズムも出題されていてた。(減った)

実装量が多いがアルゴリズムがほぼ不要な問題、通称「実装やるだけ問題」については、これは確かに現代のほうが減ったと思います。

2・バックスラッシュ(変化なし)

これは昔も今も短期コンテストでほぼ出題されていないと思います。例外的に、TopCoder・Codeforces等で、2次元のフィールドの左斜め方向を表すために使わていることありました。念のため2000年以降のICPC World Finalの問題をチェックしましたがバックスラッシュを入出力に使うケースはありませんでした。

3・言語の選択(重要になった)

昔は短期コンテストで使用できる言語は数個でしたが、現在では使用できる言語が圧倒的に増えていますし、むしろ現在の競技プログラミングのほうで重要です。文字列処理が簡単にできる言語、多倍長処理が簡単にできる言語などを適切に選べば有利になります。

4・定数倍高速化(とんとん)

昔のほうがオーダーがきっちりしておらず定数倍高速化が有効だったケースが多かったというのは同意です。しかし、逆に現在は言語が増えたことで、スクリプト言語のように実行時間が遅い言語で定数倍高速化が有効なケースもでてきたので、一長一短です。また、言語が増えたことで、すべての言語でオーダーがきっちりした問題が作るのは不可能なゆえに速い言語での定数倍高速化が有効なケースもあります。ちなみに、nuc氏は「プログラミング言語の選択は影響がないように作られています。このために、1000倍くらいの定数倍は無視します」と述べていますが、そのような問題はほとんどありません。

5・クイックソートのようなライブラリーが提供するアルゴリズムについての詳細(変化なし)

ライブラリの内容が分かっていることを要求されるアルゴリズム問題はでたまに問われますが今も昔も多くはありません。例えば、クイックソートでいえば、アンチクイックソート(クイックソートキラー)の問題については、今も特にCodeforcesで含まれています。

6・出題者の気持ちを読む能力(変化なし)

必要でしょうか?これが「制約などから逆算して、適応可能なアルゴリズムを考える」という意味なのであれば、むしろ実用的な能力です。私はこちらこちらに同意見です。出題量の意味でも変化はありません。

nuc氏は述べていないのですが、変化があるとすれば枝刈りです。

7. 枝刈り(減った)

計算量が不定な場合が多く、ICPC以外ではほとんど出題されなくなったかもしれません。

以上は問題そのものの変化についてです。

またnuc氏は、

面白くするために作られたルールだと分かっている人たちがいなくなり、そのルールとそれによる序列が絶対的なものになってしまったということです

と述べていますが、これは違います。レーティングがつかない自由な形式の短期コンテストは、現在のほうが明らかに増えてます。代表的なものとしてyukicoderががあります。
yukicoder.me
「競技プログラミングは、出題することもとてもアルゴリズムの勉強になります。完璧に出題できなくても、気軽にお互い指摘しあって向上していこうという方針で行っております。」という思想により、出題形式がかなり自由で、また「ゆるふわポイント」のように競技力以外の貢献度の指標もあります。これは明らかに「ルールとそれによる序列が絶対的なもの」と真逆です。参加者数も7000人以上います。

また、出題形式がとても自由な各種有志コンテスト(Xmas Contest 2020 - AtCoderお誕生日コンテスト - AtCoder)も増えました。これらは、競争用としては微妙ですが、プログラミングとしてはいろいろと勉強になります。例えば、入力が「1+2=?」となぜか画像で渡される問題がありましたが、短時間で画像解析をどうやるかを考えることができ、明らかにプログラミングの勉強にはなります。

ちなみに、短期コンテストそのもので良くなった点については元記事で触れられてはいないわけですが、AtCoderを初めてとした参加しやすいコンテストが増え参加への敷居が下がったため全体のレベルは上がり、さらにいろいろなアルゴリズムについて問われるようになりました。深みは増しています。

長期コンテスト・最適化コンテスト

長期コンテストや最適化のコンテストは、短期コンテストの例で述べた1~7の全てのスキルはもちろん、使用言語や計算資源も自由なことが多く、プログラミングのより幅広い知識スキルが必要になっています。そもそも実務の問題をアウトソーシングしている形のものすらあります。

各競技プログラミングサイトによって何を重視するかは違いますが、そういうコンテストは増え続けています。

SuperComputing Contest 1995~ スーパーコンピューターを使った高校生向けコンテスト
ICFPC 1998~ 自由な形式の3日間チーム戦コンテスト
TopCoder Marathon Match 2006~ 最適化・高速化・1人ゲームAI・機械学習など。NASA主催など、実務と直結するものも多い
CodinGame 2012~ ゲームっぽさ抜群の対戦型ゲームAIコンテスト
Google Hash Code 2014~ データが非常に大きい最適化コンテスト
Halite AI Programming Challenge 2017~ 15000人以上が参加したこともある対戦型ゲームAIコンテスト
AtCoder 2017~ 最適化・1人ゲームAI・ウェザーニュース社のデータ圧縮、日立・北大と量子コンピューター設計

nuc氏が記事内で、昔は良かった例として、問題が途中で変わった最適化コンテストの話を上げていますが

昔は、面白くないコンテストというのがたくさんあったのです。たとえば、線形時間アルゴリズムの最適化のコンテストで、締め切り後にフロッピーディスク内のファイルで計算が行われることが発表され、フロッピーディスクから大きなファイルを読み込むため、非同期処理をして読込み中に計算をした人が2位にダブルスコアで勝つというコンテストがありました。騙された感じはあります。ただ、本当に勉強になりました。

これについてはICFPCが代表格で、良くも悪くも現在までこういった出題傾向は続いています。

また、似たようなタイプの(面白くないコンテストかどうかは人によりますが)よりさまざまなスキルが要求されるコンテストは増え続けいています。

Google Hash Codeに至っては、30000人以上の参加者がおり、世界最大級の競技プログラミングコンテストとなっています。また、いまだに、大学や学会が独自主催の小さめのコンペティションというのも結構あります(例:http://www.jpnsec.org/files/competition2019/EC-Symposium-2019-Competition-English.html

まとめると、競技プログラミングは短期コンテストで傾向が少し変わったものの、全体としては大きく幅が広がったいえます。

第2章 競技プログラミングは変質して、悪影響を与えたのか?

最初に、「競技プログラミングは、面接のために作られたわけではないので、どう変質しようが競技プログラミング側には一切責任はない。」という部分は最初にはっきりさせておきます。

同じような仮説は各所で述べられていますが紹介します。(念のため、悪影響を与えたかどうかの立証責任は私にないです。)
f:id:shindannin:20210408125022p:plain

昔は競技プログラミングは、情報系の強い人や極めて頭の良い層しか知らなかった、そういう人達しか競技プログラミングをやれないほど敷居が高かった。アルゴリズムの勉強をちょっとすれば面接合格レベルに到達できた。
(以下の例だと、競プロをしていてアルゴリズムの能力だけであればGoogle面接合格レベルの人で、最終的に面接合格したのは、4人中3人で75%です)
f:id:shindannin:20210408125254p:plain

今は競技プログラミングが幅広い層に普及した。アルゴリズムの能力だけであればGoogle面接に通るレベルに到達できる人も増えたが、全体として面接合格レベルに到達できる割合が少なくなった。
(以下の例だと、競プロをしていてアルゴリズムの能力だけであればGoogle面接合格レベルの人で、最終的に面接合格したのは、9人中4人で44%です。割合は減っています。)
f:id:shindannin:20210408125309p:plain

といった現象が起きているだけだと予想します。アルゴリズム能力が上がること自体に悪影響はないでしょう。

第3章 競技プログラミングをがんばっている皆さんへのアドバイス

自分にとって、競技プログラミングは人生に欠かせぬものです。

  • 本職はゲームプログラマーなのですが、競技プログラミングで得た能力は仕事に大きく役立っています。むしろ、仕事で役立たない分野が見当たらないくらいです。
  • 競技プログラミングそのものが楽しいので、人生の豊かさアップにもなっています。
  • 競技プログラミングを通じて、世代や業界を越えて、いろんな人と知り合うことができました。これも素晴らしいことです。

ただ、自分の例を挙げても、世代も環境も違いますしピンとこないと思うので、いろいろなテーマについて考えてみました。ここで書いていることの多くは、競技プログラミングに限らず成り立つことだと思っています。

なにかに熱中しているってこと自体が、素晴らしい。

  • 何かが好きで熱中してがんばっているってことは、ベストな行動だと思います。一般的には高校生以下なら制約も少ないと思うので、迷わず熱中しましょう。
  • 仮に、他の方に「あまり好きでない他の事のほうが役に立つよ!」と言われたとしてそれをやるとして、同じように頑張れるでしょうか?結局ダラダラやってしまうことになると思うので、好きなことに熱中したほうがいいです。
  • 将来、自分の好きな事が他の事に変わったとしても、1つのことに熱中でき頑張れることが素晴らしいスキルなので、その経験自体が応用できます。
  • ちなみに、競技プログラミングの強さは全く関係ないです。自己ベストを出すために、ベストな行動をすること自体が大事です

競技プログラミングは役に立つ論

  • こういうのは価値判断の論題と言われていて、それぞれの人がどの価値に重きを置くかによって違ってくるので、決着がつかない論題と言われています(他の例:「男と女ではどちらが幸せか?」だったら、何をもって幸せとするかはなんとでも定義できるので議論に決着がつかない)
  • 「競技プログラミングは役に立つ」をシェアするのは、他の方の参考になるので良いことですが、他の方に押し付ける必要はないと思います。
  • もし、わざわざ山を越えて、他の方が「競技プログラミングなんて役に立たないよ。むしろ悪影響だよ。」と言って来たら、それは「お前の中ではな…」と思って相手にしないほうがいいと思います。

競技プログラミングを仕事に役立たせたい人が仕事に役立たせるためのコツ

  • 応用できないかを日ごろから考えようとすることは大事だと思います。普段の問題を解いているときでも、仕事をしているときでもいいので、応用できないか考えてみましょう。
  • 競技プログラミングで学べるスキル「最適化(=最小値を求める・最大値を求める)」は、平たくいうと、短期コンテストなら「一番良いのを探す」、長期コンテストなら「できるだけ良くする」という意味で、とても応用がききます。
  • 長期コンテストであれば、仕事を外注しただけの問題がたくさんあります。どういう風に世の中で使われているのかはヒントになると思います。

競技プログラミングがおもしろすぎて、仕事を含む他の事に興味が持てない。

  • 気持ちはとても分かりますが、上と下が参考になれば。

人生の目標が決まっていると、競技プログラミングをやる上でも迷わない。

人生の目標が決まってると優先度も決めやすいので、例えば社会人になっても優先度から時間を割り当てて競プロをするといったことができます。他の人の価値観押しつけにも惑わずに済みます。ただ人生の目標を立てるのは簡単ではありません。人によっては小中学生のころから崇高な目標を持ってる人もいるので焦りますが、ヒントを書いてみたいと思います。

  • 崇高な目標を立てる必要はありません。まずは初期解をつくりましょう「毎日5時間競プロして、5時間ゲームして、お風呂とご飯が2時間ぐらいで、12時間ぐらい寝たい。あとはモテモテの生活で一生を終える。」ぐらいの目標でいいと思います。欲望のままに立てるのがいいと思います。
  • 現実には、お金の制約・能力の制約・時間の制約・家族の制約・身体的制約などで、現状から目標達成までに大きなギャップができると思います。この例だとお金が1億円ぐらい必要な気がします。
  • そのギャップを埋めるに当たって妥協するのも途中の目標としては悪くないと思いますが、組み合わせを考えてみると妥協量を減らせるケースがあります。例えば、「5時間競プロして、5時間ゲーム」を組みあわせて、「ゲームAIを作る仕事を8時間する。残り2時間を競プロとゲーム」という風にすると、競プロ欲とゲーム欲もある程度も満たせる上にお金も入ってくるので、より現実的になり、最終目標にも近づけます。
  • また、目標を改善したい場合は、「仮に目標が全部達成できたとして、それで人生本当に満足か?」を考えると良いと思います。「毎日5時間ゲームするのも楽しいけど、せっかくならもっと時間を増やしてプロゲーマー目指すか!」みたいに考えられるといいです。
  • 子供の頃に好きだったは、その人の本能的な欲求だと思うので、人生の目標ヒントはあるかもしれません。

Googleに入社したい方へ

なんでも1次情報が大事です。競技プログラミング勢で現役でGoogleで働いている方はかなりいるので、相談するのであればそういう方々に相談する方が良いと思います。また、YouTube上にGoogle自身が就職のためのいろいろな情報を載せています。
www.youtube.com
www.youtube.com

nuc氏の記事によると性格はあまり関係ないとのことでしたが、現役Googleのエンジニアの方の情報によると、最近は技術以外なものも求められるとのことでした。
careersonair.withgoogle.com (要登録)Googleyness & Leadership で検索してもいろいろと出てきます。謙虚さやリスペクトも大事みたいです。


以上、ここまでが競プロに関していいたいことでした。ここから先は読み飛ばしても構いません。

付録1章 nuc氏の議論方法の問題点

[1] 自分の主張を読み取れないのは相手の責任にする。

nuc氏の1つ目の記事での主張です。

[A] 競技プログラミングは、東京大学競技プログラミング同好会2007年春台湾合宿から始まります。それまで、プログラミングコンテストは開催されてきましたが、競技プログラミングの名前が使われたのはこの合宿がはじめてで、このとき一つのジャンルが生み出されたのです。

[B] 我々の目的の一つは、我々が始めてしまった競技プログラミングを我々が終わらせることです。

どちらも断定しています。[A][B]を信用して正しいものとし解釈すると、nuc氏の主張は

「競技プログラミングという一つのジャンルを生み出したのは我々(=nuc氏を含めた合宿参加者)であり、我々の目的の一つは、競技プログラミングを終わらせること。」

となります。ジャンルを生み出した人がそれを終わらせると言ったら、ジャンルを丸ごと終わらせるという風に解釈するのが自然です。しかし、nuc氏の2つ目の記事によると、実際の意味は、

で、この「競技プログラミングを終わらせなければ」における「競技プログラミング」というのは、もともとは、今回の模擬面接をした3人の周りの人たちの間では、競技プログラミング同好会・クラブやその周辺の活動を指すわけです。そりゃそうじゃないですか、「競技プログラミングをする」という表現は当時はなくて、「プログラミングコンテストに出る」と言っていたわけです。だから、競技プログラミングといえば、自分たちが大学生の頃の集まりを指すわけです。「学生時代のバンドを終わらせなければ」と置き換えたら意味が通じるでしょうか。つまり、自分たちの大学生・大学院生の頃を反省して、とても大事なことをやり忘れてきたのでやり終わらなければいけない、ということです。

「そりゃそうじゃないですか」と理解できるのが当然のごとく言っていますが、2012年以前に活動は終わっているわけですし、終わらせる対象が「当時の競技プログラミング同好会・クラブやその周辺の活動」と限定的だというのは、思いこみをなしにそう確定することはできません。

[2] 相手の主張は自分の思いこみでより悪く解釈する。

chokudai氏は記事で、[C]と[D]を主張しています。

[C] 「競技プログラミングをしている」と言ったら、非常にありがたいことに、殆どの人がAtCoderに取り組んでいると思います。日本における「競技プログラミング」は、「AtCoder」と言い換えても、さほど問題がないかと思います。

[D] 昔の競技プログラミングがどんなものだったか知りませんが(とはいえ、記事で書かれていた2007年に僕は競技プログラミングにすでに行っていましたが)、今の日本の競技プログラミングの主流であるAtCoderは、このようなものになっています。

[C]についても断定まではしてません。[D]では今の日本の競技プログラミングということで、昔の競技プログラミングと明確に区別しています。

AtCoderは競技プログラミングに含まれる(競技プログラミングの一部である)ことは明らかで、[C]で言い換えても問題ないというのは
「競技プログラミングが終わる」ならば「AtCoderが終わる」
のようなケースのことを指しているのかなと解釈しました。これは真です。

これに対してnuc氏は2つ目の記事で以下のように解釈しました。

別に「競技プログラミング」という単語を商標登録していたわけでもないですから、その後、誰が使うのも自由です。ただ、さすがに、個人の代名詞や会社の代名詞のようになっていると思っている人がいることには私は気が付かなかったわけです。

「ちょくだい」は、東京大学「ちょくだい」同好会2007年春台湾合宿から始まります。
「ちょくだい」は変質し、その悪影響は看過できない所まで来てしまったと思います。
我々の目的の一つは、我々が始めてしまった「ちょくだい」を我々が終わらせることです。
「AtCoder」は、東京大学「AtCoder」同好会2007年春台湾合宿から始まります。
「AtCoder」は変質し、その悪影響は看過できない所まで来てしまったと思います。
我々の目的の一つは、我々が始めてしまった「AtCoder」を我々が終わらせることです。

これはchokudaiさんの主張に全く沿っていません。まず[D]で昔の競技プログラミングと明確に区別はしているのに、nuc氏は昔の競技プログラミングをAtCoderと置き換えてしまっています。これらの文は一目みたら意味がわからず、読者でこう解釈した人はほぼいないと思われます。特に、昔の「競技プログラミング」を「ちょくだい」と置き換えるのについては、そのような主張はなく、全く意味が分かりません。

そりゃそういう風にいわれたら怒ります。ごめんなさい。だけど、破産させる気も抹殺する気もありませんでした。というよりも、こう読まれるのにあらかじめ気がつけというのは、正直無理です。

正直無理とは言っていますが、それはnuc氏が勝手に「昔の競技プログラミング」を「ちょくだい」に置き換えたために起こった自作自演なのに、相手の責任にしています。さすがにこれはnuc氏に悪意があると思われて致し方ありません。

また[1][2]からダブルスタンダードであり、公平性がなく、説得力がないと思います。

[3] 分かりやすく書く気がない

chun さんに、このようなことをお伝えするのは本当にお耳汚しなのですが、散逸は意図的です。私の経験則で「誰にとっても新しい情報」のメッセージを広く伝えたいときには、「詳しい人は同意するが、そうでない人は違和感を感じる内容」を加えるんです。そうすると、人は、「新しい情報の真贋を、周囲の情報から判断しようとする」ので、一部の人に認知負荷がかけられます。こうすることで、根拠と結論が噛み合わない支離滅裂な発言も出てきて広まると認識しています。

バズるのには確かに成功しましたが、真摯でないと思います。自分だったら、一意に解釈できない記事を書いて誤解されたら、自分の責任だと思っていますが…。

またマウントを取るタイプの人が、このような手法をとると、書いた側が常勝してしまうので、基本相手にしないほうが良いと思います。

  • 違和感がある主張に対して、書いていないことを読みとらないようにしてると、「普通に考えてそんなわけない」
  • 違和感がある主張に対して、辻褄があるように書いていないこと仮定すると、「思いこみ。文章を読む訓練をしていない人にありがち」

[4] 不遜

[1][2]については、単に議論についてのスキル不足な場合でも起こりえます。人間は誰でも間違いがあると思うので、記事の主張に間違いがあったとしても、それは冷静に問題点を修正していけばよいだけだと思います。
しかしnuc氏の記事は謝っている内容にはなっていないし、相手を悪く解釈して、嫌味っぽい言い方が多くあり、この記事を読んでnuc氏が心から謝っていると解釈する人はほぼいないと思います。(chokudai氏はもう関わりたくないので大人の対応をしているだけかと思います)

ちょくだいさん、ごめんなさい。(ちょくだいさんが中高の後輩で、中学校一年生や中学校二年生の頃の印象からアップデートされていないことも行き違いの原因かと思いますので、この書き方にいたします。)

本文が謝っている態度にもみえないですし、大人に対して、中学校一年生や中学校二年生かのように話かけている時点で相手を馬鹿にしていると思いますが…。とても失礼だと私は思いました。

さらに、

ここで残念なお知らせがあります。とある医学部教授から「読んだよー。文章はいいけど、お前が卒業生をひょいひょい適当にエンジニアにすると教授会で問題になることがあるから、するんだったら出来の悪いのにしてよね。いいね。ほんと頼むよ。特にそこにいる生徒会長みたいなのはだめだから。」ということなので、今後は、あらかじめ「出来が悪いかを問い合わせる」約束をしてきました。

「出来が悪いかを問い合わせる」、自分はこういうのに同意するような人には教わりたくはないです。この医学部教授も問題だと思いますが…。

こういうのを見ると、最初の記事のタイトル「Twitter で医師を拾ってきて Google のソフトウェアエンジニアにするだけの簡単なお仕事」の「拾ってくる」という表現ネタではなく、上から目線で本当に失礼なだけな人にも見えてきます。

その他

もし、どなたかがnuc氏は議論することになった場合は、最初に議論のマナーを守っていただけるように約束してからのほうがいいと思います。特に4. 注意点の部分
http://www.ritsumei.ac.jp/ir/ir-navi/common/pdf/technic/technic_text_09_2019.pdf

付録2章 nuc氏のグループは、競技プログラミングを生み出したのか?

nuc氏は競技プログラミングに対して責任感や使命感を感じているようなので、今回のような行動を起こしたともいえます。しかし、そもそも競技プログラミングを始めたのでしょうか?始めたのでなければ終わらせる必要もないので、なにもせず平和に終わっていたと思います。

  • まず本題の前に、nuc氏の指す「我々」が、競技プログラミング*1というージャンルを生み出したというのは、competitive programmingはすでに存在していたので間違いです。"competitive programming"の日本語訳を考えたということであれば合っています。「ージャンルを生み出した」は間違いというのは自明ではありますが、嘘を言っていることには違いないので反省はしてください。

自分の意見ですが、「nuc氏の指す『我々』が2007年に競技プログラミングという一つのジャンルが生み出した」のが、「nuc氏の指す『我々』が2007年以降の競技プログラミングに大きく影響を与えた」という比喩であったとしても疑問が残ります。それは以下の理由からです。

ただ、nuc氏の指す競技プログラミングを生み出し終わらせようとしているメンバーが曖昧なので、確定はできません。

付録3章 残る疑問

nuc氏の指す「競技プログラミングという一ジャンルを生み出した我々」「競技プログラミングを終わらせる我々」が、台湾合宿メンバー全員なのか、nuc氏+面接の講師役2人の計3名だけなのか、今だに分かりません。もし違うのであれば、当時の状況などを知る人を教えていただけると助かります。

また、

  • Q1. 競技プログラミングを始めたメンバーはだれか?
  • Q2. 競技プログラミングを終わらせようとしているメンバーはだれか?始めたメンバーと同じか?
  • Q3. 競技プログラミングを終わらせる活動に、競技プログラミングを始めたメンバーはどれぐらい賛同しているのか?
  • Q4. 競技プログラミングを終わらせる活動は、結局何をやることなのか?(「自分たちの大学生・大学院生の頃を反省して、とても大事なことをやり忘れてきたのでやり終わらなければいけない」とありますが…)

このあたりをはっきりさせないと、これ以上議論が進まなそうです。

2007年の東大の状況は分からないのですが、2008年からはUTPCというコンテストがあり、参加者や作問者が見れます。

私自身、このメンバーの半分ぐらいは知っていると思うのですが、終わらせようとしているのに賛同している人がどれぐらいいるのか疑問が残ります。

*1:ちなみに、「競技プログラミング」という訳語自体も、実はすぐには広まりませんでした。当時、ほとんど「プログラミングコンテスト」という呼び方をしていたと思います。Googleトレンドの検索結果。プログラミングコンテストだと主語が大きく、それこそ他のプログラミングの存在を無視している感がある、そのかわりに「競技プログラミング」という呼び名が使われるケースが増えたと予想しています。→追記:情報をいただきました競技プログラミングという言葉の誕生 - MAYAH

焼きなまし法のコツ Ver. 1.3

焼きなまし法そのものの解説は少しだけにして、焼きなまし法の使い方のコツをメインに書こうと思います。

焼きなまし法の概要

最適化(=最大値か最小値を求める)の手法の1つです。以下は擬似コードです。

あらかじめ、計算する時間を決める。
以下のスコープ内のコードを時間経過するまで繰り返す。
{
    適当に、次の状態(近傍)を選ぶ。
    (1) 次の状態のスコアが、今の状態のスコアより良くなった場合は、常に、状態を次の状態にする(遷移)。
    (2) 次の状態のスコアが、今の状態のスコアより悪くなった場合でも、ある確率で、状態を次の状態にする。
        確率は以下のように決める。
       (2.A) 序盤(経過時間が0に近いとき)ほど高確率で、終盤ほど低確率。
       (2.B) スコアが悪くなった量が大きければ大きいほど、低確率。
}
最後に、今までで一番スコアのよかった状態を選ぶ。

次の状態が悪くてもそれを選ぶ可能性がある(2)の部分が、焼きなまし法の最大の特徴です。

「状態」「スコア」というのがピンとこないかもしれませんが、

  • もし、巡回セールスマン問題であれば、
    • 状態 →ルート
    • 次の状態(近傍)→元のルートをちょっとだけかえてみたルート
    • スコア →総距離
  • もし、y=f(x)の最大値を求める問題であれば、
    • 状態 →x
    • 次の状態(近傍)→ x' = x + a (aは小さめの値)
    • スコア →y

といったかんじです。

サンプルソースコード

AtCoderのコンテストIntroduction to Heuristics Contest - AtCoderで、スケジューリング問題が出題されました。 この問題は焼きなまし法が効果的です。C++でのサンプルを2つ用意しました。変数名は問題に合わせています。

サンプル1

単純な焼きなまし法。1165人中400位相当の解法です。焼きなまし法の本質は、// 焼きなまし法(ここから)の部分です。
AtCoderの提出コード


ソースコードを開く

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cassert>
#include <climits>
#include <cmath>

using namespace std;
using namespace chrono;

// 0以上UINT_MAX(0xffffffff)以下の整数をとる乱数 xorshift https://ja.wikipedia.org/wiki/Xorshift
static uint32_t randXor()
{
    static uint32_t x = 123456789;
    static uint32_t y = 362436069;
    static uint32_t z = 521288629;
    static uint32_t w = 88675123;
    uint32_t t;

    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

// 0以上1未満の小数をとる乱数
static double rand01()
{
    return (randXor() + 0.5) * (1.0 / UINT_MAX);
}

const static int NUM_TYPES = 26; // コンテストの種類数

// 全体のスコア(今回の問題のスコア)
static int getFullScore(const int D, const vector <int>& C, const vector <int>& T, const vector<vector<int>>& S)
{
    int score = 0;

    vector <int> last(NUM_TYPES, 0);

    for (int d = 0; d < D; d++)
    {
        const int j = T[d];
        last[j] = d + 1;
        for (int t = 0; t < NUM_TYPES; t++)
        {
            score -= (d + 1 - last[t]) * C[t];
        }
        score += S[d][j];
    }

    return score;
}

int main()
{
    //  入力
    int D;
    cin >> D;
    vector<int> C(NUM_TYPES);
    for (int &c : C)
    {
        cin >> c;
    }

    vector<vector<int>> S(D, vector<int>(NUM_TYPES));
    for (auto &s : S)
        for (auto &x : s)
        {
            cin >> x;
        }

    // 初期解
    vector<int> T(D);   // T[d] d日目に開くコンテスト
    for (int d = 0; d < D; d++)
    {
        T[d] = d % NUM_TYPES;
    }

    // 焼きなまし法(ここから)
    auto startClock = system_clock::now();
    int score = getFullScore(D, C, T, S);   // 現在のスコア
    int bestScore = INT_MIN;                // 最高スコア
    vector <int> bestT;                     // 最高スコアを出したときのT

    const static double START_TEMP = 1500; // 開始時の温度
    const static double END_TEMP = 100; // 終了時の温度
    const static double END_TIME = 1.8; // 終了時間(秒)

    double time = 0.0;   // 経過時間(秒)
    do
    {
        const double progressRatio = time / END_TIME;   // 進捗。開始時が0.0、終了時が1.0
        const double temp = START_TEMP + (END_TEMP - START_TEMP) * progressRatio;

        // 近傍 : d日目のコンテストをtに変えてみる。d,tはランダムに選ぶ。
        const int d = randXor() % D;
        const int t = randXor() % NUM_TYPES;
        const int backupT = T[d];
        int deltaScore = 0; // スコアの差分 = 変更後のスコア - 変更前のスコア
        deltaScore -= getFullScore(D, C, T, S);
        T[d] = t;   // 変更
        deltaScore += getFullScore(D, C, T, S);
        const double probability = exp(deltaScore / temp); // 焼きなまし法の遷移確率

        if (probability > rand01())
        {
            // 変更を受け入れる。スコアを更新
            score += deltaScore;
            if (score > bestScore)
            {
                bestScore = score;
                bestT = T;
            }
        }
        else
        {
            // 変更を受け入れないので、元に戻す
            T[d] = backupT;
        }

        time = (duration_cast<microseconds>(system_clock::now() - startClock).count() * 1e-6);
    } while (time < END_TIME);
    // 焼きなまし法(ここまで)


    // 出力
    for (int t : bestT)
    {
        cout << t + 1 << endl;
    }
    cerr << "bestScore: " << max(0, bestScore + 1000000) << endl;

    return 0;
}


サンプル2

やや複雑ですが、かなり改善した焼きなまし法。1位相当の解法です。
AtCoderの提出コード


ソースコードを開く

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cassert>
#include <climits>
#include <cmath>

using namespace std;
using namespace chrono;

// 0以上UINT_MAX(0xffffffff)以下の整数をとる乱数 xorshift https://ja.wikipedia.org/wiki/Xorshift
static uint32_t randXor()
{
    static uint32_t x = 123456789;
    static uint32_t y = 362436069;
    static uint32_t z = 521288629;
    static uint32_t w = 88675123;
    uint32_t t;

    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

// 0以上1未満の小数をとる乱数
static double rand01()
{
    return (randXor() + 0.5) * (1.0 / UINT_MAX);
}

const static int NUM_TYPES = 26; // コンテストの種類数

// 全体のスコア(今回の問題のスコア)
static int getFullScore(const int D, const vector <int>& C, const vector <int>& T, const vector<vector<int>>& S)
{
    int score = 0;

    vector <int> last(NUM_TYPES, 0);

    for (int d = 0; d < D; d++)
    {
        const int j = T[d];
        last[j] = d + 1;
        for (int t = 0; t < NUM_TYPES; t++)
        {
            score -= (d + 1 - last[t]) * C[t];
        }
        score += S[d][j];
    }

    return score;
}

// d日目のコンテストT[d]を開いたときのスコア増分
static int getContestScore(const int d, const int D, const vector <int>& C, const vector <int>& T, const vector<vector<int>>& S)
{
    const int t = T[d];
    int score = S[d][t];

    int prev = d - 1;   // d日目以前に開かれる同じコンテストの日
    while (prev >= 0 && T[prev] != t)
    {
        prev--;
    }

    int next = d + 1;   // d日目以降に開かれる同じコンテストの日
    while (next < D && T[next] != t)
    {
        next++;
    }

    // sum(x) = x*(x+1)/2 つまり1,2...,xまでの等差数列の和とすると
    //	score -= sum(next - prev -1) * (-C[t]);                       // ... (1)
    //	score += sum(day  - prev -1) + sum(next - day  -1) * (-C[t]); // ... (2)

    // p---------n コンテストをおく前
    //  123456789 // ... (1)

    // p---d-----n コンテストをおいた後
    //  123 12345 // ... (2) 

    score += (next - d) * (d - prev) * C[t];    // (1)と(2)を計算すると、簡単になる。

    return score;
}

int main()
{
    auto startClock = system_clock::now();

    //  入力
    int D;
    cin >> D;
    vector<int> C(NUM_TYPES);
    for (int &c : C)
    {
        cin >> c;
    }

    vector<vector<int>> S(D, vector<int>(NUM_TYPES));
    for (auto &s : S)
        for (auto &x : s)
        {
            cin >> x;
        }

    vector<int> T(D);   // T[d] d日目に開くコンテスト
    for (int d = 0; d < D; d++)
    {
        T[d] = d % NUM_TYPES;
    }

    int score = getFullScore(D, C, T, S);   // 現在のスコア
    int bestScore = INT_MIN;                // 最高スコア
    vector <int> bestT;                     // 最高スコアを出したときのT

    const static double START_TEMP = 1500; // 開始時の温度
    const static double END_TEMP   =  100; // 終了時の温度
    const static double END_TIME   =  1.8; // 終了時間(秒)

    double temp = START_TEMP;   // 現在の温度

    long long steps;    // 試行回数
    for (steps = 0; ; steps++)
    {
        if (steps % 10000 == 0)
        {
            const double time = duration_cast<microseconds>(system_clock::now() - startClock).count() * 1e-6;   // 経過時間(秒)
            if (time >= END_TIME)
            {
                break;
            }

            const double progressRatio = time / END_TIME;   // 進捗。開始時が0.0、終了時が1.0
            temp = START_TEMP + (END_TEMP - START_TEMP) * progressRatio;
        }

        if (rand01() > 0.5)
        {
            // 近傍1 : d日目のコンテストをtに変えてみる
            const int d = randXor() % D;
            const int t = randXor() % NUM_TYPES;
            const int backupT = T[d];
            int deltaScore = 0;

            // 変更前のd日目のコンテストのスコアを引き、変更して、変更後のコンテストのスコアtを足す。
            deltaScore -= getContestScore(d, D, C, T, S);
            T[d] = t;
            deltaScore += getContestScore(d, D, C, T, S);
            const double probability = exp(deltaScore / temp); // 焼きなまし法の遷移確率

            if (probability > rand01())
            {
                // 変更を受け入れる。スコアを更新
                score += deltaScore;
                if (score > bestScore)
                {
                    bestScore = score;
                    bestT = T;
                }
            }
            else
            {
                // 変更を受け入れないので、元に戻す
                T[d] = backupT;
            }
        }
        else
        {
            // 近傍2 : d0日目のコンテストとd1日目コンテストを交換してみる
            const int diff = randXor() % 10 + 1;    // d0とd1は10日差まで
            const int d0 = randXor() % (D - diff);
            const int d1 = d0 + diff;

            int deltaScore = 0;

            // 変更前のd0日目とd1日目のコンテストのスコアを引き、変更後のd0日目とd1日目のコンテストのスコアを足す
            deltaScore -= getContestScore(d0, D, C, T, S);
            deltaScore -= getContestScore(d1, D, C, T, S);
            swap(T[d0], T[d1]);
            deltaScore += getContestScore(d0, D, C, T, S);
            deltaScore += getContestScore(d1, D, C, T, S);

            const double probability = exp(deltaScore / temp); // 焼きなまし法の遷移確率
            if (probability > rand01())
            {
                // 変更を受け入れる。スコアを更新
                score += deltaScore;
                if (score > bestScore)
                {
                    bestScore = score;
                    bestT = T;
                }
            }
            else
            {
                // 変更を受け入れないので、元に戻す
                swap(T[d0], T[d1]);
            }
        }
    }

    // 出力
    for (int t : bestT)
    {
        cout << t + 1 << endl;
    }
    cerr << "steps: " << steps << endl;
    cerr << "bestScore: " << max(0, bestScore + 1000000) << endl;

    return 0;
}

焼きなまし法のコツ

が多いほど、重要だと思っています。

1. 高速化

試行回数が多いほど、スコアが伸びる可能性があります。基本的にはボトルネックを調べて、そこを高速化しましょう。だいたい以下のところがボトルネックになるでしょう。

★★★★ プロファイルして、計算時間がかかっているボトルネックを探す

2021/03/06 追加しました。
焼きなまし法に限らず、マラソンマッチに限らず、プログラミング一般であらゆる高速化の前にやるべきことです。プロファイルの仕方はOSやツールにより違いますが、例えばVisual Studioなら「デバッグ」→「パフォーマンス プロファイラ」で、一発でできます。思わぬところがボトルネックになってることも多いので、絶対しましょう。
f:id:shindannin:20210306115133p:plain

★★★★ 高速化がどれだけ効果的か検討する。

重要です。ためしに10秒だけやってる計算を、あえて100秒とかに伸ばしてみて、結果がどうなるか見てみましょう。

  • 時間をかければかけるほどスコアが伸びる
    • 高速化しよう&スコアが素早く伸びるように次の状態を決めよう。山登り法に変えるのも良い。
  • 時間をかけてもスコアが伸びない & スコアが高い
    • 最適解がでてる可能性が高い。計算を打ち切って、余った時間を他に使う
  • 時間をかけてもスコアが伸びない & スコアが低い
    • 次の状態の決め方、スコア関数の見直しを再検討する。焼きなまし法を使わない法がよいときもあるのも忘れずに

こういった実験は自分のPCで行うわけなので、並列化などを行い計算リソースも存分に使ってよいです。

★★★★ 変更がある変数だけを保存して、戻す

先ほどのコードだと、

        const int backupT = T[d];

        // (略)    

        {
            // 変更を受け入れないので、元に戻す
            T[d] = backupT;
        }

の部分です。変更した、T[d]の部分だけをバックアップしておけば、元に戻せます。T全体を保存する必要はありません。

★★ 逆の手で、戻す

逆の手をやれば、前の状態に高速に戻せるのであれば、そうしましょう。例えば、上下左右に駒をうごかせるというパズル問題であれば、左に動かした後であれば、右に動かせば、戻せます。また、2つをswapするといった場合は、もう1回swapすれば戻せます。

★★★★ スコア関数の高速化

スコア関数の求め方は問題によって大きく異なるので、計算時間も異なってきます。ボトルネックになってたら高速化しましょう。
また、スコア関数の正確さを犠牲にしてでも、高速化したほうが良い場合もあります。1つのコツとして覚えて置きましょう。

★★★★ スコア差分計算時の打ち切り

2021/03/06 追加しました。
スコア差分計算の途中で、差分がすでに大きくマイナスになっていて、もうその後計算し続けていても絶対に遷移の受理確率がほぼ0っぽいのであれば、差分計算を打ち切って高速化することができます。焼きなまし法は遷移が成功するケースより遷移が失敗するケースが多く、失敗するケースをさっさと打ち切ることができれば高速化につながることが多いです。
また問題によっては、スコア差分の上界・下界が分かるケースもあり、これらが短時間で求められるのであれば、それもスコア差分計算の打ち切りに使用可能です。例えば、Google Hash Code 2021の練習問題では、10000ビットのORを取り、(ビットが1の数)の2乗がスコアになる問題がありました。10000ビットのORはそれなりに時間がかかりますが、

(ほんとは10000ビットある)

111001010100117個)
001100010100014個)  
↓ OR
111101010100119個。つまり81点)  

と実際にORをとらずとも、

111001010100117個)
001100010100014個)  
↓ OR
???????????????    (1が最小で7個、最大で11個、つまり49点~121点のあいだ)  

というのが分かれば、打ち切り時の計算の参考になります。

★★★ 状態を変えずにスコア差分を計算する

2021/03/06 追加しました。
状態の更新をする部分がボトルネックとなっている場合は、
サンプル2の以下のような書き方よりも、

状態を変える
差分スコアを求める
遷移確率probabilityを求める
if (probability > rand01()) // 遷移条件を満たすか
{
  // 変更を受け入れる。スコアを更新
}
else
{
  // 変更を受け入れないので、状態を元に戻す
}

以下のような形のほうが良いです。なぜなら状態遷移しないときに状態更新の計算を省けるからです。また、スコア差分計算時の打ち切りを行う際も、打ち切った際に状態を戻す必要がないため、この形のほうが恩恵が大きいです。

状態を変えずに差分スコアを求める
遷移確率probabilityを求める
if (probability > rand01()) // 遷移条件を満たすか
{
  // 変更を受け入れる。スコアを更新。状態も更新
}

ただ、短時間で書けるほうは大抵サンプル2の形なので、まずはサンプル2の形で書いて、その後この形に持っていくのが良いと思います。

★★ C言語のrand()を使わない。

C言語のrand()は遅いので、高速なxor128を使いましょう。

unsigned int randxor()
{
    static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned int t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
時間計測の関数を呼びすぎない。

サンプル2のように、10000回に1回だけ時間計測をするという方法があります(時間計測の関数はsystem_clockを使えば近年は十分速いですが)。時間計測以外の値でも、毎回計算する必要がないものがあればここで計算してしまいましょう。

    long long steps;    // 試行回数
    for (steps = 0; ; steps++)
    {
        if (steps % 10000 == 0)
        {
            const double time = duration_cast<microseconds>(system_clock::now() - startClock).count() * 1e-6;   // 経過時間(秒)
            if (time >= END_TIME)
            {
                break;
            }

ただ、TopCoderだとこの回数を増やしすぎて、制限時間オーバーしてしまうという可能性もあります。そういった点も考えて、適切な回数おきに時間をはかるようにしましょう。残り時間が少なくなったら、ループ回数を減らすといった安全策をとる方法もあります。

2. 次の状態(状態近傍)をどう決めるか?

ここは鍵になる部分ですが、コツとしてまとめるのは難しいところですね…。

★★★★ スコアが改善しやすくなるように、次の状態を選ぶ。


これは、問題ごとによく考えて対処しなければいけないので、あまり「コツ」というかんじではないのですが…。

[問題]
タスク数aの仕事Aと、タスク数bの仕事Bがある。
作業員はx人いて、それぞれ、1時間あたりにこなせる仕事Aのタスク数と、仕事Bのタスク数は決まっている。
ただし、仕事Aの仕事Bのどちらかしか行うことができない。
仕事Aと仕事Bの両方が終わるのに時間が最小になるように、作業員を仕事Aか仕事Bのどちらかに割り当てよ。

焼きなまし法で解くなら、まず最初にてきとーに作業員をA,Bに割り振り、ここからスコア=作業時間として、改善させていきます。こういった問題を解くときに、次の状態として以下の2つを考えてみましょう。

  1. 移動:ある作業員をA→B または B→A に移動させる。
  2. 交換:Aの作業員の誰かと、Bの作業員の誰かを交換する。

移動2回は交換になることもあるので、とりあえず移動をさせておけば、交換もたまにしてくれるし良さそうに見えますが、そうとは限りません。この場合は、交換を主に行い、たまに移動させるぐらいがちょうど良いと思います。移動では、人数が偏り、片方の仕事の作業時間が増えやすくなります。2回移動すれば、交換になって、作業時間が減る可能性がありますが、

  • 移動:良スコア → 悪いスコア → とても良いスコア
  • 交換:良スコア    → とても良いスコア

と考えると、移動だけだと、スコアが悪い状態を経由しないとダメなので、運がよくないと、とても良いスコアまで辿りつけません。その点、交換ならば、人員が偏った悪いスコアになりやすい状態をスキップできるので、スムーズにとても良いスコアまで改善できます。

もちろん、正しい人数割り当てもしなければいけないので、移動も少しは試したほうがいいですが、こういった点も考えて次の状態を決めると、スコアが改善しやすくなります。

★★★★ 近傍の種類を増やす

2021/03/06 追加しました。

近傍の種類は多くあればあるほど良いです。上記のサンプル2のコードには、近傍が2種類用意されています。

            // 近傍1 : d日目のコンテストをtに変えてみる
            const int d = randXor() % D;
            const int t = randXor() % NUM_TYPES;
            // 近傍2 : d0日目のコンテストとd1日目コンテストを交換してみる
            const int diff = randXor() % 10 + 1;    // d0とd1は10日差まで
            const int d0 = randXor() % (D - diff);
            const int d1 = d0 + diff;

サンプル2では、近傍1も近傍2も50%ずつの確率で選んでいますが、ここをどの近傍をどれぐらいの確率で試すかを調整すれば、性能を改善できるチャンスがあります。また、統計をとるのも大事です。遷移が成功した回数・失敗した回数のデータを取っておけば、どの近傍が有効なのかが分かり、問題を理解するヒントにもなります。さらに、「近傍1で遷移が成功すると、その直後で近傍2で遷移が成功しやすい」などの事実が分かれば、あらたに近傍3「近傍1のあとに近傍2」という新たな近傍を用意することもできるでしょう。

★★ Greedyに、次の状態を選ぶ。

先ほどの問題であれば、「仕事Aと仕事Bそれぞれから、常に作業時間が一番多くかかっている人を1人ずつ選び、交換」とGreedyに、次の状態を選ぶことができます。こういう選び方をすると、ベストスコアは序盤はどんどん伸びていきますが、局所最適に陥りやすいです。また、ありがちなのが、Greedyに選ぶアルゴリズムが、計算時間のボトルネックになってしまうパターンです。複雑なアルゴリズムより、ランダムでとにかくいろいろ試すのが焼きなまし法の強みです。Greedyにやるにせよ、多少ランダムを入れたり、計算時間はかからない単純な選び方をしたりする工夫が必要です。

★★ 序盤は大きく変化、終盤は小さく変化させたほうがいい。

単純にy=f(x)のyを最大化する問題なら、

  • 序盤(t=0に近いとき) 次のx'は x'=x+rand()%1001 - 500
  • 終盤(t=Tに近いとき) 次のx'は x'=x+rand()% 11 - 5

とか、
作業員割り当ての問題なら、

  • 序盤(t=0に近いとき) 交換を100回やる
  • 終盤(t=Tに近いとき) 交換を 1回やる

といったかんじです。スコアが局所最適でハマっている場合は有効です。ただ、焼きなまし法自体が、局所最適にはまりにくいアルゴリズムなので、あまり効果がない場合も多いです。

★★★★ 状態が大きく変化するわりには、スコアが変わらない近傍は良い。

2021/03/06 追加しました。

  • 状態変化が大きいけど、スコアが大きい変化しかしない(悪化する確率が圧倒的に高い)
  • 状態変化が小さいけど、スコアが小さい変化しかしない近傍

となりがちなのですが、問題によっては状態が大きく変化するわりには、スコアがあまり変化がしないケースがあります。こういう近傍があると、遷移が小さい近傍だけは辿りつけない状態にも短時間で行くことができ、焼きなましの性能がアップします。見逃さないようにしましょう。

★★★ 初期状態からすべての状態に行けるようにする。

2021/03/06 追加しました。
選んだ初期状態によっては、どんなに運がよくても用意した近傍ではすべての状態に辿りつけない場合があります。特に解に制約条件があるような問題(例:パズル問題など)で、このようなことが起こりやすいです。すべての状態にいけるような近傍を用意しましょう。

  • 無理にランダムに大きく状態が変化するような近傍を入れてしまうと、それ自体が遷移の成功確率を大きく減らすことにもなり、全体の性能を落とす可能性があるので、簡単ではありません。
  • 多点スタート(後述)にすれば、ある程度緩和されますが、多点スタートでは1つの解を求めるのにかけられる計算時間が減ってしまい、あまりよくありません。
  • スコア関数にペナルティ(後述)を入れる方法もあります。
★★ 良い初期状態からスタートする

これは問題に大きく依存する項目です。初期状態はてきとーでも良い場合と、すこし時間をかけて計算して良い状態から始めたほうが良い場合があります。特に、初期状態が悪いと状態を改善する近傍の選択肢が少なすぎる、逆に言えば、状態を改善すればするほどさらに改善できる可能性が増えるタイプの問題は、初期状態に少し時間を書けて求めて、それから焼きなましたほうが良い結果がでる場合があります。

3. スコア関数

スコア関数(scoring function)とも、評価関数(evaluation function)とも呼びます。

★★★★★ 良い状態を正しく評価できるような、スコア関数を新たに用意する

問題のスコア関数をそのまま使うと、焼きなまし法がうまく行かないことがあります。良い状態を正しく評価できるような、新たなスコア関数を用意しましょう。

[問題]
 (大きく略)…  i番目の人の満足値をs(i)とする。「満足度の最小値 min s(i) 」を、最大化しなさい。

この問題は「満足度の最小値 min s(i) 」を最大化する問題なので、素直に考えると、スコア=「満足度の最小値 min s(i) 」としたくなりそうですが、これは良くありません。仮にそうした場合、

  状態A s(0)=  10, s(1)=10, s(2)=  10 のとき、スコアはmin{s(0),s(1),s(2)} = 10
  状態B s(0)=1000, s(1)=10, s(2)=1000 のとき、スコアはmin{s(0),s(1),s(2)} = 10

と状態Aと状態Bのスコアは同じになってしまいます。これはスコアは同じといえ、状態Bのほうが明らかに良い状態です。なぜなら、s(1)の点が仮に300点に増えたとしたら

  状態A' s(0)=  10, s(1)=300, s(2)=  10 のとき、スコアはmin{s(0),s(1),s(2)} =  10
  状態B' s(0)=1000, s(1)=300, s(2)=1000 のとき、スコアはmin{s(0),s(1),s(2)} = 300

と状態Bのほうは一気にスコアが増えます。しかし元のスコア関数のままだと状態Aと状態Bは同じスコアで、状態A→状態Bはスコア改善になりません。つまり焼きなまし法を行っても、状態A→状態Bには運が良くないと移動しません。
この問題であれば、例えば、
スコア=1番小さいs(i) + 0.0001 * 2番目に小さいs(i)
とすれば

  状態A s(0)=  10, s(1)=10, s(2)=  10 のとき、スコアは 10 + 0.0001 *   10  = 10.001
  状態B s(0)=1000, s(1)=10, s(2)=1000 のとき、スコアは 10 + 0.0001 * 1000  = 10.1

と状態Bの方が好スコアになり、状態A→状態Bに移動しやすくなります。
ここは問題によって大きく有効かどうか大きく異なってきますが、必ず考慮に入れたほうがいいでしょう。結果に大差がつきやすいポイントです。

★★★スコアが改善しやすくなるようなスコア関数を決める。

上記の言い換えともいえるのですが、わりと焼きなまし法のスコア関数をつくるときに、問題のスコア関数をそのまま使ったり、違う状態を正しく評価しなかったりすると、同じスコアになりがちで、青い線のような飛び飛びの平坦な関数になることが多いです。赤いように、山登りしやすいスコア関数を作れないか考えましょう。必ずしも、問題のスコア関数の最大値と、焼きなまし法で使うスコア関数の最大値が一致する必要はありません。最大値をとりうるような状態(argmax)を一致させることが重要です。
f:id:shindannin:20150526014955p:plain

★★★スコア増分が0のときを、無くす。

2021/03/06 追加しました。
スコア増分が0のときは、焼きなまし法をやっても状態が行ったりきたりブラウン運動するだけで、解がなかなか改善しません。また、遷移するときの処理のほうが遷移しないときより重くなる場合、さらにひどいことになります。必ずスコア増分の履歴をチェックし、スコア増分が0になっているときはスコアの差をつけましょう。

★★★ 制約条件がある問題では、スコア関数にペナルティをつける。

2021/03/06 追加しました。
制約条件がある問題で、「制約条件を満たさない状態への遷移を許さない」とすると、ほとんど状態遷移されないままになってしまうことがあります。こういうときの対策としては、制約を満たしていない解も許して、ペナルティをつけて、スコア関数から減点します。

  • 制約条件を満たしている度合いがひどいほど、ペナルティは大きく減点します。
  • 計算の序盤ではペナルティは小さく、徐々にペナルティを大きくして、最後には絶対に制約条件を満たすようにします。
  • 最後にでてきた最適解が制約条件を満たしているか確認しましょう(ただ、そうならないようなペナルティのつけ方を見つけるのが理想です。)

4. 遷移確率と温度

たいていの焼きなまし法の解説書には、expを使った方法が載っています。
焼きなまし法 - Wikipedia

遷移確率 P(e, e' , T) は e' < e の時に 1 を返すよう定義されている(すなわち下りの移動は必ず実行される)。
そうでない場合の確率はexp((e−e' )/T) と定義 

注:wikipediaの引用なので、本文の設定と違います。
    ここでのTは温度(=時間とともに減っていく値)です。
    最小化問題なのでe−e'となってます(最大化問題ならe'-eです)。
時刻tに置ける温度Tを調整する

最初の例の以下のコードの部分です。

     const bool FORCE_NEXT = R*(T-t)>T*(rand()%R);

上の例だと、

  • t=0のとき、常にtrue
  • t=Tのとき、常にfalse

になるような線形関数にしています。だいたいの場合は、これで問題ありませんが、バリエーションはいろいろ考えられます。実際には、ベストスコアの更新状況をみて、更新があまりに序盤と終盤に固まっているときは、2乗してみるとか、ロジスティック曲線をつかうとか、その程度で良いと思います。

★★★★exp(e-e')/Tを使う。(e-e':スコアの悪化量)

wikipediaでは以下のように書いていますが、exp(e-e')/Tの形にしたほうが良いでしょう。(理由は、次回の改定時に書きます)

焼きなまし法 - Wikipedia

関数 P は e' −e の値が増大する際には確率を減らす値を返すように設定される。
つまり、ちょっとしたエネルギー上昇の向こうに極小がある可能性の方が、
どんどん上昇している場合よりも高いという考え方である。しかし、この条件は
必ずしも必須ではなく、上記の必須条件が満たされていればよい。

ただ、このexpの式、分子はスコア差なので分かりますが、分母の温度をどう決めれば良いかは分かりづらいです。目安としては、たまには許容しても良いスコアの悪化量を温度とすると良いです。 最大の山を越えられるようにと考えると、考えられるスコアの最大値-最小値を初期温度を設定したほうが良いのですが、実際には温度調整して最終スコアがどうなるか実験してみてください。

double startTemp   =  100;
double endTemp     =   10;
double temp        = startTemp + (endTemp - startTemp) * t / T;
double probability = exp((nextScore - currentScore) / temp);  // 最大化なので、分子はnextScore - currentScoreで良い。
bool FORCE_NEXT    = probability > (double)(mXor.random() % R) / R;

時刻t=0(最初)でtemp=startTemp、時刻t=T(最後)でtemp=endTempとなります。

例えばスコアが100悪化したとき、nextScore - currentScore = -100なので、startTempを100にしてみます。endTempはとりあえず10にしてみましょう。
時間t=0であれば、exp(-100/100) = exp(- 1) = 0.36787944117と、3回に1回ぐらいは遷移します。
時間t=Tであれば、exp(-100/ 10) = exp(-10) = 0.00004539992と、まず遷移はしません。
このような感じでやると、良いと思います。

5. アレンジ

★★★★ 山登り

最初の例をFORCE_NEXT=0にすれば、山登り法になります。そもそも関数が凸であれば、山登り法も焼きなまし法も結果は一緒で、しかもrand()を使わない分、山登り法のほうが高速で、スコア改善のチャンスも多くなります。簡単に試せるので、試しましょう。

多点スタート

焼きなまし法をつかっても、局所解にはまりやすい場合は、初期値を毎回かえた、多点スタートにする方法もあります。山登りと同時に使う方法もあります。ただ、多点スタートで結果がよくなるケースは、そもそもスコア関数や近傍が良くないので、そこを見直したほうがよいかもしれません。

★★★ 1変数ごとに焼きなまし

焼きなまし法で、たとえば、y = f(x1,x2,x3,x4,x5)と、状態変数が多いとき、次の状態のパターンが多くなり、結果的にあまり多くの状態を試せず、良い解が求められないときがあります。このような場合は、x2=x3=x4=x5を固定して、x1を焼きなまし、x1=x3=x4=x5を固定して、x2を焼きなまし、x1=x2=x4=x5を固定して、x3を焼きなましというふうに1変数ずつ焼きなまししていく方法があります。xの値がそれぞれ独立性が高い(?)場合は、この方法は有効です。

6. デバッグ

スコア差分の検算

2021/03/06 追加しました。
例えばサンプル2ではスコアの差分を計算していますが、いきなり書くとバグらせる可能性もあります。以下のような手順をとれば、バグがないか確認することができます。

  1. サンプル1のgetFullScoreのように、全体のスコアの関数を用意して、それが正しいか確認します。通常のコンテストなら提出することで確認できます。
  2. 差分スコアrealDeltaScore = getFullScore(遷移後) - getFullScore(遷移前)として計算します。
  3. サンプル2のようにdeltaScoreを直接求める方法ができたら、realDeltaScoreと一致するか確認します。
デバッグの際には、決定的にする

2021/03/06 追加しました。
状態やスコアが、まれにおかしくなるといったバグがあった場合、通常の焼きなまし法は非決定的なのでバグが再現ができない場合があります。そういったときは、デバッグ時には決定的にしましょう。

  • 温度を求めるときにsystem clockを使わずに、最大ループ回数を固定して進行割合で温度を求めるようにしましょう。
    const static long long MAX_STEPS   =  10000000; // 終了までの回数
    for (long long steps = 0; steps < MAX_STEPS ; steps++) // 試行回数
    {
            const double progressRatio = static_cast<double>(steps) / MAX_STEPS;   // 進捗。開始時が0.0、終了時が1.0
            temp = START_TEMP + (END_TEMP - START_TEMP) * progressRatio;
  • 乱数はシードさえ固定すれば決定的になるので問題ありません。
  • もしマルチスレッドを使っている場合は、グローバル変数とstatic変数に気をつけましょう。とくに乱数でstaticを使っている場合は乱数をクラス化するか、シングルスレッドで実行しましょう。

7. まだ書いていない内容

  • 並列化
    • 排他制御つきの焼きなまし
    • ロックフリーの焼きなまし
  • タブーサーチ + 焼きなまし
  • レプリカ交換法

リンク集

基礎編

AtCoder wataさんによる公式解説
https://img.atcoder.jp/intro-heuristics/editorial.pdf

Tsukammoさんの記事
qiita.com

gacinさんの記事
gasin.hatenadiary.jp

応用編

ats5515さんは、巨大近傍法(状態遷移の回数は少なめになるけど、計算時間をかけてより良い次の状態を探す)が特に強いです。近傍の計算時間に。焼きなまし法の近傍を探すのに2段目の焼きなまし、制約条件をほぼ満たす準validな状態、温度遷移の工夫など、他の人があまり工夫しないもところでもいろいろバリエーションがあります。
ats5515.hatenablog.com

hakomoさんの記事は、まさに詳細という内容です。探索空間の話は、この記事が一番詳しいと思います。事例へのリンクも多いです。
github.com

2021年2月の行動目標

今月も予定が読めないので、先月達成できなかった目標は簡単にしました。

競プロ(アルゴリズム)
  • 高速フーリエ変換・数論変換の理解
  • ACLの遅延セグ木で10問解く
  • 全方位木DPをライブラリ化
競プロ(マラソン)
  • Hash Codeの練習を5回する
将棋
  • 実戦詰み筋事典を1周する(186問)
スポーツ
  • 月10回リングフィットアドベンチャーをする。

2021年1月の振り返り

仕事はだいぶおさまったのですが、プライベートがいろいろ入ったために、将棋の目標以外は達成できず。ちょっと2月以降も忙しくなるか余裕がでるか読めないのですが、おそらく1月と同じぐらいだと思うので、将棋以外はもう少し簡単な目標を立てることにします。

競プロ(アルゴリズム)
  • ABC178以降の解いてなかったやつを終わらせる
    • ❌8回分残っています…
競プロ(マラソン)
  • 記事を2つ書く
    • ❌1つも書けませんでした。
将棋
  • 5手詰めハンドブック1を1周する(200問)
    • ⭕無事完了しました。
スポーツ
  • 月15回リングフィットアドベンチャーをする。
    • ❌2回しかしていない。

2021年1月の行動目標

とにかく簡単な目標からスタートすることにしました。将棋とスポーツは朝に30分くらいやって、競プロを休日にやるかんじで。

競プロ(アルゴリズム)
  • ABC178以降の解いてなかったやつを終わらせる
競プロ(マラソン)
  • 記事を2つ書く
将棋
  • 5手詰めハンドブック1を1周する(200問)
スポーツ
  • 月15回リングフィットアドベンチャーをする。

2021年の目標

定義(成果目標と行動目標)

成果目標🏆 ... 結果を出しさえすれば良い目標。ただ、自分ががんばっても、まわりの環境により達成できない場合もあるかも(例:将棋で二段になる)
行動目標🏅 ... その行動さえやれば達成できる目標。完全に自分との戦い。(例:詰将棋10問を毎日解く)

2020年の反省

  • 2020年は成果目標も行動目標も高すぎた。2021年はまず達成できる目標を立てる。高い目標を立てていいのは、もっと現実的な目標を達成できる人間になってから!
  • 2020年は目標の種類数も多すぎた。切り替え上手な人はいいけど、意思の弱い自分は、脱線につながるのでも増えるのでことも多かったので、自分には今は無理。
  • 毎日趣味のための時間を確保すればいいと思うのだけど、今の仕事だと多忙になると難しい(無理ではないが)。とはいえ、それを目指すべきではある
  • 将棋については詰将棋が毎日定着しそうだったのだけど、自主的に負荷を増やしてみたら、その後急に忙しくなり、忙しさがある程度やんだあとも、元にもどらなくなった…。 もうちょっと目標をマメに見直していれば、途中で立て直せたかもしれない

2021年目標に立てるにあたってのテーマ

  • 行動目標の達成に集中する
  • 毎月行動目標を立てて、月末に振り返る
    • 2021年は、先が読めなく優先度が高い予定が入りそう。引っ越しは確定。仕事でも大きな動きがありそう。なんで、急に時間が確保できなくなったりすることが多いにありうる
    • 大幅に予定が狂った後に、成果目標が達成しようと帳尻あわせようと、無理やりなスケジュールを立てて、よく破綻してる。そろそろ学習して、これは避けたい。
    • まずは簡単な目標を立てて、達成できたら少しずつ難度が高い行動目標を立てていくことにします。忙しくなったら、難度を下げる。
  • そういうわけで、2021年1月の行動目標は別記事で立てました。毎月書いていきます。

shindannin.hatenadiary.com

2021年成果目標(おまけ)

年末に振り返りますが、行動目標さえ達成できれば2021年はよいことにします。成果目標はおまけ。

競プロ(アルゴリズム)
  • 2021/6/30までに、AtCoderで青1800
  • 2021/12/31までに、AtCoderで黄2000
競プロ(マラソン)
  • オンサイト決勝に進出する
  • AtCoderヒューリスティックスで、赤色相当に入る(レーティングシステムが決まり次第立て直します)
将棋
  • 2021/6/30までに、将棋ウォーズ初段50%
  • 2021/12/31までに、将棋ウォーズ二段
スポーツ
  • 週に3回以上は運動して、習慣化する。

2020年の目標が達成できたか?

結果のまとめ

予定の2割程度しか目標を達成できていないので、ダメでした。2021年は現実的な目標と、急に忙しくなった場合の対策を考えましょう(対策がなければ、極力減らす)



原文
shindannin.hatenadiary.com

以下ふりかえり。


目標原文:黒色
結果と感想:→青色

⭐⭐⭐ 2020年の目標を達成している。
⭐⭐ 2020年の目標を達成できそう。
⭐ 2020年の目標は到達できてないが、進展はある。
💀 進展していない、もしくは後退している。

目標の前に

2020年は、定時で帰る(大前提)

2019年は、仕事時間が長すぎました。長時間労働が必ずしも悪いとはいえないですし(結果を出すのがなにより重要)、別にダラダラ働いていたわけではないですが、2020年はいったん短時間労働制約を自分に課して(基本定時に帰る)で、どう効率よく仕事すればいいかを考えるきっかけにしたいと思います。これで仕事の結果がダメになったら、それは自分の責任。
→物量が読めない専門外の仕事が多く、かつ会社全体も忙しく、結局2019年よりも忙しい厳しい1年でした。9月~11月はtwitter封印しなければならない厳しい展開で、休日出勤・深夜労働もする展開に…。2021年もいろいろ変化があると思うので忙しいとは思いますが、どこらへんで折り合いをつけるかが難しいですね…。。

2020年の目標

競プロ(短時間マッチ系)💼💼🌞🌞

AtCoder 黄色
→💀1684⇒1645
AtCoder Problems 250000 pts (ABCのC以上の問題で)
→💀100100⇒135300

2019年はレートを大きく下げてしまいました。最後に目標を達成して、単純に練習量の不足なだけという結論に達したので、2020年はがんばりたいです。3ヵ月おきで目標を区切り達成を目指す予定。
(参考)2019年下半期の結果
→一番優先順位が下がってしまい、コンテストでるだけで終わってしまいました…

競プロ(マラソンマッチ系)🌞

マラソンマッチ(Hash Code・日本橋ハーフマラソンなど)で1回はオンサイトの決勝に行く
→⭐⭐⭐Hash Codeで世界大会の決勝にでる
マラソンマッチに10回参加
→⭐⭐9回

ただし、もし2020年中に、AtCoderマラソンマッチにレーティングのようなものがついたら、目標自体を追加変更するかもしれません。
→マラソンマッチ系については、一部の結果は素晴らしかったのですが(Hash Code 33位、Introduction to Heuristics Contest 1位)、Hash Codeは自分自身は不調で、実力アップのための対策や、復習も滞りました。また、時間を確保できないまま参戦しひどい結果が出てしまったのも多かったです…。

将棋 💼

将棋ウォーズ二段
→⭐将棋ウォーズ初段(達成率8.7%)
勉強記録を1年間つけ続ける
→⭐6月まではマメにつけていたが、その後滞る。ただ最低限の情報だけは記録できた。


→「将棋ウォーズの対局とその復習に偏りすぎで、忙しくなると、詰将棋・次の1手などの日課をサボってしまう」という状況から色々崩れていった気がします。対局が楽しすぎるのは、諸刃の剣で、とても忙しい時期でも将棋ウォーズ対局は現実逃避でやっていて、結果継続できたので1年で510時間25分もかけていました。このうちの100時間でも詰将棋・次の1手につぎ込んでいれば良かったのに…。とあるアマチュア向けの上達本に「将棋の実際の対局は、将棋に費やす時間の1割以下にすること」と書いてありましたが、対局7割復習2割勉強1割ぐらいになっていました…。

以下の目標は、他の目標が全然できていないので、今年の目標からカットしたもの。未達。大反省。


カットした目標

共同研究(追加) 💼🌞
以前からアイディアがあるのですが、次の記事で具体的な内容について書きますので(今週中の予定)、ぜひご協力いただければ幸いです。なお内容については変更があります。
f:id:shindannin:20200818095955p:plain
f:id:shindannin:20200818100100p:plain


ゲームをする🌞
🏅ゲームを250時間以上する
→⭐⭐⭐307時間

多くはないですが、これぐらいで。
→将棋ウォーズを入れてしまいましたが(237時間プレイした)、その他はリングフィット・壺おじ・自社のゲームぐらいしかやっていない気が。これはダメ…
→本当は他のゲームで250時間以上する予定だったのですが、目標変更するのもあれなので、今年の目標からカット!

ゲーム技術系 💼
🏆Unityの試験(エキスパート ゲームプレイプログラマ)に受かる
→💀何もしていない
🏅ゲーム開発の議論ネタになるような記事を2か月に1回書く。
→💀何もしていない

2019年は、過去のゲーム開発で得た経験・知識を徐々に忘れてきているというのを実感しました。ボケを防ぐためにも、ゲーム開発のネタの記事を今年から書いていこうと思います。記事の質は微妙になると思いますが、議論の土台になるように書いていきたいです。
また、2019年は仕事内容が変わってUnityを使うようになりました。「ゲームエンジンを使用したことがある人だったら、商用のUnityも使えるだろう」と思っていたのですが、まぁ使えてはいますが…

  • Unity経験が多い人ほど、Unityで良いゲームを作れる(あたりまえ)
  • 他のエンジンをできるだけ多く詳しく知っておくことが、将来、自前でフルスクラッチでゲームエンジンを作るときにも役立つ。

という気持ちになったので、Unityの試験を受けてみようかなと思います。
https://certification.unity.com/ja/products/expert-gameplay-programmer
→他の目標が全然できていないので、今年の目標からカット!


言語 💼

🏅中国語の勉強して、簡単な日常会話ができるよう
→💀何もしていない

まだ個人的な理由で、広東語かマンダリンのどっちを勉強するかなど、細かいことを決めていませんが、決まり次第更新します。それにより成果目標を追加予定です。
→他の目標が全然できていないので、今年の目標からカット!