本章では、指し手の評価を６章で簡易に行なった方法よりも正確に行なうことと、評価の低い指し手の探索を最初からしないことでプログラムを高速化し、より深く読むことを考える。
2015年10月 追記：前向き枝刈を行うプログラムは、今ではマイナーになった。代わりに、安全度の高い後ろ向き枝刈（最善手がαβと違う可能性があるが、より深く読めることで欠点を補える。）
ただし、ここではバランスが重視される。
評価の低い指し手の中に良い手が含まれるようでは、先読みを深くしてもそれは意味のない手順を読んでいることになる。そのため、相手の好手を見落としていたり、あるいは自分の好手を見落としているためにある手が指せない、などの状況が起きてくる。
そこで、プロの棋譜を元にチューニングを行なう※1などの方法が必要となってくる、
※1 指し手の評価で何番目になった手を実際にプロが指したか、平均などを求めて指し手の評価関数を変えていく
そのため、本章で扱う内容は評価関数に次いで、将棋プログラムで重要な部分である。
2015年10月 追記：あくまで、前向き枝刈を行う場合に重要である。
指し手の評価をする際に考慮するべき項目について考えてみよう。
・直接手 ・駒を取る手 ・駒を成る手 ・囲いを作る手 ・脅威 ・相手駒に次に取るぞ、という脅威を与える手、王手 ・自分の駒にかかっている脅威を減らす手（たとえば、「ヒモを付ける手※2」「逃げる 手」「取りをかけている駒を取る手」） ・空き王手※3、空き脅威を与える手、空き脅威を減らす手 ・焦点の歩※4
※2 ある自分の駒Aに別の自分の駒Bを利かせることで、Aが相手に取られたときに取り返せるようにすること。
※3 飛車・角・香などの前方で、相手の王との間にいる駒を動かして王手をかけること。
※4 複数の相手の駒が利いている場所に歩を打つこと。
とりあえず、以上くらいだろうか。
以上のほとんどは、実際に１手動かしてみたときの評価値の増減と、その１手による交換値の変化で表わすことができる。
たとえば、「直接手」なら、１手動かせば評価値が増減する。「脅威」は、１手動かすことで、その駒の利きとその駒を貫いていた飛び駒の利き先について、１手動かす前の交換値と、動かした後の交換値の差分を取ることで脅威を評価できる。
また、焦点の歩については、「相手の駒の利きが２つ以上集中しているところに歩を動かす（または打つ）手についてボーナスを与える」ことで評価できる。
駒を取る手についても、次に打ち込むことで攻撃のバリエーションが増えるので、ある程度ボーナスを与えることにしよう。※5
※5 これで、駒損でも駒を取って攻撃を続ける手などが読めるようになる
さっそく、手の評価をする関数の制作に取り掛かる。
// 手番から見て敵の駒
int IsEnemy(int SorE,KomaInf koma)
{
return koma!=WALL && !(SorE&koma);
}
// 手番から見て味方の駒
int IsSelf(int SorE,KomaInf koma)
{
return koma!=WALL && (SorE&koma);
}
// 手の価値の比較（qsort用）大きい順に並ぶようにする。
int teValueComp(const void *p1,const void *p2)
{
Te *te1=(Te *)p1;
Te *te2=(Te *)p2;
return te2->value-te1->value;
}
static const int Tbl[256]={
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};
// xは、何ビット１が立っているか
int bitnum(int x)
{
return Tbl[((unsigned char*)&x)[0]]+Tbl[((unsigned char*)&x)[1]]+Tbl[((unsigned char*)&x)[2]]+Tbl[((unsigned char*)&x)[3]];
}
void KyokumenKomagumi::EvaluateTe(int SorE,int teNum,Te *te)
{
int i;
int nowEval=Evaluate();
// Print();
for(i=0;i<teNum;i++) {
int LossS,LossE,GainS,GainE;
LossS=LossE=GainS=GainE=0;
KyokumenKomagumi _new(*this);
// 手番から見て敵の玉
KomaInf EnemyKing=SorE==SELF? EOU:SOU;
// 手番から見て敵の利き
unsigned int *_newControlE=SorE==SELF?_new.controlE:_new.controlS;
// 手番から見て味方の利き
unsigned int *_newControlS=SorE==SELF?_new.controlS:_new.controlE;
// 手番から見て味方の利き
unsigned int *_nowControlS=SorE==SELF?controlS:controlE;
KomaInf NewKoma=te[i].promote? te[i].koma|PROMOTED:te[i].koma;
// 実際に一手動かして、評価値の変動をみる。
_new.Move(SorE,te[i]);
te[i].value=_new.Evaluate()-nowEval;
if (SorE==ENEMY) {
// 敵の番の時には手の価値をひっくり返して置く
te[i].value=-te[i].value;
}
if (te[i].from!=0) {
// 駒が居た場所の脅威がなくなる
LossS-=Eval(te[i].from);
}
// 新しく移動した先での脅威が加わる
LossS+=_new.Eval(te[i].to);
// 相手に与える脅威と、新しく自分の駒にヒモをつけることで、減る脅威を計算
for(int dir=0;dir<12;dir++) {
if (CanMove[dir][NewKoma]) {
int p=te[i].to+Direct[dir];
if (_new.ban[p]!=EnemyKing) {
// 玉以外の駒に対する脅威
if (IsEnemy(SorE,_new.ban[p])) {
LossE+=_new.Eval(p);
} else if (IsSelf(SorE,_new.ban[p])) {
GainS+=Eval(p)-_new.Eval(p);
}
} else {
// 玉に与える脅威はそのまま計算すると大きすぎになるので調整する。
if (_newControlE[te[i].to]) {
if (_newControlS[te[i].to]) {
LossE+=1000;
} else {
LossE+=500;
}
} else {
LossE+=1500;
}
}
}
}
// 移動したことで、別の駒の飛び利きを通す（かも知れない）
if (te[i].from>OU) {
for(dir=0;dir<8;dir++) {
if ((_nowControlS[te[i].from]& (1<<(dir+16))) !=0) {
int p=_new.search(te[i].from,Direct[dir]);
if (_new.ban[p]!=WALL) {
// 飛び利きの通った先での交換値の再計算
if (IsEnemy(SorE,_new.ban[p])) {
LossE+=_new.Eval(p);
} else if (IsSelf(SorE,_new.ban[p])) {
GainS+=Eval(p)-_new.Eval(p);
}
}
}
}
}
// 移動した駒自身の飛び利きによる脅威の増減を計算する
for(dir=0;dir<8;dir++) {
if (CanJump[dir][NewKoma]) {
int p=_new.search(te[i].to,Direct[dir]);
// 例によって、玉に対する脅威は大きく評価されすぎるので調整する。
if (_new.ban[p]!=EnemyKing) {
if (IsEnemy(SorE,_new.ban[p])) {
LossE+=_new.Eval(p);
} else if (IsSelf(SorE,_new.ban[p])) {
GainS+=Eval(p)-_new.Eval(p);
}
} else {
if (_newControlE[te[i].to]) {
if (_newControlS[te[i].to]) {
LossE+=1000;
} else {
LossE+=500;
}
} else {
LossE+=1500;
}
}
}
}
te[i].value+=GainS-LossS;
if ((te[i].capture!=EMPTY && te[i].capture!=FU)) {
// 歩以外の駒を取る手は無条件に1500点プラスして、読みに入れるようにする
te[i].value+=1500;
}
if (te[i].from==FU && bitnum(_newControlE[0xaa-te[i].to])>1) {
// 焦点の歩…かも。
te[i].value+=50;
}
// 攻撃の価値はこれくらいの値（１０分の１）を加えると、実験ではちょうど良い
te[i].value+=LossE*1/10;
// te[i].Print();
// printf("val:%5d LossS:%5d LossE:%5d GainS:%5d GainE:%5d\n",te[i].value,LossS,LossE,GainS,GainE);
}
// char p[20];
// gets(p);
// 並び替え。
qsort(te,teNum,sizeof(te[0]),teValueComp);
}
「手の評価」を今まで作ってきた「αβ法」と組み合わせてみよう。
この際に、「手の評価が低い手」（＝無駄と思われる手）を読まないことで、読みが不正確になる危険性はあるが、今までより深く先読みが出来るようになるはずである。
このように、無駄と思われる手を最初から読まないことを、「前向き枝刈」という。一方で、αβ法のように、実際に先読みした値を元に、探索結果に影響を与えないような枝刈をすることを、「後ろ向き枝刈」と呼んでいる。
2015年10月 追記：先にも述べたように、安全度の高い後ろ向き枝刈（最善手がαβと違う可能性＝探索結果に影響を与える可能性があるが、より深く読めるようになることで欠点を補う。）
「前向き枝刈」には、本書の方法のように、全部の手を生成してから、評価関数などで評価する方法と、有望そうな手のみを生成する方法とが存在する。後者の方が調整も行いにくく、作成も難しいが、充分に作りこんだ場合は効果が高い方法であると言える。
評価点を基にした前向き枝刈には、二通りの考え方があり、
①ある評価点以下の手は読まない。 ②順番に並べた時に、ある順位以上は読まない。
①の方針で作成した場合、先読みの時間が安定しないが、駒得できる好手を見逃す可能性が少なくなる。
②の方法を選んだ場合、先読みの時間が安定するが、駒得できる好手を見逃す可能性が高くなる。※6
※6 ただし、代わりに、駒損する好手を読む可能性は上がる可能性もある。
今回は、①の方針で、－１００点以下の手は読まないとして、プログラムに取り込んでみる。すると、NegaAlphaBeta関数の一部は以下のようになる。
teNum=k.MakeLegalMoves(SorE,teBuf);
if (teNum==0) {
// 負け
return -INFINITE;
}
k.EvaluateTe(SorE,teNum,teBuf);
for(i=0;i0) {
break;
}
さらに、無駄と思われる手の処理について考えてみよう。
これは、主に「評価値がマイナスの手なのに、指してみると他よりも良い評価を返す」手についてのことになる。その駒を単に取られるだけで局面がほとんど変化していない場合、その手が良い評価を返すというのは水平線効果の可能性が高い。
このような手に対して、「その手を取る手」について余計に先読みを行なうことで、水平線効果を避けようという試みである。
2015年10月 追記：この方法は、処理が重過ぎた…。
これには、現在の局面に至るまでの指し手の履歴を利用する。
指し手の履歴で、現在の局面の直前の局面で選ばれた指し手が、さらにその直前の局面（＝前の前の局面）で指された駒を取る手で、かつ、前の前の局面で指した手の評価がマイナスだったときに、β値を超えないような値が返ってきているようなら、水平線効果の可能性があるとみて、２手延長してみることで可能になる。
指し手の履歴は、Stackというグローバル変数を利用して、「Stack[depth]=te[i];」をAlphaBetaの呼び出しの寸前に呼び出せば、ある局面に至る局面の履歴が取得できる。
以上の処理を取り込んだNegaAlphaBeta関数の一部は以下のようになる。