diff options
| -rw-r--r-- | Algorithm.py | 128 | ||||
| -rw-r--r-- | 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")
|