API tools faq
paste
Advertisement
VladNitu

mriv3_7feb

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