PGN Parser

1. Overview

This parser is designed to support the PGN (Portable Game Notation) format, commonly used for recording chess games. The parser reads the movetext, which is written in Standard Algebraic Notation (SAN), and processes each move to update the internal chessboard state. It fully supports the PGN specification, ensuring compatibility with most chess applications.

At the end of the game, the board state is output in an 8x8 grid format, as shown below:

Input

1
1. e4 e6 2. e5 f6 3. exf6 gxf6 4. Ke2 h6 5. Ke3 h5 6. Ke4 e5 7. Nh3 d6 8. Ng5 Be6 9. Nf3 Bh3 10. Nc3 Bxg2 11. Na4 b6 12. Nc5 b5 13. Nd3 b4 14. Nxe5 b3 1/2-1/2

Output

1
2
3
4
5
6
7
8
bR|bN|  |bQ|bK|bB|bN|bR
bP|  |bP|  |  |  |  |  
  |  |  |bP|  |bP|  |  
  |  |  |  |wN|  |  |bP
  |  |  |  |wK|  |  |  
  |bP|  |  |  |wN|  |  
wP|wP|wP|wP|  |wP|bB|wP
wR|  |wB|wQ|  |wB|  |wR

Project Requirements

CMake 3.22
GCC 12.1 and C++20 standard
Ubuntu 23.10 or the Docker image iainttho/ubuntu:23.10.02 based on Ubuntu 23.10.

2. Architecture

This project uses a modern C++ design with CRTP (Curiously Recurring Template Pattern) and std::variant to represent pieces, providing a flexible and efficient approach to handle polymorphism without traditional inheritance or virtual function tables (vtables). The code achieves runtime polymorphism using std::visit for handling different types of pieces.

2.1 BasePiece Class

The BasePiece class provides the foundation for all chess pieces, using CRTP to allow specific behavior for each piece type. This avoids the overhead of virtual function calls while keeping the code type-safe and efficient.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
template <typename ConcretePiece> class BasePiece
{
  public:
    ...
    // Potential improvement with `this ConcretePiece&& self`
    ConcretePiece &self() { return *static_cast<ConcretePiece *>(this); }
    ConcretePiece const &self() const { return *static_cast<ConcretePiece const *>(this); }

    bool IsValidBasicMove(...) const {
        return self().IsValidBasicMove_(...);
    }
    ...
  protected:
    friend ConcretePiece;
    BasePiece(...) {}
    ...
};

2.2 Concrete Piece Classes

Each piece type (like Bishop, Knight, etc.) inherits from BasePiece and implements its specific movement logic.

1
2
3
4
5
6
7
8
9
class Bishop : public BasePiece<Bishop> {
  public:
    Bishop(...) : BasePiece(...) {}
    ...
  private:
    friend class BasePiece<Bishop>;
    bool IsValidBasicMove_(...) const;
    ...
};

2.3 Piece Representation Using `std::variant`

The chessboard contains pieces represented as std::variant, allowing it to store different types of pieces in the same container while retaining type safety.

1
2
3
using Piece = std::variant<EmptyPiece, Bishop, King, Knight, Pawn, Queen, Rook>;
using Pieces = std::vector<std::vector<Piece>>;
using PiecesReference = std::vector<std::reference_wrapper<const Piece>>;

2.4 Square Class

The Square class is responsible for processing moves and managing the state of the pieces. It validates moves, checks whether the king is in check, and applies the necessary updates to the board.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Square {
  public:
    ...
    PiecesReference GetPieceOfTypeAndColor(const PieceType &pieceType, const Color &color, ...) const {
      PiecesReference subPieces;
      ...
      return subPieces;
    }
    void ProcessBasicMove(...);

  private:
    ...
    Pieces pieces_;
  private:
    void ValidateMove(...);
    bool VerifyIfKingBeingCheck(...);
};

In Square::ProcessBasicMove, std::visit is used to handle pieces of different types polymorphically:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
Square::ProcessBasicMove(...)
{
    ...
    // Get pieces of a specific type (Pawn) and color (White)
    const PiecesReference &subPieces = GetPieceOfTypeAndColor(PieceType::Pawn, Color::White, ...);
    bool isValid = false;
    // Iterate through the pieces to check if any can perform a valid basic move
    for (auto &it : subPieces) {
        std::visit(
            [&](auto &&piece) {
                isValid = piece.IsValidBasicMove();
                ValidateMove(...);
            },
            it.get());
        if (isValid)
            break;
    }
    ...
}

2.5 Polymorphism without vtables

Utilizing std::visit for Type Handling:
- std::visit is a C++17 utility that enables the application of a callable, such as a lambda function, to the value stored in a std::variant. This feature is especially beneficial for managing the diverse types of pieces that may be contained within the variant, facilitating a form of polymorphism.
Collection of Variants:
- The subPieces variable is designed as a collection of std::variant, which allows it to store various types of chess pieces. This architecture supports the retention of type safety while accommodating multiple types within a single collection.
Method Invocation Without Type Knowledge:
- With std::visit, we can call methods on the pieces stored in the variant without prior knowledge of their specific types at compile time. The lambda function provided to std::visit executes with the actual type contained in the variant, streamlining operations on the pieces.
Achieving Polymorphic Behavior:
- The combination of std::visit and std::variant enables the implementation of polymorphic behavior without relying on traditional inheritance. This design choice ensures that multiple piece types can be managed in a type-safe manner, enhancing the flexibility and robustness of the system.

3. Pros and Cons

3.1 Pros

Type Safety: Guarantees type-safe operations with std::variant.
Polymorphism: Achieves runtime polymorphism without virtual function overhead.
Performance: Avoids pointer indirection and the cost of vtables, making the code more efficient.

3.2 Cons

Compile-time Knowledge: All possible types must be known at compile time.
Error Handling: Handling unexpected types or errors in std::variant can be complex.
Debugging: Debugging std::variant interactions can be challenging.
Memory Overhead: Variants may consume more memory if piece sizes differ significantly, leading to potential inefficiencies.

4. Improvements

Add iterative move parsing and game state tracking.
Support backward and forward navigation through the game’s moves.
Improve the piece swap mechanism for better handling of complex moves.

For more insights, refer to the following resources: