2009-11-04

■　C++で書き直したBonanza

もうすでにお気づきの人がいるかも知れないが、私は、Bonanzaのソースを全面的にC++で書き直している。

何故、本家BonanzaがC++ではなくCで書かれているのか、その理由は私にはよくわからない。移植性を気にされたのかも知れない。

ともかく、Bonanzaはアルゴリズム的にはよく練られているとは思うものの、Cで書かれているというのもあって、冗長で、かつ、見通しの非常に悪いプログラムになっている。

例えば、私が書き直したbitboardクラスは次のようになっている。

// bitboard
struct bitboard
{
	// 3*9 ×3だと扱うか、別のbit layoutにするかどうかは考え中。
	u32 p[3];

	// 各32bitをbitwise orを取る
	u32 ToU() { return p[0] | p[1] | p[2]; }

	// -- bitboardに対する論理演算

	// 盤上の位置iが1のmaskとxor。ビットiを0にしたり、1にしたりするのに使う。
	void Xor(BoardPos i)
	{
		Xor(abb_mask[i]);
	}

        // 盤上の座標を90度回転されたところが1のmaskとxor。
	void XorFile(BoardPos i)
	{
		Xor(abb_mask_rl90[i]);
	}

	// 盤上の位置iの斜め(左上から右下)が1のmaskとxor。
	void XorDiag1(BoardPos i)
	{
		Xor(abb_mask_rr45[i]);
	}

	// 盤上の位置iの斜め(右上から左下)が1のmaskとxor。
	void XorDiag2(BoardPos i)
	{
		Xor(abb_mask_rl45[i]);
	}

	// 1のビット数を数える。SSE4.1の命令なら一命令なのだが..
	// 速度の要求されるところからこの関数は呼び出されないから良いか..
	int PopuCount() const
	{	
		int counter = 0;
		u32 u0 = p[0];
		while ( u0 ) { counter++;  u0 &= u0 - 1U; }
		u32 u1 = p[1];
		while ( u1 ) { counter++;  u1 &= u1 - 1U; }
		u32 u2 = p[2];
		while ( u2 ) { counter++;  u2 &= u2 - 1U; }
		return counter;
	}
	
	// ゼロ初期化するときに0を代入できるように
	bitboard operator = (u32 u)
	{
		p[0] = p[1] = p[2] = u;
		return *this;
	}
};

// operatorをいろいろ定義しとこう。

inline bitboard operator | (const bitboard& lvalue,const bitboard& rvalue)
{
	bitboard temp;
	temp.p[0] = lvalue.p[0] | rvalue.p[0];
	temp.p[1] = lvalue.p[1] | rvalue.p[1];
	temp.p[2] = lvalue.p[2] | rvalue.p[2];
	return temp;
}

inline bitboard operator & (const bitboard& lvalue,const bitboard& rvalue)
{
	bitboard temp;
	temp.p[0] = lvalue.p[0] & rvalue.p[0];
	temp.p[1] = lvalue.p[1] & rvalue.p[1];
	temp.p[2] = lvalue.p[2] & rvalue.p[2];
	return temp;
}

inline bitboard operator ^ (const bitboard& lvalue,const bitboard& rvalue)
{
	bitboard temp;
	temp.p[0] = lvalue.p[0] ^ rvalue.p[0];
	temp.p[1] = lvalue.p[1] ^ rvalue.p[1];
	temp.p[2] = lvalue.p[2] ^ rvalue.p[2];
	return temp;
}

このようにbitboardクラスを定義すれば、

  // BTGOLDは、金の利きと同等の駒の位置を表わすbitboard
  BBOr( BB_BTGOLD, BB_BPRO_PAWN,   BB_BGOLD ); // と + 金
  BBOr( BB_BTGOLD, BB_BPRO_LANCE,  BB_BTGOLD );// + 成香
  BBOr( BB_BTGOLD, BB_BPRO_KNIGHT, BB_BTGOLD );// + 成桂
  BBOr( BB_BTGOLD, BB_BPRO_SILVER, BB_BTGOLD );// + 成銀

のように書いてある部分は、次のように簡潔に書ける。

  // BTGOLDは、金の利きと同等の駒の位置を表わすbitboard
  BB_BTGOLD = BB_BPRO_PAWN | BB_BGOLD | BB_BPRO_LANCE | BB_BPRO_KNIGHT | BB_BPRO_SILVER;

このように書いた場合、temporary objectが作られて、代入のときにtemporary objectからのcopyが行なわれて損なように思えるが、C++コンパイラでは普通、temporary objectの代入の最適化というのが行なわれて、最適化がかかると実際はtemporary objectは生成されない。要するに、本家Bonanzaと同じ質のコードが生成される。

また、

  BBIni( BB_BOCCUPY );
  BBIni( BB_BPAWN );

のようなbitboardの初期化も次のように簡潔に書け、これまたC++コンパイラは普通は最適化してくれるので、同じ質のコードが生成される。

  BB_BOCCUPY = BB_BPAWN = 0;

このようにbitboardをoperatorを使って書くようにするだけでもBonanzaのソースはずいぶん見やすくなる。しかもそれらは実行速度と引き替えにする必要は全くない。

■　まとめ

私がC++で書き直したBonanzaのソースは、コメント行を除けば、本家Bonanzaの半分程度の分量しかない。速度的にも本家と比べて全く遜色がない。(それどころか、数々の改良により、本家より断然速い)

本家Bonanzaのソースを見て、「速度を追い求めるならC++ではなくCで書くべきだ」などと間違った信仰が生まれないことを願うばかりである。

あと、Bonanzaは、Cで書かれているプログラムとしてはアルゴリズム的にも洗練されていて、教育的にも価値のある、非常に完成度の高いプログラムであることも併記しておく。