9
\$\begingroup\$

Requires Python version: 3.6+

fstrings included!

External link: https://github.com/thejhonnyguy/Python-Stock-MCTS

(Questions below)

Main program: mcts.py

"stock mcts implementation"
import sys
import copy
import random
from board import Board
from node import Node

MCTS_ITERATIONS = 1000

if len(sys.argv) == 2:
    try:
        MCTS_ITERATIONS = int(sys.argv[1])
    except ValueError:
        print(f'Invalid parameter for mcts iterations, defaulting to {MCTS_ITERATIONS}')

def start_game():
    "Start a game"
    game = Board(15) #15 as a placeholder
    while True:
        print(game)
        entry = tuple(map(int, input('Move: ').replace(' ', '').split(',')))
        game.move(entry[0], entry[1])
        if game.check_win():
            print("I lost :(")
            break
        move = mcts_go(copy.deepcopy(game), 1, stats=True)
        game.move(move[0], move[1])
        if game.check_win():
            print("I won :D")
            break

def mcts_go(current_game, team, iterations=MCTS_ITERATIONS, stats=False):
    "MCTS"
    #Initialize the tree with possible moves and current position
    tree = [Node()] #for general tracking and debugging
    for move in current_game.get_obvious_moves():
        new_node = Node(parent=tree[0], move_to=move)
        tree[0].children.append(new_node)
        tree.append(new_node)

    for _ in range(iterations):
        #iterations
        current_node = tree[0] #origin node, current board.
        while not current_node.is_leaf():
            children_scores = tuple(map(lambda x: x.ucb1(), current_node.children))
            current_node = current_node.children[children_scores.index(max(children_scores))]

        board_updates = 0
        for move in current_node.moves_to:
            current_game.move(move[0], move[1])
            board_updates += 1

        #quickly check if the game if is in a terminal state
        do_rollout = True
        rollout_res = current_game.check_win()
        if rollout_res:
            do_rollout = False #the game is already terminal, look no further.

        if not current_node.visits and do_rollout: #==0
            #rollout
            rollout_res = rollout(copy.deepcopy(current_game), team)
        elif current_node.visits and do_rollout:
            #let's go deeper!!!!!!111!!!
            for move in current_game.get_obvious_moves():
                new_node = Node(parent=current_node, move_to=list(move))
                current_node.children.append(new_node)
                tree.append(new_node)
            if not current_node.children:
                rollout_res = 0
            else:
                current_node = current_node.children[0]
                #update board again
                board_updates += 1
                current_game.move(current_node.moves_to[-1][0], current_node.moves_to[-1][1])
                #rollout
                rollout_res = rollout(copy.deepcopy(current_game), team)

        #revert board
        for _ in range(board_updates):
            current_game.undo()

        #backpropogate the rollout
        while current_node.parent: #not None. only the top node has None as a parent
            current_node.visits += 1
            current_node.score += rollout_res
            current_node = current_node.parent
        current_node.visits += 1 #for the mother node

    #pick the move with the most visits
    if stats:
        print('Stats for nerds\n' f'Search tree size: {len(tree)}')
    current_node = tree[0]
    visit_map = tuple(map(lambda x: x.visits, current_node.children))
    best_move = visit_map.index(max(visit_map))
    return current_game.get_obvious_moves()[best_move]

def rollout(game, team):
    "Rollout a game"
    max_moves = game.size ** 2
    while game.moves < max_moves:
        check_win = game.check_win()
        if check_win:
            return (check_win * team + 1) // 2
        #make a random move
        while True:
            row = random.randint(0, game.size - 1)
            col = random.randint(0, game.size - 1)
            if (row, col) not in game.move_history:
                game.move(row, col)
                break
    return 0.5 #draw

if __name__ == '__main__':
    start_game()

board.py, containing the Board class, imported by mcts.py

"Board file"

class Board:
    "Board"
    def __init__(self, size):
        self.size = size
        self.move_history = []
        self.moves = 0
        self.__board = [[0 for _ in range(size)] for _ in range(size)]

    def move(self, row, col, piece=None):
        "Place a piece (-1) piece should take the first turn"
        if not piece:
            piece = (self.moves % 2) * 2 - 1
        if self.__board[row][col] == 0 and (piece == 1 or piece == -1):
            self.move_history.append((row, col))
            self.__board[row][col] = piece
            self.moves += 1
        elif piece != 1 and piece != -1:
            raise TypeError("The piece should be an integer of 0 or 1.")
        else:
            raise LookupError("The coordinates on the board are already taken.")

    def undo(self):
        "remove the last placed piece"
        if self.move_history: #is not empty
            self.__board[self.move_history[-1][0]][self.move_history[-1][1]] = 0
            self.move_history.pop()
            self.moves -= 1
        else:
            raise IndexError("No moves have been played.")

    def get(self, row, col):
        "Get a piece at row, col"
        return self.__board[row][col]

    def check_win(self): #cross my fingers and hope everything bloody works
        "check if the game has reached a terminal state"
        if not self.move_history:
            return 0
        latest_move = self.move_history[-1]
        #check horizontal area of last placed piece
        start = latest_move[1] - 4
        if start < 0:
            start = 0
        diag_start_col = start #because we can
        end = latest_move[1] + 5
        if end > self.size:
            end = self.size
        diag_end_col = end #because we can
        for start_ in range(0, end - 4):
            result = sum(self.__board[latest_move[0]][start + start_:start + start_ + 5])
            if result == 5:
                return 1
            if result == -5:
                return -1

        #check the vertical area of the last placed piece
        start = latest_move[0] - 4
        if start < 0:
            start = 0
        diag_start_row = start #because we can
        end = latest_move[0] + 5
        if end > self.size:
            end = self.size
        diag_end_row = end #because we can
        vertical = [self.__board[x][latest_move[1]] for x in range(start, end)]
        for start_ in range(0, end - start - 4):
            result = sum(vertical[start_:start_ + 5])
            if result == 5:
                return 1
            if result == -5:
                return -1

        #check the top left - bottom right diagonal
        start = - min((latest_move[0] - diag_start_row, latest_move[1] - diag_start_col))
        end = min((diag_end_row - latest_move[0], diag_end_col - latest_move[1]))
        diagonal = [self.__board[latest_move[0] + x][latest_move[1] + x]
                    for x in range(start, end)] #tuples perform better than lists
        for start_ in range(0, end - start - 4):
            result = sum(diagonal[start_:start_ + 5])
            if result == 5:
                return 1
            if result == -5:
                return -1

        #check bottom left - top right diagonal
        start = - min((latest_move[1] - diag_start_col, diag_end_row - latest_move[0] - 1))
        end = min((diag_end_col - latest_move[1], latest_move[0] - diag_start_row + 1))
        diagonal = [self.__board[latest_move[0] - x][latest_move[1] + x]
                    for x in range(start, end)]
        for start_ in range(0, end - start - 4):
            result = sum(diagonal[start_:start_ + 5])
            if result == 5:
                return 1
            if result == -5:
                return -1

        return 0

    def get_obvious_moves(self):
        """
        Returns a list of obvious moves
        Obvious spots are empty squares adjacent to an existent piece
        """
        moves = []
        for piece in self.move_history:
            directions = [(-1, 0), (-1, 1), (0, 1), (1, 1),
                          (1, 0), (1, -1), (0, -1), (-1, -1)]
            for direction in directions:
                if (0 <= (piece[0] + direction[0]) < self.size
                        and 0 <= (piece[1] + direction[1]) < self.size):
                    if not self.__board[piece[0] + direction[0]][piece[1] + direction[1]]:
                        #== 0
                        moves.append((piece[0] + direction[0], piece[1] + direction[1]))
        return list(set(moves))

    def __str__(self):
        return ('\n'.join(' '.join(map(str, x)) for x in self.__board).replace('-1', 'X')
               ).replace('1', 'O').replace('0', ' ')

node.py, containing the Node class, imported by mcts.py

"Containing the node class"
import math
import copy

