解决围棋中的获胜概率问题外文翻译资料

解决围棋中的获胜概率问题

摘要—围棋比赛中需要进行位置分析，对于职业棋手或者围棋程序都是如此。目前的围棋程序把地域分数作为其位置分析的主要标准，这是一种有缺陷的方法。本文提出了一种计算获胜概率的方法，并用遗传算法进一步优化了模型参数。通过这种方法，可以得到基于不同水平的各种获胜概率模型。经过测试，该模型的精度可以应用于计算机围棋的中局和残局模块。

关键词—获胜概率，遗传算法，围棋

1. 导言1

计算机游戏作为人工智能研究的一个重要分支，也是人工智能发展水平的一个重要标志。计算机围棋是计算机游戏中最具挑战性的分支之一[1]。由于搜索空间巨大，在下棋程序中应用的穷举研究在这里几乎行不通。因此，借鉴人类游戏者的思维方法设计的启发式搜索算法是提高计算机程序水平的一种可行途径[2]。目前，围棋程序通常以领土来分析和判断形势，对最佳走法的评价取决于它能赢得的最大化的领土点数[3][4]。然而，在比赛中，比赛的输赢与你的输赢无关，即即使你比对手多一分，也是一场胜利。

职业棋手一般都是以赢得整局比赛为目的来思考走法，而不是尽可能多地赢得点数，但基于领土的围棋程序往往会犯下即使在安全领先的情况下也要捕捉对手不安全组的战略错误，因为根据它的计算，捕捉可以获得更多的好处。

获胜概率模型曾应用于计算机围棋程序中局，取得了良好的运行效果[5]。在此基础上，本文

978-1-4244-5848-6/10/$ 26.00 2010 IEEE

描述了一种计算围棋获胜概率的计算机解决方案。该算法基于引导点和围棋态势，结合遗传算法，优化模型参数。根据两个玩家的水平，最终得到两组最优的获胜概率模型参数。

1. 获胜概率
2. 获胜概率的显著性

向职业棋手学习是提高电脑游戏围棋水平的有效途径[6]。一个职业球员对整个局势做出判断，并在此基础上决定下一步行动。如果我们在围棋比赛中领先，我们应该让每个小组都稳定下来，战场更少，以便将优势保持到比赛结束。如果形势对我们不利，就需要一张王牌来打乱对手的战略，进行最后一击。因此，位置分析被引入到计算机围棋程序中。在每一步棋之前，都要计算获胜概率，从而确定量化值K，作为动态调整攻防棋步的参考。在此基础上，决定了最佳的行动。(至于如何确定量化值K并搜索最佳走法，请参考[5])

1. 获胜概率的计算

一般来说，获胜概率与领先点数和围棋比赛进度这两个参数成正比，即:在围棋比赛领先点数相同的情况下，比赛越接近尾声，获胜概率越大；在游戏进度相同的情况下，领先点数越多，获胜概率越大。因此，我们将分别研究它们。(为方便起见，假设我们取黑石。如果选择白石，计算是相同的。)

• 1. 引导点:引导点可以分为两部分:
     1. 领先的领土点数:在真实游戏中，领土点数在开局阶段结束时计算；

黑色白色

结论是:考虑到科米

当局部战斗结束后，下一场

要点M 一世一世n一世

领土之争即将开始；当去的情况进入最后阶段。领土点数被计算出来，作为后期游戏策略的参考。通过领地点数的计算模块，

是待定参数，k代表komi点)

• 1. 围棋比赛进度:由于一场围棋比赛的随机性很高，一场比赛的围棋总走法数从50步到400步不等，围棋比赛很难判断

黑棋k

和

每一方的领土可以是白色的

基于移动次数的进度。[9]建议

获得差值黑棋与白棋，即黑石的领先点(这里差值可以是负号，这意味着我们落后的点。)

1. 在围棋比赛中，除了地盘，一个团体的实力也能极大地影响获胜概率。以下三个方面进行判断，以确定强或

前沿空间点辅助计算方法。从棋步数(T)和前沿空间点数来看，还是不太好描述游戏进度。因此，本文提出了未定区域的概念。游戏棋盘上仍未解决并需要进一步战斗的区域称为未决区域。

因为很难表示未决定的区域，所以我们使用

弱势群体对积分的影响。

• 强组和莫约的点数是由围棋格局决定的:一些常见的围棋格局，可以

间接计算:u 361t(m是未定面积值。

黑人·姆怀特

)，哪个

被保存在图案库中(从图1可以看出，黑色组有15个点[7])；如果在真实的游戏中遇到类似的围棋模式，则

获胜概率P的估计过程是

如图2所示。

U

值可以直接赋给

开始位置分析。在模块中，以下几点

• 1. 如果(

T

• 5)

