diff options
| -rw-r--r-- | Applications/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | Applications/ChessEngine/CMakeLists.txt | 8 | ||||
| -rw-r--r-- | Applications/ChessEngine/ChessEngine.cpp | 76 | ||||
| -rw-r--r-- | Applications/ChessEngine/ChessEngine.h | 49 | ||||
| -rw-r--r-- | Applications/ChessEngine/MCTSTree.cpp | 180 | ||||
| -rw-r--r-- | Applications/ChessEngine/MCTSTree.h | 67 | ||||
| -rw-r--r-- | Applications/ChessEngine/main.cpp | 36 | ||||
| -rw-r--r-- | Games/Chess/ChessWidget.cpp | 2 | ||||
| -rw-r--r-- | Libraries/LibChess/Chess.cpp | 80 | ||||
| -rw-r--r-- | Libraries/LibChess/Chess.h | 5 |
10 files changed, 501 insertions, 3 deletions
diff --git a/Applications/CMakeLists.txt b/Applications/CMakeLists.txt index 7de20e579d..e8fa7ff023 100644 --- a/Applications/CMakeLists.txt +++ b/Applications/CMakeLists.txt @@ -2,6 +2,7 @@ add_subdirectory(About) add_subdirectory(Browser) add_subdirectory(Calculator) add_subdirectory(Calendar) +add_subdirectory(ChessEngine) add_subdirectory(Debugger) add_subdirectory(DisplaySettings) add_subdirectory(FileManager) diff --git a/Applications/ChessEngine/CMakeLists.txt b/Applications/ChessEngine/CMakeLists.txt new file mode 100644 index 0000000000..288529a100 --- /dev/null +++ b/Applications/ChessEngine/CMakeLists.txt @@ -0,0 +1,8 @@ +set(SOURCES + ChessEngine.cpp + main.cpp + MCTSTree.cpp +) + +serenity_bin(ChessEngine) +target_link_libraries(ChessEngine LibChess LibCore) diff --git a/Applications/ChessEngine/ChessEngine.cpp b/Applications/ChessEngine/ChessEngine.cpp new file mode 100644 index 0000000000..16394d443c --- /dev/null +++ b/Applications/ChessEngine/ChessEngine.cpp @@ -0,0 +1,76 @@ +/* + * Copyright (c) 2020, the SerenityOS developers. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ChessEngine.h" +#include "MCTSTree.h" +#include <LibCore/ElapsedTimer.h> + +using namespace Chess::UCI; + +void ChessEngine::handle_uci() +{ + send_command(IdCommand(IdCommand::Type::Name, "ChessEngine")); + send_command(IdCommand(IdCommand::Type::Author, "the SerenityOS developers")); + send_command(UCIOkCommand()); +} + +void ChessEngine::handle_position(const PositionCommand& command) +{ + // FIXME: Implement fen board position. + ASSERT(!command.fen().has_value()); + m_board = Chess::Board(); + for (auto& move : command.moves()) { + ASSERT(m_board.apply_move(move)); + } +} + +void ChessEngine::handle_go(const GoCommand& command) +{ + // FIXME: A better algorithm than naive mcts. + // FIXME: Add different ways to terminate search. + ASSERT(command.movetime.has_value()); + + srand(arc4random()); + + Core::ElapsedTimer elapsed_time; + elapsed_time.start(); + + MCTSTree mcts(m_board); + + // FIXME: optimize simulations enough for use. + mcts.set_eval_method(MCTSTree::EvalMethod::Heuristic); + + int rounds = 0; + while (elapsed_time.elapsed() <= command.movetime.value()) { + mcts.do_round(); + ++rounds; + } + dbg() << "MCTS finished " << rounds << " rounds."; + dbg() << "MCTS evaluation " << mcts.expected_value(); + auto best_move = mcts.best_move(); + dbg() << "MCTS best move " << best_move.to_long_algebraic(); + send_command(BestMoveCommand(best_move)); +} diff --git a/Applications/ChessEngine/ChessEngine.h b/Applications/ChessEngine/ChessEngine.h new file mode 100644 index 0000000000..54c0cb7c8a --- /dev/null +++ b/Applications/ChessEngine/ChessEngine.h @@ -0,0 +1,49 @@ +/* + * Copyright (c) 2020, the SerenityOS developers. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#pragma once + +#include <LibChess/Chess.h> +#include <LibChess/UCIEndpoint.h> + +class ChessEngine : public Chess::UCI::Endpoint { + C_OBJECT(ChessEngine) +public: + virtual ~ChessEngine() override { } + + ChessEngine() { } + ChessEngine(NonnullRefPtr<Core::IODevice> in, NonnullRefPtr<Core::IODevice> out) + : Endpoint(in, out) + { + } + + virtual void handle_uci(); + virtual void handle_position(const Chess::UCI::PositionCommand&); + virtual void handle_go(const Chess::UCI::GoCommand&); + +private: + Chess::Board m_board; +}; diff --git a/Applications/ChessEngine/MCTSTree.cpp b/Applications/ChessEngine/MCTSTree.cpp new file mode 100644 index 0000000000..1724f7acd8 --- /dev/null +++ b/Applications/ChessEngine/MCTSTree.cpp @@ -0,0 +1,180 @@ +/* + * Copyright (c) 2020, the SerenityOS developers. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "MCTSTree.h" +#include <AK/String.h> +#include <stdlib.h> + +MCTSTree::MCTSTree(const Chess::Board& board, double exploration_parameter, MCTSTree* parent) + : m_parent(parent) + , m_exploration_parameter(exploration_parameter) + , m_board(board) +{ + if (m_parent) + m_eval_method = m_parent->eval_method(); +} + +MCTSTree& MCTSTree::select_leaf() +{ + if (!expanded() || m_children.size() == 0) + return *this; + + MCTSTree* node = nullptr; + double max_uct = -double(INFINITY); + for (auto& child : m_children) { + double uct = child.uct(m_board.turn()); + if (uct >= max_uct) { + max_uct = uct; + node = &child; + } + } + ASSERT(node); + return node->select_leaf(); +} + +MCTSTree& MCTSTree::expand() +{ + ASSERT(!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, m_exploration_parameter, this)); + return IterationDecision::Continue; + }); + m_moves_generated = true; + } + + if (m_children.size() == 0) { + return *this; + } + + for (auto& child : m_children) { + if (child.m_simulations == 0) { + return child; + } + } + ASSERT_NOT_REACHED(); +} + +int MCTSTree::simulate_game() const +{ + ASSERT_NOT_REACHED(); + Chess::Board clone = m_board; + while (!clone.game_finished()) { + clone.apply_move(clone.random_move()); + } + return clone.game_score(); +} + +int MCTSTree::heuristic() const +{ + if (m_board.game_finished()) + return m_board.game_score(); + + double winchance = max(min(double(m_board.material_imbalance()) / 6, 1.0), -1.0); + + double random = double(rand()) / RAND_MAX; + if (winchance >= random) + return 1; + if (winchance <= -random) + return -1; + + return 0; +} + +void MCTSTree::apply_result(int game_score) +{ + m_simulations++; + m_white_points += game_score; + + if (m_parent) + m_parent->apply_result(game_score); +} + +void MCTSTree::do_round() +{ + auto& node = select_leaf().expand(); + + int result; + if (m_eval_method == EvalMethod::Simulation) { + result = node.simulate_game(); + } else { + result = node.heuristic(); + } + node.apply_result(result); +} + +Chess::Move MCTSTree::best_move() const +{ + int score_multiplier = (m_board.turn() == Chess::Colour::White) ? 1 : -1; + + Chess::Move best_move = { { 0, 0 }, { 0, 0 } }; + double best_score = -double(INFINITY); + ASSERT(m_children.size()); + for (auto& node : m_children) { + double node_score = node.expected_value() * score_multiplier; + if (node_score >= best_score) { + // The best move is the last move made in the child. + best_move = node.m_board.moves()[node.m_board.moves().size() - 1]; + best_score = node_score; + } + } + + return best_move; +} + +double MCTSTree::expected_value() const +{ + if (m_simulations == 0) + return 0; + + return double(m_white_points) / m_simulations; +} + +double MCTSTree::uct(Chess::Colour colour) const +{ + // UCT: Upper Confidence Bound Applied to Trees. + // Kocsis, Levente; Szepesvári, Csaba (2006). "Bandit based Monte-Carlo Planning" + + // Fun fact: Szepesvári was my data structures professor. + double expected = expected_value() * ((colour == Chess::Colour::White) ? 1 : -1); + return expected + m_exploration_parameter * sqrt(log(m_parent->m_simulations) / m_simulations); +} + +bool MCTSTree::expanded() const +{ + if (!m_moves_generated) + return false; + + for (auto& child : m_children) { + if (child.m_simulations == 0) + return false; + } + + return true; +} diff --git a/Applications/ChessEngine/MCTSTree.h b/Applications/ChessEngine/MCTSTree.h new file mode 100644 index 0000000000..857a4c4110 --- /dev/null +++ b/Applications/ChessEngine/MCTSTree.h @@ -0,0 +1,67 @@ +/* + * Copyright (c) 2020, the SerenityOS developers. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#pragma once + +#include <AK/Function.h> +#include <AK/NonnullOwnPtrVector.h> +#include <LibChess/Chess.h> +#include <math.h> + +class MCTSTree { +public: + enum EvalMethod { + Simulation, + Heuristic, + }; + + MCTSTree(const Chess::Board& board, double exploration_parameter = sqrt(2), MCTSTree* parent = nullptr); + + MCTSTree& select_leaf(); + MCTSTree& expand(); + int simulate_game() const; + int heuristic() const; + void apply_result(int game_score); + void do_round(); + + Chess::Move best_move() const; + double expected_value() const; + double uct(Chess::Colour colour) const; + bool expanded() const; + + EvalMethod eval_method() const { return m_eval_method; } + void set_eval_method(EvalMethod method) { m_eval_method = method; } + +private: + NonnullOwnPtrVector<MCTSTree> m_children; + MCTSTree* m_parent { nullptr }; + int m_white_points { 0 }; + int m_simulations { 0 }; + bool m_moves_generated { false }; + double m_exploration_parameter; + EvalMethod m_eval_method { EvalMethod::Simulation }; + Chess::Board m_board; +}; diff --git a/Applications/ChessEngine/main.cpp b/Applications/ChessEngine/main.cpp new file mode 100644 index 0000000000..185b6f065c --- /dev/null +++ b/Applications/ChessEngine/main.cpp @@ -0,0 +1,36 @@ +/* + * Copyright (c) 2020, the SerenityOS developers. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ChessEngine.h" +#include <LibCore/EventLoop.h> +#include <LibCore/File.h> + +int main() +{ + Core::EventLoop loop; + auto engine = ChessEngine::construct(Core::File::stdin(), Core::File::stdout()); + return loop.exec(); +} diff --git a/Games/Chess/ChessWidget.cpp b/Games/Chess/ChessWidget.cpp index bd18c5d895..cc936cb21e 100644 --- a/Games/Chess/ChessWidget.cpp +++ b/Games/Chess/ChessWidget.cpp @@ -272,7 +272,7 @@ void ChessWidget::maybe_input_engine_move() if (drag_was_enabled) set_drag_enabled(false); - m_engine->get_best_move(board(), 500, [this, drag_was_enabled](Chess::Move move) { + m_engine->get_best_move(board(), 4000, [this, drag_was_enabled](Chess::Move move) { set_drag_enabled(drag_was_enabled); ASSERT(board().apply_move(move)); update(); diff --git a/Libraries/LibChess/Chess.cpp b/Libraries/LibChess/Chess.cpp index 7495acf0fb..6e332e3cc4 100644 --- a/Libraries/LibChess/Chess.cpp +++ b/Libraries/LibChess/Chess.cpp @@ -425,8 +425,8 @@ bool Board::apply_illegal_move(const Move& move, Colour colour) if (move.to == Square("a8") || move.to == Square("c8")) { set_piece(Square("e8"), EmptyPiece); set_piece(Square("a8"), EmptyPiece); - set_piece(Square("c8"), { Colour::White, Type::King }); - set_piece(Square("d8"), { Colour::White, Type::Rook }); + set_piece(Square("c8"), { Colour::Black, Type::King }); + set_piece(Square("d8"), { Colour::Black, Type::Rook }); return true; } else if (move.to == Square("h8") || move.to == Square("g8")) { set_piece(Square("e8"), EmptyPiece); @@ -463,6 +463,23 @@ bool Board::apply_illegal_move(const Move& move, Colour colour) return true; } +Move Board::random_move(Colour colour) const +{ + if (colour == Colour::None) + colour = turn(); + + Move move = { { 50, 50 }, { 50, 50 } }; + int probability = 1; + generate_moves([&](Move m) { + if (rand() % probability == 0) + move = m; + ++probability; + return IterationDecision::Continue; + }); + + return move; +} + Board::Result Board::game_result() const { bool sufficient_material = false; @@ -533,6 +550,65 @@ Board::Result Board::game_result() const return Result::StaleMate; } +Colour Board::game_winner() const +{ + if (game_result() == Result::CheckMate) + return opposing_colour(turn()); + + return Colour::None; +} + +int Board::game_score() const +{ + switch (game_winner()) { + case Colour::White: + return +1; + case Colour::Black: + return -1; + case Colour::None: + return 0; + } + return 0; +} + +bool Board::game_finished() const +{ + return game_result() != Result::NotFinished; +} + +int Board::material_imbalance() const +{ + int imbalance = 0; + Square::for_each([&](Square square) { + int value = 0; + switch (get_piece(square).type) { + case Type::Pawn: + value = 1; + break; + case Type::Knight: + case Type::Bishop: + value = 3; + break; + case Type::Rook: + value = 5; + break; + case Type::Queen: + value = 9; + break; + default: + break; + } + + if (get_piece(square).colour == Colour::White) { + imbalance += value; + } else { + imbalance -= value; + } + return IterationDecision::Continue; + }); + return imbalance; +} + bool Board::is_promotion_move(const Move& move, Colour colour) const { if (colour == Colour::None) diff --git a/Libraries/LibChess/Chess.h b/Libraries/LibChess/Chess.h index 2e9c078f78..f0e0b91aab 100644 --- a/Libraries/LibChess/Chess.h +++ b/Libraries/LibChess/Chess.h @@ -135,7 +135,12 @@ public: template<typename Callback> void generate_moves(Callback callback, Colour colour = Colour::None) const; + Move random_move(Colour colour = Colour::None) const; Result game_result() const; + Colour game_winner() const; + int game_score() const; + bool game_finished() const; + int material_imbalance() const; Colour turn() const { return m_turn; } const Vector<Move>& moves() const { return m_moves; } |