はじめに
オセロゲームは、2人零和有限確定完全情報ゲームという種類のゲームです。この種のゲームには、囲碁や将棋チェス、五目並べ、三目並べ等があります。
2人零和有限確定完全情報ゲームは、理論上では必勝法が存在します。三目並べに必勝法が存在することは、比較的簡単に確かめることができます。囲碁や将棋、チェスなど、このゲームに属するものは他にもありますが、ほとんどのゲームでは必勝法が未だ解明されていません。三目並べの必勝法が判明しているのは、手数が少ない（ゲーム木が小さい）からです。
このページでの目的は、強いオセロゲームのプログラムを作るための方法を調査/検討することです。
（気が向いたら･･･時々更新します(笑)）
手の探索
現在のコンピュータの能力では、すべての手を読むにはとても長い時間がかかり、非常に困難なので、ほぼ不可能だといえます。したがって、可能な範囲で先の手を読み、その中から最も良さそうな手を選ぶことになります。具体的には、何手か先読みをしてゲーム木(探索木)を作成して、それぞれの末端の局面で形勢の数値化を行い、その値が最大になるような手(最善手)を探索することになります。この形勢判断のための計算式を静的評価関数といいます。「静的」とは先読みを行わずに、その局面の形勢を直接評価することを意味します。
局面の評価は一般的に難しく、正確な静的評価関数を作ることは困難です。正確な静的評価関数が存在するということは、その関数の評価値が最大になるような手を指し続ければ、必ず勝つことになります。言い換えれば、そのゲームの必勝法が分かっているということです。
プログラムを強くするためには、できる限り正確な静的評価関数を使って工夫することが重要です。また、関数を複雑にすれば評価も正確になりますが、それだけ探索に時間がかかることにもなります。
評価関数
|
オセロゲームは打てる手の数がそれほど多くはなく、しかも終局までの手数が他の盤ゲームに比べ少ないので、コンピュータ・ゲームには極めて適したゲームの1つです。オセロゲームに用いられる評価関数としては、次のようなものが考えられます。 (1)盤面上の位置の評価値 盤面の石の位置によって評価値を与えるのは一般的な方法です。たとえば、隅にある石は相手に取られることはないので、隅を取ると有利になることが多くなります。また、隅の隣または斜めのマスに打つと、相手に隅を取られて不利になることが多くなります。したがって、隅には高い点を、その隣と斜めには低い点を与えるのが妥当です。 (2)石の打てる位置の数 石の打てる位置の数の多少によって評価する方法とは、相手の打てる手の数を少なくするような手に対して良い評価を与える方法のことです。相手は打つ手がなければパスをしなければならないので、有利となるからです。これは、他のチェスや囲碁などの盤ゲームとは本質的に異なる性質の1つです。 (3)不変石（確定石）の数 不変石の多少による評価は、その局面での直接的な評価となります。不変石とは、ゲームが進んでいっても、この先相手に取られることのない石のことをいいます。不変石は隅にある場合と同様、この先相手に取られることはないので、不変石の数で優劣を決めるのは良い方法です。不変石を評価関数として用いる場合、相手に取られる石の数を少なくできる利点があります。 これらの他に、その局面での双方の石の数を評価値とする方法も考えられますが、オセロゲームにおいては敵味方の石が取ったり取られたりするので、このような評価方法はあまり適切ではありません。 |
 盤面上の位置の評価値の例  不変石（確定石）の例 （◎の石） |
序盤，中盤，終盤の判断と戦略
オセロゲームにおける評価関数は、盤面上の位置に対応して、8×8の盤面上のマスに対して与えるのが一般的な方法です。たとえば、隅に石を置くことはオセロゲームにおいては重要なので、このマスに高い評価値を与えます。それに対して、隅の隣や斜めのマスに石を置くと隅を取られてしまう恐れがあるので、隅の隣と斜めのマスには低い(マイナスの)評価値が与えられる必要があります。しかし、すでに隅に自分の石が置かれている場合は、隅の隣は他のマス目と変わりないので、負の評価値を与える必要はありません。つまり、局面によって評価値は変わるはずです。そこでゲームをいくつかの局相に分割して、その局相ごとに評価関数を変えるということを考える必要があります。最も簡単な方法は、局相を序盤、中盤、終盤の3相に分けることです。
判断方法
|
序盤、中盤、終盤の移行の判断方法としては、次の2通りが考えられます。 (1)一定の手数の経過 オセロゲームは他の盤ゲームとは違い、最大60手となることが決まっています。そこで、一定手数で中盤、終盤に移行するような方法をとることがあります。この方法では、盤面の状況とは一切関係なく、手数で序盤や中盤、終盤の判断を行うので、誤った手により問題が生じることがあります。たとえば、終盤に移行する前に、盤上の石がどちらかの色で占められる（勝つ）ことがわかる場合には、終盤と判断して探索を行うべきですが、手数だけで判断している場合では、序盤や中盤の方法で探索を行うことになります。 (2)ある場所に石が置かれたとき 例として右図のようにマスに名前をつけると、aの位置に石が置かれた時に中盤へ移行し、c1からc4の位置に石が置かれたときに終盤へ移行するという方法です。これは、aの位置に石を置くことにより、どちらかが端の行または列に石を置くことができ、隅の隣か斜めの位置に石を置くことにより、どちらかが隅を取ることができるからです。ただし、早い段階に隅から斜めの位置に石を置いたときに、終盤判定を行ってよいのかという問題があります。 |
 序盤，中盤，終盤の判断方法 |
