模式搭配关系的获取

14.2　模式搭配关系的获取

定义模式搭配关系的目的，就是为了从棋谱中抓取这种搭配关系，获得相关统计数据，并且用之指导对弈。

模式搭配关系的获取也是以上下文模式的获取为基础的，其大致流程如下。

①对于当前棋盘状态下的最后一手棋，获取该手棋的上下文模式S；

②将该手棋周围不为空的点找出来，标记为M₁，M₂，…，M_n；

③分别获取以M₁，M₂，…，M_n为中心点的上下文模式S₁，S₂，…，S_n；

④将S和｛S₁，S₂，…，S_n｝中的每一个上下文模式分别组合形成模式对，标记为SS₁，SS₂，…，SS_n；

⑤通过假设检验判断（S，S_k）在一起的模式对SS_k的紧密程度。

其中，在获取以M_k（1≤k≤n）为中心的上下文模式时，只包含时间顺序上在M_k之前出现在棋盘上的棋子。

如图14.1所示，我们的目的是要提取以第11手棋为中心的上下文模式的搭配关系，那么，我们需要关心的不仅是第11手本身的上下文模式，还要关心处在其周围的与之相处一定距离的第8手棋的上下文模式。

图14.1　模式搭配关系的抓取

如图14.2和图14.3所示的两对9×9大小的模式就分别是两对具有搭配关系的上下文模式。其中，图14.1中，从时间顺序上看，图14.2（b）出现在图14.2（a）之后，我们可以发现，尽管这对上下文模式的中心点距离很小，但是它们展现的视野却有很大差别，图14.2（b）比图14.2（a）多看到20%的范围。而图14.3中，图14.3（b）较图14.3（a）相比，看到了显然不一样的情景，一个是角上的模式，而另一个则是边上的模式。

图14.2　范围不同的上下文模式

图14.3　角的上下文模式

模式搭配关系的获取的具体细节，在Listing14.1中给出了实现的相关伪码。在最坏的情况下，该算法的复杂度为O（N²），其中N为该棋谱中所包含的落子数。

Listing 14.1　模式搭配关系的抽取

在获得了上下文模式搭配关系的这些基本的频次信息之后，我们便可以采用假设检验的方式来对所有的搭配关系进行分析，判断每对搭配关系是偶然出现的还是必然出现的，如果是偶然出现的，我们便可以忽略此种搭配，否则的话，我们就可以确信这对模式间的搭配是具有某种必然联系的。

在关于模式搭配关系的假设检验的计算中，我们采用皮尔森的χ²检验。在具体计算中，我们通过计算模式对（P，Q）之间搭配的可能性的比率来做如下假设。

①H₁：Pr（Q｜P）＝Pr（Q｜P），即模式P和模式Q相互独立；

②H₂：Pr（Q｜P）Pr（Q｜P），即模式P依赖于模式Q，也就是说模式P和模式Q具有搭配关系。

假设检验亦称“显著性检验”，是数理统计学中根据一定假设条件由样本推断总体的一种方法。也就是说，判断样本与样本或总体之间的差异究竟是由抽样误差引起的，还是由于其事物的本质差别造成的统计推断方法。假设检验的基本思想是，先对总体的特征作出某种假设，然后通过抽样研究的统计推理，根据其具体的统计特征，对该假设应该被拒绝还是接受作出推断。

假设检验所基于的理论基础是，小概率事件（P＜0.01或P＜0.005）在一次试验中基本上不会发生。先提出假设，再用适当的统计方法对观察得到的统计信息进行判断，确定假设成立的可能性大小，如可能性很小，则认为假设不成立，也就是拒绝该假设，否则的话，则不能认为该假设不成立，也就是接受该假设。

假设检验的一般步骤如下。

①根据实际问题，提出检验假设H₀和被择假设H₁；

·检验假设H₀，是指样本与样本或样本与总体之间的差异是由抽样误差引起的；

·被择假设H₁，样本与样本或样本与总体间存在着本质的差别；

对于假设检验问题，需要预先设定一个检验水准：也就是对于假设检验为真，但是被错误地拒绝的概率，记作α，通常取α＝0.05或α＝0.01；

②根据样本的观察值按照某种统计方法计算得出相关统计量的大小；

③根据统计数据的具体特点，选用具体的检验方法，如Z检验、T检验、χ²检验、秩和检验等。

④根据实际统计量的大小及其分布确定检验假设成立的可能性P的大小并判断结果；

·若P＞α，结论为按照α所取水准不显著，则不拒绝H₀，即认为差别很可能是由于抽样的误差造成的，在统计上不成立；

·若P≤α，结论为按所取α水准显著，拒绝H₀，接受H₁，即认为此差别不太可能是由于抽样误差所致，很可能是由其本身的因素所造成的，因而其在统计意义上成立。

如图14.4所示展现了从16 067个专业棋谱提取出的出现频率最高的3个9×9大小的模式搭配关系，从这3个搭配关系我们可以很容易看出，这3个搭配关系正是围棋中经典的开局方式。

图14.4　从16 067个专业棋谱提取出出现频率最高的3个的9×9大小的上下文模式的搭配关系