覆面算法

Ⅰ 软件测试的方法一共有几种

1、从是否关心内部结构来看

（1）白盒测试：又称为结构测试或逻辑驱动测试，是一种按照程序内部逻辑结构和编码结构，设计测试数据并完成测试的一种测试方法。

（2）黑盒测试：又称为数据驱动测试，把测试对象当做看不见的黑盒，在完全不考虑程序内部结构和处理过程的情况下，测试者仅依据程序功能的需求规范考虑，确定测试用例和推断测试结果的正确性，它是站在使用软件或程序的角度，从输入数据与输出数据的对应关系出发进行的测试。

（3）灰盒测试：是一种综合测试法，它将“黑盒”测试与“白盒”测试结合在一起，是基于程序运行时的外部表现又结合内部逻辑结构来设计用例，执行程序并采集路径执行信息和外部用户接口结果的测试技术。

2、从是否执行代码看

（1）静态测试：指不运行被测程序本身，仅通过分析或检查源程序的语法、结构、过程、接口等来检查程序的正确性。

(2)动态测试：是指通过运行被测程序，检查运行结果与预期结果的差异，并分析运行效率、正确性和健壮性等性能指标。

3、从开发过程级别看

（1）单元测试：又称模块测试，是针对软件设计的最小单位----程序模块或功能模块，进行正确性检验的测试工作。其目的在于检验程序各模块是否存在各种差错，是否能正确地实现了其功能，满足其性能和接口要求。

(2)集成测试：又叫组装测试或联合，是单元测试的多级扩展，是在单元测试的基础上进行的一种有序测试。旨在检验软件单元之间的接口关系，以期望通过测试发现各软件单元接口之间存在的问题，最终把经过测试的单元组成符合设计要求的软件。

（3）系统测试：是为判断系统是否符合要求而对集成的软、硬件系统进行的测试活动、它是将已经集成好的软件系统，作为基于整个计算机系统的一个元素，与计算机硬件、外设、某些支持软件、人员、数据等其他系统元素结合在一起，在实际运行环境下，对计算机系统进行一系列的组装测试和确认测试。

在系统测试中，对于具体的测试类型有：

（1）功能测试：对软件需求规格说明书中的功能需求逐项进行的测试，以验证功能是否满足要求。

（2）性能测试：对软件需求规格说明书的功能需求逐项进行的测试，以验证功能是否满足要求。

（3）接口测试：对软件需求规格说明中的接口需求逐项进行的测试。

（4）人机交互界面测试：对所有人机交互界面提供的操作和显示界面进行的测试，以检验是否满足用户的需求。

（5）强度测试：强制软件运行在异常乃至发生故障的情况下（设计的极限状态到超出极限），验证软件可以运行到何种程序的测试。

（6）余量测试：对软件是否达到规格说明中要求的余量的测试。

（7）安全性测试：检验软件中已存在的安全性、安全保密性措施是否有效的测试，

（8）可靠性测试：在真实的或仿真的环境中，为做出软件可靠性估计而对软件进行的功能（其输入覆盖和环境覆盖一般大于普通的功能测试）

（9）恢复性测试：对有恢复或重置功能的软件的每一类导致恢复或重置的情况，逐一进行的测试。

（10）边界测试：对软件处在边界或端点情况下运行状态的测试。

（11）数据处理测试：对完成专门数据处理功能所进行的测试。

（12）安装性测试：对安装过程是否符合安装规程的测试，以发现安装过程中的错误。

（13）容量测试：检验软件的能力最高能达到什么程度的测试。

（14）互操作性测试：为验证不同软件之间的互操作能力而进行的测试。

（15）敏感性测试：为发现在有效输入类中可能引起某种不稳定性或不正常处理的某些数据的组合而进行的测试。

（16）标准符合性测试：验证软件与相关国家标准或规范（如军用标准、国家标准、行业标准及国际标准）一致性的测试。

（17）兼容性测试：验证软件在规定条件下与若干个实体共同使用或实现数据格式转换时能满足有关要求能力的测试。

（18）中文本地化测试：验证软件在不降低原有能力的条件下，处理中文能力的测试。

4、从执行过程是否需要人工干预来看

（1）手工测试：就是测试人员按照事先为覆盖被测软件需求而编写的测试用例，根据测试大纲中所描述的测试步骤和方法，手工地一个一个地输 入执行，包括与被测软件进行交互（如输入测试数据、记录测试结果等），然后观察测试结果，看被测程序是否存在问题，或在执行过程中是否会有一场发生，属于比较原始但是必须执行的一个步骤。

（2）自动化测试：实际上是将大量的重复性的测试工作交给计算机去完成，通常是使用自动化测试工具来模拟手动测试步骤，执行用某种程序设计语言编写的过程（全自动测试就是指在自动测试过程中，不需要人工干预，由程序自动完成测试的全过程；半自动测试就是指在自动测试过程中，需要手动输入测试用例或选择测试路径，再由自动测试程序按照人工指定的要求完成自动测试）

5、从测试实施组织看

（1）开发测试：开发人员进行的测试

（2）用户测试：用户方进行的测试

（3）第三方测试：有别于开发人员或用户进行的测试，由专业的第三方承担的测试，目的是为了保证测试工作的客观性

6、从测试所处的环境看

（1）阿尔法测试：是由一个用户在开发环境下进行的测试，也可以是公司内部的用户在模拟实际操作环境下进行的测试

（2）贝塔测试：是用户公司组织各方面的典型终端用户在日常工作中实际使用贝塔版本，并要求用户报告

(1)覆面算法扩展阅读

软件测试的内容：

1 得到需求、功能设计、内部设计说书和其他必要的文档

2 得到预算和进度要求

3 确定与项目有关的人员和他们的责任、对报告的要求、所需的标准和过程 ( 例如发行过程、变更过程、等等 )

4 确定应用软件的高风险范围，建立优先级、确定测试所涉及的范围和限制

5 确定测试的步骤和方法 ── 部件、集成、功能、系统、负载、可用性等各种测试

6 确定对测试环境的要求 ( 硬件、软件、通信等 )

7 确定所需的测试用具 (testware) ，包括记录 / 回放工具、覆盖分析、测试跟踪、问题 / 错误跟踪、等等

8 确定对测试的输入数据的要求

9 分配任务和任务负责人，以及所需的劳动力

