Twitter で医師が拾われて Google のソフトウェアエンジニアになって 3 年半が過ぎました

はじめに

nuc.hatenadiary.org

という、元 Google ソフトウェアエンジニア (Software Engineer、以下 SWE) が、 SWE 未経験の医師の Google SWE 選考突破をお手伝いした記事があります。当時この記事は、瞬く間に広まり、多くの方々に読まれました。自分もその読者の一人でした。

私は、 1 年半ほど前から、上記の記事の著者である nuc さんとともに、 Google SWE を志望する方々に模擬面接を行い、就職・転職をサポートしてきました。その人数は、約 60 名ほどになります。本ブログエントリでは、私のこれまでの活動を振り返りつつ、 Google SWE 入社試験対策の知見をまとめていきます。

本ブログエントリの目的は、 Google SWE への就職・転職を考えている方に、 Google SWE の入社試験の、真の姿を見ていただくことです。本ブログエントリを通じて、 Google SWE の入社試験が、天才しか通らないような世界最難関の入社試験などではなく、正しい方法でそれなりに勉強すれば合格できる、普通の入社試験であるという認識を持っていただければ幸いです。

『天才』はつくれる

Google のソフトウェアエンジニア入社試験は、天才認定試験ではありません。選ばれた者のみが合格する試験でもありません。誤解を恐れずに言えば、普通のエンジニアが合格する試験です。ここで言う普通とは、 GoogleSWE として、最低限知っていて欲しい範囲、できていて欲しい範囲をカバーしている人のことを言います。難関大学を卒業しているですとか、地頭がいいですとか、 IQ が高いですとか、特定の能力に秀でているですとか、プログラミングコンテストの上位者ですとか、機械学習に詳しいですとか、アカデミックな成果を持っているですとか、自作アプリが大ヒットしたですとか、オープンソースソフトウェアへの豊富なコミット経験があるですとか、そういったものはほとんど関係ありません。最低限知っていて欲しい範囲、できていて欲しい範囲を押さえていれば合格します。その範囲とは、コンピューターサイエンスの知識、コーディング能力、 SWE として仕事をする上でのマインドセットです。逆に、これらの範囲がカバーできていないと、合格は難しいです。

正直なことを言うと、自分自身、 Google SWE の入社試験は、天才認定試験であり、選ばれた者のみが合格する、世界最難関の入社試験だと思っていました。そして、自分自身が合格したことにより、自分が天才なのではないかとか、選ばれた者なのではないかと自惚れてしまいました。それと同時に、自分などが天才などであるはずがない、選ばれるはずがない、何か選考プロセスに誤りがあったのではないか、などとも考えるようになりました。このような葛藤が、入社後ずっと続きました。

4 年半の葛藤まみれの勤務を終えたあと、数年経ち、 nuc さんから 「Twitter で医師を拾ってきて Google のソフトウェアエンジニアにするだけの簡単なお仕事」のお話を聞きました。その中で、 nuc さんより「あれは高校化学くらいの難易度ですよ。」と説明されました。それを聞いて、何となくピンと来ました。

自分は大学受験のとき、化学の科目は、それなりに苦労しました。元々、いわゆる暗記物の勉強は苦手で、必要となる知識量がそれなりに多い化学は、あまり好きではありませんでした。それでも、受験勉強シーズンに教科書と問題集と資料集で真面目に勉強し、どうにかこうにか受験で使い物になる程度にはなりました。

GoogleSWE になるための難易度が、高校化学の難易度と同じくらいと言われると、確かに納得できそうでした。それなりの知識量が必要となり、それなりの勉強量が必要となるものの、自分自身すでに過去に経験していることですし、毎年数十万人の高校生がやっていることです。

そこから 1 か月くらい、自分の中で内容を咀嚼し、ようやく、 Google SWE の入社試験が、天才認定試験でも、選ばれたもののみが合格する試験でもない、と思えるようになりました。

しばらくして、 nuc さんが主催する模擬面接に参加させていただきました。模擬面接に参加されている方々は、その時点では、ひいき目に見ても合格できそうにありませんでした。 nuc さんは、 Google SWE の入社試験は対策が可能であるという信念の下、自身の応募者と面接官の両方の立場での経験を基に、 Google SWE の入社試験の内容を詳細に分析し、対策方法を確立し、その方法に基づいて指導されていました。自分は、正直なところ、初めのうちは、その対策方法に対し、半信半疑でした。

数か月後、 nuc さんが模擬面接で指導した方々が、次々に Google SWE の入社試験に合格された事を聞きました。この時点でも、まだ自分の中では入社試験対策に対し、半信半疑でした。

その後、 nuc さんの指導方法を真似て、自分も模擬面接を始めてみました。採用プロセスの説明スライドを用意し、模擬面接用の問題を選定し、指導内容を整理し、実際に模擬面接をしてみました。すると、確かに少なくない方が合格されるのです。正直に言って、驚きました。 Google SWE の入社試験は、天才認定試験や、選ばれた者のみが合格するようなものではなく、対策可能な普通の試験なのだということを認識しました。また、模擬面接を通して、自分自身、 Google SWE の入社試験に対する解像度や、 SWE のあり方そのものに対する解像度が高くなりました。

nuc さんの入社試験対策は、巷にあふれている「私が Google SWE 入社試験に受かった方法」的なものではありません。 Google SWE の入社試験の脆弱性を突いた、ハッキングのようなものでもありません。ソフトウェアエンジニアリングの目的を学び、その目的を達成するための手段を身につけることにより、 SWE として正しいスタート地点に立ち、その結果、入社試験にも合格するというものです。ここで、ソフトウェアエンジニアリングの目的とは、ユーザーのためになるものを提供することを表します。また、手段とは、この章の初めに登場した、最低限知っていて欲しい範囲、できていて欲しい範囲を指します。

競技プログラミング同好会競技就活部門

私たちは、社会人サークル「競技プログラミング同好会競技就活部門」 という名前で活動しています。サークル発足のきっかけは、 2017 年 2 月に主催者の nuc さんが転職希望者に対し模擬面接を行い、 GoogleSWE の面接を通過させたことです。

その後、東京大学の学生サークル「競技プログラミング同好会」の元メンバーが中心となって、競技プログラミング同好会競技就活部門が結成されました。やや余談となりますが、競技プログラミング同好会は、はじめて競技プログラミングという言葉を作ったサークルです。また、そのサークルが開催したコンテストが、東京大学プログラミングコンテスト (UTPC) で、その第 4 回である UTPC 2011 が AtCoder で開かれた初めてのコンテストです。

競技プログラミング同好会競技就活部門には、現在では他大学出身者も参加しています。

競技就活部門のメンバーは、全員が元 Google メンバーです。現在は、模擬面接・練習会を通し、参加者の皆様に指導・フィードバックを行い、就活・転職をサポートするという活動を行っています。

これまでの参加者数は、累計で百数十名に上ります。 初期は、講師役数名と生徒役数名ずつで、会議室を借りて模擬面接をしていました。この形式の頃の参加者数は、累計で 40 名弱ほどです。その後、教室を借りた講義形式と、 オンラインでの講師役数名と生徒役 1 名の模擬面接の形式に移行しました。講義形式の方には、毎回数十名が参加されました。
初期に参加された方のうち、半数の 20 名程が Google に応募しました。そのうち、約 7 割が合格され、入社されています。入社できなかった方で一番多かったのは、転職組で、応募の時点で日本にポストがないと言われたパターンです。オンサイト面接での不合格は、現時点までに一人もいなかったと思います。過去 5 年間の活動を通して、 Google に十数名、さまざまな外資 IT や外資銀行等に、若干名ずつ就職しています。

合格者の内訳は、文系が 2~3 割、医師が 2 割、競技プログラミングサイト AtCoder のアカウント所有者が半分程度です。 AtCoder アカウント所有者の色の内訳は、緑、水色、青がほぼ同数です。ただしこれは、 Google SWE の入社試験の合格に、緑が必要という意味ではありません。茶色 (下から 2 番目のランク) でも合格できると考えています。実際、茶色の方々で、私たちから見て合格できるだろうと思えるようになった方々がいます。その方々は、 Hiring Freeze の影響で採用過程が途中でストップしていますが、本番の面接を一部突破されています。

