極大値、極小アルゴリズム及びα-β剪定技術

中国の将棋のプロジェクトの中の極大値、きわめて小さい計算方法とα-β剪定技術

の極大値、極小アルゴリズム

.問題提起

.コード実現

α-β剪定最適化

.コード実現、上のコードと比較することに注意してください.

.コード解析

.その他の最適化点

極小アルゴリズム
1.質問の提出
中国将棋の人機対戦モジュールの開発において、パソコンはどうやって次の駒を選ぶかについて、まず自然に推値関数を設定して、自分の駒と駒ごとに移動できる目標位置を暴力的に遍歴し、移動後の推定値関数の値が一番大きい移動方式を見つけます.ここでの評価関数は最初は簡単に駒ごとに固定された値を設定し、自分の駒の価値の和から相手の駒の価値の和を差し引いた最大値を評価関数として返します.このような方法の効果はとても悪くて、コンピュータは歩く時いつももとの場所で回転しやすくて、実は私達の平常の碁を打って発見することができますに比べて、私達は1歩歩くごとに、いずれも相手がどのように歩くことができるかを考えて、私達は相手の1つの駒を食べて、かえって多くなることができますか?パソコンにもいろいろ考えさせたいですが、どうやって実現しますか?私達は詳しく分析してみます.私達が将棋をするのはできるだけ相手の碁を食べて、相手に自分の碁を食べられないようにします.言い換えれば、私達が選ぶ時にできるだけ最高の点数を得て、相手にできるだけ小さい点数を得させます.これは大きな値を引き出します.相手が作り出したすべての自分に対する価値の大きい选択の中で(自分に対する価値が小さいこと、またはマイナスのことを意味します)の选択の中で自分に対する価値が一番大きいものを一つ选びました.
2.コード実現
(1)何層(2)再帰的呼び出し終了条件(3)最大値(getMaxScore)と最小値(getMinScore)を求める関数でgetAllPossible関数が呼び出されるかを考慮しなければならないが、この関数は誰によって呼び出しられたかによって内部処理が異なります.最大値は自分のステップに相当しますので、最小値は相手のステップに相当します.(本プロジェクトについては、内部は、赤棋走か黒棋走かによって対応する可能なステップに戻る)(4)最上階の上に、getBestStepからgetMaxScore関数の呼び出しを開始し、初期レベルに入るべきである(本プロジェクトに対しては、最適な選択を示すステップを返します.点数ではなく、1つのステップを返します)(5)本プロジェクトでは、人が一歩歩くと、コンピュータはすぐにステップを計算します.どう考えているかは、レベルが高いと、フロントエンドのレンダリングがブロックされます.解決策は遅延時間(タイマーで実現します.)で計算してもいいです.

//step      
int getMaxScore(int level)
{
	//   0，          
	if(level == 0) return calcScore();
	vector<step*> steps;//         
	getAllPossibleStep(steps);//            steps 
	//step * res;//     
	int maxScore = int(1<<31);//      
	for(auto it = steps.begin(); it != steps.end(); it++)
	{
		step * cur = *it;
		fakeMove(step);//       
		int score = getMinScore(level-1);//          
		unFakeMove(step);//       
		if(score > maxScore)
		{
			maxScore = score;
		}
	}
	return maxScore;
}
//                     
int getMinScore(int level)
{
	//   0，         
	if(level == 0) return calcScore();
	vector<step*> steps;//         
	getAllPossibleStep(steps);//            steps 
	//step * res;//     
	int minScore = int(~(1<<31));//      
	for(auto it = steps.begin(); it != steps.end(); it++)
	{
		step * cur = *it;
		fakeMove(step);//       
		int score = getMaxScore(level-1);//          
		unFakeMove(step);//       
		if(score < maxScore)
		{
			maxScore = score;
		}
	}
	return minScore;
}

α-β剪定の最適化
1.コードを実現し、上のコードと比較することに注意する(実は大きな違いはない)