10 设立大致的时间表、期限、和里程碑

11 确定输入环境的类别、边界值分析、错误类别

12 准备测试计划文件和对计划进行必要的回顾

13 准备白盒测试案例

14 对测试案例进行必要的回顾 / 调查 / 计划

15 准备测试环境和测试用具，得到必需的用户手册 / 参考文件 / 结构指南 / 安装指南，建立测试跟踪过程，建立日志和档案、建立或得到测试输入数据

16 得到并安装软件版本

17 进行测试

18 评估和报告结果

19 跟踪问题 / 错误，并解决它

20 如果有必要，重新进行测试

21 在整个生命周期里维护和修改测试计划、测试案例、测试环境、和测试用具

Ⅱ 游戏攻击判定的三种模式

转自：http://www.gameres.com/677620.html

攻击判定流程几乎是所有包含战斗玩法的游戏都无法绕过的一块内容，常见的攻击判定流程有瀑布算法、圆桌算法以及混合算法三种。本文简述了这三种判定流程的特征，以实例对比分析了瀑布算法与圆桌算法各自的优点，以期为后续其他战斗数值设计内容的论述提供一定的基础。

攻击判定流程概述

自此开始正文内容的叙述——让我们直接代入一个实例：

在一款游戏中，攻击方有命中率和暴击率两个攻击属性，而防守方有闪避率、招架率和格挡率三个防御属性。于是相应的，一次攻击有可能产生6种判定结果：未命中、普通命中、闪避、招架、格挡和暴击。当采用不同的判定流程进行攻击结算时，6种判定结果出现的频率会截然不同。

1.  瀑布算法

顾名思义，在瀑布算法中，各事件的判定顺序如同瀑布一般自上而下。如果“水流”在某个位置被截断，则后面的流程都将不再继续进行。据我所知，瀑布算法是大多数游戏所采用的攻击判定算法。

上述实例若采用瀑布算法，则会以如下方式进行判定：

先判定攻方是否命中

再判定是否被守方闪避

再判定是否被守方招架

再判断是否被守方格挡

最后判定该次攻击是否为暴击

瀑布算法流程图

由此我们可以得出：

瀑布算法特征1：多次掷骰，一次掷骰只判定单个事件的发生与否

瀑布算法特征2：后置判定依赖于前置判定的通过

注：有的游戏会将命中和闪避合并在一次掷骰中判定，这意味着将攻方命中率与守方闪避率合并计算出实际击中概率后再进行掷骰判定，仍是瀑布算法

我们再代入一些具体的数值，设攻守双方角色的面板属性如下：

攻方命中率=90%

攻方暴击率=25%

守方闪避率=20%

守方招架率=15%

守方格挡率=30%

按照上述的流程判定，6种判定结果将会按如下的概率分布：

实际未命中概率=1-命中率=1-90%=10%

实际闪避概率=命中率*闪避率=90%*20%=18%

