2
\$\begingroup\$

Important

Prebuilt Python Extensions built for Python 3.6

Includes Python f-strings (3.6+)

Complementary GitHub link

https://github.com/thejhonnyguy/CPyMCTS

Notable: Previous attempt with stock Python

Stock Monte Carlo Tree Search implementation to a simple connect 5 game in Python (Includes bugs)

C++ is the star of the show today with a custom MCTS implementation for the 5 in a row game. To build the pyd I used boost.python with Python 3.6 amd64 and x86 versions. (3.6.4 amd64, 3.6.5 x86)

C++

main.cpp

#define BOOST_PYTHON_STATIC_LIB
#include <string>
#include "boost/python.hpp"
#include "boost/python/def.hpp"
#include "boost/python/module.hpp"

#include "board.h"
#include "search.h"


BOOST_PYTHON_FUNCTION_OVERLOADS(search_overloads, search, 2, 3);


BOOST_PYTHON_MODULE(cpymcts)
{
    using namespace boost::python;
    class_<Board>("Board", init<>())
        .def(init<int>())
        .def("reset", &Board::reset)
        .def("play", &Board::playMove)
        .def("undo", &Board::undoMove)
        .def("get", &Board::getBoardPos)
        .def("check_win", &Board::checkWin)
        .add_property("string", &Board::showString)
        .add_property("size", &Board::getSize)
        .add_property("move_count", &Board::getMoves)
        ;
    def("search", search, search_overloads());
}

Below: Node class contained within node.h and node.cpp

node.h

#pragma once
#include "board.h"
#include <vector>
#include <string>
#include <memory>

// Node class

class Node
{
public:
    Node *parentNode;
    std::vector<std::unique_ptr<Node>> children;
    unsigned long visits;
    long long score;
    unsigned long visit_offset;
    int team_multiplier;
    int move_to[2];
    bool terminal;
    int termscore;

    // Constructors
    // Default. Will assume top node
    Node();
    // Norm
    Node(Node *parent, unsigned long offset, int mt_r, int mt_c, int term = 0);

    //Methods
    void Backtrack();
    void CreateChild(unsigned long offset, int mt_r, int mt_c, int term = 0);
    void BackPropagateScore(int s);
    bool IsLeaf();
    double ucb1();
    double ucb1(double exploration);
    Node* SelectBest(Board * board);
};

node.cpp

#include "node.h"
#include "board.h"
#include <string>
#include <iostream>
#include <limits>


// Node implementations

Node::Node()
{
    // Default constuctor
    // Node * parentNode will be left undefined
    // It is the duty of the programmer to not do anything foolish
    parentNode = nullptr;
    visits = 0, score = 0, visit_offset = 0, team_multiplier = 1;
}

Node::Node(Node *parent, unsigned long offset, int mt_r, int mt_c, int term)
{
    // Constructor used when the node is not the top node.
    // int term default value 0
    parentNode = parent;
    move_to[0] = mt_r; move_to[1] = mt_c;
    visits = 0, score = 0, visit_offset = offset, team_multiplier = -parent->team_multiplier;
    if (term) terminal = true;
    termscore = term;
}

void Node::Backtrack()
{
    std::cout << "yeet" << std::endl;
    if (parentNode == nullptr) return;
    parentNode->Backtrack();
}

void Node::CreateChild(unsigned long offset, int mt_r, int mt_c, int term)
{
    // Creates a child and appends it to Node<std::unique_ptr<Node>> children
    // Nodes created here use the second constructor,
    // and `this` is the parent of its children, hence the `this` argument
    children.push_back(std::make_unique<Node>(this, offset, mt_r, mt_c, term));
}

void Node::BackPropagateScore(int s)
{
    ++visits;
    score += s;
    if (parentNode == nullptr) return;
    parentNode->BackPropagateScore(s);
}

bool Node::IsLeaf()
{
    return !children.size();
}

double Node::ucb1()
{
    return ucb1(sqrt(2));
}

double Node::ucb1(double exploration)
{
    if (!visits) return std::numeric_limits<double>::infinity();
    double average = (double)score / visits;
    return team_multiplier * average + exploration * sqrt(log(parentNode->visits) / visits);
}

