一般的なパンケーキアルゴリズムは堅実だがどこか無駄のある緩さを感じるが、ゲイツのアルゴリズムは一手も無駄にしない鋭さを感じる。ゲイツが発見したアルゴリズムをなぞることで、ゲイツの思考に触れることができ、ゲイツのエンジニアとしての大きさを実感できるはずだ。数学の知識がある方は、ゲイツの論文そのものを読んでみるもの楽しいと思う。

## 数学者、遺伝学者、コンピューター技術者、、、どれになるか迷っていたビル・ゲイツ

ビル・ゲイツは、高校時代からコンピューターに夢中になり、すでにソフトウェアを受託開発するというビジネスを始めている。しかし、そのままマイクロソフトを起業するつもりだったわけではなく、ハーバード大学に進んでからは、数学者になるか遺伝学者になるかコンピューター技術者になるか決めかねていた。

まずは数学者になることを目指して、「数学55」というハーバードの中でも最高レベルの数学の講義を受講した。しかし、ここでゲイツは人生で始めての挫折を味わったのではないかと言われている。ゲイツは数学の成績も図抜けて優秀だったが、それでは単なる優等生にすぎない。ハーバードには数学の天才としか呼びようがない学生がごろごろいたのだ。努力ではどうにもならないものをゲイツは感じたのかもしれない。

## ビル・ゲイツが書いた唯一の学術論文『パンケーキ論文』

ゲイツが数学からコンピューターに転換をする時期に、ゲイツは唯一の学術論文を書いている。これが数学の論文なのだが、実にコンピューター的なのだ。

この論文は、パンケーキ問題に関するもの。パンケーキ問題とは、1975年にヤコブ・グッドマンが提案した数学問題。「あるシェフが複数のパンケーキを焼くが、腕が悪いために、大きさがまちまちになる。しかも、それをひとつに積み重ねてしまう。これを上から小さいもの順に並べ替えたいが、n枚のパンケーキを並べ替えるのに、何回操作を行えばいいか？」というものだ。

ここで注意したいのが、並べ替えるのが縦に積まれたパンケーキだということ。並んでいるパンケーキの一箇所にヘラを入れて、そこから上をひっくり返すという操作しかできない。

~~ 積まれたパンケーキのどこからにヘラを差し込んで、そこから上をひっくり返すことしかできない。これで小さいものから順に並べ替えるというのがパンケーキ問題だ。 ~~

ゲイツは授業でこの問題を知った時「簡単じゃないか！」とバカにしたように声をあげたという。その気持ちはわかる。プログラムの基礎課程で学ぶソートアルゴリズムのうちの選択ソートの簡単な応用問題に見えるからだ。

選択ソートは、ランダムに並んだ数字の中から最小値を見つけ、これを先頭の数字と入れ替えるというもの。これで先頭に最小値がくるので、次は2番目以降の中から最小値を見つけ、2番目の数値と入れ替えるというように、先頭からソートをしていくやり方だ。パンケーキ問題も、選択ソートを応用して、最も大きなパンケーキを見つけて、最も下と入れ替える。次は下から2番目より上で最も大きなパンケーキを見つけて、下から2番目と入れ替える、とやっていけば、選択ソートの応用でできそうな気がする。

しかし、事情はそう簡単ではない。なぜなら、パンケーキではヘラをどこかに入れて、そこから上をひっくり返すことしかできず、選択ソートのように「入れ替える」ということができないのだ。

## ゲイツが数日間夢中になって見つけた最適なアルゴリズムとは!?

簡単だと思ってバカにした問題が、意外に難しかった。ゲイツはそれから数日間、このパンケーキ問題に夢中になり、ようやく最適なアルゴリズムを見つけ、指導教官のクリストス・パパディミトリューに報告をした。そして、指導教官とゲイツは、この論文を仕上げ、「離散数学」1979年9月号に掲載された。これがビル・ゲイツ唯一の学術論文として、現在でもデジタルアーカイブなどで読むことができる。

ゲイツの着想はどんなところにあったのだろうか。

その前に、パンケーキ問題の一般的なアルゴリズムを紹介しておこう。パンケーキが（2,3,4,7,6,1,5)の順で並んでいるものとする。これを(1,2,3,4,5,6,7）に並べ替えるのが目的だ。

一般的なパンケーキアルゴリズムでは、末尾から大きいものを並べていくようにする。しかし、いきなり最大値を末尾に移動させることはできないので、最大値の下でひっくり返して、いったん先頭に出し、それから全体をひっくり返すという2段構えで行う。この例では、最大値の7の下にヘラを入れて、その上の（2,3,4,7）の部分をひっくり返す。

そして、全体をひっくり返す。

これで末尾に最大値の7がきたので、上6枚から最大値6を探して、そこから上の（5,1,6)をひっくり返す。

末尾の7は定位置なので触らず、その上にヘラを入れて（6,1,5,2,3,4）をひっくり返す。

