From 1c7a9d1e88e44362b2303a2a591e4993e4dc458f Mon Sep 17 00:00:00 2001 From: vehme003 Date: Sun, 25 Apr 2021 14:54:01 -0500 Subject: Add files via upload --- Algorithm.py | 68 ++++++++++++++ Board.py | 78 ++++++++++++++++ DotsNBoxes.py | 73 +++++++++++++++ Nodes.py | 18 ++++ game.py | 282 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 519 insertions(+) create mode 100644 Algorithm.py create mode 100644 Board.py create mode 100644 DotsNBoxes.py create mode 100644 Nodes.py create mode 100644 game.py diff --git a/Algorithm.py b/Algorithm.py new file mode 100644 index 0000000..85a9f15 --- /dev/null +++ b/Algorithm.py @@ -0,0 +1,68 @@ +class Algo: # A class for defining algorithms used (minimax and alpha-beta pruning) + + def miniMax(State, Ply_num): # Function for the minimax algorithm + + for i in range(State.Current.dimY): + for j in range(State.Current.dimX): + if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children: + State.Make(j, i, True) + if Ply_num < 2: + return (i, j) + + Minimum_Score = 1000 + i = 0 + + + j = 0 + for k, z in State.children.items(): + Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score) + if Minimum_Score > Result: + Minimum_Score = Result + i = k[0] + j = k[1] + + return (i, j) + + + def Maximum(State, Ply_num, Alpha): # Alpha-beta pruning function for taking care of Alpha values + if Ply_num == 0: + return State.CurrentScore + + for i in range(State.Current.dimY): + for j in range(State.Current.dimX): + if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children: + State.Make(j, i, False) + + Maximum_Score = -1000 + i = 0 + j = 0 + for k, z in State.children.items(): + Result = Algo.Minimum(z, Ply_num - 1, Maximum_Score) + if Maximum_Score < Result: + Maximum_Score = Result + if Result > Alpha: + return Result + + return Maximum_Score + + + def Minimum(State, Ply_num, Beta): # Alpha-beta pruning function for taking care of Beta values + if Ply_num == 0: + return State.CurrentScore + + for i in range(State.Current.dimY): + for j in range(State.Current.dimX): + if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children: + State.Make(j, i, True) + + Minimum_Score = 1000 + i = 0 + j = 0 + for k, z in State.children.items(): + Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score) + if Minimum_Score > Result: + Minimum_Score = Result + if Result < Beta: + return Result + + return Minimum_Score \ No newline at end of file diff --git a/Board.py b/Board.py new file mode 100644 index 0000000..405ec23 --- /dev/null +++ b/Board.py @@ -0,0 +1,78 @@ +from random import * + + +class Game: #A class for managing different situations and states happening in the game and on the board + def __init__(self, Mat, dimX, dimY): + self.Mat = Mat + self.dimX = dimX + self.dimY = dimY + + def Initiate(self): #initiating the game board with X and Y dimensions + for i in range(0, self.dimY): + R = [] + for j in range (0, self.dimX): + if i % 2 == 1 and j % 2 == 1: + R.append(1) # Assigning a random number from 1 to 9 to the spots in the board as the points + elif i % 2 == 0 and j % 2 == 0: + R.append('*') # printing asterisks as the dots in the board + else: + R.append(' ') # adding extra space for actions in the game + self.Mat.append(R) + + def Get_matrix(self): # Board matrix + ans = [] + for i in range(0, self.dimY): + R = [] + for j in range(0, self.dimX): + R.append(self.Mat[i][j]) + ans.append(R) + return ans + + def Draw_mat(self): # Drawing the board marix as dots and lines + + if self.dimX > 9: + print(" ", end='') + print(" ", end='') + for i in range(0, self.dimX): + print(str(i), end=' ') + print() + + if self.dimX > 9: + print(" ", end='') + print(" ", end='') + for i in range(0, self.dimX + 1): + print("___", end='') + print() + for j in range(self.dimY): + if self.dimX > 9 and j < 10: + print(" ", end='') + print(str(j) + "| ", end='') + for z in range(self.dimX): + print(str(self.Mat[j][z]), end=' ') + print() + print(" _________________________\n") + + def Get_currentState(self): + return Game(self.Get_matrix(), self.dimX, self.dimY) + + def action(self, i, j): # Applying the actions made by the human or the computer + Sum = 0 + + if j % 2 == 0 and i % 2 == 1: + self.Mat[j][i] = '-' + if j < self.dimY - 1: + if self.Mat[j+2][i] == '-' and self.Mat[j+1][i+1] == '|' and self.Mat[j+1][i-1] == '|': + Sum += self.Mat[j+1][i] + if j > 0: + if self.Mat[j-2][i] == '-' and self.Mat[j-1][i+1] == '|' and self.Mat[j-1][i-1] == '|': + Sum += self.Mat[j-1][i] + + else: + self.Mat[j][i] = '|' + if i < self.dimX - 1: + if self.Mat[j][i+2] == '|' and self.Mat[j+1][i+1] == '-' and self.Mat[j-1][i+1] == '-': + Sum += self.Mat[j][i+1] + if i > 0: + if self.Mat[j][i-2] == '|' and self.Mat[j+1][i-1] == '-' and self.Mat[j-1][i-1] == '-': + Sum += self.Mat[j][i-1] + return Sum \ No newline at end of file diff --git a/DotsNBoxes.py b/DotsNBoxes.py new file mode 100644 index 0000000..ebafcc2 --- /dev/null +++ b/DotsNBoxes.py @@ -0,0 +1,73 @@ +from random import * +import collections +from Algorithm import * +from Board import * +from Nodes import * + + +class DotsNBoxes: # A class for managing the moves made by the human and the computer + def __init__(self, Board_Xdim, Board_Ydim, Ply_num): + currentState = Game([], Board_Xdim, Board_Ydim) + currentState.Initiate() + self.State = Thing(currentState) + self.Ply_num = Ply_num + self.Score = 0 + + 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): ")) + # HumanY = int(input("Please enter the 'Y' coordinate of your choice (an integer such as 4): ")) + # 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)] + 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("Current Score =====>> Your Score - AI Score = " + str(self.State.CurrentScore), end = "\n\n\n") + + if len(self.State.children) == 0: + self.State.Draw() + self.Evaluation() + return + + self.Computer() + + + def Computer(self): # Defining the Computer player and its actions/Choices + self.State.Draw() + + move = Algo.miniMax(self.State, 3) + + self.State = self.State.children[(move[0], move[1])] + + 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") + + if len(self.State.children) == 0: + self.State.Draw() + self.Evaluation() + return + + self.Human() + + def Evaluation(self): # Evaluation function for taking care of the final scores + print("Stop this Madness!!!\n") + if self.State.CurrentScore > 0: + print("You won you crazy little unicorn!! You are the new hope for the mankind!" + str(self.State.CurrentScore)) + exit() + elif self.State.CurrentScore < 0: + print("!!! Inevitable Doom!!! You were crushed by the AI!! "+ str(self.State.CurrentScore)) + exit() + else: + print("Draw! Well Congratulations! you are as smart as the AI!") + exit() + + def start(self): + self.Human() \ No newline at end of file diff --git a/Nodes.py b/Nodes.py new file mode 100644 index 0000000..51a256b --- /dev/null +++ b/Nodes.py @@ -0,0 +1,18 @@ +class Thing: # A class for Node related operations + def __init__(self, currentState): + self.Current = currentState + self.CurrentScore = 0 + self.children = {} + + def Make(self, i, j, player): # Function for generating a child node + self.children[(i, j)] = Thing(self.Current.Get_currentState()) + mul = 1 + if player: + mul *= -1 + self.children[(i, j)].CurrentScore = (self.children[(i, j)].Current.action(i, j) * mul) + self.CurrentScore + + def Populate(self, i, j, Child): # Function for adding a node + self.children[(i,j)] = Child + + def Draw(self): # function for drawing the board + self.Current.Draw_mat() \ No newline at end of file diff --git a/game.py b/game.py new file mode 100644 index 0000000..003d943 --- /dev/null +++ b/game.py @@ -0,0 +1,282 @@ +import pygame +import numpy as np +import sys + + +class Game: + def __init__(self): + self.grid_size = 10 # default + if len(sys.argv) > 1: + self.grid_size = int(sys.argv[1]) + + # It turns out that there are nice structures when setting ~0.75 walls per slot + self.start_walls = int(0.75 * self.grid_size ** 2) + + self.accept_clicks = True + + # variables for the boxes for each player (x would be computer) + self.a_boxes = 0 + self.b_boxes = 0 + self.x_boxes = 0 + + self.turn = "X" + self.caption = "'s turn " + + # 0 empty 1 is A 2 is B and 3 is X + self.grid_status = np.zeros((self.grid_size, self.grid_size), np.int) + self.upper_walls_set_flags = np.zeros((self.grid_size, self.grid_size), np.dtype(bool)) + self.left_walls_set_flags = np.zeros((self.grid_size, self.grid_size), np.dtype(bool)) + + # set the outer walls + for column in range(self.grid_size): + for row in range(self.grid_size): + if column == 0: + self.left_walls_set_flags[column][row] = True + if row == 0: + self.upper_walls_set_flags[column][row] = True + + # initialize pygame + pygame.init() + + # set the display size (one slot has 30x30 pixels; Walls: 4x26 Box: 26x26) + self.screen = pygame.display.set_mode([30 * self.grid_size + 4, 30 * self.grid_size + 4]) + + # load all images + self.empty = pygame.image.load("pics/empty.png") + self.A = pygame.image.load("pics/A.png") + self.B = pygame.image.load("pics/B.png") + self.X = pygame.image.load("pics/X.png") + self.block = pygame.image.load("pics/block.png") + self.lineX = pygame.image.load("pics/lineX.png") + self.lineXempty = pygame.image.load("pics/lineXempty.png") + self.lineY = pygame.image.load("pics/lineY.png") + self.lineYempty = pygame.image.load("pics/lineYempty.png") + + tries = 0 + # set the start walls randomly but do not create any opportunity to directly close boxes + while self.start_walls > 0 and tries < 4*self.grid_size**2: + x = np.random.randint(self.grid_size) + y = np.random.randint(self.grid_size) + up = np.random.randint(2) + + if up: + if not self.upper_walls_set_flags[x][y] \ + and self.get_number_of_walls(x, y) < 2 \ + and self.get_number_of_walls(x, y - 1) < 2: + self.upper_walls_set_flags[x][y] = True + self.start_walls -= 1 + else: + if not self.left_walls_set_flags[x][y] \ + and self.get_number_of_walls(x, y) < 2 \ + and self.get_number_of_walls(x - 1, y) < 2: + self.left_walls_set_flags[x][y] = True + self.start_walls -= 1 + + tries += 1 + + # now it's the first players turn + self.turn = "A" + self.show() + + while True: + # go through all events and check the types + for event in pygame.event.get(): + # quit the game when the player closes it + if event.type == pygame.QUIT: + pygame.quit() + exit(0) + + # left click + elif event.type == pygame.MOUSEBUTTONDOWN and pygame.mouse.get_pressed()[0]: + if not self.accept_clicks: + continue + + # get the current position of the cursor + x = pygame.mouse.get_pos()[0] + y = pygame.mouse.get_pos()[1] + + # check whether it was a not set wall that was clicked + wall_x, wall_y = self.get_wall(x, y) + + if not (wall_x >= 0 and wall_y >= 0): + continue + + upper_wall = wall_y % 30 == 0 + + if upper_wall: + if not self.upper_walls_set_flags[wall_x//30][wall_y//30]: + self.upper_walls_set_flags[wall_x//30][wall_y//30] = True + self.screen.blit(self.lineX, (wall_x, wall_y)) + else: + continue + else: + if not self.left_walls_set_flags[wall_x//30][wall_y//30]: + self.left_walls_set_flags[wall_x//30][wall_y//30] = True + self.screen.blit(self.lineY, (wall_x, wall_y)) + else: + continue + + if not self.set_all_slots() > 0: + if self.turn == "A": + self.turn = "B" + elif self.turn == "B": + self.turn = "A" + + if self.won(): + self.accept_clicks = False + + else: + + # set the display caption + pygame.display.set_caption(self.turn + self.caption + " A:" + str( + self.a_boxes) + " B:" + str(self.b_boxes)) + + # update the players screen + pygame.display.flip() + + def get_number_of_walls(self, slot_column, slot_row): + """ + Get the number of set walls around the passed slot + :param slot_column: x of the slot + :param slot_row: y of the slot + :return: number of set walls + """ + number_of_walls = 0 + + if slot_column == self.grid_size - 1: + number_of_walls += 1 + elif self.left_walls_set_flags[slot_column + 1][slot_row]: + number_of_walls += 1 + + if slot_row == self.grid_size - 1: + number_of_walls += 1 + elif self.upper_walls_set_flags[slot_column][slot_row + 1]: + number_of_walls += 1 + + if self.left_walls_set_flags[slot_column][slot_row]: + number_of_walls += 1 + + if self.upper_walls_set_flags[slot_column][slot_row]: + number_of_walls += 1 + + return number_of_walls + + @staticmethod + def get_wall(pos_x, pos_y): + rest_x = pos_x % 30 + rest_y = pos_y % 30 + + wall_slot_x = pos_x//30 + wall_slot_y = pos_y//30 + + # in a corner + if rest_x < 4 and rest_y < 4: + return -1, -1 + + if rest_x < 4: + # is left wall of the slot + return wall_slot_x*30, wall_slot_y*30 + 4 + + if rest_y < 4: + # is upper wall of the slot + return wall_slot_x*30 + 4, wall_slot_y*30 + + # inside the box => not a wall + return -1, -1 + + def set_all_slots(self): + """ + Find all newly closed boxes and close them for the current player + :return: number of closed boxes + """ + to_return = 0 + + for column_ in range(self.grid_size): + for row_ in range(self.grid_size): + if self.grid_status[column_][row_] != 0 or self.get_number_of_walls(column_, row_) < 4: + continue + + if self.turn == "A": + self.grid_status[column_][row_] = 1 + self.screen.blit(self.A, (column_ * 30 + 4, row_ * 30 + 4)) + self.a_boxes += 1 + elif self.turn == "B": + self.grid_status[column_][row_] = 2 + self.screen.blit(self.B, (column_ * 30 + 4, row_ * 30 + 4)) + self.b_boxes += 1 + elif self.turn == "X": + self.grid_status[column_][row_] = 3 + self.screen.blit(self.X, (column_ * 30 + 4, row_ * 30 + 4)) + self.x_boxes += 1 + + to_return += 1 + + return to_return + + def won(self): + """ + Check whether the game was finished + If so change the caption to display the winner + :return: won or not + """ + if self.a_boxes + self.b_boxes + self.x_boxes == self.grid_size ** 2: + if self.a_boxes < self.b_boxes: + won_caption = "Player B won! Congrats" + elif self.b_boxes < self.a_boxes: + won_caption = "Player A won! Congrats" + else: + won_caption = "It's a tie!" + + # set the display caption + pygame.display.set_caption(won_caption) + + # update the players screen + pygame.display.flip() + + return True + else: + return False + + def show(self): + """ + Reload the screen + Use the current grid and wall information to + update the players screen + """ + self.screen.fill(0) + + # loop over all slots + for column in range(self.grid_size): + for row in range(self.grid_size): + x, y = column * 30, row * 30 + self.screen.blit(self.block, (x, y)) + x += 4 + if not self.upper_walls_set_flags[column][row]: + self.screen.blit(self.lineXempty, (x, y)) + else: + self.screen.blit(self.lineX, (x, y)) + x -= 4 + y += 4 + if not self.left_walls_set_flags[column][row]: + self.screen.blit(self.lineYempty, (x, y)) + else: + self.screen.blit(self.lineY, (x, y)) + + # calculate x and y in pixels + x, y = column * 30 + 4, row * 30 + 4 + + if self.grid_status[column][row] == 0: + self.screen.blit(self.empty, (x, y)) + elif self.grid_status[column][row] == 1: + self.screen.blit(self.A, (x, y)) + elif self.grid_status[column][row] == 2: + self.screen.blit(self.B, (x, y)) + elif self.grid_status[column][row] == 3: + self.screen.blit(self.X, (x, y)) + + pygame.display.set_caption(self.turn + self.caption + " A:" + str(self.a_boxes) + " B:" + str( + self.b_boxes)) + pygame.display.flip() + + +game = Game() # start a game \ No newline at end of file -- cgit v1.2.3