参加者の募集にあたり、試験等の選抜・選別は、一切行っておりません。

Google は世界最高のプログラミングスクールである

競技就活部門が Google への就職・転職をおすすめしている理由は、勉強の場として、極めて優れていると考えているためです。

Google は、会社の中の仕組みが、とてもよくできています。Google には、 Hiring Freeze の前までは、全社で 160,000 人の正社員がいました。また、毎年 50,000 人程度が、新入社員として入社していました。これらの情報から単純計算すると、社員の平均在籍年数は、 3 年程度となります。通常の会社では、平均在籍年数 3 年程度の場合、会社の運営が立ち行かなくなるのではないかと思います。にもかかわらず、 Google は、現在 IT 系の一流企業として認識されています。この理由は、組織構成、指針、ルール、ガイドライン、価値の判断基準、インフラ、ツール、フレームワーク等、 Google の中の仕組みがとてもよくできているためだと考えられます。

Google に入社し、末端として働くことで、かなりの勉強になります。別の言い方をすると、競技就活部門としては、皆様に、 Google に入社し、技を盗んできて欲しいと考えています。さらに別の言い方をすると、 Google 自体をプログラミングスクールとみなし、勉強のためと割り切って入社して欲しいと考えています。そして、数年程度、お給料をもらいながら仕事を通じて勉強し、次のステージに進むことをおすすめしています。転職するのも良いと思いますし、起業するのも良いと思いますし、フリーランスになるのも良いと思います。 Google で働き続けても良いと思います。いずれの場合にも、 Google の中で勉強したことは、大いに役立つのではないかと思います。

雇用形態と働き方

一般的に雇用形態には、大きく分けて、「メンバーシップ型雇用」と「ジョブ型雇用」の 2 種類があります。メンバーシップ型雇用は、採用された人に対して、様々な仕事を割り当てる雇用形態です。一方、ジョブ型雇用は、採用された人に対して、特定の仕事を割り当てる雇用形態です。

また、上記 2 つとは別に、働き方の分類として、ジェネラリストとスペシャリストという分類があります。ジェネラリストは、広く様々な分野に対応できる人のことを言います。一方、スペシャリストは、特定の分野を深く掘り下げることができる人のことを言います。

GoogleSWE は、ジョブ型雇用形態を取りつつ、ジェネラリストとしての働き方が求められます。つまり、各 SWE がソフトウェアエンジニアリングに従事するために雇われ、特定の分野に限らないソフトウェアエンジニアリング全般を担当します。

GoogleSWE にジェネラリストとしての働きが求められる理由は、 Google の中では、チームの異動等、人材の流動性が高いためです。あるチームでスペシャリストとして働いていた場合、他のチームに異動した場合に、パフォーマンスが出にくくなってしまう可能性があります。また、スペシャリストは属人性を生んでしまうため、チームの規模がスケールせず、単一障害点にもなりやすくなってしまいます。

また、 メンバーシップ型雇用とは違い、ジョブ型雇用では、会社は人生プラン・スキルセットを計画してくれません。そのため、多くの Google SWE は、自分の人生プラン・スキルセットを、自分で計画します。例えば、 10 年後にどのような生き方、働き方をしたいかを想像し、そのために、 1 年後、 3 年後、 5 年後に、どのような仕事をしたり、どのような勉強をしたりするか、自分で計画します。別の言い方をすると、セルフプロデュース、セルフブランディング、とも言えます。

ソフトウェアエンジニア (SWE)

SWE とはどのような職業なのか、説明します。 SWE の説明の前に、まずエンジニアリングとは何かについて、説明します。

エンジニアリング (工学) とは、以下のようなものだとされています。

工学とは数学と自然科学を基礎とし、ときには人文社会科学の知見を用いて、公共の安全、健康、福祉のために有用な事物や快適な環境を構築することを目的とする学問である。

「8大学工学部を中心とした 工学における教育プログラムに関する検討」工学における教育プログラムに関する検討委員会、1998年5月8日。

ここで重要となるのが、エンジニアリングの目的です。エンジニアリングの目的は「公共の安全、健康、福祉のために有用な事物や快適な環境を構築すること」です。言い換えると、ユーザーのためになるものを提供することが目的となります。そして、その手段として「数学と自然科学を基礎とし、ときには人文社会科学の知見を用い」ます。この「ユーザーのため」という目的意識は、 Google SWE の入社試験に、大きく関わってきます。この部分を念頭に置いて、残りの文章を読んでいただければ幸いです。

続いて、 ソフトウェアエンジニアリングについて説明します。 ソフトウェアエンジニアリングとは、エンジニアリングのうち、手段としてソフトウェア技術を用いるものを指しています。具体的には、以下のようなものだとされています。

“しかし「ソフトウェアエンジニアリング」には、何らかの現実的で精密なものを構築するべくある種の理論的知識を応用することを意味するかのような、「プログラミング」よりは重々しい響きがある。” 

“我々が提案するのは、「ソフトウェアエンジニアリング」とは単にコードを書く行為のみならず、組織が時間の経過に応じてコードを構築し保守するために用いるツールとプロセス全てをも包含するということである。”

“ソフトウェアエンジニアリングとは「時間で積分したプログラミング」とみなせる”

Googleのソフトウェアエンジニアリング ──持続可能なプログラミングを支える技術、文化、プロセス Titus Winters

ソフトウェアの開発のみならず、計画から保守まで、開発前後の作業も対象となっているということなのだと思います。

そして、 SWE は、上記を行う者の事を指すということになります。

Google でのお仕事

Google における SWE のお仕事は、きわめて多岐にわたります。以下に、それらを挙げます。

  • 市場の需要の調査
  • 客先へのヒアリング
  • 問題の発見
  • 企画立案
  • 設計
  • 実装
  • デバッグ
  • テスト
  • コードレビュー
  • リリース
  • メンテナンス
  • 上司の説得
  • 部下の教育
  • ステークホルダーマネジメント
  • 社内広報
  • 重役へのプレゼン

これらすべてが、 GoogleSWE のお仕事です。非常に多岐にわたることが分かると思います。

ただし、すべての分野において 100 点満点を取る必要はありません。どれも 30 点ぐらいずつ取れて、得意分野で 60 点取れれば十分です。ただし、どれか 1 つでも 0 点があると、 SWE として働くのは非常に厳しいように思います。

とはいえ、最初からすべてこなせる人は、おそらくいないと思います。入社後に 1 つずつできるようになれば良いと思います。

Google の面接の内容

Google SWE の面接は、 GoogleSWE のお仕事の仮想体験となっています。この仮想体験を通し、面接官は、応募者が SWE として働けるかどうかを見定めます。

面接では、 SWE として働くにあたり、必要な知識・能力が問われます。ここで必要となる知識・能力は、 GoogleSWE の 8〜9 割が知っていること・できることです。これを nuc さんは、 GoogleSWE の常識と呼んでいます。常識の範囲は、前述の最低限知っていて欲しい範囲、できていて欲しい範囲と同等です。

面接対策の難易度は、思考力・勉強量ともに、高校化学程度です。高校時代に大学受験で高校化学を学んだ方はイメージしやすいと思うのですが、それなりの分量の勉強が必要となります。ただ、多くの大学受験生が受験で化学を選択していることを考えると、少なくない人がこの勉強量をこなせるのではないかと思います。また、しばしば計算問題も出題されます。それらを解くために必要な知識も、高校化学に登場するものとほぼ同等のものだと思います。人によっては、高校化学 + 高校物理程度の分量の勉強が必要だと感じるかもしれません。高校化学を履修していなかった方は、アルファベットを知らないところから英検 3 級に受かるまで、つまり、中学の英語全体の難易度だと思うと良いと思います。

面接においては、 GoogleSWE が仕事中に出会った問題を、そのまま応募者に聞くこともあります。例えば、面接の前日の夕方に実装で困った部分を、翌朝の面接でそのまま聞く、といった事もあります。これは、困ったときに同僚の相談相手になれるかという、仕事の一場面の仮想体験となっています。

面接には、 15〜20 分で答えられないような難しい問題は出題されません。これは、難しい問題を出題して、応募者が答えられなかった場合、応募者は難しい問題に答えられなかったという情報しか得られないためです。この情報は、採用するかどうかを判断するにあたって、まったく価値がありません。また、たとえ答えられたとしても、大した情報にはなりません。よって、そのような問題は出題されません。