これで、末尾の6と7が決まったので、その上から最大値を探し…ということを繰り返していく。

とても堅実な方法だが、1つのパンケーキの位置を決めるのに2手かかる。並び順の関係でうまく手数が少なく済む場合もあるが、最悪のケースでは2n回かかることになる。堅実だが、どうもバカ正直で面白くない。もっと手数の少ないアルゴリズムがあるのではないか。ゲイツが悩んだのはここだった。

## 「連続ブロック」を利用すると、より洗練されたアルゴリズムになることを発見

そして、ゲイツは「連続ブロック」を利用すると、より洗練されたアルゴリズムになることを発見した。連続ブロックとは[2,3,4]などのように、数字が連続している並びのことだ。

初期状態（2,3,4,7,6,1,5)では、（[2,3,4]7,6,1,5)のように[2,3,4]の部分が連続ブロックになる。また、[6,7,1]は連続ブロックと考え、[4,3,2]は逆順になるので連続ブロックとは考えない。

ゲイツは、この連続ブロックに注目をして、連続ブロックの先頭がさらに連続ブロックを伸ばすようにひっくり返していくと、ステップ数の少ないアルゴリズムになることを発見した。

では、[2,3,4]という連続ブロックがあり、この連続ブロックの先頭の2が、さらに連続ブロックを伸ばすために1の隣にくればいい。つまり、6と1の間にヘラを入れて、（2,3,4,7,6)をひっくり返せば、連続ブロック先頭の2が1の隣にきて、連続ブロックが伸びていくことになる。

[2,3,4]の連続ブロックは反転されたので、連続ブロックではなくなってしまったが、1と隣接して、[1,2,3,4]という潜伏する連続ブロックとなった。一方で、新たに[6,7]という連続ブロックが生まれている。この先頭の6がさらに連続ブロックを伸ばすには5の隣にくればいい。そのためには、1と5の間にヘラを入れて、（6,7,4,3,2,1）をひっくり返す。

最小値である1と最大値である7は隣り合っていると考え、連続ブロックの先頭の1が7と隣り合うようにするため、4と7の間にヘラを入れ、（1,2,3,4)をひっくり返す。

ここで連続ブロックがひとつもなくなった。連続ブロックがない場合は、基本のアルゴリズムを適用する。最大値でひっくり返し、それから全体をひっくり返す。

## 「プログラマーというものは、楽をするためであれば、どんな苦労もいとわないものだ」

いかがだろうか。時間のある時に、メモ帳に適当な数字を並べて、一般的なパンケーキアルゴリズムとゲイツのアルゴリズムを手段計算して、比べてみていただきたい。あるいはプログラムを組んでみてもいいだろうし、数学の力がある人はn枚のパンケーキを並べる時のパンケーキアルゴリズムとゲイツアルゴリズムの最小手数の一般解を求めても面白い。

一般的なパンケーキアルゴリズムは堅実だがどこか無駄のある緩さを感じるが、ゲイツのアルゴリズムは一手も無駄にしない鋭さを感じる。ゲイツは後年、「プログラマーというものは、楽をするためであれば、どんな苦労もいとわないものだ」と語っている。

