棋譜ツリー

SGF ファイルの棋譜ツリーと CELL 構造体の説明です。

SGF ファイルの説明

SGF ファイルを入力では、詰碁の出題図を表示しました。
ここでは、詰碁の棋譜を記録する TEXT 形式と、これをメモリー上に展開するツリー構造に付いて説明します。
SGF 形式の説明はＳＧＦ SGFファイル形式を参照して下さい。

SGF ファイルの棋譜は、例えば次のようになっています。
初期画面(出題図)に続いて「(;B[ca]」から棋譜が始まります。
棋譜に最低限必要なプロパティは B[xy] と W[xy] です。
( ) は棋譜の階層で「(」が出現したら階層を1ランク上げ「)」が出現したら階層を1ランク下げます。
( ～ ) の間が棋譜の分岐手順で、再起構造になっています。

B[xy] 座標xyに黒配石
W[xy] 座標xyに白配石

(
;FF[3]GM[1]AP[PocketGoban Ver 0.999]
SZ[19]DT[2014-02-17]
KM[5.5]
AB[bc][cc][db]AW[cd][dc][ec][eb][de][cf](
;B[ca](;W[ab];B[bb];W[ea];B[aa];W[ba];B[ac];W[da];B[cb]
)(;W[bb]
;B[ab];W[ba];B[bd];W[be];B[ad]
)(;W[ea];B[ab];W[bd];B[ba]
)
)(;B[bb]
;W[da];B[ca]
)
)

座標 [xy] は、碁盤の左上を [aa] として次のように定義されています。

  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18

ページ先頭の画像が棋譜のツリーで、 #1 #2 #3 ・・・は SGF ファイルの記述順で、生成される CELL の順でもあります。
棋譜の本筋は #1(Bca) #2(Wab) #3(Bbb) #4(Wea) #5(Baa) #6(Wba) #7(Bac) #8(Wda) #9(Bcd) です。
#1(Bca) から #20(Bbb) に cdr からリンク(別の手順)があり、#21(Wda) #22(Bca) と続きます。
また #2(Wab) から #10(Wbb) と #16(Wea) に二種類の分岐があります。
#10 には #2 の cdr から、#16 には #10 の cdr からリンクします。

CELL 構造体

棋譜を記録する CELL Class(構造体)です。
num は生成された CELL の識別番号で、プログラムのデバッグなどに使います。
level は棋譜の分岐レベルです。
car は次の手順へのリンクです。
cdr は分岐手順へのリンクです。
next は再生手順を追跡するためのリンクです。
back は next の逆リンクで、手順を戻したり手を削除するときに使います。
pos は石の座標です。
teban は黒・白の手番です。
id は局面の見出しで、msg はコメントです。
Print(CELL pt) は、リンクを辿り全ての CELL を印字するメソッドで、デバッグに使用します。

class CELL
{
    public  int     num;        //セルの番号(チェック用)
    public  int     level;      //棋譜の分岐レベル
    public  CELL    car;        //次の cell へのポインタ
    public  CELL    cdr;        //分岐 cell へのポインタ
    public  CELL    next;       //選択手順へのポインタ
    public  CELL    back;       //next の逆リンク
    public  Point   pos;        //Ｘ座標, Ｙ座標
    public  short   teban;      //黒(1)・白(-1)
    public  string  id;         //見出し
    public  string  msg;        //コメント

    // Constructor
    public  CELL(int n)
    {
        num = n;
        level = 0;
        car= null;
        cdr= null;
        next= null;
        back= null;
        id= string.Empty;
        msg= string.Empty;
        pos.X = 0;
        pos.Y = 0;
    }

    // Cell Print
    public void Print(CELL pt)
    {
        string  link;
        if (pt==null)   return;
        if (pt.car!=null)   link = "  LINK:" + pt.car.num;
        else                link = "  LINK:*";
        if (pt.cdr!=null)   link = link + " " + pt.cdr.num;
        else                link = link + " *";
        Console.Write(pt.num + " LEV:" + pt.level + link);
        Console.Write(" [" + pt.pos.X + "," + pt.pos.Y + "] ");
        Console.WriteLine(pt.teban + " ID:" + pt.id + " MSG:" + pt.msg);
        Print(pt.car);
        Print(pt.cdr);
        return;
    }
}

CELL 構造体(class CELL)に、このアプリで使用するメソッドを定義します。
現段階では早いかも知れませんが、再起メソッドのサンプルとして幾つかを紹介しましょう。

next, back のリンクをリセットするメソッドです。

    static public void Reset(CELL pt)
    {   if (pt==null)   return;
        pt.next = null;
        pt.back = null;
        Reset(pt.car);
        Reset(pt.cdr);
    }

cdr のリンクをたどり CELL を検索するメソッドです。

    // lev, ps の CELL を検索
    static public CELL Scan(CELL pt, int lev, Point ps)
    {   CELL wp;
        if (pt==null)   return null;
        if (pt.level==lev && pt.pos.X==ps.X && pt.pos.Y==ps.Y)  return pt;
        wp = Scan(pt.cdr, lev, ps);
        if (wp != null) return wp;
        return null;
    }

CELL のクローンを作成するメソッドです。
CELL をそのままコピーすると元データが変更されたとき、その影響を受けるので注意して下さい。

    static public CELL Clone(CELL pt)
    {   CELL    wp;
        wp = new CELL(0);
        wp.num = pt.num;
        wp.car = pt.car;
        wp.cdr = pt.cdr;
        wp.pos = pt.pos;
        wp.teban = pt.teban;
        wp.id = pt.id;
        wp.msg = pt.msg;
        wp.lb = pt.lb;
        wp.judge = pt.judge;
        wp.level = pt.level;
        return wp;
    }

Clone を使って CELL List をコピーするメソッドです。

    static public void Copy(CELL sou, CELL des)
    {
        if (sou==null)  return;
        des = Clone(sou);
        if (sou.car!=null)
        {   Copy(sou.car, des.car);
        }
        if (sou.cdr!=null)
        {   Copy(sou.cdr, des.cdr);
        }
    }

[Next Chapter ↓] 棋譜の再生
[Previous Chapter ↑] SGF ファイルを入力

超初心者のプログラム入門(C# Frame Work)

※・