また、 Google SWE の面接においては、マイナーな知識は要求されません。例えば、グラフ理論において、エドモンズの花アルゴリズムのようなマイナーな知識は要求されません。フォード・ファルカーソンのアルゴリズムも要求されません。ダイクストラ法も要求されません。幅優先探索は要求されます。深さ優先探索も要求されます。知識レベルとしては、そのあたりまでが要求されると思うと良いと思います。ただ、ダイクストラ法は、書けなくても大丈夫ですが、存在くらいは知っておいた方が良いと思います。

過去に、 GoogleSWE で、入社試験においてフォード・ファルカーソンのアルゴリズムが出題されたという情報を公表した方がいらっしゃいました。実際に、フォード・ファルカーソンのアルゴリズムが最適解となる問題が出題されたことはあるようです。ですが、出題者がその問題において要求しているポイントはまったく異なっており、小さなデータセットに対し、全数精査のシンプルなソースコードで答えを出力できれば十分、というものだったようです。このような問題に対し、データセットの大きさも考えずにフォード・ファルカーソンを適用しようとするのは、明らかなオーバーエンジニアリングです。保守の面等を考えても好ましくありません。

Google の面接の問題の種類

Google SWE の面接においては、

  • コーディングクイズ
  • 知識を吐き出す系
  • Open-ended question
  • システムデザイン

の 4 種類の問題が出題されます。

コーディングクイズ

コーディングクイズは、○○を行うプログラムを書いてください、というお題が出題され、それに対してソースコードを記述するという種類の問題です。問題を正確かつ素早く理解する能力、曖昧な問題から足りない条件を見つけ、面接官に相談しながら詳細を詰める能力、すばやく正確なコードを書く能力が求められます。また、面接官からのバグや改善点の指摘に対し、その内容を理解し、適切にコードを修正したり、口頭で説明したりする能力が求められます。さらに、書いたソースコードに関連する、コンピューターサイエンスに関する質問が投げられ、それらに対して適切に答える能力が求められます。この問題形式は、 SWE のお仕事のうち、実装とコードレビューの仮想体験となっています。

例: クイックソートアルゴリズムを書いてください。クイックソートの時間計算量は何ですか? どのようなときに平均計算量になりますか? どのようなときに最悪計算量になりますか? ピボットはどのように選びますか? 再帰をする場合、どのようなことに気を付けますか? 定数倍高速化したい場合、どのような工夫をしますか?

知識を吐き出す系

知識を吐き出す系は、○○について述べてください、というお題が出題され、それに対して知っていることを口頭でひたすら答えるという種類の問題です。コンピューターサイエンスについての、幅広い知識が求められます。ソフトウェアの開発経験などが役立つ場合も多々あります。この問題形式は、設計からテストに渡る広範囲に必要な知識の確認となっています。

例: パソコンの電源ボタンを押してから、起動して使えるようになるまでに起きていることを説明してください。

Open-ended question

Open-ended question は、 Yes/No では答えられない質問に対し、自由回答形式で答えるという種類の問題です。こちらも、コンピューターサイエンスについての、幅広い知識が求められます。この問題形式も、設計からテストにわたる広範囲に必要な知識の確認となっています。

例: 変数を print したらバグが直りました。何が起こっていると考えられますか?

システムデザイン

システムデザインは、○○を設計してください、というお題が出題され、○○を設計し、その内容について口頭で説明するという種類の問題です。インフラやフレームワーク、ツールなどの知識や使用経験、ソフトウェアの開発経験が役に立ちます。この問題形式は、 SWE のお仕事のうち、設計の仮想体験となっています。

例: Twitter を設計してください。

これらの種類の問題は、複合的に出題される場合もあります。

Google の面接の評価基準と対策方法

Google SWE の面接の評価基準は、面接官によって少しずつ異なります。おそらく共通しているであろう基準は、応募者が GoogleSWE の常識を身につけているかどうかです。

GoogleSWE の常識は、知識・技能・マインドセットといった要素に分解することができます。

知識

知識面については、大学の情報系の学部の授業の全範囲をカバーしていることが求められます。具体例として、コンピュータ科学カリキュラム CS2013 が挙げられます。大学で情報系の学部で授業を受けていない場合、専門書等で知識を補完する必要があります。

対策として、大学で情報系の学科に所属している方は、できるだけ多くの授業を履修しましょう。そして、授業を真面目に受けましょう。情報系の学科に所属していない学生は、情報系の授業を聴講しましょう。それ以外の方は、東大の情報科学科のカリキュラムを把握し、そこで挙げられている教科書等を読みましょう。それらのうち、特に現代の大規模 web 開発につながる分野について学ぶには、以下のブログエントリで紹介されている本を、一通り読みましょう。

nuc.hatenadiary.org

  • Twitter で医師を拾ってきて Google のソフトウェアエンジニアにするだけの簡単なお仕事 - 白のカピバラの逆極限 S.144-3 

上記を一通り読むことで、大学の情報系の学部の授業のある程度の範囲をカバーできると思います。

ただし、 nuc さんらによると、プログラミングコンテストチャレンジブックはチョイスが悪かったそうです。代わりに以下の本をお勧めするとのことです。

www.kindaikagaku.co.jp

www.kindaikagaku.co.jp

www.kindaikagaku.co.jp

nuc さんが、クイックソートアルゴリズムの詳細について Google SWE および卒業者に聞いたところ、ほぼ全員が答えられた範囲がありました。これらは Google SWE の面接の出題範囲だと考えられます。これらを説明しているのが、上記の本なのだそうです。

技能

技能面については、 LeetCode の Medium レベルの問題を初見で 10 分程度で解けるコーディング能力・アルゴリズム能力が求められます。ただし、面接においては、コーディング問題に対して解答ソースコードを書くだけではなく、ソースコードの内容に関連する様々な質問に対し、口頭で答えていかなければなりません。これらの質問に答えるためには、コンピューターサイエンスの知識を応用する必要があります。

具体例として、以下の問題が挙げられます。

leetcode.com

この問題は、練習会で模範演技としてサークルメンバー 3 名が解き、いずれも 10 分以内に書き上げることができました。

対策として、以下の LeetCode の問題集を一通り解くことをおすすめします。

1kohei1.com

leetcode.com

neetcode.io

まず、上記の問題を一問ずつ解いてみてください。そして、一問解いたら、ソースコードを消し、再度解き直してみてください。解き直すとき、よりシンプルに、より速く書けるよう意識してみてください。これを、納得できる速度がでるまで繰り返してください。ソースコードを丸暗記してしまっても構いません。九九の暗唱の練習や、掛け算の筆算の練習のように、意識しなくても体が勝手に動くようになるまで、何度も何度も繰り返してください。最終的に、難易度 Medium の問題を、初見で 10 分程度で解けるようになれば、十分だと思います。

念のため補足すると、上記の練習方法の目的は、解答のソースコードを丸暗記することではありません。目的はコードスニペット、すなわちソースコードの断片の記述を速めることです。しかし、これだけでは解ける問題の幅が広がりません。解ける問題の幅を広げるには、色々な問題に挑戦し、解法を考え、解法を考え方の部品へと分解し、自分の中に収め、自由に引き出し、自由に組み合わせられるようにしていく必要があります。

ただし、 LeetCode のようなオンラインジャッジでは、どうしても取り扱えないような範囲もあります。例えば、乱択アルゴリズム等ランダム性のあるプログラム、非同期処理を扱うプログラム、マルチプロセスを扱うプログラム、ソケットプログラミング等です。これらについては、大学の授業等で技術を学んだあと、それらを使ったプログラムを自分で作成し、理解を深めると良いと思います。

マインドセット

マインドセットは 2 つに分けられます。

1 つ目は、ユーザーに対し、過不足なく、ユーザーのためになるものを提供しようとする姿勢です。 SWE の目的は、ユーザーのためになるものを提供することです。この目的を意識できていないと、本来行うべき言動とずれた言動をしてしまい、面接においても高い評価を得にくくなってしまいます。

2 つ目は、面接官を同僚とみなし、フラットに話せるかどうかです。これについては後述します。

