Othello

オセロ

何はともあれ,実際にオセロでコンピューターと対戦してみましょう(JAVAアプレットを動かすための環境が必要です).



ゲームの操作

オセロの画面は次のようになっています.


あなたは黒(先手)です.適当に白い石をひっくり返してみましょう.すると瞬時にコンピューターは一手を打ち黒石をひっくり返してくるでしょう.もう既にその時にはゲームが始まっています.

コマンドは以下の通りです.

BLACK:黒石(先手)で打つことになります.
WHITE:白石(後手)で打つことになります.
level_0:コンピューターのレベルが0(最弱)になります.
level_up:コンピューターのレベルが一つ上がります.
pass:自分の番にパスすることが出来ます.
give up:潔く負けを認めるのも良いでしょう.
?:日本は地震が多い国だと言われています.



コンピューターの頭の中

さて,このコンピューターの頭の中はどうなっているのでしょうか.コンピューターは単に現在の盤面だけを見て次の一手を考えています(相手の顔色や仕草など気にもしていません).例えば,次の図のような場合,白が打てるマスを探し,そのマスに白石を置いた場合にどのくらい有利な盤面(状態)になるか点数をつけます.そして,素直に一番点数の高い13点の状態に遷移するマスに白石を打ちます.いくら変な手(人間では絶対に打ちそうもない手)でも,点数が高ければそれを選択します.

こういった場合,点数のつけ方が重要になってきます.そこに石を置く操作で盤の状態が変わるので,次の状態が有利ならばその操作の点数は高く,不利ならば低くなるべきです.つまり,この有利な状態・不利な状態をどう数値化するのが重要になります.

例えば,次のようにある状態に点数をつけてみたらどうでしょうか.

少し考えてみれば分かることですが,実際は全くうまくいきません.上に挙げた3つだけでなく,もっと複雑で多くのルールを追加しても結果はあまり変わりません.理由は短期的な評価だからです.例えば,一見よさそうな手でも,何手か先において,相手に形勢逆転されてしまう可能性があるからです.つまり,数手先を呼んで長期的な評価をする必要があるのです.



より強くするためには?

ゲーム木(状態遷移図)を描いて,数手先を読みながら現在の状態の得点をつければ,オセロの場合は,まあまあ強くなります.究極的に言えば,最後まで読みきればよいわけです.ただし,一手読むごとに調べる状態は指数関数的に増えてきますのでコンピューターの計算能力・メモリなどに合わせて,現実的になんて先にするか決定されるべきでしょう.これらに関しては様々に研究されていますので検索してみるのも良いでしょう.例えば,“ミニマックス法”やその探索方法を効率化した“アルファベータ法”などを調べてみてください.



他へも応用できるか?

このデモプログラムに負けたなんて人はいないと思います.ただ,その辺に転がっている他のプログラムはとても強く,何度やっても勝てません.オセロというゲームでは人間はほぼ完敗です.

それでは,似たようなボードゲームのチェス(8×8=64マス),将棋(9×9=81マス),囲碁(多くのマス)ならどうでしょうか?上で挙げた方法と同じというわけではありませんが,1997年に,IBMのコンピューター,ディープ・ブルーがチェスの世界チャンピオンのガルリ・カスパロフにチェスで勝っています.さらに将棋ソフトもアマチュア5段程度の実力をつけて,「プロ棋士と勝負するには連盟の許可が必要」という制限が出るまでになっています.囲碁はせいぜい初心者より強い程度だと話に聞いたことがあります.

どうも,強さは盤のマスの数に関わりがあるようです(もちろん,駒の種類やルールの複雑さもあるとは思います).何手か先の状態を読むときにマスの数が多くなればなるほど膨大な計算を必要します.状態数がある程度以上に多くなると,もうこの方法では現実的にかなり難しくなってきます.