int getMaxScore(int level, int currentMin)
{
	//   0，         
	if(level == 0) return calcScore();
	vector<step*> steps;//         
	getAllPossibleStep(steps);//            steps 
	//step * res;//     
	int maxScore = int(1<<31);//      
	for(auto it = steps.begin(); it != steps.end(); it++)
	{
		step * cur = *it;
		fakeMove(step);//       
		int score = getMinScore(level-1);//          
		unFakeMove(step);//       
		//    ，    （                      ，    
		//           ，                     ，  
		//             ，
		//                ，          ）
		if(score >= currentMin)
		{
			return score;
		}
		
		if(score > maxScore)
		{
			maxScore = score;
		}
	}
	return maxScore;
}
//                     
int getMinScore(int level, int currentMax)
{
	//   0，         
	if(level == 0) return calcScore();
	vector<step*> steps;//         
	getAllPossibleStep(steps);//            steps 
	//step * res;//     
	int minScore = int(~(1<<31));//      
	for(auto it = steps.begin(); it != steps.end(); it++)
	{
		step * cur = *it;
		fakeMove(step);//       
		int score = getMaxScore(level-1);//          
		unFakeMove(step);//       
		
		if(score <= currentMax)
		{
			return socre;
		}
		
		if(score < maxScore)
		{
			maxScore = score;
		}
	}
	return minScore;
}

2.コード分析
比較は最適化されていない状態と比較して、ただ一つのパラメータが多くなりました.なぜ直接的に切ることができますか?まず、スコアの計算は一番下の階で行われます.(つまり、レベルなどと0の時)例えば、ツリーの構造の中の葉っぱノードのように、計算結果を1層ずつ上に送り、送りの過程で1層ずつ比較して、枝を切らない時は、すべての葉っぱノードが計算されて、上に送り、比較して、最大値または最小値を選んで、再帰点まで送り続けます.即ち、必要な得点を得るための一番いい歩き方です.不必要な計算です.ここでの再帰は一回で最後まで計算し、その後遡って、最後まで計算します.このようにすると、葉っぱノードの計算は連続して行われていません.中間に遡る過程があります.最大値を求める関数では最小値と関数を呼び出して、現在の最大値が入ってきます.最小値関数を求める場合、下層から送られてきたスコアが着信の最大値より小さい場合、最小値関数を求める下層再帰解過程で切り落とされることは間違いないです.最小値関数を求める値は、それよりも着信の最大値より大きくないはずです.大きい値の小さい値.(2)最小値を求める関数で最大値を求める関数を呼び出し、現在の最小値を入力します.最大値を求める関数では、下層から送られてきた値が着信の最小値より大きい場合、最大値関数を求める下層再帰解過程で切り落とされることは間違いありません.上層に最小値関数を渡すために、自分の最大値を求めます.これは最大値です.この値は、着信した最小値よりも大きな値ではないはずです.最小値を求める関数では絶対に使用されません.
3.その他の最適化点
(1)現在のレイヤのすべての可能な状況を何らかの方法で並べ替えると、戻り値がより早く得られるようになり、次の層を呼び出したときに、より良い剪定効果が得られる.(具体的には、すべての状況を求める関数の中で、駒を巡る順序を調整してもいいです.例えば、車のすべての歩調は先に兵と歩ける歩を次の組に入れてもいいです.実は、これがもっと細いなら、推値関数と合わせて調整して、中間層で先に簡単に推定値関数を使用してもいいです.)評価関数の最適化については、元の手順で各駒に固定的な分値を設定しますが、実際には異なる状況で駒は異なる価値があるべきです.調整して、より良い選択を得るべきです.ある駒がある位置に移動できるかどうかを判断する時に使う関数は最適化され、判断の効率を高め、可能なステップをすべて取得する時に、異なる駒については、ある位置までは行けないと判断できます.直接フィルタしてもいいです.移動できるかどうかを判断する関数を呼び出すのではなく、充填する方法を使います.可能なすべての移動ステップを取得します.