····k

1.if ( 0.5  ( 1 1 1 ) *  )  1

每边都记为m和m，U 一



差值m mblack

黑色

• m white

白色

然后P  1

( C 1)

一

2.else if (0.5  (  1米  1 I   1米 k ) *  )  0

然后P  0

3.其他

U 一

( C 1)

 1

然后P  0.5  (  1米  1 I   1米 k ) * 

U 一

• 1. else i f ( 2 大学分校5)

T

( C1)

 1

图一。一个模式的例子

1.if ( 0.5  (  2米  2 I   2米  2 n  k ) *  )  1

• • 一个群体的实力对积分有影响:除了模式，我们还用群体影响值来表示实力。本文采用

然后P  1

1. 否则如果(0.5 (

U 2

( C 2)



2

 2米  2 I   2米  2 n  k

(大学c)



) *  2 )  0

[8]的影响模块，求出Iblack和

Iwhite，它表示未决定区域上每一方的群组影响值的总和

2

2

然后P  0

1. 其他

然后P  0.5  (  2米  2 I   2米  2 n  k ) * 

U 2

差值

i·伊布拉克

• 爱蓓洁

。

如果我们用

( C 2)

 2

I归一化方法

，我们可以得到:

3.其他

I i/64，这是黑白面的影响值差。

• • 弱势群体的负分:当弱势群体想要获得更多分数时，对手会获得更多分数

1.如果(0.5  (  3米  3我 k ) *  )  1

U 3

( C 3)

 3

然后P  1

2.else if (0.5  (  3 M   3 I  k ) *  )  0

逃跑或者未来生存。通过弱者

分组减分计算模块，通过判断石头的数量、自由度、眼睛、形状的强弱

然后P  0

3.其他

U 3

( C 3)



3

组，每个弱组的减分为

然后P  0.5 (

 3 M   3 I  k

) * 

侧面黑色

和白色

可以得到，区别

U 3

( C 3)

 3

本文得到了上海市科委重点项目(编号:075115002)的资助

图二。围棋获胜概率模型

获胜概率与棋手的围棋水平密切相关，因此主观性很强。因此，在设置参数时，需要根据不同的围棋水平对模型参数进行优化。

优化意味着在一个问题的许多可能的解决方案中找到最佳或准最佳的解决方案。优化获胜概率模型中的参数，是指根据不同的围棋水平形成参数组合，以便更准确地评估获胜概率，从而调整进攻或防守棋步的权重，最终确定最佳棋步。

本文首次将职业棋手的围棋水平作为评价标准。我们邀请了专业玩家对游戏进行评估，从而得出基于专业水平的获胜概率模型。同时，世界范围内的顶级围棋程序是2 kyu左右，并且假设相当于1 dan的围棋程序级别将在两年内问世[10]。因此，我们前瞻性地优化了基于1 dan水平的获胜概率模型的参数。

优化方法将在下一章中应用。

1. 最佳化
2. 遗传算法

我们采用遗传算法来优化参数。遗传算法(Genetic Algorithm，GA)是一种模拟生物进化过程中达尔文遗传选择和自然淘汰的计算模块。通过模拟自然进化来解决优化问题是一种有效的方法。它由密歇根大学的J. Holland教授于1975年首次提出，现已广泛应用于人工智能和机器学习等领域。

1. 适应度函数和编码方案

从图2可以推断出，优化模型的获胜概率可以由(1)表示，

n

总共有1448场比赛。首先，职业玩家在每场游戏中选择两到三个关键的游戏情境，这样就选择了3582个游戏情境；然后随机选取2507个游戏情境，用于优化参数；其他1075种游戏情况作为参数优化后的模型测试。

为了解决遗传算法中控制参数和遗传算子的组合优化问题，引入了两级遗传算法模型。

二级遗传算法模型是在原模型的基础上引入了二级遗传算法，并且一级遗传算法和二级遗传算法相互嵌入，用于实现获胜概率模型的参数优化。其中，遗传算法应用于获胜概率模型的参数优化，算法的执行策略由二级(自适应)遗传算法决定；次级遗传算法用于初级遗传算法中控制参数和遗传算子的组合优化。

与一般的遗传算法模型相比，两级遗传算法模型可以获得更好的搜索结果。虽然两级GA模型的嵌套关系运算使得迭代计算增加了几十倍[14]，但由于没有实时性要求，这是可以合理接受的。

表一。围棋获胜概率模型I的优化结果

参数	优化价值	参数	优化价值
1	0.8133	2	0.1526
1	0.3206	2	6.735
1	0.950 剩余内容已隐藏，支付完成后下载完整资料 英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料 资料编号：[594045]，资料为PDF文档或Word文档，PDF文档可免费转换为Word