残念ながらマインドセットについては、明確な訓練方法が確立されていません。少なくとも、自分を客観視するメタ認知能力、行動と目的を一致させることができる能力が必要だと思います。これらについては、模擬面接を通し、模擬面接官からのアドバイスをもとに、自らの意識を変えていくしかないと思います。

Google の面接のタブー

Google の面接には、決して侵してはならないタブー (禁忌) があります。それは、差別・ステレオタイプ・偏見を含む発言です。

Google の面接において、人種・性別・年齢・病歴・宗教・言語・国籍・来歴等について、差別的な発言、偏見を持っていると判断されるような発言をした場合、面接の他の部分の評価がどんなに高くても、一発で不合格になります。大抵の人は、自分は差別的な発言などしないと思っているようです。ところが実際のところは、無意識のうちに、外見から人種、言語、職業などを判断しがちです。

例えば、日本で面接を受け、試験官として外国人のように見える方が現れ、ネイティブ並みの日本語を話されたとき、「日本語お上手ですね」と褒めると、差別となります。理由は、相手の国籍や来歴が分からない状態で言ってしまっているためです。仮に試験官が日本生まれの日本育ちだとしたらどうでしょうか? 顔つきなどから勝手な憶測をしていた、ということになります。

差別的な発言は、同僚に対して不快感をはじめとしたネガティブな感情をもたらします。そのような状態においては、ユーザーのために何かを提供することは難しいでしょう。また、 Googleアメリカ西海岸に本社を置く会社です。アメリカ西海岸においては、面接において、面接官が差別的な発言をすると、裁判を起こされます。裁判を起こされると、その会社のイメージダウンにつながります。そのため、面接官になる Googler は、面接官になるためのトレーニングにおいて、差別的な発言をしないよう教育されます。もちろん、応募者側も決してやってはいけません。

発言する際は、相手にどのように聴こえるか考えながら発言しましょう。ただ、常に考えながら発言するのは、難しいと思います。うっかり差別的な発言をしないようにするための指針として、相手が開示した情報から直接推測できる事柄のみ話す、というものがあります。

先の例で言うと、相手が「18 歳までドイツで暮らしていたんですよ。」といったことを言ってきた場合は、「じゃあ、ドイツ語話せるんですね。」といっても問題ありません。これは、相手の来歴が分かった状態で話しているためです。

Google の面接の心構え

Google SWE の面接において持っておきたい心構えを 5 つ挙げます。

面接官への話し方

1 つ目は、面接官への話し方です。面接官に対しては、同僚に話しかけるようにフラットに話しかけましょう。

応募者の中には、面接でガチガチに緊張し、敬語謙譲語尊敬語の固い話し方をしてしまう人がいます。人によっては、刑事に尋問を受けているかのような、教授に試問されているかのような、委縮した状態で受け答えをしてしまいます。

Google SWE の入社試験は、 GoogleSWE のお仕事の仮想体験です。この仮想体験を通して、 SWE の目的である、ユーザーのためになるものを提供できる人間かを見定めています。ユーザーのためになるものを提供するには、ユーザーのほうを見て、ユーザーをつぶさに観察し、何を欲しているのかを見定める必要があります。ところが、上記のような受け答えをしている人は、話している相手のことばかり見ており、ユーザーのことを見ることができていません。これでは、ユーザーのためになるものを提供することは難しいでしょう。

同僚は、一緒にユーザーのためになるものを提供するための存在です。一緒にユーザーのためになるものを提供したいという気持ちを持ちながら話しかけましょう。軽く、弾むような会話になるのが理想的です。

話す量

2 つ目は、話す量です。面接官と同じか、それ以上話しましょう。

再度繰り返しになりますが、ソフトウェアエンジニアリングの目的は、ユーザーのためになるものを提供することです。そのためには、同僚同士が意見を出し合い、意見をブラッシュアップしていく必要があります。ところが、こちらが話しかけても、はいとかいいえとか最低限のことしか返さず、全然話さない同僚がいたらどうでしょうか? おそらく、良い意見が出にくくなり、意見のブラッシュアップもしにくくなってしまうのではないかと思います。特に面接で仮想体験するシチュエーションは、困っている同僚があなたに助けを求めているという状況です。そのような状況では、応募者のほうがたくさん話すほうが自然だと思います。

また、 Google SWE の面接においては、面接官は、レポートに応募者の発言内容を、ほぼすべて書き出します。これは、応募者の良いところをなるべく汲み取り、採用に向けて推したいからです。もし応募者の話す量が少なかった場合、いくら推したくても、レポートに書ける分量が足りず、推すことが難しい、といった事になってしまいます。

ただし、 9 割 5 分まで話すと、話しすぎです。仕事場で隣の席の人が、ずっと話しっぱなしだったら、と想像してみてください。こちらの意見を出しにくくなってしまうのではないかと思います。話す分量は 6~7 割を意識しましょう。

エリート意識

 3 つめは、エリート意識です。これを読んでいる皆様の中で、「俺は〇〇だぞ」といった、自負を持っている方はいらっしゃいませんでしょうか?

エリート意識を持つ方は、無意識のうちに、自分がエリートであることを匂わせる言動をしがちです。ところが、これらの言動は、 SWE の本来の目的である、ユーザーのためになるものを提供することに、まったく関係ありません。結果として、本来 SWE がとるべき言動から、ずれた言動をしてしまいがちです。 Google の面接官は、この辺りを嗅ぎ取る嗅覚に極めて優れています。自分がエリート意識を持っていないかどうか認識し、持っているのであれば改善しましょう。

自己愛

 4 つ目は、自己愛です。自己愛とは、自分の能力を過大評価する、注目や賞賛を求める、自分の業績を誇張することを言います。

私は、 2021 年に開催された、競プロ忘年会 in 東京 2021 に参加させていただきました。その懇親会において、初対面の方から「はじめまして、俺黄色コーダーなんですけど」と言われました。

黄色コーダーは、競技プログラミングサイト AtCoder で、上位 1% 程度の能力を持つことを表します。黄色コーダーを初対面の挨拶において、冒頭に持ってきたのは、注目や称賛を求めているため、自分の業績を誇張しているためなのではないかと思います。

こういった方は、無意識のうちに、自分の能力を過大評価する、注目や賞賛を求める、自分の業績を誇張する言動をしがちです。これらの言動も、 SWE の本来の目的である「ユーザーのためになるものを提供する」ことにまったく関係ありません。結果として、本来 SWE がとるべき言動から、ずれた言動をしてしまいがちです。自分が自己愛を持っていないかどうか認識し、持っていれば改善しましょう。

優秀さ、知識量に対するこだわり

5 つ目は、優秀さ、知識量に対するこだわりです。これを読んでいる人の中には、自分や他人が優秀であるかどうかにこだわったり、知識量がその人の格を表す、といった考えを持っている人がいらっしゃると思います。これらの人は、面接において、シンプルな解答が求められているにもかかわらず、わざと小難しい解答をしようとする場合があります。これは、自分が優秀であることや、自分が博識であることを相手に示そうとするために起こる現象だと思います。結果、求められている解答をすることができず、面接の評価が上がらない場合があります。仮に合格して SWE として働き始めたとしても、 SWE のお仕事において、同様の理由で大きな障碍になるのではないかと思います。自分が優秀さ、知識量に対するこだわりを持っていないかどうか意識し、持っているのであれば改善しましょう。

Google の面接のテクニック

Google SWE の面接には、いくつかテクニックがあります。ただし、それらのテクニックは、面接のみに限らず、実際の仕事でもしばしば使われます。是非覚えて仕事に役立てましょう。以下では 5 つ挙げます。

入力条件を確認する

1 つ目は、出題された問題の入力条件を確認するというものです。コーディングクイズが出題されたら、入力データの最小サイズ、最大サイズ、入力データの種類を確認しましょう。入力データが文字列だった場合、文字の種類も確認しましょう。英大文字のみ、 ASCII 全体、 UTF-8エンコーディングされているかどうかによって、コーディングの難易度に大きな差が出ます。また、システムデザインの問題が出題されたら、どれくらいの数のユーザーを想定するのか、どのくらいの規模を想定するのかを、必ず聞きましょう。

