? ? ? ?与或树搜索可用于判断当前局面是不是对于自己的必胜局面，因此也可以用于寻找当前局面的必胜动作，适用于计算机博弈求解和残局搜索。
在此，粗略作出一些定义：
己方必胜局面：裁判函数判断己方胜利的局面。或者，对于当前局面，己方至少存在一种必胜动作，使得接下来产生的局面中，对方执行任意动作产生的新局面，都为己方必胜局面。
己方必胜动作：执行该动作后，产生己方必胜局面的动作
因此，在搜索过程中：
1.对于轮到己方下棋的局面，只要搜索到一个己方必胜动作即可返回True, 否则返回False。
2.对于轮到敌方下棋的局面，只要搜索到一个敌方必胜动作即可返回False, 否则返回True。
代码如下：
int tree(int player, int depth) //与或树搜索，己方1，对方-1，返回1说明当前局面为必胜局面
{
if (depth == 0) //达到深度，默当前局面己方没赢
{
return -1;
}
else
{
for (int i = MIN; i < MAX; i++) //对每个位置
{
for (int j = MIN; j < MAX; j++)
{
if (p[i][j].state == 0) //当前位置为空，下面对偏僻位置进行剪枝
{
if (p[i - 1][j - 1].state != 0 || p[i - 1][j].state != 0 || p[i - 1][j + 1].state != 0 || p[i][j + 1].state != 0 ||
p[i + 1][j + 1].state != 0 || p[i + 1][j].state != 0 || p[i + 1][j - 1].state != 0 || p[i][j - 1].state != 0)
{
p[i][j].state = player; //在当前位置下棋
//如果当前局面对于当前玩家，为当前玩家必胜局面
if (win(i, j, player) == player || tree(-player, depth - 1) == player) {
p[i][j].state = 0; //撤回
return player; //对于己方，返回Ture。对于敌方，返回False
}
p[i][j].state = 0; //撤回
}
}
}
}
return -player; //一个都必胜动作都搜索不到
}
}?
?
? ? ? ?PNS可看作为利用了历史搜索信息的与或树搜索，其利用历史信息，使得当前的搜索方向朝着最有可能证实或者证否的方向。
在该算法中，对于每一个局面节点，我们都为其设置两个属性值：
proof num: 证实数，证明该局面为己方必胜局面，所需要证明的局面数。
若轮到己方下棋，取值为子局面中最小的proof num值。
若轮到敌方下棋，取值为子局面中proof num值的和。
disproof num: 证否数，证明该局面不为己方必胜局面，所需要证明的局面数。
若轮到敌方下棋，取值为子局面中最小的proof num值。
若轮到己方下棋，取值为子局面中proof num值的和。
举个栗子：对于轮到己方下棋的某局面，其有10个子局面。
要证明该该局面己方必胜，只需要证明其子局面中的一个为己方必胜局面即可，因此节点proof num = 1。
要证明该局面不为己方必胜，需证明其10个子局面都不为己方必胜，因此节点disproof num = 10
?
搜索方式改变不了局面性质，我们的目的是尽可能快速结束搜索，在我们搜索的时候：
对于轮到己方玩家的局面，应朝着proof num最小的子局面搜索，因为其最容易证实，且当前局面仅需有一个子局面被证实自己就能被证实，而证否需要证否全部子局面。
对于轮到敌方玩家的局面，应朝着disproof num最小的子局面搜索，因为其最容易证否，且当前局面仅需有一个子局面被证否自己就能被证否，而证实需要证实全部子局面。
?
def prove(v, times):
for i in range(times): # 在计算开销预算内
if v.proof == 0:
return True # 证实
elif v.disproof == 0:
return False # 证否
else:
grow(v) # 生长
return False
def grow(v):
while v.children != []: # 若已扩展，获取子节点中，证据数最少，且未被证明(不为0)，的子节点
v = min([v1 for v1 in v.children if v1.proof != 0 and v1.disproof != 0], key=lambda v1: v1.proof if v.player == 1 else v1.disproof)
expand(v)
backup(v)
def expand(v):
for action in v.action: # 扩展一层子节点，（不是一个）
v1 = v.do_action(action)
v.children.append(v1)
def backup(v): # 反向传播，更新值
while v is not None: # 未到根节点
v.proof = min(v.children, key=lambda v1: v1.proof).proof if v.player == 1 else sum(v1.proof for v1 in v.children)
v.disproof = sum(v1.disproof for v1 in v.children) if v.player == 1 else min(v.children, key=lambda v1: v1.disproof).disproof
v = v.parent?
?
?