Chemistry 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Chemistry
标  题: 电脑象棋和量子化学——计算量子化学的新思路(二)
发信站: BBS 哈工大紫丁香站 (Thu Mar 31 09:40:36 2005)

电脑象棋和量子化学
——计算量子化学的新思路

黄晨 *　2005年3月
(* 联系地址：复旦大学化学系表面化学实验室，eMail：morning_yellow@elephantbase

.net)


B．计算和搜索

B1. 象棋引擎和量子化学计算引擎有什么共同点？
B2. 局面分析和构型分析有什么区别？
B3. 局面搜索和构型搜索在策略上有什么区别？
B4. 局面搜索通常采用什么方法？
B5. 构型搜索的目标是什么？
B6. 局部和全局构型搜索各有什么算法？
B7. 单点计算的导数如何获得？
B8. 所有的单点计算方法都能通过分析法求得导数吗？
B9. 退火算法和遗传算法有什么区别？
B10. 置换表为什么能提高搜索效率？
B11. 象棋局面的对称性和分子构型的对称性有哪些区别？
B12. 搜索算法中如何有效地利用对称性？
B13. 如何只为搜索算法制作引擎？

B1. 象棋引擎和量子化学计算引擎有什么共同点？

　　象棋的局面和分子的构型作类比，是再恰当不过的了。他们都有特定的元素和形状
，以及特定的演变规律。象棋中的局面评价，以及量子计算中的单点计算，都是针对某
个静态局面或构型作出的处理，这里统称为计算；而象棋中的局势推演，以及量子计算
中的构型搜索，都是针对局面或构型的演变过程进行的处理，这里统称为搜索。

B2. 局面分析和构型分析有什么区别？

　　象棋的局面分析和量子计算中的构型分析，分别是象棋引擎和量子计算引擎的核心
，在通常的引擎设计中，这个核心模块的程序代码是最长的，少则几千行，多达数十万
行，显然这两个问题具有很大的区别，它们的代码也截然不同。但是像下面所提到的简
单举它们的区别，那却是十分肤浅的：
　　(1) 象棋局面是平面的，分子构型是立体的；
　　(2) 棋子的坐标是离散的，原子的坐标是立体的；
　　(3) 棋子所占的空间(棋盘)是有限的，分子所占的空间是立体的；
　　(4) 棋子之间是通过着法(吃、保等动作)联系起来的，原子之间是以化学键联系起
来的；
　　(5) 棋子除了种类和价值不同，分属双方，其中王是胜负的标志，而原子没有这种
区别。
　　其实，就判断依据来说，两者就有本质的不同：象棋局面判断的是双方的优劣，即
形势偏向哪方，或者哪方有可能取得胜利(或者必定取得胜利)；而构型分析则主要指它
的能量，是一个绝对数值，另外还有附带信息如能级、轨道、电荷分布等等。
　　另外，构型分析时只对一个固定的构型作计算，例如水分子(键长0.96?，键角108o)

，作构型分析时不会考虑别的构型(频率计算当然是例外，因此它不属于单点计算的范畴

)。而局面分析就不那么简单了，通常需要预料局势的发展，至少不应该在交换非常剧烈

的时候就作出评价(等到交换完毕后才作出评价的方法称为“静态搜索”)。因此，局面
分析本身就包含了搜索的成分。

B3. 局面搜索和构型搜索在策略上有什么区别？

　　这个问题就没有上面一个问题那么难回答了。很明显，局面搜索是一种“敌对搜索
”，或称“两方面的搜索”，其策略称为“最小-最大”，通俗些说就是每一着都“替对

手想”。
　　构型搜索的策略则更加简单，只要想尽一切办法找到能量最低的构型就可以了，是
一种单方面的搜索。

B4. 局面搜索通常采用什么方法？

　　基于“最小-最大”策略的搜索，其模型称为“搜索树”。由于搜索需要具有一定的

深度，因此搜索树是很庞大的，对搜索树进行有效的裁剪是很有必要的，由此引发出一
系列算法。
　　在象棋引擎的设计过程中，Alpha-Beta裁剪是最基本的算法，除此以外有历史启发
、置换表、空着裁剪、迭代加深、期望窗口、主要变例搜索、静态搜索、将军扩展等等
。由于象棋引擎的发展历程很长，现在这些方法已经日趋成熟。(在计算机诞生以前很久

，就有人开始研究用机器来下棋了，最早可以追溯到拿破仑时代。)

B5. 构型搜索的目标是什么？