上記は、 SWE が仕事として日常的に行っていることではないかと思います。例えば、サーバーを 1 台立てる事になったとき、ユーザー数、単位時間当たりのリクエスト数、 1 リクエストあたりのデータサイズ、 1 リクエストあたりの処理時間、 1 リクエスト当たりの処理負荷等を考え、サーバーが負荷に耐えられるかどうかを検討すると思います。本テクニックは、この作業の仮想化となっています。

入力の条件を簡単にできるか交渉する

2 つ目は、出題された問題の入力の条件を簡単にできるか交渉するというものです。例えば、入力データが文字列だった場合、含まれる文字が英大文字のみで良いか交渉してみましょう。交渉の結果、英数字すべて含めることになるかもしれませんが、交渉ができる事を示す事ができたという点は、プラスの評価につながると思います。また、システムデザインの問題が出題された場合でも、最初は非常に限られたユーザー数、限られた規模から設計を始めて良いか、交渉してみましょう。

上記も、 SWE が仕事として日常的に行っていることではないかと思います。例えば、入力として csv ファイルを受け取るようなシステムを考えてみましょう。また、普通はライブラリーを使用しますが、何らかの理由により、自分でパーサーを実装することになった場合を考えてみましょう。 csv ファイルは、 RFC 4180 において、フィールドはダブルクォーテーション (") で囲んでも囲まなくてもよいとしています。また、改行 (CR+LF)、カンマ (,)、ダブルクォーテーションを含むフィールドは、ダブルクォーテーションで囲むべきであるとしています。さらに、フィールドがダブルクォーテーションで囲まれている場合、フィールドの値に含まれるダブルクォーテーションは、その直前にダブルクォーテーションを付加して、エスケープしなければならないとしています。これらを自力で実装するのは、骨が折れます。そのような場合、入力として与えられる csv ファイルに、ダブルクォーテーションが含まれていないことを仮定してよいか、交渉するのではないかと思います。交渉の結果、ダブルクォーテーションなしでよいということになれば、作業がだいぶ軽くなります。本テクニックは、この作業の仮想化となっています。

テストケースを作って提示する

3 つめは、コーディングクイズにおいて、コードを書き上げたあと、テストケースを作って提示するというものです。複数のテストケースを作成して構いませんので、すべてのコードパスを通るようなテストケースを提示し、自分のコードが正しく動くことを示しましょう。

Google においては、ソースコードをレポジトリーにチェックインする際、単体テストも一緒に書いてチェックインします。その際、単体テストに含めるテストケースは、基本的にはソースコードを書いた本人が考えます。本テクニックは、この作業の仮想化となっています。

関連する知識を答える

4 つ目は、聞かれた質問の答えが分からなかった場合に、関連する知識を答えるというものです。例えば、 通信プロトコル QUIC について聞かれ、 QUIC の中身が分からなかった場合、「QUIC の中身は分からないのですが、 HTTP/1.1 なら分かります。」と答えます。ある種の逃げ方ともいえるでしょう。

Google の中でシステムを構築する際、様々な内製のフレームワークやツールを使用します。外から入ってきた人にとっては、そのほとんどが初めて見るものなのではないかと思います。そんなとき、外でしばしば使用されている似たようなフレームワークやツールの使用経験があると、より早く適応できるようになると思います。本テクニックは、そういった適応力があることを示すためのものだと思います。

正しく修正する

5 つ目は、応募者が間違った発言をして、面接官が聞き返してきたときに、正しく修正するというものです。人間は 1 時間もしゃべっていれば、必ず間違った発言をするものです。そんなとき、面接官は、いかにも「いまあなたは間違った発言をしましたよ」という雰囲気を醸し出しながら、聞き返してきます。その時に、自分が間違った発言をしたのだと認識し、正しく修正できれば大丈夫です。

上記は、日常会話の中でもしばしば行われるやりとりだと思います。例えば、「俺この前ネトフリでシン・仮面ライダー見たんだけどさぁ」「え? シン・仮面ライダーってもうやってるの?」「あ、ごめん、シン・ウルトラマンだった。」のようなやりとりは、ごくごく普通にありえると思います。応募者の中には、間違った発言をした際、間違ったことに対して、大きなペナルティになると勘違いをしてしまう方がいらっしゃいます。実際には、決してそんなことはなく、間違いに気づき、正しく修正できればまったく問題ありません。

一番まずいのは、間違いを間違いのまま押し通そうとすることです。仮に SWE のお仕事で、間違った内容を押し通し、それがもとで他の SWE に対して迷惑を掛けたり、巡り巡ってユーザーに対して被害を出す事になったらどうでしょうか? 間違いに気づき、正しく修正できれば、そのような被害は未然に防げたかもしれません。

以上が、 Google SWE の面接におけるテクニックになります。これらは、 SWE のお仕事の中でも活用できるものです。是非意識してみてください。

競技プログラミングGoogle の面接

最近、 SWE になるために、競技プログラミングを勉強している、または競技プログラミングによる勉強を勧めている、という話をよく聞くようになりました。やや逆説的ではありますが、競技プログラミング同好会競技就活部門では、競技プログラミングによる勉強はおすすめしておりません。

近年の競技プログラミングでは、各プレイヤーの競技プログラミングの強さを、レーティングという数値で表現します。レーティングは、コンテストの成績が良いと上がり、悪いと下がります。一部には、レーティングが上がることで喜びを覚えたあまり、レーティングを上げるために価値観と行動を最適化してしまう人がいます。

競技プログラミングは、算数オリンピック・数学オリンピック情報オリンピック・コンピューターサイエンスの中の分散的な雑学の中から、組み込んだときに面白くなるような知識の断片を、つなぎ合わせて作られたゲームです。このため、競技プログラミングに特化し、レーティングを上げるための勉強だけをした場合、知識に漏れが生じ、最低限知っておくべき範囲をカバーできなくなります。情報オリンピックのメダリストやレッドコーダーが落とされている理由の大半がこれでしょう。自分たちが覚えたものが、専門分野の断片しかとらえていないことを認識し、専門分野の広い範囲を、網羅的かつ体系的に勉強するべきです。

競技プログラミングで出題される問題は、計算量を最適化することによって正解できるものが多いです。そのため、計算量を最適化することが最も価値があることだ、という価値観を持ってしまう人がいます。その結果、計算量が最適でなくても、ユーザーに対して十分なものを提供できるにもかかわらず、常に過剰に計算量を最適化しようとしてしまったりします。その結果、簡単な方法で十分にもかかわらず、複雑な方法にこだわってしまう場合があります。計算量が最適でなくても、シンプルな実現方法でユーザーに対して十分なものを提供できるのであれば、そちらを選択するべきです。また、計算量が最適だからといって、メモリーアクセスパターン等の理由から、必ずしも十分に速いとは言えない場合もあります。

競技プログラミングにおいては、ソースコードの書き方に非常に強い癖が出る場合があります。典型的なソースコードを以下に示します。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,l,r) for(int i=(l); i<(r); ++i)
#define rrep(i,l,r) for(int i=(r)-1; i>=(l); --i)
using vi = vector<int>;

int N, M, K;
int dp[10005][10005];

signed main() {
  ...
}

競技プログラミングにおいては、ソースコードの提出が早ければ早いほど、成績が良くなります。そのため、可読性を無視したソースコードを書きがちです。とくに、変数名に一般的ではない略語を付けて過度に短くしたり、独自のマクロを多用したり、大文字 1 文字の変数名を多用したりします。一方、ソフトウェアエンジニアリングにおけるソースコードは、 1 度書くと、自分または他の SWE によって、将来複数回にわたって読まれます。このとき、可読性を無視したソースコードは、読むにあたって大きな認知負荷がかかります。それは時間、ひいては人件費に跳ね返ってきます。これらは決して褒められたものではないと思います。ソフトウェアエンジニアリングにおいてソースコードを書く場合は、チームの平均的なメンバーが最短で正確に意図を理解できるように書き、読む際の認知負荷を減らすべきです。

他によく見る例として、コードを書くにあたって、グローバル変数を濫用するというものがあります。競技プログラミングにおいては、様々なメリットから、グローバル変数が使用されます。理由として、以下が挙げられます。

  • 自動で初期化されるため、記述量が少なくて済む。
  • 各種コンテナと比較し、多次元配列でも取り回しやすい。
  • non-static なローカル変数と比較して、大きなサイズの配列を確保しても、スタック領域があふれることがない。

