« 最近のイライラ | トップページ | アメリカ人はなぜ福祉が嫌いか »

表計算ソフトでオセロゲームを作る方法

 今回は年寄りの昔話。しかもかなり自慢が入っている。が、若い技術者のためになる教訓もちょっとぐらいは含まれているかもしれない。保証はしないが。

 かつて一度だけオセロゲームを開発したことがある。といっても、多くの人がイメージするような、マシン語ネイティブで動くスタンドアロンのアプリケーションではない。表計算ソフト上のマクロ言語で作ったのだ。

 私が勤めていた会社は、表計算とデータベースを組み合わせたようなソフトを開発していた。当時は統合ソフトなどと呼ばれていたが、今で言えば MS Office や OpenOffice のようなオフィス・スイートに当たる。このソフトには、Excel の Visual Basic に相当するようなマクロ言語が搭載されていて、ある程度の自動処理をユーザー自身がプログラムすることができた。

(ちなみに、私が科学技術シミュレーションのようなものでもつい Excel でやってしまうのは、このころの経験が影響している。いろんな事例を表計算に落とし込む癖が体に染み付いているのである。)

 後に開発にも参加させてもらうことになるのだが、入社当初は、主にテストやバグ出し、ユーザー向けのサンプル事例の作成などを担当していた。そして、そのマクロ言語の応用例としてオセロゲームを作ってみることになったのだ。

・絶望的な遅さ

 しかし、実際やってみると、途端に障害にぶち当たった。とにかく遅いのだ。

 まず試しにプロトタイプとして、盤面全体を走査して、ルール上駒を置けるマスを探すだけのプログラムを作ってみたのだが、遅い。なんとそれだけで数分単位の時間がかかってしまう。これでは思考ルーチンどころの話じゃない。

 携帯電話ですらリバーシが動いている時代の人には想像しずらいかもしれないが、当時の PC 環境はそれほど貧弱だった。まず CPU は 8086 で、クロック周波数は数 MHz。今のCPU の数千分の一程度である。メモリ空間は 1MB で、これも今の CPU の数千分の一。補助記憶装置は 1MB のフロッピーだけ。

 さらにマクロ言語固有の問題もあった。インタープリタだ。今の Java のようにその場でコンパイルするわけでもない。リアルタイムで文字列解析しながら動作する昔ながらのインタープリタ。だからなおさら遅かったのだ。

 普通ならここで諦めてしまうところだろうが、私は当時から障害があると逆に燃えるタイプだったので、なんとかしてやろうと試行錯誤を始めた。

・コードを書くばかりが能じゃない

 まず考えたのは、できるだけインタープリタの負荷を減らすこと。表計算ソフトだから、並べ替えとか抽出とか検索とかの機能はもとから装備されていて、それ自体はマシン語ネイティブで動作している。だから、マクロ言語でアルゴリズムを組む代わりに、そういう機能を呼び出してやれば、少しは速くなるのではないか。

 プログラマというのは、ついなんでもコードで書きたくなるものだが、私は当時からズボラだったので、書かなくて済むものを書かないことに抵抗はなかった。

 さらに徹底的にムダを省くことを考えた。最初のプロトタイプでは、ゲーム盤全体を走査していたが、よく考えると、実際に駒を置ける可能性のある場所は限られている。まず、すでに駒のあるマスには置けない。また、駒のあるマスから離れたマスにも置けない。置けるのは、すでに駒のあるマスに隣接するマスだけだ。だからそれ以外のマスを走査するのは時間のムダである。

・一石二鳥の合わせ技

 先のできるだけ表計算の機能を使うというアイデアと、このムダの省略というアイデアを組み合わせると、こんな方法が考えられる。

 まず盤上のマス目の一覧表を作る。並べ替えや抽出で処理しやすいように、各行が各マスと一対一対応するようにしておく。つまり盤面自体は縦横の二次元だが、それを一次元に展開してしまうのだ。そして各行に、そのマス目や隣接するマス目に駒が置かれているかどうかを記録しておく。たとえばこんな感じ。

そこに駒がある 隣に駒がある
1 1    
1 2    
1 3  
1 4  
1 5  
1 6    
1 7    
1 8    
2 1    
2 2    

 そしてこの表から、そこに駒がなくて隣に駒があるマス目だけを抽出し、そのマスだけを走査すれば、盤面全体を走査するより大幅に計算量を減らせるというわけだ。

・差分による効率化

 でも、逆にこの表を作ること自体に計算量がいるのでは? と思う人もいるかもしれない。

 確かに、一手指して盤面が変化するごとに、表全体を作り直していたのでは、計算量が多すぎてちっとも効率化にはならない。しかし、そんな必要はないのだ。

 なぜなら、盤上の駒の初期配置は決まっているし、一手指す度の変化も決まっているからだ。だから、初期配置に対応した表を作って保存しておいて、一手指す度に必要な行だけ更新すればいいのである。要するに「差分」の発想である。

 たとえば、(1, 4) に駒が置かれたら、(1, 4) に対応する行の「そこに駒がある」の列と、(1, 3)、(1, 5)、(2, 3)、(2, 4)、(2, 5) に対応する行の「隣に駒がある」の列に「○」を書けばよいだけだ。

 試しにこのアルゴリズムを実装してみると、予想通り、プログラムは劇的に速くなった。

 -がしかし、それはあくまで最初に作ったプロトタイプに比べたら、の話であった。しかも、できるのは単に盤上から駒を置けるマスを探すだけのこと。予定ではこの後で思考ルーチンを実装しなくてはならないのだ。やはり実用的な速度のプログラムを作ることは不可能なのだろうか?

・人間の思考法に学ぶ

 ここでヒントになったのは、人間の棋士の思考法だった。当時私は米長邦雄という棋士のファンだった(今では嫌いだが)。氏は当時、プロ棋士の思考法を一般人にもわかるように解説した本で人気を博していた。

 棋士は手を何百手も読む、とは当時から言われていた事だが、米長氏によると、その表現は正確ではないという。棋士が特定の局面で実際に読む手の種類は数手であり、その数手は「直感」で絞り込むのだと。数百手というのは、絞り込んだ後でその先の手を読む数なのだそうだ。

 コンピュータには「直感」はない。これがコンピュータと人間の最大の違いだ。だからコンピュータは人間には勝てないのだ、とよく言われる。当時は、ディープ・ブルーがカスパロフに勝ったり、あからが清水市代に勝ったりするはるか以前であるから、なおさらそう思われていた。

 しかし私は今にもまして無謀だったので、この人間の思考法をなんとかコンピュータに取り入れられないかと必死で考えた。そうすれば計算量を大幅に減らせるではないかと。

 そしてある日、ついに天啓が訪れた。

・逆転の発想

 それはまさに逆転の発想だった。それまで私は、

  1. まず盤上から駒を置けるマスを探す
  2. その中から駒を置きたいマスを選ぶ

という順序でばかり考えていた。しかし、よく考えると、

  1. まず盤上から駒を置きたいマスを選ぶ
  2. そのマスに実際に駒を置けるかどうか調べる

という順序でもいいのではないか、ということに気づいたのだ。つまり、置くマスを「直感」で選ぶのだ。

 何を言ってるんだお前は。盤上を走査もしないうちから、置きたいマスがわかるわけないだろう、と思った人もいるかもしれないが、そうでもないのだ。

 なぜかというと、オセロの場合、優先順位の高いマスは、ゲーム開始時からだいたい決まっていて、それほど変化しないからだ。最も優先順位が高いのは四隅のマスで、逆に最も優先順位が低いのはその隣のマス。四辺のマスも中央のマスよりやや優先順位が高い。

 将棋などの場合、置いた駒が移動したり消えたりするので、盤上のどこが有利かは絶えず変化するのが普通なのだが、オセロの場合には必ずしもそうではない。もちろん、上級者相手になると、相手にわざと隅を取らせるような高等戦術も必要になるが、初級者相手なら、この基本原則だけでそこそこ勝負になる。

 さらに都合のよいことに、ここで先ほど作った表が利用できる。まずこの表に、評価値用の列を追加する。そして各マスの大雑把な評価値を記入しておくのだ。たとえば、こんな具合だ。

そこに駒がある 隣に駒がある 評価値
1 1     100
1 2     0
1 3   80
1 4   90
1 5   90
1 6     80
1 7     0
1 8     100
2 1     0
2 2     10

 そして先程と同じように、置ける可能性のあるマスを抽出したら、今度は、その表を評価値の順序に並べ替える。

 そして評価値の高いマス目から順に実際に駒を置けるかどうかを調べ、置けるマスが1マスでも見つかったら、即座にそこに置いてしまうのだ! そうすれば、それ以降のマスを調べる時間まで省ける。

 自分で言うのもなんだが、このアイデアのすごいところは、高速化と思考ルーチンの実装という二つの課題をまとめて解決してしまったところにある。前のアルゴリズムにさらに思考ルーチンが加わっているのに、遅くなるどころかかえって速くなっているのだ。

・誰も知らない

 もちろん思考ルーチンなどと言っても、単にマス目に優先順位をつけているだけなので、本当の上級者には通用しない。しかし、オセロは囲碁将棋などと比べると子供の遊びだと軽く見られているようで、上級者の戦術を知っている人は意外と少ないようだ。

 そのせいか、このプログラムの評判は案外よかった。ある親会社の人は、さんざん苦戦した末、「このプログラムは案外頭がいいねえ」などと言ってくれた。大企業の管理職でおそらく一流大学出身で本当は頭のいい人に違いない。

 そんな人に向かって、「いや、このプログラムは実は何も考えてなくて、最初に見つかったマスに置いているだけです」などとは言い出せず、ちょっと困ったのを今でも思い出す。

 このプログラムは結局、その会社が出版した事例集に付録として収録された。何の解説もなくソースコードだけが記載されたので、このプログラムが一見人工知能っぽく動いているのに、実際には何も考えていないことに気づいた人がどれほどいたか。そこに気づいたとしても、そんな方法を使わなければ、とても実用的な速度にならないことにまで気づいてくれた人がどれほどいたか。その本も今となってはほとんど入手不可能だ。

 このときに、自分でも不可能に思えたような課題の解決に成功したことは、私自身にとっても大きな自信となった。このことは、その後の私が、次第に「ベジエ曲線を整数の加減算だけで描画する方法」のような困難なアルゴリズムの開発に耽溺してゆくきっかけとなるのたが、それはまた別のお話。

|

« 最近のイライラ | トップページ | アメリカ人はなぜ福祉が嫌いか »

パソコン・インターネット」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/67762/53334582

この記事へのトラックバック一覧です: 表計算ソフトでオセロゲームを作る方法:

« 最近のイライラ | トップページ | アメリカ人はなぜ福祉が嫌いか »