400行的象棋程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>
namespace abc { // abc: the basic facts about a particular subject | a basic chess | alpha beta chess
int _side; // 0:红 1:黑
enum { SHI=0, XIANG, PAWN, MA, PAO, CHE, KING=6 }; // 红子8~14, 黑子16~22, 无子0
inline int myPiece(int zi=0) { return  8 + (_side << 3) + zi; } // But who am I?
inline int yourZi (int zi=0) { return 16 - (_side << 3) + zi; } // ?:是if的马甲; if导致流水线不满
char _brd[256]; // 9x10的棋盘放在16x16的数组中, 左上角(3,3); 左上51, 右下203
enum { LEFT=3, TOP=3, BEGIN=TOP * 16 + LEFT, END=(TOP + 9) * 16 + LEFT + 9 };
int xytoi(int x, int y) { return (y << 4) + x; } // xy转下标(8位)
void printb() {
  static const char *D = "９８７６５４３２１０", *Z = "·11223344556677仕相兵马砲车帅15士象卒馬炮車將";
  puts(""); for (int y = 0; y < 10; y++) {
    printf("　%.2s", &D[y * 2]); // %.2s相当于%c%c
    for (int x = 0; x < 9; x++) printf("%.2s", &Z[_brd[xytoi(LEFT + x, TOP + y)] * 2]);
    puts("");
  } puts("　　ａｂｃｄｅｆｇｈｉ\n");
}
int _whereIs[24]; // 各个棋子在brd中的下标
#define Z16 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
const char POS_FLAG[256] = { Z16, Z16, Z16, // 位置标志
  0, 0, 0, 1, 1, 1, 9, 9, 9, 1, 1, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 9, 9, 9, 1, 1, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 9, 9, 9, 1, 1, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, // 以下红方
  0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 9, 9, 9, 1, 1, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 9, 9, 9, 1, 1, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 9, 9, 9, 1, 1, 1, // (11, 9)
};
inline int inBrd(int i) { return POS_FLAG[i]; }
inline int inJiugong(int i) { return POS_FLAG[i] == 9; }
inline int sameX(int i, int j) { return !((i ^ j) & 0x0f); } 
inline int sameY(int i, int j) { return !((i ^ j) & 0xf0); }
inline int forward(int i) { return i - 16 + (_side << 5); } // 红向上, 黑向下, 帅五进一和将５进１的进
inline int sameHalf(int i, int j) { return !((i ^ j) & 0x80); } // 相用这个
inline int guoHeLe(int i) { return (i & 0x80) == (_side << 7); } // 过河了; 兵只能用这个
inline int empty(int i) { return inBrd(i) && !_brd[i]; }
int c3toi(int x, int y) { // c3, c4这样的坐标是另一种xy
  x -= 'a'; if (x < 0 || x > 8) throw 0; x += LEFT; 
  y = 9 - (y - '0'); if (y < 0 || y > 9) throw 1; y += TOP;
  return xytoi(x, y);
}
void itoc3(int& x, int& y, int i) { x = ((i & 15) - LEFT) + 'a'; y = 9 - ((i >> 4) & 15) + TOP + '0'; }
inline int fold(int i) { return 254 - i; } // 黑方查POS_V时要颠倒
const int POS_V[7][256] = { // 棋子在不同位置的价值，注意要和棋子顺序一致
  { // 仕(士)
    Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16,
    0,  0,  0,  0,  0,  0, 20,  0, 20,  0,  0,  0,  0,  0,  0,  0,
    0,  0,  0,  0,  0,  0,  0, 23,  0,  0,  0,  0,  0,  0,  0,  0,
    0,  0,  0,  0,  0,  0, 20,  0, 20,
  }, { // 相(象)
    Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16,
    0,  0,  0,  0,  0, 20,  0,  0,  0, 20,  0,  0,  0,  0,  0,  0,
    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
    0,  0,  0, 18,  0,  0,  0, 23,  0,  0,  0, 18,  0,  0,  0,  0,
    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
    0,  0,  0,  0,  0, 20,  0,  0,  0, 20,  
  }, { // 兵(卒)
    Z16, Z16, Z16,
    0,  0,  0,  9,  9,  9, 11, 13, 11,  9,  9,  9,  0,  0,  0,  0,
    0,  0,  0, 19, 24, 34, 42, 44, 42, 34, 24, 19,  0,  0,  0,  0,
    0,  0,  0, 19, 24, 32, 37, 37, 37, 32, 24, 19,  0,  0,  0,  0,
    0,  0,  0, 19, 23, 27, 29, 30, 29, 27, 23, 19,  0,  0,  0,  0,
    0,  0,  0, 14, 18, 20, 27, 29, 27, 20, 18, 14,  0,  0,  0,  0,
    0,  0,  0,  7,  0, 13,  0, 16,  0, 13,  0,  7,  0,  0,  0,  0,
    0,  0,  0,  7,  0,  7,  0, 15,  0,  7,  0,  7,
  }, { // 马
    Z16, Z16, Z16, // 107的位置既可卧槽又可挂角; 河口象脚101; 中兵头顶103
    0,  0,  0, 90, 90, 90, 96, 90, 96, 90, 90, 90,  0,  0,  0,  0,
    0,  0,  0, 90, 96,103, 97, 94, 97,103, 96, 90,  0,  0,  0,  0,
    0,  0,  0, 92, 98, 99,103, 99,103, 99, 98, 92,  0,  0,  0,  0,
    0,  0,  0, 93,108,100,107,100,107,100,108, 93,  0,  0,  0,  0,
    0,  0,  0, 90,100, 99,103,104,103, 99,100, 90,  0,  0,  0,  0,
    0,  0,  0, 90, 98,101,102,103,102,101, 98, 90,  0,  0,  0,  0,
    0,  0,  0, 92, 94, 98, 95, 98, 95, 98, 94, 92,  0,  0,  0,  0,
    0,  0,  0, 93, 92, 94, 95, 92, 95, 94, 92, 93,  0,  0,  0,  0,
    0,  0,  0, 85, 90, 92, 93, 78, 93, 92, 90, 85,  0,  0,  0,  0,
    0,  0,  0, 88, 85, 90, 88, 90, 88, 90, 85, 88,
  }, { // 炮
    Z16, Z16, Z16, // 当头炮101; 天炮地炮都100
    0,  0,  0,100,100, 96, 91, 90, 91, 96,100,100,  0,  0,  0,  0,
    0,  0,  0, 98, 98, 96, 92, 89, 92, 96, 98, 98,  0,  0,  0,  0,
    0,  0,  0, 97, 97, 96, 91, 92, 91, 96, 97, 97,  0,  0,  0,  0,
    0,  0,  0, 96, 99, 99, 98,100, 98, 99, 99, 96,  0,  0,  0,  0,
    0,  0,  0, 96, 96, 96, 96,100, 96, 96, 96, 96,  0,  0,  0,  0,
    0,  0,  0, 95, 96, 99, 96,100, 96, 99, 96, 95,  0,  0,  0,  0,
    0,  0,  0, 96, 96, 96, 96, 96, 96, 96, 96, 96,  0,  0,  0,  0,
    0,  0,  0, 97, 96,100, 99,101, 99,100, 96, 97,  0,  0,  0,  0,
    0,  0,  0, 96, 97, 98, 98, 98, 98, 98, 97, 96,  0,  0,  0,  0,
    0,  0,  0, 96, 96, 97, 99, 99, 99, 97, 96, 96,
  }, { // 车
    Z16, Z16, Z16,
    0,  0,  0,206,208,207,213,214,213,207,208,206,  0,  0,  0,  0,
    0,  0,  0,206,212,209,216,233,216,209,212,206,  0,  0,  0,  0,
    0,  0,  0,206,208,207,214,216,214,207,208,206,  0,  0,  0,  0,
    0,  0,  0,206,213,213,216,216,216,213,213,206,  0,  0,  0,  0,
    0,  0,  0,208,211,211,214,215,214,211,211,208,  0,  0,  0,  0,
    0,  0,  0,208,212,212,214,215,214,212,212,208,  0,  0,  0,  0,
    0,  0,  0,204,209,204,212,214,212,204,209,204,  0,  0,  0,  0,
    0,  0,  0,198,208,204,212,212,212,204,208,198,  0,  0,  0,  0,
    0,  0,  0,200,208,206,212,200,212,206,208,200,  0,  0,  0,  0,
    0,  0,  0,194,206,204,212,200,212,204,206,194, 
  }, { // 帅(将)
    Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16,
    0,  0,  0,  0,  0,  0,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,
    0,  0,  0,  0,  0,  0,  2,  2,  2,  0,  0,  0,  0,  0,  0,  0,
    0,  0,  0,  0,  0,  0, 11, 15, 11 }
}; // 开局每方合计888
int _material[2]; // Material, a term determined by the sum of piece material of each side
inline int FROM(int mv) { return mv & 255; } // mv:move
inline int TO(int mv) { return (mv >> 8) & 255; }
inline int MV(int from, int to) { // 高16位用来排序。原则：将军优先, 大子先动
  int k = _whereIs[yourZi(KING)];
  int x = to & 15, y = to >> 4, x2 = k & 15, y2 = k >> 4;
  int d = abs(x2 - x) + abs(y2 - y);
  return ((20 - d) << 24) | (_brd[from] << 16) | (to << 8) | from;
}
int c3c4tomv(const char* s) { return MV(c3toi(*s, s[1]), c3toi(s[2], s[3])); }
char* mvtoc3c4(int mv, char* s=0) {
  static char buf[16]; s = s ? s : buf;
  if (mv & 0xffff) {
    int x, y, x2, y2; itoc3(x, y, FROM(mv)); itoc3(x2, y2, TO(mv));
    sprintf(s, "%c%c%c%c", x, y, x2, y2, mv >> 16);
  }
  else strcpy(s, "none");
  return s;
}

int genSortedMoves(int* mvs) { // 不检查将军
  // !(zi & mine): 不是自己子(即空白或对方子); (zi & yours): 对方子
  static const int DELTA_SHIZI[4] = { -16, -1, 1, 16 }; // 十字型移动, 帅车炮用
  static const int DELTA_XIE[4] = { -17, -15, 15, 17 }; // 斜十字型, 仕相用
  static const int LEG[4] = { -16, -1, 1, 16 }; // 马腿
  static const int TI[4][2] = { {-33, -31}, {-18, 14}, {-14, 18}, {31, 33} }; // 马蹄
  int i, n = 1, mine = myPiece(), yours = yourZi();  // 0100=红 1000=黑
  for (int from = BEGIN; from < END; from++) {
    int to, d, zi = _brd[from];
    if ((zi & mine) == 0) continue; // 不是己方棋子。0000=无 01xx=红 10xx=黑
    switch (int type = zi - mine) {
    case CHE:
      for (i = 0; i < 4; i++) {
        d = DELTA_SHIZI[i];
        for (to = from + d; inBrd(to); to += d) {
          if (const int zi = _brd[to]) {
            if (zi & yours) mvs[n++] = MV(from, to); // 吃子
            break; // 前方有子
          }
          else // 不吃子时继续移动
            mvs[n++] = MV(from, to);
        }
      }
      break;
    case PAO:
      for (i = 0; i < 4; i++) {
        d = DELTA_SHIZI[i];
        for (to = from + d; empty(to); to += d) { // 移动和找炮架
          mvs[n++] = MV(from, to);
        }
        for (to += d; empty(to); to += d); // 从炮架往后找
        zi = _brd[to];
        if (zi & yours) mvs[n++] = MV(from, to);
      }
      break;
    case MA:
      for (i = 0; i < 4; i++) { // 马最多有4*2=8种走法
        if (_brd[to = from + LEG[i]]) continue; // 马腿有子
        for (int j = 0; j < 2; j++) {
          if (!inBrd(to = from + TI[i][j])) continue;
          zi = _brd[to];
          if (!(zi & mine)) mvs[n++] = MV(from, to);
        }
      }
      break;
    case PAWN:
      if (inBrd(to = forward(from))) {
        zi = _brd[to];
        if (!(zi & mine)) mvs[n++] = MV(from, to);
      }
      if (guoHeLe(from)) {
        for (d = -1; d <= 1; d += 2) {
          if (inBrd(to = from + d)) {
            zi = _brd[to];
            if (!(zi & mine)) mvs[n++] = MV(from, to);
          }
        }
      }
      break;
    case XIANG:
       for (i = 0; i < 4; i++) {
        if (_brd[to = from + DELTA_XIE[i]]) continue; // 象眼有子
        zi = _brd[to += DELTA_XIE[i]]; // 继续向斜方向移动
        if (inBrd(to) && sameHalf(from, to)) {
          if (!(zi & mine)) mvs[n++] = MV(from, to);
        }
      }
      break;
    case KING:
      for (i = 0; i < 4; i ++) {
        if (!inJiugong(to = from + DELTA_SHIZI[i])) continue;
        zi = _brd[to];
        if (!(zi & mine)) mvs[n++] = MV(from, to);
      }
      for (to = forward(from); empty(to); to = forward(to));
      if (_brd[to] == yourZi(KING)) mvs[n++] = MV(from, to); // 老将不能见面用互相吃判断
      break;
    default: // case SHI:
      for (i = 0; i < 4; i ++) {
        if (!inJiugong(to = from + DELTA_XIE[i])) continue;
        zi = _brd[to];
        if (!(zi & mine)) mvs[n++] = MV(from, to);
      }
      break;
    } // switch
  }
  *mvs = INT_MAX; for (i = 2; i < n; i++) { // 几十个元素插入排序快
    int cur = mvs[i], j;
    for (j = i - 1; cur > mvs[j]; j--) mvs[j + 1] = mvs[j];
    mvs[j + 1] = cur;
  }
  //for (i = 1; i < n; i++) { printf("%s ", mvtoc3c4(mvs[i])); } puts("");
  return n - 1; // 用mvs[1..n]返回
}

inline void PutPiece(int i, int zi) { // assert(zi);
  _brd[i] = char(zi); _whereIs[zi] = i;
  if (zi < 16) _material[0] += POS_V[zi - 8][i];
  else _material[1] += POS_V[zi - 16][fold(i)];
}
inline void TakePiece(int i, int zi) { // assert(zi);
  _brd[i] = 0; _whereIs[zi] = 0;
  if (zi < 16) _material[0] -= POS_V[zi - 8][i];
  else _material[1] -= POS_V[zi - 16][fold(i)];
}

inline int makeMove(int mv) { // 返回后走棋方改变; 不检查将军
  int from = FROM(mv), to = TO(mv), zi = _brd[from], victim = _brd[to];
  if (victim) { TakePiece(to, victim); } TakePiece(from, zi); PutPiece(to, zi);
  _side ^= 1;
  return victim;
}
inline void unmakeMove(int mv, int victim) {
  _side ^= 1;
  int from = FROM(mv), to = TO(mv), zi = _brd[to];
  TakePiece(to, zi); PutPiece(from, zi); if (victim) PutPiece(to, victim);
}

// https://www.chessprogramming.org/Negamax The Evaluation function must return a score relative to the side to being evaluated.
// 比如车10分兵1分。红车和黑车相对，兵和卒相对。如果固定红-黑，回到root层后-1 > -10，那岂不成了吃兵好？
inline int eval() { return _side ? (_material[1] - _material[0]) : (_material[0] - _material[1]); }
enum { KING_MISSING=5555, CHECKMATE=999 };
int _bestMove;

int negMax(int d=0) { // depth +1
  if (!_whereIs[myPiece(KING)]) return -KING_MISSING;
  if (!_whereIs[yourZi(KING)]) return KING_MISSING;
  if (d == 3) return eval();
  int max = -INT_MAX;
  int mvs[128], n = genSortedMoves(mvs);
  for (int i = 1; i <= n; i++) {
    int mv = mvs[i], victim = makeMove(mv);
    int score = -negMax(d + 1);
    unmakeMove(mv, victim);
    if (score == -KING_MISSING) continue; // 自己老将被吃
    else if (score == KING_MISSING) score = CHECKMATE; // 对方老将被吃
    if (score > max) {
      max = score;
      if (d) continue; // ...generates all the root move... that is where you find the particular move attached to the score
      //printf("%6d %s\n", score, mvtoc3c4(mv));
      //_bestMove = mv;
    }
  }
  return max;
}

int alphaBeta(int a, int b, int d=0) { // https://www.chessprogramming.org/Alpha-Beta
  int best = -INT_MAX;
  if (d == 2) return negMax();
  int mvs[128], n = genSortedMoves(mvs);
  for (int i = 1; i <= n; i++) {
    int mv = mvs[i], victim = makeMove(mv);
    int score = -alphaBeta(-b, -a, d + 1);
    unmakeMove(mv, victim);
    if (score >= b) return score; // https://www.chessprogramming.org/Fail-Soft
    if (score > best) {
      best = score;
      if (score > a) {
        a = score;
        if (d) continue;
        printf("%6d %s\n", score, mvtoc3c4(mv));
        _bestMove = mv;
      }
    }
  }
  return best;
}

void ComputerGo() {
  _bestMove = 0;
  //int score = negMax(); // 别忘了uncomment negMax里的_bestMove = mv;
  int score = alphaBeta(-INT_MAX, INT_MAX);
  printf("%6d %s best\n", score, mvtoc3c4(_bestMove));
  if (score == -CHECKMATE) throw printf("电脑含笑认负。");
  else if (score == CHECKMATE) throw printf("你迟早会输。");
  if (_bestMove) makeMove(_bestMove);
  puts(""); printb();
}

bool inCheck(int mv) {
  int victim = makeMove(mv);
  bool inCheck = negMax() == CHECKMATE;
  unmakeMove(mv, victim);
  return inCheck;
}

bool isLegalMove(int mv) {
  static const char SSX[512] = { // 1=帅(将), 2=仕(士), 3=相(象)
    Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 
    0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 
    1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 
    0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 
    1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0,
    0, 0, 3, 
  };
  static const char BMT[512] = { // 蹩马腿。不是日字走法的为0. 不知道“蹩马腿”咋翻译，但不是Pin: An attack (by a Rook, Bishop or Queen) on a
    // piece that cannot or should not move, because a piece behind the attacked piece is worth even more.
    Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16, Z16,
    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, -16,  
    0,-16,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, -1,  0,  
    0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, -1,  0,  
    0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 16, 
    0, 16,  
  };
  int mine = myPiece(), i;
  int from = FROM(mv), to = TO(mv), zFrom = _brd[from], zTo = _brd[to]; // z:子
  if (!(zFrom & mine) || (zTo & mine)) return false; // 不是走自己的子, 或吃自己的子
  switch (int type = zFrom - mine) {
  case KING:  return (SSX[to - from + 256] == 1) && inJiugong(to);
  case SHI:   return (SSX[to - from + 256] == 2) && inJiugong(to);
  case XIANG: return (SSX[to - from + 256] == 3) && sameHalf(from, to) &&
              !_brd[(from + to) >> 1]; // 象眼, “并行计算”(x0+x1)/2和(y0+y1)/2
  case MA:
    i = from + BMT[to - from + 256];
    return (i != from) && empty(i); // 马腿无子?
  case CHE: case PAO: {
    int d;
    if (sameY(from, to)) d = (to < from ? -1 : 1); // Y相同时在X方向移动
    else if (sameX(from, to)) d = (to < from ? -16 : 16); // X相同时在Y方向移动
    else return false; // 车炮不走直线
    for (i = from + d; (i != to) && empty(i); i += d); // 遇到to或任意一方棋子停止
    if (i == to) return ((CHE == type) || !zTo); // 无论to处有无子,车都可以到(移动或吃); 无子则炮可移到
    else if ((PAO == type) && zTo) { // 不能隔着炮架打空气
      for (i += d; (i != to) && empty(i); i += d); // 找到炮架后第一个子
      return (i == to);
    } else return false;
  }
  default: // case PAWN:
    if (guoHeLe(to) && (to == from - 1 || to == from + 1)) return true;
    return (to == forward(from));
  }
}

void ManGo() {
  for (;;) try {
    char s[80] = ""; printf("输入黑棋走法: "); strlwr(gets(s));
    if (*s == 'q') exit(0);
    int mv = c3c4tomv(s);
    if (isLegalMove(mv) && !inCheck(mv)) { makeMove(mv); break; }
  } catch(int) {}
}

int fen_atoi(int c) {
  switch (tolower(c)) {
  case 'k': return KING; case 'a': return SHI; case 'b': return XIANG; case 'n': return MA;
  case 'r': return CHE;  case 'c': return PAO; case 'p': return PAWN;  default: throw 1;
  }
}

void Init() {
  puts("电脑走红棋，你走黑棋(將象士車馬炮卒)");
  const char* s = "rnbakab2/9/1c2c1n2/p1p1p1p1p/9/9/P1P1P1PrP/1C2C1N2/3R5/RNBAKAB2 w - - 0 2";
  //const char* s = "4ka2n/4a4/3c5/9/9/9/R5C2/9/9/4K4";
  //const char* s = "3k5/9/2R1R4/9/9/9/9/9/9/5K3";
  //const char* s = "3k5/9/9/9/9/9/2R6/9/9/4K4";
  //const char* s = "4k4/9/9/6r2/9/9/9/9/9/5K3";
  //const char* s = "3k5/9/9/9/9/p8/8P/9/9/4K4 w - - 0 2";
  for (int y = TOP, x = LEFT; *s && *s != ' '; ++s) {
    const char c = *s;
    if (c == '/') (x = LEFT, ++y);
    else if (c >= '1' && c <= '9') x += c - '0';
    else _brd[xytoi(x++, y)] = char((c >= 'a' ? 16 : 8) + fen_atoi(c));
  }
  for (int i = BEGIN; i < END; i++) { if (char zi = _brd[i]) PutPiece(i, zi); }
  printb();
}
} // namespace abc
using namespace abc;
int main() {
  try { for(Init();;ComputerGo(),ManGo()); } catch(int){}
  printf("按回车键退出。"); getchar(); return 0;
}