Df-Pnアルゴリズムでチェス・プロブレムを解いてみた。

![スクリーンショット 2025-05-04 153506.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519376/b93dab61-4772-4664-a997-a9b413502cca.png)
![スクリーンショット 2025-05-04 153525.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519376/1d5d926b-e371-4972-a5b3-59f7e6f18e43.png)
```
		const int INFINITYVAL = 320000; // 無限大
		const int HASH_SIZE = 1024 * 1024;

		const int SUCCESS = 1;
		const int UN_FINISHED = 0;
		const int FAILURE = -1;

		Play[] answer = new Play[32];

		ulong hash(ulong Key)
		{
			return Key % (HASH_SIZE);
		}
		int MinFunc(int a, int b)
		{
			if (a < b) return a;
			return b;
		}
		int addition(int n, int m)
		{
			if (n == INFINITYVAL || m == INFINITYVAL)
				return INFINITYVAL;
			else
				return n + m;

		}
		// 子ノードで最小の証明数を求める
		int MinPn(List<Play> children)
		{
			int pn = 0, dn = 0;
			int pn_min = INFINITYVAL;
			for (int i = 0; i < children.Count; i++)
			{
				TTLookUp(children[i].HashKey, ref pn, ref dn);
				pn_min = pn_min < pn ? pn_min : pn;
			}
			return pn_min;
		}
		// 子ノードで最小の証明数の和を計算
		int SumPn(List<Play> children)
		{
			int pn = 0, dn = 0;
			int pn_sum = 0;
			for (int i = 0; i < children.Count; i++)
			{
				TTLookUp(children[i].HashKey, ref pn, ref dn);
				pn_sum = addition(pn_sum, pn);
			}
			return pn_sum;
		}
		// 子ノードで最小の反証数を求める
		int MinDn(List<Play> children)
		{
			int pn = 0, dn = 0;
			int dn_min = INFINITYVAL;
			for (int i = 0; i < children.Count; i++)
			{
				TTLookUp(children[i].HashKey, ref pn, ref dn);
				dn_min = dn_min < dn ? dn_min : dn;
			}
			return dn_min;

		}
		// 子ノードで最小の反証数の和を計算
		int SumDn(List<Play> children)
		{
			int pn = 0, dn = 0;
			int dn_sum = 0;
			for (int i = 0; i < children.Count; i++)
			{
				TTLookUp(children[i].HashKey, ref pn, ref dn);
				dn_sum = addition(dn_sum, dn);
			}
			return dn_sum;

		}
		int SelectChild_OR(List<Play> children, ref int dnc, ref int pn2)
		{
			int n = -1;
			int pc;
			int p_num = 0, d_num = 0;
			dnc = pc = pn2 = INFINITYVAL;
			for (int i = 0; i < children.Count; i++)
			{
				TTLookUp(children[i].HashKey, ref p_num, ref d_num);
				// pc  ɍŏ    p_num      
				// pn2  ɓ Ԗڂɏ      p_num       
				if (p_num < pc)
				{
					n = i;
					pn2 = pc;
					pc = p_num;
					dnc = d_num;
				}
				else if (p_num < pn2)
				{
					pn2 = p_num;
				}
			}
			return n;

		}
		int SelectChild_AND(List<Play> children, ref int pnc, ref int dn2)
		{
			int n = -1;
			int dc;
			int p_num = 0, d_num = 0;
			pnc = dc = dn2 = INFINITYVAL;
			for (int i = 0; i < children.Count; i++)
			{
				TTLookUp(children[i].HashKey, ref p_num, ref d_num);
				// dc  ɍŏ    d_num      
				// dn2  ɓ Ԗڂɏ      d_num       
				if (d_num < dc)
				{
					n = i;
					dn2 = dc;
					pnc = p_num;
					dc = d_num;
				}
				else if (d_num < dn2)
				{
					dn2 = d_num;
				}
			}
			return n;

		}
		void TTSave(ulong Key, int p_num, int d_num)
		{
			ulong k;
			k = hash(Key);
			MateTbl[k].HashKey = Key;
			MateTbl[k].pf = p_num;
			MateTbl[k].dn = d_num;

		}
		void TTLookUp(ulong Key, ref int p_num, ref int d_num)
		{
			ulong k;
			k = hash(Key);

			if (MateTbl[k].HashKey == Key)
			{
				p_num = MateTbl[k].pf;
				d_num = MateTbl[k].dn;
			}
			else
			{
				p_num = 1;
				d_num = 1;
			}
		}
	public int DfPnSearch(Board b, int color, int depth, int depthMax)
	{
		int mate = FAILURE - 1;
		int root_th_p_num, root_th_d_num;
		int p_num, d_num;
		for (int i = 0; i < HASH_SIZE; i++)
		{
			MateTbl[i] = new MateEntry();
		}
		root_th_p_num = root_th_d_num = INFINITYVAL - 1;
		p_num = d_num = INFINITYVAL - 1;
		MidOr(b, color, depth, depthMax, ref p_num, ref d_num, ref root_th_p_num, ref root_th_d_num);
		if (p_num == 0) mate = SUCCESS;
		if (d_num == 0) mate = FAILURE;
		return mate;
	}

	void MidOr(Board b, int color, int depth, int depthMax, ref int p_num, ref int d_num, ref int mother_th_p_num, ref int mother_th_d_num)
	{
		int i;
		int child_th_p_num;
		int child_th_d_num;
		int dnc = 0;
		int pn2 = 0;
		
		TTLookUp(b.HashKey, ref p_num, ref d_num);
		if (mother_th_p_num <= p_num || mother_th_d_num <= d_num)
		{
			// 臒l 𒴂    Ƃ 
			mother_th_p_num = p_num;
			mother_th_d_num = d_num;
			return;
		}
		
		List<Play> valid_moves = new List<Play>();
		b.get_valid_moves(color, ref valid_moves);
		if (valid_moves.Count == 0)
		{
				p_num = INFINITYVAL; d_num = 0;
				TTSave(b.HashKey, p_num, d_num);
				valid_moves.Clear();
				return;
		}
        // 千日手の処理
		int perpetual = 0;
		if (depth > 1)
		{
			for (i = depth - 1; i > 0; i -= 2)
			{
				if (b.HashHistory[i] == b.HashKey)
				{
					perpetual++;
				}
			}
		}
		if (perpetual > 1)
		{
			p_num = INFINITYVAL; d_num = 0;
			TTSave(b.HashKey, p_num, d_num);
			return;
		}
		if (depth > depthMax)
		{
			p_num = INFINITYVAL; d_num = 0;
			TTSave(b.HashKey, p_num, d_num);
			valid_moves.Clear();
			return;
		}
		for (int j = 0; j < valid_moves.Count; j++)
		{
			b.make_move(color, valid_moves[j]);
			if (b.controlW[b.kingBpos] != 0) valid_moves[j].value = 1; else valid_moves[j].value = 0;
			valid_moves[j].HashKey = b.HashKey;
			valid_moves[j].PathKey = b.PathSeed[j * depth];
			b.undo_move(color);
		}
		// 指し手を順序付ける
		for (i = 0; i < valid_moves.Count; i++)
		{
			for (int j = i + 1; j < valid_moves.Count; j++)
			{
				if (valid_moves[i].value < valid_moves[j].value)
				{
					Play play = valid_moves[i];
					valid_moves[i] = valid_moves[j];
					valid_moves[j] = play;
				}
			}
		}
		dnc = INFINITYVAL;
		pn2 = INFINITYVAL;
		while (mother_th_p_num > MinPn(valid_moves) && mother_th_d_num > SumDn(valid_moves))
		{
			i = SelectChild_OR(valid_moves, ref dnc, ref pn2);
			// 臒l ̐ݒ 
			child_th_p_num = MinFunc(mother_th_p_num, pn2 + 1);
			child_th_d_num = mother_th_d_num + dnc - SumDn(valid_moves);
			b.make_move(color, valid_moves[i]);//Refresh();MessageBox.Show("");
			MidAnd(b, b.flip(color), depth + 1, depthMax, ref p_num, ref d_num, ref child_th_p_num, ref child_th_d_num);
			b.undo_move(color);
			Best[0, depth] = valid_moves[i];
		}
		p_num = MinPn(valid_moves);
		d_num = SumDn(valid_moves);
		TTSave(b.HashKey, p_num, d_num);
		valid_moves.Clear();
	}
	void MidAnd(Board b, int color, int depth, int depthMax, ref int p_num, ref int d_num, ref int mother_th_p_num, ref int mother_th_d_num)
	{
		int i;
		int child_th_p_num;
		int child_th_d_num;
		int pnc;
		int dn2;
		
		TTLookUp(b.HashKey, ref p_num, ref d_num);
		if (mother_th_p_num <= p_num || mother_th_d_num <= d_num)
		{
			// 臒l 𒴂    Ƃ 
			mother_th_p_num = p_num;
			mother_th_d_num = d_num;
			return;
		}
		List<Play> valid_moves = new List<Play>();
		b.get_valid_moves(color, ref valid_moves);
		if (valid_moves.Count == 0)
		{
            // チェックメイト
			if (b.controlW[b.kingBpos] != 0)
			{
				p_num = 0; d_num = INFINITYVAL;
				TTSave(b.HashKey, p_num, d_num);
				pCount = depth;
				valid_moves.Clear();
				return;
			}
			else//ステイルメイト
			{
				p_num = INFINITYVAL; d_num = 0;
				TTSave(b.HashKey, p_num, d_num);
				valid_moves.Clear();
				return;
			}
		}
        
        // 千日手の処理
		int perpetual = 0;
		if (depth > 1)
		{
			for (i = depth - 1; i > 0; i -= 2)
			{
				if (b.HashHistory[i] == b.HashKey)
				{
					perpetual++;
				}
			}
		}
		if (perpetual > 1)
		{
			p_num = INFINITYVAL; d_num = 0;
			TTSave(b.HashKey, p_num, d_num);
			return;
		}
		
		for (i = 0; i < valid_moves.Count; i++)
		{
			b.make_move(color, valid_moves[i]);
			valid_moves[i].HashKey = b.HashKey;
			b.undo_move(color);
		}
		
		pnc = INFINITYVAL;
		dn2 = INFINITYVAL;
		while (mother_th_d_num > MinDn(valid_moves) && mother_th_p_num > SumPn(valid_moves))
		{
			i = SelectChild_AND(valid_moves, ref pnc, ref dn2);
			// 臒l ̐ݒ 
			child_th_p_num = mother_th_p_num + pnc - SumPn(valid_moves);
			child_th_d_num = MinFunc(mother_th_d_num, dn2 + 1);
			b.make_move(color, valid_moves[i]);
   			MidOr(b, b.flip(color), depth + 1, depthMax, ref p_num, ref d_num, ref child_th_p_num, ref child_th_d_num);
			b.undo_move(color);
			Best[0, depth] = valid_moves[i];
		}
		d_num = MinDn(valid_moves);
		p_num = SumPn(valid_moves);
		TTSave(b.HashKey, p_num, d_num);
		valid_moves.Clear();
	}
```

　４手詰め（将棋の７手詰め）が一瞬で解けました。
 ソースは以下にあるC++をC#に移植したものを使いました。
 https://www.cc.kochi-u.ac.jp/~tyamag/jyohou/crosscram.pdf