WZebra的详细解释

dragoniye

关于WZebra
　　这里提供一些WZebra的相关资料。

贴完了，其实很乱，所以没有循序编排它们，很不好意思，其实大致上没有问题的，如果很用心的看，因为您有决心要赢电脑，一定要知己知彼才能百战百胜，加油！！！！

这里是所有的斑马功能，请多多支持，如果有不明白的地方可以在此发问，谢谢

[本帖最后由 zipp_882000 于 21-8-2006 11:46 PM 编辑

dragoniye

　　WZebra的历史很大程度上就是Zebra的历史，后者是前者下棋所用的引擎。以下是一些重要事件：
1997年6月3日
　　贡纳·安德森(Gunnar Andersson)开始致力于一个被其称为Zebra的黑白棋程序。三周之后，它在黑白棋游戏网IOS(Internet Othello Server)的积分达到1500，相当于业余棋手的水平。

1997年8月
　　完成初级估值函数(evaluation function)和搜索算法(search algorithms)。

1997年9月
　　实现并调试了所有的主要程序组件，包括开局库(opening book)、散列表(hash table)、终局算法(endgame solver)。IOS积分达到1900，比大多数世界冠军都要强。

1998年1月
　　加入并调试了一种新型基于模式(pattern-based)的估值函数。IOS积分升至2300，超过所有人类棋手。

1998年3月
　　通过使用多重概率剪枝算法(Multi Prob-Cut)算法，中局及终局搜索大大改进。同时还尝试了改进的开局库算法。

1998年5月
　　Zebra第一次击败了最强大的黑白棋程序Hannibal。这时的IOS积分超过2500，这使它成为全世界五个最强大的黑白棋程序之一。

1998年5月
　　拉斯·爱文森(Lars Ivansson)开始致力于Zebra的图形用户界面程序，他决定称之为WZebra。

1998年6月
　　第一版WZebra以自由软件形式发布。

1998年8月
　　WZebra 1.41版发布，这是第一个没有严重错误的版本。

1998年10月
　　在声望很高的第二届普林斯顿(Princeton II)计算机程序锦标赛中， Zebra获季军(冠军是Hannibal、亚军是Logistello)。

1999年春
　　Zebra的搜索算法进行了修改，速度大大提高。

1999年7月
　　估值函数中加入更多关于角的知识，并去除一些错误之处。

1999年10月
　　Reindeer作为专下随机(rand)对局的IOS版Zebra，其积分达到2932。在当时ISO所有活跃棋手中，Reindeer是最高积分。

1999年11月
　　WZebra 2.0版发布。相对其早期版本，它更强大、功能更多。

2000年1月
　　WZebra 2.1版发布，它支持Thor数据库。

2000年10月
　　WZebra 2.2版发布。相对其早期版本，它提供更快的终局计算、以及更强更大的开局库。

2001年11月
　　WZebra 3.0版发布。它包含新的特性、新的外观设计、更快的黑白棋引擎。

2002年1月
　　WZebra 3.1版发布。它展示了经改进的外观和新功能。

2002年5月
　　WZebra 3.2版发布。它比以往版本功能更多、错误更少，并拥有熟知罕见棋局的估值函数。

2002年8月
　　WZebra 3.3版及LZebra 3.3版发布。后者是Linux版的WZebra，两者具有相同的功能。

2002年11月
　　WZebra 4.0版发布。它包含许多新功能、并修改了错误。此外，中局搜索深度更深。

2003年1月
　　WZebra 4.1版发布。它具有比以往版本更快的终局算法。

2003年4月
　　WZebra 4.2版发布。它展示了经改进完全可配置的棋盘外观，其中包括三维模式。


现在最新版本4.2.4

dragoniye

搜索(Search)

棋局估值(Position evaluation)

开局库(Opening book)

置换表(Transposition table)

棋步排序(Move ordering)

终局(Endgame)


1)搜索(Search)
　　当今所有强大的黑白棋程序，都是通过向前搜索许多步来确定棋局的最佳棋步：“如果我下这一步，他会下那一步，然后我再下那一步……，那么对我来说棋局有多大的优势？”所谓最佳棋步，就是下了这步棋后，对手下最佳应对、程序又下最佳应对……，最终会产生最佳棋局。这就是所谓的极大极小值搜索(minimax search)：对于程序来说，每步棋之后的棋局优势，程序是将其极大化，对手是将其极小化。
　　很明显，即使是很少的几步棋，所搜索的棋局数量也会急剧上升。在大多数中局棋局中，双方每步棋都有大约10步棋可选。只要前瞻9步(用程序员术语来说就是搜索深度为9)，就需要搜索10亿(10^9)个棋局。幸运的是，有研究表明，程序要找出最佳棋步，并不需要考虑所有这些棋局。一种被称为α-β剪枝(alpha-beta pruning)的程序取而代之，它大大减少所测试的棋局数量。这是70年代中期由唐纳德·克努特(Donald Knuth，中文名高德纳)和其他一些人发明的。其主要思路如下：对于我所考虑的一步棋，只要看到对手有步很强的应对，足以证明我这步棋不可能是最佳棋步，就没必要再去搜索其他更强的应对——因为我无论如何也不会去走这个变化。在有效情况下，这一简单的观察将大大减少需要搜索的棋局数量。所有强大的黑白棋程序(以及其他棋盘游戏程序，如国际象棋和跳棋)，都采用了这种算法的各种变形。典型情况下，Zebra前瞻9步只须考虑100 000~500 000个棋局；相对于不用α-β剪枝算法时需要考虑1 000 000 000个棋局而言，是大大减少了。 Zebra使用的是一种叫渴望负搜索(aspiration nega-scout)的变形，它是由亚历山大·赖讷费尔德(AlexanderReinefeld)发明的。