实际招架概率=命中率*（1-闪避率）*招架率=90%*(1-20%）*15%=10.8%

实际格挡概率=命中率*（1-闪避率）*（1-招架率）*格挡率=90%*(1-20%)*(1-15%)*30%=18.36%

实际暴击概率=命中率*（1-闪避率）*（1-招架率）*（1-格挡率）*暴击率=90%*(1-20%)*(1-15%)*(1-30%)*25%=10.71%

实际普通命中概率=命中率*（1-闪避率）*（1-招架率）*（1-格挡率）*（1-暴击率）=90%*(1-20%)*(1-15%)*(1-30%)*(1-25%)=32.13%

瀑布算法的判定结果分布

由此我们可以得出：

l 瀑布算法特征3：各事件出现的概率符合经典的概率计算方法

l 瀑布算法特征4：掷骰轮次越偏后的属性衰减程度越大，但不会出现无效的属性

2.圆桌算法

将所有可能出现的事件集合抽象成一个圆桌桌面，便是圆桌算法这一称呼的由来。圆桌算法的实质，是将所有可能发生的事件状态按优先级依次放上桌面，直至所有事件被放完或桌面被填满。圆桌算法正是史诗级巨作魔兽世界中所采用的算法。据笔者了解，使用该算法的游戏并不多见，但即便仅魔兽世界这一款，已足以使这种算法成为永恒的经典~

上述实例若采用圆桌算法，则会用一次掷骰判定该次攻击的结果。

圆桌算法流程图

圆桌算法的操作步骤可以归纳为：

（1）攻方角色的命中率决定圆桌桌面的大小

（2）将各个事件状态按优先级依次放上桌面，直至所有的事件均放置完或桌面被填满

（3）若桌面还未填满，则用普通命中填满空桌面

将先前设定的数值代入，6种判定结果将会按如下的概率分布：

实际未命中概率=10%

实际闪避概率=20%

实际招架概率=15%

实际格挡概率=30%

实际暴击概率=25%

实际普通命中概率=90%-实际闪避概率-实际招架概率-实际格挡概率-实际暴击概率=90%-20%-15%-30%-25%=0%

注：在上述计算中，优先级按如下排序：闪避>招架>格挡>暴击>普通命中

圆桌算法的判定结果分布

可以看出，由于普通命中的优先级最低，所以它被完全挤出了桌面。这意味着，若攻守双方以此数值模型进行对决，则攻击方的攻击结果中将不存在普通命中。

由此我们可以得出：

圆桌算法特征1：一次掷骰即得出该次攻击的判定结果

圆桌算法特征2：事件有优先级，圆桌放满后优先级低的事件将被挤出桌面。这意味着那部分溢出的属性将不再生效

圆桌算法特征3：圆桌内的各事件出现概率不会衰减，只要优先级低的属性没有被挤出圆桌，各种事件的实际发生概率就与面板属性数值吻合

3. 混合算法

这是一种先判定攻方事件，再判定守方事件的判定流程。笔者曾在一篇帖子中看到过这样判定流程，不确定是否有实际的游戏应用，故仅在此做一些简单的理论分析。

混合算法在单方事件的判定中采用圆桌算法，即：

攻方判定结果：普通命中OR未命中OR暴击

守方判定结果：闪避OR招架OR格挡OR被命中

混合算法流程图

注：上面这个图仅作示意之用，从流程图的角度来看可能不太严谨

将先前设定的数值代入，6种判定结果将会按如下的概率分布：

实际未命中概率=10%

实际闪避概率=攻方命中率*闪避率=90%*20%=18%

实际招架概率=攻方命中率*招架率=90%*15%=13.5%

实际格挡概率=攻方命中率*格挡率=90%*30%=27%

实际暴击概率=攻方暴击率*敌方被命中概率=25%*(1-20%-15%-30%)=8.75%

实际普通命中概率=攻方普通命中概率*敌方被命中概率=(90%-25%)*(1-20%-15%-30%)=22.75%

混合算法的判定结果分布

由此我们可以得出：

混合算法特征1：先判定攻方事件，再判定守方事件，共进行两次掷骰

混合算法特征2：先在单方事件的判定中采用圆桌算法，再用瀑布算法串联攻守双方事件

混合算法特征3：会产生并发动作，例如暴击被闪避等

注：这也正是实际暴击率较低原因所在

瀑布算法与圆桌算法的特性对比

在上一块内容的铺垫之下，我们不妨继续以魔兽世界中的攻击判定流程设计实例作为切入点，对比分析一下圆桌算法与瀑布算法各自的特性。

（1）面板属性传递信息的直观性

瀑布：由于各属性在判定流程上的生效时间有先后之分，所以各属性的实际效用与面板显示的不符。

圆桌：由于属性的判定没有先后之分，只要没有属性被挤出圆桌，则所有属性的实际效用与面板显示的相当。

这里可以看出圆桌算法的优点：

属性的实际效用与面板显示相符显然更易于普通玩家的理解，便于玩家掌握自身的战力情况。

（2）属性的价值

瀑布：掷骰轮次越偏后的属性衰减程度越大，但所有的属性均会生效。

圆桌：只要没有属性被挤出圆桌，则不存在属性效用的衰减。

这里可以看出圆桌算法的优点：

由于不存在判定流程上的先后，所以各属性的实际价值会比较接近，一般不会出现玩家堆了某个判定流程靠后的属性结果很废的情况。

同样也可以看出其缺点：

一旦有属性溢出，则该部分属性的效用为0，完全没有价值。

（3）相同面板数值下的生存能力

圆桌：在面板数值相同的情况下，魔兽世界用圆桌算法大大提高了坦克角色的生存能力，使得他们可以应对来自首领怪的超高攻击，匹配大型团队副本的玩法设计。

瀑布算法下，免伤概率=18%+10.8%+18.36%=47.16%

圆桌算法下，免伤概率=20%+15%+30%=65%

传统的概率为相乘关系，圆桌为相加关系，后者的概率总和要大的多

并且，当防御职业将三维堆至一个阈值（70%）后，配合技能可达100%的免伤覆盖，将命中和暴击全部挤出桌面，从而衍生出特定的玩法（70级年代伊利丹的剪切技能）。

瀑布：相同的面板数值在瀑布算法的框架下，免伤概率相较于圆桌算法要低得多。换言之，角色达到相同的有效生命值，所需的免伤属性要高得多。

这里可以看出：

在圆桌算法的框架之下，属性投放若是脱离了控制超过了阈值，将对平衡性产生较大的冲击（70级的盗贼单刷格鲁尔——当然在暴雪光环的作用下，玩家会认为这是精妙的设计~）。

在国产游戏收入导向的大环境下，设计者是否能顶住收入压力，严守属性投放的极值不越界，是值得慎思的问题。采用瀑布算法，能有更大的数值空间用于能力投放，更为适合现阶段的市场环境。

（4）运算量

瀑布：多次掷骰

圆桌：单次掷骰

显而易见：

掷骰次数越多，运算量越大。圆桌相较于瀑布，有着相对较小的运算量。简单即是美。

注：除魔兽世界外，《冒险与挖矿》的技能施放也采用了圆桌算法，大大简化了技能施放的判定流程。可以想象一下，一次攻击至多发动一个技能。而每一次攻击，一个队伍中有几十个角色的技能施放需要判定，如果采用瀑布算法，将产生多大的运算量。

思考与总结

对战斗数值的研究，应该基于理论推导而归于实践应用。毕竟游戏数值设计不是做数学研究，其本质应是一种体验设计。最后希望交流的是笔者个人对于这两种算法的一些理解。

（1）不同的攻击判定流程会向玩家传达不同的战斗感受

究其本质，不同的攻击判定流程，影响着一场战斗中的各种攻击判定结果将以何种概率分布出现。

假设在一款游戏中，闪避率的投放上限是30%，暴击率的投放上限是40%，命中率的投放上限是100%。瀑布算法下，出现闪避、暴击和普通命中的概率是30%、28%和42%；圆桌算法下，则为30%、40%和30%。这两种不同的概率分布，必然会带给玩家不同的战斗体验，但在缺少其他条件的情况下，并不能判断孰优孰劣。

使战斗体验匹配游戏的核心玩法，使属性投放的极限值能满足游戏的商业化需要，是设计攻击判定流程时首先要考虑的。

注：甚至于部分竞技游戏强调公平性，将暴击做成了伪随机。

使用瀑布算法，则不应该设计种类繁多的事件状态

若是仿照魔兽世界的做法设计一连串的事件状态（未命中、闪避、招架、格挡、暴击、普通命中、偏斜、碾压），非但运算繁杂，而且后置判定的属性衰减幅度较大，效果极不明显。这种隐晦的设计将不易传达，同时还会影响玩家的游戏感受（某个判定流程靠后的属性堆得很高结果却没用）。

使用圆桌算法，则应该严守属性投放的上限，防止平衡崩坏的情况发生

需要澄清的是，并不是说使用瀑布算法就可以无限投放数值，而是说，相较于瀑布算法，圆桌算法的属性投放上限会低很多（免伤概率的相加与相乘）

（2）不同的攻击判定流程将影响有效生命EHP和有效攻击EDPS的表达式

几乎每个数值策划都会将角色的属性转化为EHP和EDPS以衡量其的战斗能力，但曾见过不少人对所有的游戏都用统一的EHP、EDPS表达式进行分析模拟。这种偏差较大的模拟方式必然会影响体验设计的精准性。在不同的攻击判定流程之下，EHP与EDPS有着截然不同的表达式，举例说明如下。

瀑布算法下：

若命中闪避分两次判定：

EHP=HP/(1-免伤率)/(1-闪避率)/(1-招架率)

EDPS=DPS*命中率*[1+暴击率*(暴击伤害倍率-1)]

若命中闪避合并判定：

EHP=HP/(1-免伤率)/(命中率-闪避率)/(1-招架率)

EDPS=DPS*(1+暴击率*(暴击伤害倍率-1))

圆桌算法下：

EHP=HP/(1-免伤率)/(1-闪避率-招架率)

EDPS=DPS*[命中率-敌方闪避率-敌方招架率+暴击率*(暴击伤害倍率-1)]

注：闪避、招架>暴击>普通命中，且各状态发生概率之和未超过圆桌大小

混合算法下：

EHP=HP/(1-免伤率)/(1-闪避率-招架率)

EDPS=DPS*[命中率+暴击率*(暴击伤害倍率-1)]

可能有人会觉得：模拟得这么准又有什么卵用，数值平衡最后还不是靠调？诚然，在数值设计领域，确实有名言曰：数值平衡是调出来的。但在笔者看来，调节应该建立在正确的理论推导的基础之上。依靠调节来掩盖数值模型的错误设计，是本末倒置的行为。即便达到了所谓的平衡，也不过是扭曲的平衡，会为后续版本的迭代埋下隐患。

写在最后

市面上的大多数游戏，都不会设计复杂繁多的攻击事件，且基本采用瀑布算法。如此看来，攻击判定流程的设计十分简单。那么为什么要大费周章地将简单问题复杂化呢？

爱因斯坦曾说过：Everythingmust be made as simple as possible, but not one bit simpler——凡事应该力求简单，但不能过于简单。从了解一种数值设计方法到理解如此设计的目的，从模仿成功游戏的数值设计到理解其设计的内在意义，这是每个数值策划成长的必经之路。

从全盘照搬一种数值体系到能够融会贯通并根据实际情况灵活运用，这是一条并不好走的路。知其然，也应知其所以然——这是一个入行一年有余的新人的一点感悟。

免责申明：

1.笔者无法保证本文所用词汇的普适性，能力所限，请多包涵~

2.不保证文中魔兽世界实例中的设定均与原作完全相符。但即便不相符，也不会影响圆桌理论的推

Ⅲ 怎么求最小面积的三角形覆盖平面上的点集的算法

#include <stdio.h>
#include <math.h>
// 输入最多的点数目
#define MAX_POINTS_AMOUNT 100

struct Point
{
double x,y;
};
// 求点 p1, p2 的距离
double distance(struct Point p1, struct Point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
// 求 a, b, c 中的最大值
double max(double a, double b, double c)
{
return a>=b && a>=c
? a
: b>=a && b>=c
? b
: c;
}

// 判断长度为 a, b, c 的 3条线段能否组成三角形
// 判断依据为：至少有一条边的长度，大于另两条边的长度差（绝对值），小于另两条边的长度和
int canMakeTriangle(double a, double b, double c)
{
return a>fabs(b-c) && a<(b+c) ||
b>fabs(a-c) && b<(a+c) ||
c>fabs(a-b) && c<(a+b);
}

// 判断长度为 a, b, c 的 3条线段能否组成锐角三角形
// 判断依据：根据余弦定理，求出 3 个角的余弦值
int canMakeAcuteTriangle(double a, double b, double c)
{
unsigned int i;
double cos_a, cos_b ,cos_c;
if(canMakeTriangle(a, b, c))
{
cos_a = (b*b + c*c - a*a)/(2*b*c);
cos_b = (a*a + c*c - b*b)/(2*a*c);
cos_c = (a*a + b*b - c*c)/(2*a*b);
return cos_a>0 && cos_b>0 && cos_c>0;
}
return 0;
}

/* 求覆盖 n 个点 points 的最小圆的半径
算法：
只要分别求出所有3点组合覆盖的最小圆，取其中半径最大者即为所求。
确定覆盖3点的最小圆的步骤可以如下：
(1) 若3点组成直角或钝角三角形，或3点共线，此时，最小圆的半径为三边中最长边的一半。
(2) 否则，3点组成锐角三角形，最小圆为3点的外接圆。
(3) 外接圆半径计算方法：
(a) 若3点构成一个三角形(即3点不共线)，
并设3点的坐标为 (x1,y1)，(x2,y2)，(x3,y3)，求出两点(x1,y1)和(x2,y2)之间的距离
L1=sqrt((x1-x2)^2+(y1-y2)^2), 同样求出(x1,y1)和(x3,y3)之间的距离L2，
以及(x2,y2)和(x3,y3)之间的距离L3。
(b) 求出三角形半周长L=(L1+L2+L3)/2以及面积S=sqrt(L*(L-L1)*(L-L2)*(L-L3))。
(c) 根据公式4SR=L1*L2*L3，求外接圆半径R=L1*L2*L3/(4*S)。
参数：
n ： 点数目
points ： n 个点的坐标
start ： 递归参数。表示当前从在 n 个点的第 start 个开始选取。初始值为 0。
selectPointsAmount ： 递归参数。表示当前已经选好了的点数。最多为 3 个。初始值为 0。
selectPoints : 递归参数。表示当前已经选好了的点的坐标数组。初始值为 NULL。
返回：
覆盖 n 个点 points 的最小圆的半径。

*/
double minCircleRadius(unsigned int n, struct Point points[],
unsigned int start, unsigned int selectPointsAmount, struct Point selectPoints[])
{
if(n <= 1)
return 0.0;
if(n == 2)
return distance(points[0], points[1])/2.0;
else
{
if(selectPointsAmount == 3)
{// 已经选好了 3 个点，求能覆盖它们的最小圆的半径

double L1 = distance(selectPoints[0], selectPoints[1]);
double L2 = distance(selectPoints[0], selectPoints[2]);
double L3 = distance(selectPoints[1], selectPoints[2]);
double L = (L1 + L2 + L3)/2.0;
double S = sqrt(L*(L-L1)*(L-L2)*(L-L3));
if(canMakeAcuteTriangle(L1, L2, L3))
{// 能组成锐角三角形
return L1*L2*L3/(4.0*S);
}
else
{// 其他情况：三点共线，组成直角三角形，或锐角三角形
return max(L1, L2,L3)/2.0;
}
}
else
{// 任选 3 个点
double r, minR = 0.0;
unsigned int i;

struct Point temp[3];
if(selectPoints == NULL)
selectPoints = temp;

for(i=start;(n-i)>=(3-selectPointsAmount);i++)
{
selectPoints[selectPointsAmount] = points[i];
r = minCircleRadius(n, points, i+1, selectPointsAmount+1, selectPoints);
if(minR < r)
minR = r;
}
return minR;
}
}
}
int main(int argc, char *argv[])
{
struct Point points[MAX_POINTS_AMOUNT];
unsigned int i,n;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)
scanf("%lf,%lf",&points[i].x, &points[i].y);
printf("%.4lf\n",minCircleRadius(n, points, 0, 0, NULL));
}
return 0;
}
/*
4
4.2,5.6
78.3,3.8
35.4,15.9
29.88,42.56
*/

Ⅳ 我国植被覆盖率如何计算，与森林覆盖率的区别是什么

植被覆盖率是指所有植被,包草本木本植被,其覆盖率的算法为:以一个区域内的植被覆盖面积除以这个区域的总面积.
与森林覆盖率的的区别是:植被覆盖率所指的范围更广.

Ⅳ 象棋软件引擎分析，详细信息，引擎是怎么搜索招式的

作者:nicepeople10

中象棋软搜索引擎揭密(一) fenon
北京大赛终于过去了, 在这场盛事前后这段时间, 静下心来回顾了走过的象棋研究的路子,心得感触良多.为了纪念这段时间的美好, 我决定把这段时间积累的对象棋引擎的心得, 总结分享出来
我个人希望通过这篇文章,把一些顶尖棋软的知识普及开来,提高开源象棋软件的水平.

1. 搜索引擎和审局之间的关系, 如何建立

阅读下面的内容时, 首先需要了解几个背景知识
a. 人工智能的博弈搜索树和PVS搜索之间的关系
b. PVS搜索是无损搜索
c. PVS的搜索效率和搜索次序的关系

首先明确几点:

a. 做一个全PVS的搜索, 在限定了层数的情况下, 如果基于不正确的知识(比如子力表),并不能保证一定能把杀棋找出来(可能会跑去吃子)
b. 为了提高棋力, 无损搜索PVS是不足够的, 还是需要剪枝的
c. 搜索树和审局之间的关系, 首先知识必须能够引导搜索到正确盘面(这个地球人应该都知道), 第二是避免搜索把正确的分支剪除掉(这个谈论得少一些,我以前曾经有很长一段时间不知道)
我认为, 审局和搜索之间的关系的建立, 在于
a. 知识是带有正确的倾向性的(只能说是倾向性,因为知识很难做到全面准确)
b. 搜索是根据知识而采取剪枝方式的(这个下面详细分析)

