3、异或(^) 0 1 0 1 1 0 0 1 ———— 1 1 0 0
4、取补(~) a = 0001，~a = 1110。 2.4 Java中位棋盘的实现 2.4.1 位棋盘类的实现
Java中，位棋盘用3个int型的数据表示，最高六位不用。Java中“与、或、非、异或、左位移，右位移（注意，位棋盘的右位移是无符号位移）”分别是“&、|、^、<<、>>>”。代码摘要（详细代码见附件）及相关说明如下：
public class BitBoard{
private int Low,Mid,Hi//用3个int字段表示位棋盘，最高位Hi的高//6位不用
public BitBoard(int Arg1, int Arg2, int Arg3) {//构造函数 }
public static BitBoard opAnd(BitBoard arg1,BitBoard arg2) {
//位棋盘的“与”操作，保存结果。 }
public static BitBoard opOr(BitBoard arg1,BitBoard arg2)
//位棋盘的“或”操作，保存结果。
public static BitBoard opXor(BitBoard arg1,BitBoard arg2)
//位棋盘的“异或”操作，保存结果。
public static int count(BitBoard arg) //计算位棋盘中非零位的个数
public static BitBoard duplicate(int arg) //复制位棋盘 public static boolean equals(BitBoard arg1,BitBoard arg2)
//位棋盘是否相等（所有90位对应的位相同即//为相等）
public static BitBoard leftShift(BitBoard arg,int num)
//位棋盘arg左位移num位
public static rightShift(BitBoard,int num) //位棋盘右位移num位
public static int LSB(BitBoard Arg) //位棋盘最低非0位的位置（从0开始计数）
public static int MSB(BitBoard Arg) //位棋盘最高非0位的位置（从0开始计数）
public static boolean notZero(BitBoard Arg) //是否非“0”。当90位中有非0位时返回true。
int low=arg1.Low & arg2.Low; int mid=arg1.Mid & arg2.Mid; int hi=arg1.Hi & arg2.Hi; return new BitBoard(low,mid,hi); Low = Arg1; Mid = Arg2; Hi = Arg3;
}
- 13 -
2.4.2 位棋盘的初始化
某些位棋盘从程序开始运行到结束都不会改变。例如上面所述的那个位棋盘数组“knight[90]”。(他实际上记录了当马在任意格子上时，它下一步可以走的格子。)这个数组将在程序开始执行的时候被初始化并且不再改变。其余的位棋盘将不断变化。例如“AllPieces”位棋盘。当中国象棋棋盘变化时，它也跟着变化。然而，他们的初始化方式相同。对于诸如knight[90]这样不变化的位棋盘的初始化，将在“伪着法生成”章节详述。此处叙述走棋过程中随棋局变化的诸多位棋盘的初始化及相关操作。
首先，初始化“BitBoard bitMask[90]”数组： BitBoard b = new BitBoard(0,0,1); for (int c = 0; c < 90; c ++) {
mask[c] = BitBoard.leftShift(b,c); }
其次，用一个叫 ChessPosition类记录棋盘上某一状态的所有有用信息。它包含了一个整型数组 int piece_in_square[90]，还包含了一些位棋盘。 public class ChessPosition {
int piece_in_square[90];
int player; //轮到哪方走棋，0：红方走，1：黑方走 BitBoard allPieces; BitBoard redKing;//红帅 BitBoard blackKing;//黑将 BitBoard redRooks;//红车 BitBoard blackRooks;//黑车 BitBoard redKnights;//红马 BitBoard blackKnights;//黑马 BitBoard redCannon;//红炮 BitBoard redCannon;//黑炮 BitBoard redBishops;//红相 BitBoard blackBishops;//黑象 BitBoard redAdvisor;//红仕 BitBoard blackAdvisor;//黑士 BitBoard redPawns;//红兵 BitBoard blackPawns;//黑卒
BitBoard redPieces;//所有红棋子 BitBoard blackPieces;//所有黑棋子 };
初始化“piece_in_square[]”数组。 piece_in_square[0] = RED_ROOK; piece_in_square[1] = RED_KNIGHT; piece_in_square[2] = RED_BISHOP; ?
piece_in_square[89] = BLACK_ROOK;
现在初始化其他一些位棋盘:
- 14 -
for (c = 0; c < 90; c ++) { switch (piece_in_square[c]) { case : RED_ROOK
position.redPieces = BitBoard.opOr(position.redPieces,bitMask[c]); position.redRooks
BitBoard.opOr(position.redRooks,bitMask[c]);
break; ? } }
2.4.3 位棋盘的更新
当棋盘局面变动后，某些位棋盘就需要被更新。例如记录白子所在位置的―WhitePieces‖位棋盘。假如我们把h2格的红炮移动到h9格（炮二进七），吃掉黑棋的一个马，需要更新如下位棋盘：
allPieces
redPieces redCannons blackpieces blackKnights
首先，要把redPieces，redCannons位棋盘的―h2‖位清零，然后把他们的―h9‖位置1。 /* clear a bit with the \
position.allPieces = BitBoard.opXor(position.allPieces,bitMask[h2]; position.redPieces = BitBoard.opXor(position.redPieces,bitMask[h2]); position.redCannons = BitBoard.opXor(position.redCannons,bitMask[h2]; /* set a bit with the \
position.redPieces = BitBoard.opOr(position.redPieces,bitMask[h9]); position.redCannons = BitBoard.opOr(position.redCannons,bitMask[h9]);
现在我们要将blackPieces和blackKnights位棋盘的h9位清除，因为那里的黑马被吃掉了。
/* clear the captured piece */
position.blackPieces = BitBoard.opXor(position.blackPieces,bitMask[h9]); position.blackKnight = BitBoard.opXor(position.blackPieces,bitMask[h9]
- 15 -
第三章 基本数据结构——Zobrist键值
3.1 比较局面的方法
在写中国象棋程序时，需要比较两个局面看它们是否相同。如果比较每个棋子的位置，或许不需要花很多时间，但是实战中每秒种需要做成千上万次比较，因此这样会使比较操作变成瓶颈的。另外，需要比较的局面数量多得惊人，要存储每个棋子的位置，需要占用非常大的空间。
一个解决方案是建立一个标签，通常是64位。由于64位不足以区别每个局面，所以仍然存在冲突的标签，但实战中这种情况非常罕见。 3.2 Zobrist键值的实现方法
实现Zobrist必须从多维的64位数组开始，每个数组含有一个随机数。在Java中，“rand.nextLong()”函数返回一个64位的随机数值。
这个函数用来填满一个long型（64位）的三维数组：棋子的类型、棋子的颜色和棋子的位置：
long zobrist[pcMAX][coMAX][sqMAX];
程序启动时就把这个数组用随机数填满。要为一个局面产生Zobrist键值，首先把键值设成零，然后找棋盘上的每个子，并且让键值跟“zobrist[pc][co][sq]”做异或(通过“^”运算符)运算。
如果局面由白方走，那么别去动它，如果是黑方走，你还要在键值上异或一个64位的随机常数。
3.3 Zobrist键值的工作原理及用途 3.3.1 Zobrist键值的工作原理
用Zobrist技术产生的键值，表面上跟局面没什么关系。如果一个棋子动过了，就会得到完全不同的键值，所以这两个键值不会挤在一块儿或者冲突。当把它们用作散列表键值的时候会非常有效。
另一个优点在于，键值的产生是可以逐步进行的。例如，红马在e5格，那么键值里一定异或过一个“zobrist[KNIGHT][RED][E5]”。如果再次异或这个值，那么根据异或的工作原理，这个马就从键值里删除了。
这就是说，如果有当前局面的键值，并且需要把红马从e5移到f7，你只要异或一个“红马在e5”的键值，把马从e5格移走，并且异或一个“红马在f7”的键值，把红马放在f7上。比起从头开始一个个棋子去异或，这样做可以得到同样的键值。
如果要改变着子的一方，只要异或一个“改变着子方”的键值就可以了。用这种方法，可以在搜索根结点的时候构造一个Zobrist键值，在搜索时通过走子函数“MakeMove()”来更新键值，一直让它保持和当前局面同步。
- 16 -
相关推荐：
loading