Happy Hacking Keyboard(HHK)とか、キーボードの配列とか。
HHK
MacBook用に、HHK ProのType-Sを購入。初めてのJIS配列。
Jis配列固有のキーを使うショートカットなどを色々と定義しているのもあり、キーがー多い方が幸せ度高いんよね。
(VMで使っているWindowsと合わせたいという指向も。)
これで、ファミレスに篭もるときも、RMSスタイルで快適に…。
ここ最近はお仕事としてコードを書くことはしていなかったものの、HHK触っていると昔の感覚を思い出してちょっと嬉しくなる。
歴代HHK
ついでに家の中を発掘。:)
一番上は初代。 bit誌で存在を知り、その発売と同時に買ったのでした。もはや、色が年期入っちゃって小汚いですが…
家、研究室、会社と置いていたので、これ以外にも幾つか購入しているのではないかと思う。
今は打ちやすいコンパクトキーボードとしての売りのみとなってしまっているけれども（それだけ選択肢が増えたと言うことだけれど）、あの頃ははSunのType-5のキーボードがくそ大きかったこともあり、AT機でもSunでも、同じ配列で、打ちやすい高見澤製のキーボードが使えるというのが「売り」。
計算機を選ばずに同じキーボードを使えるということで、本当にお世話になりました。
キーボード配列について
プログラマはASCII(英語)配列であるべきだー、という主張をする人がいるけれども、その理由としてEnterキーが近いから打ちやすいとか、記号の配置が云々とか、見た目がスッキリとか、いう理由が挙げられることが多いように思う。
個人的に納得感があるのは見た目がスッキリくらいで、後は単なる慣れのような。
キーボードのmapping入れ替える設定が面倒だから101とかは、実務的に納得感は高いけれども。
また、効率性という観点では、ある程度触っている人が何かをキーボードの配列を理由にするのは情けないのではないかと個人的には思うところ。
実際のところ、ちょっと使っていればASCIIでもJISでも配列なんて覚えるだろうし、何れともストレス無くタッチタピング出来るだろうに。（未だカナだってタッチタイピングで打てる。）
ましてや「Enterが近い」なんて、ある程度効率性を求める人であればCtrl + mとか使うだろうから、そもそもそんなに気になるものなのか疑問でして。
というわけで、ただ単なる慣れという問題であって、他人に強いるような物でもないような気もするのだけれども。
ボードゲームの思考アルゴリズムの入門
社内の技術系Adventカレンダー向けに何か書けと言われ、とりあえずボードゲームの思考ルーチンについて書いてみたり。
せっかくなので、存在を忘れかけていたBlogメンテの意味も込めてこちらで公開。
ボードゲームをプレーする=知能?
ボードゲーム、その中でもチェスをプレーするということは、非常に人間的な行為であると思われてきました。チェスをプレーするということは知的であり、創造性を要する、極めて複雑な問題であり、人間にしかできないと思われていたわけです。
そんな知的な作業をコンピュータが行うことが出来れば、これは人工的に知能を実現したということだ、ということで、ある種の目標となり、歴史的なコンピュータサイエンスや人工知能の研究ではチェスは度々登場します。
チェスのアルゴリズムの振り返り
ご存じの通り、1996年にはチェス世界チャンピオンであるカスパロフと、IBM製のDeepBlueが対戦をし、コンピュータが勝ちました。(ここら辺はチェスファンからすると異論もありますが、ある種の節目ではありました。)
Wikipediaにもあるように、1840年バベッジ*1の頃から構想はあり、どれが初めてのチェスアルゴリズムと言って良いか分かりませんが、1951年にチューリングが手計算でチェスアルゴリズムと人間の対戦を行ったところを初のチェスアルゴリズム登場と見なすならば、かれこれ45年の歳月がかかったわけです。
人工知能としてのボードゲームの思考ルーチン
「人工知能研究は、常に未解決問題」と言われることがあります。
これは、問題を定式化し、計算というタスクに落とし込むと、結局は特定の問題に帰着し別分野として確立をしてしまうからです。
例えば最近の例で言えばGoogleの自動運転であったり、今日では実用的となっている機械学習など、様々な分野が元々は人工知能研究のテーマでしたが、今では別分野として確立をしています*2。
同様にチェスなどのボードゲームも、コンセプトを重視するなら「思考」と擬人化した表現をしたくなるものの、アルゴリズムは今日ではゲーム理論と計算機科学における単純な探索問題となります。
オセロのアルゴリズムのざっくり説明
ボードゲームの中でも、ルールが単純な、オセロについて簡単に。
ゲーム木探索
ボードゲーム探索の基本的な考え方は、「可能性のあるパターンを先読みして、最終的に最も良くなる状態の手を選択」するという方法です。この基本は、オセロのみならず、将棋、チェスと全て変わらずに同じです。
先手を四角(□)、後手を丸(○)とすると、図1のように可能性のあるパターンを全て羅列します。この例では、2手先まで先読みを行っています。
そして、「先手、後手共に、常に最善の手を打つ」という前提のもと、先読みをした範囲から「最も良い結果」となりうる最善手を目指して手を打ちます。
- Fig ゲーム木のイメージ
評価関数
盤の状態がどちら側にとって、どの程度有利なのかということを定量的に比較するために、評価関数を用いて点数化をして判断します。先手に有利であれば有利な分だけ正の点数、後手に有利であれば負の点数、そして完全に互角であれば0を返す関数です。
この評価関数の「出来の良さ」というのは、プレーをしたときの強さに最も直接的に影響します。オセロの場合は、2手先の先読みだけであっても、評価関数さえ良ければ一般的なオセロをちょっと指したことある人が勝てないレベルにはなる、と言われています。
今回は、オセロで単純な例として、置いている場所から点数化をする例を紹介します。
例えば8×8の盤に対して、以下のような点数を振ります。 (この点数の付け方は経験的なものであり、必ずしもこれが強いわけではありません。)
- Table オセロの評価関数用の点数の例
それぞれ石が置いてある場所の点数の合計(後手は有利なほどマイナスなので、× -1をして評価)によって、点数化します。
評価値 = Σ(白の石が置かれている箇所の点数) ＋ -1 × Σ(黒の石が置かれている箇所の点数)
人間の判断だけで、精度の高い評価関数を作成するのには限界があります。
応用として、この評価関数自体を機械学習(具体的には強化学習)の枠組みで、学習器によって「学習」する仕組みが可能です。
つまり、自らプレーを通じて試行錯誤しながら強くなっていくという、実に人間らしい仕組みです。
MinMax法
全ての可能性のある指してのゲーム木と、評価関数を用いて、これらをもとに最適な次の指し手を決定します。
完全情報ゼロ和ゲームと呼ばれる種類のゲームに対しての最適戦略を求めるゲーム理論の方法の1つです。
手順は以下となります。
- まず、ゲーム木を探索し(この場合は2手先まで)、その結果を「1.評価関数で点数化」を行います。 次に、この評価値をもとに探索を行います。
- 先手を四角(□)、後手を丸(○)とすると、先手にとってはよりプラスの評価値ほど良い、後手にとってはよりマイナスが良いわけです。 一番底の評価値から、以下のルールに従い探索を行います。
- 「四角(□)のノードでは、取りうる選択肢から最大値を選択」
- 「丸(○)のノードでは、取りうる選択肢から最小値を選択」
この手順に従い探索を行うと、図の赤い矢印のように-3へ続く手筋が選択されるわけです。
この手順を繰り返すことで、先読みの深さにかかわらず、最適解を導くことができます。
ここで「先手にとって最も良い点数は、左下の+25だ。なので先手は、一番左を選択するべきでは？」という疑問が出てくるかもしれません。
仮に先手が一番左を選択したとすると、次の後手は{+25, -5, -9}という選択肢が与えられます。後手の選択では最も有利となる-9を選択することになるため、+25は選択されません。
つまりこのアルゴリズムは、お互いに「合理的」な意思決定をした場合にたどり着くことが可能な範囲から、最も良い手を選択するアルゴリズムとなります。
ちなみに、、この探索ですが、ちょっと考えると、実は無駄な探索をしているということに気がつかれた方もいるかもしれません。
実は、必ずしも全てのノードを探索せずとも、同じ解を得ることが可能です。 このMinMax法を枝刈りして計算量を減らした方法としてαβ法という手法もあります。
現在の第一線のチェス、将棋ソフトでもαβ法を基本として探索をしています。
オセロ、チェス、将棋、囲碁の探索問題としての「難しさ」
オセロは、90年代の後半に、日本人チャンピオンの中島さんとPCが対決をし、6対0で人間が完敗してしまいました。
しかも、ただのPentium Pro×2のSMPというちょっと早い程度のPCでした。( 人間側チャンピオンの中島さんの「一度くらい、いい試合をしたかった」というコメントが印象的で、そこからも強さが伝わってくるかと思います。)
チェスもまた、1996年にDeepBlueという計算機クラスタにより、人間に一応勝ちました。
将棋も、2013年になり、人間に勝つ兆し(事実上勝っている?)が出てきました。
この順番というのは、コンピュータが探索をしなくてはならない局面数の大きさによっておおよそが決まっています。
各ボードゲームの局面数をざっくり推定をすると、以下のようになります。 (10の360乗というのは、0が360個ということです、念のため。)
オセロ : 10の56乗
チェス : 10の120乗
将棋 : 10の220乗
囲碁 : 10の360乗
非常に膨大な探索空間です。 探索をするという観点では、仮にコンピュータが10倍速になったとしても、せいぜいさらに数手先まで深読みが出来る程度の違いしか無かったりします。
そういう意味では、コンピュータの「早さ」の進歩も大事ながらも、適切な評価関数であったり、棋譜のデータを取り入れたりといった試みの方が大事だったりもします。
ちなみに、現在、最もホットな領域の1つが「囲碁」です。 上記の局面数を比較すると、囲碁だけが桁違いです。
これは、19×19と盤が広く、好きなところに置けるので局面数も広いことが理由で、また探索をする上でも、評価関数が非常に難しい(たった一手によって形成が逆転をしたりと安定せず、また形成の判定に地というパターン認識が求められるためスコア化が極めて行いにくい)ということが主な理由です。
そのため、ちょっと前までは、今までのゲーム木探索というアプローチとノイマン型計算機である限り、囲碁プログラムは人間には勝てないと言う研究者もいました。
しかし最近になり、確率的なアプローチでプレーをする「モンテカルロ囲碁」という方法が出現し、突如、囲碁のレベルが上がりました。
これは簡単に言ってしまうと、ランダムに手を指して、確率論的に勝つ確率が高いところに打つ、というような方法論です。
ある意味、成熟したと思われていた分野で、この様なイノベーションが起きるというのも面白いですし、今後の動向から目が離せないのでした。
作ってみた(実装編)
というわけで、上記のアルゴリズムに従って、とりあえず作ってみたものをご紹介します。
とはいえ、幾つかを単純化をしています。
ボードゲームでは、途中までの打ち手の順番は異なっても、最終的には同じ盤面になることが多々発生します。 であれば、ゲーム木をlink listで表現し、一度探索した盤面の状態をhashから辿れるようにすることで、次回以降は同じ盤面が出てきても計算と探索を省けるわけです。また探索も幅優先探索をしながら、許されている持ち時間の中で深く掘り下げると言う方が効率的です。 しかし、ここでは実装の単純化のため再帰関数による深さ優先探索とします。
ソフトウェアは壊れない。
Siri と Elizaで会話
Siriと、カウンセリングを模した古典的な会話プログラムのElizaを会話させてみたよ、というネタ記事。
大分前なのだけれど、たまたま発見。
Since I got my iPhone 4S, I’ve been intrigued, fascinated and alarmed by Siri’s fast-growing capabilities. I thought it would make sense to introduce her to my psychotherapist, Eliza.
Elizaの方が、しっかりと「会話」をしているように見えてしまう。
いや、実はSiriは、ボケて笑いをとるという、あるいみ高度な知能処理なのかもしれない。(なーんて)
ELIZAは初期の素朴な自然言語処理プログラムの1つである。スクリプト (script) へのユーザーの応答を処理する形で動作し、スクリプトとしてはDOCTORという来談者中心療法のセラピストのシミュレーションが最もよく知られている。人間の思考や感情についてほとんど何の情報も持っていないが、DOCTORは驚くほど人間っぽい対話をすることがあった。MITのジョセフ・ワイゼンバウムが1964年から1966年にかけてELIZAを書き上げた。いわゆる人工無脳の起源となったソフトウェアである。
ソフトウェアは劣化しない
と、ふと当たり前のことながら、ふと意識したのが、「ソフトウェア」は「劣化しない」ということ。
Elizaだって半世紀くらい前に書かれた「ソフトウェア」だ。
たしかACMだっかのチューリング生誕記念の催しで、ロシアのKasparov(DeepBlueと対戦したチェスのチャンピオン)と、チューリングが作ったチェスの対戦アルゴリズムが対戦をするというイベントをしていたけれども、これも表現がBinaryではないというだけで、立派なソフトウェアだ。
ソフトウェアは劣化しない。 そして50年後にも動かされるかもしれない。 うん、まぁあたり前というか、何を今更なのですが。
M-x doctor
お手元のemacsで、M-x doctor とすればElizaを動かせます。:)
オススメ本 / 「エキスパートCプログラミング―知られざるCの深層」
SunのOSとCompiler開発チームの作者が書いた、Cプログラミングの本。
Cプログラミングと言いながらも、実際にはUNIX OSのKernelに関してや、アーキテクチャについても触れられている。
エキスパートCプログラミング―知られざるCの深層 (Ascii books)
- 作者: ピーターヴァン・デ・リンデン,Peter van der Linden,梅原系
- 出版社/メーカー: アスキー
- 発売日: 1996/03
- メディア: 単行本
- 購入: 17人 クリック: 404回
- この商品を含むブログ (72件) を見る
出版されたばかりの頃に購入をして、もう本当に目から鱗が落ちた本。
今までのモヤモヤした悩みが一気に消えたのを未だに覚えている。
例えば、segmentation fault と bus errorの違いを初めて知ったのもこの本のおかげだし、Pointerのモヤモヤが完全に消えたのもこの本のおかげ。 そして、そこの背景の説明から計算機アーキテクチャについても視野が広がるという。
今なら、Webを探せば日本語でも情報を見つけることも出来るかもしれないけれど、当時は日本語での情報量も今ほどは充実していなかったし、英語ではあったけれども当時は高校生で英語もあまり出来なかったし。(man で読むのも一苦労)
何より、この本の「ノリ」はhackers dictionaryみたいな感じで、読んでいて「面白い」。笑って読める。
最近、英語版を手に入れる機会があり、改めて読んでみると再発見があったり。
Cの型(type)の読み方の部分あたりは、むしろ英語版で読んだ方が分かりやすいと思う。
並列分散プログラミングとか、高速化とか。
MPI関連を探していて発見した、良質な講義ドキュメント。
MPI、OpenMP関連、及びその組み合わせについての説明。
また高速化チューニングあたりで説明されている話は、計算機アーキテクチャを理解していないとなかなか触れる機会がない話でもあるし、せめてlow layerのコードを書く人ならば知っておいてほしい内容。
目次は以下。
第１回 プログラム高速化の基礎
［配信講義］ CMSI計算科学技術特論A — CMSI web
第２回 MPIの基礎
第３回 OpenMPの基礎
第４回 Hybrid並列化技法（MPIとOpenMPの応用）
第５回 プログラム高速化の応用
第６回 線形代数演算ライブラリBLASとLAPACKの基礎と実践１
第７回 線形代数演算ライブラリBLASとLAPACKの基礎と実践２
第８回 高速化チューニングとその関連技術１
第９回 高速化チューニングとその関連技術２
第１０回 行列計算における高速アルゴリズム１
第１１回 行列計算における高速アルゴリズム２
第１２回 古典分子動力学法の高速化１
第１３回 古典分子動力学法の高速化２
第１４回 量子化学計算の大規模化１
第１５回 量子化学計算の大規模化２