　　除了alpha-beta剪枝算法之外，Zebra还使用一种选择搜索机制。其思路非常简单，类似于人类棋手的思考方法：在大多数棋局中，许多棋步明显是坏棋，只需前瞻到足以判断出坏棋就可以了。其实现方式如下：当Zebra对棋局搜索12步时(即前瞻12步)，它先对所有棋步搜索4步，然后舍弃看起来相当坏的棋步，再对剩余的棋步搜索12步。关于由搜索4步来预测12步的可靠性，有大量的统计数字可作为“相当坏”的判别依据。该过程称为多重概率剪枝(Multi Prob-Cut)，是由迈克尔·布罗(Michael Buro)发明的。本例中使用了“剪枝对”4/12，对应于搜索深度3~18，Zebra使用15对不同的剪技对。

　　上述搜索算法使Zebra在中局能前瞻18~27步，经常能发现一些只有顶级计算机对手才能察觉到的诡秘战术陷阱。它的搜索速度达到大约是中局1 300 000~1 500 000棋局/秒、终局4 000 000~7 000 000棋局/秒。 (这些数据是在AMD雷鸟/1.33GHz上获得的。)

2)棋局估值(Position evaluation)
　　黑白棋程序所掌握的黑白棋知识，决定了程序的性能，这也是Zebra最重要的部分；如果程序无法解读所面临的棋局，再完美的搜索算法也无助于事。
　　高水平的人类棋手在中局总是努力增大行动力(mobility)、减少边缘子(frontier disc)数量，同时兼顾考虑边角结构。这些衡量标准如何写入程序呢？最成功的方法是把棋局分解成许多局部结构，这也是Zebra所使用的方法。对于每一个局部结构，如各行、各列、长度4~8的对角线、3x3角(例如a1、a2、a3、b1、b2、b3、c1、c2、c3)、5x2角(例如a1、a2、b1、b2、c1、c2、d1、d2、e1、e2)、以及边+相邻星位(例如a1、a2、a3、a4、a5、a6、a7、a8、b2、b7)，Zebra都会赋予一个对应的估值。为了评估整个棋局的价值，将上述局部结构对应的46个估值相累加；如果棋手下棋具有奇偶性(parity)，还要加上相应的附加值；其结果就是对局双方最终棋子数之差的估值。

