📄 数据结构——简介.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0053)http://www.elephantbase.net/computer/struct_intro.htm -->
<HTML><HEAD><TITLE>数据结构——简介</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="" name=Owner>
<META content="" name=Reply-To>
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=数据结构——简介_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT size=3>《对弈程序基本技术》专题</FONT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><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">David Eppstein */</FONT>文
</CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">* </FONT>加州爱尔文大学<FONT
face="Times New Roman">(UC Irvine)</FONT>信息与计算机科学系 </CENTER></DT></DIV>
<DT>
<DT> 要让机器下棋，程序首先必须对两个对象进行存储和操作，它们是局面和着法。这两个对象的表示使得程序可以进行下列操作：
<DT> <FONT face="Times New Roman">(1) </FONT>执行一个着法<FONT
face="Times New Roman">(</FONT>不仅仅是用户所指出的着法，而是在搜索过程中要用到的<FONT
face="Times New Roman">)</FONT>；
<DT> <FONT face="Times New Roman">(2) </FONT>撤消一个着法<FONT
face="Times New Roman">(</FONT>作用同上<FONT face="Times New Roman">)</FONT>；
<DT> <FONT face="Times New Roman">(3) </FONT>向用户显示棋盘；
<DT> <FONT face="Times New Roman">(4) </FONT>产生所有可能的着法；
<DT> <FONT face="Times New Roman">(5) </FONT>对棋盘的局面作出评估。
<DT> 除了显示棋盘以外，所有的操作都应该尽可能地迅速，因为它们会在搜索的循环内被调用。<FONT
face="Times New Roman">(</FONT>而显示棋盘的操作毕竟不是经常要做的。<FONT
color=#0000ff>【译注：在</FONT><FONT face="Times New Roman"
color=#0000ff>UCI</FONT><FONT color=#0000ff>协议</FONT><FONT
face="Times New Roman" color=#0000ff>(</FONT><FONT
color=#0000ff>国际象棋通用引擎协议</FONT><FONT face="Times New Roman"
color=#0000ff>)</FONT><FONT
color=#0000ff>中，引擎从不显示棋盘，因此这个操作事实上是多余的。】</FONT><FONT
face="Times New Roman">)</FONT>
<DT> 着法的内部表示应该是非常简洁的<FONT
face="Times New Roman">(</FONT>因为我们不需要花太多的时间来生成一系列着法<FONT
face="Times New Roman">)</FONT>而且能快速解读，但是非常重要的是，它应该能代表所有的着法！在国际象棋中，机器内典型的着法表示，就是记录移动棋子的起点格子和终点格子，例如王前兵进两格就表示为“<FONT
face="Times New Roman">e2e4</FONT>”<FONT
face="Times New Roman">(e2</FONT>代表这个兵起点位置而<FONT
face="Times New Roman">e4</FONT>代表终点位置<FONT
face="Times New Roman">)</FONT>。不管是否吃子，被吃的棋子都不必记录，因为它可以由终点格子来判断。在机器中位置能表示为<FONT
face="Times New Roman">6</FONT>位的数值，所以一个着法可以用<FONT
face="Times New Roman">2</FONT>个字节表示。尽管很多程序都是这样表示的，但是这种表示方法不足以表示所有的着法！王车易位时，有两个子要移动，此时我们把它当作特殊情况来考虑，只记录王的移动。问题在于，当兵从第七行走到第八行时，可以升变为后、车、马或象，上述表示方法不能让我们指定升变为哪个棋子。因此在设计着法表示时需要非常仔细，要确认这种表示能够涵盖棋局中所有可能发生的特殊情况。
<DT><FONT
color=#0000ff> 【一般而言，棋类的着法有两种形式，即添子式和移动式。五子棋、围棋、黑白棋等属于添子式，记录着法时只要记录棋子所下到的那个格子。其中五子棋最简单，下完的棋子不再会改变；黑白棋稍复杂些，下完的棋子可能会被后续着法所变换黑白，但每下一子棋盘上就多一子；围棋是最复杂的，由于存在提子的着法，所以局势是可逆的，打劫这样的着法需要很复杂的处理过程。</FONT>
<DT><FONT
color=#0000ff> 国际象棋和中国象棋都属于移动式，相比较而言中国象棋更简单，当一个棋子从起点移到终点时，只要简单地做一下终点的覆盖即可；而国际象棋由于三条特殊规则的存在而必须做特别处理，有时别的特殊位置的棋子要跟着移动</FONT><FONT
face="Times New Roman" color=#0000ff>(</FONT><FONT
color=#0000ff>王车易位</FONT><FONT face="Times New Roman"
color=#0000ff>)</FONT><FONT color=#0000ff>，有时别的特殊位置的子要被吃掉</FONT><FONT
face="Times New Roman" color=#0000ff>(</FONT><FONT
color=#0000ff>吃过路兵</FONT><FONT face="Times New Roman"
color=#0000ff>)</FONT><FONT color=#0000ff>，有时移动的棋子要被其他棋子所替代</FONT><FONT
face="Times New Roman" color=#0000ff>(</FONT><FONT
color=#0000ff>升变</FONT><FONT face="Times New Roman"
color=#0000ff>)</FONT><FONT color=#0000ff>。】</FONT>
<DT> 棋盘的表示可能稍许复杂了些，但也不应该太庞大。它必须包括所有相关的信息，而不仅仅是表观上的，但无关的信息不包括在其中。例如在国际象棋里，我们必须知道棋子在棋盘上的位置<FONT
face="Times New Roman">(</FONT>表观上的信息<FONT
face="Times New Roman">)</FONT>，而且需要知道一些不可见的信息——现在是谁在走，每方是否还有易位权，哪个过路兵可以吃，从吃子或进兵到现在一共走了多少步。我们还需要知道以前发生过哪些重复的局面<FONT
face="Times New Roman">(</FONT>因为三次重复局面即导致和棋<FONT
face="Times New Roman">)</FONT>，而不需要知道以前所有的着法。
<DT><FONT color=#0000ff> 【在网络通讯中常常用一种称为</FONT><FONT face="Times New Roman"
color=#0000ff>FEN</FONT><FONT color=#0000ff>串的</FONT><FONT
face="Times New Roman" color=#0000ff>6</FONT><FONT
color=#0000ff>段式代码来记录局面，在国际象棋中它的</FONT><FONT face="Times New Roman"
color=#0000ff>6</FONT><FONT
color=#0000ff>段代码依次为：棋盘、走子方、王车易位权、吃过路兵的目标格、可逆着法数以及总回合数，基本上涵盖了国际象棋某个局面的所有信息。但是</FONT><FONT
face="Times New Roman" color=#0000ff>FEN</FONT><FONT
color=#0000ff>字符串无法记录重复局面，因此</FONT><FONT face="Times New Roman"
color=#0000ff>UCI</FONT><FONT color=#0000ff>协议中规定，局面由棋局的最后一个不可逆局面</FONT><FONT
face="Times New Roman" color=#0000ff>(</FONT><FONT
color=#0000ff>发生吃子、进兵或升变的局面</FONT><FONT face="Times New Roman"
color=#0000ff>)</FONT><FONT color=#0000ff>和它的后续着法共同表示，这样就涵盖了重复局面的信息。】</FONT>
<DT>
<DT><FONT face=楷体_GB2312 size=5><STRONG>举例说明国际象棋中的诸多棋盘表示方法</STRONG></FONT>
<DT>
<DT> 国际象棋中有很多表示棋盘的方法，以下这些是程序中可能用到的：
<DT>
<DT><FONT face=楷体_GB2312 size=3><STRONG> </STRONG></FONT><FONT face=楷体_GB2312
size=4><STRONG>一、棋盘格子的</STRONG></FONT><FONT face=Arial
size=4><STRONG>8x8</STRONG></FONT><FONT face=楷体_GB2312
size=4><STRONG>数组</STRONG></FONT>
<DT> 每个格子的值代表格子中的棋子<FONT face="Times New Roman">(</FONT>例如：<FONT
face="Times New Roman">enum { empty, wK, wN, wB, wR, wQ, wP, bK, bN, bR, bQ,
bP })</FONT>。它的优点在于：<FONT face="Times New Roman">(1) </FONT>简单；<FONT
face="Times New Roman">(2) </FONT>容易计算子力价值：
<DD>
<DD>for (i = 0; i < 8; i ++)
<DD> for( j = 0; j < 8; j ++)
<DD> score += value[square[i, j]];
<DT>
<DT> 计算可能的着法有些麻烦但并不非常困难，可以找遍棋盘的每个格子，根据棋子的颜色和类型来做分枝：
<DD>
<DD>for (i = 0; i < 8; i++) {
<DD> for(j = 0; j < 8; j++) {
<DD> switch (board[i, j]) {
<DD> case wP:
<DD> if (board[i + 1, j] = empty) {
<DD> 生成到(i + 1, j)的着法;
<DD> }
<DD> if (i == 2 && board[i + 1, j] == empty && board[i + 2,
j] empty) {
<DD> 生成到(i + 2, j)的着法;
<DD> }
<DD> if (j > 0 && board[i + 1, j - 1]有黑子) {
<DD> 生成吃(i + 1, j - 1)子的着法;
<DD> }
<DD> if (j < 7 && board[i + 1, j + 1]有黑子) {
<DD> 生成吃(i + 1, j + 1)子的着法;
<DD> }
<DD> break;
<DD> ...
<DD> }
<DD> }
<DD>}
<DT>
<DT> 但是很多检测边界的判断<FONT face="Times New Roman">(</FONT>例如，兵在车一路就不能吃更外侧的子<FONT
face="Times New Roman">)</FONT>，使得代码非常复杂，速度非常缓慢。
<DT>
<DT><FONT face=楷体_GB2312><STRONG> </STRONG></FONT><FONT face=楷体_GB2312
size=4><STRONG>二、扩展数组</STRONG></FONT>
<DT> 包括扩展边界的<FONT face="Times New Roman">10x10</FONT>数组，在棋子类型中应包括“<FONT
face="Times New Roman">boundary</FONT>”这个值。这样就可以花很少的代价，来简化一些判断。<FONT
color=#0000ff>【在下面提到的</FONT><FONT face="Times New Roman"
color=#0000ff>0x88</FONT><FONT color=#0000ff>方法问世以前，最普遍的做法却是用</FONT><FONT
face="Times New Roman" color=#0000ff>12x12</FONT><FONT
color=#0000ff>的数组</FONT><FONT face="Times New Roman"
color=#0000ff>(</FONT><FONT color=#0000ff>即有双重的扩展边界</FONT><FONT
face="Times New Roman" color=#0000ff>)</FONT><FONT
color=#0000ff>，这样连马的着法也不用担心跳出棋盘了。】</FONT>
<DT>
<DT> <FONT face=楷体_GB2312 size=4><STRONG>三、</STRONG></FONT><FONT face=Arial
size=4><STRONG>0x88</STRONG></FONT>
<DT> 这个名称来自一个技巧——通过判断格子编码是否包含<FONT face="Times New Roman">136</FONT>这个数<FONT
face="Times New Roman">(</FONT>在<FONT
face="Times New Roman">16</FONT>进制中是<FONT
face="Times New Roman">0x88)</FONT>来检测着法是否合理。下表就是格子的编码<FONT
face="Times New Roman">(</FONT>用一个字节<FONT
face="Times New Roman">)</FONT>，高<FONT
face="Times New Roman">4</FONT>位表示行，低<FONT
face="Times New Roman">4</FONT>位表示列。 </DT></DL>
<DL>
<DD>
<TABLE border=1>
<TBODY>
<TR>
<TD align=middle bgColor=#ffffff><FONT
face="Times New Roman"><STRONG>120</STRONG></FONT></TD>
<TD align=middle bgColor=#000000><FONT face="Times New Roman"
color=#ffffff><STRONG>121</STRONG></FONT></TD>
<TD align=middle bgColor=#ffffff><FONT
face="Times New Roman"><STRONG>122</STRONG></FONT></TD>
<TD align=middle bgColor=#000000><FONT face="Times New Roman"
color=#ffffff><STRONG>123</STRONG></FONT></TD>
<TD align=middle bgColor=#ffffff><FONT
face="Times New Roman"><STRONG>124</STRONG></FONT></TD>
<TD align=middle bgColor=#000000><FONT face="Times New Roman"
color=#ffffff><STRONG>125</STRONG></FONT></TD>
<TD align=middle bgColor=#ffffff><FONT
face="Times New Roman"><STRONG>126</STRONG></FONT></TD>
<TD align=middle bgColor=#000000><FONT face="Times New Roman"
color=#ffffff><STRONG>127</STRONG></FONT></TD></TR>
<TR>
<TD align=middle bgColor=#000000><FONT face="Times New Roman"
color=#ffffff><STRONG>96</STRONG></FONT></TD>
<TD align=middle bgColor=#ffffff><FONT
face="Times New Roman"><STRONG>97</STRONG></FONT></TD>
<TD align=middle bgColor=#000000><FONT face="Times New Roman"
color=#ffffff><STRONG>98</STRONG></FONT></TD>
<TD align=middle bgColor=#ffffff><FONT
face="Times New Roman"><STRONG>99</STRONG></FONT></TD>
<TD align=middle bgColor=#000000><FONT face="Times New Roman"
color=#ffffff><STRONG>100</STRONG></FONT></TD>
<TD align=middle bgColor=#ffffff><FONT
face="Times New Roman"><STRONG>101</STRONG></FONT></TD>
<TD align=middle bgColor=#000000><FONT face="Times New Roman"
color=#ffffff><STRONG>102</STRONG></FONT></TD>
<TD align=middle bgColor=#ffffff><FONT
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -