《棋战顺序基本手艺》专题
 
调整评定函数
 
David Eppstein */
* 加州爱尔文大学(UC Irvine)信息与盘算机迷信系
 
  上次我谈到下排场评定中的许多函数,把这些函数加起来就能够够搭配成评定函数。然则数值从那里来?
  譬喻在是非棋中,你能够说出四种函数:
  (1) f(局势) = 子力(我的子数 - 对手的子数)
  (2) g(局势) = (我掌握的 - 对手掌握的)
  (3) h(局势) = 灵活性(我能够走的)
  你必需搭配这些函数(能够另有其他项)来组成一个评定函数:eval = a·f + b·g + c·h。譬喻,你能够实验:eval = -1·f + 10·g + 1·h。然则这些数值从那里来?哪种数值的搭配能够失掉最好的效果?
  下面是手工找到这些数值的一些要领:
 
  (1) 规格化(Normalize)若是你只体贴评定的递次,而一般不怎样体贴评定值,那末你就能够够把每一项都乘以异样的常数。这就意味着你对某个特定的项目(例如说兵的价值)能够硬性设一个值,其他值就透露表现成它们相即是若干个兵。这个要领可以使你增加一个要求设定的参数。
 
  (2) 约束法(Deduce Constraints)你希冀让计算机作出甚么样的剖断,斟酌这些问题就能够够一定一些参数了。譬喻在国际象棋中,纵然你赚到一个兵,用车换象或马一般照样坏的,然则若是你赚到两个兵那照样好的,因而子力价值要知足R>B+P(预防换单兵)R<B+2P(勉励换双兵)。这样的不等式你给得越多,适宜的权重搭配就越少。在一最先设定权重值的时刻,这个要领一般能够失掉适宜的值,然则前面你依然要求做一些调整。
 
  (3) 交手法(Hand Tweaking)这是很经常使用的要领,仅仅是使你的顺序棋战足够多的次数,来找到它的优势和瑕玷,预测哪些参数会让顺序更好,然后选择新的参数。这个要领能够很快失掉恰当的效果,然则你要求对这类棋类有足够的相识,这样就能够够依据顺序的对局来做剖析,知道顺序的问题在那里。(也就是说,当顺序很笨然则你很智慧时,这个要领最有用。)
 
  不要求野生干预的要领有:
 
  (4) 爬山法(Hill-Climbing)相似于交手法,每次对权重作很小的改动,测试改动后的显示,仅当做绩提升时才采用这个改动,要求一次又一次许屡次。这个要领看上去很慢,而且只能找到“一般中央最优”的搭配(即评定能够很差,然则任何很小的改动都邑使评定更差)
 
  (5) 模拟退火法(Simulated Annealing)相似于爬山法,也是对权重做改动来提升结果的。然则若是改动没有提升结果,有时候(随机地,给定一个几率)也采用改动,试图跳出全局最优。这个要领要求给定一些几率,从几率高、梯度大的条件最先,然后逐渐减小。模拟退火法比爬山法更慢,然则一直能够失掉对照好的值。
 
  (6) 遗传算法(Genetic Algorithms)爬山法和模拟退火法能够失掉一组好的权重,它们是逐突转变的。相反,遗传算法能够失掉几组分歧的好的权重,络续增长新的搭配跟正本的做对照(取用某组中的某个权重,其余一组中的其余一个权重,互订交流失掉新的),经由历程淘汰坏的搭配来掌握种群的数目。
 
  (7) 神经网络(Neural Networks)现实上这更多地是一种评定函数的类型,而不是用来选择权重的:神经元是阈值(输入权重的和)的函数,第一层神经元输入的关于局势的性子(譬喻位棋盘透露表现中的某几个位)就能够够组织网络,然后前一层的效果输入到后一层。因而单输着迷经元的单层网络就同等于咱们上次议论过的一阶评定函数,然则接上去就能够够组织更庞大的神经网络了,而且用这类要领作为评定函数是很容易的(只需依据输入的改动来重新盘算神经元的输入就能够够了)。问题依然像前面所说的,怎样设置权重?除了前面的要领外,重点一定神经网络还生长出一些要领,譬喻“暂时差异学习”(Temporal Difference Learning)。其基本头脑是一定网络什么时候会作出坏的评定,而且让每一个权重增长或减小视是否是会评定得更好,这很相似于爬山法。跟其他自动学习的要领相比,神经网络的有益之处就在于它不要求许多人类的智慧:你不要求晓得太多的棋类知识,就能够让顺序有个对照好的评定函数。然则依据现在咱们掌握的状况,依据自身的智慧来做评定函数,要比机械学习做得好,而且做得快。
 
  这些要领都要求依托一些自动化的手艺,以便对顺序的性能停止评价:
  (1) 咱们能够用顺序处置责罚少量的测试局势(例如人类棋手的高质量对局中收罗的局势)而且看它是否是失掉准确的效果。
  (2) 咱们可以让顺序对阵一些著名的对手(例如其他顺序)来看它能赢几盘。也许咱们可以让顺序和它自身对阵,以及和它自身的其他版本对阵,譬喻在爬山法中,用修正过的版本对阵没修正过的版本。这个要领有自身的瑕玷,除非系统中增长一些随组织键要点,否则两个顺序每次会下出一样的棋,因而你只是发现一局棋的效果而没有设施象征悉数竞赛。一个适宜的要领就是拿一组测试局势,从每一个局势最先就能够够下出分歧的棋。
  (3) 咱们能够对照两个效果,一个用评定函数失掉,其余一个用评定和搜索相联系失掉。若是评定是好的,那末两者应当靠近,然则反过去说行吗?
 
  那末怎样来自动掌握评定中的权重呢?能够参考Jay Scott的“博弈中的机械学习”这个网站。他枚举了两个执行要领,我以为对照有趣:
  (1) John Stanback(著名的商业国际象棋顺序设想师)实验用遗传算法来设置他的顺序Zarkov中评定函数的权重搭配。他只测试了2000-3000局,我以为太少,失掉的值还不错,然则依然比手工调整的差。这个案例能够看出遗传算法实在有用,然则要求遗传许多代,也许有一个好的权重搭配作为祖先。
  (2) Risto Miikkulainen,是得克萨斯大学里遗传算法的研讨员,他以前重点一定是非棋的执行做了个申报。他用遗传算法来调整神经网络型评定函数中的权重。评定网络经由历程对阵流动顺序来竖立,若是这个流动顺序下棋是随机的,那末神经网络会以棋子-格子数组的形式掌握评定(棋子在角上是好的,在角的相近格子上是坏的,等等),直到它一直能赢了才住手学习。然后对阵一个浅的搜索联系棋子-格子数组的顺序,它一直(经由历程几个星期的盘算)掌握了基于灵活性的战略。然则若是对手以前是很智慧的基于感动性的顺序,那末它一直会输而且不会学习。这个案例能够看出,要停止学习就必需对阵水平相等的顺序,譬喻在遗传算法的统一个种群里,让两个分歧的评定的顺序停止对阵,也能够让某个顺序对阵分歧棋力的对手。
 
  原文:http://www.ics.uci.edu/~eppstein/180a/970415.html
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译
  • 上一篇 局势评价函数——简介()
  • 下一篇 其他战略——胜利局势
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com