Node* Node::SelectBest(Board * board)
{
    if (parentNode != nullptr) board->playMove(move_to[0], move_to[1]);
    // This will only have effect on the top node.
    if (IsLeaf()) return this;
    double max_value = -1.0;
    int max_index = 0;
    for (unsigned int i = 0; i < children.size(); i++)
    {
        double tmp = children[i]->ucb1();
        if (tmp > max_value)
        {
            max_value = tmp;
            max_index = i;
        }
    }
    return children[max_index]->SelectBest(board);
}

Below: Board class contained within board.h and board.cpp

board.h

#pragma once
#include <vector>
#include <array>


// Class declaration and class method declarations go in the .h file here

class Board
{
private:
    short board[23][23];
    int lastPlaced[2];
    int size;
    int moves;
    std::vector<std::array<int, 2>> playedPieces;

public:

    Board(); // Default initialization to 19x19 board
    Board(int); // Initialization to NxN board

    std::string showString();
    void print();
    void reset();
    void playMove(int, int);
    void undoMove();
    void replayMoves();
    void manOverridePlayedPieces(std::vector<std::array<int, 2>> ov);
    int checkWin();
    int getMoves();
    int getSize();
    int getBoardPos(int r, int c);

    std::vector<std::array<int, 2>> getObvMoves();
};

board.cpp

#include "board.h"
#include <string>
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>


// Board class implementation goes here (the literal functions)

Board::Board()
{
    size = 19;
    reset();
}

Board::Board(const int s)
{
    size = (s < 19) ? s : 19;
    reset();
}

std::string Board::showString()
{
    std::string str;
    for (int r = 0; r < size; ++r)
    {
        for (int c = 0; c < size; ++c)
        {
            str += std::to_string(board[r][c]);
            if (board[r][c] != -1) str += " ";
        }
        str += "\n";
    }
    return str;
}

void Board::print()
{
    for (int r = 0; r < size; ++r)
    {
        for (int c = 0; c < size; ++c)
        {
            std::cout << board[r][c] << "\t";
        }
        std::cout << std::endl;
    }
}

void Board::reset()
{
    // Reset values
    moves = 0;

    // Reset board
    for (int r = 0; r < 23; ++r)
    {
        for (int c = 0; c < 23; ++c)
        {
            board[r][c] = 0;
        }
    }

    playedPieces.clear();
}


void Board::playMove(int r, int c)
{
    if (!board[r][c])
    {
        board[r][c] = (moves % 2) * 2 - 1;
    }
    else return;
    ++moves;

    lastPlaced[0] = r;
    lastPlaced[1] = c;
    std::array<int, 2> lp{ { r,c } };
    playedPieces.push_back(lp);
}

void Board::undoMove()
{
    board[lastPlaced[0]][lastPlaced[1]] = 0;
    --moves;
    playedPieces.pop_back();
    if (playedPieces.size())
    {
        lastPlaced[0] = playedPieces[playedPieces.size() - 1][0];
        lastPlaced[1] = playedPieces[playedPieces.size() - 1][1];
    }
}

void Board::replayMoves()
{
    std::cout << "Replaying moves:" << std::endl;
    for (unsigned int i = 0; i < playedPieces.size(); ++i)
    {
        std::cout << i << ": " << playedPieces[i][0] << ", " << playedPieces[i][1] << std::endl;
    }
}

void Board::manOverridePlayedPieces(std::vector<std::array<int, 2>> ov)
{
    playedPieces = ov;
    moves = playedPieces.size();
}


