おお！ついでに、黒の駒の後ろにも白で描画された白の駒を置いてあります。分かりにくいけどbishopの十字がちゃんと白くなっていたりね。
JavaScript / CSS は次のようになった。
こうなると、盤面は違う色でも構わないので変更。さらにマスが正方形になっていないのでサイズを調整。r.bqkbnr pppp.ppp ..n..... .B..p... ....P... .....N.. PPPP.PPP RNBQK..R
2012/04/13
Blogger parts: Chess Board (cont.)
暗い背景の上に白いチェスの駒を表示すると、駒の本体のあたりが透けて白く見えない問題があったが、「黒の駒を白く表示した上に、白の駒を表示すればいいんだよ」というすごいアイデアを見つけた。
さっそくやってみる。
Blogger parts: Chess Board
これまでチェス盤の表示はプログラムの出力のASCII出力のチェス盤をpreで貼っただけだった。こんな感じ。
JavaScriptは次の通り。文字列をスキャンしてKとかnとかをチェスの駒へと変換し（unicodeにチェスの駒がある！）、全体をtableとして構成し、もとのエレメントと入れ替える。
Closure compilerにかけてscriptタグで囲んだものを、Bloggerのレイアウト > HTML/JavaScriptガジェットとして登録する。
次にCSSを設定。CSSはCSS3 Chess Boardを参考にさせてもらった。以下のCSSをテンプレート > アドバンス > CSSを追加 から設定。
unicodeに含まれるチェスの駒を使うと白い駒の白い部分が白くならないという問題があって（フォントは黒い部分を定義するものなので）、オリジナルのCSSだと市松模様にグラデーションをかけて白く見せている。どちらがいいかなと思ったんだけどグラデーションはなしにしている。
r. bqkbnr pppp. ppp . . n. . . . . . B. . p. . . . . . . P. . . . . . . . N. . PPPP. PPP RNBQK. . Rしかし、これだとみづらいので、これをclass="chessboard"をつけるだけで下図に変換するJavaScriptを書いた。 (2012/4/12 追記: スクリプトの変更前の画像に差し替え）
2012/03/28
Stalemate
現在の実装ではPawnを1歩づつしか進ませることしかできないので、32手で必ず手がなくなる。
32. rnbqkbnr . . . . . . . . . . . p. . . . pp. Ppppp PPp. PPPP . . P. . . . . . . . . . . . . RNBQKBNRこのとき引き分けとして1/2-1/2と表示して終了する。 ちなみに、上の例では白にも黒にも手がないので引き分けというのがしっくりくるが、このプログラムはどちらかが有効手がなくなった時点で引き分けにしている。リバーシなら相手にも手がないときに初めて引き分けだったが、Chessではこのプログラムであっていて、どちらかに有効手がなくなった時点でそれをstalemateとよび引き分けになる。 また将棋では、次のような場合は王には自殺する手しか残されてなく攻め手の勝ちとなる。
＿｜＿｜王｜ ＿｜飛｜＿｜ ＿｜金｜＿｜しかしChessではKingの自殺は有効手ではなく、パスもないため、そういう手しかなかった場合は有効手がないということで引き分けになる。 （Chessでは相手のKingは殺さない。殺してしまっては領民は従わない、生かして降伏させる方がよい。） 例えば、上とほぼ同じこういう局面（黒の番）はstalemateで引き分けである。
. . k . R . . Q .圧倒的に不利な局面でもChessではstalemateに持込み引き分けにしてしまうことがままあるので攻め手は最後まで気が抜けない。 Stalemateの具体例はWikipediaが詳しい。http://en.wikipedia.org/wiki/Stalemate
2012/03/26
Shannon: Programming a computer for playing chess, 1950.
Shannonが1949年に書いた論文に"Programming a computer for playing chess"というChessをコンピュータに実行させるにはというものがある。
http://portal.acm.org/citation.cfm?id=61701.67002
ENIACができたのが1946年で、プログラム内蔵方式のEDVACが1949年から研究所に入ったという話なのでEDVACのテストして書いたプログラムの話かもしれない。
Shannonはこの論文で、MinMax手法、盤面評価、静止探索、機械学習の可能性といった現在でも基本となっている手法をすでに発表している。
彼の書いたプログラムがどんなものであったかは分からないが論文から再現してみるのは面白そうなので書いてみようと思った。
ただし、彼が用いたのがENIACだったとすると配線で、EDVACだったとするとマシン語であったろうが、それはハードルが高すぎるのでC++ではなくCという程度にする。
今回は全体の枠組みをとりあえず書いてみた。
まだlast_moveやcastlingに関する情報は利用していないが、論文には必要だと書いてあったのでエントリーだけでも作っておく。
こういうところをみると実際に作ったなと感じる。
初期レイアウトも論文のままに、この数字が盤面評価のスコアとして使われる。
Cで書いてもC++っぽくなってしまう。
とりあえずPawnが前に進むだけ。
generateしたmovesに入っていればvalidということにする。
コンピュータはとりあえずランダムに。論文にはランダムはとても弱いと書いてある。まあ、fool's mateが決まるよね、ランダムじゃ。
http://portal.acm.org/citation.cfm?id=61701.67002
ENIACができたのが1946年で、プログラム内蔵方式のEDVACが1949年から研究所に入ったという話なのでEDVACのテストして書いたプログラムの話かもしれない。
Shannonはこの論文で、MinMax手法、盤面評価、静止探索、機械学習の可能性といった現在でも基本となっている手法をすでに発表している。
彼の書いたプログラムがどんなものであったかは分からないが論文から再現してみるのは面白そうなので書いてみようと思った。
ただし、彼が用いたのがENIACだったとすると配線で、EDVACだったとするとマシン語であったろうが、それはハードルが高すぎるのでC++ではなくCという程度にする。
今回は全体の枠組みをとりあえず書いてみた。
#include#include #include #include #include typedefstruct { int from_x; int from_y; int to_x; int to_y; int piece; } Move; typedefstruct { int board[8][8]; int side; // castling is available? int king_is_moved[2]; int rook_is_moved[2][2]; // last move Move last_move; // for 50 moves rule int moves_after_pawn; // next moves Move next_moves[8]; // 8 Pawns int num_moves; } Position;
まだlast_moveやcastlingに関する情報は利用していないが、論文には必要だと書いてあったのでエントリーだけでも作っておく。
こういうところをみると実際に作ったなと感じる。
void InitPosition(Position*);
void CopyPosition(Position* dst, constPosition* src);
void PrintPosition(constPosition*);
void PrintMove(constMove*);
void DoMove(constPosition*, constMove*, Position*);
void CalcPawnMoves(Position*, int, int);
void CalcBishopMoves(Position*, int, int);
void CalcKnightMoves(Position*, int, int);
void CalcRookMoves(Position*, int, int);
void CalcQueenMoves(Position*, int, int);
void CalcKingMoves(Position*, int, int);
void CalcMoves(Position*);
void ReadMove(Move*);
int IsValidMove(constPosition*, constMove*);
int a2piece(char);
char piece2a(int);
void ThinkNextMove(Position*, Move*);
conststaticchar* PIECE_MARK = "kqrbnp.PNBRQK";
staticint init_board[] = {
4, 2, 3, 5, 6, 3, 2, 4,
1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
-1, -1, -1, -1, -1, -1, -1, -1,
-4, -2, -3, -5, -6, -3, -2, -4
};
初期レイアウトも論文のままに、この数字が盤面評価のスコアとして使われる。
staticPosition position[200]; // how many is needed?
void InitPosition(Position* pos) {
int x, y;
int i = 0;
for (y = 0; y < 8; ++y) {
for (x = 0; x < 8; ++x) {
pos->board[x][y] = init_board[i];
++i;
}
}
pos->side = 1;
for (int s = 0; s < 2; ++s) {
pos->king_is_moved[s] = 0;
pos->rook_is_moved[s][0] = 0;
pos->rook_is_moved[s][1] = 0;
}
pos->last_move.from_x = -1;
pos->last_move.from_y = -1;
pos->last_move.to_x = -1;
pos->last_move.to_y = -1;
pos->moves_after_pawn = 0;
pos->num_moves = 0;
}
void CopyPosition(Position* dst, constPosition* src) {
memcpy(dst, src, sizeof(Position));
}
void PrintPosition(constPosition* pos) {
for (int y = 7; y >= 0; --y) {
for (int x = 0; x < 8; ++x) {
printf("%c", piece2a(pos->board[x][y]));
}
printf("\n");
}
for (int i = 0; i < pos->num_moves; ++i) {
constMove* m = &(pos->next_moves[i]);
PrintMove(m);
}
printf("\n\n");
}
Cで書いてもC++っぽくなってしまう。
void PrintMove(constMove* move) {
if (move->piece != 0) {
printf("%c%d%c%d%c ", 'a' + move->from_x, move->from_y + 1, 'a' + move->to_x, move->to_y + 1, piece2a(move->piece));
} else {
printf("%c%d%c%d ", 'a' + move->from_x, move->from_y + 1, 'a' + move->to_x, move->to_y + 1);
}
}
void DoMove(constPosition* src, constMove* m, Position* dst) {
assert(m->from_x >= 0 && m->from_x < 8);
assert(m->from_y >= 0 && m->from_y < 8);
CopyPosition(dst, src);
int x = dst->board[m->from_x][m->from_y];
dst->board[m->from_x][m->from_y] = 0;
dst->board[m->to_x][m->to_y] = x;
dst->side = -(dst->side);
}
// Calculates pawn moves.
// Assumes the piece of the given (x, y) is a pawn.
void CalcPawnMoves(Position* pos, int x, int y) {
Move* m = &(pos->next_moves[pos->num_moves]);
int to_y = y + pos->side;
if (to_y >= 0 && to_y < 8) {
if (pos->board[x][to_y] == 0) {
m->from_x = x;
m->from_y = y;
m->to_x = x;
m->to_y = to_y;
++(pos->num_moves);
}
}
}
とりあえずPawnが前に進むだけ。
void CalcBishopMoves(Position* pos, int x, int y) {
}
void CalcKnightMoves(Position* pos, int x, int y) {
}
void CalcRookMoves(Position* pos, int x, int y) {
}
void CalcQueenMoves(Position* pos, int x, int y) {
}
void CalcKingMoves(Position* pos, int x, int y) {
}
void CalcMoves(Position* pos) {
for (int y = 0; y < 8; ++y) {
for (int x = 0; x < 8; ++x) {
switch (pos->board[x][y] * pos->side) {
case1:
CalcPawnMoves(pos, x, y);
break;
case2:
CalcKnightMoves(pos, x, y);
break;
case3:
CalcBishopMoves(pos, x, y);
break;
case4:
CalcRookMoves(pos, x, y);
break;
case5:
CalcQueenMoves(pos, x, y);
break;
case6:
CalcKingMoves(pos, x, y);
break;
default:
// error
break;
}
}
}
}
void ReadMove(Move* move) {
printf("? ");
move->from_x = -1;
char buf[100];
if (fgets(buf, 100, stdin)) {
switch (strlen(buf)) { // fgets includes \n.
case5:
move->from_x = buf[0] - 'a';
move->from_y = buf[1] - '1';
move->to_x = buf[2] - 'a';
move->to_y = buf[3] - '1';
move->piece = 0;
break;
case6:
move->from_x = buf[0] - 'a';
move->from_y = buf[1] - '1';
move->to_x = buf[2] - 'a';
move->to_y = buf[3] - '1';
move->piece = a2piece(buf[4]);
break;
default:
// error!
break;
}
}
}
int IsValidMove(constPosition* pos, constMove* m) {
constMove* next_move = pos->next_moves;
for (int i = 0; i < pos->num_moves; ++i) {
if (next_move->from_x == m->from_x &&
next_move->from_y == m->from_y &&
next_move->to_x == m->to_x &&
next_move->to_y == m->to_y &&
next_move->piece == m->piece) {
return1;
}
++next_move;
}
return0;
}
generateしたmovesに入っていればvalidということにする。
int a2piece(char a) {
switch (a) {
case'p':
return1;
case'n':
return2;
case'b':
return3;
case'r':
return4;
case'q':
return5;
case'k':
return6;
default:
// error!
break;
}
return0;
}
char piece2a(int p) {
if (p >= -6 && p <= 6) {
returnPIECE_MARK[p + 6];
}
return' ';
}
void ThinkNextMove(Position* pos, Move* move) {
int i = rand() % pos->num_moves;
move->from_x = pos->next_moves[i].from_x;
move->from_y = pos->next_moves[i].from_y;
move->to_x = pos->next_moves[i].to_x;
move->to_y = pos->next_moves[i].to_y;
move->piece = pos->next_moves[i].piece;
}
コンピュータはとりあえずランダムに。論文にはランダムはとても弱いと書いてある。まあ、fool's mateが決まるよね、ランダムじゃ。
int main(int argc, char* argv[]) {
srand((unsigned)time(NULL));
InitPosition(&position[0]);
int ply = 0;
while (1) {
Position* pos = &position[ply];
CalcMoves(pos);
PrintPosition(pos);
Move move;
if (ply % 2 == 0) {
// player move
move.from_x = -1;
while (move.from_x == -1) {
ReadMove(&move);
if (!IsValidMove(pos, &move)) {
move.from_x = -1;
}
}
} else {
ThinkNextMove(pos, &move);
printf("-> ");
PrintMove(&move);
printf("\n\n");
}
DoMove(&position[ply], &move, &position[ply+1]);
++ply;
}
return0;
}
2011/07/16
Iterative Deepening
Iterative Deepening [1]は探索の深さを1から順にnまで増やしながら探索を行う手法である。
実際の試合では通常、思考のための制限時間が設けられているがIterative Deepeningを用いることで、設定していた探索の最大深さnに達する前に深さiで制限時間がきた場合でも、深さi-1あるいはi-2での最善手を答えることができる。これは通常のαβ探索で、宣言時間が来た時点での最善手を出力したのよりはいい手であることが期待できる。（move orderingが問題なければ、それでも問題がない可能性もあるが、そもそもmove orderingが完璧なら探索は不要）
また、逆に制限時間ぎりぎりまで探索を行い、探索の最大深さnを予め設定しないという戦略も考えられる。
Iterative Deepeningを用いる欠点としては、何度も探索を繰り返すため、一度に深さnまで探索することに比べて、計算時間がかかるということがある。しかし、実際にはreversiで探索の深さを2つ増やすと10倍のノード数を探索することになることから、計算時間の殆どは最後の深さで費やされる。
また、killer heuristicあるいはhistory heuristicとtransposition tableを用いることで、一度、探索したノードに関してのmove orderingに関するヒントがあるため、2回目以降のあるノードの探索はそれ以前の探索よりも効率が改善される。
[1] Marsland. Relative efficiency of alpha-beta implementations. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-83) (1983) pp. 763–766
[2] Plaat and University of Alberta. Dept. of Computing Science. A new paradigm for minimax search. (1994)
実際の試合では通常、思考のための制限時間が設けられているがIterative Deepeningを用いることで、設定していた探索の最大深さnに達する前に深さiで制限時間がきた場合でも、深さi-1あるいはi-2での最善手を答えることができる。これは通常のαβ探索で、宣言時間が来た時点での最善手を出力したのよりはいい手であることが期待できる。（move orderingが問題なければ、それでも問題がない可能性もあるが、そもそもmove orderingが完璧なら探索は不要）
また、逆に制限時間ぎりぎりまで探索を行い、探索の最大深さnを予め設定しないという戦略も考えられる。
Iterative Deepeningを用いる欠点としては、何度も探索を繰り返すため、一度に深さnまで探索することに比べて、計算時間がかかるということがある。しかし、実際にはreversiで探索の深さを2つ増やすと10倍のノード数を探索することになることから、計算時間の殆どは最後の深さで費やされる。
また、killer heuristicあるいはhistory heuristicとtransposition tableを用いることで、一度、探索したノードに関してのmove orderingに関するヒントがあるため、2回目以降のあるノードの探索はそれ以前の探索よりも効率が改善される。
abstract class NegaAlphaBetaTKIPlayer[N <: Node[N]](
override val maxDepth: Int,
override val numKillerMoves: Int
) extends NegaAlphaBetaTKPlayer[N](maxDepth, numKillerMoves) {
override def play(ply: Int, node: N, last: Move): Move = {
initKillerMoves(maxDepth)
initTranspositionTable()
var m = Move.empty
var s = 0
for (d <- 1 to maxDepth) {
var ret = play(node, Int.MinValue + 1, Int.MaxValue, d)
m = ret._1
s = ret._2
}
m
}
}
また、MTD(f)で深さiの探索でスコアsiが得られたとき、次の深さi+1での探索で用いるf値としてsiを用いることで、効率の改善を行うことができる。 abstract class MTDfIPlayer[N <: Node[N]](override val maxDepth: Int, override val numKillerMoves: Int) extends MTDfPlayer[N](maxDepth, numKillerMoves) {
override def play(ply: Int, node: N, last: Move): Move = {
var m = Move.empty
var f = 0
for (d <- 1 to maxDepth) {
var ret = mtd(node, f, d)
m = ret._1
f = ret._2
}
m
}
}
実験結果は次のようになった。 mtdfi = MTD(f) + Iterative Deepeningはmtdf = MTD(f)と比較して、ずいぶんと遅くなってしまった。 reversiでは、1手ごとに盤面が大きく反転するため、各盤面のマーカーの数の差を評価関数としている今の実装では、1手ずつ深さを大きくしては評価関数が大きく異なってしまう。そこで、深さを2つずつ深くすることにしたのがmtdfiiである。 mtdfiiでは驚異的な高速化が実現できていることが分かる。Plaatも文献[2]でIterative Deepeningを用いたほうがMTD(f)は高速化できると述べているが、それが確認できた。これは上述したように、正しいf値がわかっていればMTD(f)が高速に実行できることによる。 xtabs(node ~ name + depth + test, data=data) xtabs(node ~ name + depth + test, data=data) , , test = end40.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 27 144 312 1407 2748 12027 22896 95966 166264 mtdf 19 157 201 1145 2184 8630 19720 80814 125003 mtdfi 38 273 468 1350 2649 61645 71797 544975 617768 mtdfii 29 210 130 1222 977 9220 7333 70436 52315 , , test = end41.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 48 320 1260 4601 16389 62575 134156 697922 1344073 mtdf 26 249 540 2540 10144 32079 89519 272946 730291 mtdfi 51 550 2193 7426 25878 114998 307825 1092744 2608613 mtdfii 26 140 245 1714 2528 21369 14180 293350 71827 , , test = end42.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 47 240 880 3708 10722 38172 94721 284084 432764 mtdf 38 345 421 5835 4035 46867 34123 456385 278434 mtdfi 59 575 1580 8255 17903 96307 204907 1114367 1906220 mtdfii 38 107 181 843 1061 6954 5889 65086 37483 , , test = end43.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 54 180 765 2536 13292 34713 116837 267089 1174524 mtdf 67 110 707 1647 5795 14456 71506 140004 910524 mtdfi 74 217 1015 3946 12843 51678 189323 661060 2500599 mtdfii 78 66 459 571 3030 3384 33946 22912 366578 , , test = end44.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 52 344 1099 5003 15538 59180 147316 439640 997603 mtdf 40 240 499 2551 4997 25153 27638 185753 202377 mtdfi 37 165 606 2154 7053 22857 72144 283054 703381 mtdfii 33 127 292 1182 2762 10376 29753 64848 231725 , , test = end45.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 43 482 1091 7021 12591 61363 112906 633612 1143702 mtdf 26 372 229 4987 2873 53545 25900 821370 264835 mtdfi 145 548 1825 6801 9686 50700 80793 719172 1015111 mtdfii 26 270 203 2918 1652 28193 13046 344268 106753 , , test = end46.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 43 351 1251 6172 17777 63246 175963 527763 1486986 mtdf 39 281 523 4198 3262 39651 42332 329191 613156 mtdfi 88 330 1024 4863 16408 50115 247527 555860 3092708 mtdfii 28 198 308 1902 2881 16609 16787 121939 177208 , , test = end47.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 44 203 894 2684 12688 31567 94186 200162 544096 mtdf 36 78 429 2577 4856 19380 67651 109788 197836 mtdfi 51 435 1284 5069 14830 49130 123938 351612 863045 mtdfii 31 88 335 522 3212 2880 41819 17430 186658 , , test = end48.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 48 431 1052 8071 18760 81991 184514 788373 1864961 mtdf 67 326 915 4102 15734 29080 255981 243128 3512508 mtdfi 90 417 1938 6050 28545 70722 389946 779557 5202121 mtdfii 46 223 286 2382 4762 21489 45791 200969 416676 , , test = end49.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 56 232 1242 4025 13435 49126 157654 453791 1133343 mtdf 38 156 885 1148 11959 9846 121120 159526 1046491 mtdfi 51 338 1367 5939 17179 51172 150261 758475 1685930 mtdfii 39 122 267 1296 2464 14150 23171 137191 176559 , , test = end50.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 56 572 1332 13494 25639 172585 365969 2063853 3945385 mtdf 40 530 739 8118 10159 74391 123517 827792 1296946 mtdfi 65 1009 2034 28671 41322 395558 561635 4992068 6668513 mtdfii 39 304 334 5234 3586 46466 35443 567751 323205 , , test = end51.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 71 315 1259 5109 18757 62872 173480 641455 2174737 mtdf 52 125 622 3728 8393 28470 78740 280931 615093 mtdfi 85 451 1392 8534 17525 78786 171940 838877 1961416 mtdfii 47 146 415 1166 5141 10768 61652 75997 639172 , , test = end52.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 56 354 1211 4601 12285 46639 149329 504289 1772591 mtdf 86 222 1315 2712 10970 23226 138992 214488 1826514 mtdfi 103 286 1753 4269 18762 41305 238447 479219 3653675 mtdfii 100 148 411 1408 2408 10023 21096 77156 305320 , , test = end53.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 55 450 1795 7861 27736 82230 299993 1027148 3897564 mtdf 39 230 852 3732 12847 32240 150454 339665 1530138 mtdfi 53 397 1274 6754 19627 75227 210558 888269 2105971 mtdfii 42 239 437 2554 6465 21991 43476 201229 253059 , , test = end54.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 35 299 785 4811 11957 69781 154930 733142 1498804 mtdf 25 244 264 2154 2919 26304 27551 356998 277035 mtdfi 62 312 1215 3673 16481 47658 141373 617936 1525344 mtdfii 25 164 243 1698 2454 14098 19153 124606 154492 , , test = end55.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 69 524 1400 6788 25108 95356 268716 1443151 4697020 mtdf 37 222 807 5464 9661 66834 129831 1378381 1613133 mtdfi 72 697 1431 15361 29588 161211 314955 2492192 4609357 mtdfii 29 227 547 2525 8511 30598 93606 351371 1157032 , , test = end56.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 63 299 1484 5344 15299 57231 221934 698765 3553217 mtdf 54 129 983 1819 8245 17193 135445 175100 2163370 mtdfi 64 251 1404 4914 18623 61892 331602 895358 5403801 mtdfii 39 119 596 1174 3945 12069 56802 84958 990616 , , test = end57.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 56 323 1064 5476 16899 54500 152238 553410 1779973 mtdf 42 360 471 3790 6903 32076 69937 324390 743752 mtdfi 66 617 1692 8459 22629 100704 266140 922625 3069773 mtdfii 46 176 219 1598 2162 18404 21477 111504 174753 , , test = end58.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 82 663 2082 9142 35925 129141 421977 1384790 5002305 mtdf 65 351 1113 4090 17028 46623 194900 756321 2240661 mtdfi 50 765 1652 7709 18686 89967 228445 891754 1971828 mtdfii 63 403 428 3903 4312 48304 40838 413731 389535 , , test = end59.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 33 271 555 3398 6433 37380 60376 305924 473199 mtdf 26 234 340 2702 4503 53546 43223 664528 400769 mtdfi 33 194 396 5297 7543 37372 52452 525732 932387 mtdfii 24 187 173 1990 1591 23700 15184 174436 146142 xtabs(inode ~ name + depth + test, data=data) , , test = end40.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 35 175 425 1801 4229 16695 39191 128551 mtdf 20 40 217 308 2533 2516 22999 26555 153526 mtdfi 27 82 293 513 2092 18028 30854 170707 264561 mtdfii 51 110 181 457 1367 2586 20231 21128 163351 , , test = end41.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 83 401 1688 6224 26529 61534 342616 710022 mtdf 13 79 204 1032 3885 15013 41419 128792 334734 mtdfi 18 166 663 2509 8855 43754 110265 430495 1003273 mtdfii 14 59 155 723 1886 10708 10919 184394 64339 , , test = end42.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 11 58 344 1195 5207 14679 53900 121472 260799 mtdf 21 102 318 1858 3391 16191 30349 162371 247556 mtdfi 27 187 694 3024 8171 36022 88875 432348 862871 mtdfii 28 36 190 341 1451 3101 7970 36530 51367 , , test = end43.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 8 56 196 1158 3951 17136 44746 149262 474638 mtdf 37 83 430 1387 3786 13279 37569 131401 442206 mtdfi 39 144 618 3189 8846 45974 112050 590142 1391417 mtdfii 75 37 356 466 1666 3203 20743 21112 172946 , , test = end44.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 72 374 1593 6296 21843 62154 186770 486334 mtdf 27 64 360 767 3434 9050 18672 77939 127106 mtdfi 18 64 314 901 3379 10100 32943 111393 315380 mtdfii 38 41 212 475 1940 5170 22170 34052 162233 , , test = end45.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 16 76 492 1689 6158 17622 61537 211198 692718 mtdf 17 93 236 1221 3221 13172 30165 224838 317661 mtdfi 83 191 1371 2590 5791 15514 50209 215649 570301 mtdfii 32 87 283 688 2704 6991 18780 111687 156860 , , test = end46.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 14 82 447 2059 7448 25337 78953 225211 684600 mtdf 29 135 469 2330 3341 24990 40478 213988 580150 mtdfi 59 146 817 2600 13696 31254 217213 391750 2489635 mtdfii 54 76 273 689 2636 6915 31127 67477 452266 , , test = end47.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 10 51 292 911 4514 14649 42732 90664 245612 mtdf 20 26 198 708 2143 6788 25443 36938 98494 mtdfi 24 144 449 1742 5672 18807 47613 145070 360800 mtdfii 24 28 256 224 1402 1665 21316 14008 86311 , , test = end48.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 15 68 439 1909 8493 24921 92023 273357 1004646 mtdf 59 80 920 1342 16486 9785 277602 88358 3447820 mtdfi 62 149 1539 2876 23631 42225 360139 554422 4532668 mtdfii 115 56 498 671 3960 6040 37174 65008 339421 , , test = end49.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 10 61 328 1439 4500 19206 62015 189614 516945 mtdf 14 46 266 473 3466 4445 38142 70714 391549 mtdfi 17 118 422 1992 5657 18011 54053 320202 681282 mtdfii 18 51 125 660 1630 9782 12386 79578 85884 , , test = end50.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 17 88 541 2879 12255 44650 190361 612250 2196754 mtdf 25 96 457 1730 6632 17587 93442 205131 1057440 mtdfi 30 213 780 5795 13061 84063 198306 1206164 2473435 mtdfii 35 61 313 1376 3834 11202 43461 143730 415332 , , test = end51.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 67 379 1547 6704 19270 73905 238106 1043256 mtdf 22 34 296 987 3345 7547 43402 77323 312141 mtdfi 30 116 495 2381 6075 22924 70092 264603 763406 mtdfii 26 36 202 511 4045 4537 33661 26643 465021 , , test = end52.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 79 398 1421 5028 16171 66216 198423 850712 mtdf 54 100 992 1526 9120 13207 116745 121724 1447330 mtdfi 57 134 1216 2634 15355 30207 200087 375522 2724856 mtdfii 98 47 368 675 2033 4027 14491 33007 243152 , , test = end53.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 13 84 511 2262 9718 27978 107702 403217 1574439 mtdf 17 61 292 1152 3918 11160 50430 120455 499125 mtdfi 17 113 404 2184 6164 26825 70732 309251 715027 mtdfii 26 110 228 1049 2818 6967 23303 67523 146003 , , test = end54.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 61 347 1123 6213 19908 84094 231311 824160 mtdf 13 81 186 562 2415 7050 26675 95999 285069 mtdfi 39 117 876 1504 12164 19943 102348 220389 1096924 mtdfii 13 49 183 407 2193 5042 21355 37920 192041 , , test = end55.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 16 76 470 1598 10615 28906 120124 467316 2071576 mtdf 25 46 411 1136 5360 14684 79257 363423 1027242 mtdfi 36 159 542 3274 10154 40651 123161 720938 1885125 mtdfii 26 62 428 592 8595 7518 64036 151976 798874 , , test = end56.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 11 69 338 1693 4845 23624 75291 276756 1133606 mtdf 37 57 553 1019 4991 12052 69517 127131 933129 mtdfi 39 134 853 3004 11170 40989 137902 552298 2047606 mtdfii 56 43 393 487 2193 8249 35652 45701 517070 , , test = end57.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 10 62 330 1810 5836 21013 63370 246939 734281 mtdf 18 111 204 1351 2652 12826 23726 141613 255644 mtdfi 25 192 536 2599 6837 34051 82945 326333 969907 mtdfii 31 122 146 1125 1340 9303 12345 55076 101367 , , test = end58.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 15 127 597 2792 11048 41198 127573 477666 1925393 mtdf 27 78 402 1404 5113 19975 55775 286178 668517 mtdfi 24 197 520 2199 6113 29353 77148 293688 735727 mtdfii 34 155 240 1791 2478 15063 23048 239345 221394 , , test = end59.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 13 54 262 853 3544 10599 38819 98781 320323 mtdf 22 70 330 860 4335 15360 45494 171830 442720 mtdfi 22 58 301 1392 4054 10364 28514 127138 616389 mtdfii 32 55 238 583 2039 6497 20395 42391 198626 xtabs(time ~ name + depth + test, data=data) , , test = end40.pos
, , test = end40.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 192 344 591 967 1712 3217 7476 17203 45032
mtdf 212 360 673 864 1838 2277 8747 12284 47928
mtdfi 266 481 775 1008 1820 9848 14145 77050 106235
mtdfii 327 498 553 968 1296 2466 6302 11380 37774
, , test = end41.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 200 532 950 1946 4173 14444 28540 159529 296993
mtdf 201 476 684 1431 2925 8170 18707 58725 134018
mtdfi 237 654 1233 2443 5786 23117 54947 205308 462909
mtdfii 194 403 555 1226 1667 6319 5240 80132 22742
, , test = end42.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 197 448 839 1641 3339 8264 22135 52980 94388
mtdf 241 555 754 2117 2351 9530 12319 76665 85495
mtdfi 281 706 1145 2657 4913 18456 39600 198399 357176
mtdfii 273 351 583 883 1299 2705 3791 17235 16225
, , test = end43.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 192 455 740 1554 3350 10251 23406 75513 216398
mtdf 343 467 914 1625 2849 7777 16976 60063 178443
mtdfi 350 563 1144 2700 5366 23269 51047 250602 583770
mtdfii 408 333 758 941 1619 2574 8574 10655 64743
, , test = end44.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 218 520 934 1977 4436 13719 36305 99221 250647
mtdf 285 449 837 1289 2586 5851 9100 36664 52860
mtdfi 241 436 834 1444 3257 7220 21003 64578 172130
mtdfii 287 351 641 1026 1799 4056 9750 18874 61517
, , test = end45.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 237 575 1017 2081 4110 10471 29125 102126 294069
mtdf 218 528 663 1708 2405 8171 13207 109720 117397
mtdfi 458 682 1565 2409 3791 9031 22507 103948 233756
mtdfii 259 472 672 1275 1994 5015 8518 51630 55499
, , test = end46.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 234 584 1024 2177 5109 13252 39768 101521 322282
mtdf 302 610 938 2019 2970 10998 20808 80104 264504
mtdfi 412 594 1238 2398 8311 15621 102484 175383 1147167
mtdfii 320 445 732 1185 2251 4249 12565 28659 137486
, , test = end47.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 211 407 845 1413 3666 8094 21691 42747 123128
mtdf 255 289 685 1233 2162 4401 13992 17980 45107
mtdfi 280 623 994 1986 4214 10705 25330 71187 175736
mtdfii 249 314 663 684 1610 1708 10429 6676 38406
, , test = end48.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 220 510 947 2328 5209 15548 42680 146659 433613
mtdf 379 504 1166 1826 7198 6729 90920 46893 1165974
mtdfi 397 625 1546 2541 10675 20484 139057 237483 1724120
mtdfii 417 433 752 1275 2660 4618 14549 35254 119404
, , test = end49.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 212 456 952 1861 3647 11814 32138 96812 241927
mtdf 223 387 816 1011 3061 3418 20681 34559 186244
mtdfi 247 564 1030 2249 4542 11233 30069 161707 341093
mtdfii 249 369 576 1121 1643 5605 7019 35260 40367
, , test = end50.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 235 569 1002 2864 6552 24849 77082 298901 2002592
mtdf 267 573 911 2165 4071 11508 38965 110762 409172
mtdfi 298 781 1271 4687 7968 48354 93651 639259 1143363
mtdfii 299 466 736 1833 2501 7562 16264 76513 139852
, , test = end51.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 233 527 970 1964 5067 11699 39280 120552 512157
mtdf 287 348 819 1535 2941 5385 22720 40695 148588
mtdfi 326 632 1079 2609 4727 14342 38478 142872 399493
mtdfii 288 351 686 1001 2814 3552 16272 14322 176716
, , test = end52.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 213 564 947 1915 3675 10595 31643 106557 377542
mtdf 381 550 1282 1840 5208 8920 46244 67656 535107
mtdfi 395 577 1529 2411 8080 16423 83995 182167 1124812
mtdfii 445 396 758 1160 1762 3328 6937 18772 82253
, , test = end53.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 232 561 1170 2668 7390 18835 65650 239651 902737
mtdf 252 452 847 1658 3404 7237 28050 62352 256171
mtdfi 250 575 1024 2608 5440 18398 47266 196535 446006
mtdfii 292 511 707 1559 2529 5695 12128 42288 66074
, , test = end54.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 205 476 869 1738 4508 12885 41999 127080 392055
mtdf 203 497 636 1186 2198 5136 13612 52716 127569
mtdfi 354 564 1311 1880 7277 11499 47860 113797 489012
mtdfii 211 398 646 1015 2049 3526 10752 21598 83234
, , test = end55.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 254 541 1037 2085 7345 17497 67683 249175 1083552
mtdf 285 412 948 1710 4070 9539 39537 190733 495246
mtdfi 355 688 1150 3265 7303 25520 69167 409245 1031610
mtdfii 266 437 855 1315 4756 5660 30332 70663 357100
, , test = end56.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 223 492 965 2123 4420 14306 43053 152191 625376
mtdf 345 421 1093 1447 3981 7542 37263 63112 466109
mtdfi 353 601 1350 2810 7680 23314 78749 282362 1124166
mtdfii 341 385 842 1024 2111 5437 15539 24942 210108
, , test = end57.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 202 493 1000 2350 4874 14416 36762 148146 411699
mtdf 248 627 686 1726 2438 8153 13480 72412 123414
mtdfi 289 721 1159 2927 5779 23182 54314 204918 591781
mtdfii 308 556 562 1439 1506 6935 6630 33987 43895
, , test = end58.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 269 664 1279 3055 7966 25900 74164 266082 1047197
mtdf 319 521 988 1825 4327 11638 34256 150629 381071
mtdfi 303 759 1169 2598 5121 18952 47575 170188 422570
mtdfii 334 617 816 1902 2483 9966 13338 108924 107658
, , test = end59.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 205 448 781 1462 2903 7098 18863 51594 140848
mtdf 252 479 775 1415 3074 9710 21045 92571 185497
mtdfi 259 437 765 1877 3263 7207 15440 73102 284825
mtdfii 282 422 676 1212 1788 5052 9615 25040 79079
[1] Marsland. Relative efficiency of alpha-beta implementations. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-83) (1983) pp. 763–766
[2] Plaat and University of Alberta. Dept. of Computing Science. A new paradigm for minimax search. (1994)
2011/07/10
MTD(f)
ScoutのTest関数およびNegaScoutのnull-window searchは各ノードの真のminmax値を求めることはせずに、ある閾値より大きいか小さいかだけを調べることで多くのcut-offを引き起こし、その結果、高速な探索を実現している。しかし、Test関数が失敗した場合、すなわち、そのノードの探索を省略することができないことが分かったとき、ScoutおよびNegaScoutは通常のαβ探索を行う。
Plaatらによって考案されたMTD [1]はScoutおよびNegaScoutのその問題点を解決する。MTDは通常のαβ探索は一切行わず、Test関数のみを用いる。現在、αβ探索から派生した探索手法の中では最も高速な探索として知られている。
MTDにおけるTest関数はMemory-enhanced Test (MT)とよぶ。これは、NegaScoutのnull-window searchにTransposition tableを加えたものと考えてよい。（現論文ではスコアに実数値を使っているところが違うという記述があるが、そこは本質的な差ではないと思う。むしろ、alpha cut、beta cutの際に実際の値を返すところに差がある。）
ベンチマーク結果のNegaScoutとの比較は次のようになった。
端末ノード数
内部ノード数
実行時間
概ね高速であるが、ときどき非常に遅い時がある。
[1] Plaat and University of Alberta. Dept. of Computing Science. A new paradigm for minimax search. (1994)
Plaatらによって考案されたMTD [1]はScoutおよびNegaScoutのその問題点を解決する。MTDは通常のαβ探索は一切行わず、Test関数のみを用いる。現在、αβ探索から派生した探索手法の中では最も高速な探索として知られている。
MTDにおけるTest関数はMemory-enhanced Test (MT)とよぶ。これは、NegaScoutのnull-window searchにTransposition tableを加えたものと考えてよい。（現論文ではスコアに実数値を使っているところが違うという記述があるが、そこは本質的な差ではないと思う。むしろ、alpha cut、beta cutの際に実際の値を返すところに差がある。）
def mt(node: N, gamma: Int, depth: Int): (Move, Int) = {
if (depth == 0 || node.isTerminal) {
return (Move.empty, score(node))
}
// check transposition table
val (recordedMove, recordedScore) = probeNode(node, depth, gamma - 1, gamma)
var moves = node.possibleMoves().toList
// use the recorded move if it is available
if (recordedMove != Move.empty && (moves contains recordedMove)) {
moves = recordedMove :: (moves filterNot {_ == recordedMove})
}
var bestMove = Move.empty
var g = Int.MinValue + 1
for (m <- moves) {
val n = node.play(m).get
val (_, s) = mt(n, -gamma + 1, depth - 1)
if (-s >= gamma) {
// record transpositon table
recordNode(node, depth, -s, TranspositionTable.BETA, m)
return (m, -s)
}
if (-s > g) {
bestMove = m
g = -s
}
}
if (g < gamma)
recordNode(node, depth, g, TranspositionTable.ALPHA, bestMove)
(bestMove, g)
}
そして、MTを使う、MT Driver関数が次のようになる。これは、最初、解の上限upperと下限lowerをそれぞれ+∞、-∞に設定し、適当な値fからMTを用いて解の探索を行い、upperとlowerが一致したとき、それが求めるminmax値になるというものである。 def mtd(node: N, f: Int, depth: Int): (Move, Int) = {
var g = f
var bestMove = Move.empty
var upper = Int.MaxValue
var lower = Int.MinValue + 1
while (lower < upper) {
val bound = if (g == lower) g + 1 else g
val (m, s) = mt(node, bound, depth)
g = s
bestMove = m
if (g < bound) {
upper = g
} else {
lower = g
}
}
return (bestMove, g)
}
ベンチマーク結果のNegaScoutとの比較は次のようになった。
端末ノード数
xtabs(node ~ name + depth + test, data=data)
, , test = end40.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 13 118 150 869 1426 6877 11739 50161 107685
negascout_k 13 118 141 902 1324 7883 10528 65640 88274
negascout_t 13 118 144 825 1217 5736 8835 36378 72029
negascout_kt 13 118 141 875 1138 7226 10083 53044 73327
mtdf 29 234 201 1173 1302 7735 9647 52626 63001
, , test = end41.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 30 277 498 3942 5522 38672 51316 637813 507317
negascout_k 26 205 328 2391 3854 21961 29935 379585 282423
negascout_t 30 255 423 3607 4750 34045 33459 504176 278609
negascout_kt 26 187 325 2184 3832 19717 25478 334212 205353
mtdf 26 210 280 2038 3523 23302 32603 182267 263264
, , test = end42.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 30 177 375 2436 3176 25612 42839 248198 549411
negascout_k 30 114 325 1181 2374 8101 27187 64654 213624
negascout_t 30 169 351 2638 3081 22922 36559 204722 367558
negascout_kt 30 114 310 1176 2352 8224 22283 57193 170565
mtdf 38 210 290 2563 2279 21173 17029 163380 125509
, , test = end43.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 49 64 455 1241 5358 13714 74902 246768 1342957
negascout_k 48 59 300 936 3259 8122 34030 82466 697031
negascout_t 49 64 452 1121 4794 11178 66526 159512 873095
negascout_kt 48 59 300 1122 2793 6589 28902 77931 833684
mtdf 78 103 795 1278 4137 9855 62631 83677 626759
, , test = end44.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 37 163 718 2376 6146 31217 41518 382253 369021
negascout_k 31 154 553 1903 4252 19442 32793 193691 250324
negascout_t 37 145 661 1978 5712 26938 35992 307232 271322
negascout_kt 31 134 526 1690 3977 19028 28238 198876 188543
mtdf 33 133 479 1493 3613 16429 20386 106444 138136
, , test = end45.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 34 341 307 5106 2720 48033 26628 663943 243477
negascout_k 24 263 246 4243 2446 42004 26254 542838 293315
negascout_t 34 350 293 4548 2435 44768 18250 507703 154510
negascout_kt 24 266 236 3649 2189 39254 24296 414675 204045
mtdf 26 348 197 3686 1771 32145 15908 357230 111041
, , test = end46.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 25 374 485 9812 9666 120794 121581 867828 1146500
negascout_k 24 239 412 4179 5676 34681 53114 199289 393103
negascout_t 25 346 440 8225 9262 92633 105958 674553 820007
negascout_kt 24 221 399 4038 5138 34552 50520 157812 320921
mtdf 28 331 337 2732 2064 25001 25891 206345 289721
, , test = end47.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 47 77 742 709 12574 6465 147226 35518 647303
negascout_k 36 76 661 635 7067 6277 95607 39140 374661
negascout_t 47 77 735 507 12231 4950 117537 20431 415691
negascout_kt 36 76 626 454 10148 4509 86232 17140 273479
mtdf 31 78 376 598 4341 3657 54517 20163 137717
, , test = end48.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 29 237 487 4048 8711 47471 101834 447611 1157189
negascout_k 28 215 426 2508 5893 27912 54901 234412 535168
negascout_t 29 225 435 3325 7348 38797 92198 342054 921632
negascout_kt 28 215 378 2523 5536 23540 57060 212023 430229
mtdf 46 260 452 2665 4791 21272 76293 188805 1262584
, , test = end49.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 34 278 539 1791 6544 15755 119662 171897 1286707
negascout_k 34 178 556 1283 7316 10730 84280 187484 469384
negascout_t 34 253 526 1578 5643 12621 96787 130468 741520
negascout_kt 34 170 523 1182 7096 9134 93741 147926 399412
mtdf 39 116 478 1031 6895 8009 67221 119862 584316
, , test = end50.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 33 323 675 12049 10445 311521 165628 8331136 2730443
negascout_k 33 307 540 5224 6775 77991 95550 1070570 1200398
negascout_t 33 323 604 10528 8292 248164 121633 0 1549757
negascout_kt 33 307 511 5195 5647 71885 70762 877446 783511
mtdf 39 362 454 6862 5704 58813 58077 580193 530472
, , test = end51.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 59 202 1030 1938 19853 24097 375925 327750 8490980
negascout_k 59 155 712 1635 9593 20397 82927 222009 969788
negascout_t 59 205 1005 2013 18482 20749 303961 247261 0
negascout_kt 59 145 661 1583 9301 19182 81196 146625 912394
mtdf 47 124 546 1780 7955 13778 59771 111734 458086
, , test = end52.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 63 180 902 1709 5654 19288 81468 195141 1277140
negascout_k 37 162 353 1527 3548 16149 44295 148178 676770
negascout_t 63 173 860 1687 4917 15049 67976 134405 922381
negascout_kt 37 163 327 1608 3252 13121 47402 111351 550509
mtdf 100 229 1386 2256 8565 17936 80934 139339 1002842
, , test = end53.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 43 349 1278 10972 25288 247619 274617 10298036 3186665
negascout_k 35 279 855 4318 11674 31320 158313 327077 1444664
negascout_t 43 320 1146 10194 22327 204413 250846 0 2293979
negascout_kt 35 271 782 4716 10903 29281 164489 260376 1312628
mtdf 42 198 583 2503 7333 22081 94618 190844 782647
, , test = end54.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 23 216 371 2194 5870 26600 92194 287651 927408
negascout_k 24 189 262 1950 2957 22626 34695 273318 345191
negascout_t 23 216 371 2066 5222 20270 70386 218128 615772
negascout_kt 24 181 261 1593 2659 18939 27884 212148 244200
mtdf 25 246 249 1644 2675 15708 20004 189045 172175
, , test = end55.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 49 295 857 4616 20627 59091 189197 1009661 3447413
negascout_k 46 281 784 3663 12208 42926 157864 535946 1913433
negascout_t 49 290 782 3765 19311 49978 174816 684694 2790214
negascout_kt 46 281 743 3258 13625 42493 152997 394130 1709642
mtdf 29 219 583 3210 8008 35739 102432 674335 894445
, , test = end56.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 56 120 1326 1596 14771 21502 222253 230785 6013316
negascout_k 54 111 825 1349 5028 14212 63928 147220 1852309
negascout_t 56 120 1226 1463 12164 18036 180860 163746 4371241
negascout_kt 54 111 768 1262 3992 11816 48671 105271 1901167
mtdf 39 130 849 1716 6891 12869 108870 105432 1541331
, , test = end57.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 38 237 507 4475 4477 61001 30822 849439 392082
negascout_k 37 161 480 2561 4497 16136 32622 163275 394994
negascout_t 38 237 496 4291 4445 52345 31573 716148 306181
negascout_kt 37 161 451 2463 4398 15841 36980 157818 383875
mtdf 46 283 390 2681 3991 26394 32885 212230 320514
, , test = end58.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 55 547 863 14095 16348 194209 211595 2727903 2286834
negascout_k 55 407 830 4674 13645 56220 170146 811251 1984559
negascout_t 55 498 847 11013 16801 159529 187444 2205883 1854687
negascout_kt 55 323 821 4154 15337 53196 183057 755832 1836974
mtdf 63 235 877 3600 10648 36041 106170 381251 1121595
, , test = end59.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 18 214 209 2844 2643 58239 30403 1008983 216835
negascout_k 18 197 205 2070 2262 36733 23426 345174 193849
negascout_t 18 217 204 2730 2126 46808 21839 489119 134627
negascout_kt 18 208 199 1969 2081 33587 19116 256418 137030
mtdf 24 225 243 2609 2325 27312 19056 241424 147367
内部ノード数
xtabs(inode ~ name + depth + test, data=data)
, , test = end40.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 25 146 228 1486 2075 12348 17988 110404
negascout_k 11 25 136 229 1365 2139 11491 19991 99489
negascout_t 11 25 144 228 1345 1922 9857 14867 78863
negascout_kt 11 25 136 229 1257 2011 11958 17234 87156
mtdf 51 84 444 474 2569 2858 14480 19742 87419
, , test = end41.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 99 187 1437 2399 15724 23784 276227 263413
negascout_k 11 81 171 1109 1951 11428 16272 209894 169736
negascout_t 11 99 187 1464 2427 14722 17715 260280 178906
negascout_kt 11 80 171 1067 2238 10939 14737 215444 136676
mtdf 14 92 372 1205 4666 16123 42790 112425 341222
, , test = end42.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 10 59 221 933 2237 9461 30490 93282 386576
negascout_k 10 46 193 579 1931 3864 23020 29194 181507
negascout_t 10 59 222 1011 2311 9476 27946 84480 286373
negascout_kt 10 46 197 590 2012 4532 20312 27993 158697
mtdf 28 232 475 2670 3482 20447 23804 150417 165449
, , test = end43.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 7 36 137 817 1623 9972 23253 175405 490033
negascout_k 7 31 110 662 1038 6449 10930 71533 227741
negascout_t 7 36 137 847 1515 9055 21982 133849 335105
negascout_kt 7 31 110 815 946 5840 9931 78039 271967
mtdf 75 162 995 2208 6432 19594 63710 192235 576167
, , test = end44.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 56 289 1066 2970 16492 22113 202603 199765
negascout_k 11 47 238 682 2221 9250 20116 100449 145518
negascout_t 11 52 289 1005 2982 14577 19810 172924 150666
negascout_kt 11 43 255 736 2183 9696 17478 104399 109212
mtdf 38 79 520 923 4652 9742 15219 75605 94409
, , test = end45.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 15 69 244 1148 2709 11993 28158 196678 275525
negascout_k 15 63 242 998 2675 10515 30380 159167 345525
negascout_t 15 69 244 1099 2825 12641 23895 169888 201339
negascout_kt 15 63 242 950 2745 11038 31767 149743 277033
mtdf 32 151 237 1421 2790 11477 23465 140888 163771
, , test = end46.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 13 85 283 3247 5509 45549 60467 352518 506864
negascout_k 13 80 238 1790 3208 16933 30125 93203 198553
negascout_t 13 85 259 3102 5496 38485 53279 307404 383787
negascout_kt 13 70 237 1962 3074 17963 28074 95152 170354
mtdf 54 327 779 3835 4706 40256 61445 342364 741716
, , test = end47.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 9 23 233 242 4412 2907 50354 16539 265864
negascout_k 9 23 237 218 2495 2557 35508 14928 170292
negascout_t 9 23 253 213 4536 2650 44470 11196 189768
negascout_kt 9 23 236 196 3402 2486 32863 9442 131268
mtdf 24 35 194 872 1816 7573 22351 40556 70613
, , test = end48.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 14 54 269 1162 4806 15760 57034 161902 590192
negascout_k 14 48 268 748 3740 8510 40008 78939 392969
negascout_t 14 53 246 1094 4298 14212 54275 136782 508642
negascout_kt 14 48 245 807 3636 7758 41386 76328 347276
mtdf 115 174 3686 1565 33706 11014 318696 87909 3335746
, , test = end49.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 9 87 175 665 2430 6695 50796 96831 633869
negascout_k 9 76 170 487 2145 5294 30454 89221 199667
negascout_t 9 87 174 656 2332 6067 45934 82621 411842
negascout_kt 9 74 173 486 2280 4719 35268 76532 185430
mtdf 18 59 398 425 4388 5808 43475 52318 436428
, , test = end50.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 16 58 381 2252 6548 61806 113884 1698516 2008267
negascout_k 16 59 318 1260 4729 18750 74147 278057 1047587
negascout_t 16 58 367 2221 5535 53573 90114 0 1304914
negascout_kt 16 59 319 1399 4528 17254 60574 237079 790573
mtdf 35 107 521 1606 5981 14810 61181 153408 602477
, , test = end51.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 52 300 652 5511 8643 101866 120491 2358758
negascout_k 11 51 272 577 3892 6765 42186 76838 473081
negascout_t 11 52 298 751 5326 9104 90639 110583 0
negascout_kt 11 51 262 579 3906 8330 40806 69717 430606
mtdf 26 47 300 1139 3389 8412 31932 77393 248831
, , test = end52.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 59 253 683 1842 8098 26735 85174 439938
negascout_k 11 50 168 640 1745 7181 21864 71238 303779
negascout_t 11 59 253 709 1704 7328 24112 69626 346116
negascout_kt 11 50 168 670 1638 6773 22229 62285 266658
mtdf 98 239 2778 2591 22377 21733 207041 177547 2162716
, , test = end53.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 12 89 346 2509 7090 55204 88090 2234507 1190850
negascout_k 12 86 308 1784 4077 13542 59671 148293 549581
negascout_t 12 88 319 2624 6861 52306 86502 0 961771
negascout_kt 12 84 283 2052 4077 15441 58487 147603 537028
mtdf 26 77 329 1186 3397 11747 43672 108713 424288
, , test = end54.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 50 175 531 2409 7285 37752 83641 392862
negascout_k 11 52 179 490 2438 6557 31799 79308 340974
negascout_t 11 50 175 514 2314 6773 33036 73678 301036
negascout_kt 11 51 179 427 2273 6603 28324 71890 267328
mtdf 13 129 186 663 2258 6736 21495 77638 198195
, , test = end55.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 15 65 404 1248 9188 19798 92140 392794 1662603
negascout_k 15 61 358 953 5513 12038 80770 157799 951606
negascout_t 15 65 408 1148 9117 17778 87351 304024 1364431
negascout_kt 15 61 360 905 6644 12260 78871 147038 837889
mtdf 26 62 425 1455 4854 17477 65316 379933 615088
, , test = end56.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 10 45 311 757 3912 12865 57796 140488 1530114
negascout_k 10 37 252 541 2067 8742 25142 94894 492491
negascout_t 10 45 317 742 3509 12036 51373 113677 1235365
negascout_kt 10 37 247 534 1841 8398 21623 80730 545025
mtdf 56 108 877 1530 8107 14727 110192 142411 1358622
, , test = end57.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 9 52 173 1432 1739 19135 13780 285120 168055
negascout_k 9 38 175 1049 1675 7488 14165 98433 164247
negascout_t 9 52 173 1530 1940 17446 14387 266146 140052
negascout_kt 9 38 172 1163 1844 7637 15122 104688 154033
mtdf 31 160 344 1521 2993 13571 26000 131647 242334
, , test = end58.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 14 172 303 4253 6287 61713 81874 882182 893434
negascout_k 14 111 262 1723 3872 25178 44528 357158 573485
negascout_t 14 172 303 3644 6467 55475 71662 784289 733810
negascout_kt 14 98 262 1657 4426 23251 49307 364851 532404
mtdf 34 85 426 2009 4704 28404 48100 333251 561307
, , test = end59.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 12 46 199 653 2777 14461 34540 261477 252083
negascout_k 12 47 197 541 2509 9757 27143 89008 225199
negascout_t 12 46 199 644 2475 12611 27142 141370 173857
negascout_kt 12 47 197 539 2396 9869 24011 73875 177330
mtdf 32 120 403 1202 3382 12808 27145 102514 201141
実行時間
xtabs(time ~ name + depth + test, data=data)
, , test = end40.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 146 290 496 725 1261 1963 5291 8146 33362
negascout_k 162 294 495 725 1244 1993 4737 9275 29403
negascout_t 181 301 496 709 1262 1836 4309 6832 24828
negascout_kt 160 299 507 761 1249 1994 5221 8312 27056
mtdf 340 470 721 933 1637 2272 5530 8861 25979
, , test = end41.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 173 496 605 1667 1977 8624 10067 120363 95956
negascout_k 174 463 578 1429 1749 6304 7540 86696 59828
negascout_t 173 508 604 1633 1961 7853 7756 108516 60461
negascout_kt 178 473 591 1433 1909 6113 6932 88807 48840
mtdf 191 481 720 1378 2644 7353 14772 43787 102702
, , test = end42.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 167 424 645 1352 1731 6502 11983 44883 124855
negascout_k 172 374 597 1037 1587 2970 9065 14075 58752
negascout_t 170 423 623 1444 1761 5906 10800 40040 93727
negascout_kt 175 384 606 1066 1679 3370 8448 13988 51949
mtdf 266 613 777 1993 2076 8051 9112 49056 51157
, , test = end43.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 177 316 553 1149 1696 6324 11723 83606 186748
negascout_k 183 332 541 1080 1391 4197 6140 32211 93706
negascout_t 184 326 603 1165 1729 5298 10554 58282 131350
negascout_kt 190 313 544 1231 1365 4115 5665 34501 117310
mtdf 403 505 1090 1638 3056 7782 20668 60042 169510
, , test = end44.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 189 388 750 1338 2393 8659 10858 85144 80372
negascout_k 196 370 702 1166 1941 5401 9315 43392 57375
negascout_t 193 396 757 1315 2350 7564 9461 71131 60152
negascout_kt 191 366 729 1193 1988 5652 8475 44551 44293
mtdf 289 420 872 1169 2545 5127 7184 28775 36413
, , test = end45.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 204 457 634 1568 1974 7181 12158 87261 99123
negascout_k 208 444 658 1469 1980 6405 12799 71853 120692
negascout_t 213 472 648 1536 2033 7233 9805 73823 69151
negascout_kt 205 451 674 1441 2050 6774 13111 66399 96151
mtdf 259 562 647 1578 1938 6295 9632 58944 55833
, , test = end46.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 193 484 741 2420 3799 19658 29535 132102 231939
negascout_k 200 457 697 1710 2632 7765 15340 36120 89377
negascout_t 205 524 710 2343 3764 16092 25815 113883 172976
negascout_kt 219 456 705 1829 2637 8310 14298 35768 76634
mtdf 312 692 937 2090 2706 11933 21978 85995 227521
, , test = end47.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 189 277 708 704 3187 2443 25664 7825 138700
negascout_k 185 274 739 687 2312 2133 17950 7385 72540
negascout_t 195 270 758 667 3258 2127 21355 5521 78977
negascout_kt 189 280 740 647 2957 2105 16781 4966 56960
mtdf 251 308 682 985 1873 3420 11653 13291 30711
, , test = end48.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 188 425 682 1623 2927 9997 21834 80545 213768
negascout_k 194 418 698 1286 2544 5719 15166 39882 134581
negascout_t 193 422 676 1549 2749 8907 20961 67341 184257
negascout_kt 197 417 719 1388 2550 5398 16376 39458 120786
mtdf 406 569 1609 1696 8698 6329 70877 40292 793007
, , test = end49.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 176 486 627 1114 2289 4473 24078 41946 264479
negascout_k 187 460 650 1005 2166 3613 15768 39655 88779
negascout_t 179 501 638 1105 2223 3883 21157 34196 168660
negascout_kt 195 475 660 1010 2344 3393 18102 33940 83500
mtdf 242 382 797 921 2991 3477 18092 24142 160935
, , test = end50.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 204 442 826 2346 3672 36083 45100 905580 693858
negascout_k 211 455 753 1726 2984 11536 28311 140752 364351
negascout_t 207 460 784 2383 3266 30463 33674 0 443437
negascout_kt 213 464 761 1830 2905 10904 22865 121707 272435
mtdf 288 530 852 1985 3388 9266 22517 79284 202871
, , test = end51.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 211 399 822 1149 4117 5536 55090 56954 1165039
negascout_k 214 387 800 1084 3100 4517 24468 36420 211630
negascout_t 211 410 856 1231 4000 5573 47679 50778 0
negascout_kt 218 393 788 1102 3167 5198 20978 32365 200718
mtdf 276 365 779 1289 2863 4561 15748 29685 107617
, , test = end52.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 206 432 737 1185 1827 5641 13071 45879 195934
negascout_k 193 406 613 1167 1692 5179 10211 39142 122034
negascout_t 207 428 750 1216 1771 5144 11997 36647 144741
negascout_kt 196 421 611 1232 1729 4937 11026 33539 109840
mtdf 440 629 1703 1993 7584 9989 54343 71080 541046
, , test = end53.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 210 500 901 2407 4884 31277 44704 1201767 553896
negascout_k 210 505 837 1891 3298 7955 30283 69314 262176
negascout_t 211 528 878 2504 4764 28718 43612 0 443394
negascout_kt 214 504 828 2102 3293 8745 30791 67698 253523
mtdf 290 451 802 1479 2718 6192 20951 45044 174004
, , test = end54.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 191 401 621 1095 2191 5277 18367 45771 168647
negascout_k 190 417 607 1066 2069 4777 15367 41653 145154
negascout_t 186 423 623 1089 2153 4653 15757 36421 126648
negascout_kt 193 429 626 1016 2078 4743 13757 37260 112983
mtdf 201 548 633 1131 2049 4325 10279 35448 81802
, , test = end55.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 228 451 867 1625 5865 11516 47866 191687 776131
negascout_k 229 452 879 1466 3990 7497 39249 79331 440569
negascout_t 232 468 887 1541 5690 9876 42431 138889 635360
negascout_kt 236 464 881 1455 4697 7738 38621 71558 397801
mtdf 263 423 880 1535 3578 8308 30333 147236 265348
, , test = end56.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 201 366 849 1204 3260 8014 31708 69252 806823
negascout_k 206 354 780 1057 2095 5503 13382 45388 247042
negascout_t 207 373 862 1199 2960 7195 27368 53603 606342
negascout_kt 208 354 804 1076 1963 5348 11614 37573 277568
mtdf 335 502 1111 1499 4333 7058 40382 52695 465928
, , test = end57.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 177 421 626 1772 1743 12042 7732 145348 74015
negascout_k 180 369 646 1480 1775 4947 7565 46505 73514
negascout_t 190 436 636 1795 1883 10308 7669 133608 61528
negascout_kt 185 373 655 1574 1906 5102 8252 49164 69514
mtdf 296 587 734 1641 2222 7370 11412 56582 90320
, , test = end58.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 237 651 855 3380 4692 32901 44719 449075 462755
negascout_k 244 584 809 1929 3465 13789 26732 171201 306630
negascout_t 238 693 847 3107 4734 29215 38682 396939 367758
negascout_kt 251 557 830 1918 3774 13085 29430 178562 287312
mtdf 323 491 940 1865 3498 12176 23809 124279 249729
, , test = end59.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 176 391 601 1270 2129 9195 15964 137736 108460
negascout_k 179 401 620 1092 2034 6278 12079 45030 88573
negascout_t 179 404 623 1228 2003 7652 12094 71868 70125
negascout_kt 184 413 623 1116 2004 6419 10978 38308 70561
mtdf 273 527 751 1520 2322 6888 11698 44938 76771
概ね高速であるが、ときどき非常に遅い時がある。
[1] Plaat and University of Alberta. Dept. of Computing Science. A new paradigm for minimax search. (1994)
2011/07/07
NegaScout with Killer heuristic, History heuristic and Transposition table
NegaScoutはそのアルゴリズムからβ値を変えて同じノードに2度訪れることがある。そこで、killer heuristicあるいはhistory heuristicや、transposition tableが効果的であると予想される。
実際にkiller heuristicとtransposition tableのheuristicをNegaScoutに組み合わせて実験した結果が以下である。（history heuristicはreversiにおいてkiller heuristicほどの効果が出ていなかったため、今回は実験から外した）
末端ノード数
中間ノード数
実行時間
若干、入れ替わりもあるが多くの盤面でNegaScout + killer heuristic + transposition tableが最も効果的であることが分かる。
実際にkiller heuristicとtransposition tableのheuristicをNegaScoutに組み合わせて実験した結果が以下である。（history heuristicはreversiにおいてkiller heuristicほどの効果が出ていなかったため、今回は実験から外した）
末端ノード数
xtabs(node ~ name + depth + test, data=data) , , test = end40.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 0 117 139 866 1278 7055 11826 56216 102936 killer 13 117 142 919 1259 8141 11188 71872 90244 history 13 117 138 934 1445 9054 14257 68699 140375 transposition 13 117 139 866 1205 6537 9804 46648 76452 transposition_killer 13 117 142 919 1220 7559 10179 62101 73378 transposition_history 13 117 138 934 1329 8091 11475 53604 109842 negascout 13 118 150 869 1426 6877 11739 50161 0 negascout_k 13 118 141 902 1324 7883 10528 65640 88274 negascout_t 13 118 144 825 1217 5736 8835 36378 72029 negascout_kt 13 118 141 875 1138 7226 10083 53044 73327 , , test = end41.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 30 289 525 4332 6865 55580 78076 795144 637477 killer 26 225 351 2338 4463 33890 39953 520238 367350 history 30 220 349 2835 6983 37146 98640 919163 794438 transposition 30 289 466 4044 5159 46822 51639 591896 344524 transposition_killer 26 225 333 2245 3338 30104 27403 424445 234508 transposition_history 30 220 319 2724 5744 37691 67072 628915 468730 negascout 30 277 498 3942 5522 38672 51316 637813 507317 negascout_k 26 205 328 2391 3854 21961 29935 379585 282423 negascout_t 30 255 423 3607 4750 34045 33459 504176 278609 negascout_kt 26 187 325 2184 3832 19717 25478 334212 205353 , , test = end42.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 30 223 338 3747 4063 47325 48221 538729 579236 killer 30 116 308 1274 2894 10944 32071 101725 262883 history 30 105 371 1151 3980 9421 41376 209558 454887 transposition 30 223 338 3664 3818 43552 39808 456392 426999 transposition_killer 30 116 308 1254 2695 10544 26828 93565 197734 transposition_history 30 105 367 1144 3669 8977 32338 157518 277244 negascout 30 177 375 2436 3176 25612 42839 248198 549411 negascout_k 30 114 325 1181 2374 8101 27187 64654 213624 negascout_t 30 169 351 2638 3081 22922 36559 204722 367558 negascout_kt 30 114 310 1176 2352 8224 22283 57193 170565 , , test = end43.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 49 77 673 1388 10677 23115 115886 319520 1253254 killer 48 66 328 1058 3733 12721 35870 124176 903364 history 49 64 333 1005 3720 6941 68929 136484 2786356 transposition 49 77 667 1245 9939 18804 102284 205934 956383 transposition_killer 48 66 327 968 3327 10567 29593 88481 661575 transposition_history 49 64 332 916 3511 6336 63268 83974 2138847 negascout 49 64 455 1241 5358 13714 74902 246768 1342957 negascout_k 48 59 300 936 3259 8122 34030 82466 697031 negascout_t 49 64 452 1121 4794 11178 66526 159512 873095 negascout_kt 48 59 300 1122 2793 6589 28902 77931 833684 , , test = end44.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 37 208 575 4023 6969 59839 53319 834028 541004 killer 31 160 467 2017 4865 23442 35409 238600 357664 history 37 133 546 1914 7391 22165 76166 616349 1593877 transposition 37 208 561 3681 6347 46897 42988 550738 375304 transposition_killer 31 160 455 1865 4397 19168 27886 176391 233292 transposition_history 37 133 531 1749 6947 18253 59695 402070 976074 negascout 37 163 718 2376 6146 31217 41518 382253 369021 negascout_k 31 154 553 1903 4252 19442 32793 193691 250324 negascout_t 37 145 661 1978 5712 26938 35992 307232 271322 negascout_kt 31 134 526 1690 3977 19028 28238 198876 188543 , , test = end45.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 34 370 329 5777 2723 61868 26343 817688 226751 killer 24 297 255 4019 2491 47940 25762 660510 266069 history 34 316 346 6778 2902 75623 34891 757864 520050 transposition 34 370 311 5469 2120 52819 16278 626279 111302 transposition_killer 24 297 241 3900 2035 41268 18864 479841 153268 transposition_history 34 316 321 6509 2179 69593 18111 568700 268464 negascout 34 341 307 5106 2720 48033 26628 663943 243477 negascout_k 24 263 246 4243 2446 42004 26254 542838 293315 negascout_t 34 350 293 4548 2435 44768 18250 507703 154510 negascout_kt 24 266 236 3649 2189 39254 24296 414675 204045 , , test = end46.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 25 335 594 10135 11688 124574 152214 1237488 1574325 killer 24 254 447 4512 6313 36650 61276 260928 515348 history 25 318 406 3577 6068 37323 61844 432780 567664 transposition 25 335 590 9514 10377 106820 128322 975838 1134359 transposition_killer 24 254 444 4345 5122 32156 50284 191644 360248 transposition_history 25 318 403 3334 5533 28162 50656 327399 371485 negascout 25 374 485 9812 9666 120794 121581 867828 1146500 negascout_k 24 239 412 4179 5676 34681 53114 199289 393103 negascout_t 25 346 440 8225 9262 92633 105958 674553 820007 negascout_kt 24 221 399 4038 5138 34552 50520 157812 320921 , , test = end47.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 47 77 788 843 14354 7810 191791 43789 1106182 killer 36 76 640 741 8238 6805 100279 53765 466128 history 47 77 596 767 16889 15476 349324 168819 830096 transposition 47 77 719 607 12686 5073 147481 24796 700526 transposition_killer 36 76 622 502 7778 3970 84706 25859 329388 transposition_history 47 77 587 683 14725 6916 233077 40078 447648 negascout 47 77 742 709 12574 6465 147226 35518 647303 negascout_k 36 76 661 635 7067 6277 95607 39140 374661 negascout_t 47 77 735 507 12231 4950 117537 20431 415691 negascout_kt 36 76 626 454 10148 4509 86232 17140 273479 , , test = end48.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 29 313 470 6681 9337 89444 145149 1129818 1887604 killer 28 247 366 3780 6105 33229 64567 458057 844925 history 29 254 410 3589 6299 46210 107392 549059 1419914 transposition 29 313 457 6344 8672 76201 123290 839472 1453216 transposition_killer 28 247 354 3718 5599 31171 56995 397104 687915 transposition_history 29 254 397 3449 6113 40535 90263 360566 970608 negascout 29 237 487 4048 8711 47471 101834 447611 1157189 negascout_k 28 215 426 2508 5893 27912 54901 234412 535168 negascout_t 29 225 435 3325 7348 38797 92198 342054 921632 negascout_kt 28 215 378 2523 5536 23540 57060 212023 430229 , , test = end49.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 34 273 494 2408 6707 20749 125380 310137 1682987 killer 34 172 462 1376 6608 13216 81486 255557 524162 history 34 228 423 1474 9535 19105 289988 393921 3777028 transposition 34 273 485 2182 5633 16981 90868 239325 988432 transposition_killer 34 172 453 1285 5928 11376 72695 200781 423956 transposition_history 34 228 413 1344 8294 15510 233306 328403 2841075 negascout 34 278 539 1791 6544 15755 119662 171897 1286707 negascout_k 34 178 556 1283 7316 10730 84280 187484 469384 negascout_t 34 253 526 1578 5643 12621 96787 130468 741520 negascout_kt 34 170 523 1182 7096 9134 93741 147926 399412 , , test = end50.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 33 452 626 15963 10816 534240 202532 25385511 3547451 killer 33 435 539 7796 8119 83069 113527 1832744 1494987 history 33 451 593 8706 6781 92923 143691 2292800 3743392 transposition 33 452 609 14679 9222 432283 148792 0 2010526 transposition_killer 33 435 515 7315 6826 71301 81404 1311352 920816 transposition_history 33 451 566 8326 5375 79616 108243 1532784 1562466 negascout 33 323 675 12049 10445 311521 165628 8331136 2730443 negascout_k 33 307 540 5224 6775 77991 95550 1070570 1200398 negascout_t 33 323 604 10528 8292 248164 121633 0 1549757 negascout_kt 33 307 511 5195 5647 71885 70762 877446 783511 , , test = end51.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 59 183 1160 2032 31843 24937 479486 347731 11632682 killer 59 161 774 1868 11697 19841 98216 262291 1104365 history 59 169 736 1870 19981 31994 360828 604427 4472669 transposition 59 183 1149 1959 29411 22011 405309 266596 0 transposition_killer 59 161 763 1780 11206 16255 86046 164997 892147 transposition_history 59 169 724 1764 20090 25715 285860 409513 3386776 negascout 59 202 1030 1938 19853 24097 375925 327750 8490980 negascout_k 59 155 712 1635 9593 20397 82927 222009 969788 negascout_t 59 205 1005 2013 18482 20749 303961 247261 0 negascout_kt 59 145 661 1583 9301 19182 81196 146625 912394 , , test = end52.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 63 204 992 1946 6498 22494 94032 247170 1771168 killer 37 196 393 1637 3956 18064 49810 179793 852766 history 63 161 544 1866 8367 22680 98793 295964 2455819 transposition 63 204 972 1850 5734 18459 74058 178937 1250059 transposition_killer 37 196 391 1572 3598 14539 43911 127181 674720 transposition_history 63 161 538 1591 8070 17767 79829 180651 1630442 negascout 63 180 902 1709 5654 19288 81468 195141 1277140 negascout_k 37 162 353 1527 3548 16149 44295 148178 676770 negascout_t 63 173 860 1687 4917 15049 67976 134405 922381 negascout_kt 37 163 327 1608 3252 13121 47402 111351 550509 , , test = end53.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 43 350 1214 11389 29471 576664 332677 41483269 4314728 killer 35 279 735 5006 13370 40594 178650 445833 1754219 history 43 355 1110 5428 13158 124141 372892 1367582 5578264 transposition 43 350 1155 10658 25134 433393 269960 0 3066676 transposition_killer 35 279 700 4723 11054 34225 146314 318687 0 transposition_history 43 355 1076 5134 11771 99584 292184 974032 3880547 negascout 43 349 1278 10972 25288 247619 274617 10298036 3186665 negascout_k 35 279 855 4318 11674 31320 158313 327077 1444664 negascout_t 43 320 1146 10194 22327 204413 250846 0 2293979 negascout_kt 35 271 782 4716 10903 29281 164489 260376 1312628 , , test = end54.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 23 239 586 2323 14222 22906 211911 292473 2569049 killer 24 246 315 2388 4067 18566 45106 291315 470461 history 23 220 373 1817 4789 17893 72521 359292 715648 transposition 23 239 577 2249 12567 20147 162326 227775 1645949 transposition_killer 24 246 314 2317 3530 15654 36506 223254 325445 transposition_history 23 220 371 1746 4416 15349 66466 234062 551696 negascout 23 216 371 2194 5870 26600 92194 287651 927408 negascout_k 24 189 262 1950 2957 22626 34695 273318 345191 negascout_t 23 216 371 2066 5222 20270 70386 218128 615772 negascout_kt 24 181 261 1593 2659 18939 27884 212148 244200 , , test = end55.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 49 322 841 5657 20688 82789 223240 1981849 3913589 killer 46 296 766 4125 13649 46313 163901 722587 2040108 history 49 265 943 5640 30422 69445 397639 1603105 6168796 transposition 49 322 819 5260 19080 63943 191773 1264255 3028256 transposition_killer 46 296 751 3776 12423 35688 137594 510299 1341651 transposition_history 49 265 939 5320 27967 57095 365209 1070158 4059380 negascout 49 295 857 4616 20627 59091 189197 1009661 3447413 negascout_k 46 281 784 3663 12208 42926 157864 535946 1913433 negascout_t 49 290 782 3765 19311 49978 174816 684694 2790214 negascout_kt 46 281 743 3258 13625 42493 152997 394130 1709642 , , test = end56.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 56 148 1532 2013 26438 37070 373227 380459 7594219 killer 54 121 850 1636 6337 21764 72508 233316 2472901 history 56 119 894 1550 7353 39741 141838 388380 5768474 transposition 56 148 1481 1863 22952 30839 296251 272832 5006864 transposition_killer 54 121 841 1558 5298 18056 53975 167074 1628893 transposition_history 56 119 891 1418 6018 32654 113206 310646 4946440 negascout 56 120 1326 1596 14771 21502 222253 230785 6013316 negascout_k 54 111 825 1349 5028 14212 63928 147220 1852309 negascout_t 56 120 1226 1463 12164 18036 180860 163746 4371241 negascout_kt 54 111 768 1262 3992 11816 48671 105271 1901167 , , test = end57.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 38 289 458 5651 4485 107143 44017 1887772 575659 killer 37 180 423 3213 4357 26746 40364 298000 527039 history 38 235 576 3640 5982 46710 64018 938145 2003176 transposition 38 289 457 5310 4152 94560 37778 1516325 421555 transposition_killer 37 180 416 3134 4193 23936 36344 255174 390780 transposition_history 38 235 554 3579 5387 40223 54459 711127 1758121 negascout 38 237 507 4475 4477 61001 30822 849439 392082 negascout_k 37 161 480 2561 4497 16136 32622 163275 394994 negascout_t 38 237 496 4291 4445 52345 31573 716148 306181 negascout_kt 37 161 451 2463 4398 15841 36980 157818 383875 , , test = end58.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 55 828 904 15508 15619 238957 206252 3275672 2451690 killer 55 428 848 5153 12740 69276 167306 908990 1931340 history 55 360 871 5269 12378 96896 172737 2948327 6144882 transposition 55 828 901 14500 14000 202472 160207 2516306 1623764 transposition_killer 55 428 843 4941 10983 62908 118411 682704 1193542 transposition_history 55 360 862 4967 10597 81042 118137 2254222 3507519 negascout 55 547 863 14095 16348 194209 211595 2727903 2286834 negascout_k 55 407 830 4674 13645 56220 170146 811251 1984559 negascout_t 55 498 847 11013 16801 159529 187444 2205883 1854687 negascout_kt 55 323 821 4154 15337 53196 183057 755832 1836974 , , test = end59.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha 18 240 210 3747 2592 63628 31206 690918 271286 killer 18 230 203 2750 2370 46393 26761 386843 229761 history 18 246 166 2618 2264 34901 27709 373796 350067 transposition 18 240 205 3646 2248 59270 24330 552747 180116 transposition_killer 18 230 198 2704 2127 42624 22069 317663 162933 transposition_history 18 246 164 2575 2062 30880 22591 292021 270288 negascout 18 214 209 2844 2643 58239 30403 1008983 216835 negascout_k 18 197 205 2070 2262 36733 23426 345174 193849 negascout_t 18 217 204 2730 2126 46808 21839 489119 134627 negascout_kt 18 208 199 1969 2081 33587 19116 256418 137030
中間ノード数
xtabs(inode ~ name + depth + test, data=data)
, , test = end40.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 0 23 132 223 1302 2082 11920 19422 101474
killer 11 23 130 224 1277 2145 11654 21362 101178
history 11 23 126 232 1459 2393 14724 22043 149215
transposition 11 23 132 223 1302 2014 11056 17262 83852
transposition_killer 11 23 130 224 1277 2076 11283 19434 89130
transposition_history 11 23 126 232 1430 2282 13122 19003 129201
negascout 11 25 146 228 1486 2075 12348 17988 0
negascout_k 11 25 136 229 1365 2139 11491 19991 99489
negascout_t 11 25 144 228 1345 1922 9857 14867 78863
negascout_kt 11 25 136 229 1257 2011 11958 17234 87156
, , test = end41.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 11 71 190 1358 2769 20464 33119 330680 308137
killer 11 65 173 955 2255 15048 22970 258629 208052
history 11 65 154 973 2849 14941 41311 418687 389117
transposition 11 71 190 1342 2338 18670 24754 274772 193663
transposition_killer 11 65 173 950 1988 14241 17837 226416 146928
transposition_history 11 65 154 956 2592 16133 30591 323616 250751
negascout 11 99 187 1437 2399 15724 23784 276227 263413
negascout_k 11 81 171 1109 1951 11428 16272 209894 169736
negascout_t 11 99 187 1464 2427 14722 17715 260280 178906
negascout_kt 11 80 171 1067 2238 10939 14737 215444 136676
, , test = end42.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 10 49 189 979 2491 13889 31707 177559 386552
killer 10 36 178 507 2170 4439 26028 41839 216051
history 10 33 197 433 2504 3419 27266 72808 292881
transposition 10 49 189 979 2446 13410 28756 161727 318723
transposition_killer 10 36 178 507 2151 4327 24560 39885 179452
transposition_history 10 33 197 433 2439 3369 23601 56543 213037
negascout 10 59 221 933 2237 9461 30490 93282 386576
negascout_k 10 46 193 579 1931 3864 23020 29194 181507
negascout_t 10 59 222 1011 2311 9476 27946 84480 286373
negascout_kt 10 46 197 590 2012 4532 20312 27993 158697
, , test = end43.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 7 36 141 729 2416 14067 33387 210205 432483
killer 7 31 103 679 1186 8853 12428 99661 294090
history 7 31 96 547 1151 4389 22344 79647 983657
transposition 7 36 141 712 2306 12718 30813 157759 353273
transposition_killer 7 31 103 674 1118 8033 11066 80444 235159
transposition_history 7 31 96 546 1124 4177 21464 61819 830486
negascout 7 36 137 817 1623 9972 23253 175405 490033
negascout_k 7 31 110 662 1038 6449 10930 71533 227741
negascout_t 7 36 137 847 1515 9055 21982 133849 335105
negascout_kt 7 31 110 815 946 5840 9931 78039 271967
, , test = end44.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 11 50 252 1181 3143 22079 25069 357369 260561
killer 11 43 206 684 2595 9517 20997 108323 193208
history 11 41 242 640 3245 8155 30682 213433 655351
transposition 11 50 252 1145 3017 19176 21720 268827 195301
transposition_killer 11 43 206 668 2429 8714 17319 87938 130218
transposition_history 11 41 242 630 3287 7452 25639 156206 446432
negascout 11 56 289 1066 2970 16492 22113 202603 199765
negascout_k 11 47 238 682 2221 9250 20116 100449 145518
negascout_t 11 52 289 1005 2982 14577 19810 172924 150666
negascout_kt 11 43 255 736 2183 9696 17478 104399 109212
, , test = end45.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 15 56 251 1126 2685 14361 27310 231821 251247
killer 15 50 250 823 2683 11012 29122 192413 311528
history 15 51 263 1324 2927 17418 32372 219100 476012
transposition 15 56 251 1108 2581 12989 22014 193510 153634
transposition_killer 15 50 250 811 2578 10220 25024 155175 214397
transposition_history 15 51 263 1307 2461 16894 20606 181770 277657
negascout 15 69 244 1148 2709 11993 28158 196678 275525
negascout_k 15 63 242 998 2675 10515 30380 159167 345525
negascout_t 15 69 244 1099 2825 12641 23895 169888 201339
negascout_kt 15 63 242 950 2745 11038 31767 149743 277033
, , test = end46.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 13 64 287 2781 5602 42850 69816 480548 668693
killer 13 64 253 1570 3511 15919 33491 119357 267745
history 13 63 238 1189 3243 15427 33061 188180 259193
transposition 13 64 287 2693 5307 39092 63734 412848 532736
transposition_killer 13 64 253 1556 3368 15200 30485 102300 214233
transposition_history 13 63 238 1172 3127 13558 30607 153539 190467
negascout 13 85 283 3247 5509 45549 60467 352518 506864
negascout_k 13 80 238 1790 3208 16933 30125 93203 198553
negascout_t 13 85 259 3102 5496 38485 53279 307404 383787
negascout_kt 13 70 237 1962 3074 17963 28074 95152 170354
, , test = end47.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 9 23 220 241 4855 3056 66266 18290 454535
killer 9 23 217 219 2781 2550 38654 20258 220209
history 9 23 171 234 4742 4701 95903 59810 311353
transposition 9 23 220 212 4504 2274 55227 12105 320144
transposition_killer 9 23 217 191 2682 1897 34136 12846 157673
transposition_history 9 23 171 220 4395 2772 71804 17183 192655
negascout 9 23 233 242 4412 2907 50354 16539 265864
negascout_k 9 23 237 218 2495 2557 35508 14928 170292
negascout_t 9 23 253 213 4536 2650 44470 11196 189768
negascout_kt 9 23 236 196 3402 2486 32863 9442 131268
, , test = end48.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 14 51 256 1412 5112 24048 84987 340659 1073904
killer 14 46 244 910 4105 9107 47252 131084 633594
history 14 46 223 758 3879 11629 78476 149146 943794
transposition 14 51 256 1388 5037 22269 78095 280424 908420
transposition_killer 14 46 244 903 4026 8801 45263 119865 563727
transposition_history 14 46 223 762 3947 10581 70156 111085 718975
negascout 14 54 269 1162 4806 15760 57034 161902 590192
negascout_k 14 48 268 748 3740 8510 40008 78939 392969
negascout_t 14 53 246 1094 4298 14212 54275 136782 508642
negascout_kt 14 48 245 807 3636 7758 41386 76328 347276
, , test = end49.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 9 67 150 752 2270 7504 48272 143403 765326
killer 9 59 144 477 1901 5223 30264 102848 217404
history 9 60 135 503 2924 7809 118261 119874 1848428
transposition 9 67 150 740 2040 6896 39485 120556 505251
transposition_killer 9 59 144 476 1765 4570 28182 83716 186957
transposition_history 9 60 135 500 2646 6731 101971 110958 1535764
negascout 9 87 175 665 2430 6695 50796 96831 633869
negascout_k 9 76 170 487 2145 5294 30454 89221 199667
negascout_t 9 87 174 656 2332 6067 45934 82621 411842
negascout_kt 9 74 173 486 2280 4719 35268 76532 185430
, , test = end50.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 16 58 357 2672 6816 93930 136456 4671517 2599972
killer 16 59 331 1614 6011 19287 93077 426838 1378214
history 16 58 344 1401 4578 18560 97150 487473 2689349
transposition 16 58 357 2596 6376 82047 113643 0 1729700
transposition_killer 16 59 331 1580 5750 16970 78209 329649 1004435
transposition_history 16 58 344 1372 4142 16342 86405 374834 1379372
negascout 16 58 381 2252 6548 61806 113884 1698516 2008267
negascout_k 16 59 318 1260 4729 18750 74147 278057 1047587
negascout_t 16 58 367 2221 5535 53573 90114 0 1304914
negascout_kt 16 59 319 1399 4528 17254 60574 237079 790573
, , test = end51.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 11 41 305 607 8116 8323 127095 123004 3162709
killer 11 40 261 585 4977 6704 45981 84988 531179
history 11 40 237 539 5938 8594 108244 161915 1554607
transposition 11 41 305 604 7878 7887 114842 103380 0
transposition_killer 11 40 261 577 4947 6289 41670 63936 447004
transposition_history 11 40 237 540 6099 7530 92977 119700 1286432
negascout 11 52 300 652 5511 8643 101866 120491 2358758
negascout_k 11 51 272 577 3892 6765 42186 76838 473081
negascout_t 11 52 298 751 5326 9104 90639 110583 0
negascout_kt 11 51 262 579 3906 8330 40806 69717 430606
, , test = end52.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 11 50 273 686 2085 8728 30754 101885 621643
killer 11 50 185 582 2069 6713 24692 72808 439507
history 11 41 191 575 2701 8574 42812 119296 1197099
transposition 11 50 273 683 1990 7929 26376 83348 481590
transposition_killer 11 50 185 579 1940 6214 22853 60167 383624
transposition_history 11 41 191 552 2649 7669 37026 90012 861339
negascout 11 59 253 683 1842 8098 26735 85174 439938
negascout_k 11 50 168 640 1745 7181 21864 71238 303779
negascout_t 11 59 253 709 1704 7328 24112 69626 346116
negascout_kt 11 50 168 670 1638 6773 22229 62285 266658
, , test = end53.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 12 73 358 2355 8971 114961 116264 8171951 1741812
killer 12 69 277 1676 4757 16050 69987 188570 737723
history 12 74 336 1520 4077 33617 120077 426351 1823453
transposition 12 73 358 2299 8316 96981 98945 0 1336562
transposition_killer 12 69 277 1664 4282 14436 59054 148803 0
transposition_history 12 74 336 1503 3764 30845 100164 339884 1392543
negascout 12 89 346 2509 7090 55204 88090 2234507 1190850
negascout_k 12 86 308 1784 4077 13542 59671 148293 549581
negascout_t 12 88 319 2624 6861 52306 86502 0 961771
negascout_kt 12 84 283 2052 4077 15441 58487 147603 537028
, , test = end54.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 11 44 251 509 5509 6265 84666 81824 1087544
killer 11 47 212 515 3260 5208 39655 79360 459352
history 11 43 201 403 3167 5601 55730 98584 649170
transposition 11 44 251 502 5345 5925 73592 70011 799366
transposition_killer 11 47 212 508 3038 4918 34549 68033 347819
transposition_history 11 43 201 396 3046 5189 56432 75542 562014
negascout 11 50 175 531 2409 7285 37752 83641 392862
negascout_k 11 52 179 490 2438 6557 31799 79308 340974
negascout_t 11 50 175 514 2314 6773 33036 73678 301036
negascout_kt 11 51 179 427 2273 6603 28324 71890 267328
, , test = end55.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 15 55 350 1157 8782 22308 105781 679500 1821915
killer 15 51 351 883 6394 11781 89365 212535 1060256
history 15 48 364 1105 11729 17002 152102 395372 2313536
transposition 15 55 350 1123 8537 18749 95701 481705 1512281
transposition_killer 15 51 351 860 6183 10078 81359 169999 764746
transposition_history 15 48 364 1086 11182 15560 144906 303851 1702475
negascout 15 65 404 1248 9188 19798 92140 392794 1662603
negascout_k 15 61 358 953 5513 12038 80770 157799 951606
negascout_t 15 65 408 1148 9117 17778 87351 304024 1364431
negascout_kt 15 61 360 905 6644 12260 78871 147038 837889
, , test = end56.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 10 45 291 818 5578 18199 87632 204781 1867631
killer 10 37 232 601 2333 11424 30004 137397 723001
history 10 37 220 540 2467 15428 46501 188916 1547089
transposition 10 45 291 798 5139 16721 76070 170540 1375443
transposition_killer 10 37 232 594 2109 10852 25703 113358 546719
transposition_history 10 37 220 535 2267 14395 40969 170735 1531471
negascout 10 45 311 757 3912 12865 57796 140488 1530114
negascout_k 10 37 252 541 2067 8742 25142 94894 492491
negascout_t 10 45 317 742 3509 12036 51373 113677 1235365
negascout_kt 10 37 247 534 1841 8398 21623 80730 545025
, , test = end57.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 9 52 167 1505 1911 28647 21516 508303 278772
killer 9 38 157 1099 1810 11010 20162 133774 228099
history 9 43 180 1034 2252 15430 24730 299690 819951
transposition 9 52 167 1489 1839 26910 19685 441559 225046
transposition_killer 9 38 157 1091 1759 10486 18706 119673 180604
transposition_history 9 43 180 1034 2100 14203 22601 255452 777106
negascout 9 52 173 1432 1739 19135 13780 285120 168055
negascout_k 9 38 175 1049 1675 7488 14165 98433 164247
negascout_t 9 52 173 1530 1940 17446 14387 266146 140052
negascout_kt 9 38 172 1163 1844 7637 15122 104688 154033
, , test = end58.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 14 143 290 3752 5514 67974 75689 1003094 917040
killer 14 92 260 1546 3845 24402 48328 339857 558328
history 14 72 291 1302 3589 25256 46011 855329 2108334
transposition 14 143 290 3694 5233 62057 63898 824784 683281
transposition_killer 14 92 260 1540 3691 22275 39526 269293 403325
transposition_history 14 72 291 1288 3325 22302 37021 707513 1441550
negascout 14 172 303 4253 6287 61713 81874 882182 893434
negascout_k 14 111 262 1723 3872 25178 44528 357158 573485
negascout_t 14 172 303 3644 6467 55475 71662 784289 733810
negascout_kt 14 98 262 1657 4426 23251 49307 364851 532404
, , test = end59.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 12 40 192 735 2643 14452 34055 168657 293835
killer 12 41 190 619 2562 11258 30369 91581 261650
history 12 40 150 632 2374 9362 27668 98848 280713
transposition 12 40 192 730 2529 13938 29340 144037 224385
transposition_killer 12 41 190 617 2485 10738 27459 80502 208024
transposition_history 12 40 150 630 2300 8735 25211 83533 255873
negascout 12 46 199 653 2777 14461 34540 261477 252083
negascout_k 12 47 197 541 2509 9757 27143 89008 225199
negascout_t 12 46 199 644 2475 12611 27142 141370 173857
negascout_kt 12 47 197 539 2396 9869 24011 73875 177330
実行時間
xtabs(time ~ name + depth + test, data=data)
, , test = end40.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 0 279 472 813 1201 1944 4887 9171 31487
killer 149 296 485 784 1236 1990 4838 9956 30126
history 154 268 467 736 1267 2098 5797 9748 45530
transposition 155 282 471 724 1227 1889 4994 7864 26056
transposition_killer 153 286 491 769 1308 2069 4930 9330 27286
transposition_history 152 285 480 791 1387 2221 5498 8998 44440
negascout 146 290 496 725 1261 1963 5291 8146 0
negascout_k 162 294 495 725 1244 1993 4737 9275 29403
negascout_t 181 301 496 709 1262 1836 4309 6832 24828
negascout_kt 160 299 507 761 1249 1994 5221 8312 27056
, , test = end41.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 173 449 610 1692 2089 10683 13632 143450 107279
killer 173 442 586 1356 1871 8100 9828 109400 74397
history 160 422 530 1329 2160 7870 16957 171294 131549
transposition 176 463 622 1665 1951 9747 10348 116878 66313
transposition_killer 172 483 596 1435 1740 7763 7854 94940 52573
transposition_history 185 450 581 1485 2220 8896 13456 136463 110766
negascout 173 496 605 1667 1977 8624 10067 120363 95956
negascout_k 174 463 578 1429 1749 6304 7540 86696 59828
negascout_t 173 508 604 1633 1961 7853 7756 108516 60461
negascout_kt 178 473 591 1433 1909 6113 6932 88807 48840
, , test = end42.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 166 405 576 1494 1835 8446 12419 86336 128649
killer 171 345 570 1071 1672 3344 10153 20727 70409
history 159 317 586 919 1839 2827 10575 34222 94164
transposition 173 409 588 1533 1890 8265 11042 78897 103576
transposition_killer 176 354 594 1052 1822 3323 9525 19521 58445
transposition_history 167 331 627 977 2041 2983 9858 28640 80609
negascout 167 424 645 1352 1731 6502 11983 44883 124855
negascout_k 172 374 597 1037 1587 2970 9065 14075 58752
negascout_t 170 423 623 1444 1761 5906 10800 40040 93727
negascout_kt 175 384 606 1066 1679 3370 8448 13988 51949
, , test = end43.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 173 316 612 1247 2181 7611 15773 97968 169137
killer 185 309 512 1116 1489 5327 6604 44159 121802
history 158 294 478 965 1399 3117 10654 37228 364094
transposition 183 328 610 1136 2198 7097 14636 68377 137943
transposition_killer 184 316 520 1107 1470 4954 6029 35510 98219
transposition_history 185 308 516 1055 1514 3174 10754 28169 359052
negascout 177 316 553 1149 1696 6324 11723 83606 186748
negascout_k 183 332 541 1080 1391 4197 6140 32211 93706
negascout_t 184 326 603 1165 1729 5298 10554 58282 131350
negascout_kt 190 313 544 1231 1365 4115 5665 34501 117310
, , test = end44.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 190 379 702 1529 2389 11320 11888 153310 105496
killer 189 359 660 1218 2107 5672 9905 47811 78371
history 176 336 673 1127 2514 4946 14874 94093 271368
transposition 195 389 711 1533 2426 9897 10356 111516 77421
transposition_killer 194 366 666 1172 2123 5222 8209 37994 53031
transposition_history 194 351 719 1153 2712 4780 12932 71112 211404
negascout 189 388 750 1338 2393 8659 10858 85144 80372
negascout_k 196 370 702 1166 1941 5401 9315 43392 57375
negascout_t 193 396 757 1315 2350 7564 9461 71131 60152
negascout_kt 191 366 729 1193 1988 5652 8475 44551 44293
, , test = end45.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 204 443 654 1749 1950 8403 12390 103386 98525
killer 200 424 662 1489 1971 6783 12650 88328 111953
history 191 395 668 1732 2061 9696 13983 96618 173117
transposition 209 441 657 1628 1859 7653 8951 87273 52642
transposition_killer 202 425 679 1407 1939 6455 10638 70843 74892
transposition_history 208 430 697 1850 2026 10166 9000 85703 107569
negascout 204 457 634 1568 1974 7181 12158 87261 99123
negascout_k 208 444 658 1469 1980 6405 12799 71853 120692
negascout_t 213 472 648 1536 2033 7233 9805 73823 69151
negascout_kt 205 451 674 1441 2050 6774 13111 66399 96151
, , test = end46.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 191 444 744 2468 3732 18278 33908 178646 322917
killer 197 432 712 1646 2809 7517 17048 47842 122559
history 188 422 653 1429 2597 7357 16906 70515 116225
transposition 199 470 755 2309 3714 16834 30863 157784 241775
transposition_killer 200 450 732 1697 2698 7241 15454 39206 94981
transposition_history 197 452 707 1573 2714 6771 16128 59818 96247
negascout 193 484 741 2420 3799 19658 29535 132102 231939
negascout_k 200 457 697 1710 2632 7765 15340 36120 89377
negascout_t 205 524 710 2343 3764 16092 25815 113883 172976
negascout_kt 219 456 705 1829 2637 8310 14298 35768 76634
, , test = end47.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 183 268 711 755 3420 2343 32273 9206 207272
killer 191 269 707 706 2460 2154 19588 10158 95632
history 180 254 609 705 3552 3283 48855 26540 136188
transposition 192 265 704 699 3293 1904 26653 6029 134247
transposition_killer 191 276 714 642 2497 1782 17311 6317 68326
transposition_history 206 272 655 713 3627 2361 37764 8389 94987
negascout 189 277 708 704 3187 2443 25664 7825 138700
negascout_k 185 274 739 687 2312 2133 17950 7385 72540
negascout_t 195 270 758 667 3258 2127 21355 5521 78977
negascout_kt 189 280 740 647 2957 2105 16781 4966 56960
, , test = end48.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 195 424 669 1988 2964 14853 32306 186216 391341
killer 195 409 673 1479 2640 6153 17910 71020 216746
history 180 383 615 1313 2473 7780 27533 79128 327419
transposition 191 439 679 1951 3026 13533 28723 144681 315593
transposition_killer 193 413 668 1538 2691 6110 17209 64097 194951
transposition_history 196 423 659 1463 2730 7617 25916 60381 282573
negascout 188 425 682 1623 2927 9997 21834 80545 213768
negascout_k 194 418 698 1286 2544 5719 15166 39882 134581
negascout_t 193 422 676 1549 2749 8907 20961 67341 184257
negascout_kt 197 417 719 1388 2550 5398 16376 39458 120786
, , test = end49.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 178 442 595 1307 2204 4635 23294 62160 319660
killer 184 425 596 1009 2095 3835 15660 49073 96031
history 169 410 563 991 2467 4882 52347 55957 738070
transposition 178 454 616 1240 2061 4322 18909 51320 207842
transposition_killer 189 426 605 998 2005 3401 15144 38496 83294
transposition_history 179 438 601 1022 2532 4520 46944 52960 710784
negascout 176 486 627 1114 2289 4473 24078 41946 264479
negascout_k 187 460 650 1005 2166 3613 15768 39655 88779
negascout_t 179 501 638 1105 2223 3883 21157 34196 168660
negascout_kt 195 475 660 1010 2344 3393 18102 33940 83500
, , test = end50.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 200 485 751 2827 3720 55758 50671 2491893 931608
killer 210 492 752 2131 3410 12013 35261 227140 474763
history 195 441 716 1895 2772 11375 35854 246142 922977
transposition 217 478 766 2794 3542 47966 41393 0 575047
transposition_killer 211 485 758 2054 3335 10757 29008 174299 341710
transposition_history 204 485 785 1980 2708 10894 31205 193935 512147
negascout 204 442 826 2346 3672 36083 45100 905580 693858
negascout_k 211 455 753 1726 2984 11536 28311 140752 364351
negascout_t 207 460 784 2383 3266 30463 33674 0 443437
negascout_kt 213 464 761 1830 2905 10904 22865 121707 272435
, , test = end51.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 212 362 837 1201 5664 5245 69571 57538 1688834
killer 214 358 799 1202 3707 4492 27389 41321 243976
history 195 361 689 1064 4276 5464 55629 77957 840714
transposition 213 375 848 1334 5527 5086 62287 48701 0
transposition_killer 221 376 812 1242 3733 4290 21390 30226 205549
transposition_history 223 368 760 1127 4745 5133 50674 60370 775909
negascout 211 399 822 1149 4117 5536 55090 56954 1165039
negascout_k 214 387 800 1084 3100 4517 24468 36420 211630
negascout_t 211 410 856 1231 4000 5573 47679 50778 0
negascout_kt 218 393 788 1102 3167 5198 20978 32365 200718
, , test = end52.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 198 414 756 1247 1937 6062 14808 54985 260111
killer 194 417 623 1139 1849 5101 11592 40707 170471
history 186 353 610 1090 2331 5982 18558 64198 447542
transposition 200 408 771 1331 1928 5629 12989 43926 200285
transposition_killer 197 417 647 1163 1824 4646 10925 32587 149735
transposition_history 203 377 658 1134 2521 5580 17178 49029 374971
negascout 206 432 737 1185 1827 5641 13071 45879 195934
negascout_k 193 406 613 1167 1692 5179 10211 39142 122034
negascout_t 207 428 750 1216 1771 5144 11997 36647 144741
negascout_kt 196 421 611 1232 1729 4937 11026 33539 109840
, , test = end53.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 212 461 863 2485 5738 67904 57590 4345872 790559
killer 210 455 779 1885 3680 9357 36045 94305 342322
history 198 450 841 1740 3292 18286 59906 210539 848386
transposition 213 482 895 2461 5426 53619 48650 0 607965
transposition_killer 215 469 812 1894 3418 8434 30114 70209 0
transposition_history 214 491 903 1898 3297 17306 52562 169035 757692
negascout 210 500 901 2407 4884 31277 44704 1201767 553896
negascout_k 210 505 837 1891 3298 7955 30283 69314 262176
negascout_t 211 528 878 2504 4764 28718 43612 0 443394
negascout_kt 214 504 828 2102 3293 8745 30791 67698 253523
, , test = end54.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 188 395 710 1103 3626 4524 38123 44213 457657
killer 190 409 649 1205 2527 4020 18607 42947 188959
history 176 372 623 943 2492 3984 25835 50882 272092
transposition 188 393 729 1155 3566 4339 33159 35897 335481
transposition_killer 188 418 659 1165 2431 3885 16170 35659 160509
transposition_history 186 393 669 996 2670 3944 26757 40295 265733
negascout 191 401 621 1095 2191 5277 18367 45771 168647
negascout_k 190 417 607 1066 2069 4777 15367 41653 145154
negascout_t 186 423 623 1089 2153 4653 15757 36421 126648
negascout_kt 193 429 626 1016 2078 4743 13757 37260 112983
, , test = end55.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 228 446 843 1690 5587 12700 51784 318298 842304
killer 229 451 843 1505 4559 7560 43926 107064 501104
history 213 388 833 1578 7407 9879 76901 197943 1131108
transposition 228 440 837 1741 5498 10754 46958 225456 702885
transposition_killer 241 430 860 1442 4437 6468 39790 83033 397591
transposition_history 232 413 919 1718 7493 9449 77771 156008 922494
negascout 228 451 867 1625 5865 11516 47866 191687 776131
negascout_k 229 452 879 1466 3990 7497 39249 79331 440569
negascout_t 232 468 887 1541 5690 9876 42431 138889 635360
negascout_kt 236 464 881 1455 4697 7738 38621 71558 397801
, , test = end56.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 202 373 861 1330 4255 11085 48370 99938 945029
killer 213 351 783 1130 2274 7082 15962 67068 363159
history 187 336 704 1005 2289 8976 24629 89861 761428
transposition 206 379 875 1371 4029 9714 41064 81146 689591
transposition_killer 216 364 775 1168 2232 6592 13460 53590 296338
transposition_history 211 355 776 1065 2321 8685 22177 82144 842391
negascout 201 366 849 1204 3260 8014 31708 69252 806823
negascout_k 206 354 780 1057 2095 5503 13382 45388 247042
negascout_t 207 373 862 1199 2960 7195 27368 53603 606342
negascout_kt 208 354 804 1076 1963 5348 11614 37573 277568
, , test = end57.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 178 424 609 1951 1793 17068 10352 265466 124935
killer 182 369 602 1562 1807 6926 9994 66725 99974
history 163 378 620 1520 1923 9225 12215 154068 342606
transposition 184 439 632 2025 1893 15878 9614 230702 93906
transposition_killer 187 375 616 1597 1820 6648 9379 59434 85372
transposition_history 181 395 678 1620 2116 9181 11898 133863 374408
negascout 177 421 626 1772 1743 12042 7732 145348 74015
negascout_k 180 369 646 1480 1775 4947 7565 46505 73514
negascout_t 190 436 636 1795 1883 10308 7669 133608 61528
negascout_kt 185 373 655 1574 1906 5102 8252 49164 69514
, , test = end58.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 236 644 829 3409 4273 37559 42141 516123 480012
killer 241 535 815 1913 3399 14112 29522 173560 304126
history 219 461 780 1741 3133 15023 27099 438299 1025183
transposition 235 668 833 3381 4106 34323 34691 425568 339072
transposition_killer 242 559 825 1942 3298 12978 23376 135639 234761
transposition_history 236 518 859 1850 3143 13990 22354 377009 855769
negascout 237 651 855 3380 4692 32901 44719 449075 462755
negascout_k 244 584 809 1929 3465 13789 26732 171201 306630
negascout_t 238 693 847 3107 4734 29215 38682 396939 367758
negascout_kt 251 557 830 1918 3774 13085 29430 178562 287312
, , test = end59.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 175 382 598 1446 2051 9316 15701 91050 125357
killer 182 382 601 1223 1981 7358 13614 48518 104513
history 168 367 541 1178 1846 5823 12334 48768 114204
transposition 182 383 600 1396 1991 8719 12928 74567 90219
transposition_killer 183 392 612 1243 2069 7224 12367 43784 91378
transposition_history 180 390 565 1272 1963 6026 11536 43587 114230
negascout 176 391 601 1270 2129 9195 15964 137736 108460
negascout_k 179 401 620 1092 2034 6278 12079 45030 88573
negascout_t 179 404 623 1228 2003 7652 12094 71868 70125
negascout_kt 184 413 623 1116 2004 6419 10978 38308 70561
若干、入れ替わりもあるが多くの盤面でNegaScout + killer heuristic + transposition tableが最も効果的であることが分かる。
登録:
投稿 (Atom)