diff options
| -rw-r--r-- | Algorithm.py | 68 | ||||
| -rw-r--r-- | Board.py | 78 | ||||
| -rw-r--r-- | DotsNBoxes.py | 73 | ||||
| -rw-r--r-- | Nodes.py | 18 | ||||
| -rw-r--r-- | game.py | 282 |
5 files changed, 519 insertions, 0 deletions
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 @@ -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 |