　　估值函数中所使用的一系列模式(pattern)，表明程序所掌握的黑白棋知识，因此选择好的模式相当重要。另一方面是速度，复杂的模式会使程序变慢。Zebra所选用的模式可以十分快速地进行运算，而且很强大，足以牢固掌握有关棋局方面的知识。

　　现在主要的难题是：需要给许许多多不同的局部模式赋予对应的估值——仅仅是边就有3321个不同的边结构，如果算上所有的结构，会有上万个。更槽糕的是，不同结构所对应的估值又是和对局的不同阶段紧密相关的。毫无疑问，为所有结构评定估值的过程必须能自动完成。其实现过程是先获得大量高手对局的数据库，再计算出所有对局中每个阶段各个结构的统计数据。Zebra花了大约一周的时间，分析了100 000个对局，给1 000 000个不同的盘面模式评定了合适的估值。

3)局库(Opening book)
　　Zebra拥有一个包含经分析对局的大型数据库，在开局阶段(有时还会延伸到中局)用来选择棋步。开局库包含大约35 000个优秀对局，其中大约5 000个对局是由IOS上一些最优秀棋手所下的，其余的是由Zebra自己和自己对弈产生的。虽然程序自我对弈的设置各不相同，但是大多数对局的中局搜索深度都达到22步、胜负正确(WLD-correct)棋步达到28个空格。
　　开局库所含棋局的一些统计数据：

空格数 精确比分(Exactscore) 胜负正确(Win/loss/draw)  
<= 23 100% 100%  
24 30% 100%  
25 14% 100%  
26 12% 100%  
27 12% 100%  
28 11% 100%  
29 0.6% 33%  
30 0.5% 0.9%  
31 0.5% 0.5%  
32 0.4% 0.4%  
33 0.4% 0.4%  

4)置换表(Transposition table)
　　不同的下棋顺序经常会出现同一个棋局，Tiger开局定式就是这样的一个例子，它可以由f5-d6-c3-d3-c4下成，也可以由f5-d6-c4-d3-c3下成。两种下棋顺序的结果是同一个棋局，这就称为置换(Transposition)。为了避免多次搜索同一个棋局，Zebra将搜索过程中遇到的大多数棋局，都贮存在一个置换表中(用散列表数据结构来实现)。对于每个局面，Zebra的估值和搜索到的最佳棋步都被保存起来。在中局阶段，典型情况下可减少深度搜索时间20~50%。在终局阶段，置换的情况更普遍，其好处就更大了。

5)棋步排序(Move ordering)
　　对于α-β剪枝(alpha-beta pruning)，最先搜索棋局的最佳棋步是很有必要的。Zebra使用多种不同的启发式来达到这一目的：对于每一步棋，贮存了这步棋的“杀手应对(killer response)”——如果对手下星位(X-square)g2，我明显应该先看看能否占角h1、以及占角是否明智。另一种有用的启发式是先完成浅度搜索；在开始搜索12步之前，程序先对棋局搜索2步。在浅度搜索之后，找出看起来最好的棋步。相对于完全搜索来说，浅度搜索所花时间明显可以忽略不计。

6)终局(Endgame)
　　由于临近终局时双方棋手可下的棋步减少，Zebra在终局阶段可以搜索得更深远些。在势均力敌的对局中，当盘面还剩下25~35步棋可下时，Zebra通常就能判断出谁会获胜。在一边倒的对局中，Zebra会更早作出判断。完美下法(perfect-play)比分较比较难计算，但一般在盘面还剩下23~28步棋可下时也能计算出。
　　中局所使用的搜索算法同样适用于终局；但棋局估值功能会被关闭，因为所有变化都一直搜索到双方无棋可下为止。在真正开始终局搜索之前，使用多重概率剪枝(Multi Prob-Cut)的一种变形来初步判断比分，并找出看起来最好的棋步。

