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

タイトル:オセロゲーム開発 ~ミニマックス探索法~

このサイトでは、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」を掛けて、常に最大値を選択するというものです。

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

オススメ書籍

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

楽天市場で買う 楽天市場で買う 楽天市場で買う 楽天市場で買う

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

楽天市場で買う 楽天市場で買う 楽天市場で買う 楽天市場で買う

ページの先頭へ移動

このページの人気コンテンツ

    全ページの人気コンテンツ

    Copyright ©2016 .(since 2001/11/18)