5
Help us understand the problem. What are the problem?

posted at

updated at

競技プログラミングAI「AlphaCode」のコードレビューをしてみた 😱

DeepMindのAlphaシリーズ最新作「AlphaCode」が、競技プログラマーの標準レベル(Codeforces TOP 54%)に達したとの発表がありました。
AlphaCodeは今をときめくTransformer系のディープラーニングで、課題文を入力すると解答プログラムを出力する自然言語処理を行います。そうです、これはすなわちプログラミングをするプログラムです。マジかよ……。
詳しい手法については公式ブログ論文を参照してほしいのですが、DeepMindは別途いくつかの解答例について正誤あわせて確認できるデモサイトも用意していて、これがめちゃくちゃ面白いです。

ええ、こちとら天然物のプログラマーです。人工知能とやらが絵や写真を自動生成しはじめたあたりはまだ笑って眺めていられましたが、我々の崇高なるプログラミング領域を侵されるとなってはたまりません。いうて大したことないやろ的な、上から目線で厳しく評価していきます(フラグ

1553_D.Backspace (Python)

1553_D.Backspaceは、代表例として取り上げられているシンプルな課題です。
たとえば「abcde」という文字列をタイピングするとします。その際、それぞれの文字キーを押す代わりに「BackSpace」を押しても構いません。仮に、1番目の文字「a」と4番目の文字「d」の代わりに「Backspace」を押したとすると、二回目の「Backspace」で「c」も消えて、タイピングした結果は「be」となります。
ということを踏まえて、たとえば「ababa」をタイピングして「ba」にできるかどうか判定してください、というのがこの課題になります。(このケースはできるので「YES」と出力できれば正解)

コードレビュー

このプログラム自体は正しく課題を解けるので、競技プログラミング的にはOKなのですが、あえてコードレビューしてみました。あれ、思ったよりツッコミ所が少ない……。
逆に、褒めポイントとしては、

  • しっかりインデントできている。
  • 問題文に書かれている文字列 s t を表す変数は、そのまま s t と名付けている。
  • if elif のAND条件の並びが揃っていて読みやすい。

というところでしょうか。うーん、よく書けてるなぁ……。

コーディング中の迷い

AlphaCodeが人間よりも優れている点として、コーディング中の思考過程もトークンの確率として出力できることが挙げられます。確率の高い候補が複数あれば、それはだいぶ迷っていると解釈できますし、100%の1択であれば、そこは確信を持ってコーディングしていたということになります。
なお冒頭のスクリーンショット動画で色が付いている部分はMulti Head Attentionを可視化していて、それもかなり興味深いのですが、明確に読み解くのが難しそうだったのでここでは触れません。

変数命名

最も確率高く実際に選んだ s 以外にも、よくある変数名 a x flag str などが候補に上がっています。

スペースかタブか


初めにインデントするところで、タブを選ぶ確率も少しあったようです。


以降は、ほぼスペース一択になっています。
初めにタブを選んでいたら、タブに統一していたであろう雰囲気を感じます。

指運


この while を選ぶ確率はTOP10に入っておらず、1%未満だったようです。
直前で変数 c を宣言していたので、その流れで変数 d も宣言するのが最有力だったようで、その後に必要なループを書きはじめるつもりだったのかもしれませんが、ここで while により正着のループ構文に入れたのは運が良かったですね。

Annotated Problems

デモサイトには1553_D.Backspace以外にも多数の解答例が掲載されているのですが、その中にいくつかPetr Mitrichev氏(国際大会優勝多数の競技プログラマー)による評価文付きのものがあります。
注目すべきものということだと思うので、正答例を覗いてみましょう。

サブ関数

  • 1556_E. Buds Re-hanging (C++)

  • 1623_B. Game on Ranges (C++)

サブ関数を定義して、のちにメイン関数で使っている例です。
ただ実際には不要であったり、メンバー変数が冗長であることが評価文で指摘されています。
ただ人間の競技プログラマーも、持ち込んだスニペットを整理しないまま提出することはわりとありそうなので、そこまでおかしなことでもない気はします。

scanfかcinか

  • 1556_E. Buds Re-hanging (C++)

  • 1618_B. Missing Bigram (C++)

  • 1618_E. Singers' Tour

  • 1623_B. Game on Ranges (C++)

Codeforcesの課題は1行目でテストケース数を読みこむという入力形式になっているようで、やるべき読み込み処理は変わらない中でも、scanfのみ使う場合、cinのみ使う場合、両方使う場合、とコード上ではバリエーション豊かなところが面白いですね。

コメント行

デモサイトに掲載されている正答例から目についたコメント行を集めてみたのですが、面白いことに全てPythonコードで、C++コードには見当たりませんでした。
これはおそらく学習データの違いで、C++競技プログラマーは無駄なコメントを残さないが、Python競技プログラマーはコメント残っていても気にしない人がそこそこいる、ということを示唆しているような気がします。

謎の指示

  • 1554_C. Mikasa (Python)

ちなみに、この課題はとくに料理とは関係ありません。

謎の作者

  • 1566_D1. Seating Arrangements (easy version) (Python)

人間性を捧げたのでしょうか……

長いコメントアウト

  • 1560_A. Dislike of Threes (Python)

  • 1556_A. A Variety of Operations (Python)

コメントアウトされたコード自体に、あまり意味のなそうな繰り返し構造が見られますね。RNNでありがち。

感想

いや、ホント凄いですね。5年前にLSTMでなんちゃってコード生成をしたことあるのですが、それから隔世の感があります。

もちろん、これは競技プログラミングに特化したものであり、課題として仕様がしっかり書かれているからこそ出来る芸当であって、人間のプログラマーが仕事を奪われるような事態には程遠いのですが、とはいえ凄いです。ぶっちゃけ怖い……。
少なくとも私の場合、ここで取り上げた課題についてはゼロから解くよりAlphaCodeの書いたコードを修正するほうが楽そうなので、将来的に限定的な領域において人間の仕事はコーディングすることではなくコードレビューすること、という未来はありそうです。
アルゴリズム実装できるようになったら、次はクラス設計ですかねー。仕様にあたるものの学習データどう集めるんだ問題はありますが、そこさえ何となかれば、いずれどうにかなってしまいそうな雰囲気はあります。そうしたら、そうしたら我々は(文章はここで途切れている

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
5
Help us understand the problem. What are the problem?