int Board::checkWin()
{
    if (!moves) return 0;
    // Fast version: Check only the surroundings of the last placed piece
    int locR{ lastPlaced[0] };
    int locC{ lastPlaced[1] };

    // Check horizontal of the area. Verified to work.
    int startC{ (locC - 4 < 0) ? 0 : locC - 4 };
    int endC{ (size - locC >= 4) ? locC : size - 4 }; // Maths checks out
    for (int sC = startC; sC <= endC; ++sC)
    {
        int sum{ 0 };
        for (int a = 0; a < 5; ++a)
        {
            sum += board[locR][sC + a];
        }
        if (sum == -5)
        {
            return -1;
        }
        if (sum == 5)
        {
            return 1;
        }
    }

    // Check vertical of the area. Seems to work as well...
    int startR{ (locR - 4 < 0) ? 0 : locR - 4 };
    int endR{ (size - locR >= 4) ? locR : size - 4 };
    for (int sR = startR; sR <= endR; ++sR)
    {
        int sum{ 0 };
        for (int a = 0; a < 5; ++a)
        {
            sum += board[sR + a][locC];
        }
        if (sum == -5)
        {
            return -1;
        }
        if (sum == 5)
        {
            return 1;
        }
    }

    // Check the \ diagonal (top left to bottom right)
    // startR and startC will be used from above code for streamlining
    // delta-Row / delta-Col to be used in future
    int dRow = locR - startR;
    int dCol = locC - startC;
    int offset{ (dRow < dCol) ? dRow : dCol };
    // Too lazy for now to program more to truncate the search if it goes out of the zone
    // trust me I'm a programmer and it won't go out of index
    for (int sD = -offset; sD <= 0; ++sD)
    {
        int sum{ 0 };
        for (int a = 0; a < 5; ++a)
        {
            sum += board[locR + sD + a][locC + sD + a];
            //std::cout << "Access: " << locR + sD + a << " " << locC + sD + a << std::endl;
        }
        if (sum == -5)
        {
            return -1;
        }
        if (sum == 5)
        {
            return 1;
        }
    }

    // Check the / diagonal (bottom left to top right) - holy shit I hope this works
    // Calculate the offset to the left of which we start looking
    // Reuse `dRow` from last time
    offset = dCol; // I put a buffer so it won't go out of range
                   // Scenario: Top left of board. Program will go too far up. Going too far up is the only concern.
    int truncate{ (dRow < 4) ? dRow - 4 : 0 };
    for (int sD = -offset; sD <= truncate; ++sD)
    {
        int sum{ 0 };
        for (int a = 0; a < 5; ++a)
        {
            sum += board[locR - sD - a][locC + sD + a];
            //std::cout << "Access: " << (locR + sD + a) << " " << (locC + sD + 4 - a) << std::endl;
            //std::cout << board[locR + sD + a][locC + sD + 4 - a] << " log" << std::endl;
        }
        if (sum == -5)
        {
            return -1;
        }
        if (sum == 5)
        {
            return 1;
        }
    }

    // Draw
    return 0;
}

int Board::getMoves()
{
    return moves;
}

int Board::getSize()
{
    return size;
}

int Board::getBoardPos(int r, int c)
{
    return board[r][c];
}

std::vector<std::array<int, 2>> Board::getObvMoves() //TODO
{
    std::vector<std::array<int, 2>> adjCells;

    for (const std::array<int, 2>& piece : playedPieces)
    {
        int cpR = piece[0];
        int cpC = piece[1];

        std::vector<std::array<int, 2>> direcs;
        // Above
        direcs.push_back({ cpR - 1, cpC - 1 });
        direcs.push_back({ cpR - 1, cpC });
        direcs.push_back({ cpR - 1, cpC + 1 });
        // Beside
        direcs.push_back({ cpR, cpC - 1 });
        direcs.push_back({ cpR, cpC + 1 });
        // Below
        direcs.push_back({ cpR + 1, cpC - 1 });
        direcs.push_back({ cpR + 1, cpC });
        direcs.push_back({ cpR + 1, cpC + 1 });
        for (const std::array<int, 2>& direc : direcs)
        {
            if (std::find(adjCells.begin(), adjCells.end(), direc) != adjCells.end()) continue;
            if (direc[0] < 0 || direc[0] >= size || direc[1] < 0 || direc[1] >= size) continue;
            if (board[direc[0]][direc[1]]) continue;
            adjCells.push_back(direc);
        }
    }

    return adjCells;
}

Below: The MCTS algorithm used contained within search.h and search.cpp

search.h

#pragma once
#define BOOST_PYTHON_STATIC_LIB
#include "boost/python/tuple.hpp"

#include "board.h"
#include "node.h"


boost::python::tuple search(Board inBoard, int team, unsigned long iterations = 10000);
void viewStats(Node* n, int t);
int simulation(Board board);
int simulation(Board board, bool rebuild);

search.cpp

#define BOOST_PYTHON_STATIC_LIB
#include "boost/python/tuple.hpp"

#include "search.h"
#include "node.h"
#include <iostream>
#include <vector>
#include <algorithm>


