API tools faq
paste
Advertisement
VladNitu

mriv2

VladNitu
Feb 17th, 2024
87
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 29.83 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int inf = 1e9;
  6. const int maxv = 100;
  7.  
  8. struct Cell {
  9. int x, y;
  10.  
  11. Cell() {
  12. x = y = -1;
  13. }
  14.  
  15. Cell(int _x, int _y) {
  16. x = _x;
  17. y = _y;
  18. }
  19.  
  20. Cell operator+ (const Cell& other) const {
  21. return {x + other.x, y + other.y};
  22. }
  23.  
  24. bool operator ==(const Cell& other) const {
  25. return x == other.x && y == other.y;
  26. }
  27.  
  28. [[nodiscard]] inline bool inRange() const {
  29. if (1 <= x && x <= 8
  30. && 1 <= y && y <= 8)
  31. return true;
  32. return false;
  33. }
  34. };
  35.  
  36. struct Piece {
  37. enum PieceType {
  38. Pawn,
  39. Knight,
  40. Bishop,
  41. Rook,
  42. Queen,
  43. King
  44. };
  45.  
  46. PieceType type;
  47. Cell cell;
  48. char color;
  49.  
  50. Piece () = default;
  51.  
  52. Piece(PieceType _type, Cell _cell, char _color) {
  53. type = _type;
  54. cell = _cell;
  55. color = _color;
  56. }
  57.  
  58. Piece(char c, int x, int y) {
  59. if (isupper(c)) {
  60. color = 'w';
  61. c = tolower(c);
  62. } else {
  63. color = 'b';
  64. }
  65.  
  66. if (c == 'p')
  67. type = Pawn;
  68. else if (c == 'n')
  69. type = Knight;
  70. else if (c == 'b')
  71. type = Bishop;
  72. else if (c == 'r')
  73. type = Rook;
  74. else if (c == 'q')
  75. type = Queen;
  76. else if (c == 'k')
  77. type = King;
  78.  
  79. cell = Cell(x, y);
  80. }
  81.  
  82. struct Directions {
  83. vector<int> dx;
  84. vector<int> dy;
  85. int steps;
  86. };
  87.  
  88. [[nodiscard]] inline static Directions generateDirections(PieceType pieceType) {
  89. if (pieceType == Knight) {
  90. return {vector<int>({2, 2, 1, 1, -1, -1, -2, -2}),
  91. vector<int>({1, -1, 2, -2, 2, -2, 1, -1}),
  92. 1};
  93. } else if (pieceType == Bishop) {
  94. return {vector<int>({-1, -1, 1, 1}),
  95. vector<int>({-1, 1, -1, 1}),
  96. 7
  97. };
  98. } else if (pieceType == Rook) {
  99. return {vector<int>({1, -1, 0, 0}),
  100. vector<int>({0, 0, 1, -1}),
  101. 7
  102. };
  103.  
  104. } else if (pieceType == Queen) {
  105. return {vector<int>({-1, -1, 1, 1, 1, -1, 0, 0}),
  106. vector<int>({-1, 1, -1, 1, 0, 0, 1, -1}),
  107. 7
  108. };
  109. } else if (pieceType == King) {
  110. return {vector<int>({-1, -1, -1, 0, 1, 1, 1, 0}),
  111. vector<int>({-1, 0, 1, 1, 1, 0, -1, -1}),
  112. 1
  113. };
  114. }
  115.  
  116. return {}; // Compiler stops complaining
  117. }
  118.  
  119. [[nodiscard]] inline vector<vector<Cell> > generateMoves() const {
  120. vector<vector<Cell> > allMoves;
  121. if (type == Pawn) {
  122. for (int step = 1; step <= 2; ++step) {
  123. int sgn = (color == 'w' ? 1 : -1);
  124. if (step == 2 &&
  125. ((color == 'w' && cell.x != 2) || (color == 'b' && cell.x != 7)))
  126. continue;
  127. vector<Cell> currMove;
  128. bool illegal = false;
  129. for (int currStep = 1; currStep <= step; ++currStep) {
  130. Cell newCell = cell + Cell(currStep * sgn, 0);
  131. if (!newCell.inRange()) {
  132. illegal = true;
  133. break;
  134. }
  135. currMove.push_back(newCell);
  136. }
  137. if (!illegal) {
  138. allMoves.push_back(currMove);
  139. }
  140. }
  141. } else {
  142. Directions directions = generateDirections(type);
  143. for (int dir = 0; dir < directions.dx.size(); ++dir) {
  144. int dirX = directions.dx[dir];
  145. int dirY = directions.dy[dir];
  146. for (int step = 1; step <= directions.steps; ++step) {
  147. vector<Cell> currMove;
  148. bool illegal = false;
  149. for (int currStep = 1; currStep <= step; ++currStep) {
  150. Cell newCell = cell + Cell(currStep * dirX, currStep * dirY);
  151. if (!newCell.inRange()) {
  152. illegal = true;
  153. break;
  154. }
  155. currMove.push_back(newCell);
  156. }
  157. if (!illegal) {
  158. allMoves.push_back(currMove);
  159. }
  160. }
  161. }
  162. }
  163. return allMoves;
  164. }
  165. };
  166.  
  167. struct BoardState;
  168. string generateFEN(BoardState board, bool includeMoves);
  169.  
  170. struct BoardState {
  171. vector<Piece> pieces;
  172. char activeColor;
  173. char whiteCastling;
  174. char blackCastling;
  175. Cell enPassant;
  176. int halfMoves;
  177. int fullMoves;
  178.  
  179. [[nodiscard]] inline bool isInCheck(char color) const {
  180. Cell kingPosition;
  181. for (const Piece& piece : pieces) {
  182. if (piece.color == color && piece.type == Piece::King) {
  183. kingPosition = piece.cell;
  184. break;
  185. }
  186. }
  187. vector<vector<bool> > attacked = attackedCells(color ^ 'w' ^ 'b');
  188. return attacked[kingPosition.x][kingPosition.y];
  189. }
  190.  
  191. [[nodiscard]] inline bool isDraw() const {
  192. if (halfMoves >= 50 || pieces.size() == 2)
  193. return true;
  194. vector<BoardState> boardStates = generateAllMoves();
  195. if (boardStates.empty() && !isInCheck(activeColor))
  196. return true;
  197. return false;
  198. }
  199.  
  200.  
  201. [[nodiscard]] inline bool isCheckMate() const {
  202. if (!isInCheck(activeColor))
  203. return false;
  204. vector<BoardState> boardStates = generateAllMoves();
  205. return boardStates.empty();
  206. }
  207.  
  208. [[nodiscard]] inline vector<vector<bool> > attackedCells(char color) const {
  209. char b[10][10];
  210. memset(b, 0, sizeof(b));
  211. for (const Piece& piece : pieces) {
  212. b[piece.cell.x][piece.cell.y] = (piece.color == 'w' ? 1 : -1);
  213. }
  214. vector<vector<bool> > isAttacked(9, vector<bool>(9, false));
  215. for (const Piece& piece : pieces) {
  216. if (piece.color != color)
  217. continue;
  218. if (piece.type != Piece::Pawn) {
  219. vector<vector<Cell>> movesPiece = piece.generateMoves();
  220. for (vector<Cell> movesList : movesPiece) {
  221. bool invalid = false;
  222. for (int i = 0; i < movesList.size(); ++i) {
  223. Cell cell = movesList[i];
  224. if (b[cell.x][cell.y] != 0) {
  225. if (i != movesList.size() - 1) {
  226. invalid = true;
  227. break;
  228. } else {
  229. if ((color == 'w' && b[cell.x][cell.y] == 1)
  230. || (color == 'b' && b[cell.x][cell.y] == -1)) {
  231. invalid = true;
  232. break;
  233. }
  234. }
  235. }
  236. }
  237. if (invalid)
  238. continue;
  239. Cell endPosition = movesList.back();
  240. isAttacked[endPosition.x][endPosition.y] = true;
  241. }
  242. } else {
  243. if (piece.color == 'w') {
  244. Cell newCell = piece.cell + Cell(1, -1);
  245. if (newCell.inRange() && b[newCell.x][newCell.y] != 1)
  246. isAttacked[newCell.x][newCell.y] = true;
  247. newCell = piece.cell + Cell(1, 1);
  248. if (newCell.inRange() && b[newCell.x][newCell.y] != 1)
  249. isAttacked[newCell.x][newCell.y] = true;
  250. } else if (piece.color == 'b') {
  251. Cell newCell = piece.cell + Cell(-1, -1);
  252. if (newCell.inRange() && b[newCell.x][newCell.y] != -1)
  253. isAttacked[newCell.x][newCell.y] = true;
  254. newCell = piece.cell + Cell(-1, 1);
  255. if (newCell.inRange() && b[newCell.x][newCell.y] != -1)
  256. isAttacked[newCell.x][newCell.y] = true;
  257. }
  258. }
  259. }
  260. return isAttacked;
  261. }
  262.  
  263. [[nodiscard]] inline vector<BoardState> generateAllMoves() const {
  264. vector<BoardState> newBoards;
  265.  
  266. char newColor = activeColor ^ 'w' ^ 'b';
  267.  
  268. char b[10][10];
  269. memset(b, 0, sizeof(b));
  270. for (const Piece& piece : pieces) {
  271. char p;
  272. if (piece.type == Piece::Pawn) {
  273. p = 'p';
  274. } else if (piece.type == Piece::Knight) {
  275. p = 'n';
  276. } else if (piece.type == Piece::Bishop) {
  277. p = 'b';
  278. } else if (piece.type == Piece::Rook) {
  279. p = 'r';
  280. } else if (piece.type == Piece::Queen) {
  281. p = 'q';
  282. } else if (piece.type == Piece::King) {
  283. p = 'k';
  284. }
  285. if (piece.color == 'w')
  286. p = toupper(p);
  287. b[piece.cell.x][piece.cell.y] = p;
  288. }
  289.  
  290. for (int pieceIdx = 0; pieceIdx < pieces.size(); ++pieceIdx) {
  291. Piece piece = pieces[pieceIdx];
  292. if (piece.color != activeColor)
  293. continue;
  294.  
  295. vector<vector<Cell>> movesPiece = piece.generateMoves();
  296. if (piece.type == Piece::Pawn) {
  297. if (piece.color == 'w') {
  298. Cell newCell = piece.cell + Cell(1, -1);
  299. if (newCell.inRange() && b[newCell.x][newCell.y] != 0 && islower(b[newCell.x][newCell.y]) && b[newCell.x][newCell.y] != 'k')
  300. movesPiece.push_back(vector<Cell>({newCell}));
  301. newCell = piece.cell + Cell(1, 1);
  302. if (newCell.inRange() && b[newCell.x][newCell.y] != 0 && islower(b[newCell.x][newCell.y]) && b[newCell.x][newCell.y] != 'k')
  303. movesPiece.push_back(vector<Cell>({newCell}));
  304. } else if (piece.color == 'b') {
  305. Cell newCell = piece.cell + Cell(-1, -1);
  306. if (newCell.inRange() && b[newCell.x][newCell.y] != 0 && isupper(b[newCell.x][newCell.y]) && b[newCell.x][newCell.y] != 'K')
  307. movesPiece.push_back(vector<Cell>({newCell}));
  308. newCell = piece.cell + Cell(-1, 1);
  309. if (newCell.inRange() && b[newCell.x][newCell.y] != 0 && isupper(b[newCell.x][newCell.y]) && b[newCell.x][newCell.y] != 'K')
  310. movesPiece.push_back(vector<Cell>({newCell}));
  311. }
  312. }
  313. for (vector<Cell> movesList : movesPiece) {
  314. BoardState newBoard;
  315. bool invalid = false;
  316. for (int i = 0; i < movesList.size(); ++i) {
  317. Cell cell = movesList[i];
  318. if (b[cell.x][cell.y] != 0) {
  319. if (i != movesList.size() - 1) {
  320. invalid = true;
  321. break;
  322. } else {
  323. if ((islower(b[cell.x][cell.y]) && activeColor == 'b')
  324. || (isupper(b[cell.x][cell.y]) && activeColor == 'w') || tolower(b[cell.x][cell.y]) == 'k') {
  325. invalid = true;
  326. break;
  327. }
  328. if (piece.type == Piece::Pawn && cell.y == piece.cell.y) {
  329. invalid = true;
  330. break;
  331. }
  332. }
  333. }
  334. }
  335. if (invalid)
  336. continue;
  337. Cell endPosition = movesList.back();
  338. char oldPiece = b[endPosition.x][endPosition.y];
  339. b[endPosition.x][endPosition.y] = 0;
  340. newBoard.pieces = pieces;
  341. newBoard.activeColor = newColor;
  342. newBoard.fullMoves = fullMoves + 1;
  343. // compute newBoard.enPassant
  344. if (piece.type == Piece::Pawn && abs(endPosition.x - piece.cell.x) == 2) {
  345. newBoard.enPassant = piece.cell + Cell((endPosition.x - piece.cell.x) / 2, 0);
  346. } else {
  347. newBoard.enPassant = Cell(-1, -1);
  348. }
  349. // compute newBoard.castling
  350. newBoard.whiteCastling = newBoard.blackCastling = 0;
  351. if (whiteCastling & 1) {
  352. // K
  353. if (b[1][5] == 'K' && b[1][8] == 'R')
  354. newBoard.whiteCastling += 1;
  355. }
  356. if (whiteCastling & 2) {
  357. // Q
  358. if (b[1][5] == 'K' && b[1][1] == 'R')
  359. newBoard.whiteCastling += 2;
  360. }
  361. if (blackCastling & 1) {
  362. // k
  363. if (b[8][5] == 'k' && b[8][8] == 'r')
  364. newBoard.blackCastling += 1;
  365. }
  366. if (blackCastling & 2) {
  367. // q
  368. if (b[8][5] == 'k' && b[8][1] == 'r')
  369. newBoard.blackCastling += 2;
  370. }
  371. b[endPosition.x][endPosition.y] = oldPiece;
  372. if (piece.type == Piece::Pawn || b[endPosition.x][endPosition.y] != 0)
  373. newBoard.halfMoves = 0;
  374. else
  375. newBoard.halfMoves = halfMoves + 1;
  376. newBoard.pieces[pieceIdx].cell = endPosition;
  377. if (b[endPosition.x][endPosition.y] != 0) {
  378. for (int removeIdx = 0; removeIdx < newBoard.pieces.size(); ++removeIdx) {
  379. if (newBoard.pieces[removeIdx].cell == endPosition && newBoard.pieces[removeIdx].color != activeColor) {
  380. std::swap(newBoard.pieces[removeIdx], newBoard.pieces.back());
  381. newBoard.pieces.pop_back();
  382. break;
  383. }
  384. }
  385. }
  386. if (piece.type == Piece::Pawn && (endPosition.x == 1 || endPosition.x == 8)) {
  387. for (auto newPieceType : {Piece::Queen, Piece::Knight, Piece::Bishop, Piece::Rook}) {
  388. newBoard.pieces[pieceIdx].type = newPieceType;
  389. if (!newBoard.isInCheck(activeColor)) {
  390. newBoards.push_back(newBoard);
  391. }
  392. }
  393. } else if (!newBoard.isInCheck(activeColor)) {
  394. newBoards.push_back(newBoard);
  395. }
  396. }
  397. }
  398.  
  399. // implement en passant
  400. if (enPassant.x != -1) {
  401. int upDir = (activeColor == 'w' ? 1 : -1);
  402. for (int dir : {-1, 1}) {
  403. Cell capturePawn = enPassant + Cell(-upDir, dir);
  404. Cell toCapturePawn = enPassant + Cell(-upDir, 0);
  405. if (capturePawn.inRange() &&
  406. ((activeColor == 'w' && b[capturePawn.x][capturePawn.y] == 'P') ||
  407. (activeColor == 'b' && b[capturePawn.x][capturePawn.y] == 'p'))) {
  408. BoardState newBoard;
  409. newBoard.pieces = pieces;
  410. newBoard.activeColor = newColor;
  411. newBoard.whiteCastling = whiteCastling;
  412. newBoard.blackCastling = blackCastling;
  413. newBoard.fullMoves = fullMoves + 1;
  414. newBoard.halfMoves = 0;
  415. newBoard.enPassant = Cell(-1, -1);
  416. for (auto & piece : newBoard.pieces) {
  417. if (piece.cell == capturePawn) {
  418. piece.cell = enPassant;
  419. break;
  420. }
  421. }
  422. for (int pieceIdx = 0; pieceIdx < newBoard.pieces.size(); ++pieceIdx) {
  423. if (newBoard.pieces[pieceIdx].cell == toCapturePawn) {
  424. std::swap(newBoard.pieces[pieceIdx], newBoard.pieces.back());
  425. newBoard.pieces.pop_back();
  426. break;
  427. }
  428. }
  429. if (!isInCheck(activeColor)) {
  430. newBoards.push_back(newBoard);
  431. }
  432. }
  433. }
  434. }
  435. // implement castling
  436. if (activeColor == 'w') {
  437. vector<vector<bool>> attacked = attackedCells(newColor);
  438. if (whiteCastling & 1) {
  439. bool invalid = false;
  440. for (int col = 6; col <= 7; ++col) {
  441. if (b[1][col] != 0) {
  442. invalid = true;
  443. break;
  444. }
  445. }
  446. for (int col = 5; col <= 6; ++col) {
  447. if (attacked[1][col]) {
  448. invalid = true;
  449. break;
  450. }
  451. }
  452. if (!invalid) {
  453. BoardState newBoard;
  454. newBoard.pieces = pieces;
  455. newBoard.activeColor = newColor;
  456. newBoard.whiteCastling = 0;
  457. newBoard.blackCastling = blackCastling;
  458. newBoard.fullMoves = fullMoves + 1;
  459. newBoard.halfMoves = halfMoves + 1;
  460. newBoard.enPassant = Cell(-1, -1);
  461. for (auto & piece : newBoard.pieces) {
  462. if (piece.cell == Cell(1, 5)) {
  463. piece.cell = Cell(1, 7);
  464. break;
  465. }
  466. }
  467. for (auto & piece : newBoard.pieces) {
  468. if (piece.cell == Cell(1, 8)) {
  469. piece.cell = Cell(1, 6);
  470. break;
  471. }
  472. }
  473. if (!isInCheck(activeColor)) {
  474. newBoards.push_back(newBoard);
  475. }
  476. }
  477. }
  478. if (whiteCastling & 2) {
  479. bool invalid = false;
  480. for (int col = 2; col <= 4; ++col) {
  481. if (b[1][col] != 0) {
  482. invalid = true;
  483. break;
  484. }
  485. }
  486. for (int col = 3; col <= 5; ++col) {
  487. if (attacked[1][col]) {
  488. invalid = true;
  489. break;
  490. }
  491. }
  492. if (!invalid) {
  493. BoardState newBoard;
  494. newBoard.pieces = pieces;
  495. newBoard.activeColor = newColor;
  496. newBoard.whiteCastling = 0;
  497. newBoard.blackCastling = blackCastling;
  498. newBoard.fullMoves = fullMoves + 1;
  499. newBoard.halfMoves = halfMoves + 1;
  500. newBoard.enPassant = Cell(-1, -1);
  501. for (auto & piece : newBoard.pieces) {
  502. if (piece.cell == Cell(1, 5)) {
  503. piece.cell = Cell(1, 3);
  504. break;
  505. }
  506. }
  507. for (auto & piece : newBoard.pieces) {
  508. if (piece.cell == Cell(1, 1)) {
  509. piece.cell = Cell(1, 4);
  510. break;
  511. }
  512. }
  513. if (!isInCheck(activeColor)) {
  514. newBoards.push_back(newBoard);
  515. }
  516. }
  517. }
  518. } else {
  519. vector<vector<bool>> attacked = attackedCells(newColor);
  520. if (blackCastling & 1) {
  521. bool invalid = false;
  522. for (int col = 6; col <= 7; ++col) {
  523. if (b[8][col] != 0) {
  524. invalid = true;
  525. break;
  526. }
  527. }
  528. for (int col = 5; col <= 6; ++col) {
  529. if (attacked[8][col]) {
  530. invalid = true;
  531. break;
  532. }
  533. }
  534. if (!invalid) {
  535. BoardState newBoard;
  536. newBoard.pieces = pieces;
  537. newBoard.activeColor = newColor;
  538. newBoard.whiteCastling = 0;
  539. newBoard.blackCastling = blackCastling;
  540. newBoard.fullMoves = fullMoves + 1;
  541. newBoard.halfMoves = halfMoves + 1;
  542. newBoard.enPassant = Cell(-1, -1);
  543. for (auto & piece : newBoard.pieces) {
  544. if (piece.cell == Cell(8, 5)) {
  545. piece.cell = Cell(8, 7);
  546. break;
  547. }
  548. }
  549. for (auto & piece : newBoard.pieces) {
  550. if (piece.cell == Cell(8, 8)) {
  551. piece.cell = Cell(8, 6);
  552. break;
  553. }
  554. }
  555. if (!isInCheck(activeColor)) {
  556. newBoards.push_back(newBoard);
  557. }
  558. }
  559. }
  560. if (blackCastling & 2) {
  561. bool invalid = false;
  562. for (int col = 2; col <= 4; ++col) {
  563. if (b[8][col] != 0) {
  564. invalid = true;
  565. break;
  566. }
  567. }
  568. for (int col = 3; col <= 5; ++col) {
  569. if (attacked[8][col]) {
  570. invalid = true;
  571. break;
  572. }
  573. }
  574. if (!invalid) {
  575. BoardState newBoard;
  576. newBoard.pieces = pieces;
  577. newBoard.activeColor = newColor;
  578. newBoard.whiteCastling = 0;
  579. newBoard.blackCastling = blackCastling;
  580. newBoard.fullMoves = fullMoves + 1;
  581. newBoard.halfMoves = halfMoves + 1;
  582. newBoard.enPassant = Cell(-1, -1);
  583. for (auto & piece : newBoard.pieces) {
  584. if (piece.cell == Cell(8, 5)) {
  585. piece.cell = Cell(8, 3);
  586. break;
  587. }
  588. }
  589. for (auto & piece : newBoard.pieces) {
  590. if (piece.cell == Cell(8, 1)) {
  591. piece.cell = Cell(8, 4);
  592. break;
  593. }
  594. }
  595. if (!isInCheck(activeColor)) {
  596. newBoards.push_back(newBoard);
  597. }
  598. }
  599. }
  600. }
  601. return newBoards;
  602. }
  603. };
  604.  
  605. inline BoardState parseFEN(string fen) {
  606. int currIndex = 0;
  607. BoardState board;
  608. for (int i = 8; i >= 1; --i) {
  609. int pos = 0;
  610. while (pos < 8) {
  611. if (isdigit(fen[currIndex])) {
  612. pos += fen[currIndex] - '0';
  613. } else {
  614. pos++;
  615. board.pieces.emplace_back(fen[currIndex], i, pos);
  616. }
  617. currIndex++;
  618. }
  619. currIndex++;
  620. }
  621.  
  622. board.activeColor = fen[currIndex];
  623. currIndex += 2;
  624.  
  625. board.whiteCastling = board.blackCastling = 0;
  626. while (fen[currIndex] != ' ') {
  627. if (fen[currIndex] == 'K')
  628. board.whiteCastling += 1;
  629. else if (fen[currIndex] == 'Q')
  630. board.whiteCastling += 2;
  631. else if (fen[currIndex] == 'k')
  632. board.blackCastling += 1;
  633. else if (fen[currIndex] == 'q')
  634. board.blackCastling += 2;
  635. currIndex++;
  636. }
  637.  
  638. currIndex++;
  639. if (fen[currIndex] == '-') {
  640. board.enPassant = Cell(-1, -1);
  641. currIndex += 2;
  642. } else {
  643. board.enPassant = Cell(fen[currIndex + 1] - '0', fen[currIndex] - 'a' + 1);
  644. currIndex += 3;
  645. }
  646.  
  647. board.halfMoves = 0;
  648. while (fen[currIndex] != ' ') {
  649. board.halfMoves = board.halfMoves * 10 + fen[currIndex] - '0';
  650. currIndex++;
  651. }
  652. currIndex++;
  653.  
  654. board.fullMoves = 0;
  655. while (currIndex < fen.size()) {
  656. board.fullMoves = board.fullMoves * 10 + fen[currIndex] - '0';
  657. currIndex++;
  658. }
  659.  
  660. return board;
  661. }
  662.  
  663. //string generateFEN(const BoardState& board, bool includeMoves) {
  664. // string fen = "";
  665. // char b[10][10];
  666. // memset(b, 0, sizeof(b));
  667. // for (const Piece& piece : board.pieces) {
  668. // char p;
  669. // if (piece.type == Piece::Pawn) {
  670. // p = 'p';
  671. // } else if (piece.type == Piece::Knight) {
  672. // p = 'n';
  673. // } else if (piece.type == Piece::Bishop) {
  674. // p = 'b';
  675. // } else if (piece.type == Piece::Rook) {
  676. // p = 'r';
  677. // } else if (piece.type == Piece::Queen) {
  678. // p = 'q';
  679. // } else if (piece.type == Piece::King) {
  680. // p = 'k';
  681. // }
  682. // if (piece.color == 'w')
  683. // p = toupper(p);
  684. // b[piece.cell.x][piece.cell.y] = p;
  685. // }
  686. //
  687. // for (int i = 8; i >= 1; --i) {
  688. // int pos = 0;
  689. // for (int j = 1; j <= 8; ++j) {
  690. // if (b[i][j] == 0) {
  691. // pos++;
  692. // } else {
  693. // if (pos > 0) {
  694. // fen += to_string(pos);
  695. // pos = 0;
  696. // }
  697. // fen += b[i][j];
  698. // }
  699. // }
  700. // if (pos != 0)
  701. // fen += to_string(pos);
  702. // if (i == 1) {
  703. // fen += " ";
  704. // } else {
  705. // fen += "/";
  706. // }
  707. // }
  708. //
  709. // fen += board.activeColor;
  710. // fen += " ";
  711. //
  712. // if (board.whiteCastling == 0 && board.blackCastling == 0)
  713. // fen += "-";
  714. // else {
  715. // if (board.whiteCastling & 1) {
  716. // fen += "K";
  717. // }
  718. // if (board.whiteCastling & 2) {
  719. // fen += "Q";
  720. // }
  721. // if (board.blackCastling & 1) {
  722. // fen += "k";
  723. // }
  724. // if (board.blackCastling & 2) {
  725. // fen += "q";
  726. // }
  727. // }
  728. // fen += " ";
  729. //
  730. // if (board.enPassant.x == -1) {
  731. // fen += "-";
  732. // } else {
  733. // fen += ('a' + board.enPassant.y - 1);
  734. // fen += ('0' + board.enPassant.x);
  735. // }
  736. //
  737. // if (includeMoves) {
  738. // fen += " ";
  739. // fen += to_string(board.halfMoves);
  740. // fen += " ";
  741. // fen += to_string(board.fullMoves);
  742. // }
  743. //
  744. // return fen;
  745. //}
  746.  
  747. struct SortedBoards {
  748. BoardState board;
  749. int value{};
  750. };
  751.  
  752. inline int computeBoardScore(const BoardState& board) {
  753. int score = 0;
  754. for (const Piece& piece : board.pieces) {
  755. int value = 0;
  756. if (piece.type == Piece::Pawn) {
  757. value = 1;
  758. } else if (piece.type == Piece::Bishop) {
  759. value = 3;
  760. } else if (piece.type == Piece::Knight) {
  761. value = 3;
  762. } else if (piece.type == Piece::Rook) {
  763. value = 5;
  764. } else if (piece.type == Piece::Queen) {
  765. value = 9;
  766. }
  767. if (piece.color == 'w')
  768. score += value;
  769. else
  770. score -= value;
  771. }
  772. return score;
  773. }
  774.  
  775. inline int alphaBetaMiniMax(const BoardState& board, int depth, int alpha, int beta) {
  776. if (depth >= 6)
  777. return 0;
  778. if (board.isDraw())
  779. return 0;
  780. if (board.isCheckMate()) {
  781. if (board.activeColor == 'w') {
  782. return -maxv + depth;
  783. } else {
  784. return maxv - depth;
  785. }
  786. }
  787. vector<BoardState> generatedBoards = board.generateAllMoves();
  788. vector<SortedBoards> sortedBoards(generatedBoards.size());
  789. for (int i = 0; i < generatedBoards.size(); ++i) {
  790. swap(sortedBoards[i].board, generatedBoards[i]);
  791. sortedBoards[i].value = computeBoardScore(sortedBoards[i].board);
  792. }
  793. if (board.activeColor == 'w') {
  794. int maxEval = -inf;
  795. sort(sortedBoards.begin(), sortedBoards.end(), [](const auto& b1, const auto& b2) {return b1.value > b2.value; });
  796. for (const auto& newBoard : sortedBoards) {
  797. int eval = alphaBetaMiniMax(newBoard.board, depth + 1, alpha, beta);
  798. maxEval = max(maxEval, eval);
  799. alpha = max(alpha, eval);
  800. if (beta <= alpha)
  801. break;
  802. }
  803. return maxEval;
  804. } else {
  805. int minEval = inf;
  806. sort(sortedBoards.begin(), sortedBoards.end(), [](const auto& b1, const auto& b2) {return b1.value < b2.value; });
  807. for (const auto& newBoard : sortedBoards) {
  808. int eval = alphaBetaMiniMax(newBoard.board, depth + 1, alpha, beta);
  809. minEval = min(minEval, eval);
  810. beta = min(beta, eval);
  811. if (beta <= alpha)
  812. break;
  813. }
  814. return minEval;
  815. }
  816. }
  817.  
  818. int main() {
  819. freopen("instances/easy/5.in", "r", stdin);
  820.  
  821. string fen;
  822. getline(cin, fen);
  823. BoardState board = parseFEN(fen);
  824.  
  825. int answer = alphaBetaMiniMax(board, 0, -inf, inf);
  826. if (answer == 0) {
  827. cout << "Draw" << endl;
  828. } else if (answer > 0) {
  829. cout << "W M" << (-answer + maxv + 1) / 2 << endl;
  830. } else {
  831. cout << "B M" << (answer + maxv + 1) / 2 << endl;
  832. }
  833.  
  834. return 0;
  835. }
  836.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!