2017年7月
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          

最近のトラックバック

無料ブログはココログ

コンピュータ将棋の作り方

コンピュータ将棋の作り方

この記事よりオススメのページがあります

こちらで以前書籍となっていた「コンピュータ将棋のアルゴリズム」をHTML化したものを公開しています。

ただし、10年以上前の本ですので、内容はかなり古いです。

また、このページ自体も内容が古くなっていますが、書き直し始めると、ものすごい時間がかかりそうですので、当面(2016/6/18現在)このままにしておくと思います。

前書き

今では、色々な方法がこなれてきたので、新規にページを作成してみました。

大きな変化は、『評価関数の作り方』で、Bonanza Methodが成果を挙げていることもあり、私なりの方法で機械学習に取り組んでみた結果も書いていきたいと思います。

駒と局面の内部表現を決める

ここが実はとてもとてもとても重要なのですが、最初は試しに単純に作ってみましょう。

駒については、歩香桂銀金角飛王とそれぞれの成り駒、そして敵味方の区別が必要です。

敵味方の区別には、Cならビット演算が使えると高速でしょう。

で、ざっくりと駒の内部表現を考えると、

enum KOMAINF {
    OUT_OF_BOARD = 64,
    EMPTY  = 0,
    FU = 1,
    KY = 2,
    KE = 3,
    GI = 4,
    KI = 5,
    KA = 6,
    HI = 7,
    OU = 8,
    PROMOTED = 8,
    TO = PROMOTED + FU,
    NY = PROMOTED + KY,
    NK = PROMOTED + KE,
    NG = PROMOTED + GI,
    UM = PROMOTED + KA,
    RY = PROMOTED + HI,
    ENEMY = 16,
    EFU = ENEMY + FU,
    EKY = ENEMY + KY,
    EKE = ENEMY + KE,
    EGI = ENEMY + GI,
    EKI = ENEMY + KI,
    EKA = ENEMY + KA,
    EHI = ENEMY + HI,
    EOU = ENEMY + OU,
    ETO = ENEMY + TO,
    ENY = ENEMY + NY,
    ENK = ENEMY + NK,
    ENG = ENEMY + NG,
    EUM = ENEMY + UM,
    ERY = ENEMY + RY
};

typedef unsigned char KomaInf;

ついでに、

inline int IsEnemy(KomaInf koma) {
  return (koma & ENEMY);
}

inline int IsSelf(KomaInf koma) {
  return (FU<=koma && koma<=RY);
}

inline int IsEnemy(int sengo,KomaInf koma)
{
  if (sengo==0) {
    IsEnemy(koma);
  } else {
    IsSelf(koma);
  }
}

inline int IsSelf(int sengo,KomaInf koma)
{
  if (sengo==0) {
    IsSelf(koma);
  } else {
    IsEnemy(koma);
  }
}

という感じで、敵味方の駒の判別を準備しておきます。

局面ですが、単純に作るなら、とりあえず、11*11(盤面の外には外であることをあらわすデータ=OUT_OF_BOARDSを入れておくと簡単になるので)の配列と、先手と後手の持ち駒の数をあらわす配列[2][8]があれば良いでしょう。

class Kyokumen {
protected:
	KomaInf Board[11][11];
	// Hand[0][xx]が先手の持ち駒の枚数、Hand[1][xx]が後手の枚数
	int		Hand[2][HI+1];
};

局面の表示を作る

ここはどうやってもいいです。
#CSAの配っているのを使うのも一つの方法。

まあ、駒をあらわす文字列を、

char *komaStr[]={
	"   "," 歩"," 香"," 桂"," 銀"," 金"," 角"," 飛"," 玉"," と"," 杏"," 圭"," 全"," 金"," 馬"," 竜",
	"   ","v歩","v香","v桂","v銀","v金","v角","v飛","v王","vと","v杏","v圭","v全","v金","v馬","v竜"
};

なんてしておいて、Kyokumenクラスに、Printメソッド

void Kyokumen::Print()
{
	int dan,suji;
	int koma;

	printf("先手 持ち駒 ");
	for(koma=FU;koma<=HI;koma++) {
		if (Hand[0][koma]==1) {
			printf("%s ",komaStr[koma]);
		} else if (Hand[0][koma]>1) {
			printf("%s%d ",komaStr[koma],Hand[0][koma]);
		}
	}
	printf("\n");
	printf("   9 8 7 6 5 4 3 2 1 \n");
	printf("  +---+---+---+---+---+---+---+---+---+\n");
	for(dan=1;dan<=9;dan++) {
		printf("%s|","  \0一\0二\0三\0四\0五\0六\0七\0八\0九\0"+dan*3);
		for(suji=9;suji>=1;suji--) {
			printf("%s|",komaStr[Board[dan][suji]]);
		}
		printf("\n");
		printf("  +---+---+---+---+---+---+---+---+---+\n");
	}
	printf("後手 持ち駒 ");
	for(koma=FU;koma<=HI;koma++) {
		if (Hand[1][koma]==1) {
			printf("%s ",komaStr[koma]);
		} else if (Hand[1][koma]>1) {
			printf("%s%d ",komaStr[koma],Hand[1][koma]);
		}
	}
}

を作るのが簡単で良いのではないでしょうか。

「手」の内部表現を決め、「手」によって局面を進められるようにする

とても重要です。
大雑把に言うと、この速度で先読みの速さ=何手先まで読めるかが決まってしまいます。

また、この時点で、デバッグのことを考えて、手の表示を考えておいた方が良いでしょう。

とりあえず、簡単に作ってみると、

struct Pos {
	unsigned char dan,suji;
};

struct Te {
	Pos from,to;
	KomaInf koma;
	bool promote;
};

で、どこから(from)どこへ(to)、どんな種類の駒(koma)が、成り・不成り(promote)動いたか、を表現できます。持ち駒を盤に打つ時には、from.Sujiが0とでもしておくと良いでしょう。

ついでに、手の表示を作成します。