下面我举一个简单的例子, 来说明知识和搜索之间的关系

帅
_____
| | |
马 _| 将_|_兵
| _ |_ |_ |_象

在这个盘面, 兵只要靠近王一步, 就可以将死了对方, 但是基于子力表做depth=1的PVS搜索,只会选择: 兵吃象, 有利, 而且评估子力分数很高, 所以吃象

那么, 有什么办法避免这种情况呢?

a. depth=1的时候不做剪枝
b. 给予引擎审局的知识, 告诉引擎保持"马非底线兵"这种组合对将才具有杀伤力

这样就给出了两种选择, 哪种更好?

实际上, b这种选择有两种局限
a. 局限于现在对审局模型建立的水平, b这种情况需要花费大量的人力功夫来维护完整的知识, 而且很难做到准确
b. 目前的引擎的搜索棋步排序, 大都是基于最近访问->杀棋步->吃子步这样的棋步排序方法, 我们可以很容易想象到, 使用全面复杂的知识, 会引起搜索结果冲突(凑着一个吃子或者杀棋的步子去走, 但是最后发现达不到预期的效果), 大大降低了搜索的效率

正是因为上面的原因, 现在我所了解到的高端引擎, 大都是通过控制剪枝的危险程度, 来弥补知识的不足, 比如, 在nullmove中限制depth>=2, 或者, 在lmr(late move rection)--如变种:fruit的history pruning, 控制depth>=3, 都是利用控制剪枝来弥补知识的缺陷.

我们很清楚知道, depth<=2的时候, 都限制了不能剪枝的话, 那么刚才的盘面, 并不需要任何知识,就可以找出杀棋步, 但是, 这个是不是我们需要的呢? 我想不是的, 如果限制了depth<=2不能剪枝的话, 我们会发现我们的搜索, 产生了大量的节点, 啊, 天啊, 可怕的搜索浪费

当然, 最理想的方法是, 搜索排序的次序是基于知识的, 而且盘面评估是基于知识的, 如果我们能够达到这样的效果, 嗯, 我想depth<=1不剪枝的限制也可以去掉了, 这样的引擎肯定效率更高吧

现在, 让我们想想, 哪些分支我们是不想被错误剪掉的? 当然是杀棋步, 杀棋>吃子, 基于子力表的搜索PVS, 很可能漏掉的棋步是杀棋步, 而这个恰恰是我们不想见到的
对于攻杀激烈的中国象棋,可以说两个引擎的差别在于,谁能更快更准确找到杀棋步.

口语化一点来说,给你多搜索两层的能耐,你能保证绝对能通过蚕食我的大子把我变成光棍司令? 尤其是随着高层效应的出现(引擎和硬件的发展,搜索的层数越来越大), 这种可能更是趋向于零, 所以, 我们应该尽量避免漏掉杀棋步

我知道有很多引擎的做法是, 对有潜在攻势的局面做出模糊判断, 并且赋予高分, 如越容易发生杀棋的棋步, 给予越高的分数, 例如三子归边的分数>马炮的分数, 这样就可避免因为吃马炮而漏掉杀棋, 但是这种模糊判断有些致命的缺点
a. 模糊知识,会造成大量的搜索浪费(条件越不准确, 越容易造成搜索浪费)
b. 模糊知识会造成错误的判断, 导致乱弃子
c. 引擎发展需要更长的发展周期, 需要大量的对局来积累知识

一种比较适中的解决方案是, 采取depth<=1不剪枝的搜索方法, 并且给予depth=1时候, 可以形成杀棋的棋型知识的判断
这种方法的原理是, depth=1的搜索,可以达到depth==2的效果, 并且可以避免模糊知识判断带来的误搜索的缺陷

这种解决方案的优点在于
a. depth=1可以生成杀棋的知识可以穷举
b. 知识准确度高,可以大幅度减少搜索浪费

缺点在于, depth=1可以形成的杀型, 覆盖面有限, 剩下的知识, 还是需要通过一些模糊判断来补充, 当然, 这种补充少很多了, 而且完善起来也难度降低很多

上面的介绍可以说是知识模型的缺陷造成的对搜索的依赖, 下面我再来说说, 知识对搜索产生的影响

我们假设有一个盘面, depth=11的PVS全搜索才能发现杀棋, 那么下面的知识, 做depth=10搜索时,哪种才能走出正确的棋步呢?

a. 对depth=1情况可杀棋的知识评估
b. 对depth>=2情况可杀棋的知识评估
c. 子力组合(如单车单王胜单王)和子力优势
d. 位置分(不是子力表,只是位置的分数,如灵活度等)

实际上我们很容易就可以判断出来, depth=1的知识评估,能走出正确的棋步,情况b也可能走出正确的棋步, 但是会有一定的误判, c, d大都情况下, 走不出正确的棋步

我们现在对所有的知识打分, 这个分数依赖的因素应该是(depth, 准确度, 搜索浪费), 即score=形势*(准确度/(depth*搜索浪费))

因为用评估盘面希望得到的分数等于depth>3的棋步, 准确度是相当低甚至会引起大量错误的, 所以我们对盘面评估会有一定的限度,同理,评估depth=1变化内的盘面,我们可以做到非常精确,这个时候可以给一个准确的分数

上面提到的a,b,c,d四种知识,对中国象棋软件的知识覆盖面是相当广了, 我们可以很简单看出, a可以奖励>马炮的分数, 而b因为可能走入误区, 常常只是奖励>士相的分数, 子力组合不会产生误区,但是需要搜索很深才能得出正解,所以分数也是不会太高,位置分则更小了

但是, 给予引擎全面而准确的知识是否恰当呢? 即, 知识是不是越全面, 棋力越强呢? 很多朋友都问过这个问题, 并且认为恰当的知识会减少搜索量, 而且这也是很多朋友追求的方向. 我实践的答案是否. 搜索其实是追求一种性价比, 单位搜索量内, 能得到最好的搜索结果, 才是好的搜索. 简单说说原理, 当盘面有两三个知识倾向都可以产生PV路径的时候, 只会带来引擎的左右徘徊, 尤其在杀棋的盘面, 会大大降低搜索的效率, 这部分的实践结果, 我会在"6. 建立以kingsafety为核心的审局, 以及审局模型的详细分析"再进一步详细分析

这里我想纠正一个错误的想法,常常有一些不了解搜索引擎原理的朋友,拿一些盘面,让棋软去判断,看谁能更快更准找到正解,要尽快解出这种盘面,往往需要大量的模糊知识,或者足够的深度,前者无疑是把棋软送上绝路的一种做法.这种评估只是有一定的意义,但绝对不是衡量棋软水平的标准.

2. fruit引擎分析, fruit引擎能达到2600的高度的原因 (对比crafty进行阐述)

fruit引擎并不追求速度,实际上,fruit并没有使用流行的bitfile,bitrank技术或者bitboard,所以fruit的nps在国际象棋引擎中并不算高(我想比起crafty应该比不上),如果说两者的差异在于评估的话,嗯,那不在我所了解的范围,我只谈谈两者引擎上面的差别

a. fruit的pv节点的意义以及基于pv节点搜索剪枝的效率
能够在搜索中, 把PV节点区分出来, 并且根据节点类型进行剪枝, fruit可以说对PVS理解是非常深刻的.

PV节点的定义大家可以查查相关资料, 既然PV节点表示正确的搜索结果, 那么就肯定不应该剪掉. 同样,对于不是PV节点的, 就不会找出正确的搜索路径, 这就应该剪掉.这个也是fruit剪枝的理论依据。

道理是这样说, 但是我们一开始并不知道每一个节点的类型, 所以在搜索的时候, 会假设某个节点不是PV节点, 然后看它是否会fail, 如果fail,再做PV节点的搜索.

假如这种假设是成立的, 那么就成功完成了对该非PV节点路径的剪枝,否则,需要重新搜索,因为对PV节点假设判断的搜索是做windows=1的搜索,所以耗费的代价是很低的.

下面来看看fruit的实现方法,我认为fruit对PV节点理解的实现方法非常优雅.

int search_root()
{
本节点做PV搜索

if (树根节点并且首节点)
下一层节点为PV节点 // 这个时候还没有找出PV路径,所以必须做PV节点搜索
else
{
下一层节点做假设不是PV节点的搜索
if (fail)
下一层节点做PV节点的搜索
}
}
int search_full()
{
根据上一层对该节点的判断, 进行节点搜索

if (首节点 || 假设不是PV节点的搜索) // 当假设不是PV节点时, windows=1这个时候不应该假设,应该直接计算了,否则就是重复计算浪费时间
下一节点的节点类型跟本节点类型一致
else
{
下一层节点做假设不是PV节点的搜索
if (fail)
下一层节点做PV节点的搜索
}
}

中象棋软搜索引擎揭密(二) fenon
crafty中,对PV节点的区分方法,是PV节点是否落在[-vMate,+vMate]中,实际上,这种判断方法,对子树的PV节点并不能做出有效的判断,这也直接导致了搜索效率的下降

正是因为PV节点的特殊意义,所以凡是PV节点,fruit都不做剪枝,不从HASH取步,甚至PV节点还需要加强搜索的强度(参考TogaII)

b. fruit的nullmove剖析

