I am trying to make a tree of possible moves for the game Othello, on which I will later use a minimax algorithm. The game is played in Player vs AI mode where the player has "1" on the board and the AI "2". This is my current function for getting the best move for the AI:
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 am trying to make a 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)
Also, this is how I initialize board:
board = [['.' for x in range(8)] for y in range(8)]
At the place I marked in the code, I am trying to make a tree for every possible move for the AI in that moment, and then do minimax on it and get the best possible move.
I have class TreeNode and class Tree for building the tree:
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
This is what I tried for making the tree:
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
But now this creates many Tree instances, while I would need one tree and many nodes. How I can resolve this with this recursive approach?
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)
# ...