dragoniye

制作人员
　　WZebra程序的创作者为：
贡纳·安德森(Gunnar Andersson)
　　黑白棋程序Zebra(WZebra程序就是基于它的)、图形用户界面设计、3.0版及后续版本新增功能的创作者，也是当前WZebra程序的唯一维护者。

拉斯·爱文森(Lars Ivansson)
　　大部分图形用户界面程序段、以及最初功能的创作者。

　　感谢以下人员将WZebra程序翻译成各种不同的语言：

语言 译者  
法语 Bintsa Andriani
意大利语 Donato Barnaba
日语 Ryuichi Hoshi
芬兰语 Hannu及Satu Kotipalu
葡萄牙语 Luis Antunes Coutinho Cabral
西班牙语 Jorge Bandres
荷兰语 Daniel Rokven
丹麦语 Claus Qvist Jessen
土尔其语 Ibrahim Okuyucu
汉语 阿晖


　　同时还要感谢扬·C·德格拉夫(Jan C. de Graaf)允许Zebra程序在他的电脑上扩展开局棋谱库，感谢科林·施普林格(Emmanuel Lazard)允许我们加入法国黑白棋联盟(FFO)策略指南，感谢戴维·萨默斯(David Summers)允许我们加入其终局算法的稳定代码，感谢罗伯特·加德利夫(Robert Gatliff)允许我们使用其开局定式表。

　　我们还要感谢那些从先前版本中找出错误的测试者，特别是G&ouml;ran Andersson、Pierre Martin、BeppiMenozzi、 Edmund Yiu、Marc Tastet、Norihiro Tanaka以及Borlam Lam。

版权声明
　　本程序是自由软件，你可以自由复制，但不得自行修改——这是我们回报网上黑白棋社团的方式。未经程序创作者的明确许可，不得用于任何商业用途。
　　对于WZebra的运行结果，我们不承担任何责任。

dragoniye

数据库(Database)菜单
　　本菜单提供了对Thor数据库的操作界面。Thor数据库所包含的对局超过70 000个，可以从FFO下载页面下载。
　　以下列出的菜单选项，许多是必须加载了一个棋手库、一个比赛库和至少一个对局库后才会显示出来，对这些菜单选项将加注星号(*)。

查找当前棋局(Look up thisposition)*
　　在数据库中查询当前棋局。只有加载了棋手库、比赛库和对局库，才能完成本操作。搜索结果显示在一个单独的窗口内。
　　实例： (这里没有)

　　标题部分包含了棋局的概要信息。在本例中，所加载的数据库有48个对局出现过当前棋局，其中33.3%的对局是黑胜、2.1%平局、其余64.6%白胜，平均比分是黑棋28.2子比白棋35.8子。下得最多回应的是f2，出现了31次，率胜34%；d2出现15次，率胜33%；d1出现2次，率胜50%。

　　列表中每一行包含一个相匹配的对局，从左到右各栏分别是：黑棋棋手、白棋棋手、比赛名称、比赛年份、黑棋子数、白棋子数行分。如果双击一个对局，当前棋局就会按那个对局的变化下一步棋。


查找所有棋局(Look up allpositions)*
　　自动运行上述的查找当前棋局：在对局、打谱或复盘模式中出现的所有棋局，都将对数据库进行查询。

加载对局库(Load gamedatabase)
　　加载一个对局数据库，通常一个对局库对应一个特定年份中所下的对局。对局库的标准文件名形如wth_2002.wtb。可以同时加载多个对局库，但每个年份只能有一个对局库。

加载棋手库(Load playerdatabase)
　　加载一个棋手数据库，每次只能加载一个。棋手库的标准文件名为wthor.jou。必须确保所加载的棋手库是最新的；否则，如果加载一个更新的对局库，它所包含的棋手可能不在老的棋手库内。