boost::python::tuple search(Board inBoard, int team, unsigned long iterations)
{
    std::cout << "Iterations being run: " << iterations << std::endl;
    if (!inBoard.getMoves())
    {
        std::cout << "Defaulting to middle of board for first move." << std::endl;
        return boost::python::make_tuple(inBoard.getSize() / 2, inBoard.getSize() / 2);
    }

    Node topNode;
    topNode.team_multiplier = -team;

    int info_every(std::max(unsigned long(2000), iterations / 5));

    /////////////////////////////// M C T S //////////////////////////////////
    for (unsigned long iteration = 0; iteration < iterations; ++iteration)
    {
        if (0 == iteration % info_every)
        {
            std::cout << "Progress %: " << iteration * 100 / iterations << std::endl;
            viewStats(&topNode, team);
        }
        Board tmp_board{ inBoard };
        Node* bestLeaf = topNode.SelectBest(&tmp_board);
        if (bestLeaf->terminal)
        {
            bestLeaf->BackPropagateScore(bestLeaf->termscore);
            continue;
        }
        if (!bestLeaf->visits)
        {
            int score = simulation(tmp_board, false);
            bestLeaf->BackPropagateScore(score);
            continue;
        }
        // Expand
        std::vector<std::array<int, 2>> obvMoves = tmp_board.getObvMoves();
        if (obvMoves.size() == 0)
        {
            bestLeaf->terminal = true;
            bestLeaf->termscore = 0; // tie
        }
        for (const std::array<int, 2>&move : obvMoves)
        {
            tmp_board.playMove(move[0], move[1]);
            int termscore = tmp_board.checkWin();
            if (termscore) bestLeaf->CreateChild(topNode.visits, move[0], move[1], termscore);
            bestLeaf->CreateChild(topNode.visits, move[0], move[1]);
            // Undo the move
            tmp_board.undoMove();
        }
    }

    // Suggest move

    int bestmove[2];
    unsigned long maxvisits = 0;
    for (const std::unique_ptr<Node>& move : topNode.children)
    {
        if (move->visits > maxvisits)
        {
            maxvisits = move->visits;
            bestmove[0] = move->move_to[0];
            bestmove[1] = move->move_to[1];
        }
    }
    std::cout << "Suggest: " << bestmove[0] << "," << bestmove[1] << std::endl;
    std::cout << "Win %:   " << team * topNode.score * 100 / topNode.visits << std::endl;

    return boost::python::make_tuple(bestmove[0], bestmove[1]);
}


void viewStats(Node * n, int t)
{
    if (n->children.size() == 0) return;
    int bestmove[2];
    unsigned long maxvisits = 0;
    for (const std::unique_ptr<Node>& move : n->children)
    {
        if (move->visits > maxvisits)
        {
            maxvisits = move->visits;
            bestmove[0] = move->move_to[0];
            bestmove[1] = move->move_to[1];
        }
    }
    if (maxvisits == 0 || n->visits == 0) return;
    std::cout << "Think: " << bestmove[0] << "," << bestmove[1] << std::endl;
    std::cout << "Win %: " << t * n->score * 100 / n->visits << "\n" << std::endl;
}


int simulation(Board board)
{
    return simulation(board, true);
}

int simulation(Board board, bool rebuild)
{
    if (rebuild)
    {
        /* Rebuild the board states to make sure it works properly
           Will not guarantee proper working order initially, but
               for the purpose of this function, it will suffice
        */
        std::vector<std::array<int, 2>> tmp;
        for (int r = 0; r < board.getSize(); ++r)
        {
            for (int c = 0; c < board.getSize(); ++c)
            {
                if (board.getBoardPos(r, c)) tmp.push_back(std::array<int, 2>{ r, c });
            }
        }
        board.manOverridePlayedPieces(tmp);
    }

    while (board.getMoves() < pow(board.getSize(), 2))
    {
        // Make a random move
        std::vector<std::array<int, 2>> choices = board.getObvMoves();
        std::array<int, 2> randMove = choices[rand() % choices.size()];
        board.playMove(randMove[0], randMove[1]);
        if (board.checkWin()) return board.checkWin();
    }
    return 0;
}

Python

Below: the loader and module scripts

loader.py

import sys


if sys.maxsize == 2147483647:  # 32 bit python install
    from x86.cpymcts import Board, search

else:  # 64 bit
    from x64.cpymcts import Board, search

Reach.py (fancy naming)

"""
This script is designed to function as a higher level interface
to an end user & programmer. It also handles input checking and such
NO functionality is removed because of this
"""
from typing import Tuple
from loader import Board as Board_, search as search_