ゲイツが発見したアルゴリズムをなぞることで、ゲイツの思考に触れることができ、ゲイツのエンジニアとしての大きさを実感できるはずだ。数学の知識がある方は、[※ゲイツの論文そのもの](https://people.eecs.berkeley.edu/~christos/papers/Bounds%20For%20Sorting%20By%20Prefix%20Reversal.pdf)を読んでみるもの楽しいと思う。

~~（※）ビル・ゲイツ唯一の学術論文。学会誌に掲載される頃にはゲイツはすでに起業していたため、肩書きは「マイクロソフト」となっている。ただし、住所は、後のシアトル市ではなく、創業地のニューメキシコ州アルバカーキになっている。~~

[『マイナビIT AGENT』なら、IT業界に精通した専任アドバイザーと豊富な求人で、あなたの転職を丁寧にサポートします。](https://mynavi-agent.jp/it/?utm_source=and-engineer&utm_medium=content-text&utm_campaign=acv08)

ビル・ゲイツの思考に触れられるゲイツ唯一の学術論文「パンケーキ論文」とは!?

macOSで利用できるパソコンはMacだけです。細部までこだわったMacのデザインは魅力的ですが、一般的なWindows PCに比べて、同じようなスペックでもMacは価格が高いのが玉にキズ。だから、もっと低価格なPCやもっと高スペックなPCでmacOSを使いたいという声が昔から根強く上がっていました。そんなmacOSの解放を求める声に対するテリー・ランバート氏のQuoraでの解説が神回答であると話題になっています。

## 根強い「どうしてmacOSはMac限定?」

Macは、macOSがUNIXベースのため、多くの開発者に使われています。仕事用のパソコンも、OSを選べたり、BYOが認められるようになって、スマートフォンがiPhoneだからMacを選ぶという人が増えています。しかし、Windows PCに比べてMacは価格が高いのが玉にキズ。スペックが同程度の機種を比べると、Windows PCならMacの半分ぐらいの価格の製品が見つかります。細部までこだわったMacのデザインは魅力的ですが、価格差ほどの価値の差はあるのでしょうか？

そんなユーザーのもやもやとした気持ちに対して、Appleで長くソフトウエアエンジニアとして活躍していたテリー・ランバート氏のQuora（Q&Aサイト）での解説が神回答であると話題になっています。同氏はAppleでmac OS Xのカーネル開発を担当、その後はGoogleでもChrome OSの開発に携わりました。

Quoraの質問は「どうしてAppleブランド以外でOS X（macOS）が動作するPCがないの?」でした。MacはIntelのCPUを採用しているので、乱暴な言い方をすると多くのWindows PCやLinux PCと中身は同じx86/ x64プラットフォームです。だから、macOSを使いたくて使っている人の中には、もっと価格の安いPCや高スペックなPCにmacOSをインストールして使ってみたいと考えている人が少なくありません。

[【関連記事】「IT・エンジニアの職種図鑑」](https://mynavi-agent.jp/it/jobindex/?utm_source=and-engineer&utm_medium=content-text&utm_campaign=acv08)

[【関連記事】「未経験だけどIT業界に転職する方法! 職種や仕事内容もご紹介」](https://mynavi-agent.jp/knowledge/it/762.html?utm_source=and-engineer&utm_medium=content-text&utm_campaign=acv08)

~~昨年末に登場したMacBook Pro（右）、MacBook Air（左）よりコンパクトになりましたが、Proモデルとして、もっと高スペックを追求してほしいという声も。~~

## 同じスペックでも異なるPCとMacのパーツ

それができない理由を一言で説明すると「Appleが認めていないから」。もう少し長いバージョンだと「ハードウエアをMacに限定して、Macに最適化したOSとしてmacOSを開発することで、パソコンとして最高の使用体験を提供できるから」、これが最もよく見る回答ですね。でも、「ハードウエアに最適化」と言われても、具体的にどういうことなのか、一般的にはイメージできません。他のPCだってハードウエアに最適化しているはずです。「それならMacは何が違うのか？」という点についてランバート氏は分かりやすく説明していますので、かいつまんで紹介しましょう。AppleがMacにこだわるのは、一般的なスペックの性能ではなく、Appleが求める性能を発揮させるためです。

今日のMacBookシリーズではRAMのユーザーを交換できません。Appleは電力管理を向上させるためにRAMの動作周波数や電圧も変動させており、その動作を効果的に実行できる水準のRAMに限定するためです。CPUも同様に、動作周波数を上げるバーストモードや安定した電圧コントロールなどで微細なコントロールを求めています。そのため、スペック上は他のブランドのPCと同じIntelのCoreプロセッサを採用していても、Intelの基準ではなく、より高いAppleの基準を満たす部品を求め、Intelへの支払いにはその分のプレミアを乗せているそうです。

macOSではKEXT（Kernel EXTension）というモジュールを通じてカーネルの機能を拡張し、デバイスドライバなどを、カーネルと分離しながら安全に、そして容易に追加/削除できます。KEXTには「The Stepper」と呼ばれる電力や周波数などを微細にコントロールするモジュールが組み込まれています。厳選したパーツをKEXTで微細にコントロールすることで、パワフルな性能と効率的な動作が実現します。効率的な動作によって放熱が抑えられ、よりスリムで軽量なデザインも可能になります。

以前はデスクトップは据え置き型のデザインでしたが、今日では全てのMacでモバイルノートに見られる電力効率優先が徹底されています。たとえば、量販されているPCのマザーボードは信号の遅延を抑えるようにデザインされていますが、Appleは電力効率と放熱を優先してロジックボードを設計しています。ボードだけ見ると冗長で奇妙なデザインに思えますが、それが筐体と組み合わさった時に、小さなヒートシンクや最小限の冷却ファンで効率的に熱を逃がせる設計が完成します。

~~MacBook Proの内部、エアフローに沿って効率的に放熱されるように全てがデザインされています。~~

## マージンを確保するMac、低価格競争に向かうPC

厳選したハードウエア、その性能や機能を存分に引き出すOSとソフトウエア。最初から最終的な製品をイメージした統合的な設計によって生み出される相乗効果がMacならではの使用体験です。対照的に、Windowsは存在するあらゆるPC向けパーツをサポートする必要があるので平均的になってしまいます。汎用パーツと平均的なWindowsの組み合わせはスペック通りの性能に納まり、性能で差別化できないPCメーカーは「低価格」で競争し始めます。より安くを求めすぎると、粗悪なパーツや低品質なパーツが含まれる可能性が高まるという悪循環です。

Macのマージンは35％程度と言われています。それほどあれば、2011年にタイの水害でHDDの価格が上昇したようなパーツ価格の変動があっても吸収できます。また、コストのかかる新しい素材や機能の採用にも挑戦可能です。一方、低価格競争にあるWindows PCのマージンは3〜6％程度。コストの上昇によって利益が吹き飛んでしまいかねません。

もちろん、Appleのモデルがいつでも正しいというわけではありません。ムーアの法則が有効で、CPUの性能の向上がそのままPCの価値になっていた頃は、汎用パーツを組み合わせて低価格を実現したWindows PCがMacを圧倒していました。

ただ、ムーアの法則の進行が鈍って、差別化のポイントがCPU性能から総体的な使用体験に移ったことで風向きが変わり始めました。PCの主流はデスクトップからモバイルノートに、そして従来型のPCからポストPCへと移るに従って、Macの価格の価値を認める人が増えています。見方を変えると、限られた電力の中でPC並みの性能が求められるスマートフォンをAppleが編み出せたのも、統合的なデザインを是とするAppleであってこそ。Macで培ってきたモデルは、iPhoneの強みにもなっています。

「Macはなぜ高い」に元Appleエンジニアが神回答

2017年5月、Unityの一大イベントであるUniteが開催されました。
Unity2017に関する魅力的な機能も色々発表され、期待に胸が膨らんじゃいます。

そういえば、今回のUniteには会社の後輩がボランティアスタッフとして参加しました。
「大変だったけどとっても楽しかった！」とのことですので、予定が確保できそうな方はぜひ次回のUniteに参加してみてください！（筆者も参加してみたい・・・！）

さてさて、今回はシミュレーションゲームのアルゴリズムを作ってみましょう。（賀好 昭仁）

## シミュレーションゲームというジャンルは広すぎました

改めて調べてみると、シミュレーションゲームには

・シミュレーションRPG
・恋愛シミュレーション
・フライトシミュレータ

など多種多様なゲームが含まれております。

ということで、今回はシミュレーションゲームの中でも特に歴史のある「マス目を使ったターン制戦略シミュレーションゲーム」のアルゴリズムを作ってみます。

※「マス目を使ったターン制戦略シミュレーションゲーム」ですとちょっと長いので、以降は「戦略シミュレーション」と称させていただきます。

＜余談＞
最近、ファイアーエムブレムヒーローズ（FEH）で久々にシミュレーションRPGをプレイしました。
筆者はこれまでシミュレーションRPGをいろいろプレイしてきましたが、すべて1マップに1時間前後かかるガッツリ系のゲームばかりでした。
FEHもその類かと思いきや、1マップ数分で終わるというスマホゲームらしいライトさ。
本格シミュレーションPRGでも工夫次第でここまでライトに作れるものなのか、と驚いたものです。（そして、ライトでも面白い・・・！）

## 戦略シミュレーションの要素を考えてみる

ゲームを作っていくにあたって、まずは戦略シミュレーションの要素を考えてみましょう。

戦略と名がつく通り、自軍のユニットを使って敵軍のユニットと戦うゲームですので、

・自軍ユニット
・敵軍ユニット

そして、戦うための舞台も必要です。
障害物の無い平原、うっそうとした森、山岳地帯など、さまざまなマップが登場すると楽しそうですね。

戦略シミュレーションに最低限必要な要素はこれくらいでしょうか。要素はとっても少ないですが、ユニットの種類・マップの種類・自軍と敵軍の戦力バランスや戦況・敵AIなどに変化をつければ、要素は少なくてもさまざまな楽しみ方ができます。

そういえば、将棋やチェスなどはユニットの種類が固定でマップも1種類しかありません。
それでも打ち手次第でさまざまな局面が楽しめることを考えますと、戦略シミュレーションの根本的な部分の奥深さが垣間見えますね。

## ユニットの動ける範囲を考えてみる

いざ戦略シミュレーションを作ろうとしたとき、まず頭を悩ませるのは「ユニットが動ける範囲をどう計算するか」だと思います。

将棋やチェスでは各コマの移動のルールがシンプルなため、動ける範囲を求めるのは簡単です。
ただ、戦略シミュレーションではユニットの移動力に応じて1回の行動で複数マス動けたり、同じ1マスでも平原と森で移動コストが変わったりと、さまざまな要素が絡んできます。

これらを解決するために、移動可能範囲を計算するためのアルゴリズムを実装する必要があります。

移動可能範囲は、簡単なアルゴリズムで求めることができます。まずはマップの各マス目の移動コストを列挙します。
移動不可のマス目は、どのユニットも移動不可能になるような大きな値を入れておけばOKです。
下の図では、移動コスト1の茶色のマスは平原、移動コスト2の緑色のマスは森、移動コスト9の灰色のマスは岩山（進入不可）と考えてください。

続いて、移動力の計算を行います。まずは動かしたいユニットが居るマスの座標に、そのユニットの移動力分の数値を入れておきます。下図は移動力4を持つユニットがマップ中央にいた場合の例です。

続いて、ユニットの居る上下左右のマスに、対象マスの移動コスト分を引いた値を入れます。
※対象マスに既に値が入っていた場合、上書きせずそのままにします。

下図では、ユニットの居る赤いマスを基準に、その四方のマス（黄色いマス）に値を入れています。
右側のマスは森（移動コスト2）なので、ここだけ数値が2になっています。

続いて、移動力の値を1減らしたマス、つまり値が「3」のマスを基準に同じ計算を行います。

あとは値を1ずつ減らしていき、0になるまで同じ処理を繰り返せば、移動可能範囲を導き出すことができます。
ちなみに、値がマイナスになったマスは移動力が足りず移動できないマスですので、最終的な移動可能範囲は下図の青いマスとなります。

特殊なマス（後述）がない限り、移動力や地系が変わっても同じ処理で移動範囲を求めることができます。

シミュレーションPRGや戦略シミュレーション全般で大活躍しそうなアルゴリズムですね！

ユニットを移動させる際にユニットが移動先にパッとワープしたり、移動不可マスを通って移動したりすると、プレイヤーは違和感を感じてしまいます。
違和感を感じさせないようにするためには、目的地までの移動経路を算出する必要があります。

移動経路は、先ほどの移動範囲の計算と逆の手順で導き出すことが可能です。

下図は赤いマスが移動先だった場合の例です。
まずは移動先マスの値（残りの移動力）に、そのマスの移動コストを足します。
四方にあるマスを見ると、上記の値に合致するマスが必ず1つ以上存在します。（図中の黄色いマス）
ユニットはこの黄色いマスを通って移動したことになります。
続いて黄色いマスを基点に同じ処理を繰り返すことで、徐々に移動経路が明らかになっていきます。

~~図 6 経路算出（移動先から2歩手前まで）~~

もし黄色いマスが複数存在する場合は「どちらからでも来られる」ことになります。

あとはユニットが元居た位置までこれを繰り返せば、移動経路が明らかになります。下図では、中央にある「4」のマスから「←↓←←」の経路と「↓←←←」の経路の2パターンが割り出せました。

## アルゴリズムの注意点と改良方法

今回は不要ですが、もしもマップに下記のようなマスが存在する場合は前述のアルゴリズムをそのまま使うことができません。

・移動力を消費しないマス
・通ると移動力が回復するマス

このようなマスに対応する場合、下記のような処理を加える必要があります。

・該当マスから周りのマスに対し、移動力の計算＆書き込みが終わったかどうかのフラグを設ける
・数字（残りの移動力）が埋まっているマスに対して、より大きい値が入れられる場合は値を上書き、上記フラグをクリアする処理
・ひと通りの計算が終わったのち、マス目上の最大移動力をベースに再度同じ計算を行う（この際、上記フラグが立っているマスは計算対象から除外）、全てのマスにフラグが立つまで何周も続ける

また、移動力回復マスにワープするマスを組み合わせると無限ループに陥る可能性もありますので、このようなマスを実装する場合は注意しましょう。

今回のサンプルプロジェクトはこちら。

https://github.com/akako/gamealgorithm-war-simulation/releases/tag/for_algorithm10

Unityで作ろう！ゲームアルゴリズム10 1

ユニットを選択して移動可能マスをハイライト、マスを選択して経路計算＋移動するところまでを作りました。
まだまだゲームとは言えませんが、これだけでも戦略シミュレーションの香りがプンプン漂ってきますね。

今回のアルゴリズムは、マス目を使った戦略シミュレーションであれば必ず活躍します。
HEX（6角形）のマス目でも同じアルゴリズムが適用できますので、ぜひ試してみてください！

【Unityで作ろう！ゲームアルゴリズム】シミュレーションゲームのアルゴリズムを作ってみる

筆者はずっとインドア派（というかゲーマー）だったのですが、最近は外出して体を動かすことにハマっています。

お散歩にジョギング、立ち寄った公園でお花の写真を撮るなど、楽しみ方はいろいろ。ちょっと歩くだけで、脳をビビっと刺激する変わった人や妙なモノに出会ったりするものです。アイデアが煮詰まったなら、ぜひ気晴らしに散歩に出てみましょう！

それでは早速ですが、今回はリバーシの対戦相手となるAIを作ってみましょう。（賀好 昭仁）

まずは用語の説明から入りましょう。
AIとは、Artificial Intelligence（人工知能）のことです。

世の中には様々なAIが溢れています。
そして、AIのほとんどは何らかの目的を達成するために作られています。
例えば、工業用の機械を制御して製品を作るための制御AIや、部屋中をくまなく掃除するための掃除機AIなど、その用途専用に最適化されたAIが沢山存在しています。
本記事で作成するAIも「リバーシの対戦相手を務める」という目的があります。

一方で、最近ディープラーニングと呼ばれる手法を利用した新しいタイプのAIが登場し始めています。

ディープラーニングとは、機械学習の手法のひとつです。
ざっくり説明しますと、まず「ニューラルネットワーク」という、人間の脳の仕組みを模した機能を備えるAIを準備します。
このAIにデータを与えると、AIはデータの特徴を分析し、学習していきます。
十分に学習が進むと、それまでの学習を元にして、与えられた情報がどのようなものであるかを判断することが出来るようになります。

ディープラーニングで出来上がったAIの例を挙げてみますと、2016年3月、Googleが「ネコを認識するAI」が出来たと発表し、話題となりました。

このAIがなぜスゴイかと言いますと、「人間がAIにネコとはどのようなものであるかを教えた」わけではなく、AIにYouTubeから取り出した1,000万枚の画像を与えてディープラーニングを進めた結果、「AIがネコの特徴を覚えた（ネコを判別させたかった訳ではないのに、勝手にネコを判別できるようになった）」という点です。

これは驚くべきことで、AIが置かれた状況に応じて臨機応変に（それこそ、まるで生き物のように）成長していける可能性を示唆しています。
いずれは「自ら言葉を覚え、人と自在に会話できるAI」なども誕生することでしょう。

いやはや、思い切り脱線してしまいました。

ディープラーニング用AIのプログラミングも記事にしたいところですが、筆者自身まだまだ理解が足りていませんので、いずれ機会があればということで。（笑

今回作成するAIは「リバーシができるAI」です。

一言で「リバーシができるAI」と言っても、実装の方向性はいくつか考えられます。

### １．ゲームの展開を予測するAI

今後のゲームの展開を予測し、最善と思われる手を打つAI

どういった手を打った結果どのような成果が得られたかを逐次収集し、どんどん強くなっていくAI

リバーシをプレイする上で「有利になる条件」「不利になる条件」を定義し、それに応じてプレイを進めるAI

リバーシの場合は打てる手が限られています。
ロジックが完璧に実装出来たとすると、1.のパターンが最強です。
AIに手を完全に予測されてしまうと、どう足掻いても勝ち目はありません。
その代わり、手を予測するために凄まじい処理能力が必要となります。

2.は対戦する度に強くなっていくAIで、実装するのがとても面白そうです。
ただ、仕組みがかなり複雑になってしまいます。

今回は一番シンプルな3.のパターンで実装を進めてみましょう。
（部分的に1.のパターンも使用します）

## リバーシのAIに必要なインターフェース

リバーシのAIが必要とする情報と、情報を与えられた時にどのようなレスポンスを返せばよいかを考えてみましょう。

まず、AIが次の手を打つために必要な最低限の情報は

・自分の石の色
・現在の盤面の状況

これらの情報から現在の状況がわかれば、次にどのような手を打てばよいかが計算出来るというわけです。

情報を受け取ったのち、AIが返すべきレスポンスは「次の手」です。
リバーシにおける「次の手」とは「どのマスに石を置くか」ということですので、マスの座標を返せばOKです。

## ランダムに石を置くAIを作ってみる

まずは適当なAIを作ってみましょう。
石が置けるマスからランダムで1マス選ぶAIです。

AIに必要な処理をまとめた基底クラスです。
盤面シミュレータのサブクラスを同梱し、簡単に盤面のシミュレーションが出来るようにしています。
AIはこのクラスを継承し、フィールド情報を受け取って次の手を返すGetNextMove()メソッドを実装すればOKです。

https://github.com/akako/gamealgorithm-reversi/blob/master/Assets/Scenes/Game/Scripts/AI/Game_AI_Base.cs

ランダムに石を置くAIです。
盤面シミュレータから石を置けるマスを取得し、その中からランダムで1つ選んで返すだけの処理となっています。

https://github.com/akako/gamealgorithm-reversi/blob/master/Assets/Scenes/Game/Scripts/AI/Game_AI_Random.cs

以下にAIを組み込んだプロジェクトを準備しましたので、試しにプレイしてみてください。

https://github.com/akako/gamealgorithm-reversi/releases/tag/for_algorithm3

今回のAIはシンプルで組み込みはとても簡単ですので、組み込みに関する解説は割愛させていただきます
（Game SceneController.cs・Game Field.cs・Game Cell.cs スクリプトの前回との差分をご確認ください）

## ちゃんと動くAIを作ってみる

Game AI RandomのAIと対戦してみると、ランダムに石を置くだけではとっても弱いことがお判りいただけるかと思います。
次はリバーシのセオリーに沿って次の手を打つAIを作ってみましょう。

まずはセオリーを書き出してみます。
Google先生にセオリーを教えてもらい、実装しやすそうなものをいくつかチョイスしました。

・角を取る
・角の斜め隣は出来るだけ打たない
・序盤は少なく取る
・取った石が相手の石に囲まれている場所を狙う（「中割り」と呼ぶそうです）
・終盤は石をたくさん返せる場所を狙う

余談ですが、筆者は今回の調査で「中割り」を初めて知りました。

## セオリーの重み付けをしてみる

盤面の状況は様々で一概には判断出来ないため、「どの状況がどの程度重要か」をAIに教えてあげます。

・角を取る
「50ポイント」の重要度

・終盤までは角の斜め隣は出来るだけ打たない
盤面の3分の2が埋まるまでは、該当マスは「-30ポイント」の重要度

・序盤は少なく取る
盤面の3分の1が埋まるまでは、「取れる石の数 ✕ -10ポイント」の重要度

・取った石が相手の石に囲まれている場所を狙う（「中割り」と呼ぶそうです）
「取った石の周囲にある相手の石の数 ✕ 2ポイント」の重要度

・終盤は石をたくさん返せる場所を狙う
盤面の3分の2が埋まっていれば、「返した石の数 ✕ 5ポイント」の重要度

上記の計算を実装し、どの手を打てば良いかを判断出来るようにしてみます。
（なお、各値は筆者の感覚で適当に設定しています

前述の処理を実装したAIです。
石を置けるマスのポイントを計算し、ポイントが一番高いマスを返すというわかりやすい処理になっています。

https://github.com/akako/gamealgorithm-reversi/blob/master/Assets/Scenes/Game/Scripts/AI/Game_AI_Theory.cs

に同梱しており、Game SceneController.cs 63〜64行目のコメントを付け外しして

//ais.Add(Game_Field.StoneColor.Black, new Game_AI_Random(Game_Field.StoneColor.Black));
ais.Add(Game_Field.StoneColor.White, new Game_AI_Theory(Game_Field.StoneColor.White));

にすれば、Game AI Theoryと対戦出来るようになります。
ちなみに、両方の行のコメントアウトを外せばGame AI RandomとGame AI fTheoryの対戦を見ることも出来ますよ！

## （オマケ）AIに性格を付けてみる

AIにも個性があった方が、より一層ゲームが盛り上がります。

・調子に乗るAI
盤面に自分の石が多いと調子に乗って適当に打つようになるAI

・欲に目がくらんでしまうAI
3つ以上石をひっくり返せるならば、それがどんな酷い手であっても打ってしまうAI

・スロースターターなAI
序盤は適当に打つが、終盤になると急に強くなるAI

などです。
リバーシのAIであれば、上記のいずれもGame AI Theoryを少しカスタムするだけで作れるかと思います。

ゲームに登場するキャラクターの性格を考えて、それに相応しいAIを作ってみると良いかもしれません。

ディープラーニングからAIの性格まで、ずいぶん話が広がってしまいました。
ゲームにおいてAIはゲームバランスに直結するため、プログラマとしては腕の見せどころです。
強すぎず弱すぎず、プレイヤーが「心地よい」と思えるような対戦相手を作ることを目指しましょう。（激ムズゲームも需要はありますけどね）

また、複雑で面白いAIが作れるならば、それ自体がゲームになることもあります。
少し昔のゲームですが、シーマンやワンダープロジェクトJなどは高度なAIが主役の興味深いゲームでした。

応用の幅は無限大ですので、本格的にAIに関して勉強してみるのも楽しそうですね。

【Unityで作ろう！ゲームアルゴリズム】リバーシのAIを作ってみよう

グロースハッカーとは、世界でもっとも最先端のIT職種のひとつ。
シリコンバレーで流行し、日本のIT業界にもその需要は急速に広まっています。

でも、一体、何をする仕事のこと？
どんな成功例がある？
どうしたらなれる？

今回は、いまさら聞けないグロースハッカーの定義をまとめてみました。（イワタテ）

## グロースハッカーって何をする仕事？

グロースハッカーとは、会社、製品、サービスの成長（＝グロース）を加速させることを使命とする仕事のことです。あいまいすぎてよくわからない？
それもそのはず、グロースハッカーという言葉が生まれたのは2010年のこと。
まだその手法は、確立されているわけではありません。
言い換えてみれば、グロースに繋がる手法を自ら編み出し、実行できる人。
トライアンドエラーを繰り返しながら、新たな成果を創造できる人を、広くグロースハッカーと定義することができそうです。

## とはいえ、実際にはどんな行動をして、どんな成果を得ている？

【例1：1億8000万ドルの政治献金を集めたABテスト！】
2012年のアメリカ大統領選で、共和党のミット・ロムニー陣営は、弱冠24歳のグロースハッカー、アーロン・ジーンを招集。「好感度の高い」ウェブサイトデザインの変更を依頼しました。
ジーンは、徹底したABテストを敢行。
バナーのサイズ、位置、色などを、繰り返し微調整し、有権者にとってもっとも好感度の高いウェブサイトデザインを追求し、1億8000万ドルもの政治献金を集めることに成功したということです。
結果的に、大統領選は現職のバラク・オバマに敗北しましたが、この例はグロースハックの夜明けを告げる成功事例として知られています。

【例2：友人招待やSNS連携でユーザー数を2億7500万人まで増やしたDropbox！】
クラウドストレージの大手Dropboxも、従来にはないアイディアでユーザー数を爆発的に増やしたグロースハックの好事例。
たとえば、ユーザーを紹介したり、アカウントをFacebookやTwitterなどと連携すると、無料使用できる容量が増えるサービスは、後続の事業者にも非常に参考にされているようです。
また、ウェブサイトのトップページに存在するプロダクトは、2分間の動画とアプリのダウンロードボタンだけというシンプルな設計も、ユーザーのアクションをフォーカスする意図に適ったグロースハックですね。

【例3：3年で400万人の有料会員獲得を目指すクックパッド！】
料理レシピの紹介サイトとして有名なクックパッドは、グロースハックによって3年以内に有料会員数を現在の100万人から400万人に増やすという目標を設定しています。
具体的な手法としては、「有料機能の7日間無料お試し」や、「外部サービスの会員限定で無料クーポンを付与」、「誕生日クーポン」の発行、9月9日限定で無料クーポンを配布する「クックの日」キャンペーン、検索結果の最適化を目的とした「殿堂入りレシピ」の設置などが公開されています。
期間内の目標達成が果たせるか、見守っていきたい事例ですね。

## マーケティングと比較されることが多いけど、どう違うの？

共通しているのは、テレビやラジオ、雑誌などの既存メディアを使った従来的なマーケティング手法よりも、ウェブサイトやアプリといった、IT的な手法でテストを繰り返すという部分。

また、時には開発の現場と一体になって行動する必要があるため、現場の技術を知っている必要があるという点です。

その他の特徴を比較してみると、以下の通りです。

●予算と期間が決められている。
●手法が確立されていて成果は（比較的）安定的である。
●製品やサービスの開発に自らは携わらない。

●予算と期間は選択した行動によって流動的である。
●前例のない手法を生み出すため実際に行動してみるまで誰にも成果がわからない。
●製品やサービスの開発に、必要とあれば自らも積極的に携わる。

## どうしたらグロースハッカーになれる？

ビジネス特化型SNSとして知られるLinkedinには、自身の仕事を「グロースハッカー」と表記する例が増えているようです。
実際アメリカでは、マーケティングの仕事をしてきたという人でも、「マーケター」という呼び名を「グロースハッカー」と書き換えただけで、複数のIT企業からオファーが来ることもあるとか。
グロースハッカーの事例がまだ少ない日本でも、自ら「グロースハッカー」を名乗るのが、ほとんど唯一のグロースハッカーになる手段。
もちろん、名乗ったからといっていきなり能力が高まるわけではありません。
しかし、グロースハックという言葉の意味を知り、行動することを決意しただけで、仕事への意識は変わるはず。
目の前の仕事に対して、ただ無心で取り組むのではなく、「どうしたらもっと良くなる？」と自身に問いかけることが、グロースハッカーへの第一歩でしょう。

[グロースハッカーに関する求人を効率よく探し出すために、転職エージェントを利用してみませんか？](https://mynavi-agent.jp/entry/?utm_source=and-engineer&utm_medium=content-text&utm_campaign=acv08)

グロースハッカーとは？～いまさら聞けないトレンドワード解説～

ビジネスのスピードが大きく変わったと言われるグローバル時代。中でも変化の早いIT業界で生きていくためには、そして活躍するためには、情報を味方につけ、武器としなければなりません。

今回は、デキるITエンジニアに人気のニュースサイトをご紹介。

新人エンジニアのみなさんが、そろそろ会社に慣れてきたかな…仕事に慣れてきたかな…と油断した今こそ、つぎのステップとしての「情報収集」をオススメします！

シリコンバレーに本拠を持つテクノロジーメディア。

国内外のスタートアップニュースやリーク情報が掲載される早さには定評があり、IT業界の最先端を継続的かつ効率的にキャッチアップすることが可能な定番中の定番。

とりあえずこれだけでも押さえておけば、世の中の流れに遅れてしまうことはなさそうです。

[http://jp.techcrunch.com](http://jp.techcrunch.com)

海外のITエンジニアやギークの間でマニアックな人気を集めているユーザー投稿型ニュースサイト。テキストはすべて英語。そして異常なまでにシンプルな外観に尻込みしてしまうかもしれませんが、まだ他のメディアに載っていないような現場の一次情報が流れたり、ユーザーは気になるニュースや技術的な悩みについて筋金入りのギークに質問・相談することができたりして、他にはないオンリーワンの魅力があります。

日本ではまだあまり知られていない今こそ、ここで得た情報が大きな武器になるかも？

[https://news.ycombinator.com](https://news.ycombinator.com)

「ITエキスパートのための問題解決メディア」というサブタイトルの通り、新人エンジニアが日々の業務で悩んだりつまずいたりする問題を技術的なTipsや仕事術の紹介で解決するブログメディア。

情報インデックスは設計・開発・運用構築といった業務フェーズ、あるいは使用言語や環境別に検索しやすいつくりになっているので、毎日巡回するだけではなく、何か問題が発生した際に辞書引きで使うのも便利です。

[http://www.atmarkit.co.jp](http://www.atmarkit.co.jp)

お役立ち記事