互いに長所と短所があるので、この2つの方法を組み合わせることにより、次のような方法で序盤、中盤、終盤の判定を行うべきだと推測できます。
(ア)bの場所に石が置かれる
→序盤から中盤へ移行
aではなくbに置かれた場合に中盤へ移行としたのは、aに石を置いたとしても、次の手が必ずしもbの場所(端の行または列)に置かれるわけではないからです。オセロでは中盤の戦略として、端を確保することは重要な意味を持ちます。端を確保することにより、周りから攻めることができるからです。
(イ)30手以降で、2つ以上の隅に同じ色の石が置かれている
→中盤から終盤1へ移行
自分あるいは相手が手を誤ることにより、30手以降ですでに同じ色の石が隅に2つ以上置かれている場合、大抵の場合は勝ちが確定しています。この場合には、本来の中盤や終盤とは異なった戦術を取る必要があります。
(ウ)44手まで経過
→中盤もしくは終盤1から終盤2へ移行
すべての隅とその隣や斜めのマスの数は16なので、これらのマス以外に石を置いていくと、最大44手まで進めることができます。したがって、遅くても45手目には終盤判定を行う必要があります。
序盤，中盤，終盤の戦略
序盤から中盤にかけての戦略としては、中盤から終盤において有利に進めるための前準備を行うことを考える必要があります・具体的には、相手が石を打てる位置の数を少なくするように手を取る方法が有効です。これは、石を打てる位置の数が多ければ、好手のある可能性が高くなり、結果として不利になるからです。
終盤では、単純に石をたくさん取るという目標があるので、ゲーム終了時に最も石が多くなるような手順の探索を行います。
探索手法
ゲーム木を探索する場合、可能な全ての指し手を読む、または、いくつかの見込みのありそうな指し手の先を読むという選択があります。前者の場合を全幅探索、後者の場合を選択的探索といいます。全幅探索は重要な手をもらす危険性はありませんが、評価する局面が膨大になるため、あまり深く読むことができません。それに対して、選択的探索は見込みのありそうな指し手のみ探索を行うので深く読むことができますが、候補を絞る段階で重要な手を見逃してしまう恐れがあります。
全幅探索であっても選択的探索であっても、ミニマックス法が基礎となっています。しかし、ミニマックス法には、一つの解を求める場合には冗長な部分が多く、計算時間がかかるのであまり深く探索できないという短所があります。この短所を改良した方法として、ゲーム木から実際には指さないような手順を探索しないように枝刈りをして、探索の効率化をおこなうαβ法や反復深化法があります。
ミニマックス法
ミニマックス法は、ゲーム木から次の候補手を選択する方法の基本です。ミニマックス法では、ゲーム木のすべての節点に以下のルールで評価値を与えます。
この２つを用いることにより、互いに最善を尽くしている場合の、次に取るべき手を導き出すことができます。すなわち、探索した次の局面の評価値が最大になる指し手が、現在局面においての最善手となります。
人もこれを同じようなことを行っていますが、コンピュータの場合には問題があります。人の場合は、実力や心理状態に応じて評価する手段が異なりますが、コンピュータの場合は、相手の手も自分と同じ評価関数を用いて探索を行っているからです。また、人の場合は、最善手を取らずに次善手（2番目に良いと判断した手）をあえて打つ場合があります。最善手を取り続けたからといって、必ず有利な局面に運べるとは限らないからです。
αβ法
上に示すゲーム木を例として、枝刈りについて説明します。
ミニマックス法を用いて局面を評価していくとき、読む必要のない手のあることがわかります。上の図のゲーム木をB→Eと、左から順に読んでいきます。Eの局面で、その先の評価を終えたとき、ミニマックス法の原理によって評価値の最大を求め、＋2が得られます。次にFの局面でOの手を読んだ結果、+5の評価値が得られたとします。この時点でFの局面の評価値はPの評価値に関係なく、最低＋5である保証が得られます。Bの局面は後手番で、最小値を求めることになるので、この時点では、局面Bの評価値はEの＋2となります。この方法で探索を進めることで、P、R、S、Uの枝刈りを行うことができます。この枝刈りをβカットといいます。さらに探索が進み、Jの局面で＋1の評価値が確定したら、Dの局面の評価値は＋1以下となり、K以降の局面は調べる必要がなくなります。この枝刈りをαカットといいます。
このような方法を用いて枝刈りを行うことで、ミニマックス法と同じ結果が得られ、しかも探索時間を短縮できる利点があります。
反復深化法
反復深化法は、ミニマックス法とαβ法の利点を持ち合わせた探索方法です。この探索では、深さ優先に探索が進められますが、深さに上限が設定されていて、最初は0、次は1、その次は2というように、少し調べては有力手を候補に選び、再び少し深く調べては有力手を探すという形で、徐々に深い深度まで調べていきます。深さに制限を設定することにより大量のメモリを必要としないという深さ優先探索の利点を保ちながら、無限ループに陥ることを回避しています。また、ミニマックス法のように解が存在する場合に、その解を見つけることも保証されます。一方、多くの状態が何回も展開されるので無駄が多いように見えますが、実際にはほとんどの場合において、複数回展開するのに必要なオーバーヘッドはかなり小さくなります。
探索の高速化
先読み探索のスピードを高めることは、一般的に実力の向上に貢献すると言われています。「一般的に」というのは、探索を高速化することにより、同じ時間内でより多くの局面を調べることができますが、コンピュータも人間同様、先を読みすぎたためにかえってまずい手を選択する場合があるからです。歴史的に見て、αβ法の効率化をさらに向上させるためのヒューリスティクス（発見的手法）がいろいろ提案されています。有力なものとしては、前の局面で先読みした結果を利用するという方法があります。
上の図のゲーム木において、1手前の局面で3手先まで探索していたとすると、今回の探索は1手先（B、C、D）のところまで探索が完了しているといえます。新たにゲーム木を作成するとき、1手前の局面のＡにおけるB、C、Dでの探索結果を利用して、この中から最も大きな値（最善手）と判断した手順から探索を行うことで、探索の効率化を図ることができます。
この他の効率化の方法として、前向き枝刈りというものがあります。探索を行うときに、調べる手が多すぎると、あまり深く読むことができません。そこで、見込みのありそうな手以外を読まないようにするのが前向き枝刈りです。見込みのなさそうな木の一部を枝刈りすることで枝が少なくなった分、より深く読むことができるようになります。しかし、見込みの高い手を選ぶ段階で、重要な手をもらしてしまう危険もあります。そこで、どのような枝刈り方法を選ぶかが問題となりますが、一般的には評価値の高い手を選んだり、経験的知識を用いて選んだりします。
定跡データベースの利用
序盤戦略としては、過去の指し手（例としては、名人レベルのエキスパートらによる指し手）、言い換えると、定跡のデータベースを利用することは有効な作戦です。序盤では、プログラムが先読みをして手を選ぶのは、最善手はともかく、それなりの手でさえも簡単ではありません。そこで定跡データベースを作成し、それを序盤の思考ルーチンで参照することで、探索の簡略化を行うことができます。
さいごに
オセロゲームのプログラムを強くするためには、まだ多くの課題が残されています。例としては、評価関数の改良が挙げられます。手の位置を評価関数とする場合、隅と隣および斜めの評価値のバランスが悪いと、隅を取ろうとして、反対に相手に取られる危険があります。また、序盤から相手の石を多く取る手を続けていくと、終盤には不利になることが多くなるので、評価関数として獲得可能な石の数を用いる場合には注意をする必要があります。
探索時間はアルゴリズムの改良により短縮されてきていますが、一本筋の手しかないような場合においても、そのことを判断できず、これまでと同じように探索を続けてしまうという問題もあります。また、攻めるか受けるかの戦略的判断も必要です。
より強いオセロゲームのプログラムを作るには、これらの課題を解決する必要があります。