将棋プログラムを作ってみましょう。
お断り：私はC++で書くのが一番速くコードが書けるので、コード例は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);
}
}
なんていう、敵味方の駒の判別を準備しておきます。
局面ですが、単純に作るなら、とりあえず、１１＊１１（盤面の外には 外であることをあらわすデータ=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(" ９ ８ ７ ６ ５ ４ ３ ２ １ \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) || ()) {
// 歩と香は１段目に入ったら必ず成る
teBuf[teNum++]=;
} else {
// 成る手とならない手を生成
teBuf[teNum++]=;
teBuf[teNum++]=;
}
} else if (koma==KE) {
// 桂馬は２段目に入ったら必ず成る
} else if (koma==OU) {
// 敵の利きのあるところには動けない
} else if () {
// 成っても成らなくても良い
}
}
}
}
}
}
// 盤に持ち駒を打つ手
for() {
if (koma==FU) {
// 二歩と打ち歩詰めのチェック
}
}
}
えーと、まだ完成してません(^^;;;チェックしないと、先手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は、
これこそが、現在のコンピュータ将棋の中心アルゴリズムです。
---- 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をベースにします。
これは、
---- 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は、非常に効率の悪いアルゴリズムです。 ほんとーに全部の手と局面を探索しないといけません。
これを将棋で行うと、１秒間に100万局面を評価できる非常に高速なプログラムを作成出来たとしても、 （100万はでたらめに早いと思う。うさぴょんでは1万ぐらい。）30秒で3000万局面しか読めません。
大体、可能な指し手の数が８０ぐらいとしたら、 評価しないといけない局面が80*80*80*80=4096万局面 になるので、40秒かけて、4手先しか読めないことになります！
しかも、可能な指し手はちょっとしたことで200を超えるので、 4手先を読むには、 200*200*200*200=16億局面 なんと、1600秒（27分）かけないと4手先が読めません。
しかも、実際には、思考時間は20秒くらいで、普通にプログラムを作った場合には、1秒間に5万局面ぐらい しか読めないでしょう。そうすると、100万局面しか読めないことになります。 そうすると、指し手の数が80だとしてもMinMaxでは、3手＋α先しか読めないのです。 指し手の数が200だとすると、3手先を読むには、200*200*200/50000=160 で、160秒かけないと ３手先が読めません。
コンピュータの評価関数は、へたくそな人間の評価関数と比べても、だいたい読みが1〜3手浅いのに
匹敵するぐらい「だめ」な評価関数なので、「1手先しか読めない人間と互角」なプログラムという
ことになります(--;;
＃もっとも、これぐらいしっかりした評価関数を持つ人間なら３手の読みがしっかりできればほとんど初段のような気もします。
これはなんとかしないといけません。
実は、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;
}
αβの動作原理を説明するのはややこしいです。他力本願で、よそのページを紹介しておきます。 柿木将棋の柿木さんの将棋プログラムの解説のページです。
理論的には、αβを採用すると、同じ時間で２倍の深さまで読むことができます。 さっきの例だと、もしも100万局面/秒を達成できるなら、8手先が読めることになります。 これなら、評価関数がそれなりなら人間の有段者に対抗できそうです。
実際には、5万局面/秒だとしても、6〜7手先がきちんと読めれば、初段に近い力を
持てることでしょう。
＃ただし、実際には可能な指し手はすぐに200を超えることを考えると、だいたい4〜5手先しか読めなくなり、初段とは言い難いことになるでしょうが…。
ここまでは、基礎技術で、将棋プログラムを書き始めれば誰でも調べものをしながら到達できる地点です。 ここからが各将棋プログラムの工夫になります。
さて、理論的にはαβは十分高速（これ以上早いアルゴリズムは存在しない！）なのですが、
実は、その速さを達成するためには、非常に厳しい条件があります。
指し手が最終的な評価の良い順に並んでいないといけないのです！
＃そもそも、どの指し手が良いのか事前に分かっているなら、αβを呼び出す必要もありません。
もしも、最終的な評価の*悪い順*に並んでいた場合、αβは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手先が読めるでしょうか？
実験すると…駄目です(--;
所詮一手先をみたぐらいでは、ろくなことになりません。
相手の飛車先の歩を飛車で取る手が、歩の価値だけ点数が増えるから良い手だ、
なんて判断じゃ駄目なのです。
それでも、何もしないよりはましになっているでしょうか？計測してみましょう。
…まだ未計測…
将棋では、あまりにも可能な手の数が多くなることがあるため、前向き枝刈りとよばれる手法で、先読みをする指し手を絞り込むのが一般的です。
たとえば、もしも常に候補手を20手に絞り込むことができれば、αβが理想的に働いた場合、75万局面（1秒間に５万局面を読めれば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;
}
今思うと、かなりひどい枝刈りだったと思います(--;
ただし、刈った後に残す手が多かったので、ものすごい勝手読みは特に見られませんでした…
残す手が多いので５手先しか読めませんでしたが。
しかし、それぞれの指し手を評価する部分を、局面の評価を単純に呼び出すのではなく、 その指し手でどれぐらい得ができそうか？をきちんとプログラミングすれば、この方法は非常に有効です。
ところで、コンピュータチェスでは、このような前向き枝刈りの手法はほとんど採用されていません。
これは、可能な指し手の数が将棋と比べて少ないことが一つの理由であると思います。 全部の手を読むことで得られる強さが、読みの深さを増すことによる強さの向上を上回っているわけです。 読みぬけが発生した場合に極端にプログラムが弱くなるような何らかの性質 …次善手と最善手の差が大きく、最善手がしばしば局面の評価値だけを見るといったん悪くなっている、というような… を持っているのかも知れません。 それに、絞り込むために指し手を評価する作業がありますから、元々多いものを少なく絞り込むには有効ですが、元々少ないものをさらに少なくしようとしても単に無駄な時間をつかうだけのことも多いのかも知れません。
しかし、コンピュータチェスでも全く前向き枝刈りをしないわけではなく、このように手を絞り込む手法とは違った、
ある意味ではもっと穏やかな前向き枝刈りを使用しています。
チェスで行われている代表的な手法には、NullMoveと呼ばれる手法とFutilityPrunningと呼ばれる手法があります。
この手法は、将棋でも有効なので、そのうちここで解説するかもしれません。
既に紹介している方法で局面の評価と先読みを実際に行うと、実はいろいろな問題が起きてきます。
まず、問題その１から。
以下の局面で、先手番なら先手が飛車を素抜いてほとんど勝ちですが、
後手番だったら後手が飛車を素抜いてほとんど勝ちでしょう。
ですが、ここまでに紹介した評価関数では、この局面の点数はどちらの手番でも０点です。駒の損得はありませんからね。
----あとでちゃんとした図を入れる---- 持ち駒：歩1 ９ ８ ７ ６ ５ ４ ３ ２ １ +---------------------------+ |v香v桂v銀v金v玉v金v銀v桂v香|一 | ・ ・ ・ ・ ・ ・ ・v角 ・|二 |v歩 ・v歩v歩v歩v歩v歩v歩v歩|三 | ・ ・ ・ ・ ・ ・ ・ ・ ・|四 | ・v飛 ・ ・ ・ ・ ・ 飛 ・|五 | ・ ・ ・ ・ ・ ・ ・ ・ ・|六 | 歩 歩 歩 歩 歩 歩 歩 ・ 歩|七 | ・ 角 ・ ・ ・ ・ ・ ・ ・|八 | 香 桂 銀 金 玉 金 銀 桂 香|九 +---------------------------+ 持ち駒：歩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;
}
しかし、こんなコードでは、いくらなんでも先読みに時間がかかり過ぎです(^^;;さっきの図で、ぶつかり合っていない駒を進める手（たとえば、▲１四歩、▽１六歩、…）なんてお互いに読んでいたら、２五飛と８五飛はいつまでもぶつかりあったままで、次に指す手で取れる駒がある状態がずーっと続いて、いつまでも先読みが終わりません。
そこで、もうちょっと読む手をしぼって、とにかく駒のぶつかり合いを解決することを考えてみます。駒を取る手がある間はその手を指してみて先読みを続けることにしてみます。
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;
}
しかし、これだと、以下の局面で先手番を評価させてみると、すごく変な評価値が帰ってきます。先手番の駒を取る手は、３３角成（不成でもいいけど）しかありませんが、そんなことをしたら即座に同角とか同桂馬とかされて、歩と角の交換をした評価値になってしまいます。これを解決するために、「そこで先読みを中断して、その局面の評価値を得る」か、「駒を取る手を指して、先読みを続ける」かを選択できることにします。つまり、パスを許すわけです。
----あとでちゃんとした図を入れる---- 持ち駒：なし ９ ８ ７ ６ ５ ４ ３ ２ １ +---------------------------+ |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;
}
どうでしょう、速度的にもだいぶましになってきたのではないでしょうか？
読みの延長の実装は非常に簡単です。いつものプログラムにちょっとだけコードを追加すれば出来ちゃいます。
先頭に'*'をつけた行が今までとの違いです。
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の中身です。どんな手を深く読むと強くなるのでしょう？それに、何でもかんでも延長してしまったりすると、探索に時間がかかるばかりで、深く読んで欲しい手を深く読んでくれなくなってしまいます。一般的には、一本道になるような手…王手、囲いの駒を取る手、互いに利きを付けあっている駒の取り合い、同じ升での取り合いなど…を延長すると良い結果が得られるといわれています。
将棋プログラムを作成する上で、問題になることの一つに、序盤をどうするか？があります。普通に先読みを行っても、囲いを作ったり、攻める形を作ったりというのは不可能です。まともな将棋を指させるには、プログラムにどうにかして「定跡」を組み込む必要があるのです。
定跡を組み込む方法はいくつか考えられます。一番単純な方法は、直接プログラムを書く方法です。例えば、先手に四間飛車を指させるには、
if(先手) {
if (手数==1) return 76歩;
if (手数==3) return 66歩;
if (手数==5) {
if (盤面[85]==歩) return 77角;
return 86飛;
}
}
なんてやればいいのです。しかし、この方法には大きな欠点があります。後手が予想もできないことをしたらどうしましょう？例えば、76歩 34歩 66歩 同角！とかしてきても、このプログラムだと86飛としてしまいます。で、あとは、後手 57角成 とかすれば先手の不利は明らかです。予想も出来ないような事をされたかどうかチェックして、されていたら先読みを呼ぶようにすればいいのですが…どうやってチェックしましょう？プログラムにこういう局面じゃなかったらとかいう条件チェックのif文をたくさん並べる？この方法だと、プログラムを書くのがとっても大変そうです。そして、それは、実はデータとプログラムの分離が出来ていないのが問題なのです。
ここで、定跡について考えて見ます。
----これからまた書く----
うさぴょんで採用している