4.1 盤面の取り扱いその１

この章では、オセロプログラムTurtle について、私がわかっている範囲で解説をします。
わからない部分も多いので、誤りを見つけた場合にはご指摘をよろしくお願いします。

Turtleのプログラムソースはこちらからダウンロードできます。
turtle.tar.gzにソースおよびデータが含まれています。
Windows上で実行する場合、Cのコンパイラがなければturtle.exeとcygwin.dllも必要です。
しかしソースをコンパイルする方が高速に動作するので、コンパイルすることをお勧めします。

この節では、Turtleで盤面をどのように扱っているかについて説明を行います。
Turtleでは盤面を表すのに構造体を使っていますが、用途に応じて３つの構造体を使い分けています。
()内は定義されているファイルの名前です。

  • BOARD (board.h)
    対局時に用いる構造体です。
    手番、各マス、現在までの手で返された石の情報が含まれています。
  • MBOARD (mboard.h)
    中盤および終盤探索を行う時に用いる構造体です。
    BOARDによる情報に加え、局面のハッシュ値、パターンインデックス(列、辺などのパターンに割り振られた番号)を含みます。
  • EBOARD (eboard.h)
    終盤の末端付近のノードで用いる構造体です。
    BOARDによる情報に、局面のハッシュ値が加えられています。
では各構造体について詳しく見ていきましょう。

BOARDの定義は次のようになっています。 


typedef struct {
   int   Colour;
   int   Square[SQUARE_NB];
   int **FlipSP;
   int  *FlipStack[FLIP_NB];
} BOARD;
Colourは黒番か白番かを表し、Squareは各マスにある石を表します。
いずれも黒番(石)なら-1、白番(石)なら1です。
また空きマスは0で表されます。
定数SQUARE_NBは91で、1.1節で解説した方法と同様に、盤外のマスを空きマスで表すことにより、石を返す処理をするときに利用しています。
FlipStackは、どの石を返したかを記憶するためのスタックで、石を返したマスへのポインタが配列になっています。
データはNULLポインタで区切られます。
FlipSPはスタックへのポインタです。

MBOARDの定義は次のようになっています。 


typedef struct {
   int       Colour;
   MSQUARE **FlipSP;
   int       Key[2];
   MSQUARE   Square[SQUARE_NB];
   int       Index[INDEX_NB+1]; /* Index[INDEX_NB] = dummy index */
   MSQUARE  *FlipStack[FLIP_NB];
} MBOARD;
Squareは各マスの情報です。
Keyは局面のハッシュ値、Indexはパターンインデックスです。
Colour、FlipStackおよびFlipSPはBOARDのときと同様です。
MBOARDでは、各マスの情報を表すのにMSQUAREという構造体を使用しています。
MSQUAREの定義は次のようになっています。

typedef struct {
   int   Disk;
   int   Move;
   int   FlipKey[2];
   int   MoveKey[2][2];
   INDEX Index[4];
} MSQUARE;
Diskは石の色、Moveは自身のインデックスを表します。
(すなわち、任意のiに対しMBoard->Square[i].Move=i)
FlipKeyとMoveKeyはハッシュ値を生成するのに使われます。
Indexはパターンインデックスの変化量です。
構造体INDEXの定義は次のようになっています。

typedef struct {
   int *Index;
   int  Inc1;  /* ushort */
   int  Inc2;  /* ushort */
} INDEX;
Indexは変化させるパターンインデックスへのポインタ、Inc1、Inc2は変化量です。
Inc1は空きマスに石を置いたときの変化量で、Inc2は石が返されたときの変化量です。

EBOARDの定義は次のようになっています。 


typedef struct {
   int       Colour;
   ESQUARE **FlipSP;
   int       Key[2];
   ESQUARE   Square[SQUARE_NB];
   ESQUARE  *FlipStack[FLIP_NB];
} EBOARD;
Colour、Key、FlipStack、FlipSPについてはMBOARDの場合と同様です。
Squareは各マスの情報で、構造体ESQUAREの定義は次のようになっています。

typedef struct ESquare {
   int Disk;
   int Move;
   int FlipKey[2];
   int MoveKey[2][2];
   struct ESquare *Succ;
   struct ESquare *Pred;
} ESQUARE;
SuccとPredは終盤の探索の末端付近のノードで、空きマスの双方向リストを作成するのに使います。
それ以外の変数についてはMSQUAREの場合と同様です。

トップに戻る
4.2 盤面の取り扱いその２