class Node:
    "Node"
    def __init__(self, parent=None, move_to=None):
        self.parent = parent #the object
        if parent and not move_to:
            raise TypeError("A parent is provided with no move_to paramenter.")
        elif parent:
            self.moves_to = copy.deepcopy(self.parent.moves_to)
            self.moves_to.append(move_to)
        else:
            self.moves_to = []
        self.score = 0
        self.visits = 0
        self.children = []

    def is_leaf(self):
        "Returns a boolean variable on whether the node is a leaf node"
        return not bool(self.children)

    def ucb1(self):
        "Returns UCB1 score"
        try:
            return self.score / self.visits + 2 * math.sqrt(math.log(self.parent.visits)
                                                            / self.visits)
        except ZeroDivisionError:
            #equivalent to infinity
            #assuming log(parent visits) / visits will not exceed 100
            return 10000

More details

✔ Default PYLINT limit of 100 characters.

✘ The usual limit of 79 characters. (Do I really have to?)

✔ PYLINT shows no warnings

✘ PYLINT reports notices, saying too many return statements and branches(???)

✔ Module, class, function docstrings included.

✘ They're awful. (Recently saw Google's recommendation for python docstrings)

✔ Code is commented, outlining much of the code.

✘ Sometimes comments are sparse, or hard to understand. (I'm unsure whether my comments are acceptable, as sometimes I see very well commented code.)

(Make recommendations on what you feel is necessary, and preferably also on the above points.)

Other notes.

I made this program to try to make a Monte Carlo Tree Search implementation for Python, and the game is just there for you to have a bit of fun with, hence why it's not really that great.

\$\endgroup\$
  • 1
    \$\begingroup\$ "The usual limit of 79 characters. (Do I really have to?)" It's there to encourage easy to read code, something the 100 char limit isn't doing for you. \$\endgroup\$ – Peilonrayz Dec 12 '17 at 10:54
  • \$\begingroup\$ Understandable, but VSCode defaults Pylint's settings to 100 characters, is there a reason for that? \$\endgroup\$ – Luke Dec 12 '17 at 11:02
  • \$\begingroup\$ @Peilonrayz Meh, if his screen is large enough, it doesn't matter for the writer. My screen can handle way more before it becomes a problem. Part of that rule is legacy, part of that rule is compatibility with other developer's computers. It's one of those rules where it doesn't hurt to comply and you should really aim for it, but nothing is lost if you go a couple of characters beyond it. The compatibility problem is nicely illustrated in this question though, since the code now is too large to be shown without side-scrolling. Side-scrolling is always a pain in the behind when reading code. \$\endgroup\$ – Mast Dec 12 '17 at 11:03
  • \$\begingroup\$ Luke, I suspect there's a module available to check against PEP8 instead of arbitrary rules, but I have limited experience with VSCode so wouldn't know for sure. \$\endgroup\$ – Mast Dec 12 '17 at 11:04
  • 4
    \$\begingroup\$ "The usual limit of 79 characters. (Do I really have to?)" If you did, we wouldn't have to scroll sideways here on this page to read it. \$\endgroup\$ – mkrieger1 Dec 12 '17 at 13:00
8
\$\begingroup\$

There's a bunch of stuff to dislike about your code:

  1. The superficial docblocks are annoying. Please delete them. I really don't care if some automated checker passes with no errors or not - because the people who write automated checkers have gone way past the point of helpfulness into puerile prescriptivism: "Your variables must be at least 3 letters. Your sentences cannot contain more than two pronouns. Your participles are dangling." If the tool isn't helping you, don't use it! Or spend the time to gen up a config file that turns off all the stupid.

  2. Your organization is confused. You have a class Node, which appears to be used by mcts_go and no other. So why isn't there an mcts.py file, with mcts_go and a private class Node? This reads like Java code. Get used to the idea that modules can contain more than just a class.

    Also, you spend a lot of time doing little special-purpose "play the game" logic. Why not write a Player class and simplify all the code?

    from abc import ABC, abstractmethod
    
    class Player(ABC):
        @abstractmethod
        def make_move(board):
            """Make a move on the game board"""
            pass
    

    You can provide a KeyboardPlayer class that moves by inputting numbers, and a MctsPlayer class that moves by calling mcts_go (or whatever).

  3. Node is a terrible name. Nobody expects the Spanish Inquisition. Also, nobody expects a Node to take a move_to parameter. Make that a HistoryNode or TurnHistory or something.

  4. Every move is followed by a check to see if the board is in a terminal state. You might want to make your move function a boolean, or define an exception, so that you can merge those two operations together.

  5. Your mcts_go function spends time calling undo. If you change your implementation, you can probably let the garbage collector handle that for you.

  6. I don't think copy.deepcopy does what you think it does. If I understand your Node class, you can get what you want just by shallow copying the list.

  7. You set parent in Node.__init__ but you don't append to parent.children?

\$\endgroup\$
6
\$\begingroup\$

There's something off about the following function:

def ucb1(self):
    "Returns UCB1 score"
    try:
        return self.score / self.visits + 2 * math.sqrt(math.log(self.parent.visits)
                                                        / self.visits)
    except ZeroDivisionError:
        #equivalent to infinity
        #assuming log(parent visits) / visits will not exceed 100
        return 10000

First, the return of the try is too complex. You're doing something simple here, but it doesn't look simple. Make it look simple. If that means splitting it up, go for it.

You're checking for a ZeroDivisionError. Very good, but what can cause this error? Consider what the function will look like when you simply check whether self.visits == 0 before dividing.

If you want to go the try/except route anyway, consider what happens when taking the square root of a negative number, or the logarithm of zero:

ValueError: math domain error

Shouldn't you be catching those as well?

#equivalent to infinity
#assuming log(parent visits) / visits will not exceed 100

I'm not sure what you're trying to convey here. I am sure there should be a space between the hash and the rest of the comment for improved readability.

return 10000

Yea, and that's where my "magic number" alarm goes off. Why is it 1000? Why not one more or one less? If you intend to convey the function failed (the try did not hold), use a negative return value instead and make sure the function calling it understands what that means.

Now you're simply suppressing the error and using the try/catch as part of your calculator. Your except is doing things it shouldn't be doing, even if it looks like it's doing next to nothing. True, but it's doing the wrong things.

\$\endgroup\$
  • 5
    \$\begingroup\$ Why is it 1000? and that's where magic numbers bite you in the rear. Well, one of the ways. In this case, you've exhibited one of the main problems, that of reuse. It's very easy to type a magic number incorrectly and not notice. In fact here, it's been 6hrs and 6 upvotes (doubtless many more readers) and no-one has twigged until now. \$\endgroup\$ – Baldrickk Dec 12 '17 at 18:07
  • 2
    \$\begingroup\$ @Baldrickk I secretly hoped it was on purpose :) \$\endgroup\$ – Brian J Dec 12 '17 at 19:20
3
\$\begingroup\$

Great answers so far. But I'd like to say few words about some stuff that was not yet covered.

  1. PEP 8: Top-level functions should be surrounded by two blank lines. Docstrings should be surrounded by triple quotes. "Inline comments should be separated by at least two spaces from the statement. They should start with a # and a single space." Block comments should start with # and a single space. Use more blank lines. Your code is pretty dense.
  2. You have inconsistent docstrings. Some start with words like "Returns" and some with "Start". Use one grammatical form. Personally, I prefer the 1st option. Once, I had a docstring saying something like "Make sure that..." And it was not clear for other people if it was up to a function to "make sure" to do something or I was asking users to do that.
  3. You write game = Board(15). Why not board = Board(15)? Also, this 15 is a magic number.
  4. Use type hints. It will help you and other people to understand what your functions should get as input and what type of output you expect to get from it. For example, the signature of your mcts_go would look like this:

    def mcts_go(current_game: Board,
                *,
                team: int,
                iterations: int = MCTS_ITERATIONS,
                stats: bool = False) -> Tuple[int, int]:
    

    Note the asterisk. All the arguments that go after it will become keyword-only. So, to call the function in your case you have to write:

    move = mcts_go(copy.deepcopy(game), 
                   team=1, 
                   stats=True)
    

    Btw, what is 1?

  5. Use line breaks in list comprehensions. Instead of writing:

    vertical = [self.__board[x][latest_move[1]] for x in range(start, end)]
    

    write

    vertical = [self.__board[x][latest_move[1]] 
                for x in range(start, end)]
    

    Much clearer like this I think.

  6. Your calculating of Board.__str__ looks not cool. How about making a board like:

    rows_generator = (' '.join(map(str, row))
                      for row in __board)
    board = '\n'.join(rows_generator)
    

    And then replacing digits with other symbols like this:

    replacements = {'-1': 'X',
                    '0': ' ',
                    '1': '0'}
    for key, value in replacements.items():
        board = board.replace(key, value)
    

    Probably you would want to take this dict somewhere to some function's signature as a default parameter as well.

  7. In the beginning your board is empty. So, I suppose, it will print just blank lines. Maybe, it is worth to add borders at least?

  8. entry = tuple(map(int, input('Move: ').replace(' ', '').split(',')))
    I think it's better to make a function for this. For starters, something like:

    def ask_moves(moves_count: int = 2) -> Tuple[int, ...]:
        moves = input('Move: ')
        moves = moves.replace(' ', '').split(',')
    
        if len(moves) != moves_count:
            raise ValueError(f'Bad input. Expected {moves_count} moves')
    
        return tuple(map(int, moves))
    
  9. Instead of writing if piece == 1 or piece == -1 why not write if abs(piece) == 1?

  10. Are you sure you want to write if not piece and not if piece is not None? Because not 0 == True. Also in if parent and not move_to: can't we have move_to == 0?

  11. piece = (self.moves % 2) * 2 - 1
    I think, some explanation would be good. Or better a separate function for this.

  12. You write:

    elif piece != 1 and piece != -1:
        raise TypeError("The piece should be an integer of 0 or 1.")
    

    Where is the logic?

  13. The places where you have multiple conditions (like in move function) are very hard to read. Try to separate the logic.

  14. # Cross my fingers and hope everything bloody works
    Well... Learn how to write tests.

  15. Choose one way to refer to row and column indexes of your "moves". In some places you write move[0] and I see one place where you write just row and col for them. Wouldn't it be better to use named tuples?

    import collections
    
    Move = collections.namedtuple('Move', ['row', 'column'])
    human_move = Move(row=3,
                      column=5)
    
  16. In your check_win what are 4 and 5? Again some magic numbers. Also, I think it's not a really good name for a function that doesn't return bool.

  17. Instead of writing things like:

    start = latest_move[1] - 4
    if start < 0:
        start = 0
    

    You can write:

    start = max(0, latest_move[1] - 4)
    
  18. You can omit start index in range(0, N) and write just range(N)

  19. It looks like the logic for all 4 big blocks in check_win is the same. You could use a function like this (check it carefully, use better names and do something about magic numbers):

    def check_area(*,
                   start_index: int,
                   end_index: int,
                   line: List[int]) -> int:
        for index in range(end_index - 4):
            first_index = start_index + index
            last_index = first_index + 5
    
            return sum(line[first_index:last_index])
    

    Then, for all 4 blocks create lists of start/end indexes and lines. Iterate over them with zip. In the end you will have something like:

    for start_index, end_index, line in zip(start_indexes,
                                            end_indexes,
                                            lines):
        result = check_area(start_index=start_index,
                            end_index=end_index,
                            line=line)
        if result == 5:
            return 1
        if result == -5:
            return -1
    else:
        return 0
    
  20. top left - bottom right diagonal - this is called major diagonal. And the other one is minor diagonal.

  21. This:

    directions = [(-1, 0), (-1, 1), (0, 1), (1, 1),
                  (1, 0), (1, -1), (0, -1), (-1, -1)]
    

    can be taken out of for-loop. Also, it can be rewritten as:

    directions = list(itertools.product([-1, 0, 1],
                                        repeat=2))
    directions.remove((0, 0))
    
  22. In is_leaf why not write just:

    if self.children:
        return False
    return True
    
  23. You have a counter variable board_updates. You should use enumerate:

    for board_updates, move in enumerate(current_node.moves_to, start=1):
        current_game.move(move[0], move[1])
    
  24. You write:

    tuple(map(lambda x: x.visits, current_node.children))
    

    But why not write:

    [child.visits 
     for child in current_node.children]
    
  25. And finally, why do you keep both move_history and moves? Looks like you can get moves from the 1st one.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.