コンピュータ将棋の基礎知識

この用語集の内容は無保証です。この用語集を信じて開発した将棋ソフトが 選手権で大敗しても、私は責任はもちませんし関知しません。あしからず

コードや数式は極力書かず、読み物に徹しています。


ドーピング

　自動学習でうまく行かない所や、データがないところを手動で補ってやる行為。語源は棚瀬さん？

FutilityCut

　探索中に残り１手の場合に、評価関数の値よりある程度alphaを下回っていれば、あと1手さらに指してもalphaを下回るだろうという予測の元にalphaカットとみなす。逆にある程度betaを上回っていると、あと1手指してもbetaを超えるだろうと予測してbetaカットする、といった後ろ向き枝狩り手法。評価関数の値の代わりに静止探索の値を用い、上回る定数幅をやや広げることで、残り2手の場合にも適用される。

KillerMove

　探索中にベータを超えた良い手などを深さに応じて保持しておき、同じ深さの兄弟ノードを探索時に、先ほどの手（Killer手）を優先して探索するとベータカットが起こる可能性が高いので、探索を効率化できる（手が合法手であることを確認して指せば、手生成をする前にKiller手を探索できる）

singular-extension

　兄弟ノードの中で突出して探索結果の良い手(singular)を延長探索する手法。

前向き枝狩り

　探索行為を行わずに、予め静的なルールを用いて枝狩りを行う行為。

後ろ向き枝狩り

　狭義には、Alpha-Beta法など、理論上MinMax探索と等価であると見なせる枝狩りを指す。探索途中の結果を動的に活用し枝狩りを行う行為も広義には後ろ向き枝狩りと呼ばれている。

選択的探索

　古来、コンピュータ将棋においてPCの処理能力の問題もあり、生成された手の中から有力なものだけを残して探索を行っていた。選択的探索の選択行為は前向き枝狩りが使われることが多い。読み抜けを起こさないように枝狩りすることが肝要である。

全幅探索

　近年のPCの性能アップを受けて、将棋の手生成後に前向き枝狩りをせずにすべての手を探索することで、読み抜けの問題を無くしている。通常、全幅探索とは言っても深く読むためには探索が深いところでは、数々の枝狩り手法が適用されている。

NullMove枝狩り

　自分がパスをして相手に手番を渡しても、それでも結果がベータ以上なら、パスしないでどんな手を指したところでベータ以上になるはずなので、それ以上探索しないでのベータ以上と仮定する。山下さんによれば、商業チェスソフト界においてこっそり使われていた手法らしい

NullWindowサーチ

　Alpha-Beta探索の幅を1にして探索する手法。探索が高速に行える。alpha以下？beta以上か？など境界を調べるときに使われる。

ハッシュ値

　置換表などで使われる。将棋の局面を64ビットの数値で表現することで、高速に局面認識をする。ハッシュの作り方を参照。

ハッシュの作り方

　ある指し手の駒や位置毎にランダムな数値を予め割り当てておき、手を指し、局面を更新するときに64ビットなどのハッシュ値を更新していくと、任意の局面を任意のハッシュ値で表現できる。1^64の空間が表現できるので、違う局面が同じハッシュ値になってしまう危険性はかなり少ない（乱数の精度にもよる）

置換表

　将棋の局面をハッシュで表現し、ハッシュ毎に、alpha値やbeta値、最善手などを保存して置く。探索中に置換表を参照し、既に探索済み局面であれば置換表のデータを活用して探索を省略する。

部分ハッシュ

　通常は、将棋の局面の全体をハッシュ値として表すが、「金と銀だけ」や「持ち駒を除いて盤面だけ」などと部分的なハッシュを指す。

山下さん

　YSSの作者。YSSは商業ブランドとしては「AI将棋」として販売されている

手筋マクロ

　将棋の手で、よくある三手続きのリストを持っておいて、局面において登場した場合に、1手〜2手延長することで、お約束の手筋をスキップしてさらに先を読ませる

n-gram手筋マクロ

　大槻さんがGPWで発表された。プロの棋譜よりよく現れる手筋をn-gramとしてリストアップし、エントロピーを考慮して出現頻度を評価している

実現確率探索

　プロの棋譜より、指し手の種類毎の出現頻度を統計的に求める。探索で深く局面を進める上で、指し手の実現確率を掛け合わせた「残確率」を優先して縦型探索をする探索手法。激指が始めた。多数のソフトが採用している。

ABC探索

　探索中に展開される合法手のうち、最善手の候補として有望と思われる手が多いノードほど、探索木のルートへの共謀度が高いとし、不確定要素の少ない共謀数が少ないノード（より強制された）を優先して深く探索する探索法。KFEndが用いている。

証明数詰め探索

　王手に対する応手の数を証明数として、王手する側が詰みを証明しないといけない証明数が減る局面を優先して探索する手法。詰みは速く判るが、不詰みはなかなか判らない（らしい）

df-pn詰め探索

　証明数探索に対して、逆に不詰みに対応する反証明数も定義し、両方から詰め探索を行うもの。詰みと不詰みの両方が素早く認識できる。一方で浅い詰め物に時間がかかかる場合もある。

落とし穴

　序盤に王を囲う為に、金や銀などを囲いの位置へ誘導する行為。駒が移動する経路は評価値が少しずつ上昇するようになり、囲いの位置で最大評価値となる。評価値が高い方へ、駒が落とし穴に落ちていくように移動するため、落とし穴と呼ばれている。

静止探索

　局面を「静止化」させるための探索。 　ある局面で、次の手番がただで飛車を取れる場合、ある局面をそのまま駒割を計算すると飛車が相手に渡ることが評価値に盛り込まれない。よって、駒のぶつかり合いがなくなって「静かな局面」になるまで、駒を取る手のみの探索が行う。

手の逐次生成

　通常指し手の生成は合法手をすべて生成し、オーダリングを行って、有望な手の順に探索を行うが、逐次生成では、カテゴリ毎等に少数の手を逐次的に生成する。逐次生成では、中途でベータカットが発生すれば、速度的な探索効率が上昇する可能性がある。逐次生成では速度アップとの引き替えに、全体のオーダリング精度の維持が必要となる。

Bitboard

　歩のあるなしを1/0のビットで表現するなど、すべての駒について盤上のあるなしを、別の変数として1/0で保持しておく。駒の移動などにともない該当するbitboardを更新する。bitboardで駒の状態を保持することで、ビットパラレル性による並列処理が可能になる。chessではCrafty、将棋ではBonanza等が採用している。

反復深化

　たとえば7手読むときにいきなり7手を読まずに、まず3手、次に4手、次に5手という具合に徐々に深さを深めながら段階的に探索を行う行為。再探索は行うことになるが、ハッシュテーブルに情報を保持していることと、探索結果でオーダリングが行われることから、より高速に探索を行える。縦型探索の欠点を緩和し、横型探索に近づけている。

Aspirationサーチ

　反復深化の改良型。ルートでの探索範囲を[-∞,+∞]とせずに、反復深化での前回の探索結果にいくらかの定数で前後した範囲で探索を行う。仮に探索範囲を超えていた場合は、超えた方向を∞に変えて再探索を行う。再探索のオーバーヘッドは発生するが、探索範囲を狭めることでの高速化が見込める。

オーダリング

　Alpha-Beta探索は理論的にMinMax探索と等価であることが証明されているが、探索時間はより少なくて済む。ただし探索する手の順番が理論上の評価が悪い順に並んでいるとAlpha-Beta探索はMin-Max探索と同等の探索時間がかかると言われている（証明されている模様）。よって手の順番（オーダリング）は重要であると言える。

脅威

　KFEndの有岡さんによる解説ページが詳しい。同じ評価値の違う局面において、片方は自分がパスをすると、相手が駒を取れる場合は、その損害を定数で割って脅威として評価値に足し込む。同じ評価値の局面なら、より相手から脅威を受けている局面の方が評価値は少なくなるという考え方に基づく。

二つの脅威

　相手から受ける脅威が一つであれば防御をすることで対処できる可能性が高いが、脅威が二つの場合は、高い方の脅威は防御できても、低い方の脅威は現実になる可能性が高い。一つより二つの脅威を相手に与える方が効果的である。両取りなどは二つの脅威の例である。

コンピュータ将棋関係イベント

　

コンピュータ将棋協会（CSA）例会に行ってきました

　 http://d.hatena.ne.jp/mkomiya/20070909

定跡の利用

　

れさぴょんの定跡処理

　 http://d.hatena.ne.jp/mkomiya/20080129#p1 　

Bonanzaの定跡処理

　 http://d.hatena.ne.jp/mkomiya/20080129#p2

コンピュータ将棋における機械学習

　

ゲームでの強化学習など学習の分類をしてみた

　 http://d.hatena.ne.jp/mkomiya/20071112/p1 　

強化学習TD法による将棋の学習について（農工大小谷研）

　 http://d.hatena.ne.jp/mkomiya/20070401#p2 　

Bonanzaの評価関数の学習手法について

　 http://d.hatena.ne.jp/mkomiya/20070401/p4 　

ボナンザvs勝負脳の新書を買ってきました

　 http://d.hatena.ne.jp/mkomiya/20070821/p3 　

拘束条件によるペナルティ

　 http://d.hatena.ne.jp/mkomiya/20080117/p2

新しい流れ - coming future

　

遠見将棋がモンテカルロになってる！！（激震）

　 http://d.hatena.ne.jp/mkomiya/20071116/p3 　

将棋の階層化された戦略について

　 http://d.hatena.ne.jp/mkomiya/20071107/p1

探索手法のサンプルコード紹介

　

null-move pruning

　パス(nullMove)をして浅く探索してみて、それでもβ値を超えるようなら、何を指してもβ越える（と予想される）ので、βカットしていいと判断する枝狩り手法。
　かなり強力に枝狩りできます。

　浅く探索しても結果が得られるので、高速に判断できます（パスをするハンデを背負っているのに、少ない手しか挽回できないのにβを越えるなら、深く指せばβを越えること間違いないという考え方） 
if( !in_check && depth>=3 && (depthMax-depth)>=2 && doNull==1 ) {
	int R=2;
	if( (depthMax-depth)>=6 ) R=3;

	nullMove(SorE);
	value = -full_search(enemy(SorE),-beta,-beta+1,depth+1,depthMax-R, doNull-1 );
	nullUndo(SorE);

	if( value>=beta ) return value;
}
　

futility cut

　残り探索数が１の時、評価関数を呼んで、β値よりEXT_F_MARGINも上回るなら、 残り1手を指してみてもβを越えると予想できるので、βカットしておこうという枝狩り手法。

　終盤は特に枝狩りを可能な手が増える（ただし終盤ほどマージンを高くしないと誤った枝狩りが増える危険も増す模様） 
int stand_pat=MUGEN;
if( depth>=3 && !in_check ) {
	if( depthMax-depth<=1 ) {
		stand_pat = eval(SorE,alpha,beta);
		stand_pat = (SorE==SELF)? stand_pat: -stand_pat;
		if( beta+EXT_F_MARGIN <= stand_pat ) return beta;
	}
}
　

principal variation search

　オーダリングされた合法手のうち、一番有望な手はそのまま探索し、二番目以降の手については、いきなり探索する前に、まず[alpha,alpha+1]のNullWindow探索によって、alphaを越えないかどうかだけを高速に探索し、alphaを越えそうな場合は、[alpha,beta]の元の広さで再探索する手法。

　ハッシュ手の有効度、未知のノードならオーダリングが正確なほど、二番目以降の手で、最善手が更新される可能性は低くなるため、ほとんどの手が高速なNullWindow探索のみで枝狩りできる可能性が高くなる。 　
if( retval==ValueNone ) { // first move
	value = -full_search(enemy(SorE),-beta,-alpha,depth+1,depthMax,doNull );
}
else { // other moves
	value = -full_search(enemy(SorE),-alpha-1,-alpha,depth+1,depthMax,doNull );
	if( value > alpha ) {
		value = -full_search(enemy(SorE),-beta,-alpha,depth+1,depthMax,doNull );
	}
}
　

iterative deepening - 反復深化