我们先来看看fruit的nullmove的实现
if (UseNull && depth >= NullDepth && node_type != NodePV) { // 不对PV节点进行剪枝, 而且depth==1时不剪枝(原因参考上文)

if (!in_check // 不是将军盘面
&& !value_is_mate(beta) // 当落入一个不知道上限的窗口时,不剪枝,这种情况发生在height==2时
&& do_null(board) // 国象规矩限定子>=2
&& (!UseNullEval || depth <= NullRection+1 || eval(board) >= beta)) { // 根据距离叶子或者alpha,beta搜索中,棋形的评估进行控制

我想, 对上面的控制条件,大家都是很好理解的, fruit中NullRedcution==3, 这个可以理解为fruit审局做得比较完善,depth<=4进入审局搜索盘面评估的结果, 逼近搜索的结果, 而eval则是对depth>4时候剪枝的控制条件,这种控制条件往往是根据棋形进行控制, crafty是控制大子的个数, fruit是控制评估的结果, 考虑到这个结果因引擎而异, 我就不在这里讨论哪种条件才是更好的了

new_depth = depth - NullRection - 1;

move_do_null(board,undo);
value = -full_search(board,-beta,-beta+1,new_depth,height+1,new_pv,NODE_OPP(node_type));
move_undo_null(board,undo);

fruit的nullmove会导致一种和以外不同的搜索情况产生,crafty的做法是,上一层做了NULLMOVE,现在轮到我了,我应该移动棋步,但是fruit的做法,会引起双方的等待,这是否正确?

答案是,很正确.首先,考虑算法上面的等价性,连续做NULLMOVE,其实等价于我不知道你是否做了NULLMOVE,不过我也尝试做一个NULLMOVE,看你是否能对我造成威胁,这个并不违背NULLMOVE的思想,而且一个不会产生PV路径的节点,做搜索有意义吗?没有意义.既然如此,那么就剪掉吧.

对nullmove的结果,fruit有两种特别的处理手段

第一,不保存结果,因为fruit的算法的剪枝,会让实际的值和nullmove产生的值差别很大
第二,对某些特殊情况,fruit会做一个nullmove verify的search, fruit尝试全面利用nullmove, 但是某些情况, nullmove成功的概率有限, 需要做一定的验证

fruit对nullmove的实现方法,可以说得上是历史性的(开源的引擎来说),这个算法的优异,是fruit搜索效率特高的一个根本原因

c. fruit的qs加强

在上文中, 我已经提过, fruit是尝试通过控制depth<=1使用全搜索的方法, 尽可能发现杀棋, 那么, 对nullmove来说, 如果depth<=4,发生了一个剪枝, 立刻进入了qs, 马上就把杀棋步剪掉了

为了防止这种情况, fruit对刚进入qs的棋步,不单单生成吃子步,还生成将军步,这可以有效防止把杀棋步漏掉的情况.

qs里面,fruit对吃子步产生的将军步,会解将,让对方保持继续进攻的机会,这也是为了防止qs漏掉杀棋步的一种有效措施

虽然qs的论述很少,而且很简单,但是,对qs中,将军的检查,却有着消耗20%性能,提高50%功能的性价比,这个也是crafty所缺少的

d. fruit的history pruning

要了解history pruning, 首先建议参考国象中成熟的算法lmr (late move rection)的论述
fruit对lmr引入了history value,并且对搜索结果做了verify,有效避免了lmr曾经的fail high的问题
这里就不对history pruning的限制条件做详细的阐述了,实际上这种防止危险的检查方法和nullmove的限制是类似的,而且会根据不同引擎知识和搜索结合的特点而存在差异
history pruning经实践证明, 是一种非常有效的剪枝方法, 并且绝对不会对棋力有降低的影响(其实根本原因是不会漏掉杀棋步)

history pruning根据国外的测试,能够提高elo 100,旧版的crafty并没有history pruning

e. fruit的hash实现方法

fruit的hash实现方法,经实践,大概比crafty的方法提高了5%~10%的性能

fruit对每个盘面,保存了一个上界和一个下界,如果对一个盘面搜索时,发现该盘面的搜索范围上界比过往的下界都要小, 则返回保存的下界, 如果发现搜索范围的下界比保存的上界要大, 则返回保存的上界, 如果发现盘面落入保存的窗口中, 则当保存的上界和下界重合而且搜索深度比当前搜索深度更深时, 返回保存的结果

这种hash的处理方法,修正了crafty中,只能对单边情况保存的不足, 有效提高了效率

需要注意的地方是, 在iterative search中, 每次fruit都会把搜索出来的PV路径都保存到hash中,这是用于取步(不是取值), 还有,在处理hash冲突时候, fruit使用了多个cluster的方法...需要细究的细节很多, 大家有兴趣可以仔细看看fruit的实现

f. fruit的search root move list

fruit对每次搜索后对root节点记录分值,并根据分值重新排序,以便下一次使用,当棋步产生振荡的时候(在两个棋步之间徘徊)会有效提高引擎的搜索效率

g. fruit的FAIL SOFT

嗯, 关于FAIL SOFT以及实践的方法, 可以参考纵马奔流的****和fruit的代码, 我就不再无聊多说一次了..

3. fruit 2.1和TogaII1.2.1的差异,elo 100的差距原因

首先需要说明的是,我是用diff的方法,比较两者在搜索实现上的差别的, 应该是没有遗漏的

两者的差别列举如下
a. 延伸的差异, 根据特定棋形做了depth+1的搜索, 也就是越搜反而越深(当然TogaII有手段防止过深)
b. 剪枝的差异, 包括打开futility, delta, 并且对底层也做了history pruning
c. 对棋步稳定的盘面(只产生一个PV路径), 用渴望窗口搜索, 减少搜索量
d. 对危险情况的搜索的加强

两者差异原理分析
简单概括TogaII的改进,那就是利用国际象棋的知识调整了fruit的搜索树,对危险的盘面进行了更深的搜索,否则就剪掉.

首先，TogaII最有效的改进，是在叶子附近，利用history value把证明曾经无效的叶子节点丢弃掉，这是一个非常有效的算法，这里面的道理值得我们深思？为什么我们不能够发现一个这样的算法呢？

如果光是观察futility和delta剪枝法, 我想肯定会有人对我提出疑问? 不是说这些根据子力情况剪掉的分支会漏掉杀棋步吗? 为什么还打开剪枝, OK, 我来一个简单的回答, 假如已经是用了知识判断过这类分支并不危险, 那就可以剪掉了.

TogaII能改进fruit的原因基于对国际象棋的深刻理解(也许是大量的测试的证明), 它的剪枝和延伸, 是相辅相成的, 如果有人想尝试这个方向, 千万不要只开剪枝或者只加延伸

这个方向, 是在搜索树中, 加入对棋类知识的判断. 调整搜索树更适合某种棋规.

4. fruit算法应用于中象引擎的分析及中象引擎算法改进分析

下面的内容，是基于上述阐述的一些具体应用的例子，可对引擎做出一定的修正

a. nullmove改进

nullmove限制条件中, 当depth<=4时, 进入nullmove. 这种情况会忽略了depth=1可能产生的杀棋步, 当审局的知识缺乏该方面的内容时, 会漏掉杀棋步

这个时候, 可以根据自己引擎的审局知识的特点, 做depth=1的search_verify

代码如下

if (depth<=4)
do_nullmove;

if (nullscore>=beta)
do_search_verify(depth=1);

这种方法可以避免一些杀棋情况的漏算, 这个也可以算是搜索和知识结合的一个典型例子吧

b. history pruning改进

考虑下面的情况

[炮]吃车1, 车2吃[炮], 车2移动, 和车1移动, 这两个棋步, 会引起同样的history value的减少, 虽然限制了history pruning发生在不吃子的情况, 但是, 中象的交换频率远>国象, 这种情况对fruit中historyvalue<9830就剪枝(60%)显然不适合, 因为中象发生上面的情况要高多了, 而historyvalue<9834(60%)只要该棋步有一次被检索的情况就会发生, 这个时候, 修正historyvalue<16384*45%, 可以有效减少误判

c. futility剪枝及delta剪枝的意义分析

嗯, 这个, 首先参考TogaII和fruit对比的文章

futility和delta, 如果不会漏掉杀棋步, 或者, 在不会被对方杀死的情况, 非常有助于扩大自己的子力优势, 这是这两个剪枝法的机制决定的(注意，这两个剪枝法的依据是扩大子力优势，所以适用的范围是有限的，对双方对杀的盘面是会削弱攻击能力的)

我建议使用这两个剪枝法, 当然是建立在调整过搜索树以后(避免在容易引发杀棋的盘面使用，常见的手段是判断kingsafety，是否处于被攻击状态中)

中象棋软搜索引擎揭密(三) fenon
d. 棋步排序的改进

从PVS搜索的原理出发, 搜索效率取决于搜索次序

常见的棋步排序是历史步->吃子步->killer->etc, 这是基于最大化子力优势的搜索, 当对杀时, 这种搜索排序效率是非常低的.

考虑killer棋步,如果能够发生一个killer步的分数是杀棋步,那么调整棋步排序为历史步->killer->吃子步->etc,这样就很好地把杀棋和吃子都结合起来了

5. fruit算法和象眼的差异, 如何提高象眼的棋力
通过本篇的介绍, 希望能够把开源的象眼程序, 改进到一个全新的高度, 假如有人希望一起完成象眼的改进, 请站内和我联系

下面是我认为可以有效提高象眼棋力的几个地方
a. 基于PV节点的nullmove pruning
b. qs加强
c. History pruning及TogaII剪枝法
d. 棋步排序
e. hash的改进
f. IID算法修正
g.search root move list

6. 建立以kingsafety为核心的审局, 以及审局模型的详细介绍

a. 对盘面区分阶段, 不同阶段采取的策略是不同的, 开中残差异是很大的

实际上, 开局通过开局库和子力位置分+若干简单知识, 是很容易走出正确的棋步盘面的, 这个研究不深, 我更多是依赖开局库解决这个问题

残局时候, 调整位置分表, 判断子力组合, 这个时候因为子力很少, 基本上难以进取, 更多是应该考虑防守, 控制搜索的危险程度和给予适当的分数, 很容易做到这点

中局是比较复杂的, 下面详细说说我所理解的地方

b. 对某个阶段的知识, 不要给引擎太多的选择, 避免引擎找出多个PV路径, 引起棋步的来回选择, 如中局, 应该集中思考杀棋或者扩大子力的优势

c. 上面1.讲述了搜索和知识之间的关系, 其中也提及了depth=1时候的杀棋知识评估的重要性, 但是, 只是局限于depth=1的杀棋知识, 我们的盘面判断力还是很有限的, 这个时候怎么办? 我们能不能对depth>=2的情况进行评估

我提供一个实践的方法, 那就是分层次打分.

比如: 三子归边的判断, 我们通过以下三种层次评分
(a) 有沉底炮, +分 (depth=3)
(b) 有沉底炮和车可做炮架, +分 (depth=2)
(c) 有沉底炮和车并且马进入了可以助攻的区域, +分 (depth=1)

刚才在上面的审局和搜索的关系中，我列举了4种知识，并且强调了知识只应该选择有效的，下面分别说说哪些知识是必须的，不在下面列表内的知识，我都不做判断了
a. 准确的杀型
利用位置分值提示车马兵攻击王周围，依赖搜索完成
b. 模糊的杀型
(a) 当头炮 (空头炮,镇中)
(b) 底炮 (三子归边)
(c) 双车杀
c. 子力组合，只做会引起问题的子力组合判断，如兑子后双马不佳
d. 某些特别容易出问题的知识的补充

7. 国际象棋Rybka的胜利以及将来棋软发展的一些展望

一些未来的研究方向, 所以个人的意见应该是一些胡言乱语,仅作笑料

上面所说的一切, 都是基于知识会有一个确定的分数, 但是, 这明显是错误的, 谁能说三子归边是400分,而不是395分呢? 有没有一种方法, 可以动态评估这个分数, 从而达到知识的最优化呢?

第二,传说中的根据知识排序棋步的方法

在国外流行的认为Rybka超越其他软件的原因是因为更聪明的搜索和知识, 从作者言论和Rybka反映的信息做一个猜测(nps超低, 搜索准确度超高), 一致认为Rybka在搜索和评估中, 都采取了全新的方法

其中一个流派3moves现在被认为是Rybka最有可能采取的方法(包含了我的理解补充)

什么是3moves? 首先, 当前盘面移动一步, 对可以攻击的子,计算3步内可以攻击的点集,这个点集每个点都有权重.那么,多个攻击子做交集的时候, 密度最高权重最高的区域, 就是当前盘面最容易攻击的位置, 这表明了这一个棋步的攻击能力
当这个棋步能攻击到王或者其他子时, 这自然就是一个好的棋步,这时候根据点集的情况进行算分,自然是非常准确的.

这种方法超越了子力表和知识分数的局限, 而且更好理解了棋规, 也难怪被认为是最有可能的

以上转载，不知是否你想要的？