class Board:

    def __init__(self, size: int = 19) -> None:
        if size <= 0:
            raise ValueError("Bad value for size.")
        if size > 19:
            raise ValueError("Size may not be larger than 19.")
        self.board = Board_(size)

    # Read only properties and (magic) methods
    def __str__(self) -> str:
        return self.board.string.replace('-1', 'X ').replace('1', 'O')

    @property
    def size(self) -> int:
        """Returns the size of the board. If 19x19 then will return 19"""
        return self.board.size

    @property
    def move_count(self) -> int:
        """Moves that have been played since game start minus undone moves"""
        return self.board.move_count

    def check_win(self) -> int:
        """Returns -1 for P1 win, 0 for no win, 1 for P2 win"""
        return self.board.check_win()

    # The remainder of the methods to interface with Board_
    def reset(self) -> None:
        """Resets to a new instance of `Board`"""
        self.board.reset()

    def search(self, team: int = None, iterations: int = 10000
            ) -> Tuple[int, int]:
        """
        An alias for search(Board, int, int). Please see Reach.search
        ```python
        >>> a = Board()
        >>> a.search()
        (9, 9)
        >>> b = Board()
        >>> search(b)
        (9, 9)
        ```
        """
        return search(self, team, iterations)

    def get(self, row: int, col: int) -> int:
        """
        Gets the piece (-1, 1 or 0) where -1 is a black stone (player 1)
            and 1 is a white stone, and 0 is empty of the position.
        ```python
        >>> a = Board()
        >>> a.play(9, 9)
        >>> a.get(9, 9)
        -1
        ```

        Args:  
        row: `int`
            The row of the piece starting from 0  

        col: `int`
            The column of the piece starting from 0  

        Returns:  
        piece: `int`
            The piece at the position (row, col) of the board.  

        Raises:  
        `IndexError`
            row or col are out of bounds.
        """
        if not 0 <= row < self.size or not 0 <= col < self.size:
            raise IndexError(f"Invalid coordinates (row, col): ({row}, {col}) "
                            f"exceeds dimentions of {self.size}x{self.size}.")
        return self.board.get(row, col)

    def play(self, row: int, col: int) -> None:
        """
        Places a piece at the location (row, col)  
        Args:  
        row `int`:
            The row of which to place the piece  
        col `int`:
            The column of which to place the piece  

        Raises:  
        `ValueError`
            row or col are out of bounds.
        """
        if not 0 <= row < self.size or not 0 <= col < self.size:
            raise ValueError(f"Invalid coordinates (row, col): ({row}, {col}) "
                            f"exceeds dimentions of {self.size}x{self.size}.")
        self.board.play(row, col)

    def undo(self) -> None:
        """Undoes the last move. May be called multiple times."""
        self.board.undo()


def search(ref_board: Board, team: int = None, iterations: int = 10000
        ) -> Tuple[int, int]:
    """
    Args:  
    ref_board: `Board`
        The board to be examined.  
    team: `int`
        The number of the piece that will be played this turn. First player is \
-1  
    iterations: `int`
        The amount of MCTS iterations to run.  

    Returns:  
    bestmove: `Tuple[int, int]`
        A 2-tuple of the position to place the next piece for best perceived \
outcome  

    Raises:
    `ValueError`
        when there is an object type mismatch

    ```python
    >>> a = Board()
    >>> a.search()
    (9, 9)
    >>> b = Board()
    >>> search(b)
    (9, 9)
    ```
    """
    if team is not None:
        print('You have chosen to manually overwrite the `team` parameter. '
            'It is recommended to allow this to handle this automatically.')
    else:
        team = (ref_board.move_count % 2) * 2 - 1

    if not isinstance(team, int):
        raise ValueError(f"team should be of {int} and not "
                        f"{type(team)}")
    if not isinstance(iterations, int):
        raise ValueError(f"iterations should be of {int} and not "
                        f"{type(iterations)}.")

    if isinstance(ref_board, Board):
        return search_(ref_board.board, team, iterations)
    elif isinstance(ref_board, Board_):
        return search_(ref_board, team, iterations)
    else:
        raise ValueError(f"ref_board should be of {Board} or {Board_} and not"
                        f" {type(ref_board)}.")

This is my first ever C++ work.
Not my first Python work, however, hence the overall higher quality. Now with...

✔ Python within 80 characters at all times
✔ Python functions well documented
✘ Lack of comments at some places
✘ This is your job to complain, not mine.

Give feedback on any of two languages.

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.