αβ＋PV保存ルーチン

　http://d.hatena.ne.jp/Gasyou/comment?date=20080108#cで将棋所の作者さんから質問があった件で、TDLeaf(λ)をやってる人にも有用そうな情報なので、αβでの先読みにPV*1保存機能を追加したバージョンをアップ。

　ざっくり説明すると、AlphaBetaSearcherというクラスのsearchNegaMax関数で、ルートでは

Te *pv[ 100 ];// PV保存用の領域。サイズは適当。
const double score = searcher->searchNegaMax( kyokumen, evaluator, pv, 0, LOSE, WIN ); // 関数終了後は配列pvにPVが入る。

　という感じで呼び出すと、pv[ 0 ]にルートノードでの最善手が、以下[1],[2]・・・には順に深さ1,2・・・の最善手が入ります。

　通常のαβからの変更点は

1. 引数にpvを追加。
2. 関数内で「そのノードから先のPV」を一時的に保存する為の領域currentPvを確保。
3. pvのターミネート（二箇所）。
4. 最善手更新の際にcurrentPvからpvにコピー。

　といった辺りです。

　以下、コードです。長いので「続きを読む」で。

// NegaMaxアルゴリズムで探索を行い、評価値を返す関数。
// 引数は順に局面、評価関数、PV保存用の領域、深さ、α、β
double AlphaBetaSearcher::searchNegaMax( Kyokumen *const kyokumen, Evaluator *const evaluator, 
                                         Te **pv, const int depth, const double alpha,const double beta ) {

	// リーフノード判定
	if( depth == 3 ) {

                   // PVをターミネート
		 pv[ depth ] = NULL;

                   // 現在の局面の評価値を返す
		 return evaluator->evaluate( kyokumen->getCurrentView(), kyokumen->getTeban() ); 

	}// if(リーフノード)

	// このノードの評価値
	double bestEvaluatedValue = LOSE + depth;

	// このノードのα値
	double currentAlpha = alpha;

	// このノードから先のPV
	Te *currentPv[ 100 ];

	// とりあえずPVをターミネート
	// 必要なら後で更新する
	pv[ depth ] = NULL;


	// 合法手一覧生成し、teArrayに保存。
         // teNumには合法手の数が入る。
	Te *teArray[ TE_MAX ];
	const int teNum = kyokumen->getApplicableTeArray( teArray );


	// 合法手が無い＝投了
	if( teNum == 0 ) {

		pv[ depth        ] = Te::TORYO;
		pv[ depth + 1 ]    = NULL;

		return LOSE + depth;

	}// if(投了)


	// 全ての合法手を順にチェック
	for( int i = 0; teArray[ i ] != NULL; i++ ) {


		// 一手進める
		kyokumen->apply( teArray[ i ] );

		// 再帰的に評価
		const double currentEvaluatedValue = 
                           -1 * this->searchNegaMax( kyokumen, evaluator, currentPv, depth + 1, -beta, -currentAlpha );

		// 一手戻す
		kyokumen->undo();

		// 最善手更新か否か判定
		if( bestEvaluatedValue <= currentEvaluatedValue ) {


			// 評価値更新
			bestEvaluatedValue = currentEvaluatedValue;

			// PV更新（NULLターミネートの部分まで)
			pv[ depth ] = teArray[ i ];
			for(int j = depth + 1; true; j++ ){

				pv[ j ] = currentPv[ j ];
				
				if( currentPv[ j ] == NULL ) break;

			}// for(..j..)

			// βカット判定
			if( beta < bestEvaluatedValue ) {

				return bestEvaluatedValue;

			}// if(βカット)

			// α更新
			currentAlpha = MAX( currentAlpha, bestEvaluatedValue );

		}// if(最善手更新)

	}// for(..i..)

         // このノードの評価値を返す
	return bestEvaluatedValue;

}// searchNegaMax(...)

　てか、相変わらず無駄に長いコードですね。うーんf(-_-;

*1:双方最善を尽くした際の手順