一方、ソフトウェアエンジニアリングにおいては、グローバル変数は、様々な理由から避けるべきだとされています。理由として、以下が挙げられます。

  • external linkage となる事も含め、グローバル名前空間を汚す。
  • 生存期間が必要以上に長い。
  • 複数個所から参照される場合、コードの流れを追いにくくなる。
  • 想定外の場所で値が変更される場合がある。
  • マルチスレッドプログラミングにおいては、スレッド同期を適切に取らないと、スレッド競合を引き起こす。
  • 複数回呼んだ時に、適切に初期化しないと、毎回計算結果が変わる。

これらのデメリットを知らないまま、面接において競技プログラミングの要領でグローバル変数を濫用し、評価を下げてしまう人がいます。面接においては、仕事で書くコードを意識し、一般に避けるべきとされる書き方は避けるべきです。

また、根本的な問題として、競技プログラミングソースコードにはユーザーがいません。サーバーが機械的に実行し、正解かどうかを判定するだけです。そのため、ユーザーのためになるものを提供するという意識が、まったく養われません。

SWE のお仕事との共通部分は、 1 割程度しかないと思います。その 1 割の部分も、実装・デバッグ・テストのさらにほんの一部にすぎず、 AtCoder Beginner Contest でいう A・B 問題程度の内容がほとんどです。競技プログラミングの問題の難しさという観点において、 A・B 問題より難しいコーディングやアルゴリズムが必要となることは、ほとんどありません。 SWE のお仕事の難しさは、実装・デバッグ・テスト以外、すなわち、需要を見つけられるか、問題を発見できるか、何を作るか、どのように作るか、どのようにユーザーに提供するか、結果をどのように計測するか、どのように維持するか、といったところにあります。

競技プログラミングで勉強すれば SWE になれるという誤解があまりにも広まったためか、 Google 公式サイトには以下の文章が掲載されています。

Q: 面接における質問は競技プログラミングでの質問と同じですか?
A: いいえ。コーディングに関する質問もありますが、他の様々な質問も行います(例:API デザイン、プロダクトデザイン)。面接の目的は、問題解決能力とプログラミングスキルを確認することにあります。詳細はこのサイト(英語)とビデオ (英語)を参照してください。

ある Google SWE は、以前、「競技プログラミングは、 Google SWE の面接に対し、タイピングゲームの練習程度には役に立つ」とおっしゃっていました。個人的には、もう少し役に立つかなという感覚です。

別の Google SWE は、「エンジニアになるために競技プログラミングをするのは、 DJ になるためにビートマニアをするようなものだ」とおっしゃっていました。競技プログラミングビートマニアも、きっかけとしてはとても良いと思います。ですが、本職になるためには、専門の勉強と訓練が必要になります。

以上の理由から、SWE になるために競技プログラミングで勉強することは、おすすめしません。また、競技プログラミングをプレイする際は、競技プログラミングがゲームであるという認識を持ち、楽しむために割り切ってプレイされることをおすすめします。

十分なコーディング能力があれば、コーディングクイズ対策のためのコーディング練習は必要ありません。ですが、もしするのであれば、 LeetCode の良問集をおすすめします。ただし、 LeetCode には、企業の面接で実際に使われた問題がリークしているとされています。 LeetCode への問題の投稿は、応募者と各社との間で結ばれた秘密保持契約 (NDA) に反する行為です。このため、 LeetCode を使用することに倫理的な抵抗感がある方もいるでしょう。とはいえ、 LeetCode を用いて勉強する人としない人とでは、パフォーマンスに大きな違いが出てしまうと思います。また、 GAFA+M のリクルーターの中には、応募者に LeetCode での練習を勧めている方もいますし、 Amazon は LeetCode のスポンサーをしています。個人的には、 LeetCode は必要悪とみなし、勉強するために割り切って使用することをお勧めします。

おわりに

Google SWE の入社試験は、天才認定試験ではありません。秀才のみが合格する試験でもありません。誤解を恐れずに言えば、普通のエンジニアが合格する試験です。ただし、それなりの勉強量は必要となります。とはいえ、その勉強量も高校化学 (+高校物理) の全範囲と同じ程度の分量です。この記事を読まれている方の中には、過去にそれくらいの勉強量をこなしてこられた方が少なからずいらっしゃるのではないかと思います。

この記事を読んでくださった方が、 Google SWE の入社試験が、遥か天上界の高みにあるものではなく、いま地上に立っている自分と、地続きの場所に存在しているものだ、という感覚を持っていただけたのであれば幸いです。

最後となりますが、告知をします。社会人サークル「競技プログラミング同好会競技就活部門」では、 2023 年 3 月 12 日に外資 IT 入社試験練習会を開催します。元 Google SWE に直接指導・フィードバックしてもらえるチャンスです。詳細は以下の通りです。

日時: 2023 年 3 月 12 日 13:00~

場所: 〒101-0061 東京都千代田区神田三崎町3-6-15 東京学院ビル 本館 3F教室

内容: SWE 入社試験の面接対策・指導

費用: 無料

無料で行っている理由は、前職の知見を使って行っている都合上、有料で行うと商売の道義上問題があると考えているためです。

ご希望の方は奮ってご参加ください。皆様のご参加お待ちしています。

 

一般財団法人『高IQ者認定支援機構』の高域知能検査『CAMS』

このエントリは、2020年7月5日に受験した、一般財団法人『高IQ者認定支援機構』の高域知能検査『CAMS』の体験談です。試験のヒントやネタバレは極力しないようにしたつもりです。万が一まずい表現を見つけられた方がいらっしゃいましたら、  nodchip@tanuki- (@nodchip) | Twitter までご一報ください…。

CAMSを受けたきっかけ

ある日、TwitterでたまたまCAMSの簡易版を見かけ、試しにやってみました。簡易版で出題された問題は、普段よく目にするIQテストの問題に比べワンランク難しく、とても印象に残りました。また、簡易版の結果が、過去にプレイしたWEB IQテストに比べてかなり良く、驚きました。

 これを受けて、本試験も受験しようと思いました。

第6回CAMS本試験

2020年7月5日の第6回CAMSの本試験の日、頭脳を酷使するだろうと思い、朝は糖分の多い食事を摂り、お昼にレッドブルを飲んでから向かいました。

少し早く着いたのですが、すでに何人か会場にいらっしゃいました。どの人からも頭が良さそうなオーラが出ており、気圧されてしまいました。

ふと気づくと、知り合いがいました。競技プログラミングで何度かお会いしたことのある方でした。「お久しぶりです。○○さんですよね?」といった軽い挨拶を交わしたような気がします。

試験が行われる部屋に入り、割り当てられた席が…、ありませんでした…。受験予定者数に対し、テーブルが足りていなかったのです…。運営側の手違いでしょう…。おっちょこちょいな運営だなと、ちょっと和みました。

受付をしました。受付テーブルに座っていらっしゃったのは幸田さんご本人!モンペのような服を着てニコニコしていらっしゃいました。受付の際、思わず「本物ですか!?」と声をかけてしまいました。爆笑されてしまいました。

写真撮影です。自分は写真撮影がどうも苦手です。必ず顔と目が斜めを向いてしまうのです。なるべく顔が斜めを向かないよう、そして目も斜めを向かないよう、いつも斜めを向いてしまう方向とは逆の方向を意識して撮影しました。斜めを向きすぎました。

試験時間がやってきました。試験用紙が配られます。そして、試験の形式の説明と諸注意がありました。試験の形式を聞いて焦りました。想像していたものと全く違う形式だったのです。同じように焦った人が他にもいたに違いありません。

