API tools faq
paste
Advertisement
VladNitu

mri

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