加载比赛库(Load tournamentdatabase)
　　加载一个比赛名称数据库，每次只能加载一个。比赛库的标准文件名为wthor.trn。必须确保所加载的比赛库是最新的；否则，如果加载一个更新的对局库，它所包含的比赛可能不在老的比赛库内。

加载数据库配置(Load databaseconfiguration)
　　打开先前保存的数据库配置，数据库配置中所包含的数据库都将自动加载。

保存数据库配置(Save databaseconfiguration)
　　保存当前数据库配置，包括加载的棋手库、比赛库和对局库列表。这一配置为下次需要读取这些数据库时提供便利，你只要使用上述加载数据库配置菜单，就能恢复到当前环境状态。

显示加载库(Display loadeddatabases)
　　显示当前加载的所有数据库(棋手库、比赛库和对局库)。

限定棋手(Playerrestrictions)*
　　选择所要关注的棋手。以后查询数据库时，将只考虑由选定棋手所下的对局。这里提供两种选择方式：一种是对局的一方被选中即可，另一种是对局的双方都被选中才有效。第一种方式通常用于为对抗某特定棋手做准备；通过只选择该棋手，就会列出他所下过的对局。第二种方式通常用于分析由一小部分棋手下过的对局；例如，选择一些世界级的棋手，就有机会看到高手间对局的情况。

限定比赛(Tournamentrestrictions)*
　　选择所要关注的比赛。以后查询数据库时，将只考虑在选定比赛中所下的对局。

限定年份(Yearrestrictions)*
　　选择所要关注的时间段。该时间段之外的对局只保存在内存上，但不会被考虑。如果时间段改变，这些对局仍会重新被考虑。

棋盘上显示频度(Display frequencies)*
　　棋盘上显示/不显示数据库棋步的频度。本功能只在对局和打谱模式下才有效。频度之和总是等于100%(除了舍入误差)。
　　不能和棋盘上显示胜率同时使用。


棋盘上显示胜率(Display winrates)*
　　棋盘上显示/不显示数据库棋步的胜率。本功能只在对局和打谱模式下才有效。胜率之和不一定等于100%。
　　不能和棋盘上显示频度同时使用。


显示人-人对局(Display human-human games)*
　　显示/不显示由人和人所下的对局。

显示人-机对局(Display human-program games)*
　　显示/不显示由人和程序所下的对局。

显示人-机对局(Display program-program games)*
　　显示/不显示由程序和程序所下的对局。

指定排序方式(Specifysorting order)*
　　指定包含当前棋局的对局如何排序，选项包括日期、黑棋棋手姓名、比赛名称等等。

显示前100项匹配(List first 100 matches)*
　　如果包含当前棋局的对局超过100个，那么只列出前100个。

显示前1000项匹配(List first 1000 matches)*
　　如果包含当前棋局的对局超过1000个，那么只列出前1000个匹配的对局。

dragoniye

导出(Export)子菜单
　　目前可以导出七种不同格式的文件:
文本文件(game as text)
　　生成一个包含当前对局所有信息的文本文件，其中包括对局双方所下全部棋步，以及Wzebra所下棋的估值、搜索深度、主要变化。当使用对局(Game)菜单的分析(Analyze game)工具进行分析时，文件会包含对局双方的实战棋步、Zebra所认为的最佳棋步以及其估值。

SGF文件(game as SGF)
　　采用标准对局格式(Standard Game Format)将导出对局。这种格式可以用在多种不同类型的对局中，详见这里。

网页文件(game as HTML)
　　生成一个包含对局棋谱、WZebra分析(如果分析过的话)的网页。可以用两种不同的方法来建立网页：
对局所下每步棋都显示一幅图片。
使用Java小程序来显示所下的每步棋。
　　导出网页实例：使用Java，不用Java。

　　注意：为了生成尽可能紧凑的网页，网页使用了JavaScript，这使它缩小2~10倍。据我所知，在所有主流浏览器上都能正确显示。


