📄 数据结构——zobrist键值.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://www.elephantbase.net/computer/struct_zobrist.htm -->
<HTML><HEAD><TITLE>数据结构——Zobrist键值</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=数据结构——Zobrist键值_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT>《对弈程序基本技术》专题 </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face=Arial size=6><STRONG>Zobrist</STRONG></FONT><FONT face=隶书
size=6>键值</FONT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">Bruce Moreland (</FONT><A
href="mailto:brucemo@seanet.com"><FONT
face="Times New Roman">brucemo@seanet.com</FONT></A><FONT
face="Times New Roman">) /</FONT> 文 </CENTER></DT></DIV>
<DT>
<DT><FONT face=楷体_GB2312 size=5><STRONG>比较局面的方法</STRONG></FONT>
<DT>
<DT> 国际象棋局面包含了棋盘上的棋子、哪一方走棋、是否能易位、是否能吃过路兵等信息。
<DT> 在写国际象棋的程序时，需要比较两个局面看它们是否相同。如果你比较每个棋子的位置，或许不需要花很多时间，但是实战中你每秒种需要做成千上万次比较，因此这样会使比较操作变成瓶颈的。另外，需要比较的局面数量多得惊人，要存储每个棋子的位置，需要占用非常大的空间。
<DT> 一个解决方案是建立一个标签，通常是<FONT face="Times New Roman">64</FONT>位。由于<FONT
face="Times New Roman">64</FONT>位不足以区别每个局面，所以仍然存在冲突的标签。但是实战中这种情况非常罕见，你可以有充分的把握不会发生冲突。
<DT> 用<FONT face="Times New Roman">32</FONT>位是否足够，目前争论很多，而用<FONT
face="Times New Roman">64</FONT>位通常是明智的。
<DT> <FONT face="Times New Roman">Zobrist</FONT>键值是一个常用的建立标签的方法。
<DT>
<DT><FONT face=楷体_GB2312 size=5><STRONG>实现</STRONG></FONT>
<DT>
<DT> 你必须从多维的<FONT face="Times New Roman">64</FONT>位数组开始，每个数组含有一个随机数。在<FONT
face="Times New Roman">C</FONT>语言中，“<FONT
face="Times New Roman">rand()</FONT>”函数返回一个<FONT
face="Times New Roman">15</FONT>位的值<FONT
face="Times New Roman">(0~32767)</FONT>，所以要得到<FONT
face="Times New Roman">64</FONT>位的随机数还需要再加工一下。实际上我已经为你做好了，这个<FONT
face="Times New Roman">64</FONT>位随机数的函数是：
<DD>
<DD>U64 rand64(void) {
<DD> return rand() ^ ((U64)rand() << 15) ^ ((U64)rand() << 30) ^
((U64)rand() << 45) ^ ((U64)rand() << 60);
<DD>}
<DT>
<DT> 这个函数用来填满一个“<FONT face="Times New Roman">U64</FONT>”的元素<FONT
face="Times New Roman">(</FONT>你需要自己来定义这个类型，这取决于你的编译器，试一下“<FONT
face="Times New Roman">long long</FONT>”或者“<FONT
face="Times New Roman">__int64</FONT>”<FONT
face="Times New Roman">)</FONT>，它是通过调用一系列“<FONT
face="Times New Roman">rand()</FONT>”来实现的。
<DT> 无论如何你的数组要有三维：棋子的类型、棋子的颜色和棋子的位置：
<DD>
<DD>U64 zobrist[pcMAX][coMAX][sqMAX];
<DT>
<DT> 程序启动时就把这个数组用随机数填满，随机数是必须非常随机的，我看到<FONT
face="Times New Roman">Usenet(</FONT>新闻组网络系统<FONT
face="Times New Roman">)</FONT>上很多人说“<FONT
face="Times New Roman">rand()</FONT>”用在这里随机性不是很好，但是我一直都用“<FONT
face="Times New Roman">rand()</FONT>”并且没有出现问题。如果你想使数组更随机，就去找更强大的随机函数，但是你要确保它的随机性不比“<FONT
face="Times New Roman">rand()</FONT>”差。
<DT> 要为一个局面产生<FONT
face="Times New Roman">Zobrist</FONT>键值，首先把键值设成零，然后找棋盘上的每个子，并且让键值跟“<FONT
face="Times New Roman">zobrist[pc][co][sq]</FONT>”做异或<FONT
face="Times New Roman">(</FONT>通过“<FONT
face="Times New Roman">^</FONT>”运算符<FONT face="Times New Roman">)</FONT>运算。
<DT> 如果局面由白方走，那么别去动它，如果是黑方走，你还要在键值上异或一个<FONT
face="Times New Roman">64</FONT>位的随机常数。
<DT>
<DT><FONT face=楷体_GB2312 size=5><STRONG>为什么</STRONG></FONT><FONT face=Arial
size=5><STRONG>Zobrist</STRONG></FONT><FONT face=楷体_GB2312
size=5><STRONG>键值特别有用</STRONG></FONT>
<DT>
<DT> 用<FONT
face="Times New Roman">Zobrist</FONT>技术产生的键值，表面上跟局面没什么关系。如果一个棋子动过了，你会得到完全不同的键值，所以这两个键值不会挤在一块儿或者冲突。当你把它们用作散列表键值的时候会非常有效。
<DT> 另一个优点在于，键值的产生是可以逐步进行的。例如，你的白兵在<FONT
face="Times New Roman">e5</FONT>格，那么键值里一定异或过一个“<FONT
face="Times New Roman">zobrist[PAWN][WHITE][E5]</FONT>”。如果你再次异或这个值，那么根据异或的工作原理，这个兵就从键值里删除了。
<DT> 这就是说，如果你有当前局面的键值，并且需要把白兵从<FONT face="Times New Roman">e5</FONT>移到<FONT
face="Times New Roman">e6</FONT>，你只要异或一个“白兵在<FONT
face="Times New Roman">e5</FONT>”的键值，把兵从<FONT
face="Times New Roman">e5</FONT>格移走，并且异或一个“白兵在<FONT
face="Times New Roman">e6</FONT>”的键值，把兵放在<FONT
face="Times New Roman">e6</FONT>上。比起从头开始一个个棋子去异或，这样做可以得到同样的键值。
<DT> 如果你要改变着子的一方，只要异或一个“改变着子方”的键值就可以了。你可以用类似的方法处理王车易位和吃过路兵的标志。
<DT> 用这种方法，你可以在搜索根结点的时候构造一个<FONT
face="Times New Roman">Zobrist</FONT>键值，在搜索时通过走子函数“<FONT
face="Times New Roman">MakeMove()</FONT>”来更新键值，一直让它保持和当前局面同步。
<DT>
<DT><FONT face=Arial size=5><STRONG>Zobrist</STRONG></FONT><FONT
face=楷体_GB2312 size=5><STRONG>键值的用途</STRONG></FONT>
<DT>
<DT> <FONT
face="Times New Roman">Zobrist</FONT>键值通常用在散列键值当中，而散列键值在国际象棋程序里有以下几个作用：
<DT> <FONT face="Times New Roman">(1) </FONT>用<FONT
face="Times New Roman">Zobrist</FONT>键值来实现置换表。置换表是一个巨大的散列表，来保存以前搜索过的局面，让你节省很多搜索的时间。如果你需要对某个局面搜索<FONT
face="Times New Roman">9</FONT>层，你可以从置换表中查找该局面，如果它已经搜索过<FONT
face="Times New Roman">9</FONT>层，那么你不必去重复搜索。置换表的一个并不起眼的作用是，它可以帮助你改善着法的顺序。
<DT> <FONT face="Times New Roman">(2) </FONT>用<FONT
face="Times New Roman">Zobrist</FONT>键值来实现兵型的散列表。你可以用一个键值只记录棋盘上的兵，对兵型做了很复杂的分析后，在散列表中记录分析的结果。在实战中兵型是很少发生变化的，所以这个散列表的命中率会非常高，它可以为你评估兵型节省很多时间。
<DT> <FONT face="Times New Roman">(3) </FONT>可以用<FONT
face="Times New Roman">Zobrist</FONT>键值制造一个很小的散列表，来检测当前着法路线中有没有重复局面，以便发现长将或其他导致和局的着法。
<DT> <FONT face="Times New Roman">(4) </FONT>可以用<FONT
face="Times New Roman">Zobrist</FONT>键值创建支持置换的开局库。
<DT>
<DT> 原文：<A href="http://www.seanet.com/~brucemo/topics/zobrist.htm"
target=_blank><FONT
face="Times New Roman">http://www.seanet.com/~brucemo/topics/zobrist.htm</FONT></A>
<DT> 译者：黄晨 <FONT face="Times New Roman">(</FONT><A
href="mailto:webmaster@elephantbase.net"><FONT
face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT
face="Times New Roman">)</FONT>
<DT> 类型：全译 </DT></DL>
<DIR>
<LI>上一篇 <A
href="http://www.elephantbase.net/computer/struct_0x88.htm">数据结构——<FONT
face="Times New Roman">0x88</FONT>着法产生方法</A>
<LI>下一篇 <A
href="http://www.elephantbase.net/computer/search_intro1.htm">基本搜索方法——简介<FONT
face="Times New Roman">(</FONT>一<FONT face="Times New Roman">)</FONT></A>
<LI>返 回 <A href="http://www.elephantbase.net/computer.htm">象棋百科全书——电脑象棋</A>
</LI></DIR>
<DIV align=center>
<CENTER>
<TABLE border=0>
<TBODY>
<TR>
<TD>
<P align=center><A href="http://www.elephantbase.net/" target=_blank><IMG
height=31 src="数据结构——Zobrist键值_files/elephantbase.gif" width=88
border=0></A></P></TD></TR>
<TR>
<TD><A href="http://www.elephantbase.net/" target=_blank><FONT face=Arial
size=2><STRONG>www.elephantbase.net</STRONG></FONT></A></TD></TR></TBODY></TABLE></CENTER></DIV></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -