オセロゲーム開発 ～ミニマックス探索法～

このサイトでは、C言語でのオセロ（リバーシ）のプログラム開発方法を解りやすく説明しています。初級者、初心者でも作れるオセロ実装のコツが満載です。

リバーシは自分と相手との成績争いです。一般にゲームをコンピュータで解く場合には、「ゲーム木（グラフ）」を作り、その木（グラフ）の上で最適な解を探索する方法をとります。

評価値探索では、相手が最善手を打ってきたら困るけれど、もしミスをしたら一気に形勢が変わるような勝負手、といったものは考慮しません。

Minimax（ミニマックス）探索法

ゲームは、自分にとっては最も有利な手を自分が打ち（max）、次に相手が自分にとって

最も不利な手を打ち（min）、それらが交互に繰り返されることによって成り立ちます。

例えば下図の3手先読みを考えてみましょう。一見、自分にとっては最も有利な手は「 7 」ですが、「 7 」を評価値として選択しても良いのでしょうか？

図1　Minimax 実行例

まず「S」→「A」→「C」とゲーム木を探索していきます。

そして、自分にとっては最も有利な手である「 5 」を選択して「C」に返します。

図2　Minimax 実行例

この状態では、まだ他の枝を探索していないため終了しません。

同様に「S」→「A」→「D」・・・とゲーム木を探索して、自分にとっては最も有利な手を選択します。

図3　Minimax 実行例

この状態で、確かに自分にとっては最も有利な手は「 7 」だと判断できます。

ただし、3手読みをしているので、相手が「 7 」を簡単に選ばしてはくれません。相手は、自分にとっては最も不利な手である「4」を選択するかもしれません。

このため、次に相手の番を考慮し「S」→「A」・・とゲーム木を探索して、自分にとっては最も不利な手を探索していきます。

図4　Minimax 実行例

最後に、自分の番なので、「 A=5 」と「 B=4 」を比較して今度は自分にとって最も有利な手を探索します。

図5　Minimax 実行例

このゲーム木の評価値探索で選ばれる結果は、最終的には「 5 」だと分かります。

以上のように、先手・後手の双方が互いに最善を尽くすと仮定して、その上で自分にとって最も有利になるように手を選ぶ手法です。

プログラム例

このMinimax 探索法をプログラムで記述する場合は、再帰を利用します。

int Minimax(局面 node, 手番 turn, 先読みの深さ depth){

  /* 葉の場合、評価値を返す */
  if(depth == 0) return eval();

  /* 現在の局面から1手進めた状態をa1,a2,a3・・akとする */
  expand_node(node, 次の turn);

  best = -INFINITY;
  for(i=0; i<k; i++){
    val = Minimax(ai, 次の turn, depth-1);
    if(turn == 先手 && best < val)  best= val;
    if(turn == 後手 && best <-val)  best=-val;
  }

  return best;
}

eval() は、その時の盤面で局面評価を行い、評価値を返す関数です。

また実際の処理には、パス判定なども必要となってきます。

Negamax 探索法

Negamax 探索法は、基本的な考え方はMinimax 探索法と同じです。

図6　Minimax 実行例

違うのは、相手はこちらの利益を最小にするように打つのではなく、自分自身の利益を最大にするように打つというところです。

int NegaMax(局面 node, 手番 turn, 先読みの深さ depth){

  /* 葉の場合、評価値を返す */
  if(depth == 0) return eval();

  /* 現在の局面から1手進めた状態をa1,a2,a3・・akとする */
  expand_node(node, 次の turn);

  best = -INFINITY;
  for(i=0; i<k; i++){
    val = - Negamax(ai, 次の turn, depth-1);
    if(best < val)   best= val;
  }

  return best;
}

つまり、Negamax 探索法は、得られた評価値に「-1」を掛けて、常に最大値を選択するというものです。

これにより、自分も相手も常に最大値を選ぶようになるので、プログラムが簡潔になるという利点があります。

オススメ書籍

オセロに強くなりたい人は下記を読むことをお勧めします。

オセロ（将棋等）のプログラムを開発したい人・ゲームプログラマーになりたい人は下記は持っていて損はないでしょう。

ページの先頭へ移動