计算机博弈求解算法

发布时间:2024年01月14日

1.与或树搜索

? ? ? ?与或树搜索可用于判断当前局面是不是对于自己的必胜局面,因此也可以用于寻找当前局面的必胜动作,适用于计算机博弈求解和残局搜索。

在此,粗略作出一些定义:

己方必胜局面:裁判函数判断己方胜利的局面。或者,对于当前局面,己方至少存在一种必胜动作,使得接下来产生的局面中,对方执行任意动作产生的新局面,都为己方必胜局面。

己方必胜动作:执行该动作后,产生己方必胜局面的动作

因此,在搜索过程中:

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;  //一个都必胜动作都搜索不到
	}
}

?

?

2.证据计数搜索(PNS)

? ? ? ?PNS可看作为利用了历史搜索信息的与或树搜索,其利用历史信息,使得当前的搜索方向朝着最有可能证实或者证否的方向。

2.1数据结构

在该算法中,对于每一个局面节点,我们都为其设置两个属性值:

proof num: 证实数,证明该局面为己方必胜局面,所需要证明的局面数。

若轮到己方下棋,取值为子局面中最小的proof num值。

若轮到敌方下棋,取值为子局面中proof num值的和。

disproof num: 证否数,证明该局面不为己方必胜局面,所需要证明的局面数。

若轮到敌方下棋,取值为子局面中最小的proof num值。

若轮到己方下棋,取值为子局面中proof num值的和。

举个栗子:对于轮到己方下棋的某局面,其有10个子局面。

要证明该该局面己方必胜,只需要证明其子局面中的一个为己方必胜局面即可,因此节点proof num = 1。

要证明该局面不为己方必胜,需证明其10个子局面都不为己方必胜,因此节点disproof num = 10

?

2.2搜索方法

搜索方式改变不了局面性质,我们的目的是尽可能快速结束搜索,在我们搜索的时候:

对于轮到己方玩家的局面,应朝着proof num最小的子局面搜索,因为其最容易证实,且当前局面仅需有一个子局面被证实自己就能被证实,而证否需要证否全部子局面。

对于轮到敌方玩家的局面,应朝着disproof num最小的子局面搜索,因为其最容易证否,且当前局面仅需有一个子局面被证否自己就能被证否,而证实需要证实全部子局面。

?

2.3代码实现

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

?

?

?

文章来源:https://blog.csdn.net/qq_63670969/article/details/135570001
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。