void Te::Print()
{
	if (from.Suji!=0) {
		printf("%1d%1d",from.Suji,from.Dan);
	}
	printf("%1d%1d",to.Suji,to.Dan);
	printf("%s",komaStr[koma & ~ENEMY]);
	if (from.Suji==0) {
		printf("打  ");
	} else if () {
		printf("成");
	} else {
		printf("  ");
	}
}

で、Kyokumenクラスに手によって局面を変化させるクラスを作成します。

void Kyokumen::Move(int teban,const Te &te)
{
	KomaInf capture=Board[te.to.Dan][te.to.Suji];
	
	if (from.Suji) {
		Board[te.from.Dan][te.from.Suji]=EMPTY;
	} else {
		Hand[teban][te.koma]--;
	}
	if (te.promote) {
		Board[te.to.Dan][te.to.Suji]=te.koma | PROMOTED;
	} else {
		Board[te.to.Dan][te.to.Suji]=te.koma;
	}
	if (capture!=EMPTY) {
		Hand[teban][capture & ~ENEMY & ~PROMOTED]++;
	}
}

こんな感じでしょうか。 tebanは、0が先手1が後手としておきます。

手を入力できるようにする

いや、当たり前なんですけど、これが出来ないと対人でテストするのが大変(^^;;

方法は色々あるわけですけど、テキストベースなら、どこからどこへ駒を動かすか、成るかを問い合わせればいいのでしょう。

局面をファイルから読み込めるようにする

これをしておかないと、後でデバッグが大変です。

棋譜をファイルに読み書きできるようにする

これをしておかないと、後でデバッグが大変。うさぴょんでは、この機能をCSA将棋が持っています(^^;;;;;;;

局面から手を生成できるようにする

いよいよ将棋プログラムの一番面倒な部分です(^^;;
#合法手の生成って、結構面倒なんですよね。

// 方向をあらわす
struct Direction {
	int dan,suji;
	const Pos &operator +(const Pos &x,const Dir &y) {
		Pos ret;
		ret.dan =x.dan +y.dan;
		ret.suji=x.suji+y.suji;
		return ret;
	}
	const Pos &operator -(const Pos &x,const Dir &y) {
		Pos ret;
		ret.dan =x.dan -y.dan;
		ret.suji=x.suji-y.suji;
		return ret;
	}
	bool operator==(const Dir &p) const {
		return p.dan==dan && p.suji==suji;
	}
	const Dir & operator-() const {
		Dir ret;
		ret.dan=-dan;
		ret.suji=-suji;
		return ret;
	}
};


Direction Direct[12]={
	// 8方向
	{0,1},		// ↓
	{1,1},		// ←↓
	{1,0},		// ←
	{1,-1},		// ←↑
	{0,-1},		// ↑
	{-1,-1},	// →↑
	{-1,0},		// →
	{-1,1},		// →↓
	// 先手の桂馬飛び
	{-2,1},
	{-2,-1}
	// 後手の桂馬飛び
	{2,1},
	{2,-1}
};

// ある方向に進めるかどうか
int canGo[12][ERY+1]={
//	{0,1},		// ↓
{
//	 歩香桂銀金角飛玉と杏圭全金馬竜,
	0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,
//	 歩香桂銀金角飛玉と杏圭全金馬竜,
	0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1
},
//	{1,1},		// ←↓
{
//	 歩香桂銀金角飛玉と杏圭全金馬竜,
	0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,1,
//	 歩香桂銀金角飛玉と杏圭全金馬竜,
	0,0,0,0,1,1,1,0,1,1,1,1,1,1,1,1
},
//	{1,0},		// ←
{
//	 歩香桂銀金角飛玉と杏圭全金馬竜,
	0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,
//	 歩香桂銀金角飛玉と杏圭全金馬竜,
	0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1
},
//	{1,-1},		// ←↑
//	{0,-1},		// ↑
//	{-1,-1},	// →↑
//	{-1,0},		// →
//	{-1,1},		// →↓
};

// ある方向に飛べるかどうか
int canJump[12][ERY+1]={
};

// startからdirの方向に空でない升を探す
Pos Kyokumen::Search(Pos start,Direction dir)
{
	Pos p;
	for (i = start + dir; ban[p.dan][p.suji] == EMPTY; p += dir) ;
	return p;
}

void Kyokumen::MakePinInf(Direction pin[11][11])
{
	// 王への敵の利きを防いでいる駒について、その利きの来る方向を覚えておく
	int dan,suji;
	Pos kingS,kingE;
	
	for(dan=1;dan<=9;dan++){
		for(suji=1;suji<=9;suji++) {
			pin[dan][suji]=0;
			if (Board[dan][suji]==OU) {
				kingSdan=dan;
				kingSsuji=suji;
			}
			if (Board[dan][suji]==EOU) {
				kingEdan=dan;
				kingEsuji=suji;
			}
		}
	}
	for (i = 0; i < 8; i++) {
		Pos m, p;
		p = search(kingS, Direct[i]); 
		if ((Board[p.dan][p.suji] != WALL) && !(Board[p.dan][p.suji] & ENEMY)) { //味方の駒が有る
			m = search(p, Direct[i]);
			if ((Board[m.dan][m.suji] & ENEMY) && canJump[i][Board[m.dan][m.suji]]) { //敵の飛び駒が有る
				pin[p] = Direct[i];
			}
		}
	}
	for (i = 0; i < 8; i++) {
		Pos m, p;
		p = search(kingE, -Direct[i]);
		if ((Board[p.dan][p.suji] != WALL) && (Board[p.dan][p.suji] & ENEMY)) { //敵の駒が有る
			m = search(p, -Direct[i]);
			if (!(Board[m.dan][m.suji] & ENEMY) && canJump[i][Board[m.dan][m.suji]]) { //味方の飛び駒が有る
				pin[p] = -Direct[i];
			}
		}
	}
}

Kyokumen::MakeMoves(int sengo,int &teNum,Te *teBuf)
{
	Direction pin[11][11];
	MakePinInf(pin);

	// 王手がかかっていたら防ぐ手を生成しないといけない。
	if () {
		MakeAntiCheck();
	}
	
	// 盤上のsengoの駒を進める手の生成(pinを意識する)
	Position pos;
	for(pos.dan=1;pos.dan<=9;pos.dan++) {
		for(pos.suji=1;pos.suji<=9;pos.suji++) {
			if (IsSelf(sengo,ban[pos.dan][pos.suji]) {
				// 動かせる方向に動かす
				KomaInf koma=ban[pos.dan][pos.suji];
				for(int dir=0;dir<12;dir++) {
					Pos newpos=pos+Direction[dir];
					if (canGo[i][koma] && ban[newpos.dan][newpos.suji]!=OUT_OF_BOARD && !IsSelf(sengo,ban[newpos.dan][newpos.suji]) && (pin[dan][suji]==0 || pin[dan][suji]==Direction[dir] || -pin[dan][suji]==Direction[dir])) {
						if (koma==FU || koma==KY) {
							if ((sengo==0 && newpos.dan==1) || ()) {
								// 歩と香は1段目に入ったら必ず成る
								teBuf[teNum++]=;
							} else {
								// 成る手とならない手を生成
								teBuf[teNum++]=;
								teBuf[teNum++]=;
							}
						} else if (koma==KE) {
							// 桂馬は2段目に入ったら必ず成る
						} else if (koma==OU) {
							// 敵の利きのあるところには動けない
						} else if () {
							// 成っても成らなくても良い
						}
					}
				}
			}
		}
	}
	// 盤に持ち駒を打つ手
	for() {
		if (koma==FU) {
			// 二歩と打ち歩詰めのチェック
		}
	}
}

えーと、まだ完成してません(^^;;;
動くコードを示すだけなら、うさぴょんのコードをそのまま貼り付ければいいんですけど、このあたりのうさぴょんのコードは鈴木将棋2000年版のために鈴木君の書いたものが結構残っているので…。
なお、鈴木将棋の次の版ではこのあたりを全部書き直しているようです。

ある手が合法かどうかチェックする機能を作る

チェックしないと、先手5951OUで必勝ですからね(^^;;

玉を取るか、取られたら終了する(^^;;;

いや、本当は合法な指し手がなくなったら投了というのが正しいんですが。

実はここまでで、対局できる将棋プログラムの半分以上を作成しています。

さて、以下が本当の意味での思考です。

局面の評価をする関数を作る

とてもとても重要なところです。

単純には、局面を渡したら先手から見た評価値が帰ってくるように作れば良いでしょう。局面をクラスにしているなら、局面に対して現在の評価値を得るメソッドがあると良いでしょう。

この関数の実行速度も先読みの深さに関わってきます。

したがって、駒の価値などは、盤面を全部調べて駒の価値を足し算&持ち駒の価値を足し算するような処理にしないで、局面クラスの内部状態として、駒の価値の合計を持ち、手によって局面を進める時に差分だけ計算するなどの工夫が必要です。
#この辺の詳細は鈴木将棋のKyokumenKomawariクラスのソース参照。

さらに、玉の周りでは金銀の価値を高くしたり、壁形はマイナスしたり、位取りに点数を足したり、いろいろ評価項目は考えられます。

でも、とりあえずは駒割りだけで動かせるようにすると良いと思います。
#それなりに将棋になるもんです。

じゃ、試しに作ってみます(遅いけど)。

int HandValue[OU]={
	//    , 歩, 香, 桂, 銀, 金,  角,  飛,玉
		 0,120,550,660,880,990,1400,1650,9999999
};

int PieceValue[]={
	//    , 歩, 香, 桂, 銀, 金,  角,  飛,  玉,  と,  杏,  圭,  全,  金,  馬,  竜,
		 0,100,500,600,800,900,1300,1500,9999,1100,1000,1000, 900,   0,1500,1700,
	//    , v歩, v香, v桂, v銀, v金,  v角,  v飛,  v王,  vと,  v杏,  v圭, v全, v金, v馬, v竜
		 0,-100,-500,-600,-800,-900,-1300,-1500,-9999,-1100,-1000,-1000,-900,   0,-1500,-1700,
};

int Kyokumen::Evaluate(int sengo)
{
	int Eval=0;
	for(dan=1;dan<=9;dan++) {
		for(suji=1;suji<=9;suji++) {
			Eval=Eval+PieceValue[Board[dan][suji]];
		}
	}
	for(koma=FU;koma<=HI;koma++) {
		Eval=Eval+HandValue[koma]*Hand[0][koma]
		Eval=Eval-HandValue[koma]*Hand[1][koma]
	}
	if (sengo==1) return -Eval;
	return Eval;
}

簡単な評価関数だと、合法手の生成と比べると、とっても簡単ですね(^^)

本格的に、学習を入れたりするのは、また後のテーマとしたいと思います。

思考ルーチンについて理解する

思考ルーチンですが、ここでは、クラスの名前をThinkとしておきます。

まずは、MinMaxを組みましょう。

MinMaxは、

  • 自分は自分にとって一番良い手を選ぶ(Maxを選ぶ)
  • 相手は自分にとって一番悪い手を選ぶ(Minを選ぶ)

とした場合に、最初にどの手を選ぶと相手の最高の指し手(Min)に対して良い結果(Max)を得られるか?そして、その結果何点をえられるか?を調べるアルゴリズムです。

これこそが、現在のコンピュータ将棋の中心アルゴリズムです。

---- MinMax ----
#define INFINITE 99999999

int Think::MinMax(int sengo,int depth,int depthMax,const Kyokumen &k)
{
	if (depth==depthMax) {
		return k.Evaluate(sengo);
	}
	int teNum=0;
	Te teBuf[600];
	k.MakeMove(sengo,teNum,teBuf);

	// 合法な指し手がない=負け(詰んでいる)
	if (teNum==0) {
		return -INFINITE;
	}

	Kyokumen child(k);
	child.Move(sengo,teBuf[0]);
	int retval=MinMax(sengo ? 0:1,depth+1,depthMax,child);
	for(i=1;i<teNum;i++) {
		child=k;
		child.Move(sengo,teBuf[1]);
		if (sengo==0) {
			// maxの手番
			retval=max(retval,MinMax(sengo ? 0:1,depth+1,depthMax,child));
		} else {
			// minの手番
			retval=min(retval,MinMax(sengo ? 0:1,depth+1,depthMax,child));
		}
	}
	return retval;
}

ところで、これだと、一番いい手を指した時の最終的な評価値は得られるのですが、どの手が良かったのか分かりません(^^;;

それに、これだと遅い部分がある(Kyokumenのコピーがたくさん起きる)ので、普通はKyokumenにBackという関数を用意して、こんな感じにするでしょう。

---- MinMax2 ----
// 無限大をあらわすためのでかい数値
#define INFINITE 99999999

// 「手」で取った駒を記憶していないと元の状態に戻せないので、変更します m(..)m
struct Te {
	Pos from,to;	// どこからどこへ
	KomaInf koma;	// 動いた駒
*	KomaInf capure;	// 取った駒(追加)
	bool promote;	// 成/不成
};

// MakeMoveの中で、取った駒を記憶するような変更も必要だけど割愛

// 手を見てもとの状態に戻す
Kyokumen::Back(int teban,const Te &te)
{
	if (from.Suji) {
		Board[te.from.Dan][te.from.Suji]=te.koma;
	} else {
		Hand[teban][te.koma]++;
	}
	if (te.capture!=EMPTY) {
		Hand[teban][capture & ~ENEMY & ~PROMOTED]--;
		Board[te.to.Dan][te.to.Suji]=te.capture;
	}
}

// Kyokumen &kはもはやconstではない!
int Think::MinMax2(int sengo,int depth,int depthMax,Kyokumen &k,Te &bestTe)
{
	if (depth==depthMax) {
		return k.Evaluate(sengo);
	}
	int teNum=0;
	Te teBuf[600];
	k.MakeMove(sengo,teNum,teBuf);

	// 合法な指し手がない=負け(詰んでいる)
	if (teNum==0) {
		return -INFINITE;
	}

	k.Move(sengo,teBuf[0]);
	int retval=MinMax(sengo ? 0:1,depth+1,depthMax,child);
	k.Back(sengo,teBuf[0]);

	bestTe=teBuf[0];

	Te childBest;
	for(i=1;i<teNum;i++) {
		k.Move(sengo,teBuf[i]);
		int newval=MinMax(sengo ? 0:1,depth+1,depthMax,k,childBest);
		k.Back(sengo,teBuf[i]);
		if (sengo==0) {
			// maxの手番
			if (newval>retval) {
				bestTe=teBuf[i];
				retval=newval;
			}
		} else {
			// minの手番
			if (newval<retval) {
				bestTe=teBuf[i];
				retval=newval;
			}
		}
	}
	return retval;
}

これで、一番良かった手の記録も出来るので、ぐーな感じです。

また、実際のプログラムでは、MinMaxを変形して以下のようなNegaMaxとして使うことが多いです。
#以降、別の探索アルゴリズムを紹介する時にも、特に断りのない場合、NegaMaxをベースにします。

これは、

  • 自分は自分にとって一番良い手を選ぶ(Maxを選ぶ)
  • 相手は相手にとって一番良い手を選ぶ(-Maxが最大になるものを選ぶ)

ことに相当します。

---- NegaMax ----
int Think::NegaMax(int sengo,int depth,int depthMax,Kyokumen &k,Te &bestTe)
{
	if (depth==depthMax) {
		return k.Evaluate(sengo);
	}
	int teNum=0;
	Te teBuf[600];
	k.MakeMove(sengo,teNum,teBuf);
	// 合法な指し手がない=負け(詰んでいる)
	if (teNum==0) {
		return -INFINITE;
	}

	Te childBest;

	int retval=-INFINITE;
	for(i=0;i<teNum;i++) {
		k.Move(sengo,teBuf[i]);
		int newval=-NegaMax(sengo ? 0:1,depth+1,depthMax,k,childBest);
		if (newval>retval) {
			bestTe=teBuf[i];
			retval=newval;
		}
		k.Back(sengo,teBuf[i]);
	}
	return retval;
}

思考ルーチンを強くする

ところで、NegaMaxにしろMinMaxにしろ、単純なMinMaxは、非常に効率の悪いアルゴリズムです。ほんとーに全部の手と局面を探索しないといけません。

これを将棋で行うと、1秒間に100万局面を評価できる非常に高速なプログラムを作成出来たとしても、(100万はでたらめに早いと思う。うさぴょんでは1万ぐらい。)30秒で3000万局面しか読めません。

大体、可能な指し手の数が80ぐらいとしたら、評価しないといけない局面が80*80*80*80=4096万局面になるので、40秒かけて、4手先しか読めないことになります!

しかも、可能な指し手はちょっとしたことで200を超えるので、 4手先を読むには、 200*200*200*200=16億局面なんと、1600秒(27分)かけないと4手先が読めません。

しかも、実際には、思考時間は20秒くらいで、普通にプログラムを作った場合には、1秒間に50万局面ぐらいしか読めないでしょう。そうすると、1000万局面しか読めないことになります。

そうすると、指し手の数が80だとしてもMinMaxでは、3手+α先しか読めないのです。指し手の数が200だとすると、3手先を読むには、200*200*200/500000=16 で、16秒かけないと3手先が読めません。

コンピュータの評価関数は、へたくそな人間の評価関数と比べても、だいたい読みが1~3手浅いのに匹敵するぐらい「だめ」な評価関数なので、「1手先しか読めない人間と互角」なプログラムということになります(--;;
#もっとも、これぐらいしっかりした評価関数を持つ人間なら3手の読みがしっかりできればほとんど初段のような気もします。

これはなんとかしないといけません。

実は、MinMaxと同じ効果をあげつつ、MinMaxよりも高速なアルゴリズムがいろいろと研究されています。その中でも歴史の古いアルゴリズムに、αβと呼ばれるアルゴリズムがあります。

では、αβに挑戦です。

---- AlphaBeta ----
int Think::AlphaBeta(int sengo,int depth,int depthMax,int alpha,int beta,const Kyokumen &k,Te &bestTe)
{
	if (depth==depthMax) {
		return k.Evaluate(sengo);
	}
	int teNum=0;
	Te teBuf[600];
	k.MakeMove(sengo,teNum,teBuf);
	// 合法な指し手がない=負け(詰んでいる)
	if (teNum==0) {
		return -INFINITE;
	}

	int retval=-INFINITE;

	Te childBest;
	for(i=0;i<teNum;i++) {
		k.Move(sengo,teBuf[i]);
		int newval=-AlphaBeta(sengo ? 0:1,depth+1,depthMax,-beta,-max(retval,alpha),k,childBest);
		k.Back(sengo,teBuf[i]);
		if (newval>retval) {
			bestTe=teBuf[i];
			retval=newval;
		}
		if (retval>=beta) {
			return retval;
		}
	}
	return retval;
}

αβの動作原理を説明するのはややこしいです。他力本願で、よそのページを紹介しておきます。柿木将棋の柿木さんの将棋プログラムの解説のページです。

理論的には、αβを採用すると、同じ時間で2倍の深さまで読むことができます。さっきの例だと、もしも100万局面/秒を達成できるなら、8手先が読めることになります。これなら、評価関数がそれなりなら人間の有段者に対抗できそうです。

実際には、50万局面/秒だとしても、6~7手先がきちんと読めれば、初段に近い力を持てることでしょう。
#ただし、実際には可能な指し手はすぐに200を超えることを考えると、だいたい4~5手先しか読めなくなり、初段とは言い難いことになるでしょうが…。

ここまでは、基礎技術で、将棋プログラムを書き始めれば誰でも調べものをしながら到達できる地点です。ここからが各将棋プログラムの工夫になります。

もっと強くするために

さて、ここからは、もっと強くするための方法を考えて行きます。
そして、ここからが、以前の将棋プログラムの作り方とは、大幅に異なった内容になっていきます!

その中でもプログラムの作り方に一番影響を与えたのが、『Bonanza』です。

手の並べ替え

さて、理論的にはαβは十分高速(これ以上早いアルゴリズムは存在しない!)なのですが、実は、その速さを達成するためには、非常に厳しい条件があります。指し手が最終的な評価の良い順に並んでいないといけないのです!
#そもそも、どの指し手が良いのか事前に分かっているなら、αβを呼び出す必要もありません。
もしも、最終的な評価の*悪い順*に並んでいた場合、αβはMinMaxと全く同じ動作になります。

非常に厳しい条件=指し手が最終的な評価の高い順に並んでいる、を満たさなくても、ある程度評価の高い順に並んでさえいれば、αβは効率的に動作します。そこで、今度は指し手を良い順に並べることを考えます。

では、まず、初代鈴木将棋でしていた手の並べ替えの工夫を一つ紹介しましょう。

---- AlphaBeta with MoveOrdering ----
int Think::AlphaBeta2(int sengo,int depth,int depthMax,int alpha,int beta,const Kyokumen &k,Te &bestTe)
{
	if (depth==depthMax) {
		return k.Evaluate(sengo);
	}
	int teNum=0;
	Te teBuf[600];
	k.MakeMove(sengo,teNum,teBuf);

	// 合法な指し手がない=負け(詰んでいる)
	if (teNum==0) {
		return -INFINITE;
	}

	// それぞれの指し手を評価する
	int value[600];
	for(i=0;i<teNum;i++) {
		k.Move(sengo,teBuf[i]);
		value[i]=k.Evaluate();
		if (sengo==1) {
			value[i]=-value[i];
		}
		k.Back(sengo,teBuf[i]);
	}
	
	// 指した後の評価の高い順に手をソートする
	for(i=0;i<teNum-1;i++) {
		int max=value[i];
		int maxid=i;
		for(j=i+1;j<teNum;j++) {
			if (value[j]>max) {
				max=value[j];
				maxid=j;
			}
		}
		swap(value[i],value[maxid]);
		swap(teBuf[i],teBuf[maxid]);
	}

	int retval=-INFINITE;

	Te childBest;
	for(i=0;i<teNum;i++) {
		k.Move(sengo,teBuf[i]);
		int newval=-AlphaBeta2(sengo ? 0:1,depth+1,depthMax,-beta,-max(retval,alpha),k,childBest);
		k.Back(sengo,teBuf[i]);
		if (newval>retval) {
			bestTe=teBuf[i];
			retval=newval;
		}
		if (retval>=beta) {
			return reval;
		}
	}
	return retval;
}

一手指してみた後の局面を評価して、その順番でソートする、単純な順番付けです。

さて、これで本当に6~7手先が読めるでしょうか?
実験すると…駄目です(--;
所詮一手先をみたぐらいでは、ろくなことになりません。相手の飛車先の歩を飛車で取る手が、歩の価値だけ点数が増えるから良い手だ、なんて判断じゃ駄目なのです。

それでも、何もしないよりはましになっているでしょうか?計測してみましょう。
…まだ未計測…

前向き枝刈り

将棋では、あまりにも可能な手の数が多くなることがあるため、前向き枝刈りとよばれる手法で、先読みをする指し手を絞り込むのが一般的でした。(過去形です。)

従って、以下は、古い内容となりますが、1990年代の作り方として記念に残しておきます。また、同じ方法に戻ってくるかも知れませんしね。

もしも常に候補手を20手に絞り込むことができれば、αβが理想的に働いた場合、75万局面(1秒間に5万局面を読めれば15秒)を読むことで、9手先読みが出来ます。

問題は、絞り込んだ中に最善手か、それに近い手が残っていなければ、ただの勝手読みになってしまうことです。

初代鈴木将棋では、ぢつは先ほど手の並べ替えで紹介したような、一手読みの評価値で候補手を絞り込んで先読みをしていました。以下のコードは鈴木将棋とはちょっと違った方法なのですが、まあ、こんな感じです。

// 残りの深さでどれだけの手を先読みするか決める
int TeMax[]={10,20,20,50,50,100,100};

int Think::AlphaBeta2(int sengo,int depth,int depthMax,int alpha,int beta,const Kyokumen &k,Te &bestTe)
{
:
この辺は今までと同様
:
	int retval=-INFINITE;

	Te childBest;
*	for(i=0;i<min(teNum,TeMax[depthMax-depth-1]);i++) {
		k.Move(sengo,teBuf[i]);
		int newval=-AlphaBeta2(sengo ? 0:1,depth+1,depthMax,-beta,-max(retval,alpha),k,childBest);
		k.Back(sengo,teBuf[i]);
		if (newval>retval) {
			bestTe=teBuf[i];
			retval=newval;
		}
		if (retval>=beta) {
			return reval;
		}
	}
	return retval;
}

今思うと、かなりひどい枝刈りだったと思います(--;
ただし、刈った後に残す手が多かったので、ものすごい勝手読みは特に見られませんでした… 残す手が多いので5手先しか読めませんでしたが。

しかし、それぞれの指し手を評価する部分を、局面の評価を単純に呼び出すのではなく、その指し手でどれぐらい得ができそうか?をきちんとプログラミングすれば、この方法は非常に有効です。
うさぴょんではこの関数をどのようにしているかをそのうち解説します。
非常に複雑なのですが、役立つ内容となっていると思います。

ところで、コンピュータチェスでは、このような前向き枝刈りの手法はほとんど採用されていません。

これは、可能な指し手の数が将棋と比べて少ないことが一つの理由であると思います。全部の手を読むことで得られる強さが、読みの深さを増すことによる強さの向上を上回っているわけです。読みぬけが発生した場合に極端にプログラムが弱くなるような何らかの性質 …次善手と最善手の差が大きく、最善手がしばしば局面の評価値だけを見るといったん悪くなっている、というような… を持っているのかも知れません。それに、絞り込むために指し手を評価する作業がありますから、元々多いものを少なく絞り込むには有効ですが、元々少ないものをさらに少なくしようとしても単に無駄な時間をつかうだけのことも多いのかも知れません。

しかし、コンピュータチェスでも全く前向き枝刈りをしないわけではなく、このように手を絞り込む手法とは違った、ある意味ではもっと穏やかな前向き枝刈りを使用しています。
チェスで行われている代表的な手法には、NullMoveと呼ばれる手法とFutilityPrunningと呼ばれる手法があります。

この手法は、将棋でも有効です。

静的探索/静止探索

既に紹介している方法で局面の評価と先読みを実際に行うと、実はいろいろな問題が起きてきます。まず、問題その1から。以下の局面で、先手番なら先手が飛車を素抜いてほとんど勝ちですが、後手番だったら後手が飛車を素抜いてほとんど勝ちでしょう。ですが、ここまでに紹介した評価関数では、この局面の点数はどちらの手番でも0点です。駒の損得はありませんからね。

持ち駒:歩1
  9 8 7 6 5 4 3 2 1
+---------------------------+
|v香v桂v銀v金v玉v金v銀v桂v香|一
| ・ ・ ・ ・ ・ ・ ・v角 ・|二
|v歩 ・v歩v歩v歩v歩v歩v歩v歩|三
| ・ ・ ・ ・ ・ ・ ・ ・ ・|四
| ・v飛 ・ ・ ・ ・ ・ 飛 ・|五
| ・ ・ ・ ・ ・ ・ ・ ・ ・|六
| 歩 歩 歩 歩 歩 歩 歩 ・ 歩|七
| ・ 角 ・ ・ ・ ・ ・ ・ ・|八
| 香 桂 銀 金 玉 金 銀 桂 香|九
+---------------------------+
持ち駒:歩1

しかし、人間で将棋を知っている人なら誰が見ても手番の側がいいと思うでしょう。これは、実は1手以上の先読みを行っているのです。この例では、飛車を取っても取り返されない=飛車を得する、ということを確認するには、2手の読みが必要です。ここで、ものごとをものすごく単純にいってしまうと、ようするに必要なだけ先読みすればいいのです。

ですが、いったい「必要なだけ」とは「どれだけ」なのでしょうか?次の図の局面では、まあ、どちらの手番でも互角と評価してもかまわないでしょう。

持ち駒:なし
  9 8 7 6 5 4 3 2 1
+---------------------------+
|v香v桂v銀v金v玉v金v銀v桂v香|一
| ・v飛 ・ ・ ・ ・ ・v角 ・|二
|v歩v歩v歩v歩v歩v歩v歩v歩v歩|三
| ・ ・ ・ ・ ・ ・ ・ ・ ・|四
| ・ ・ ・ ・ ・ ・ ・ ・ ・|五
| ・ ・ ・ ・ ・ ・ ・ ・ ・|六
| 歩 歩 歩 歩 歩 歩 歩 歩 歩|七
| ・ 角 ・ ・ ・ ・ ・ 飛 ・|八
| 香 桂 銀 金 玉 金 銀 桂 香|九
+---------------------------+
持ち駒:なし

#将棋は先手有利といわれているので、手番をもっている側が有利ではあるでしょうが。

では、これは、先ほどの飛車の取り合いの局面と何が違うのでしょうか?ものすごく単純に考えると、次に指す手で取れる駒があるかないかの違い、というのが大きそうです。次に指す手で取れる駒がある間は先読みを続けるようなしかけをプログラムにいれればよさそうです。

int Think::AlphaBeta2(int sengo,int depth,int depthMax,int alpha,int beta,const Kyokumen &k,Te &bestTe)
{
:
この辺は今までと同じ
:
	int retval=-INFINITE;
	
*	int depthEnchou=0;		// 先読みを何手延長するか?

*	// もしも駒を取る手があれば一手延長する
*	for(i=0;i<teNum;i++) {
*		if (teBuf[i].capture!=EMPTY) {
*			depthEnchou=1;
*		}
*	}
	

	Te childBest;
	for(i=0;i<teNum;i++) {
		k.Move(sengo,teBuf[i]);
*		int newval=-AlphaBeta2(sengo ? 0:1,depth+1,depthMax+depthEnchou,-beta,-max(retval,alpha),k,childBest);
		k.Back(sengo,teBuf[i]);
		if (newval>retval) {
			bestTe=teBuf[i];
			retval=newval;
		}
		if (retval>=beta) {
			return reval;
		}
	}
	return retval;
}

しかし、こんなコードでは、いくらなんでも先読みに時間がかかり過ぎです(^^;;さっきの図で、ぶつかり合っていない駒を進める手(たとえば、▲1四歩、▽1六歩、…)なんてお互いに読んでいたら、2五飛と8五飛はいつまでもぶつかりあったままで、次に指す手で取れる駒がある状態がずーっと続いて、いつまでも先読みが終わりません。

そこで、もうちょっと読む手をしぼって、とにかく駒のぶつかり合いを解決することを考えてみます。駒を取る手がある間はその手を指してみて先読みを続けることにしてみます。

int Think::AlphaBeta2(int sengo,int depth,int depthMax,int alpha,int beta,const Kyokumen &k,Te &bestTe)
{
:
この辺は今までと同じ
:
	int retval=-INFINITE;

	Te childBest;
	for(i=0;i<teNum;i++) {
		int depthEnchou=0;		// 先読みを何手延長するか?
		if (teBuf[i].capture!=EMPTY) {	// 駒を取る手は一手読みを延長する
			depthEnchou+=1;
		}
		k.Move(sengo,teBuf[i]);
		
*		int newval=-AlphaBeta2(sengo ? 0:1,depth+1,depthMax+depthEnchou,-beta,-max(retval,alpha),k,childBest);
		k.Back(sengo,teBuf[i]);
		if (newval>retval) {
			bestTe=teBuf[i];
			retval=newval;
		}
		if (retval>=beta) {
			return reval;
		}
	}
	return retval;
	
}

しかし、これだと、以下の局面で先手番を評価させてみると、すごく変な評価値が帰ってきます。先手番の駒を取る手は、33角成(不成でもいいけど)しかありませんが、そんなことをしたら即座に同角とか同桂馬とかされて、歩と角の交換をした評価値になってしまいます。これを解決するために、「そこで先読みを中断して、その局面の評価値を得る」か、「駒を取る手を指して、先読みを続ける」かを選択できることにします。つまり、パスを許すわけです。

持ち駒:なし
  9 8 7 6 5 4 3 2 1
+---------------------------+
|v香v桂v銀v金v玉v金v銀v桂v香|一
| ・v飛 ・ ・ ・ ・ ・v角 ・|二
|v歩 ・v歩v歩v歩v歩v歩v歩v歩|三
| ・v歩 ・ ・ ・ ・ ・ ・ ・|四
| ・ ・ ・ ・ ・ ・ ・ ・ ・|五
| ・ ・ 歩 ・ ・ ・ ・ ・ ・|六
| 歩 歩 ・ 歩 歩 歩 歩 歩 歩|七
| ・ 角 ・ ・ ・ ・ ・ 飛 ・|八
| 香 桂 銀 金 玉 金 銀 桂 香|九
+---------------------------+
持ち駒:なし
int Think::qsearch(int sengo,int alpha,int beta,Kyokumen &k)
{
    int retval;
	retval=k.Evaluate(sengo); // これが、パスした時の価値
    if (retval>beta) return retval;

	int teNum=0;
	Te teBuf[600];
	k.MakeMove(sengo,teNum,teBuf);
    for(i=0;i<teNum;i++) {
        if (teBuf[i].capture==EMPTY) continue;
		k.Move(sengo,teBuf[i]);
		int newval=-qsearch(sengo ? 0:1,-beta,-max(retval,alpha),k);
		k.Back(sengo,teBuf[i]);
		if (newval>retval) {
			bestTe=teBuf[i];
			retval=newval;
		}
		if (retval>=beta) {
			return retval;
		}
    }
    return retval;
}

int Think::AlphaBeta2(int sengo,int depth,int depthMax,int alpha,int beta,const Kyokumen &k,Te &bestTe)
{
	if (depth==depthMax) {
		return qsearch(sengo,alpha,beta,k);
	}
:
この辺は今までと同じ
:
}

このqsearchという関数は、チェスプログラムで良く採用されている方法で、「取り合いの静的探索」と呼ばれます。ところで、先ほどまでは通常の先読みを行う関数の中に小細工をして先読みを延長していました。それでもできないことはないのですが、ちょっとプログラムの見通しが悪くなります。

それに、実際のプログラムでは、静的探索の評価値を末端の評価以外でも利用することがありますから、分離しておく方が良いのです。

ところで、静的探索のアルゴリズムも基本的にはαβ法ですので、どういう手から先読みを行うかが大きく速度に利いてきます。大雑把に言って、価値の大きい駒を価値の小さい駒で取る手ほど良い手である可能性が高いので、こんな風にソートしてみます。また、探索しなくても、パスした点数がβ値より大きいかどうかもチェックする価値があります。

int Think::qsearch(int sengo,int alpha,int beta,Kyokumen &k)
{
    int retval;
	retval=k.Evaluate(sengo); // これが、パスした時の価値
    if (retval>beta) return retval;

	int teNum=0;
	Te teBuf[600];
	k.MakeMove(sengo,teNum,teBuf);
	
*	// それぞれの指し手を評価する
*	int value[600];
*	for(i=0;i<teNum;i++) {
*		// 大きい駒を小さい駒で取る手ほど評価が高くする
*       value[i]=k.capture << 8 - k.koma;
*	}
*
*	// 指した後の評価の高い順に手をソートする
*	for(i=0;i<teNum-1;i++) {
*		int max=value[i];
*		int maxid=i;
*		for(j=i+1;j<teNum;j++) {
*			if (value[j]>max) {
*				max=value[j];
*				maxid=j;
*			}
*		}
*		swap(value[i],value[maxid]);
*		swap(teBuf[i],teBuf[maxid]);
*	}

    for(i=0;i<teNum;i++) {
        if (teBuf[i].capture==EMPTY) continue;
		k.Move(sengo,teBuf[i]);
		int newval=-qsearch(sengo ? 0:1,-beta,-max(retval,alpha),k);
		k.Back(sengo,teBuf[i]);
		if (newval>retval) {
			bestTe=teBuf[i];
			retval=newval;
		}
		if (retval>=beta) {
			return retval;
		}
    }
    return retval;

}

どうでしょう、速度的にもだいぶましになってきたのではないでしょうか?

読みの延長

先程の静的探索は、末端での評価値を正確にするために、末端の評価値をそのまま返す代わりに特定の方法で探索を行うというものでした。それもいわば読みの延長なのですが、もっと探索と一体化した読みの延長を行うのが一般的です。例えば、YSSでは0.5手延長というアルゴリズムを用いているそうです。この部分はいろいろと工夫を各プログラムが凝らしているところで、YSSでは、その他に

  • 王手なら一手読みを延長
  • (その時点の)最善手なら0.5手読みを延長

などを行っているそうです。

読みの延長の実装は非常に簡単です。いつものプログラムにちょっとだけコードを追加すれば出来ちゃいます。
先頭に'*'をつけた行が今までとの違いです。

int CalcExtension(const Kyokumen &k,const Te& te)
{
	int Extension=0;
	// 必要に応じて何手先読みを伸ばすか決定する
	return Extension;
}

int Think::AlphaBeta2(int sengo,int depth,int depthMax,int alpha,int beta,const Kyokumen &k,Te &bestTe)
{
	if (depth==depthMax) {
		return k.Evaluate(sengo);
	}
	int teNum=0;
	Te teBuf[600];
	k.MakeMove(sengo,teNum,teBuf);

	// 合法な指し手がない=負け(詰んでいる)
	if (teNum==0) {
		return -INFINITE;
	}

	// それぞれの指し手を評価する
	int value[600];
	for(i=0;i<teNum;i++) {
		k.Move(sengo,teBuf[i]);
		value[i]=k.Evaluate();
		if (sengo==1) {
			value[i]=-value[i];
		}
		k.Back(sengo,teBuf[i]);
	}
	
	// 指した後の評価の高い順に手をソートする
	for(i=0;i<teNum-1;i++) {
		int max=value[i];
		int maxid=i;
		for(j=i+1;j<teNum;j++) {
			if (value[j]>max) {
				max=value[j];
				maxid=j;
			}
		}
		swap(value[i],value[maxid]);
		swap(teBuf[i],teBuf[maxid]);
	}

	int retval=-INFINITE;

	Te childBest;
	for(i=0;i<teNum;i++) {
*		int depthExtension=CalcExtension(k,teBuf[i]);
		k.Move(sengo,teBuf[i]);
*		int newval=-AlphaBeta2(sengo ? 0:1,depth+1,depthMax+depthExtension,-beta,-max(retval,alpha),k,childBest);
		k.Back(sengo,teBuf[i]);
		if (newval>retval) {
			bestTe=teBuf[i];
			retval=newval;
		}
		if (retval>=beta) {
			return reval;
		}
	}
	return retval;
}

問題は、CalcExtensionの中身です。どんな手を深く読むと強くなるのでしょう?それに、何でもかんでも延長してしまったりすると、探索に時間がかかるばかりで、深く読んで欲しい手を深く読んでくれなくなってしまいます。一般的には、一本道になるような手…王手、囲いの駒を取る手、互いに利きを付けあっている駒の取り合い、同じ升での取り合いなど…を延長すると良い結果が得られるといわれています。

現在では、激指のチームが開発した方法が主流になっています。これは、指し手の種類に応じて、CalcExtensionを行う代わりに、読みの深さを変える方法です。コードは、以下のようになります。

int CalcDepth(const Kyokumen &k,const Te& te)
{
	int Extension=0;
	// teの種類に応じて何手深さを読むのか決定する
	return Extension;
}

int Think::AlphaBeta2(int sengo,int depth,int depthMax,int alpha,int beta,const Kyokumen &k,Te &bestTe)
{
*	if (depth>=depthMax) {
		return k.Evaluate(sengo);
	}
	int teNum=0;
	Te teBuf[600];
	k.MakeMove(sengo,teNum,teBuf);

	// 合法な指し手がない=負け(詰んでいる)
	if (teNum==0) {
		return -INFINITE;
	}

	// それぞれの指し手を評価する
	int value[600];
	for(i=0;i<teNum;i++) {
		k.Move(sengo,teBuf[i]);
		value[i]=k.Evaluate();
		if (sengo==1) {
			value[i]=-value[i];
		}
		k.Back(sengo,teBuf[i]);
	}
	
	// 指した後の評価の高い順に手をソートする
	for(i=0;i<teNum-1;i++) {
		int max=value[i];
		int maxid=i;
		for(j=i+1;j<teNum;j++) {
			if (value[j]>max) {
				max=value[j];
				maxid=j;
			}
		}
		swap(value[i],value[maxid]);
		swap(teBuf[i],teBuf[maxid]);
	}

	int retval=-INFINITE;

	Te childBest;
	for(i=0;i<teNum;i++) {
*		int UseDepth=CalcExtension(k,teBuf[i]);
		k.Move(sengo,teBuf[i]);
*		int newval=-AlphaBeta2(sengo ? 0:1,depth+UseDepth,depthMax,-beta,-max(retval,alpha),k,childBest);
		k.Back(sengo,teBuf[i]);
*		if (newval>retval && UseDepth>HyoujunUseDepth) {
*			newval=-AlphaBeta2(sengo ? 0:1,depth+HyoujunUseDepth,depthMax,-beta,-max(retval,alpha),k,childBest);
*		}
*		if (newval>retval) {
			bestTe=teBuf[i];
			retval=newval;
		}
		if (retval>=beta) {
			return reval;
		}
	}
	return retval;
}

違いをじっくりと味わって、意味を考えてみて下さい。

次回予告?

今後は、うさぴょん2で採用している、探索の中身を解説していきます。

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/148072/46526983

この記事へのトラックバック一覧です: コンピュータ将棋の作り方:

コメント

感謝

コメントを書く

(ウェブ上には掲載しません)

コンピュータ将棋BOOKS