　　构型搜索的模型称为“势能面”，即能量关于坐标的函数，这里的坐标可以是键长
、键角等广义坐标，通常坐标不止两个，因此构型搜索的势能面实际上是多维面。
　　势能面通常是连续的曲面，但是有时像地形图一样无规律可寻，因此构型搜索的目
标有两种：
　　(1) 原始构型并不处于势能面的极小点上，通过搜索让构型到达邻近的极小点，这
种搜索称为局部构型搜索；
　　(2) 原始构型可能已经位于极小点，但是周围一定距离内可能有能量更低的构型，
要搜索到这种构型，必须进行全局构型搜索。

B6. 局部和全局构型搜索各有什么算法？

　　局部构型搜索的方法通常有爬坡法、最速下降法和牛顿法，其中爬坡法适用于任何
情况，最速下降法要求势能面的一阶导数不变号，牛顿法则要求二阶导数也不变号，收
敛速度最快的算法适应的条件最苛刻。在一些常用的量子计算程序中，通常采用一种称
为Berny搜索的算法，实际上是对这三种算法的综合运用。
　　平衡构型搜索是找势能面极小点，而过渡态的则是找势能面的鞍点。寻找过渡态的
方法同平衡构型有所不同，这里不作过多的阐述。
　　退火算法和遗传算法是最常用的全局构型搜索，它们都检测附近的多个构型，以获
得最低的一个。由于运算程序不可能直接获得，整个势能面，所以理论上不可能确保找
到能量最低的构型。
　　要确保最低构型，唯一的办法就是做势能面扫描，显然这是一种极其花费时间的做
法。

B7. 单点计算的导数如何获得？

　　最速下降法需要知道势能面上某个点的梯度(即一阶导数)，而牛顿法则需要知道二
阶导数。这里以一阶导数为例，势能面是能量U关于坐标(r1,r2,...,rn)的函数，如果其

导数可以描述为：
http://www.elephantbase.net/other/quantumchem1.gif
(抱歉，公式贴不出来了)，那么求得导数就有以下两种方法：
　　(1) 数值法：求导数的数值公式很简单：
http://www.elephantbase.net/other/quantumchem2.gif
　　但是要注意到这里Dri有3个分量，所以这个公式蕴涵着额外计算3个点的构型，得到

能量关于3个坐标的导数。对于有n个原子的分子构型来说，计算势能面的梯度就需要额
外计算3n个构型的能量，这显然是很花费时间的。
　　(2) 分析法：在对分子构型作量子计算时，需要计算大量的双电子积分uij，它是坐

标(ri,rj)的函数。因此通过对能量U的剖析可以得出U(u12,u13,u23,...)，数值法在求
导数时对大量双电子积分作了重复运算，而分析法在求导数时这些双电子积分并非要逐
个算过来。因此分析法求导数的公式是：
http://www.elephantbase.net/other/quantumchem3.gif
　　现在，在n(n-1)个函数u里，只有n-1个需要额外计算，大大缩短了运算时间。

B8. 所有的单点计算方法都能通过分析法求得导数吗？

　　理论上单点计算都有办法通过分析法来求一阶和二阶导数，但是很多单点计算方法
在求导数时，使用分析法很不现实。
　　对于精度很差的单点方法，例如半经验和经验方法，求得导数的结果可能就是零，
例如在Gaussian程序中，半经验方法只能用分析法求一阶导数，经验方法则无法用分析
法求导数。
　　对于精度很高的单点方法，例如高阶微扰、组态相关、耦合簇等，由于存在三电子
积分，所以用分析法求一阶导数就已经很不容易(这将导致求导数的程序非常烦琐)，二
阶导数就更不现实了。在Gaussian程序中，这些方法大多只能用分析法求一阶导数，精
度最高的耦合簇方法甚至连一阶导数的分析法也不提供。
　　所以，能比较方便地求得二阶导数的，是那些最普通的方法，例如自恰场、二次微
扰、密度泛函等。

B9. 退火算法和遗传算法有什么区别？

　　退火算法和遗传算法的确具有惊人的相似之处，首先它们都检测某个构型附近的多
个构型，其次在搜索过程中这些构型不断变化，变化的方式都带有随机的成分。
　　这两种算法的关键区别在于构型变化方式的不同。退火算法的关键在于，随着温度
的降低，变化幅度越来越小，直到温度降到零变化停止为止，取诸多构型中最低者就可
以了。而遗传算法构型变化时保留了原来的构型，同时把能量最高的一批构型淘汰掉，
而构型变化的幅度则不会缩小，因此遗传算法一直可以进行下去，是一种“没有最好，
只有更好”的思路。
　　后面将会看到，退火算法和遗传算法的应用范围极其广泛，在象棋引擎中，它们会
被用来调节局面评估的经验参数。

