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