全部671行(不計最后空行)，不是只有界面，界面很簡陋：
原始碼就一個.cpp:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #include "stdint.h" enum { KING = 0, SHI, XIANG, MA, CHE, PAO, PAWN }; // 紅子為8+x, 黑子為16+x; 8=帥, 22=卒 inline int MyFirstZi(int sd) { return 8 + (sd << 3); } // zi:子; sd:side inline int YourFirstZi(int sd) { return 16 - (sd << 3); } char _brd[256]; // 9x10的棋盤放在16x16的陣列中, 左上角為(3,3); brd:board enum { LEFT = 3, TOP = 3, BEGIN = TOP * 16 + LEFT, END = (TOP + 9) * 16 + LEFT + 9 }; inline int XY2SQ(int x, int y) { return x + (y << 4); } // sq:square, 國際象棋的方格=象棋的交叉點 void PrintBoard() { static char *D = "９８７６５４３２１０", *Z = "·１２３４５６７帥仕相馬車炮兵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[XY2SQ(LEFT + x, TOP + y)] * 2]); puts(""); } puts(" ａｂｃｄｅｆｇｈｉ\n"); } #define Z16 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 const char Z_POS_FLAG[256] = { Z16, Z16, Z16, // 棋子(z)位置(Position)標志 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, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, }; inline int InBrd(int sq) { return Z_POS_FLAG[sq]; } inline int InJiugong(int sq) { return Z_POS_FLAG[sq] == 9; } inline int Empty(int sq) { return InBrd(sq) && !_brd[sq]; } // 0=沒有棋子 inline int GuoHeLe(int sq, int sd) { return (sq & 0x80) == (sd << 7); } // 過河了, (square, side), 兵只能用這個 inline int SameHalf(int from, int to) { return !((from ^ to) & 0x80); } // (square, square), 相用這個 inline int SameX(int sq, int sq2) { return !((sq ^ sq2) & 0x0f); } inline int SameY(int sq, int sq2) { return !((sq ^ sq2) & 0xf0); } inline int Up(int sq, int sd) { return sq - 16 + (sd << 5); } // 紅向上, 黑向下 inline int MOVE(int from, int to) { return int(from | (to << 8)); } inline int FROM(int mv) { return mv & 255; } // mv=move inline int TO(int mv) { return mv >> 8; } inline int Flip(int sq) { return 254 - sq; } // 黑方查Z_POS_VL時要顛倒，左上51, 右下203 const uint8_t Z_POS_VL[7][256] = { // 棋子在不同位置的價值 { // 帥(將) 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, }, { // 仕(士) 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, // 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, 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, // 當頭炮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, 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, } }; template<typename T>inline void Swap(T& a, T& b) { T t = a; a = b; b = t; } struct ZNum { // Invented by Albert Zobrist, Zobrist Hashing is to get an almost unique index number for any position uint64_t n; ZNum() { static RC4PRGA rc4; n = rc4.Next(); for (int i = 0; i < 7; i++) n = (n << 8) | rc4.Next(); } // n為0的概率非常低 operator const uint64_t () const { return n; } void operator^= (const ZNum &z) { n ^= z.n; } // xor-operation is own inverse and can be undone struct RC4PRGA { // RC4 Pseudo-Random Generation Algorithm int s[256], i, j; // 我們只需要ZNum盡量不同，key不變程式的行為不變, 便于除錯，搜索結果和搜索時間有關，不一定是改錯了程式(但一般是) RC4PRGA(const char* key = "https://www.geeksforgeeks.org/what-is-rc4-encryption/") { int len = strlen(key); for (i = 0; i < 256; i++) s[i] = i; for (i = 0; i < 256; i++) { j = (j + s[i] + key[i % len]) & 255; Swap(s[i], s[j]); } i = j = 0; } int Next(); }; }; int ZNum::RC4PRGA::Next() { i = (i + 1) & 255; j = (j + s[i]) & 255; Swap(s[i], s[j]); return s[(s[i] + s[j]) & 255]; } ZNum _zn; // 當前局面的ZNum ZNum BLACK_ZN; // 局面資訊含“該誰走”，0=紅, 1=黑，^BLACK_ZN得黑, 再^去掉黑——紅 // 每方7種棋子，雖然...most recent x86 chips...imul instruction...3 cycles, 但*8(hopefully << 3)總不會比*7慢? ZNum ZN_TBL[2][8][256]; // [紅黑][棋子型別][square] int _side; // 該誰走 int _redVl, _blackVl; // 雙方子力價值，vl:value int _stop, _bestMove; // 停止搜索, 最佳著法 unsigned _nTotalMove; // 搜索了多少步, 每步對應1個新局面 clock_t _startTime, _endTime; struct Position { uint64_t zn; int mv; // 從上個局面到本局面的move, 可用于對局結束后print int victim; // 從上個局面到本局面時被吃的子, 用于檢查重復局面(吃子就不算重復) int check; // 本局面要走棋的一方是否被將軍 void Set(int m, int v, int c, uint64_t zn_) { mv = m; victim = v; check = c; zn = zn_; } } _pstack[200]; // _pstack存放人走-電腦走-人走...的局面，nPos: number of positions. 搜索時不破壞已走局面, 在后面追加distance個, 結束后洗掉， // _表示是全域變數，nPos和distance像是stack frame的bp (base pointer)和sp (stack pointer). distance是sp - bp. int _distance, _nPos; inline int LastPositionInCheck() { return _pstack[_nPos - 1].check; } inline void SwitchSide() { _side ^= 1; _zn ^= BLACK_ZN; } int InCheck() { static const int DELTA_SHIZI[4] = { -16, -1, 1, 16 }; // 十字型移動, 帥車炮用 int i, k = 0; // 將(帥)的位置，TODO: 記錄而不是每次找 if (char* p=(char*)memchr(_brd + 0, MyFirstZi(_side) + KING, 256)) k = p - _brd; if (!k) return 0; int yours = YourFirstZi(_side), pawn = yours + PAWN; if (_brd[Up(k, _side)]==pawn || _brd[k-1]==pawn || _brd[k+1]==pawn) return 1; // 被兵(卒)將 for (i = 0; i < 4; i++) { // 被馬將? static const int tui[4] = { -17, -15, 15, 17 }; // 腿 static const int ma[4][2] = { {-33, -18}, {-31, -14}, {14, 31}, {18, 33} }; // 馬 if (_brd[k + tui[i]]) continue; // 蹩腿 for (int j = 0; j < 2; j++) if (_brd[k + ma[i][j]] == yours + MA) return 1; } for (i = 0; i < 4; i++) { // 被車或炮將或將帥對臉? int to, d = DELTA_SHIZI[i]; for (to = k + d; Empty(to); to += d); if (_brd[to] == yours || _brd[to] == yours + CHE) return 1; // KING=0 for (to += d; Empty(to); to += d); // 向炮架后找 if (_brd[to] == yours + PAO) return 1; } return 0; } inline int InCheckAfterMove(int mv) { // 非破壞性判斷 int from = FROM(mv), to = TO(mv); char zFrom = _brd[from], zTo = _brd[to]; _brd[to] = _brd[from]; _brd[from] = 0; int inCheck = InCheck(); _brd[to] = zTo; _brd[from] = zFrom; return inCheck; } int GenerateMoves(int* mvs, int jinChizi = 0) { // jinChizi: 只吃對方子; 否則吃子或不吃子(即不吃自己子) // !(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 = 0, mine = MyFirstZi(_side), yours = YourFirstZi(_side); // 0100=紅 1000=黑 for (int from = BEGIN; from < END; from++) { int to, d, zi = _brd[from]; if ((zi & mine) == 0) continue; // 不是己方棋子，0000=無 01xx=紅 10xx=黑 const int* delta = DELTA_XIE; switch (int type = zi - mine) { case KING: delta = DELTA_SHIZI; // 后續處理和仕相同, 只是delta不同，不break case SHI: for (i = 0; i < 4; i ++) { if (!InJiugong(to = from + delta[i])) continue; zi = _brd[to]; if (jinChizi ? (zi & yours) : !(zi & mine)) mvs[n++] = MOVE(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 (jinChizi ? (zi & yours) : !(zi & mine)) mvs[n++] = MOVE(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 (jinChizi ? (zi & yours) : !(zi & mine)) mvs[n++] = MOVE(from, to); } } break; 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++] = MOVE(from, to); // 吃子 break; // 前方有子 } else if (!jinChizi) // 不吃子時繼續移動 mvs[n++] = MOVE(from, to); } } break; case PAO: for (i = 0; i < 4; i++) { d = DELTA_SHIZI[i]; for (to = from + d; Empty(to); to += d) { // 移動和找炮架 if (!jinChizi) mvs[n++] = MOVE(from, to); } for (to += d; Empty(to); to += d); // 從炮架往后找 zi = _brd[to]; if (zi & yours) mvs[n++] = MOVE(from, to); } break; default: // case PAWN: if (InBrd(to = Up(from, _side))) { zi = _brd[to]; if (jinChizi ? (zi & yours) : !(zi & mine)) mvs[n++] = MOVE(from, to); } if (GuoHeLe(from, _side)) { for (d = -1; d <= 1; d += 2) { if (InBrd(to = from + d)) { zi = _brd[to]; if (jinChizi ? (zi & yours) : !(zi & mine)) mvs[n++] = MOVE(from, to); } } } } // switch } return n; } // 人走時, c3c4ToSQ檢查square是否越界, LegalMove !不! 檢查走子后被將軍 // 電腦走時, GenerateMoves !不! 檢查走子后被將軍; 由于Hash沖突, 從表里查來的move可能illegal int LegalMove(int mv) { // Chess Terminology里用legal而不是valid; LDOCE說legal W1S3 (常用, Written, Spoken) 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 = MyFirstZi(_side), sq; int from = FROM(mv), to = TO(mv), zFrom = _brd[from], zTo = _brd[to]; // z:子 if (!(zFrom & mine) || (zTo & mine)) return 0; // 不是走自己的子, 或吃自己的子 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: sq = from + BMT[to - from + 256]; return (sq != from) && Empty(sq); // 馬腿無子? 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 0; // 車炮不走直線 for (sq = from + d; (sq != to) && Empty(sq); sq += d); // 遇到to或任意一方棋子停止 if (sq == to) return ((CHE == type) || !zTo); // 無論to處有無子,車都可以到(移動或吃); 無子則炮可移到 else if ((PAO == type) && zTo) { // 不能隔著炮架打空氣 for (sq += d; (sq != to) && Empty(sq); sq += d); // 找到炮架后第一個子 return (sq == to); } else return 0; } default: // case PAWN: if (GuoHeLe(to, _side) && (to == from - 1 || to == from + 1)) return 1; return (to == Up(from, _side)); } } const int MAX_GEN_MOVES = 128; // ELEEYE說“象棋任何局面不超過120種可能走法”，mvs[MAX_GEN_MOVES]是遞回函式的區域變數 const int MATE_VALUE = https://www.cnblogs.com/funwithwords/p/10000; // 最高分數，即將死的分，Checkmate可簡稱mate const int BAN_VALUE = https://www.cnblogs.com/funwithwords/p/MATE_VALUE - 100; // 長將判負的分 const int WIN_VALUE = https://www.cnblogs.com/funwithwords/p/MATE_VALUE - 200; // 超出此值說明已搜索出殺棋 const int DRAW_VALUE = https://www.cnblogs.com/funwithwords/p/20; // 和棋時的分 int Checkmate() { int mvs[MAX_GEN_MOVES], n = GenerateMoves(mvs); for (int i = 0; i < n; i++) if (!InCheckAfterMove(mvs[i])) return 0; return 1; // 所有的走法都解不了將 } inline void PutPiece(int sq, int zi) { _brd[sq] = char(zi); if (zi < 16) { zi -= 8; _redVl += Z_POS_VL[zi][sq]; _zn ^= ZN_TBL[0][zi][sq]; } else { zi -= 16; _blackVl += Z_POS_VL[zi][Flip(sq)]; _zn ^= ZN_TBL[1][zi][sq]; } } inline void TakePiece(int sq, int zi) { _brd[sq] = 0; if (zi < 16) { zi -= 8; _redVl -= Z_POS_VL[zi][sq]; _zn ^= ZN_TBL[0][zi][sq]; } else { zi -= 16; _blackVl -= Z_POS_VL[zi][Flip(sq)]; _zn ^= ZN_TBL[1][zi][sq]; } } int MakeMove(int mv) { if (!(++_nTotalMove & 0xfffff)) { // 每100萬次檢查下 clock_t now = clock(), d = now - _startTime; static const int S = CLOCKS_PER_SEC / 1000; printf("%d ms %d 千步/秒\r", (d * 1000 / CLOCKS_PER_SEC), _nTotalMove * S / d); // \r\n CR (Carriage Return) LF (Line Feed)/New Line 0d 0a if (now >= _endTime) _stop = 1; // 不要return 0也不要throw, 讓搜索干凈地結束 } if (!mv || InCheckAfterMove(mv)) return 0; int from = FROM(mv), to = TO(mv), zi = _brd[from], victim = _brd[to]; if (victim) TakePiece(to, victim); TakePiece(from, zi); PutPiece(to, zi); SwitchSide(); // 改變走棋方后重新判斷是否將軍 _pstack[_nPos].Set(mv, victim, InCheck(), _zn); ++_nPos; ++_distance; return 1; } void UnmakeMove() { --_distance; --_nPos; SwitchSide(); int mv = _pstack[_nPos].mv, from = FROM(mv), to = TO(mv), victim = _pstack[_nPos].victim, zi = _brd[to]; TakePiece(to, zi); PutPiece(from, zi); if (victim) PutPiece(to, victim); } inline int Evaluate() { return (_side ? (_blackVl - _redVl) : (_redVl - _blackVl)) + 3; } // 空著(Null-Move)是自己不走讓對手連走兩次，“在歷史表和迭代加深等啟發的作用下，空著啟發已經意義不大了，”測驗好像減少百分之十幾的搜索時間， int NullMoveOK() { return (_side ? _blackVl : _redVl) > 400; } // 根據子力判斷是否允許空步裁剪 inline void NullMove() { SwitchSide(); _pstack[_nPos].Set(0, 0, 0, _zn); ++_nPos; ++_distance; } inline void UndoNullMove() { --_distance; --_nPos; SwitchSide(); } int DrawValue() { return (_distance & 1) == 0 ? -DRAW_VALUE : DRAW_VALUE; } int RepCode(int nRep = 1) { // rep: repetition int side = 0, meCJ = 1, youCJ = 1; // cj:長將(perpetual check) for (const Position* p = _pstack + _nPos - 1; p->mv && !p->victim; p--) { // 初始局面和空著產生的局面，mv和victim為0 if (side) { meCJ &= p->check; if (p->zn == _zn && !--nRep) return (1 | (meCJ ? 2 : 0) | (youCJ ? 4 : 0)); } else youCJ &= p->check; side ^= 1; } return 0; } int GameOver() { if (Checkmate()) return puts("絕殺無解"); if (int c = RepCode(3)) { printf("%s", "存在重復局面，"); switch (c) { case 1: return puts("雙方都無長將(判和)"); case 3: return puts("本方長將(判本方負)"); // 1|2 case 5: return puts("對方長將(判對方負)"); // 1|4 case 7: return puts("雙方長將(判和)"); // 1|2|4 } } if (_nPos > 100) return puts("無聊死了"); return 0; } int RepValue(int c) { // 重復局面的分數 int v = ((c & 2) ? _distance - BAN_VALUE : 0) + ((c & 4) ? BAN_VALUE - _distance : 0); return v ? v : DrawValue(); } struct HashItem { uint64_t zn; short mv, vl; // 有很多個所以想省點記憶體 char depth, flag; }; const int MAX_DISTANCE = 20; // 最大搜索深度 // 不同的路可以到達同樣局面的現象叫做“置換”(Transposing)，置換表存盤已搜過的結果，它通常是個散串列， const int HASH_SIZE = 1 << 23; const int HASH_ALPHA = 1; // Alpha節點的置換表項 const int HASH_BETA = 2; // Beta節點的置換表項 const int HASH_PV = 3; // Principal Variation節點的置換表項 namespace history { HashItem _hashTbl[HASH_SIZE]; // 請看main()前注釋，車砍砲, 車吃車, 另一個車鐵門栓，只看當前局面的評價函式如何寫? 得子了, 丟車了, 贏了， // 國際象棋程式設計(四)：“用評估函式對著法打分然后排序，直覺上這會起作用，評估函式越好，這個方法就越有效，不幸的是在Chess中它一點也不起作用， // 因為下個月我們將了解到，很多局面是不能準確評估的，”(四)和(五)隔了一個月, 可見確實難，:-) int _vls[65536]; // values void Clear() { memset(_hashTbl, 0, sizeof(_hashTbl)); memset(_vls, 0, sizeof(_vls)); } // 如 MATE=100, BAN(長將)=90, WIN(將要將死, 殺棋)=80 void Update(int flag, int vl, int depth, int mv) { // mv可能是0(沒有bestMove) HashItem& hsh = _hashTbl[_zn & (HASH_SIZE - 1)]; if (hsh.depth > depth) return; // 沖突時保存更深的 hsh.flag = char(flag); hsh.depth = char(depth); hsh.mv = short(mv); hsh.zn = _zn; if (vl > WIN_VALUE) { // 紅方殺棋 if (mv || vl > BAN_VALUE) hsh.vl = short(vl + _distance); } else if (vl < -WIN_VALUE) { // 黑方殺棋 if (mv || vl < -BAN_VALUE) hsh.vl = short(vl - _distance); } else hsh.vl = short(vl); if (mv) _vls[mv] += depth * depth; } int Find(int alpha, int beta, int depth, int &mv) { const HashItem& h = _hashTbl[_zn & (HASH_SIZE - 1)]; if (h.zn != _zn) { mv = 0; return -MATE_VALUE; } mv = h.mv; int vl = h.vl, mate = 0; if (vl > WIN_VALUE) { if (vl < BAN_VALUE) return -MATE_VALUE; vl -= _distance; mate = 1; } else if (vl < -WIN_VALUE) { if (vl > -BAN_VALUE) return -MATE_VALUE; vl += _distance; mate = 1; } if (mate || h.depth >= depth) { // 殺棋不在乎深度 if (h.flag == HASH_BETA) return (vl >= beta ? vl : -MATE_VALUE); else if (h.flag == HASH_ALPHA) return (vl <= alpha ? vl : -MATE_VALUE); return vl; } return -MATE_VALUE; } int GenMoves(int* mvs, int best = 0) { mvs[0] = best; int n = GenerateMoves(mvs + 1) + 1; // 生成所有著法 for (int i = 2; i < n; i++) { // 元素數量幾十個時Insertion Sort快 int t = mvs[i], tv = _vls[t], j; // 如b12 b11 b21 for (j = i - 1; j >= 1 && tv > _vls[mvs[j]]; j--) mvs[j + 1] = mvs[j]; mvs[j + 1] = t; } if (best) for (int i = 1; i < n; i++) if (best == mvs[i]) mvs[i] = 0; return n; } } // history namespace mvvlva { // Most Valuable Victim/Least Valuable Attacker) 卒吃炮: good, 卒吃車: goood, 卒吃帥: goooood! static const int T[24] = { 0, 0, 0, 0, 0, 0, 0, 0, 5, 1, 1, 3, 4, 3, 2, 0, 5, 1, 1, 3, 4, 3, 2, 0 }; inline int calc(int mv) { return (T[_brd[TO(mv)]] << 3) - T[_brd[FROM(mv)]]; } int GenMoves(int* mvs) { int values[MAX_GEN_MOVES], i; int n = GenerateMoves(mvs, 1); // 生成僅吃子走法 for (i = 0; i < n; i++) values[i] = calc(mvs[i]); for (i = 1; i < n; i++) { // 注意兩個排序稍有不同 int t = mvs[i], v = values[i], j; for (j = i - 1; j >= 0 && v > values[j]; j--) mvs[j + 1] = mvs[j]; mvs[j + 1] = t; } return n; }; } // mvvlva // 《高級搜索方法——靜態搜索》、《高級搜索方法——簡介(一)》 相對穩定的局面叫做Quiescent局面， // 靜態搜索一般只搜索吃子著法, 因為吃子導致局面劇烈變化(不再inactive; passive; quiet). sanction有類似的情況， int Quies(int alpha, int beta) { if (int c = RepCode()) return RepValue(c); // 重復局面處理 if (_stop || _distance == MAX_DISTANCE) return Evaluate(); int best = -MATE_VALUE, mvs[MAX_GEN_MOVES], n; if (LastPositionInCheck()) n = history::GenMoves(mvs); // 被將軍時生成全部走法 else { int score = Evaluate(); if (score > best) { best = score; if (score >= beta) return score; if (score > alpha) alpha = score; } // Evaluate速度非常快, 盡量避免GenMoves n = mvvlva::GenMoves(mvs); } for (int i = 0; i < n; i++) { if (!MakeMove(mvs[i])) continue; int score = -Quies(-beta, -alpha); UnmakeMove(); if (score > best) { best = score; if (score >= beta) return score; if (score > alpha) alpha = score; } } return (best == -MATE_VALUE) ? (_distance - MATE_VALUE) : best; } /* 《高級搜索方法——簡介(二)》 https://www.chessprogramming.org/Fail-Soft Fail-Soft is related to Alpha-Beta. Returned scores might be outside the bounds. */ int Fail_Soft(int alpha, int beta, int depth, int noNullmove) { // 《高級搜索方法——簡介(一)》 每一步棋都搜索到一個固定的深度, 這個深度叫做“水平線”(Horizon) if (depth <= 0) return Quies(alpha, beta); // 到達水平線則呼叫靜態搜索(注意由于空步裁剪，深度可能小于零) if (int c = RepCode()) return RepValue(c); // 不要在根節點檢查重復局面，否則就沒有走法了 if (_stop || _distance == MAX_DISTANCE) return Evaluate(); // 嘗試置換表裁剪，并得到置換表走法 int hashMove, score = history::Find(alpha, beta, depth, hashMove); if (score > -MATE_VALUE) return score; // 嘗試空步裁剪(根節點的Beta值是MATE_VALUE，所以不可能發生空步裁剪) if (!noNullmove && NullMoveOK() && !InCheck()) { NullMove(); enum { NULL_DEPTH = 2 }; score = -Fail_Soft(-beta, 1 - beta, depth - NULL_DEPTH - 1, 1); UndoNullMove(); if (score >= beta) return score; } int hashFlag = HASH_ALPHA, bestMove = 0, bestScore = -MATE_VALUE; int mvs[MAX_GEN_MOVES], n = history::GenMoves(mvs, hashMove); for (int i = 0; i < n; i++) { int mv = mvs[i]; if (!MakeMove(mv)) continue; /* Check Extensions have two distinct forms: one of them extends when giving check, the other - when evading it. In each case, typical depth to extend is one ply. A ply is a half-move, or the move of one player. When both players move, that is two ply, or one full move. www.chessprogramming.org/Check_Extensions */ int newDepth = LastPositionInCheck() ? depth : (depth - 1); if (bestScore == -MATE_VALUE) { score = -Fail_Soft(-beta, -alpha, newDepth, 0); } else { score = -Fail_Soft(-alpha - 1, -alpha, newDepth, 0); if (score > alpha && score < beta) score = -Fail_Soft(-beta, -alpha, newDepth, 0); } UnmakeMove(); // 進行Alpha-Beta大小判斷和截斷 if (score > bestScore) { // 找到最佳值(但不能確定是Alpha、PV還是Beta走法) bestScore = score; // bestScore是目前要回傳的最佳值, 可能超出Alpha-Beta邊界 if (score >= beta) { // 找到一個Beta走法 hashFlag = HASH_BETA; bestMove = mv; // Beta走法要保存到歷史表 break; // Beta截斷(退出回圈不再試其它著法) } if (score > alpha) { // 找到一個Principal Variation走法 hashFlag = HASH_PV; bestMove = mv; // PV走法要保存到歷史表 alpha = score; // 縮小Alpha-Beta邊界 } } } // 搜完所有走法, 把最佳走法(不能是Alpha走法)保存到歷史表, 回傳最佳值 if (bestScore == -MATE_VALUE) return _distance - MATE_VALUE; // 殺棋根據步數給出評價 history::Update(hashFlag, bestScore, depth, bestMove); return bestScore; } int RootSearch(int depth) { int score, best = -MATE_VALUE; int mvs[MAX_GEN_MOVES], n = history::GenMoves(mvs, _bestMove); for (int i = 0; !_stop && (i < n); i++) { int mv = mvs[i]; if (!MakeMove(mv)) continue; int newDepth = LastPositionInCheck() ? depth : depth - 1; if (best != -MATE_VALUE) { // Fail-Hard: Alpha <= Score <= Beta. 對<alpha和>beta的不感興趣 score = -Fail_Soft(-best - 1, -best, newDepth, 0); // Soft比hard放寬一點限制，使用null-move if (score > best) score = -Fail_Soft(-MATE_VALUE, -best, newDepth, 1); // No null-move } else score = -Fail_Soft(-MATE_VALUE, MATE_VALUE, newDepth, 1); // 先有個著法再說 UnmakeMove(); if (score > best) { best = score; _bestMove = mv; } } history::Update(HASH_PV, best, depth, _bestMove); return best; } void ComputerGo() { history::Clear(); _nTotalMove = _distance = _bestMove = _stop = 0; _startTime = clock(); _endTime = _startTime + _endTime * CLOCKS_PER_SEC; for (int i = 1; !_stop && i <= MAX_DISTANCE; i++) { // 在滿足時間限制的前提下改進，“迭代加深”(Iterated Deepening) int score = RootSearch(i); if (score > WIN_VALUE || score < -WIN_VALUE) break; // 搜到殺棋提前終止 } MakeMove(_bestMove); puts(""); } int c3c4ToSQ(int x, int y) { 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 XY2SQ(x, y); } void ManGo() { for (int mv;;) try { char s[80] = ""; printf("%d. 輸入著法: ", (_nPos + 1) / 2); strupr(gets(s)); if (*s == 'Q') exit(0); _endTime = atoi(s + 4); if (_endTime < 1 || _endTime > 99) _endTime = 2; mv = MOVE(c3c4ToSQ(*s, s[1]), c3c4ToSQ(s[2], s[3])); if (LegalMove(mv) && MakeMove(mv)) break; } catch(int) {} } int fen_atoi(int c) { switch (toupper(c)) { case 'K': return 0; case 'A': return 1; case 'B': return 2; case 'N': return 3; case 'R': return 4; case 'C': return 5; case 'P': return 6; default: abort(); } } void Init() { const char* s = "rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR"; //const char* s = "r3kab2/4a4/4b4/c3C4/9/R1R6/9/9/9/4K4 "; 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[XY2SQ(x++, y)] = char((c >= 'a' ? 16 : 8) + fen_atoi(c)); } for (int sq = BEGIN; sq < END; sq++) { if (char zi = _brd[sq]) PutPiece(sq, zi); } _pstack[_nPos++].Set(0, 0, InCheck(), _zn); } /* ９車···將士象··* 《國際象棋程式設計(4)基本搜索方法》《基本搜索方法——簡介1,2,最小-最大搜索》 https://www.chessprogramming.org/Minimax ８····士····* 評價函式給每個局面打1個分，如紅方子數 - 黑方子數，15對紅方是極好的(黑光桿老將), -15對黑方是極好的，-15 < 0 < 15, Min, Max ７····象····* 對方總是極不配合, 紅方總選max, 黑方總選min. Minimax搜索時return red ? Max(depth) : Min(depth); ６砲···炮····* -1的n次方不斷變號，score = -NegativeMax(depth - 1); 如黑在-15和-7中選min相當于在15和7中選max. ５·········* alpha male: the dominant male animal or person in a group. 希臘字母洋氣，完全搜索的結點叫alpha結點， ４車·車······* 如節點F的子節點的分是{11,12,7,9}, 則F的分是12. G是F的兄弟, 子節點是{15,一大堆沒搜的}, 那對手會怎么辦? ３········· 對手肯定不會選擇G, 因為如果他選G, 他知道聰明的你會選至少15那個(G)，他選F, 你用盡洪荒之力也只能選12. ２·········* 程式天然有自己和自己下的能力(靠depth的奇偶區分雙方)，到達葉子結點的路叫做“主要變例”(Principal Variation) １·········* 改偽碼是好主意，改別人寫好的更好(說我自己)，Don't be cocky, 覺得“這么改咋會錯”, 勤測驗, 勤備份(還是說自己)， ０····帥····* 以下alpha和beta是分, 不是節點或人， ａｂｃｄｅｆｇｈｉ def alpha_beta(alpha, beta, int depth): # depth不斷減少 if depth <= 0: return evaluate() {生成并排序著法} for (每個著法): 執行著法 score = -alpha_beta(-beta, -alpha, depth - 1); 撤消著法 */ int main() { puts("小清象棋——改自象棋小巫師[ http://www.xqbase.com/ ]\n\n例子 說明"); puts("q 退出\nc3c4 兵七進一，電腦2級\nb2c5 9 炮二進七，電腦9級"); for (Init(); !GameOver();) PrintBoard(), ManGo(), ComputerGo(); return 0; }View Code
沒有stdint.h的話：
typedef unsigned __int64 uint64_t;
typedef unsigned __int8 uint8_t;
View Code
從象棋小巫師改的，計算機博弈講了很多相關知識，
Windows 10自帶的殺毒軟體歧視用戶自己編譯的.exe，啟動時總要檢查一番，可在“病毒和威脅防護”設定—管理設定—添加或洗掉排除項里把.exe所在的檔案夾添加進去，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539713.html
標籤：其他
上一篇：地下城地圖圖塊生成演算法