围棋AI之路（五）自然选择过程

上次一个网友建议我用遗传算法，不过当时我没有找到合适的遗传因子，其实根本原因是我那时候正在手工测试程序的棋力，我自己和程序下，发现问题，然后看看怎么改进。这个过程中其实带有太强的主观色彩了，直到一周前我正式摒弃了UCG的想法，我才终于决定用自然选择的方式来测试程序的棋力。

摒弃UCG

前面的文章中提到过UCG的思想，也就是认为博弈树实际上应该看做是一个图，因为下棋时的每一个局面，都可以用不止一种顺序走出来，也就是每个节点不止一个父节点。我刚接触UCT算法时，就想到了这一点，而且奇怪为何没人这么做，总觉得如果按照图来处理，模拟的结果应该更逼近真实情况吧！因为图的处理比树麻烦，还是使用树结构去做了。

再后来，我发现计算机围棋论坛上也有人提出UCG，而我又想到了可以用置换表等效的实现后，很是兴奋，人都是会对自己的想法夸大优点，并且无意中忽略缺点。例如我对我实现的UCG多占用的一倍内存视而不见，速度比UCT慢我也能接受，并且出于良好的自我感觉，在与程序对战后，我做出了“UCG使得程序棋力立即有了提高”的判断。

幸好我在进一步改进UCG机制前，我写了个脚本让两个程序之间对战。并从对战结果中发现一个残酷的事实：使用UCG的程序完败。

在事实面前，我才想明白了原由：UCT算法本身是一个对所有节点公平的算法，如果某个节点在树中有同型节点存在，那么其任何一个兄弟节点也存在同型节点。而UCG的作用是使一个节点的模拟结果被其全部同型节点共享，共享或者不共享，影响的只是对节点过往胜率的重视程度，但是UCT算法本身就有调节这种重视程度的机制，还记得UCT的本质吗？就是在开发和探索之间寻求一种平衡，对过往胜率的重视就意味着把开发的权重加大。

这就是说我挖空心思做的一个UCG改进没有丝毫意义，它的效果可以通过调整UCB公式的参数模拟出来。

AMAF的使用

这是一种最大限度利用模拟结果的手段，All Moves As First，即所有的棋步都像第一步一样。例如，黑棋假设它在A1处下一步棋，然后进行模拟，模拟结果为黑胜，那么传统的UCT计分方法是为A1这个节点加一分，并把结果向A1的祖先节点汇总，也就是把黑棋胜利归功于A1这步棋。而按照AMAF的做法，则是把功劳均摊到A1以及模拟对局中黑方所下的每一个位置。

这个方法的优点在于能用少量的模拟局数获取大量的得分情况，从而加快局面评估速度。但是其缺点和优点一样突出，在棋类游戏中的一个常识是，棋步的顺序是与胜负有关系的。这样的快速评估很可能会得出错误的结论。因此，AMAF不是一个一致的算法。

一个折中的做法是设定一个分割比率，只对模拟对局前一部分的棋步计分，通常我们认为先下的棋步要比后下的棋重要。这个比率的取值从0到1，显而易见，如果取0，算法就还原为原始的UCT了；如果取1，则又相当于一个完整的AMAF了。取什么样的值，我用自然选择来决定。

自然选择

遗传因子我已经选好了，一共3个，分别是节点的成熟度（一个节点被模拟多少局后才为其创建子节点，going down的说法是ooxx多少次后才生娃），探险的权重，AMAF的分割比率。

维护一个种群数量不变，每次随机取出两个遗传因子不同的个体，让它们分先下两局棋，输了的杀掉，赢了的可以无性繁殖一个后代，繁殖的过程中有一定几率发生变异。如果没有分出胜负，那也不能让它们无限的活下去，无论胜负，每下一次棋，生命减1，生命到0也直接抹掉。然后我会再随机创造新的个体去补齐数量的。

听起来颇有造物主的感觉呀，进化将会是一个漫长的过程，为了让它们下的棋有意义，我每步棋给了它们足足一秒钟的思考时间。从本文开始写作时，它们的竞争已经开始了，到现在，预先设置的两个种子选手之一已经被淘汰掉了一个，不过离进化的终点还差的很远，按照游戏规则，这场进化的结束条件是全部的个体都拥有相同的遗传因子。

程序实现上，我采用了unix的传统，用C实现核心部分，脚本语言作为黏合剂。至于代码，实在没什么新东西，无非是测试和调整了些参数，我也懒得一遍遍上传了。实现自然选择的脚本我贴在下面，有兴趣可以参考。

1. #!/usr/bin/perl-w
2. #http://search.cpan.org/~jzucker/DBD-CSV-0.22/lib/DBD/CSV.pm
3. useDBI;
4. local$MAX_COUNT=40;
5. local$curid;
6. local$prgname="oygo.exe";
8. my$time_to_die=0;
9. subsignal_handler{
10. $time_to_die=1;
11. }
12. $SIG{INT}=$SIG{TERM}=$SIG{HUP}=\&signal_handler;
14. my$dbh=DBI->connect("DBI:CSV:f_dir=./csv");
15. $dbh->{'RaiseError'}=1;
16. $@='';
17. eval{
18. $dbh->do("CREATETABLErenju(idINTEGER,gidINTEGER,lifeINTEGER,gene1INTEGER,gene2char(50),gene3char(50))");
19. };
20. subinsert_rand{
21. my$id=shift;
22. my($gene1,$gene2,$gene3)=rand_gene();
23. return"INSERTINTOrenjuVALUES($id,$id,10,'$gene1','$gene2','$gene3')";
24. }
25. subremove{
26. my$id=shift;
27. return"deletefromrenjuwhereid=$id";
28. }
29. #mature[0,+infinite)
30. #explore_rate[0,16)float
31. #aaf_fraction[0,1]float
32. subrand_gene{
33. return(int(rand50000),rand16,rand1);
34. }
35. subclone{
36. my$a=shift;
37. my($id,$gid,$life,$gene1,$gene2,$gene3)=@$a;
38. $curid++;
39. if(int(rand5)==1){
40. my$n=int(rand3);
41. if($n==0){
42. $gene1=int(mutate($gene1,0,50000));
43. }elsif($n==1){
44. $gene2=mutate($gene2,0,16);
45. }else{
46. $gene3=mutate($gene3,0,1);
47. }
48. unless(($gene1==$a->[3]&&
49. $gene2==$a->[4]&&
50. $gene3==$a->[5])){
51. $gid=$curid;
52. }
53. }
54. return"INSERTINTOrenjuVALUES($curid,$gid,10,'$gene1','$gene2','$gene3')";
55. }
56. #<1>步长变异
57. #<2>高斯变异
58. #这里用的是步长变异
59. submutate{
60. my$value=shift;
61. my$lower=shift;
62. my$upper=shift;
63. my$Boundary=1/20;
64. my$Delta=0;
65. for(my$i=0;$i<20;$i++){
66. if(rand1<$Boundary){
67. $Delta+=1/(1<<$i);
68. }
69. }
70. if(rand1>0.5){
71. $value+=($upper-$value)*$Delta*0.5;
72. }else{
73. $value-=($value-$lower)*$Delta*0.5;
74. }
75. return$value;
76. }
77. submatch{
78. my$a1=shift;
79. my$a2=shift;
80. my$gid1=$a1->[1];
81. my$gid2=$a2->[1];
82. my$str1=join(",",(@$a1)[3,4,5]);
83. my$str2=join(",",(@$a2)[3,4,5]);
84. #print"$str1win$str2\n";
85. my$cmd="perltowgo.pl--games2-b='$prgname--arg=$str1'-w='$prgname--arg=$str2'2>/dev/null";
86. my$result=`$cmd`;
87. if($result=~/winner:(.*)$/i){
88. $winner=$1;
89. if($winnereq"$prgname--arg=$str1"){
90. print"$gid1->$gid2\n";
91. return1;
92. }else{
93. print"$gid2->$gid1\n";
94. return-1;
95. }
96. }
97. print"--$gid1,$gid2\n";
98. return0;
99. }
100. while(!$time_to_die){
102. my$count;
103. $sth=$dbh->prepare("SELECTcount(id)asnFROMrenju");
104. $sth->execute();
105. $sth->bind_columns(undef,\$count);
106. $sth->fetch;
107. $sth->finish;
109. $sth=$dbh->prepare("SELECTmax(id)asnFROMrenju");
110. $sth->execute();
111. $sth->bind_columns(undef,\$curid);
112. $sth->fetch;
113. $sth->finish;
114. $curid=0unless($curid);
115. $count=0unless($count);
116. for(my$i=$count;$i<$MAX_COUNT;$i++){
117. $curid++;
118. $dbh->do(insert_rand($curid));
119. }
121. my$randrow=int(rand($MAX_COUNT));
122. $sth=$dbh->prepare("SELECT*FROMrenjulimit$randrow,1");
123. $sth->execute();
124. my@a1=$sth->fetchrow();
125. $sth->finish;
126. my$gid1=$a1[1];
127. $sth=$dbh->prepare("SELECTcount(id)asnFROMrenjuwheregid<>$gid1");
128. my$numrows;
129. $sth->execute();
130. $sth->bind_columns(undef,\$numrows);
131. $sth->fetch;
132. $sth->finish;
133. die"selectionfinished!"unless($numrows);
134. $randrow=int(rand($numrows));
135. $sth=$dbh->prepare("SELECT*FROMrenjuwheregid<>$gid1limit$randrow,1");
136. $sth->execute();
137. my@a2=$sth->fetchrow();
138. my$result=match(\@a1,\@a2);
139. if(!$time_to_die){
140. $a1[2]--;
141. $a2[2]--;
142. $dbh->do("updaterenjusetlife=".$a1[2]."whereid=".$a1[0]);
143. $dbh->do("updaterenjusetlife=".$a1[2]."whereid=".$a2[0]);
144. }
145. if($result>0){
146. $dbh->do(clone(\@a1));
147. $dbh->do(remove($a2[0]));
148. }elsif($result<0){
149. $dbh->do(clone(\@a2));
150. $dbh->do(remove($a1[0]));
151. }else{
152. }
153. $dbh->do("deletefromrenjuwherelife<=0");
155. }#endwhile
157. $dbh->disconnect();
158. print"exit...\n";