API tools faq
paste
Guest User

Untitled

a guest
Dec 7th, 2025
27
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 15.95 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <chrono>
  5. #include <sstream>
  6.  
  7. using namespace std;
  8.  
  9. typedef unsigned long long U64;
  10.  
  11. // Piece representation
  12. enum { PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING };
  13. enum { WHITE, BLACK };
  14.  
  15. // Bitboard utilities
  16. #define C64(x) x##ULL
  17. #define SET_BIT(bb, sq) ((bb) |= (C64(1) << (sq)))
  18. #define GET_BIT(bb, sq) ((bb) & (C64(1) << (sq)))
  19. #define POP_BIT(bb, sq) ((bb) &= ~(C64(1) << (sq)))
  20.  
  21. int count_bits(U64 bb) {
  22. int count = 0;
  23. while (bb) {
  24. count++;
  25. bb &= bb - 1;
  26. }
  27. return count;
  28. }
  29.  
  30. int lsb(U64 bb) {
  31. if (!bb) return -1;
  32. return count_bits((bb & -bb) - 1);
  33. }
  34.  
  35. struct Move {
  36. int from, to, piece, captured, promoted, flags;
  37. Move(int f = 0, int t = 0, int p = 0, int c = -1, int pr = -1, int fl = 0)
  38. : from(f), to(t), piece(p), captured(c), promoted(pr), flags(fl) {}
  39. };
  40.  
  41. class Position {
  42. public:
  43. U64 pieces[2][6]; // [color][piece_type]
  44. U64 occupied[2];
  45. U64 all_occupied;
  46. int side;
  47. int ep_square;
  48. int castle_rights;
  49. int fifty_move;
  50.  
  51. Position() {
  52. for (int i = 0; i < 2; i++) {
  53. for (int j = 0; j < 6; j++) {
  54. pieces[i][j] = 0;
  55. }
  56. occupied[i] = 0;
  57. }
  58. all_occupied = 0;
  59. side = WHITE;
  60. ep_square = -1;
  61. castle_rights = 15;
  62. fifty_move = 0;
  63. }
  64.  
  65. void set_fen(const string& fen) {
  66. for (int i = 0; i < 2; i++) {
  67. for (int j = 0; j < 6; j++) pieces[i][j] = 0;
  68. occupied[i] = 0;
  69. }
  70.  
  71. istringstream ss(fen);
  72. string board, turn, castle, ep;
  73. ss >> board >> turn >> castle >> ep;
  74.  
  75. int sq = 56;
  76. for (char c : board) {
  77. if (c == '/') sq -= 16;
  78. else if (isdigit(c)) sq += (c - '0');
  79. else {
  80. int color = isupper(c) ? WHITE : BLACK;
  81. c = tolower(c);
  82. int piece = (c == 'p') ? PAWN : (c == 'n') ? KNIGHT : (c == 'b') ? BISHOP :
  83. (c == 'r') ? ROOK : (c == 'q') ? QUEEN : KING;
  84. SET_BIT(pieces[color][piece], sq);
  85. sq++;
  86. }
  87. }
  88.  
  89. side = (turn == "w") ? WHITE : BLACK;
  90.  
  91. castle_rights = 0;
  92. for (char c : castle) {
  93. if (c == 'K') castle_rights |= 1;
  94. if (c == 'Q') castle_rights |= 2;
  95. if (c == 'k') castle_rights |= 4;
  96. if (c == 'q') castle_rights |= 8;
  97. }
  98.  
  99. ep_square = (ep == "-") ? -1 : (ep[0] - 'a') + (ep[1] - '1') * 8;
  100.  
  101. update_occupancy();
  102. }
  103.  
  104. void update_occupancy() {
  105. occupied[WHITE] = occupied[BLACK] = 0;
  106. for (int i = 0; i < 6; i++) {
  107. occupied[WHITE] |= pieces[WHITE][i];
  108. occupied[BLACK] |= pieces[BLACK][i];
  109. }
  110. all_occupied = occupied[WHITE] | occupied[BLACK];
  111. }
  112.  
  113. U64 get_attacks_pawn(int sq, int color) {
  114. U64 att = 0;
  115. if (color == WHITE) {
  116. if (sq % 8 != 0) att |= C64(1) << (sq + 7);
  117. if (sq % 8 != 7) att |= C64(1) << (sq + 9);
  118. } else {
  119. if (sq % 8 != 0) att |= C64(1) << (sq - 9);
  120. if (sq % 8 != 7) att |= C64(1) << (sq - 7);
  121. }
  122. return att;
  123. }
  124.  
  125. U64 get_attacks_knight(int sq) {
  126. U64 att = 0;
  127. int offsets[] = {17, 15, 10, 6, -6, -10, -15, -17};
  128. int rank = sq / 8, file = sq % 8;
  129. for (int off : offsets) {
  130. int to = sq + off;
  131. if (to < 0 || to > 63) continue;
  132. int tr = to / 8, tf = to % 8;
  133. if (abs(tr - rank) + abs(tf - file) == 3) att |= C64(1) << to;
  134. }
  135. return att;
  136. }
  137.  
  138. U64 get_attacks_king(int sq) {
  139. U64 att = 0;
  140. int offsets[] = {8, -8, 1, -1, 9, -9, 7, -7};
  141. int rank = sq / 8, file = sq % 8;
  142. for (int off : offsets) {
  143. int to = sq + off;
  144. if (to < 0 || to > 63) continue;
  145. int tr = to / 8, tf = to % 8;
  146. if (abs(tr - rank) <= 1 && abs(tf - file) <= 1) att |= C64(1) << to;
  147. }
  148. return att;
  149. }
  150.  
  151. U64 get_attacks_slider(int sq, int dir[4][2], U64 occ) {
  152. U64 att = 0;
  153. for (int i = 0; i < 4; i++) {
  154. int r = sq / 8, f = sq % 8;
  155. while (true) {
  156. r += dir[i][0]; f += dir[i][1];
  157. if (r < 0 || r > 7 || f < 0 || f > 7) break;
  158. int to = r * 8 + f;
  159. att |= C64(1) << to;
  160. if (occ & (C64(1) << to)) break;
  161. }
  162. }
  163. return att;
  164. }
  165.  
  166. U64 get_attacks_rook(int sq, U64 occ) {
  167. int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  168. return get_attacks_slider(sq, dir, occ);
  169. }
  170.  
  171. U64 get_attacks_bishop(int sq, U64 occ) {
  172. int dir[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
  173. return get_attacks_slider(sq, dir, occ);
  174. }
  175.  
  176. bool is_square_attacked(int sq, int by_color) {
  177. if (get_attacks_pawn(sq, 1 - by_color) & pieces[by_color][PAWN]) return true;
  178. if (get_attacks_knight(sq) & pieces[by_color][KNIGHT]) return true;
  179. if (get_attacks_king(sq) & pieces[by_color][KING]) return true;
  180.  
  181. U64 rook_att = get_attacks_rook(sq, all_occupied);
  182. if (rook_att & (pieces[by_color][ROOK] | pieces[by_color][QUEEN])) return true;
  183.  
  184. U64 bishop_att = get_attacks_bishop(sq, all_occupied);
  185. if (bishop_att & (pieces[by_color][BISHOP] | pieces[by_color][QUEEN])) return true;
  186.  
  187. return false;
  188. }
  189.  
  190. void generate_moves(vector<Move>& moves) {
  191. int us = side, them = 1 - side;
  192.  
  193. // Pawn moves
  194. U64 pawns = pieces[us][PAWN];
  195. while (pawns) {
  196. int from = lsb(pawns);
  197. int to, rank = from / 8;
  198.  
  199. // Single push
  200. to = us == WHITE ? from + 8 : from - 8;
  201. if (to >= 0 && to <= 63 && !(all_occupied & (C64(1) << to))) {
  202. if ((us == WHITE && rank == 6) || (us == BLACK && rank == 1)) {
  203. for (int pr = KNIGHT; pr <= QUEEN; pr++)
  204. moves.push_back(Move(from, to, PAWN, -1, pr, 0));
  205. } else {
  206. moves.push_back(Move(from, to, PAWN, -1, -1, 0));
  207. }
  208.  
  209. // Double push
  210. if ((us == WHITE && rank == 1) || (us == BLACK && rank == 6)) {
  211. int to2 = us == WHITE ? from + 16 : from - 16;
  212. if (!(all_occupied & (C64(1) << to2)))
  213. moves.push_back(Move(from, to2, PAWN, -1, -1, 1));
  214. }
  215. }
  216.  
  217. // Captures
  218. U64 attacks = get_attacks_pawn(from, us);
  219. U64 targets = attacks & occupied[them];
  220. while (targets) {
  221. to = lsb(targets);
  222. int cap = -1;
  223. for (int p = 0; p < 6; p++) {
  224. if (GET_BIT(pieces[them][p], to)) { cap = p; break; }
  225. }
  226. if ((us == WHITE && rank == 6) || (us == BLACK && rank == 1)) {
  227. for (int pr = KNIGHT; pr <= QUEEN; pr++)
  228. moves.push_back(Move(from, to, PAWN, cap, pr, 0));
  229. } else {
  230. moves.push_back(Move(from, to, PAWN, cap, -1, 0));
  231. }
  232. POP_BIT(targets, to);
  233. }
  234.  
  235. // En passant
  236. if (ep_square != -1 && (attacks & (C64(1) << ep_square))) {
  237. moves.push_back(Move(from, ep_square, PAWN, PAWN, -1, 2));
  238. }
  239.  
  240. POP_BIT(pawns, from);
  241. }
  242.  
  243. // Knight moves
  244. U64 knights = pieces[us][KNIGHT];
  245. while (knights) {
  246. int from = lsb(knights);
  247. U64 attacks = get_attacks_knight(from) & ~occupied[us];
  248. while (attacks) {
  249. int to = lsb(attacks);
  250. int cap = -1;
  251. if (GET_BIT(occupied[them], to)) {
  252. for (int p = 0; p < 6; p++) {
  253. if (GET_BIT(pieces[them][p], to)) { cap = p; break; }
  254. }
  255. }
  256. moves.push_back(Move(from, to, KNIGHT, cap, -1, 0));
  257. POP_BIT(attacks, to);
  258. }
  259. POP_BIT(knights, from);
  260. }
  261.  
  262. // Bishop moves
  263. U64 bishops = pieces[us][BISHOP];
  264. while (bishops) {
  265. int from = lsb(bishops);
  266. U64 attacks = get_attacks_bishop(from, all_occupied) & ~occupied[us];
  267. while (attacks) {
  268. int to = lsb(attacks);
  269. int cap = -1;
  270. if (GET_BIT(occupied[them], to)) {
  271. for (int p = 0; p < 6; p++) {
  272. if (GET_BIT(pieces[them][p], to)) { cap = p; break; }
  273. }
  274. }
  275. moves.push_back(Move(from, to, BISHOP, cap, -1, 0));
  276. POP_BIT(attacks, to);
  277. }
  278. POP_BIT(bishops, from);
  279. }
  280.  
  281. // Rook moves
  282. U64 rooks = pieces[us][ROOK];
  283. while (rooks) {
  284. int from = lsb(rooks);
  285. U64 attacks = get_attacks_rook(from, all_occupied) & ~occupied[us];
  286. while (attacks) {
  287. int to = lsb(attacks);
  288. int cap = -1;
  289. if (GET_BIT(occupied[them], to)) {
  290. for (int p = 0; p < 6; p++) {
  291. if (GET_BIT(pieces[them][p], to)) { cap = p; break; }
  292. }
  293. }
  294. moves.push_back(Move(from, to, ROOK, cap, -1, 0));
  295. POP_BIT(attacks, to);
  296. }
  297. POP_BIT(rooks, from);
  298. }
  299.  
  300. // Queen moves
  301. U64 queens = pieces[us][QUEEN];
  302. while (queens) {
  303. int from = lsb(queens);
  304. U64 attacks = (get_attacks_rook(from, all_occupied) |
  305. get_attacks_bishop(from, all_occupied)) & ~occupied[us];
  306. while (attacks) {
  307. int to = lsb(attacks);
  308. int cap = -1;
  309. if (GET_BIT(occupied[them], to)) {
  310. for (int p = 0; p < 6; p++) {
  311. if (GET_BIT(pieces[them][p], to)) { cap = p; break; }
  312. }
  313. }
  314. moves.push_back(Move(from, to, QUEEN, cap, -1, 0));
  315. POP_BIT(attacks, to);
  316. }
  317. POP_BIT(queens, from);
  318. }
  319.  
  320. // King moves
  321. U64 kings = pieces[us][KING];
  322. int from = lsb(kings);
  323. U64 attacks = get_attacks_king(from) & ~occupied[us];
  324. while (attacks) {
  325. int to = lsb(attacks);
  326. int cap = -1;
  327. if (GET_BIT(occupied[them], to)) {
  328. for (int p = 0; p < 6; p++) {
  329. if (GET_BIT(pieces[them][p], to)) { cap = p; break; }
  330. }
  331. }
  332. moves.push_back(Move(from, to, KING, cap, -1, 0));
  333. POP_BIT(attacks, to);
  334. }
  335.  
  336. // Castling
  337. if (us == WHITE) {
  338. if ((castle_rights & 1) && !(all_occupied & (C64(1) << 5)) &&
  339. !(all_occupied & (C64(1) << 6)) &&
  340. !is_square_attacked(4, BLACK) && !is_square_attacked(5, BLACK))
  341. moves.push_back(Move(4, 6, KING, -1, -1, 3));
  342. if ((castle_rights & 2) && !(all_occupied & (C64(1) << 3)) &&
  343. !(all_occupied & (C64(1) << 2)) && !(all_occupied & (C64(1) << 1)) &&
  344. !is_square_attacked(4, BLACK) && !is_square_attacked(3, BLACK))
  345. moves.push_back(Move(4, 2, KING, -1, -1, 3));
  346. } else {
  347. if ((castle_rights & 4) && !(all_occupied & (C64(1) << 61)) &&
  348. !(all_occupied & (C64(1) << 62)) &&
  349. !is_square_attacked(60, WHITE) && !is_square_attacked(61, WHITE))
  350. moves.push_back(Move(60, 62, KING, -1, -1, 3));
  351. if ((castle_rights & 8) && !(all_occupied & (C64(1) << 59)) &&
  352. !(all_occupied & (C64(1) << 58)) && !(all_occupied & (C64(1) << 57)) &&
  353. !is_square_attacked(60, WHITE) && !is_square_attacked(59, WHITE))
  354. moves.push_back(Move(60, 58, KING, -1, -1, 3));
  355. }
  356. }
  357.  
  358. void make_move(const Move& m) {
  359. int us = side, them = 1 - us;
  360.  
  361. // Remove piece from origin
  362. POP_BIT(pieces[us][m.piece], m.from);
  363.  
  364. // Handle capture
  365. if (m.captured != -1) {
  366. POP_BIT(pieces[them][m.captured], m.to);
  367. }
  368.  
  369. // Handle en passant capture
  370. if (m.flags == 2) {
  371. int cap_sq = us == WHITE ? m.to - 8 : m.to + 8;
  372. POP_BIT(pieces[them][PAWN], cap_sq);
  373. }
  374.  
  375. // Place piece at destination
  376. if (m.promoted != -1) {
  377. SET_BIT(pieces[us][m.promoted], m.to);
  378. } else {
  379. SET_BIT(pieces[us][m.piece], m.to);
  380. }
  381.  
  382. // Handle castling
  383. if (m.flags == 3) {
  384. if (m.to == 6) { // White kingside
  385. POP_BIT(pieces[WHITE][ROOK], 7);
  386. SET_BIT(pieces[WHITE][ROOK], 5);
  387. } else if (m.to == 2) { // White queenside
  388. POP_BIT(pieces[WHITE][ROOK], 0);
  389. SET_BIT(pieces[WHITE][ROOK], 3);
  390. } else if (m.to == 62) { // Black kingside
  391. POP_BIT(pieces[BLACK][ROOK], 63);
  392. SET_BIT(pieces[BLACK][ROOK], 61);
  393. } else if (m.to == 58) { // Black queenside
  394. POP_BIT(pieces[BLACK][ROOK], 56);
  395. SET_BIT(pieces[BLACK][ROOK], 59);
  396. }
  397. }
  398.  
  399. // Update en passant square
  400. if (m.flags == 1) {
  401. ep_square = us == WHITE ? m.to - 8 : m.to + 8;
  402. } else {
  403. ep_square = -1;
  404. }
  405.  
  406. // Update castling rights
  407. if (m.piece == KING) {
  408. if (us == WHITE) castle_rights &= ~3;
  409. else castle_rights &= ~12;
  410. }
  411. if (m.piece == ROOK) {
  412. if (m.from == 0) castle_rights &= ~2;
  413. if (m.from == 7) castle_rights &= ~1;
  414. if (m.from == 56) castle_rights &= ~8;
  415. if (m.from == 63) castle_rights &= ~4;
  416. }
  417.  
  418. side = them;
  419. update_occupancy();
  420. }
  421. };
  422.  
  423. U64 perft(Position& pos, int depth) {
  424. if (depth == 0) return 1;
  425.  
  426. vector<Move> moves;
  427. pos.generate_moves(moves);
  428.  
  429. if (depth == 1) return moves.size();
  430.  
  431. U64 nodes = 0;
  432. for (const Move& m : moves) {
  433. Position new_pos = pos;
  434. new_pos.make_move(m);
  435.  
  436. // Skip if king is in check after move
  437. int us = 1 - new_pos.side;
  438. int king_sq = lsb(new_pos.pieces[us][KING]);
  439. if (new_pos.is_square_attacked(king_sq, new_pos.side)) continue;
  440.  
  441. nodes += perft(new_pos, depth - 1);
  442. }
  443.  
  444. return nodes;
  445. }
  446.  
  447. int main() {
  448. Position pos;
  449. pos.set_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
  450.  
  451. cout << "Chess Move Generator with Perft\n";
  452. cout << "================================\n\n";
  453.  
  454. for (int depth = 1; depth <= 5; depth++) {
  455. auto start = chrono::high_resolution_clock::now();
  456. U64 nodes = perft(pos, depth);
  457. auto end = chrono::high_resolution_clock::now();
  458. auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
  459.  
  460. cout << "Depth " << depth << ": " << nodes << " nodes";
  461. cout << " (" << duration.count() << " ms";
  462. if (duration.count() > 0) {
  463. cout << ", " << (nodes * 1000 / duration.count()) << " nps";
  464. }
  465. cout << ")\n";
  466. }
  467.  
  468. return 0;
  469. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!