EPS文件(game as EPS)
　　生成一个描述当前对局所有棋步的EPS(Encapsulated PostScript，压缩PostScript)图形文件。

PNG文件(game as PNG)
　　生成一个描述当前对局所有棋步的PNG(Portable Network Graphics，可移植网络图像)图形文件。

盘面存为EPS文件(board as EPS)
　　生成一个描述当前盘面棋局的EPS(Encapsulated PostScript，压缩PostScript)图形文件。

盘面存为BMP文件(board as BMP)
　　生成一个描述当前盘面棋局的BMP(Windows位图)图形文件。

盘面存为PNG文件(board as PNG)
　　生成一个描述当前盘面棋局的PNG(Portable Network Graphics，可移植网络图像)图形文件。

dragoniye

打开(Load game)
　　打开一个先前由WZebra所保存的对局。

保存(Save game)
　　将对局保存到文件。

另存为(Save game as)
　　将对局另存到新的文件。

放弃(Release game)
　　将当前对局与所保存的文件分离开来。

文本输入(Enter game as text)
　　键入或粘贴一个黑白棋对局的棋谱文本，对局可以是完整也可是不完整的。语法相当宽松：用两个字符代表一步棋，第一个字符是字母A~H(或a~h)，第二个字符是数字1~8。

图谱输入(Enter game as transcript)
　　填入一个黑白棋对局的棋步序号，对局可以是完整也可是不完整的。第一步棋的序号是1，最多可以输入60步。棋步序号必须是连续的，中间不能有空缺。

导入(Import)子菜单
　　导入各种格式的文件。

导出(Export)子菜单
　　导出各种格式的文件。

退出(Exit)
　　退出程序。

dragoniye

功能(Function)子菜单
颜色随机选择(Zebra's color is chosen at random)
　　新开一个对局时，WZebra的颜色是随机选择的。

Zebra执黑(Zebra plays black)
　　对局时WZebra下黑棋。

Zebra执白(Zebra plays white)
　　对局时WZebra是下白棋。

Zebra旁观(Zebra observes)
　　WZebra只是分析棋盘上的棋局，但不下棋。这也是一种让WZebra分析棋局的方法。

Zebra休息(Zebra unactive)
　　WZebra休息，可能是在“数羊”(或者是在“数瞪羚”) 。通常这是用WZebra的棋盘来给两个人下棋。

复盘时进行分析(Spy on replay)
　　如果选中这个选项，在使用对局(Game)菜单中的复盘(Replay game)项进行复盘时， Zebra将会对全部棋局进行分析。

dragoniye

　　选用较大的棋局表会使WZebra下棋更快，但也消耗更多的内存。特定系统下的最佳设置取决于内存总量和同时运行的应用程序数量；如果出现(disc-swapping)情况，就必须减少棋局表的大小。
　　当搜索深度增加时，增加棋局表大小将变得更为重要。特别是在中局进行深度分析时，选用较大的棋局表能加速搜索。

　　菜单中可选的棋局表大小:

0.5MB
1MB
2MB
4MB
8MB
16MB
32MB
64MB
128MB
256MB


帮助(Help)菜单
关于(About)

显示版本号和编译日期。

目录(Contents)

在网页浏览器中打开帮助目录

dragoniye

导入(Import)子菜单
　　目前可以导入四种格式的文件:
文本文件(text game)
　　与文件(File)菜单中的文本输入(Enter game as text)相同，只不过棋谱文本是从文件中读取的。

PGN文件(PGN game)
　　导入一个采用可移植对局记录法(Portable Game Notation，Vinco Online Games所使用的格式)表示的对局。

SGF文件(SGF game)
　　导入一个采用标准对局格式(Standard Game Format)表示的对局。这种格式可以用在多种不同类型的对局中，详见这里。

GGF文件(GGF game)
　　导入一个采用通用对局格式(Generic Game Format)表示的对局，这是Generic Game Server所使用的格式。