B10. 置换表为什么能提高搜索效率？

　　象棋引擎的诸多搜索方法中，大部分是针对“敌对搜索”策略的，但是置换表却对
常规搜索都有效，例如在求最短路径的算法中，可以通过使用置换表来减少很多重复计
算。置换表存储的是静止的局面或构型，如果搜索时能够通过不同路线命中置换表当中
的数据，那么置换表就提高了搜索效率。
　　在求平衡构型和过渡态时，经常会产生构型不收敛的情况，引擎往往会在若干个构
型中间反复计算，如果引擎能得知置换表中已经有计算过的构型，那么它就会采取措施
改变搜索途径或收敛条件。
　　置换表从数据结构上讲是一种散列表，只能以离散的数据作为索引值，因此在为分
子构型产生索引值的时候，首先必须根据对称性来摆正坐标架(坐标架应当为转动主轴)
，然后对原子坐标进行格点化处理，这样坐标就离散化了，最后求得索引值。求索引值
的方法可以借鉴象棋引擎中的Zobrist方案。

B11. 象棋局面的对称性和分子构型的对称性有哪些区别？

　　国际象棋的残局分析中，利用对称性可以减少很多重复的计算，由于棋盘是正方形
的，因此在无兵残局中，一个局面往往可以衍生出多个对称局面。对称变换有多种形式
，例如将棋盘顺时针或逆时针旋转90o，作水平或垂直镜像等，以及这些对称变换的组合

(例如沿对角线作镜像)，除此以外，黑子和白子作交换也不改变局面的内涵，这也是一
种局面的对称性。
　　当然，对称性会被某些因素破坏，例如局面中存在兵，由于兵只能向前走，所以局
面仅仅能作垂直镜像(左右对称)，如果局面中存在可以王车易位的情况，那么连垂直镜
像的对称性也没有了。
　　相比之下，分子构型的对称性就丰富很多，对称类型可以用“点群”描述，每个点
群都有一个对称数来反映对称变换的多少，对称数越多就说明对称性越高。例如V字型的

水分子的对称数是4，具有正四面体结构的甲烷的对称数是24，足球型的碳60的对称数是

120。国际象棋无兵残局的对称数是8(加上黑白互换也只有16)。

B12. 搜索算法中如何有效地利用对称性？

　　利用对称性信息可以大幅度提高搜索效率，首先要建立包含对称性信息的置换表，
在置换表中写入局面或构型的同时，连同对称的局面或构型一同写入，这样当搜索到某
个局面或构型时，如果与其对称的局面或构型已经被搜索过，那么可以直接到置换表当
中找到结果。
　　国际象棋的残局库实际上是一种置换表，其中最常见的Nalimov格式就是考虑对称性

的，这样可以使存储局面的数量大大减少。
　　目前的量子计算程序Gaussian只在单点计算中利用对称性，例如水分子中有两个氢
原子，那么一个氢原子的基轨道跟其他轨道的作用，等同于另一个氢原子的基轨跟其他
轨道的作用，这部分作用就不重复计算了。

B13. 如何只为搜索算法制作引擎？

　　Gaussian等量子计算程序尽管功能强大，但是仍然无法完成某些特定的搜索算法，
例如遗传算法。这就需要使用者自己开发一个支持新的搜索算法的引擎。由于搜索过程
必定涉及到单点计算，因此带来一个问题，新的引擎是否要重新写一套单点运算的程序
？
　　答案是不需要的，只要有其他单点计算的引擎，能被搜索引擎调用就可以了。搜索
引擎调用计算引擎，其原理和界面调用引擎是一样的，只是需要注意三点：
　　(1) 被调用引擎必须是来路明确的，否则新引擎就无法发布，计算出的结果也无法
发表；
　　(2) 新引擎必须遵循被调用引擎的协议，就像界面遵循引擎协议一样；
　　(3) 新引擎在启动时就要加载被调用引擎，而不能在每次做单点计算时临时加载，
因为引擎的启动需要一定的时间，反复加载引擎势必会影响效率。
--
  我的友情测试更新了，欢迎测试!
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]


※ 来源:·哈工大紫丁香 http://bbs.hit.edu.cn·[FROM: 202.118.229.*]