ChessEngine: Use reduced Board objects in MCTSTree

Monte-Carlo methods are known to intensively create nodes and in our
case each leaf of the tree stores a board. However, for this use case,
we don't need a full board object that also contains game information.

This patch adds a `clone_cleared()` method that return a clone without
game information and uses it when constructing the tree.
It allows the ChessEngine much more possibility before getting out of
memory.

3 files changed, 15 insertions, 4 deletions

diff --git a/Userland/Libraries/LibChess/Chess.cpp b/Userland/Libraries/LibChess/Chess.cpp
index 577e82fcb6..9cfbe3817e 100644
--- a/Userland/Libraries/LibChess/Chess.cpp
+++ b/Userland/Libraries/LibChess/Chess.cpp
@@ -259,6 +259,16 @@ Board::Board()
     set_piece(Square("h8"), { Color::Black, Type::Rook });
 }
 
+Board Board::clone_without_history() const
+{
+    // Note: When used in the MCTSTree, the board doesn't need to have all information about previous states.
+    // It spares a huge amount of memory.
+    auto result = *this;
+    result.m_moves.clear();
+    result.m_previous_states.clear();
+    return result;
+}
+
 String Board::to_fen() const
 {
     StringBuilder builder;
diff --git a/Userland/Libraries/LibChess/Chess.h b/Userland/Libraries/LibChess/Chess.h
index a67e173a93..44a542c8dd 100644
--- a/Userland/Libraries/LibChess/Chess.h
+++ b/Userland/Libraries/LibChess/Chess.h
@@ -117,6 +117,7 @@ struct Move {
 class Board {
 public:
     Board();
+    Board clone_without_history() const;
 
     Piece get_piece(Square const&) const;
     Piece set_piece(Square const&, Piece const&);
diff --git a/Userland/Services/ChessEngine/MCTSTree.cpp b/Userland/Services/ChessEngine/MCTSTree.cpp
index a1a65af4d0..524b347104 100644
--- a/Userland/Services/ChessEngine/MCTSTree.cpp
+++ b/Userland/Services/ChessEngine/MCTSTree.cpp
@@ -39,10 +39,10 @@ MCTSTree& MCTSTree::expand()
     VERIFY(!expanded() || m_children.size() == 0);
 
     if (!m_moves_generated) {
-        m_board->generate_moves([&](Chess::Move move) {
-            Chess::Board clone = *m_board;
-            clone.apply_move(move);
-            m_children.append(make<MCTSTree>(clone, this));
+        m_board->generate_moves([&](Chess::Move chess_move) {
+            auto clone = m_board->clone_without_history();
+            clone.apply_move(chess_move);
+            m_children.append(make<MCTSTree>(move(clone), this));
             return IterationDecision::Continue;
         });
         m_moves_generated = true;