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 
 

 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)
 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.sizexself.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.sizexself.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.