　深さ優先縦型探索では、探索中にメモリをあまり消費しない利点はあるが、指定した深さまで探索しないと、次のノードへの探索へ移れないため、深く探索できない。

　たとえば、ハノイの塔で考えてみると、3手の組合せでゴールに導く正解があったとしても、いきなり5手の深さ優先探索をすると、とりかかりの手が悪い場合は、3手のゴールを見つけ出す前に、持ち時間が終わってしまう危険性がある。

　3手で深さ探索をすれば探索時間はかなり減り、速やかにゴールを見つけられる。しかし、一般に正解がどの深さにあるかは判らないため、浅く初めて、徐々に深くしていくと効率が良い。

　このように、探索する深さを徐々に深くして反復探索していく手法を「反復深化」と呼ぶ。探索結果はハッシュとして置換表に残しているため、再探索のオーバーヘッドは抑えられる。
　探索中に探索時間が尽きた場合も、1段浅い探索での最善手は求まっているという利点もある。 　
int ITDeep(uchar SorE,int alpha,int beta,int depth,int depthMax )
{
	int retval;

	Te t[700];
	int tp=generateAllMoves( SorE,t );
	tp=ReOrder(SorE,t,tp);

	for(int i=1;i<=depthMax;i++) {
		retval=full_root( t,tp, SorE,alpha,beta,0,i );
		if( retval<=-MUGEN || retval>=+MUGEN ) break;
	}
	return retval;
}
　

aspiration search

　通常、反復深化でのルートの探索幅は[-∞,∞]で行うが、前回の探索結果を利用して探索幅(Window)を狭める反復深化の改良法。
　Windowを狭めたことで枝狩りの発生を期待できる。
　ただし、探索結果がalphaカット、もしくはbetaカットされた場合は、探索結果が[alpha,beta]の範囲に入っていないので、Window幅を広げて再探索をする必要がある（置換表もあるのでオーバーヘッドは抑えられる）
　一般に最善手が不安定になる傾向がある。 　
const int Aspiration=150;
int ITDeep(uchar SorE,int alpha,int beta,int depth,int depthMax )
{
	int retval;

	Te t[700];
	int tp=generateAllMoves( SorE,t );
	tp=ReOrder(SorE,t,tp);

	for(int i=1;i<=depthMax;i++) {
LOOP:
		retval=full_root( t,tp, SorE,alpha,beta,0,i );
		if( retval<=-MUGEN || retval>=+MUGEN ) break;

		if( retval <= alpha ) { alpha=-MUGEN;goto LOOP; }
		else
		if( retval >= beta  ) { beta=+MUGEN;goto LOOP; }

		alpha = retval-Aspiration;
		beta  = retval+Aspiration;
	}
	return retval;
}

ネットで読める論文


局面評価の学習を目指した探索結果の最適制御

http://www.geocities.jp/bonanza_shogi/gpw2006.pdf

情報量に基づく探索制御手法. チェスにおけるSingular Extension への応用

http://www.graco.c.u-tokyo.ac.jp/~takeuchi/pdf/gpw07.pdf

UCTでオンライン知識とオフライン知識を組み合わせる

http://www.geocities.jp/hideki_katoh/387.jp.pdf

将棋における指し手枝刈りへのProbCut の適用

http://www-nkn.ics.nitech.ac.jp/paper/H17-B/oso.pdf

TD法を用いた将棋の評価関数の学習

http://shouchan.ei.tuat.ac.jp/~shougi/old_shougi/presentation/1999-10-07P.pdf

詰将棋におけるdf-pn+ 探索のための，展開後の証明数と反証数を予測する評価関数

http://www.graco.c.u-tokyo.ac.jp/~kaneko/papers/gpw04.pdf

SVMによる将棋の詰みの予測とその応用

http://www.logos.t.u-tokyo.ac.jp/~miwa/papers/master/mthesis.pdf

駒の関係を利用した将棋の評価関数

http://www.graco.c.u-tokyo.ac.jp/~kaneko/papers/gpw03.pdf

将棋プログラムにおける棋譜を利用した囲いの評価.

http://www.graco.c.u-tokyo.ac.jp/~kaneko/papers/prosym03s.pdf