首页 > 编程学习 > 中国象棋采用128位整数通过位运算的算法探索(2)

书接上回,现在来讨论

棋子的走法

棋子的走法除了车、炮这两种步长没有限制的无法采用128位整数来表示外,其余均可以。
这里综合考虑棋子的固定走法较为单一,决定不再表示妻子的固定走法,直接在可以走的点位中写死。
这里是以前采用数组方式表示写算法的例子:

QList<QPoint> Chess::getPieceValidePos(const QPoint pos)
{
    QList<QPoint> result = {};
    int x = pos.x();
    int y = pos.y();
    PieceType piece = curGrid[x][y];
    if (piece == NU) return result;
    switch (piece) {
    case RB:
        if ((y+1 <= 9)&&(curGrid[x][y+1] <= NU)) { if (!mayKingWasArming(pos, QPoint(x,y+1), true)) result.append(QPoint(x,y+1)); }
        if (y > 4){
            if ((x-1 >= 0)&&(curGrid[x-1][y] <= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y), true)) result.append(QPoint(x-1,y));
            if ((x+1 <= 8 )&&(curGrid[x+1][y] <= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y), true)) result.append(QPoint(x+1,y));
        }
        break;
    case BB:
        if ((y-1 >= 0)&&(curGrid[x][y-1] >= NU))  if (!mayKingWasArming(pos, QPoint(x,y-1), false)) result.append(QPoint(x,y-1));
        if (y < 5){
            if ((x-1 >= 0)&&(curGrid[x-1][y] >= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y), false)) result.append(QPoint(x-1,y));
            if ((x+1 <= 8 )&&(curGrid[x+1][y] >= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y), false)) result.append(QPoint(x+1,y));
        }
        break;
    case RP:
        if (x+1 <= 8){
            int betweens = 0;
            for (int i = x + 1; i <= 8; i++){
                if ((betweens== 0 )&&(curGrid[i][y] == NU)) { if (!mayKingWasArming(pos, QPoint(i,y), true))  result.append(QPoint(i,y)); }
                else {
                    if ((betweens == 1)&&(curGrid[i][y] < NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), true)) result.append(QPoint(i,y)); }
                    if (curGrid[i][y] != NU) betweens++;
                }
            }
        }
        if (x-1 >= 0){
            int betweens = 0;
            for (int i = x - 1; i >= 0; i--){
                if ((betweens== 0 )&&(curGrid[i][y] == NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), true)) result.append(QPoint(i,y)); }
                else {
                    if ((betweens == 1)&&(curGrid[i][y] < NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), true)) result.append(QPoint(i,y)); }
                    if (curGrid[i][y] != NU) betweens++;
                }
            }
        }
        if (y+1 <= 9){
            int betweens = 0;
            for (int j = y + 1; j <= 9; j++){
                if ((betweens== 0 )&&(curGrid[x][j] == NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), true)) result.append(QPoint(x,j)); }
                else {
                    if ((betweens == 1)&&(curGrid[x][j] < NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), true)) result.append(QPoint(x,j)); }
                    if (curGrid[x][j] != NU) betweens++;
                }
            }
        }
        if (y-1 >= 0){
            int betweens = 0;
            for (int j = y - 1; j >= 0; j--){
                if ((betweens== 0 )&&(curGrid[x][j] == NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), true)) result.append(QPoint(x,j)); }
                else {
                    if ((betweens == 1)&&(curGrid[x][j] < NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), true)) result.append(QPoint(x,j)); }
                    if (curGrid[x][j] != NU) betweens++;
                }
            }
        }
        break;
    case BP:
        if (x+1 <= 8){
            int betweens = 0;
            for (int i = x + 1; i <= 8; i++){
                if ((betweens== 0 )&&(curGrid[i][y] == NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), false)) result.append(QPoint(i,y)); }
                else {
                    if ((betweens == 1)&&(curGrid[i][y] > NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), false)) result.append(QPoint(i,y)); } //仅本行" > NU"与RB不同
                    if (curGrid[i][y] != NU) betweens++;
                }
            }
        }
        if (x-1 >= 0){
            int betweens = 0;
            for (int i = x - 1; i >= 0; i--){
                if ((betweens== 0 )&&(curGrid[i][y] == NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), false)) result.append(QPoint(i,y)); }
                else {
                    if ((betweens == 1)&&(curGrid[i][y] > NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), false)) result.append(QPoint(i,y)); }
                    if (curGrid[i][y] != NU) betweens++;
                }
            }
        }
        if (y+1 <= 9){
            int betweens = 0;
            for (int j = y + 1; j <= 9; j++){
                if ((betweens== 0 )&&(curGrid[x][j] == NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), false)) result.append(QPoint(x,j)); }
                else {
                    if ((betweens == 1)&&(curGrid[x][j] > NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), false)) result.append(QPoint(x,j)); }
                    if (curGrid[x][j] != NU) betweens++;
                }
            }
        }
        if (y-1 >= 0){
            int betweens = 0;
            for (int j = y - 1; j >= 0; j--){
                if ((betweens== 0 )&&(curGrid[x][j] == NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), false)) result.append(QPoint(x,j)); }
                else {
                    if ((betweens == 1)&&(curGrid[x][j] > NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), false)) result.append(QPoint(x,j)); }
                    if (curGrid[x][j] != NU) betweens++;
                }
            }
        }
        break;
    case RC:
        if (x+1 <= 8){
            int betweens = 0;
            for (int i = x + 1; i <= 8; i++){
                if ((betweens== 0 )&&(curGrid[i][y] == NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), true)) result.append(QPoint(i,y)); }
                else {
                    if ((betweens == 0)&&(curGrid[i][y] < NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), true)) result.append(QPoint(i,y)); }
                    if (curGrid[i][y] != NU) betweens++;
                }
            }
        }
        if (x-1 >= 0){
            int betweens = 0;
            for (int i = x - 1; i >= 0; i--){
                if ((betweens== 0 )&&(curGrid[i][y] == NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), true)) result.append(QPoint(i,y)); }
                else {
                    if ((betweens == 0)&&(curGrid[i][y] < NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), true)) result.append(QPoint(i,y)); }
                    if (curGrid[i][y] != NU) betweens++;
                }
            }
        }
        if (y+1 <= 9){
            int betweens = 0;
            for (int j = y + 1; j <= 9; j++){
                if ((betweens== 0 )&&(curGrid[x][j] == NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), true)) result.append(QPoint(x,j)); }
                else {
                    if ((betweens == 0)&&(curGrid[x][j] < NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), true)) result.append(QPoint(x,j)); }
                    if (curGrid[x][j] != NU) betweens++;
                }
            }
        }
        if (y-1 >= 0){
            int betweens = 0;
            for (int j = y - 1; j >= 0; j--){
                if ((betweens== 0 )&&(curGrid[x][j] == NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), true)) result.append(QPoint(x,j)); }
                else {
                    if ((betweens == 0)&&(curGrid[x][j] < NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), true)) result.append(QPoint(x,j)); }
                    if (curGrid[x][j] != NU) betweens++;
                }
            }
        }
        break;
    case BC:
        if (x+1 <= 8){
            int betweens = 0;
            for (int i = x + 1; i <= 8; i++){
                if ((betweens== 0 )&&(curGrid[i][y] == NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), false)) result.append(QPoint(i,y)); }
                else {
                    if ((betweens == 0)&&(curGrid[i][y] > NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), false)) result.append(QPoint(i,y)); }
                    if (curGrid[i][y] != NU) betweens++;
                }
            }
        }
        if (x-1 >= 0){
            int betweens = 0;
            for (int i = x - 1; i >= 0; i--){
                if ((betweens== 0 )&&(curGrid[i][y] == NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), false)) result.append(QPoint(i,y)); }
                else {
                    if ((betweens == 0)&&(curGrid[i][y] > NU)) {  if (!mayKingWasArming(pos, QPoint(i,y), false)) result.append(QPoint(i,y)); }
                    if (curGrid[i][y] != NU) betweens++;
                }
            }
        }
        if (y+1 <= 9){
            int betweens = 0;
            for (int j = y + 1; j <= 9; j++){
                if ((betweens== 0 )&&(curGrid[x][j] == NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), false)) result.append(QPoint(x,j)); }
                else {
                    if ((betweens == 0)&&(curGrid[x][j] > NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), false)) result.append(QPoint(x,j)); }
                    if (curGrid[x][j] != NU) betweens++;
                }
            }
        }
        if (y-1 >= 0){
            int betweens = 0;
            for (int j = y - 1; j >= 0; j--){
                if ((betweens== 0 )&&(curGrid[x][j] == NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), false)) result.append(QPoint(x,j)); }
                else {
                    if ((betweens == 0)&&(curGrid[x][j] > NU)) {  if (!mayKingWasArming(pos, QPoint(x,j), false)) result.append(QPoint(x,j)); }
                    if (curGrid[x][j] != NU) betweens++;
                }
            }
        }
        break;
    case RM:
        if ((x-2 >= 0)&&(y-1 >= 0)&&(curGrid[x-1][y] == NU)&&(curGrid[x-2][y-1] <= NU))  if (!mayKingWasArming(pos, QPoint(x-2,y-1), true)) result.append(QPoint(x-2,y-1));
        if ((x-2 >= 0)&&(y+1 <= 9)&&(curGrid[x-1][y] == NU)&&(curGrid[x-2][y+1] <= NU))  if (!mayKingWasArming(pos, QPoint(x-2,y+1), true)) result.append(QPoint(x-2,y+1));
        if ((x-1 >= 0)&&(y-2 >= 0)&&(curGrid[x][y-1] == NU)&&(curGrid[x-1][y-2] <= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y-2), true)) result.append(QPoint(x-1,y-2));
        if ((x-1 >= 0)&&(y+2 <= 9)&&(curGrid[x][y+1] == NU)&&(curGrid[x-1][y+2] <= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y+2), true)) result.append(QPoint(x-1,y+2));
        if ((x+2 <= 8)&&(y-1 >= 0)&&(curGrid[x+1][y] == NU)&&(curGrid[x+2][y-1] <= NU))  if (!mayKingWasArming(pos, QPoint(x+2,y-1), true)) result.append(QPoint(x+2,y-1));
        if ((x+2 <= 8)&&(y+1 <= 9)&&(curGrid[x+1][y] == NU)&&(curGrid[x+2][y+1] <= NU))  if (!mayKingWasArming(pos, QPoint(x+2,y+1), true)) result.append(QPoint(x+2,y+1));
        if ((x+1 <= 8)&&(y-2 >= 0)&&(curGrid[x][y-1] == NU)&&(curGrid[x+1][y-2] <= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y-2), true)) result.append(QPoint(x+1,y-2));
        if ((x+1 <= 8)&&(y+2 <= 9)&&(curGrid[x][y+1] == NU)&&(curGrid[x+1][y+2] <= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y+2), true)) result.append(QPoint(x+1,y+2));
        break;
    case BM:
        if ((x-2 >= 0)&&(y-1 >= 0)&&(curGrid[x-1][y] == NU)&&(curGrid[x-2][y-1] >= NU))  if (!mayKingWasArming(pos, QPoint(x-2,y-1), false)) result.append(QPoint(x-2,y-1));
        if ((x-2 >= 0)&&(y+1 <= 9)&&(curGrid[x-1][y] == NU)&&(curGrid[x-2][y+1] >= NU))  if (!mayKingWasArming(pos, QPoint(x-2,y+1), false)) result.append(QPoint(x-2,y+1));
        if ((x-1 >= 0)&&(y-2 >= 0)&&(curGrid[x][y-1] == NU)&&(curGrid[x-1][y-2] >= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y-2), false)) result.append(QPoint(x-1,y-2));
        if ((x-1 >= 0)&&(y+2 <= 9)&&(curGrid[x][y+1] == NU)&&(curGrid[x-1][y+2] >= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y+2), false)) result.append(QPoint(x-1,y+2));
        if ((x+2 <= 8)&&(y-1 >= 0)&&(curGrid[x+1][y] == NU)&&(curGrid[x+2][y-1] >= NU))  if (!mayKingWasArming(pos, QPoint(x+2,y-1), false)) result.append(QPoint(x+2,y-1));
        if ((x+2 <= 8)&&(y+1 <= 9)&&(curGrid[x+1][y] == NU)&&(curGrid[x+2][y+1] >= NU))  if (!mayKingWasArming(pos, QPoint(x+2,y+1), false)) result.append(QPoint(x+2,y+1));
        if ((x+1 <= 8)&&(y-2 >= 0)&&(curGrid[x][y-1] == NU)&&(curGrid[x+1][y-2] >= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y-2), false)) result.append(QPoint(x+1,y-2));
        if ((x+1 <= 8)&&(y+2 <= 9)&&(curGrid[x][y+1] == NU)&&(curGrid[x+1][y+2] >= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y+2), false)) result.append(QPoint(x+1,y+2));
        break;
    case RX:
        if ((x-2 >= 0)&&(y-2 >= 0)&&(curGrid[x-1][y-1] == NU)&&(curGrid[x-2][y-2] <= NU))  if (!mayKingWasArming(pos, QPoint(x-2,y-2), true)) result.append(QPoint(x-2,y-2));
        if ((x-2 >= 0)&&(y+2 <= 4)&&(curGrid[x-1][y+1] == NU)&&(curGrid[x-2][y+2] <= NU))  if (!mayKingWasArming(pos, QPoint(x-2,y+2), true)) result.append(QPoint(x-2,y+2));
        if ((x+2 <= 8)&&(y-2 >= 0)&&(curGrid[x+1][y-1] == NU)&&(curGrid[x+2][y-2] <= NU))  if (!mayKingWasArming(pos, QPoint(x+2,y-2), true)) result.append(QPoint(x+2,y-2));
        if ((x+2 <= 8)&&(y+2 <= 4)&&(curGrid[x+1][y+1] == NU)&&(curGrid[x+2][y+2] <= NU))  if (!mayKingWasArming(pos, QPoint(x+2,y+2), true)) result.append(QPoint(x+2,y+2));
        break;
    case BX:
        if ((x-2 >= 0)&&(y-2 >= 5)&&(curGrid[x-1][y-1] == NU)&&(curGrid[x-2][y-2] >= NU))  if (!mayKingWasArming(pos, QPoint(x-2,y-2), false)) result.append(QPoint(x-2,y-2));
        if ((x-2 >= 0)&&(y+2 <= 9)&&(curGrid[x-1][y+1] == NU)&&(curGrid[x-2][y+2] >= NU))  if (!mayKingWasArming(pos, QPoint(x-2,y+2), false)) result.append(QPoint(x-2,y+2));
        if ((x+2 <= 8)&&(y-2 >= 5)&&(curGrid[x+1][y-1] == NU)&&(curGrid[x+2][y-2] >= NU))  if (!mayKingWasArming(pos, QPoint(x+2,y-2), false)) result.append(QPoint(x+2,y-2));
        if ((x+2 <= 8)&&(y+2 <= 9)&&(curGrid[x+1][y+1] == NU)&&(curGrid[x+2][y+2] >= NU))  if (!mayKingWasArming(pos, QPoint(x+2,y+2), false)) result.append(QPoint(x+2,y+2));
        break;
    case RS:
        if ((x-1 >= 3)&&(y-1 >= 0)&&(curGrid[x-1][y-1] <= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y-1), true)) result.append(QPoint(x-1,y-1));
        if ((x-1 >= 3)&&(y+1 <= 2)&&(curGrid[x-1][y+1] <= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y+1), true)) result.append(QPoint(x-1,y+1));
        if ((x+1 <= 5)&&(y-1 >= 0)&&(curGrid[x+1][y-1] <= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y-1), true)) result.append(QPoint(x+1,y-1));
        if ((x+1 <= 5)&&(y+1 <= 2)&&(curGrid[x+1][y+1] <= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y+1), true)) result.append(QPoint(x+1,y+1));
        break;
    case BS:
        if ((x-1 >= 3)&&(y-1 >= 7)&&(curGrid[x-1][y-1] >= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y-1), false)) result.append(QPoint(x-1,y-1));
        if ((x-1 >= 3)&&(y+1 <= 9)&&(curGrid[x-1][y+1] >= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y+1), false)) result.append(QPoint(x-1,y+1));
        if ((x+1 <= 5)&&(y-1 >= 7)&&(curGrid[x+1][y-1] >= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y-1), false)) result.append(QPoint(x+1,y-1));
        if ((x+1 <= 5)&&(y+1 <= 9)&&(curGrid[x+1][y+1] >= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y+1), false)) result.append(QPoint(x+1,y+1));
        break;
    case RK:
        if ((x-1 >= 3)&&(curGrid[x-1][y] <= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y), true)) result.append(QPoint(x-1,y));
        if ((x+1 <= 5)&&(curGrid[x+1][y] <= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y), true)) result.append(QPoint(x+1,y));
        if ((y-1 >= 0)&&(curGrid[x][y-1] <= NU))  if (!mayKingWasArming(pos, QPoint(x,y-1), true)) result.append(QPoint(x,y-1));
        if ((y+1 <= 2)&&(curGrid[x][y+1] <= NU))  if (!mayKingWasArming(pos, QPoint(x,y+1), true)) result.append(QPoint(x,y+1));
        break;
    case BK:
        if ((x-1 >= 3)&&(curGrid[x-1][y] >= NU))  if (!mayKingWasArming(pos, QPoint(x-1,y), false)) result.append(QPoint(x-1,y));
        if ((x+1 <= 5)&&(curGrid[x+1][y] >= NU))  if (!mayKingWasArming(pos, QPoint(x+1,y), false)) result.append(QPoint(x+1,y));
        if ((y-1 >= 0)&&(curGrid[x][y-1] >= NU))  if (!mayKingWasArming(pos, QPoint(x,y-1), false)) result.append(QPoint(x,y-1));
        if ((y+1 <= 2)&&(curGrid[x][y+1] >= NU))  if (!mayKingWasArming(pos, QPoint(x,y+1), false)) result.append(QPoint(x,y+1));
        break;
    case NU:
        break;
    }
    qDebug()<<"validPos:"<<result;
    return result;
}

这种采用数组的算法,虽然比较繁琐。但是其不但处理了可走点,还排除了限制点及走后送将的点位。送将通过函数“mayKingWasArming”判断。
从上面可以看出程序需要进行大量的判断和遍历,速度相比位运算肯定要低很多。

但是上面的算法是完善和正确的。

采用位移运算来得到棋子可走点位的算法。

伪代码如下:

__uint128_ getValidePos(const Piece &p)
{
	__uint128 kind = p & MASKKIND;
	__uint128 pos = p & MASKPOS;
	switch(kind){
	case RK:
	  ........
	  break;
	case RB:
	  ........
}

其中MASKKIND为棋子种类,即128位的高位32位,pos为低位90位。
先获取棋子种类,再判断棋子的可以走法。
这里算法同数组算法,不同的是之间的判断和运算均通过位运算获得。
具体新的位移代码,详见下一节。

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式