試験が始まりました。見た瞬間分かる問題もあるのですが、ぱっと見では何が何だか全く分からないもののほうが多かったです。各問題を解いたときの感想をいくつか挙げると、

  • 分かるか~~~~~~~~っっっっっっっ!!!!!
  • こ… これでいいのかな… 自信ない…
  • と… 解けた… なんで自分この問題解けてるの…
  • 分からん… (あきらめて別の問題に挑戦する) (元の問題に戻ってくる) 分からん… (あきらめて別の問題に挑戦する) (元の問題に戻ってくる) 分からん… (あきらめて別の問題に挑戦する) (元の問題に戻ってくる) これがこうなればこうなんだけどなぁ… あ… あ゛あ゛あ゛あ゛あ゛あ゛あ゛あ゛あ゛あ゛あ゛あ゛あ゛あ゛あ゛!!!!!!!!!!!!!
  • はい典型~… (←競技プログラミング脳) 典型…? て・ん・け・い…? て゛~~~~~~ん゛~~~~け゛~~~~~~い゛~~~~~~~~~~~う~~~ぼ~~~~ぁ~~~~~~~~~~
  • ぎゃあああああああああ!!!!!!! これこういう意味だったのか!!!!!! 30分前の自分の馬鹿野郎ーーーーーーー!!!!!
  • あ… これ見たことある… むしろ遊んだことある…
  • いや… 分かるよ… 分かるんだよ… ただね… ひたすら面倒なんじゃ~~~~~~!!!!!
  • IQだ~!!!!! IQだ~!!!!! IQだ~!!!!!
  • え… それでいいの…?
  • (試験時間残り数分) 疲れたよ… あ… あ… あ… あ… あ… あ… あ… なんでよりにもよってこのタイミングで分かるの…(;_;) 疲れたよ~(;_;) あと数分しかないよ~(;_;) 頭働かないよ~(;_;) うわぁぁぁぁぁぁぁんんんんんん~(;_;)

といった感じでした。テンションMAXになっていたことが伝わるかと思います。

 結果

約1か月後、結果が返ってきました。

望外の結果に本気で驚きました。

終わりに

このエントリを見て、ひとりでも多くの方にCAMSに興味を持っていただければ幸いです。また、CAMSはIQを計測するための試験のではあるのですが、あまり難しく考えず、謎解きゲームや、パズルゲームの感覚で気軽に参加されることをお勧めします。

www.hiqa.or.jp

ユーザーモードダンプを収集する

将棋所で対局中に思考エンジンがクラッシュした場合の原因を調べたいとき、ユーザーモードダンプを収集するように設定しておくと、クラッシュ時に自動的にユーザーモードダンプを特定のフォルダに保存してくれる。メモリダンプはVisual Studioのファイルから開くことで、デバッガ経由で実行してブレークポインタで止めたときのようにデバッグすることができる。
ユーザーモードダンプの設定はレジストリの HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\Windows Error Reporting\LocalDumps から行う

  • DumpFolder
    • ユーザーモードダンプを保存するフォルダパス
    • デフォルトは %LOCALAPPDATA%\CrashDumps
  • DumpCount
    • ダンプを保存する最大数
    • デフォルトは 10
  • DumpType
    • ダンプの種類
    • 0はカスタムダンプ CustomDumpFlagsでダンプする種類を指定する
    • 1はミニダンプ デフォルトはこれ
    • 2はフルダンプ ヒープメモリの内容も全て保存される
  • CustomDumpFlags
    • DumpTypeに0を指定した時のダンプの種類を指定する
    • MINIDUMP_TYP列挙の値のorを指定する

リンク

コンピュータ将棋で学ぶ組み込み関数(intrinsic)入門

はじめに

この記事はコンピュータ将棋 Advent Calendar 2016 25日目の記事として書かれたものです。
内容は tanuki- WCSC26 版以降に実装されているKPPT評価関数のAVX2による高速化についてです。C91 で頒布予定の『コンピュータ将棋 2016年度課題技術総復習』の内容を一部抜粋・加筆・修正したものになります。
コンピュータ将棋 Advent Calendar 2016 へのリンクはこちら http://www.adventar.org/calendars/1457

AVX2を用いた評価関数の高速化

 NPSはコンピュータ将棋ソフトにとって重要な要素の一つです。これはNPSがN%上がるとレーティングが2×N程度向上すると言われているためです。このため多くの開発者がコンピュータ将棋ソフトの高速化に挑んでいます。
 コンピュータ将棋ソフトの処理時間の30%〜40%は評価関数が占めています。そして評価関数の処理時間のほとんどを評価値配列から評価値をCPUのレジスタにロードする部分が占めています。この部分を高速化することでレーティングの向上を期待することができます。
 近年のIntel製CPUにはAVX2拡張命令という命令が実装されています。これはYMMレジスタと呼ばれる256ビット長のレジスタに、複数の整数・浮動小数を格納し、それらに対して同時に演算を行うことができるという命令です。これらの命令はSIMD (Single Instruction Multiple Data)命令とも呼ばれています。
 評価関数は駒リストを用いて評価関数配列を参照し、それらの値を足し合わせるという処理を行っています。この処理はAVX2拡張命令を用いて高速化することができます。以下ではAVX2拡張命令を用いた高速化について解説していきます。
 今回使用するAVX2拡張命令の中で最も重要な命令がVPGATHERDD命令です。この命令は入力としてメモリアドレスと要素のインデックスが格納されたYMMレジスタを受け取り、出力レジスタの各要素にメモリアドレスにインデックスを加えた位置にある要素をロードするというものです。この処理はギャザーと呼ばれています。この処理をC++風の擬似コードで表現すると以下のようになります。

void vpgatherdd(int dest[8], const int* base_addr, int vindex[8]) {
  for (int i = 0; i < 8; ++i) {
    dest[i] = base_addr[vindex[i]];
  }
}

 VPGATHERDD命令を始めとしたVPGATHER**命令はIntel Broadwellアーキテクチャ及びSkylakeアーキテクチャで高速化されたとされています。この命令を利用して評価関数のメモリから評価値をロードする部分を中心に高速化してみましょう。
 CPUに実装されている命令をC++から使用する場合、一昔前はインラインアセンブラを使うしかありませんでした。一方、近年は組み込み関数(intrinsic)を使う方法が広まっています。今回は組み込み関数を使って実装していきます。
組み込み関数を使う際はCPUのレジスタに対応した特別な構造体と、組み込み関数と呼ばれるCPUの命令にほぼ1対1に対応した関数を使用します。
 Intel製CPUのYMMレジスタに対応する構造体は以下の3種類です。

  • __m256
  • __m256d
  • __m256i

 __m256は32ビットの浮動小数を8個、__m256dは64ビットの浮動小数を4個保持することができます。__m256iは8ビットの整数なら32個、16ビットの整数なら16個、32ビットの整数なら8個、64ビットの整数なら4個格納することができます。今回は__m256iを主に使用していきます。一部XMMレジスタに対応した__m128i構造体も使用します。
 今回使用する組み込み関数は以下の通りです。

// 値を0に設定したYMMレジスタを返す
__m256i _mm256_setzero_si256();

// aから連続する32バイトのデータをロードしてYMMレジスタに格納する
// aは32バイトでアラインメントされてなければならない
// VMOVDQA命令に相当する
__m256i _mm256_load_si256(__m256i const *a);

// 指定されたベースアドレス、インデックス、スケールを用いてメモリから
// 8つの32ビット整数をギャザーする
// VPGATHERDD命令に相当する
__m256i _mm256_i32gather_epi32(int const *base, __m256i vindex, const int scale);

// aの下位128ビットまたは上位128ビットを対象のXMMレジスタに格納する
// VEXTRACTI128命令に相当する
__m128i _mm256_extracti128_si256(__m256i a, const int offset);

// 8つの16ビット符号付き整数を32ビット整数に変換する
// VPMOVSXWD命令に相当する
__m256i _mm256_cvtepi16_epi32(__m128i s1);

// 8つの32ビット符号付き整数同士を加算する
// VPADDD命令に相当する
__m256i _mm256_add_epi32(__m256i s1, __m256i s2);

// 指定された分だけバイト要素を右へ論理シフトする
// VPSRLDQ命令に相当する
__m256i _mm256_srli_si256(__m256i s1, const int count);

 これらの組み込み関数を利用して、前節のKPPT評価関数を高速化してみましょう。以下のコードは玉が移動した場合の差分計算と玉以外の駒が動いた場合の差分計算に共通して適用することができます。
 始めに駒リストをメモリからYMMレジスタにロードします。駒リストは32ビットの整数の配列ですので、一度に8個のBonaPieceをロードし、YMMレジスタに格納することができます。これには_mm256_load_si256()関数を使います。

__m256i indexes = _mm256_load_si256((const __m256i*)&list0[i]);

 ここでlist0は先手から見た駒リストを表しています。
 続いて駒リストの内容に従って評価値配列から評価値をギャザーしてきます。これには_mm256_i32gather_epi32()関数を使います。

__m256i w = _mm256_i32gather_epi32((const int*)pkppb, indexes, 4);

 ここでpkppbはkpp配列の2次元目までのインデックスを埋めたポインターです。ギャザーの対象が32ビットの要素のため、第3引数のscaleには4を指定しています。
 ギャザーしてきた32ビットの要素は16ビットの整数2つがパックされたものです。これを32ビットに符号拡張付き変換を行い、足し合わせていきます。32ビットに符号拡張付き変換を行うためには、YMMレジスタの上位・下位ビットをXMMレジスタに_mm256_extracti128_si256()を使ってムーブし、その後で_mm256_cvtepi16_epi32()を使って変換する必要があります。評価値を足し合わせるときは_mm256_add_epi32()を使います。

__m256i wlo = _mm256_cvtepi16_epi32(_mm256_extracti128_si256(w, 0));
diffp0 = _mm256_add_epi32(diffp0, wlo);

 上位128ビットについても同様に行います。これで評価関数の最内周のループの処理を8要素分同時に行うことができました。
 ただし、上記のコードは完全ではありません。駒リストの要素数は38要素ですので、8個ずつ要素を処理すると6個の余りが出てしまいます。この余りに対処する方法として2通りの方法が考えられます。1つ目の方法は6個の要素を4個と2個の要素に分け、4個の要素をXMMレジスタで処理し、残りの2個の要素をSIMD命令を使わないで処理するというものです。もう1つの方法はマスク付きギャザー命令を用いて最後の2要素の処理結果を強制的に0とするというものです。どちらの方法が良いかはベンチマークを取って決めるのが良いと思います。
 『やねうら王』のevaluate_kppt.cppより評価関数中の先手玉が移動した場合の評価値の差分計算を一部抜粋・改変して掲載します。

// 先手玉の移動
const auto* ppkppb = kpp[sq_bk];
diff.p[0][0] = 0;
diff.p[0][1] = 0;
__m256i zero = _mm256_setzero_si256();
__m256i diffp0 = zero;
for (int i = 0; i < PIECE_NO_KING; ++i) {
  const int k0 = list0[i];
  const auto* pkppb = ppkppb[k0];
  int j = 0;
  for (; j + 8 < i; j += 8) {
    // list0[j]から8要素ロードする
    __m256i indexes = _mm256_load_si256(reinterpret_cast<const __m256i*>(&list0[j]));
    // indexesのオフセットに従い、pkppwから8要素ギャザーする
    __m256i w = _mm256_i32gather_epi32(reinterpret_cast<const int*>(pkppb), indexes, 4);
    // 下位128ビットを16ビット整数→32ビット整数に変換する
    __m256i wlo = _mm256_cvtepi16_epi32(_mm256_extracti128_si256(w, 0));
    // diffp0に足し合わせる
    diffp0 = _mm256_add_epi32(diffp0, wlo);
    // 上位128ビットを16ビット整数→32ビット整数に変換する
    __m256i whi = _mm256_cvtepi16_epi32(_mm256_extracti128_si256(w, 1));
    // diffp0に足し合わせる
    diffp0 = _mm256_add_epi32(diffp0, whi);
  }
  for (; j + 4 < i; j += 4) {
    // list0[j]から4要素ロードする
    __m128i indexes = _mm_load_si128(reinterpret_cast<const __m128i*>(&list0[j]));
    // indexesのオフセットに従い、pkppwから4要素ギャザーする
    __m128i w = _mm_i32gather_epi32(reinterpret_cast<const int*>(pkppb), indexes, 4);
    // 16ビット整数→32ビット整数に変換する
    __m256i wlo = _mm256_cvtepi16_epi32(w);
    // diffp0に足し合わせる
    diffp0 = _mm256_add_epi32(diffp0, wlo);
  }
  for (; j < i; ++j) {
    const int l0 = list0[j];
    diff.p[0] += pkppb[l0];
  }
  diff.p[2] += kkp[sq_bk][sq_wk][k0];
}
// diffp0とdiffp0の上位128ビットと下位128ビットを独立して8バイトシフトしたものを足し合わせる
diffp0 = _mm256_add_epi32(diffp0, _mm256_srli_si256(diffp0, 8));
// diffp0の上位128ビットと下位128ビットを足しあわせてdiffp0_128に代入する
__m128i diffp0_128 = _mm_add_epi32(
_mm256_extracti128_si256(diffp0, 0),
_mm256_extracti128_si256(diffp0, 1));
// diffp0_128の下位64ビットをdiff.p[1]にストアする
std::array<int32_t, 2> diffp0_sum;
_mm_storel_epi64(reinterpret_cast<__m128i*>(&diffp0_sum), diffp0_128);
diff.p[0] += diffp0_sum;

 以上により評価関数を高速化することができました。手元の実験環境ではAVX2を用いない場合に比べてNPSが約9%程向上しました。これはレーティングに換算して18程度の向上となります。
 評価関数のAVX2化は組み込み関数の使い方さえ分かれば比較的容易に行うことができます。気軽にレーティングを向上させることができるため、今後も広く使われていくのではないかと思います。

C91 告知


コミックマーケット C91 にて同人誌『コンピュータ将棋 2016年度課題技術総復習』を委託頒布予定です。内容は2016年度に流行した課題技術の解説となります。自分も売り子をさせていただく予定です。C91 1日目 12月29日(木) 西み34b YUHA でお待ちしております。

最後に

これにてコンピュータ将棋 Advent Calendar 2016は終了となります。素敵なイベントを企画してくださった平岡氏に心よりお礼申し上げます。それでは皆様、良いお年を。

Visual Studioをアンインストールする

Visual Studioをアンインストールしたいとき、本体をプログラムと機能からアンインストールしても関連コンポーネントがアンインストールされずに困ることがある。公式ドキュメントには各コンポーネントを主導でアンインストールするように書かれているが正直面倒に感じる。そのような場合は、インストーラーに"/uninstall /force"をつけて実行すると良いらしい。

C:\Users\someone\Downloads>vs_langpack.exe /uninstall /force
C:\Users\someone\Downloads>vs_community.exe /uninstall /force

SubversionレポジトリをGitに移行する

自宅サーバーのSubversionレポジトリをGitに移行したのでメモ。

Gitではデータ転送用のプロトコルとして以下の4種類が使用できる。

  • Local
  • Secure Shell (SSH)
  • Git
  • HTTP

自分は自宅サーバーに既にセットアップしてある環境を再利用するため、SSHを使用することにした。

移行元のSubversionのレポジトリは/home/subversionにおいてある。また、移行先のGitレポジトリは/home/gitに置くことにした。

SubversionレポジトリからGitレポジトリへ移行するには以下の手順で行う。

  1. git svn clone で既存のSubversionレポジトリをGitレポジトリとしてローカルにcloneする
  2. タグを変換する
  3. 参照をローカルブランチに移動する
  4. git clone --bare でベアレポジトリを作る

以下は自宅サーバーのSubversionレポジトリをまとめて移行するためのスクリプト。/home/git以下でgitユーザーでログインして実行する。

#!/bin/sh
for directory in `ls ~subversion/`
do
    if [ -e ${directory}.git ]
    then
        echo "*** Skipping ${directory} ..."
        continue
    fi

    echo "*** Converting ${directory} ..."
    echo "*** Cloning ${directory} ..."
    cd
    git svn clone http://kishibe.dyndns.tv/svn/${directory} --authors-file=users.txt --no-metadata -s ${directory} || exit 1

    echo "*** Cleaning up ${directory} ..."
    cd  ${directory}
    git for-each-ref refs/remotes/tags | cut -d / -f 4- | grep -v @ | while read tagname; do git tag "$tagname" "tags/$tagname"; git branch -r -d "tags/$tagname"; done
    git for-each-ref refs/remotes | cut -d / -f 3- | grep -v @ | while read branchname; do git branch "$branchname" "refs/remotes/$branchname"; git branch -r -d "$branchname"; done

    echo "*** Cloning ${directory}.git ..."
    cd
    git clone --bare ${directory} ${directory}.git || exit 1

    echo "*** Removing ${directory} ..."
    rm -Rf ${directory}
done

Ubuntuで古いカーネルを削除する

コマンドを忘れてしまっていたので備忘録として。

sudo apt-get autoremove

リンク