From 32118bd22ae3acf5aea9c473db405498831e13ad Mon Sep 17 00:00:00 2001 From: Matt Strapp Date: Mon, 26 Apr 2021 13:07:08 -0500 Subject: Test commit --- Algorithm.py | 128 ++++++++++++++++++++++++++++++++++++---------------------- DotsNBoxes.py | 20 +++++---- 2 files changed, 92 insertions(+), 56 deletions(-) diff --git a/Algorithm.py b/Algorithm.py index 5a2e4f8..99488a8 100644 --- a/Algorithm.py +++ b/Algorithm.py @@ -1,3 +1,11 @@ +# import MCTS +import math +from copy import deepcopy +from time import clock +from random import choice + +from GameState import GameState + class Algo: # A class for defining algorithms used (minimax and alpha-beta pruning) def miniMax(State, Ply_num): # Function for the minimax algorithm @@ -66,53 +74,75 @@ class Algo: # A class for defining algorithms used (minimax and alpha-beta pruni return Result return Minimum_Score -class MCTS: - # main function for the Monte Carlo Tree Search - - def monte_carlo_tree_search(root): - - while resources_left(time, computational power): - leaf = traverse(root) - simulation_result = rollout(leaf) - backpropagate(leaf, simulation_result) - - return best_child(root) - -# function for node traversal - - - def traverse(node): - while fully_expanded(node): - node = best_uct(node) - - # in case no children are present / node is terminal - return pick_univisted(node.children) or node - -# function for the result of the simulation - - - def rollout(node): - while non_terminal(node): - node = rollout_policy(node) - return result(node) - -# function for randomly selecting a child node - - - def rollout_policy(node): - return pick_random(node.children) - -# function for backpropagation - - - def backpropagate(node, result): - if is_root(node) return - node.stats = update_stats(node, result) - backpropagate(node.parent) - -# function for selecting the best child -# node with highest number of visits - - def best_child(node): - #pick child with highest number of visits +# class MCTSNode(object): +# """Monte Carlo Tree Node. +# Each node encapsulates a particular game state, the moves that +# are possible from that state and the strategic information accumulated +# by the tree search as it progressively samples the game space. +# """ + +# def __init__(self, state, parent=None, move=None): +# self.parent = parent +# self.move = move +# self.state = state + +# self.plays = 0 +# self.score = 0 + +# self.pending_moves = state.get_moves() +# self.children = [] + +# def select_child_ucb(self): +# # Note that each node's plays count is equal +# # to the sum of its children's plays +# def ucb(child): +# win_ratio = child.score / child.plays \ +# + math.sqrt(2 * math.log(self.plays) / child.plays) +# return win_ratio + +# return max(self.children, key=ucb) + +# def expand_move(self, move): +# self.pending_moves.remove(move) # raises KeyError + +# child_state = deepcopy(self.state) +# child_state.play_move(move) + +# child = MCTSNode(state=child_state, parent=self, move=move) +# self.children.append(child) +# return child + +# def get_score(self, result): +# # return result +# if result == 0.5: +# return result + +# if self.state.player == 2: +# if self.state.next_turn_player == result: +# return 0.0 +# else: +# return 1.0 +# else: +# if self.state.next_turn_player == result: +# return 1.0 +# else: +# return 0.0 + +# if self.state.next_turn_player == result: +# return 0.0 +# else: +# return 1.0 + +# def __repr__(self): +# s = 'ROOT\n' if self.parent is None else '' + +# children_moves = [c.move for c in self.children] + +# s += """Score ratio: {score} / {plays} +# Pending moves: {pending_moves} +# Children's moves: {children_moves} +# State: +# {state}\n""".format(children_moves=children_moves, **self.__dict__) + +# return s \ No newline at end of file diff --git a/DotsNBoxes.py b/DotsNBoxes.py index ebafcc2..14cdd2a 100644 --- a/DotsNBoxes.py +++ b/DotsNBoxes.py @@ -3,6 +3,7 @@ import collections from Algorithm import * from Board import * from Nodes import * +import MCTS class DotsNBoxes: # A class for managing the moves made by the human and the computer @@ -15,19 +16,21 @@ class DotsNBoxes: # A class for managing the moves made by the human and the com def Human(self): # Defining the Human player and his actions/Choices self.State.Draw() - - # HumanX = int(input("Please enter the 'X' coordinate of your choice (an integer such as 4): ")) + + # HumanX = int(input("Please enter the 'X' coordinate of your choice (an integer such as 4): ")) # HumanY = int(input("Please enter the 'Y' coordinate of your choice (an integer such as 4): ")) - # if (HumanX, HumanY) not in self.State.children: + # if (HumanX, HumanY) not in self.State.children: # self.State.Make(HumanX, HumanY, False) - # self.State = self.State.children[(HumanX, HumanY)] - # else: # self.State = self.State.children[(HumanX, HumanY)] + + # else: + # self.State = self.State.children[(HumanX, HumanY)] + move = Algo.miniMax(self.State, 2) self.State = self.State.children[(move[0], move[1])] - print("AI selected the following coordinates to play:\n" + "(" ,str(move[0]), ", " + str(move[1]), ")", end = "\n\n") + print("AI1 selected the following coordinates to play:\n" + "(" ,str(move[0]), ", " + str(move[1]), ")", end = "\n\n") print("Current Score =====>> Your Score - AI Score = " + str(self.State.CurrentScore), end = "\n\n\n") @@ -42,10 +45,13 @@ class DotsNBoxes: # A class for managing the moves made by the human and the com def Computer(self): # Defining the Computer player and its actions/Choices self.State.Draw() + # Temporarily commented out. TODO hardcore MCTS into working then alternate comments lol move = Algo.miniMax(self.State, 3) - self.State = self.State.children[(move[0], move[1])] + # move = MCTS.MCTSGameController() # check what MCTSGameController returns? + + print("AI2 selected the following coordinates to play:\n" + "(" ,str(move[0]), ", " + str(move[1]), ")", end = "\n\n") print("Current Score =====>> Your Score - AI Score = " + str(self.State.CurrentScore), end = "\n\n\n") -- cgit v1.2.3