⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 其他策略——重复检测.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0057)http://www.elephantbase.net/computer/other_repetition.htm -->
<HTML><HEAD><TITLE>其他策略——重复检测</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2817" name=GENERATOR></HEAD>
<BODY background=其他策略——重复检测_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=隶书 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>　　我们有必要提一下重复和局的问题。如果棋局面<FONT face="Times New Roman">(</FONT>同一方走的情况下<FONT 
  face="Times New Roman">)</FONT>重复三次，就可以宣布和棋。如果程序领先一个车但是它陷入长将，那将是非常糟糕的，对手会在你即将取得胜利的时候宣布和棋。 

  <DT>　　要解决这个问题，就必须检测以前出现过的局面，并采取对策。如果程序懂得重复，它就可以根据盘面上局势的需要，来谋求重复或避免重复。如果程序即将输棋，那么它应该试图寻找长将，反之应该避免。 

  <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> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>一个相当麻烦的选择</STRONG></FONT> 
  <DT>　 
  <DT>　　有两种局面可能会重复：棋局的历史局面，即在棋局中盘面上走过的局面；搜索树局面，即程序搜索的路线上出现的局面，它们没有在盘面上出现过，但是程序的思考中会不断地撤消和执行着法。 

  <DT>　　很明显，搜索树中的重复局面应该能被立即检测出，并且会得到处理。一般来说会返回一个和局分值，但是我听说有些程序会在中局遇到长将时，如果程序一方在将军，就故意返回一个正值。这是为了说明，如果你能找到长将，那么局面通常会好些。如果搜索树中的重复没有被处理，那么程序就不会看到长将或其他重复和局的情况。 

  <DT>　　对于搜索树与棋局中局面出现的重复局面，该怎么做就不清楚了。如果某个局面在棋局中出现两次，在搜索中出现一次，那么应该当作和局处理，因为棋局中再出现一次就会和了。困难在于某个局面只在棋局中出现一次，在搜索树中也出现一次。 

  <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>4</FONT><FONT color=#0000ff>层。】</FONT> 
  <DT>　　我看过一些比赛的例子，其中一盘是<FONT 
  face="Times New Roman">GNUChess</FONT>对阵我的程序。有个能赢的王兵残局被<FONT 
  face="Times New Roman">GNUChess</FONT><FONT color=#0000ff>【</FONT><FONT 
  face="Times New Roman" color=#0000ff>WinBoard</FONT><FONT 
  color=#0000ff>自带的程序，源代码是公开的】</FONT>错过了，这两个程序就进入一系列和局局面。最后，他们又走回那个被<FONT 
  face="Times New Roman">GNUChess</FONT>错过的能赢的局面。我的程序很高兴看到这个重复局面，因为它是作为和局来评分的<FONT 
  face="Times New Roman">(</FONT>它已经出现在棋局的历史局面中<FONT 
  face="Times New Roman">)</FONT>。当然，第二次<FONT 
  face="Times New Roman">GNUChess</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">Greg 
  Kennedy</FONT>的人类大师。<FONT 
  face="Times New Roman">Kennedy</FONT>领先两个兵，但是他走了一步臭棋可以导致对手一马踏双，并能让对手得回一个兵。<FONT 
  face="Times New Roman">Kennedy</FONT>看到他的王被将军了，必须走他的王，他就把王走到原来待过的地方。然而我的程序走回了上一步，让局面回到两步前的样子，而没有通过吃兵来达到仅落后一个兵的局面。重复问题使得程序期待<FONT 
  face="Times New Roman">Kennedy</FONT>会把王走回来，并且让程序再对他一马踏双<FONT 
  color=#0000ff>【这样他的王就第三次回到原来的位置上了】</FONT>。当然他不会这么做，这样就让他继续领先两个兵了。 
  <DT>　　其他假设也是有可能的。一个很强的人类棋手发动了压倒性的进攻，但是后来没走好而让程序逃掉了王，因此人类棋手就只有长将了，因为他子力落后并没有杀棋。程序会乐于把王走回逃跑前原来的位置，因为这些位置是重复的并且会得到和局。<FONT 
  color=#0000ff>【被长将会导致和局，把王走回原来危险的位置也被程序认为是和局，如果程序选择了后者，就给了对手第二次尝试杀棋的机会。】</FONT> 

  <DT>　　我已经在我的程序里做了修改，忽略棋局中出现一次并且搜索树中出现一次的重复局面。这样就解决了上面提到的问题，但是带来了新的问题。 
  <DT>　　程序会把一个局面重复几次，这使得棋局有时非常烦琐。这可能会干扰人类对手，或者在电脑国际象棋比赛中干扰对手，因为棋局到达复杂残局时，可能不会有进展，并且可能周旋很长时间，从而离<FONT 
  face="Times New Roman">50</FONT>回合限制越来越近。<FONT 
  color=#0000ff>【人类棋手在棋局没有进展时，第二次出现重复局面就会握手言和，而采用这种策略的程序则不肯提和，这会让他的对手感到不舒服。】</FONT> 

  <DT>　　选择哪种做法，是需要斟酌的。<FONT 
  color=#0000ff>【从效率上说，第二次重复就返回和局分值的做法比较好，然而这种做法给了对手一个机会，当对手第一次犯错误时，第二次就有机会纠正了。】</FONT> 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>可能的实现</STRONG></FONT> 
  <DT>　 
  <DT>　　有很多方法可以检测重复。其中一个在<FONT face="Times New Roman">Tom Kerrigan</FONT>的<FONT 
  face="Times New Roman">TSCP</FONT>中使用，他把这个方法归功于<FONT 
  face="Times New Roman">John 
  Stanback</FONT>。在他的代码中他声明了这一点，但是没有任何详细的信息来告诉我们这是如何做的，因此我也不知道。如果你想知道它，就不得不到<FONT 
  face="Times New Roman">TSCP</FONT>的源程序中挖掘。 
  <DT>　　我能知道的实现方法已经在“<A 
  href="http://www.elephantbase.net/computer/struct_zobrist.htm"
12

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -