こんにちは、筆無精の牧野です。お久しぶりです。
PHPの話題を期待していた人、すみません。
一応、技術っぽくアルゴリズムについてですが、PHPとは全然関係ありません。。

先日（といっても、もう先月だったかな）、将棋に詳しい友達から、将棋のトッププロとコンピュータの対局が行われたという話を聞きました。
結局プロが勝ったのですが、コンピュータも相当善戦したそうです。
チェスでは既にコンピュータが勝っていますが、将棋でもこんなに差が縮まっていたとは。。驚きました。

チェスと将棋では完全に読み切るまでの計算量でいうと10の100乗倍くらいの差があり、将棋の方が遙かに複雑です。
ちなみに、完全読み切りはチェスはおろか、オセロでも無理だと言われています。

今回は、こういった思考ゲーム
・勝ち負けが必ず決まり、
・運の要素（不確定要素）がなく、
・相手の情報が全部わかっている
のアルゴリズムについてです。

完全読み切りができる終盤は問題ありません。全ての手を最後まで探索できるなら、最善手は絶対見つけられます。
問題は、序盤、中盤です。
まず、局面が自分にとってどれくらい有利か、不利かを判断する関数（評価関数）が必要です。状況を判断できなければどうしようもありません。
その上でコンピュータがとる戦略は、ミニマックス法と呼ばれるものです。
相手が常に（相手にとっての）最善手を打った場合、自分が取り得る最善手を探す、というアルゴリズムです。

図の数字は評価関数の値で、数が大きいほど自分が有利な状況を表します。
値は下から順に決まっていきます。自分が打つ時は大きい方を、相手が打つ時は小さい方を選びます。
図の場合、左の方がいい手だということになります。
上の図では全パターン調べていますが、本当は全部調べなくても結果がわかります。
左から順番に探索していった場合、次の図で赤線で囲んだ部分は調べる必要がありません。

このようにミニマックス法から調べなくてもよい部分の探索を省くようにしたアルゴリズムをα-β法といいます。

先読みの基本はこんな感じです。あと、序盤、中盤に使えるのに定跡（定石）の利用があります。
もともと善い手とわかっている展開、定跡についてデータを持っておいて、その通りに進んでいるうちは探索を行わないようにするのです。

アルゴリズムの基本はこれくらいですが、実際はなかなか難しいです。

・読める手数の限界
複雑なゲームになるほど、読める手数が短くなります。
そうなると、例えば一時的に局面が悪くても、後で逆転する、というような手は打つことができなくなります。

・評価関数の的確さ
そもそも、局面を正しく評価すること自体が困難です。
評価関数では高評価でも、実はとんでもない悪手というのを一度でも打ってしまうとその後の挽回が不可能、というような場合もよくあります。

それでも、定跡が使える序盤、読み切り可能な終盤の範囲はコンピュータの進化とともにますます広くなり、アルゴリズムも改良されていくので、コンピュータは急速にもっと強くなっていくはずです。
中盤から先、読み切りのできないところまでの間をどうやって強くしていくかがポイントになるのかな。

ちなみに、オセロだったら単純な評価関数（打てる場所の数と、石を置いた場所による得点くらい）でかなり強いプログラムを作ることができます。
興味と時間のある人は自分で作ってみるとおもしろいと思います。