File size: 3,222 Bytes
afab5da | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | import math
import numpy as np
class Node:
def __init__(self, game, args, state, parent = None, action = None):
self.game = game
self.args = args
self.state = state
self.parent = parent
self.action = action
self.children = list()
self.expandable_moves = self.game.get_moves(self.state)
self.visits = 0
self.total_value = 0
def leaf_or_not(self):
return (len(self.children) > 0 and len(self.expandable_moves) == 0)
def search(self):
best_child = None
best_ucb = -np.inf
for child in self.children:
ucb = self.get_ucb(child)
if best_ucb < ucb:
best_ucb = ucb
best_child = child
return best_child
def get_ucb(self, child):
q_value = 1 - ((child.total_value / child.visits) + 1) / 2
return q_value + self.args["EXPLORATION_CONSTANT"] * math.sqrt(math.log(self.visits) / child.visits)
def expand(self):
rand_move = np.random.choice(self.expandable_moves)
self.expandable_moves.remove(rand_move)
child = self.game.make_move(self.state.copy(), rand_move, 1)
child = self.game.change_perspective(child)
child = Node(self.game, self.args, child, self, rand_move)
self.children.append(child)
return child
def simulate(self):
is_terminal, value = self.game.know_terminal_value(self.state, self.action)
value = self.game.get_opponent_value(value)
if is_terminal:
return value
state = self.state.copy()
player = 1
while True:
possible_moves = self.game.get_moves(state)
rand_move = np.random.choice(possible_moves)
state = self.game.make_move(state, rand_move, player)
is_terminal, value = self.game.know_terminal_value(state, rand_move)
if is_terminal:
if player == -1:
value = self.game.get_opponent_value(value)
return value
player = self.game.get_opponent(player)
def backpropagate(self,value):
self.total_value += value
self.visits += 1
value = self.game.get_opponent_value(value)
if self.parent is not None:
self.parent.backpropagate(value)
class MCTS:
def __init__(self, game, args):
self.game = game
self.args = args
def search(self, node):
root = Node(self.game, self.args, node)
for _ in range(self.args["NO_OF_SEARCHES"]):
node = root
while node.leaf_or_not():
node = node.search()
is_terminal, value = self.game.know_terminal_value(node.state, node.action)
value = self.game.get_opponent_value(value)
if not is_terminal:
node = node.expand()
value = node.simulate()
node.backpropagate(value)
move_probability = np.zeros(self.game.possible_state)
for children in root.children:
move_probability[children.action] = children.visits
move_probability /= np.sum(move_probability)
return move_probability
|