How to implement tree made from possible moves in game Othello (Reversi)

Question

I need help with making tree from possible moves in game Othello, on which I will later use MiniMax algorithm. Game is played in Player vs AI mode and I am always "1" on board and AI is always "2" on board. This is how my current function for getting best move for AI looks like:

def findMoveForAI(board, player, depth, start):
    best_score_for_move = -float('inf')
    play_x = play_y = -1
    moves = validMoves(board, player)
    if not moves:
        return (play_x , play_y)
    for x, y in moves:
        # this is where I would like to make tree
        (temp, total_fillped) = PlayMove(copy.deepcopy(board), x, y, player)
        move_eval = AlphaBeta(temp, player, depth, -999999999999, 999999999999, True, start)
        if move_eval > best_score_for_move  :
            best_score_for_move = move_eval 
            play_x = x; play_y= y
    return (play_x , play_y)

So, my idea is that on marked place, I make tree for every possible move for AI in that moment and then do MiniMax on it and get the best possible move. Problem is, that I don't know how to make tree. I have class TreeNode and class Tree but apparently, I don't know how to use them. This is how those 2 classes look like.

class TreeNode(object):

    def __init__(self, data):
        self.parent = None
        self.children = []
        self.data = data

    def is_root(self):
        return self.parent is None

    def is_leaf(self):
        return len(self.children) == 0

    def add_child(self, x):
        x.parent = self
        self.children.append(x)

class Tree(object):
    def __init__(self):
        self.root = None

Also, this is how I initialize board if that's needed.

board = [['.' for x in range(8)] for y in range(8)]

I would really appreciate any kind of help because I feel like it should be done with recursion but it's really not my strongest side.

This is what I tried:

def makeTree(tree, board, player, depth):
    if depth > 0:
        new_player = change_player(player)
        possible_moves = validMoves(board, new_player)
        for x, y in possible_moves:
            new_board = PlayMove(copy.deepcopy(board), x, y, new_player)[0]
            child_tree = makeTree(tree, new_board, new_player, depth - 1)
            tree.add_child(child_tree)
    return tree

Thanks in advance.

Answer 1

You would need your recursive function to return a TreeNode instance, not a Tree instance. The top level call will then return the root node, which should then be assigned to the root attribute of a single Tree instance.

I would also suggest creating an Edge class, so you can store the information about the move that was played in the parent board in order to get to the child board.

If I understand correctly you want to separate the minimax/alphabeta algorithm from the actual game rules, and first create the tree of states (specific to the game), and then feed that to a generic minimax/alphabeta algorithm which can then be ignorant about the game rules, and just focus on the information in the tree.

Here is an idea for an implementation:

class Tree:
    def __init__(self):
        self.root = None

class TreeNode:

    def __init__(self, board, player, value=None):
        self.parent = None
        self.children = []
        self.board = board
        self.player = player
        self.value = value  # Initially only provided for leaf nodes

    def is_root(self):
        return self.parent is None

    def is_leaf(self):
        return len(self.children) == 0

    def add_edge(self, edge):
        edge.child.parent = self
        self.children.append(edge)

    def to_list(self):  # to ease debugging...
        return [self.board, [edge.child.to_list() for edge in self.children]]

class Edge:
    def __init__(self, x, y, child):
        self.x = x
        self.y = y
        self.child = child

    
def makeTree(board, player, depth):

    def makeNode(board, player, depth):
        if depth == 0:  # Create a leaf with a heuristic value
            return TreeNode(board, player, heuristic(board, player))
        
        node = TreeNode(board, player)
        new_player = change_player(player)
        possible_moves = validMoves(board, new_player)
        for x, y in possible_moves:
            new_board = PlayMove(copy.deepcopy(board), x, y, new_player)[0]
            node.add_edge(Edge(x, y, makeNode(new_board, new_player, depth - 1)))
        return node

    tree = Tree()
    tree.root = makeNode(board, player, depth)
    return tree

Your findMoveForAI and AlphaBeta functions would no longer get a board and player as argument, nor would they call PlayMove. Instead they would just traverse the tree. findMoveForAI would get the tree instance as argument, and AlphaBeta would get a node as argument. The values would bubble up the tree as this executes, based on the values that are stored in the leaves of the tree.

So findMoveForAI could look like this:

def findMoveForAI(tree):
    best_score_for_move = -float('inf')
    play_x = play_y = -1
    for x, y, child in tree.root.children:
        move_eval = AlphaBeta(child, depth, -999999999999, 999999999999)
        if move_eval > best_score_for_move:
            best_score_for_move = move_eval 
            play_x = x
            play_y = y
    return (play_x , play_y)

And the driver code would have these two steps:

DEPTH = 3
# ...
tree = makeTree(board, player, DEPTH) 
best_move = findMoveForAI(tree)
# ...