オセロ（リバーシ）の作り方 ～NegaScout探索法～

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

Alexander Reinefeldが発見した探索方法です。これはNegaMax法を少し改良するだけで実現可能です。MTD(f)法が開発されるまではリバーシプログラムでの高速化が実証されており、多くのリバーシプログラムで利用されていました。

NegaMax法を実装するにあたって、「Null windows search」と言う概念を理解しておく必要があります。

Null windows search

Null windows search の目的は､値を求めることではなく､値の範囲を絞り込むことです

αβ法におけるα（下限値）とβ（上限値）の幅を Window (探索窓)といい、 この幅を Null(Zero) にして行います。

NegaScout探索法

int NegaScout(int a,int b){

  /* 葉の場合、評価値を返す */
  if(leaf()) return eval();
  else{
    int t,i,m=b;
    for(i=0;i<n && a<b;i++){
      t=-child[i]->NegaScout(-m,-a);
      if(a<t){
        if(t<=m && i) a=-child[i]->NegaScout(-b,-t);
        else          a=t;
      }
      /* +1とする */
      m=a+1;
    }
    return a;
  }
}

オススメ書籍

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

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

ページの先頭へ移動