3.3.2 Zobrist键值的用途
Zobrist键值通常用在散列键值当中，而散列键值在象棋程序里有以下几个作用： 1、用Zobrist键值来实现置换表。置换表是一个巨大的散列表，来保存以前搜索过的局面，这样可以节省很多搜索的时间。如果需要对某个局面搜索9层，可以从置换表中查找该局面，如果它已经搜索过9层，那么不必去重复搜索。置换表的另一个并不起眼的作用是，它可以帮助我们改善着法的顺序。
2、可以用Zobrist键值制造一个很小的散列表，来检测当前着法路线中有没有重复局面，以便发现长将或其他导致和局的着法。
3、可以用Zobrist键值创建支持置换的开局库。 3.4 Java中实现Zobrist键值
本系统使用一个key和一个lock结合来区分每个局面，这样发生冲突（即两个局面对应的key和lock一样）的概率几乎为0。示例代码及相关说明如下
1、填充数组。
上述的三维数组现在改变为二维（将颜色与棋子兵种类型合并） ??
public static long ZobristKeyPlayer;//改变走子方的key public static long ZobristLockPlayer;//改变走子方的lock public static long[][] ZobristKeyTable = new long[14][90]; public static long[][] ZobristLockTable = new long[14][90]; ?? static{ ??
zobristGen();
}
public static void zobristGen() { int i, j;
Random rand = new Random();
long RandSeed;
RandSeed = 1;
rand.setSeed(RandSeed);
ZobristKeyPlayer = rand.nextLong(); for (i = 0; i < 14; i ++) {
//0：红帅1：红仕2：红相3：红马4：红车5：红炮6：红兵 //7：黑将8：黑士9：黑象10：黑马11：黑车12：黑炮13：黑卒 for (j = 0; j < 90; j ++) {
ZobristKeyTable[i][j] = rand.nextLong(); } }
ZobristLockPlayer = rand.nextLong(); for (i = 0; i < 14; i ++) { for (j = 0; j < 90; j ++) {
ZobristLockTable[i][j] = rand.nextLong();
- 17 -
} } }
2、移子函数
当移动（添加、删除）一个棋子时，将当前局面的Zobrist键值与键值表中该棋子的键值进行异或操作，同时也与改变走子方的键值进行异或操作。 public class ChessPosition{ long ZobristKey, ZobristLock;
//当前局面的zobrist键值 public ChessPosition{ ??
ZobristKey=0;//初始化为0 ZobristLock=0; ?? } ??
public void makeMove(int Square, int Piece, boolean IsAdd) { ?? ZobristKey^=ZobristKeyTable[PieceType][Square];
ZobristLock^=ZobristLockTable[PieceType][Square]; ZobristKey ^= ZobristKeyPlayer;//改变走子方 ZobristLock ^= ZobristLockPlayer; ?? } }
3、开局库：开局库的实现，将在“搜索方法”中说明。
- 18 -
第四章 着法生成
着法生成在不同的象棋引擎中差异较大。本章使用位棋盘生成着法的基本原理。高级的国际象棋引擎通常具备一次只生成一小部分着法的能力。例如，仅生成象走的着法，马走的着法，“将”的着法，所有的吃子着法等等，这正是位棋盘的强项。那为什么用这种方式生成着法呢？原因是生成着法耗费一定的时间。如果引擎在检查了一部分着法后发现了必须走的棋，那它就无需生成余下的棋步了。因此，可能先生成所有吃子的着法，如果没有满意的棋再生成余下的着法。(用来减少耗时的着法生成策略很多——发挥你的想象力吧)。
大名鼎鼎的免费国际象棋引擎Crafty(其作者是Robert Hyatt博士)使用三个着法生成函数。一个用来生成所有伪合法吃子着法，一个生成所有伪合法不吃子着法，最后一个生成所有摆脱被将军状态的着法。注意前两个函数生成的是伪合法的着法。就是说，这些函数生成的着法并非都是合法的。例如，你要生成所有将军的着法并且发现了一步你想走的棋，但随后发现这步不合法再把它抛弃。这看起来很奇怪，但它确实比那种在所有局面下都严格生成合法着法的策略更快！Hyatt博士曾经这样解释：当国王被将时，你需要生成摆脱被将的着法，这时大部分生成的着法是不合法的，在这种局面中你使用生成所有合法着法的策略会帮你节省时间；但在大多数局面中，生成的着法都是合法的，推迟验证合法性会更有效率。
中国象棋的着法生成与此类似，先生成所有伪合法的着法，存入静态数组中。在对局中可以用“查表”的方式查找生成的伪着法，并对其合法性作出判断。这样可以节省大量的时间。 4.1伪合法着法的生成
伪合法着法包含几类： ? 各兵种的不吃子着法 ? 各兵种的吃子着法 ? “将”和摆脱“将”的着法
其中，马、相（象）、兵、帅（将）、仕（士）的吃子着法与其对应的不吃子着法规则相同。（伪合法着法并不考虑被吃的棋子的颜色——该棋子是对方的棋子还是己方的棋子，也不考虑该子是否能动，例如动了该子，双方的帅将会面。）炮和车的不吃子着法规则相同，但分为纵向横向行走两类。炮的吃子着法分为纵向和横向两类，车的吃子着法也分为纵向和横向两类。马和象的着法要考虑蹩马腿和塞象眼。将军的着法单独作为一类。
本程序使用静态数组存储生成的位合法着法，先对其作一些说明。
- 19 -
4.1.1 数组及其下标的含义
1、保存帅（将）、仕（士）、相（相）、马、兵的伪合法静态数组如下：
public static final int[][] KingMoves=new int[90][8]; public static final int[][] AdvisorMoves=new int[90][8]; public static final int[][] BishopMoves=new int[90][8]; public static final int[][] ElephantEyes=new int[90][4]; public static final int[][] KnightMoves=new int[90][12]; public static final int[][] HorseLegs=new int[90][8];
public static final int[][][] PawnMoves=new int[90][2][4];
第一个下标说明棋子所在的格，第二个下标含义不尽相同。帅（将）在某个位置最多有4种走法，例如KingMoves[13][0]=12表示帅在13格（e1格）时可以走到12格（当然，也可以走到14、4、22格，保存到其他几个数组元素中）。第5种（如果前面只有3种着法，则此处是第4种）保存的是非法着法即KingMoves[13][4]=-1，其作用作为查询算法的“哨兵”，提高查询算法的速度。为了速度（以位移运算取代除法运算），第2个坐标值用2的整次方幂。（在后面所讲的开局库和置换表的大小设置是2的整次方幂也是这个道理。）兵的走棋规则需要分颜色，红色的垂直走棋方向和黑色的垂直走棋方向是相反的。兵最多有三种走棋方法。AdvisorMoves[90][8]保存的是士的着法。BishopMoves[90][8]保存的是相（象）的着法，ElephanEyes[90][4]保存的是相（象）着法对应的塞象眼的位置。KnightMoves和HorseLegs是马的着法和蹩马腿的位置。
2、车、炮的伪合法着法静态数组如下：
- 20 -
public static final int[][][] FileNonCapMoves=new int[10][1024][12]; //共十条横线,FileNonCapMoves[y][bitWordY][index]=newY,进 public static final int[][][] FileRookCapMoves=new int[10][1024][4]; public static final int[][][] FileCannonCapMoves=new int[10][1024][4]; public static final int[][][] RankNonCapMoves=new int[9][512][12]; //RankNonCapMoves[x][bitWordX][index]=newX,平
public static final int[][][] RankRookCapMoves=new int[9][512][4]; public static final int[][][] RankCannonCapMoves=new int[9][512][4]; public static final int[][] FileNonCapMax=new int[10][1024]; //FileNonCapMax[y][bitwordY]=MaxY//进退
public static final int[][] FileNonCapMin=new int[10][1024]; //FileNonCapMax[y][bitwordY]=MinY
public static final int[][] FileRookCapMax=new int[10][1024]; public static final int[][] FileRookCapMin=new int[10][1024]; public static final int[][] FileCannonCapMax=new int[10][1024]; public static final int[][] FileCannonCapMin=new int[10][1024]; public static final int[][] RankNonCapMax=new int[9][512];//平
相关推荐：
loading