Apr-27-2019, 09:09 PM
I wrote a simpler scoring heuristic and implemented minimax with alpha-beta pruning. The result is a bot that makes some moves that give me pause, but it still dives into the corners at almost the first opportunity. The pseudocode on the Wikipedia article was a little hard to read. I'm not certain if my implementation of alpha-beta pruning is correct. The scoring heuristic also needs to be significantly improved. This is in another version of the file so the original scoring heuristic is still around. Here's the whole Othello - different scoring logic.pyw file:
import wx import os from functools import partial import random from math import inf from concurrent import futures thread_pool_executor = futures.ThreadPoolExecutor(max_workers = 1) # The wxPython implementation of an Othello game I wrote for my mother. # These are displayed in help windows when an item from the help menu is selected: gameRules = """Game Rules Othello is a game played on a board with an 8x8 grid on it. There are 2 players and 64 gamepieces, enough to fill the entire gameboard. Each piece has a black side and a white side and each player plays as either black or white. The goal is when either the board is filled or their is no valid move available to either player for the majority of the pieces on the board to have your color upturned. The application will automatically assess whether an attempted move is valid but to alleviate the frustration of guessing where one can place a gamepiece, here is a brief explanation: If a space is already occupied, the move is invalid. If there are no adjacent pieces, the move is invalid. When there are adjacent pieces, their must be at least one vertical, horizontal or diagonal row of your opponents pieces with another of your pieces on the other end. When you place a gamepiece, all adjacent vertical, horizontal or diagonal rows of your opponents pieces with another of your pieces at the other end will be flipped. You may occaisionally find yourself in a situation in which there is no valid move available to you but your opponent has a valid move. You can give your opponent your move by clicking their player button. The text in their button will turn red, indicating that it is their turn. If there are no valid moves available to you, it will say so in the status bar. """ applicationHelp = """Application Help Options Menu: The options menu provides options for starting a new game, saving a game, opening an existing game, saving and quitting and quit without saving. A single player gamemode is also listed in this menu, but it is not yet implemented. Give Move to Opponent: There are situations in which the current player has no valid move, but their opponent does. In this situation, you give your move to your opponent by clicking their player button (one of the large buttons at the top or bottom of the window.) The text in their button will turn red indicating that it's their move. Options Menu Items: New Game -- Start a new game. New Single Player Game -- coming soon Save Game -- Displays a file navigator to locate and select a save file to save the current game. The destination file must be a text file (*.txt). The application will remember the path of a current saved game until it is closed, so you won't be prompted for a save file if you have specified one already. When 'new game' is clicked, the path of any previously specified save file is forgotten to avoid overwriting a pre-existing saved game. Save Game As -- Allows you to save a previously saved game under a different name. This feature can be used for among other things, creating back-ups of your saves. Open Game -- Displays a file navigator to locate the a save file (*.txt) to open a pre-existing game. The filepath of the selected game is remembered until the application is closed, so you won't be prompted to re-select the file when saving. Save and Quit -- Automatically saves the game before exiting. If no file has been previously specified, the user will be prompted for a save file. Quit Without Saving -- Quits the game without saving. """ # The program itself is implemented inside a class for encapsulation and to allow import, # ease of implementation, and readability. class OthelloGameFrame(wx.Frame): """ The Othello game proper. Almost all of the code that makes this app work is in here. It uses a pretty standard constructor for a class inheriting from Frame: __init__(self, *args, **kwArgs) Passing in the size parameter is recommended. """ # I know it is not recommended to create custom IDs but I didn't find wx IDs which # corresponded to the actions of these four menu items. ID_NEW_SINGLE_PLAYER = wx.NewIdRef(1) ID_SAVE_AND_QUIT = wx.NewIdRef(1) ID_GAMERULES = wx.NewIdRef(1) ID_QUIT_WITHOUT_SAVING = wx.NewIdRef(1) # Constants for buttons: PLAYER1BUTT = wx.NewIdRef(1) PLAYER2BUTT = wx.NewIdRef(1) # Color Constants: bgAndBoardColor = wx.Colour(0x41, 0xA1, 0x23) player1Color = wx.Colour(0x00, 0x00, 0x00) player2Color = wx.Colour(0xFF, 0xFF, 0xFF) def __init__ (self, *args, **kwArgs): wx.Frame.__init__(self, *args, **kwArgs) """ OthelloGameFrame.__init__(self, *args, *kwArgs) Returns an object representing the main window of the Othello game app. Specifying the size parameter in the arg list is recommended. Otherwise, it works just like a normal wx.Frame. """ # non-GUI related instance variables: self.saveFile = "" self.firstPlayersMove = True self.gameAltered = False self.robot = False # All instances of classes evaluate to True unless __bool__ is defined and can return False. # Basically, whether the game is single player or 2 player is indicated by whether this object, # whatever its type evaluates to True. self.SetBackgroundColour(wx.Colour(0x30, 0x30, 0x30)) self.CreateStatusBar() # Creating an options menu with all the non-gameplay related options # I want to make available to the user. self.optionsMenu = wx.Menu() menuNewGame = self.optionsMenu.Append(wx.ID_NEW, "&New Game", "Start a new game.") menuNewSinglePlayer = self.optionsMenu.Append(self.ID_NEW_SINGLE_PLAYER, "New Single &Player Game", "Start a game against the AI. This feature is currently unavailable.") self.optionsMenu.AppendSeparator() menuSaveGame = self.optionsMenu.Append(wx.ID_SAVE, "&Save Game", "Save the current game and remember the filename for future saves.") menuSaveAs = self.optionsMenu.Append(wx.ID_SAVEAS, "Save Game &As...", "Save a previously save game under a new name.") menuOpenGame = self.optionsMenu.Append(wx.ID_OPEN, "&Open Game", "Open a previously saved game.") menuSaveAndQuit = self.optionsMenu.Append(self.ID_SAVE_AND_QUIT, "Sa&ve and Quit", "Save the game and quit.") menuQuitWithoutSaving = self.optionsMenu.Append(self.ID_QUIT_WITHOUT_SAVING, "Quit &Without Saving", "Close the application without saving the game.") # The help menu will display instances of HelpWindow containing a helptext # appropriate to the menu item selected. self.helpMenu = wx.Menu() menuShowGamerules = self.helpMenu.Append(self.ID_GAMERULES, "Game&rules", "Explains Othello game rules.") menuShowAppHelp = self.helpMenu.Append(wx.ID_HELP, "Application &Help", "How to use this software") # Create the toolbar. self.toolbar = wx.MenuBar() self.toolbar.Append(self.optionsMenu, "&Options") self.toolbar.Append(self.helpMenu, "&Help") self.SetMenuBar(self.toolbar) # Add Widgets player1ButtonFont = wx.Font(30, wx.ROMAN, wx.NORMAL, wx.NORMAL) player2ButtonFont = wx.Font(30, wx.ROMAN, wx.NORMAL, wx.NORMAL) gameboardButtonFont = wx.Font(12, wx.ROMAN, wx.NORMAL, wx.NORMAL) # You should see what this code looked like before I put this in! # Thank you, yoriz! buttonGrid = wx.GridSizer(8, 8, 0, 0) buttonGrid.SetHGap(2) buttonGrid.SetVGap(2) self.gameboard = [] for row in range(8): board_columns = [] for col in range(8): btn = wx.Button(self, style=wx.NO_BORDER) btn.SetFont(gameboardButtonFont) btn.SetBackgroundColour(self.bgAndBoardColor) btn.SetForegroundColour(wx.Colour(0xFF, 0x00, 0x00)) btn.Bind(wx.EVT_BUTTON, partial(self.gameboardButtonClicked, row=row, col=col)) buttonGrid.Add(btn, 0, wx.EXPAND) board_columns.append(btn) self.gameboard.append(board_columns) # Creating the layout: self.player1Butt = wx.Button(self, self.PLAYER1BUTT, "Player 1", style = wx.NO_BORDER) self.player1Butt.SetFont(player1ButtonFont) self.player1Butt.SetBackgroundColour(self.player1Color) self.player1Butt.SetForegroundColour(wx.Colour(0xFF, 0x00, 0x00)) self.player2Butt = wx.Button(self, self.PLAYER2BUTT, "Player 2", style = wx.NO_BORDER) self.player2Butt.SetFont(player2ButtonFont) self.player2Butt.SetBackgroundColour(self.player2Color) self.layout = wx.BoxSizer(wx.VERTICAL) self.layout.Add(self.player1Butt, 1, wx.EXPAND) self.layout.Add(buttonGrid, 8, wx.CENTRE) self.layout.Add(self.player2Butt, 1, wx.EXPAND) self.SetSizer(self.layout) # Bind the menu events to their respective callbacks. self.Bind(wx.EVT_MENU, self.newGame, menuNewGame) self.Bind(wx.EVT_MENU, self.newSinglePlayer, menuNewSinglePlayer) self.Bind(wx.EVT_MENU, self.saveGame, menuSaveGame) self.Bind(wx.EVT_MENU, self.saveAs, menuSaveAs) self.Bind(wx.EVT_MENU, self.openGame, menuOpenGame) self.Bind(wx.EVT_MENU, self.saveAndQuit, menuSaveAndQuit) self.Bind(wx.EVT_MENU, self.quitWithoutSaving, menuQuitWithoutSaving) self.Bind(wx.EVT_MENU, self.showGameRules, menuShowGamerules) self.Bind(wx.EVT_MENU, self.showAppHelp, menuShowAppHelp) # Bind the player buttons to callbacks self.Bind(wx.EVT_BUTTON, self.player1ButtonClicked, id = self.PLAYER1BUTT) self.Bind(wx.EVT_BUTTON, self.player2ButtonClicked, id = self.PLAYER2BUTT) # Bind all close events to self.quitWithoutSaving to ensure the user is always # asked whether they're sure they want to quit without saving their game. self.Bind(wx.EVT_CLOSE, self.quitWithoutSaving) self.Show(True) self.newGame() def newGame (self, event = None): """ OthelloGameFrame.newGame(self, event = None) Resets the gameboard and resets the saveFile field to prevent an existing game from being overwritten. """ self.saveFile = "" self.gameAltered = False for row in range(8): for col in range(8): self.gameboard[row][col].SetBackgroundColour(self.bgAndBoardColor) self.gameboard[3][3].SetBackgroundColour(self.player2Color) self.gameboard[3][4].SetBackgroundColour(self.player1Color) self.gameboard[4][3].SetBackgroundColour(self.player1Color) self.gameboard[4][4].SetBackgroundColour(self.player2Color) # For testing purposes: #self.gameboard[2][2].SetBackgroundColour(self.player2Color) #self.gameboard[2][5].SetBackgroundColour(self.player1Color) self.firstPlayersMove = True self.player1Butt.SetForegroundColour("RED") self.player2Butt.SetForegroundColour("BLACK") def newSinglePlayer (self, event = None): """ OthelloGameFrame.newSinglePlayer(self, event = None) This feature is not yet implemented. """ with SelectDifficultyDialog(self) as dlg: if dlg.ShowModal() == wx.ID_OK: self.newGame() self.robot = PlayerBot(self, dlg.getCurrentDifficulty()) self.SetStatusText("") else: self.SetStatusText("New single player aborted.") return def saveGame (self, event = None): """ OthelloGameFrame.saveGame(self, event = None) Prompt the user for a file in which to save the game if none has been selected yet and save the game """ saveList = [[]] for row in range(8): for col in range(8): # Map each gameboard color to a number: 0 for empty space, 1 for player 1 (black), and 2 for player 2. saveList[-1].append( {str(self.bgAndBoardColor): 0, str(self.player1Color): 1, str(self.player2Color):2}[str(self.gameboard[row][col].GetBackgroundColour())]) if row != 7: saveList.append([]) isSinglePlayer = False; if self.robot: isSinglePlayer = True saveDict = {"saveList": saveList, "firstPlayersMove": self.firstPlayersMove, "isSinglePlayer": isSinglePlayer} # Save everything in a dictionary. if self.robot: saveDict["difficulty"] = self.robot.difficulty # If no file has been previously selected, use a wx.FileDialog to get the # path of the file in which the user wants to save their game. if self.saveFile == "": fd = wx.FileDialog(self, "Select a file", os.getcwd(), "", "*.txt", wx.FD_OPEN) if fd.ShowModal() == wx.ID_OK: self.saveFile = fd.GetPath() else: fd.Destroy() return fd.Destroy() # Save the game as a string representation of saveDict. with open(self.saveFile, "w") as f: try: f.write(repr(saveDict)) except FileNotFoundError: mdlg = wx.MessageDialog(self, "The currently selected file could not be accessed at this time. Please try again.", "wxOthello", wx.OK) mdlg.ShowModal() mdlg.Destroy() self.saveFile = "" self.gameAltered = False def saveAs (self, event = None): """ OthelloGameFrame.saveAs(self, event = None) Save a previously saved game under a different filename. """ self.saveFile = "" self.saveGame() def openGame (self, event = None): """ OthelloGameFrame.openGame(self, event = None) Open a previously saved game stored in the format described in the saveGame method {"saveList": [Nested lists containing integers mapped to gameboard colors], "firstPlayersMove": True/False} """ # Use wx.FileDialog to get the save file to open. fd = wx.FileDialog(self, "Select a file", os.getcwd(), "", "*.txt", wx.FD_OPEN) if fd.ShowModal() == wx.ID_OK: self.saveFile = fd.GetPath() else: fd.Destroy() return fd.Destroy() # Open the save file and convert its contents into a dictionary. with open(self.saveFile, "r") as f: try: saveDict = eval(f.read()) except FileNotFoundError: mdlg = wx.MessageDialog(self, "The currently selected file could not be accessed at this time. Please try again.", "wxOthello", wx.OK) mdlg.ShowModal() mdlg.Destroy() self.saveFile = "" return # If the files contents are incompatible with the attempted parse into a dictionary, inform the user. except SyntaxError: mdlg = wx.MessageDialog(self, "The currently selected file is either corrupted or its contents incompatible with opening in this game.", "wxOthello", wx.OK) mdlg.ShowModal() mdlg.Destroy() self.saveFile = "" return # Load the dictionarys data into the relevant instance variables. When single player mode is implemented, # a check for the key "isSinglePlayer" will also need to be added here. self.firstPlayersMove = saveDict["firstPlayersMove"] if "isSinglePlayer" in saveDict: if saveDict["isSinglePlayer"]: self.robot = PlayerBot(self, saveDict["difficulty"]) for row in range(8): for col in range(8): self.gameboard[row][col].SetBackgroundColour([self.bgAndBoardColor, self.player1Color, self.player2Color][saveDict["saveList"][row][col]]) self.Refresh() self.gameAltered = False def saveAndQuit (self, event = None): """ OthelloGameFrame.saveAndQuit(self, event = None) Saves the game and quits. """ self.saveGame() self.Destroy() exit() def quitWithoutSaving (self, event = None): """ OthelloGameFrame.quitWithoutSaving(self, event = None) If the game has been altered since last save, this function asks the user via messageBox whether they are sure they don't want to save. It exits the game if they answer yes, calls saveGame if they answer no and returns if they click cancel. """ if self.gameAltered: usersFinalDecision = wx.MessageBox("All progress you've made in this game will be lost. Are you sure you want to quit without saving? Answering 'no' will open a save dialog if no file was selected previously then exit the game.", "wxOthello", wx.YES_NO | wx.CANCEL, self) if usersFinalDecision == wx.YES: self.Destroy() exit() elif usersFinalDecision == wx.NO: self.saveGame() elif usersFinalDecision == wx.CANCEL: return else: self.Destroy() exit() def showGameRules (self, event = None): """ OthelloGameFrame.showGameRules(self, event = None) This callback displays an instance of HelpWindow that displays the rules of Othello as its help text with a call to showHelp. """ global gameRules self.showHelp(gameRules) def showAppHelp (self, event = None): """ OthelloGameFrame.showAppHelp(self, event = None) This callback displays an instance of HelpWindow that displays help information for this application with a call to showHelp. """ global applicationHelp self.showHelp(applicationHelp) def showHelp(self, helpText): """ OthelloGameFrame.showHelp(self, helpText) Displays an instance of HelpWindow displaying the value of helpText. """ with HelpWindow(self, helpText) as hdlg: hdlg.ShowModal() def player1ButtonClicked (self, event = None): """ OthelloGameFrame.player1ButtonClicked(self, event = None) Gives the next move to player 1. This feature is intended for use when it is player 2s turn and there are no moves available to player 2. """ self.firstPlayersMove = True self.player1Butt.SetForegroundColour("RED") self.player2Butt.SetForegroundColour("BLACK") def player2ButtonClicked (self, event = None): """ OthelloGameFrame.player2ButtonClicked(self, event = None) Gives the next move to player 2. This feature is intended for use when it is player 1s turn and there are no moves available to player 1. """ self.firstPlayersMove = False self.player1Butt.SetForegroundColour("WHITE") self.player2Butt.SetForegroundColour("RED") if self.robot: self.robot.makeMove() def displayErrorOnButton(row, col, message): self.gameboard[row][col].SetLabel(message) wx.MilliSleep(1000) self.gameboard[row][col].SetLabel("") def gameboardButtonClicked (self, event = None, row = 0, col = 0): """ OthelloGameFrame.gameboardButtonClicked(self, event = None, row = 0, col = 0) This method is called through lambdas bound to the gameboard buttons generated in __init__. It displays an error message in the space where the move is attempted and returns if a move is invalid. Otherwise, it executes the move, checks whether somebody has won, gives the next move to the other player, and informs the next player if there is no move available to them in the status bar. """ # self,firstPlayersMove is a boolean indicating whether it's player 1s turn. if self.firstPlayersMove: me = self.player1Color opponent = self.player2Color else: me = self.player2Color opponent = self.player1Color # Detect invalid move attempts, inform the user if their move is invalid and # the reason their move is invalid and return from the function. moveIsValid, message = self.isValidMove(row, col, me, opponent) if not moveIsValid: self.gameboard[row][col].SetLabel(message) wx.MilliSleep(1000) self.gameboard[row][col].SetLabel("") return # Make the move selected by the player. self.makeMove(row, col, me, opponent) self.gameAltered = True # The method detectWin returns a tuple with a boolean indicating whether there # are no valid moves available to either player and a message string appropriate to # the situation of 1: A player 1 victory, 2: A draw, or 3: A player 2 victory. winDetected, message = self.detectWin() if winDetected: m = wx.MessageDialog(self, message, "wxOthello") m.ShowModal() m.Destroy() self.gameAltered = False # Invert the value of the self.firstPlayersMove flag and change the color of the # text in the player 1 and player 2 buttons in a manner according to whose turn it # is. self.firstPlayersMove = not self.firstPlayersMove if self.firstPlayersMove: self.player1Butt.SetForegroundColour("RED") self.player2Butt.SetForegroundColour("BLACK") else: self.player1Butt.SetForegroundColour("WHITE") self.player2Butt.SetForegroundColour("RED") # Inform the next player if there is no valid move available to them. if not self.moveAvailableToPlayer(opponent, me): if opponent == self.player1Color: self.SetStatusText("No move available to player 1.") else: self.SetStatusText("No move available to player 2.") else: self.SetStatusText("") # If in single player mode, let the bot make a move and then return. if self.robot and not self.firstPlayersMove: self.robot.makeMove() return def moveAvailableToPlayer(self, me, opponent): for row in range(8): for col in range(8): if self.isValidMove(row, col, me, opponent)[0]: return True return False def isValidMove (self, row, col, me, opponent): """ OthelloGameFrame.isValidMove(self, row, col, me, opponent) This method returns the tuple (isValidMove, messaage). It tests whether a move at a specified position on the gameboard is valid for a specific player and if the move is invalid, returns a message explaining why the move is invalid. """ # Check whether the grid space is empty if self.gameboard[row][col].GetBackgroundColour() != self.bgAndBoardColor: return False, "This Space\nIs Occupied!" # A series of scanning vectors for the 8 scanning directions: up, down, left, right and the four diagonal directions scanningDirections = ((-1, 0), (0, 1), (1, 0), (0, -1), (-1, -1), (-1, 1), (1, 1), (1, -1)) # Iterate over the diffetent scanning directions, return True if the move is valid and set message to a message string # that explains why the move is invalid, if the move is invalid. message = "No Adjacent\nGamepieces!" for SDRow, SDCol in scanningDirections: currentRow = row + SDRow currentCol = col + SDCol sawOpponent = False while currentRow in range(0, 8) and currentCol in range(0, 8): if self.gameboard[currentRow][currentCol].GetBackgroundColour() == self.bgAndBoardColor: break else: message = "No Pieces\nTo Flip!" if self.gameboard[currentRow][currentCol].GetBackgroundColour() == opponent: sawOpponent = True if self.gameboard[currentRow][currentCol].GetBackgroundColour() == me and sawOpponent: return True, "You won't see this message!" if self.gameboard[currentRow][currentCol].GetBackgroundColour() == me and not sawOpponent: break currentRow += SDRow currentCol += SDCol return False, message def makeMove (self, row, col, me, opponent): """ OthelloGameFrame.makeMove(self, row, col, me, opponent) Performs a move for a specified player at a specified position. """ # Put down the players gamepiece self.gameboard[row][col].SetBackgroundColour(me) # A series of scanning vectors for the 8 scanning directions: up, down, left, right and the four diagonal directions scanningDirections = ((-1, 0), (0, 1), (1, 0), (0, -1), (-1, -1), (-1, 1), (1, 1), (1, -1)) # Iterate over the scanning vectors. for SDRow, SDCol in scanningDirections: currentRow = row + SDRow currentCol = col + SDCol sawOpponent = False canFlipPieces = False # Check whether gamepieces can be flipped in the current scanning direction. while currentRow in range(0, 8) and currentCol in range(0, 8): if self.gameboard[currentRow][currentCol].GetBackgroundColour() == self.bgAndBoardColor: break if self.gameboard[currentRow][currentCol].GetBackgroundColour() == opponent: sawOpponent = True if self.gameboard[currentRow][currentCol].GetBackgroundColour() == me and sawOpponent: canFlipPieces = True break if self.gameboard[currentRow][currentCol].GetBackgroundColour() == me and not sawOpponent: break currentRow += SDRow currentCol += SDCol # If gamepieces can be flipped in the current scanning direction, flip the pieces. currentRow = row + SDRow currentCol = col + SDCol while canFlipPieces and currentRow in range(0, 8) and currentCol in range(0, 8): if self.gameboard[currentRow][currentCol].GetBackgroundColour() == opponent: self.gameboard[currentRow][currentCol].SetBackgroundColour(me) elif self.gameboard[currentRow][currentCol].GetBackgroundColour() == me: break else: print("Kyle, you have some debugging to do! This else clause is never supposed to execute. Something has gone horribly wrong!") currentRow += SDRow currentCol += SDCol def detectWin (self): """ OthelloGameFrame.detectWin(self) This method returns a the tuple (noValidMoves, message), where noValidMoves is a boolean indicating whether there are no more valid moves available to either player and message is one of the the strings "The winner is player 1!", if the majority of the pieces on the board are black, "This game is a draw!" if player 1 and player 2 have equal numbers of pieces on the board, or "The winner is player 2!" if the majority of the pieces on the board are white. """ noValidMoves = True # We begin by assuming that neither player has a valid move available to them. player1Count = 0 # Counters for the number of spaces each player has captured. player2Count = 0 # Iterate over the gameboard. Check whether there is a valid move available to either player and # count the number of spaces captured by each player. for row in range(8): for col in range(8): if self.isValidMove(row, col, self.player1Color, self.player2Color)[0] or self.isValidMove(row, col, self.player2Color, self.player1Color)[0]: noValidMoves = False if self.gameboard[row][col].GetBackgroundColour() == self.player1Color: player1Count += 1 if self.gameboard[row][col].GetBackgroundColour() == self.player2Color: player2Count += 1 if noValidMoves: # Return True and a message indicating who won if player1Count > player2Count: return True, "The winner is player 1!" elif player1Count == player2Count: return True, "This game is a draw!" elif player1Count < player2Count: return True, "The winner is player 2!" else: return False, "You're not supposed to see this message." class PlayerBot: """ Instances of this class play as player 2 in single player mode. class PlayerBot: __init__(self, parent, difficulty) parent - an OthelloGameFrame instance difficulty - an integer between 0 and 100 """ positionalScoringMap = ((500, -200, 99, 80, 80, 99, -200, 500), (-200, -300, -10, -5, -5, -10, -300, -200), (99, -10, 200, 150, 150, 200, -10, 99), (80, -5, 150, 100, 100, 150, -5, 80), (80, -5, 150, 100, 100, 150, -5, 80), (99, -10, 200, 150, 150, 200, -10, 99), (-200, -300, -10, -5, -5, -10, -300, -200), (500, -200, 99, 80, 80, 99, -200, 500)) bdCode = 0 # Constants for encoding empty board spaces, player 1 and player 2 in an internal p1Code = 1 # representation of the current game state. p2Code = 2 # Constants for early game, mid game and late game used by the scoring heuristic. ST_EARLY = 3 ST_MID = 4 ST_LATE = 5 # Constants for top, left, right, and bottom used by the trap and entrance detection and assessment # methods. TOP = (0, 2) LEFT = (2, 0) RIGHT = (2, 6) BOTTOM = (6, 2) def __init__ (self, parent, difficulty): self.parent = parent self.difficulty = difficulty self.gameState = self.getInitialGameState() # A list of moves potentially detrimental to the bots midgame. self.movesDetrimentalToMidgame = [] def getInitialGameState (self): """ PlayerBot.getInitialGameState (self): Returns 8 integer lists nested inside a list representing the initial state of a game of Othello, where 0 is an empty space, 1 is player 1, and 2 is player 2. """ gameState = [] for row in range(8): currentRow = [] for col in range(8): currentRow.append(self.bdCode) gameState.append(currentRow) currentRow = [] gameState[2][2] = self.p2Code gameState[2][3] = self.p1Code gameState[3][2] = self.p1Code gameState[3][3] = self.p2Code return gameState def makeMove(self): """ PlayerBot.makeMove (self) This method makes a move in its parent as player2 and surrenders its move to player 1 if there are no moves available to it. """ self.updateGameState() # Update the objects internal representation of the current state of the game. validMoves = self.getAllValidMoves(self.gameState, self.p2Code, self.p1Code) if validMoves == []: # If there are no moves available to the bot, give player 1 its move. self.parent.player1ButtonClicked() return if random.randint(0, 100) <= self.difficulty: # This outer if statement is used to make the occasional 'mistake'; a move # selected randomly from the set of all valid moves. The frequency of these # 'mistakes' is determined by the difficulty setting. _, bestMove = self.miniMax(self.gameState, 5, -inf, inf, True) self.parent.gameboardButtonClicked(row = bestMove[0], col = bestMove[1]) return else: # Make a 'mistake'. randomMove = validMoves[random.randint(0, len(validMoves) - 1)] self.parent.gameboardButtonClicked(row = randomMove[0], col = randomMove[1]) self.updateGameState() def miniMax (self, gameState, depth, alpha, beta, maximizingPlayer): if depth == 0 or (self.getAllValidMoves(gameState, self.p2Code, self.p1Code) == [] and self.getAllValidMoves(gameState, self.p1Code, self.p2Code)): return self.scoreGameState(gameState), (0, 0) if maximizingPlayer: allValidMoves = self.getAllValidMoves(gameState, self.p2Code, self.p1Code) maxScore = -inf bestMove = (0, 0) for move in allValidMoves: _, gameStateAfterMove = self.scoreMove(move, gameState, self.p2Code, self.p1Code) moveScore, _ = self.miniMax(gameStateAfterMove, depth - 1, alpha, beta, False) if moveScore > alpha: alpha = moveScore if alpha >= beta: break if moveScore > maxScore: maxScore = moveScore bestMove = move return maxScore, bestMove else: # Minimizing player allValidMoves = self.getAllValidMoves(gameState, self.p1Code, self.p2Code) minScore = inf bestMove = (0, 0) for move in allValidMoves: _, gameStateAfterMove = self.scoreMove(move, gameState, self.p1Code, self.p2Code) moveScore, _ = self.miniMax(gameStateAfterMove, depth - 1, alpha, beta, True) if moveScore < beta: beta = moveScore if alpha >= beta: break if moveScore < minScore: minScore = moveScore bestMove = move return minScore, bestMove def getAllValidMoves (self, gameState, me, opponent): """ PlayerBot.getAllValidMoves(self, gameState, me, opponent) Return a list of all moves which are valid for the player 'me' in the given game state. """ validMoves = [] for row in range(8): for col in range(8): if self.isValidMove(row, col, me, opponent, gameState): validMoves.append( (row, col) ) return validMoves def scoreGameState (self, gameState): """ PlayerBot.scoreGameState(self, gameState) Used by the minMax algorithm to score a game state using a series of heuristics, returning positive score values to game states which are favorable to the bot and negative score values for game states which are unfavorable. """ score = 0 # Initialize score to zero. me = self.p2Code # I use the terms 'me' and 'opponent' in this function opponent = self.p1Code # for code clarity. These variables serve no other purpose. validMoves = self.getAllValidMoves(gameState, me, opponent) # Check whether the bot has no options available. if len(validMoves) == 0: # Check whether the player has any moves. Return winning or losing score values # if there are no moves available to the player. if len(self.getAllValidMoves(gameState, opponent, me)) == 0: # Score the game. myScore = 0 oppScore = 0 for row in range(8): for col in range(8): if gameState[row][col] == me: myScore += 1 if gameState[row][col] == opponent: oppScore += 1 score += myScore - oppScore if score > 0: return 999_999_999_999 + score # Return this if the bot won. elif score == 0: return 0 # Return 0 in a draw. elif score < 0: return -999_999_999_999 + score # Return this if the bot loses. else: # Issue a score penalty for the bot losing a turn to the opponent. score -= 250 # Add the positional value of all the bots pieces and subtract the positional # value of all the players pieces. for row in range(8): for col in range(8): if gameState[row][col] == me: score += self.positionalScoringMap[row][col] if gameState[row][col] == opponent: score -= self.positionalScoringMap[row][col] # Look for any of the bots pieces shielded from attack by surrounding opponents pieces # and add 15 to score for each one. score += self.findShieldedPieces(gameState, me, opponent) * 15 # Look for any of the players pieces shielded from attack by surrounding bot pieces and # subtract 15 from score for each one. score -= self.findShieldedPieces(gameState, opponent, me) * 15 # Look for any bots piece that has been made permanently inaccessible to the player and # add 100 to the score for each one. score += self.findPermanentPieces(gameState, me, opponent) * 100 # Look for any player piece that has been made permanently inaccessible to the bot and # subtract 100 from the score for each one. score -= self.findPermanentPieces(gameState, opponent, me) * 100 # Tell the bot Oh, by the way, your goal is to get as many pieces as possible. myScore = 0 oppScore = 0 for row in range(8): for col in range(8): if gameState[row][col] == me: myScore += 1 if gameState[row][col] == opponent: oppScore += 1 score += (myScore - oppScore) * 10 # Reward to bot for creating more options for itself than the player: score += (len(validMoves) - len(self.getAllValidMoves(gameState, opponent, me))) * 30 return score def findPermanentPieces (self, gameState, me, opponent): """ PlayerBot.findPermanentPieces(self, gameState, me, opponent) Returns the number of pieces in a given game state which can never be altered """ permanentPieceCount = 0 # The only way pieces can become permanent is if they're wedged into corners, so we # only need to see whether a corner has our color in it and if it doesn't, we can ignore # it entirely. However, if two non-opposing corners are filled, special care must be used # to ensure that permanent pieces aren't counted twice. topLeftHorizontalEdge = 0 topLeftVerticalEdge = 0 topRightHorizontalEdge = 0 topRightVerticalEdge = 0 bottomLeftVerticalEdge = 0 bottomLeftHorizontalEdge = 0 bottomRightVerticalEdge = 0 bottomRightHorizontalEdge = 0 # Count up contiguous rows and columns of our pieces on the edges starting from the corners until we come to an # opponent piece or empty space. if gameState[0][0] == me: row = 0 for col in range(8): if gameState[row][col] == me: topLeftHorizontalEdge += 1 else: break col = 0 for row in range(8): if gameState[row][col] == me: topLeftVerticalEdge += 1 else: break if gameState[0][7] == me: row = 0 for col in range(7, -1, -1): if gameState[row][col] == me: topRightHorizontalEdge += 1 else: break col = 7 for row in range(8): if gameState[row][col] == me: topRightVerticalEdge += 1 else: break if gameState[7][0] == me: row = 7 for col in range(8): if gameState[row][col] == me: bottomLeftHorizontalEdge += 1 else: break col = 0 for row in range(7, -1, -1): if gameState[row][col] == me: bottomLeftVerticalEdge += 1 else: break if gameState[7][7] == me: row = 7 for col in range(7, -1, -1): if gameState[row][col] == me: bottomRightHorizontalEdge += 1 else: break col = 7 for row in range(7, -1, -1): if gameState[row][col] == me: bottomRightVerticalEdge += 1 else: break # Some boolean flags to keep track of which gamepieces have already been counted as permanent: # The letters T, B, L, R, V and H are top, bottom, left, right, vertical and horizontal respectively. TLHedgeCounted = False; TLVedgeCounted = False TRHedgeCounted = False; TRVedgeCounted = False BLHedgeCounted = False; BLVedgeCounted = False BRHedgeCounted = False; BRVedgeCounted = False # Check whether any of the edges are filled corner to corner and start counting at any filled edges. if topLeftHorizontalEdge == 8: TRHedgeCounted = True canBreak = False for row in range(8): for col in range(8): if gameState[row][col] == me: permanentPieceCount += 1 else: canBreak = True break if canBreak: break if topLeftVerticalEdge == 8 and not TRHedgeCounted: BRVedgeCounted = True canBreak = False for col in range(8): for row in range(8): if gameState[row][col] == me: permanentPieceCount += 1 else: canBreak = True break if canBreak: break if bottomRightHorizontalEdge == 8: BRHedgeCounted = True canBreak = False for row in range(7, -1, -1): for col in range(7, -1, -1): if gameState[row][col] == me: permanentPieceCount += 1 else: canBreak = True break if canBreak: break if bottomRightVerticalEdge == 8 and not BRHedgeCounted: TRVedgeCounted = True canBreak = False for col in range(7, -1, -1): for row in range(7, -1, -1): if gameState[row][col] == me: permanentPieceCount += 1 else: canBreak = True break if canBreak: break # Count pieces in disconnected corners using the boolean flags to avoid counting pieces twice. # We count along the shorter edge, reducing the length of our scan along a diagonal if topLeftHorizontalEdge <= topLeftVerticalEdge and not TLHedgeCounted and not TLVedgeCounted: permanentPieceCount += topLeftVerticalEdge - topLeftHorizontalEdge HScanDist = topLeftVerticalEdge for row in range(8): for col in range(HScanDist): if gameState[row][col] == me: permanentPieceCount += 1 else: HScanDist = 0 break if HScanDist > 0: HScanDist -= 1 else: break TLHedgeCounted = True TLVedgeCounted = True elif topLeftVerticalEdge <= topLeftHorizontalEdge and not TLHedgeCounted and not TLVedgeCounted: permanentPieceCount += topLeftHorizontalEdge - topLeftVerticalEdge VScanDist = topLeftVerticalEdge for row in range(8): for col in range(VScanDist): if gameState[row][col] == me: permanentPieceCount += 1 else: VScanDist = 0 break if VScanDist > 0: VScanDist -= 1 else: break TLHedgeCounted = True TLVedgeCounted = True if topRightHorizontalEdge <= topRightVerticalEdge and not TRHedgeCounted and not TRVedgeCounted: permanentPieceCount += topRightVerticalEdge - topRightHorizontalEdge HScanDist = topRightHorizontalEdge for row in range(8): for col in range(7, -HScanDist - 1, -1): if gameState[row][col] == me: permanentPieceCount += 1 else: HScanDist = 0 break if HScanDist > 0: HScanDist -= 1 else: break TRHedgeCounted = True TRVedgeCounted = True elif topRightVerticalEdge <= topRightHorizontalEdge and not TRHedgeCounted and not TRVedgeCounted: permanentPieceCount += topRightHorizontalEdge - topRightVerticalEdge VScanDist = topRightVerticalEdge for col in range(7, -1, -1): for row in range(VScanDist): if gameState[row][col] == me: permanentPieceCount += 1 else: VScanDist = 0 break if VScanDist > 0: VScanDist -= 1 else: break TRHedgeCounted = True TRVedgeCounted = True if bottomLeftHorizontalEdge <= bottomLeftVerticalEdge and not BLHedgeCounted and not BLVedgeCounted: permanentPieceCount += bottomLeftVerticalEdge - bottomLeftHorizontalEdge HScanDist = bottomLeftHorizontalEdge for row in range(7, -1, -1): for col in range(HScanDist): if gameState[row][col] == me: permanentPieceCount += 1 else: HScanDist = 0 break if HScanDist > 0: HScanDist -= 1 else: break BLHedgeCounted = True BLVedgeCounted = True elif bottomLeftVerticalEdge <= bottomLeftHorizontalEdge and not BLVedgeCounted and not BLHedgeCounted: permanentPieceCount += bottomLeftHorizontalEdge - bottomLeftVerticalEdge VScanDist = bottomLeftVerticalEdge for col in range(8): for row in range(7, -VScanDist - 1, -1): if gameState[row][col] == me: permanentPieceCount += 1 else: VScanDist = 0 break if VScanDist > 0: VScanDist -= 1 else: break BLVedgeCounted = True BLHedgeCounted = True if bottomRightHorizontalEdge <= bottomRightVerticalEdge and not BRHedgeCounted and not BRVedgeCounted: permanentPieceCount += bottomRightVerticalEdge - bottomRightHorizontalEdge HScanDist = bottomRightHorizontalEdge for row in range(7, -1, -1): for col in range(7, -HScanDist -1, -1): if gameState[row][col] == me: permanentPieceCount += 1 else: HScanDist = 0 break if HScanDist > 0: HScanDist -= 1 else: break BRedgeCounted = True BLedgeCounted = True elif bottomRightVerticalEdge <= bottomRightHorizontalEdge and not BRHedgeCounted and not BRVedgeCounted: permanentPieceCount += bottomRightVerticalEdge - bottomRightHorizontalEdge VScanDist = bottomRightVerticalEdge for col in range(7, -1, -1): for row in range(VScanDist): if gameState[row][col] == me: permanentPieceCount += 1 else: VScanDist = 0 break if VScanDist > 0: VScanDist -= 1 else: break BRHedgeCounted = True BRVedgeCounted = True return permanentPieceCount def findShieldedPieces (self, gameState, me, opponent): """ PlayerBot.findShieldedPieces(self, gameState, me, opponent) Returns the number of pieces which cannot be flipped in the current gamestate. """ shieldedPiecesCount = 0 movesAvailableToOpponent = self.getAllValidMoves(gameState, me, opponent) for sRow in range(8): # sRow for searchRow, sCol for searchColumn for sCol in range(8): if gameState[sRow][sCol] == me: # Try to find a position on the board where the opponent could capture this piece. foundPossibleAttack = False for move in movesAvailableToOpponent: _, gameStateAfterMove = self.scoreMove(move, gameState, me, opponent) if gameStateAfterMove[sRow][sCol] != me: foundPossibleAttack = True if not foundPossibleAttack: shieldedPiecesCount += 1 return shieldedPiecesCount def isValidMove (self, row, col, me, opponent, gameState): """ PlayerBot.isValidMove(self, row, col, me, opponent, gamestate) Returns True if the given move is valid for the given gamestate and False if the given move is invalid for the given gamestate. """ if gameState[row][col] != self.bdCode: return False # If the space where we're trying to move isn't empty, we already know this move is invalid. scanningDirections = ((-1, 0), (0, 1), (1, 0), (0, -1), # A series of scanning vectors. (-1, -1), (-1, 1), (1, 1), (1, -1)) for SDRow, SDCol in scanningDirections: # Iterate over the scanning vectors. currentRow = row + SDRow # Start scanning at a position offset from the move by one currentCol = col + SDCol # along the current scanning vector. sawOpponent = False # The opponents gamepieces haven't yet been seen on this vector. while currentRow in range(0, 8) and currentCol in range(0, 8): if gameState[currentRow][currentCol] == self.bdCode: break # If the gamespace is empty, we know there are no pieces to flip on this vector. if gameState[currentRow][currentCol] == opponent: sawOpponent = True # The opponents gamepieces have been seen. if gameState[currentRow][currentCol] == me and sawOpponent: return True # There are at least pieceses on this vector that can be flipped. The move is valid. if gameState[currentRow][currentCol] == me and not sawOpponent: break # There are no pieces to flip along this vector. Proceed to the next. currentRow += SDRow # Proceed to the next gamespace in the current vector. currentCol += SDCol return False # If we've fallen out of the vector scanning loop, we know the move is invalid. def updateGameState (self): """ PlayerBot.updateGameState(self) Synchronizes the objects gameState attribute with the current state of parent.gameboard. """ for row in range(8): for col in range(8): # Iterate over the parents gameboard and insert integer values into self.gameState # corresponding to black pieces, white pieces and empty spaces. if self.parent.gameboard[row][col].GetBackgroundColour() == self.parent.bgAndBoardColor: self.gameState[row][col] = self.bdCode elif self.parent.gameboard[row][col].GetBackgroundColour() == self.parent.player1Color: self.gameState[row][col] = self.p1Code elif self.parent.gameboard[row][col].GetBackgroundColour() == self.parent.player2Color: self.gameState[row][col] = self.p2Code def scoreMove (self, possibleMove, gameState, me, opponent): """ PlayerBot.scoreMove (self, possibleMove, gameState, me, opponent) Calculate the number of pieces captured by a given move in a given game state and return a tuple containing the number of captures at index 0 and the state of the game after the move at index 1 """ gameState = gameState.copy() # We wouldn't want to alter the value of self.gameState now, would we? row, col = possibleMove # Unpack the move parameter to make the code more readable. moveScore = 1 # We already know that we at least have the grid space where we placed our piece. scanningDirections = ((-1, 0), (0, 1), (1, 0), (0, -1), # A series of scanning vectors (-1, -1), (-1, 1), (1, 1), (1, -1)) for SDRow, SDCol in scanningDirections: # Scann along all 8 vectors. currentRow = row + SDRow # Start at a position offset from the position of the move along the current currentCol = col + SDCol # scanning vector. sawOpponent = False # None of the opponents gamepieces have been seen on the current scanning vector at this time. canCountPieces = False # No row of my opponents pieces with another of my pieces at the other end has been seen on # on this scanning vector at this time. while currentRow in range(0, 8) and currentCol in range(0, 8): if gameState[currentRow][currentCol] == self.bdCode: break # If we see an empty space, we know we can't flip pieces on this vector. if gameState[currentRow][currentCol] == self.p1Code: sawOpponent = True if gameState[currentRow][currentCol] == me and sawOpponent: canCountPieces = True # We now know we can flip pieces on this vector. break # There is no need to continue scanning this vector. if gameState[currentRow][currentCol] == me and not sawOpponent: break # If I see another of my pieces without seeing an opponents piece, # there are no pieces to flip on this vector. currentRow += SDRow currentCol += SDCol currentRow = row + SDRow currentCol = col + SDCol while canCountPieces and currentRow in range(0, 8) and currentCol in range(0, 8): if gameState[currentRow][currentCol] == opponent: gameState[currentRow][currentCol] = me # Flip the pieces on this vector and increment the move score. moveScore += 1 elif gameState[currentRow][currentCol] == me: break currentRow += SDRow currentCol += SDCol return moveScore, gameState # Return the tuple class SelectDifficultyDialog (wx.Dialog): """ class SelectDifficultyDialog (wx.Dialog): __init__(self, parent) This object displays a dialog which prompts the user to set the difficulty using a slider. ShowModal returns wx.ID_OK if the user clicks the button labeled 'set difficulty' and wx.ID_CANCEL if the user closes the dialog. The getCurrentDifficulty method returns the difficulty selected by the user. """ ID_DIFFICULTY_SLIDER = wx.NewIdRef(1) # An ID constant for the difficulty slider used to bind a callback to motion of the slider. def __init__(self, parent): # Create all the widgets wx.Dialog.__init__(self, parent = parent, id = -1, title = "Please Select Difficulty") self.SetMinSize(wx.Size(400, 290)) self.prompt = wx.StaticText(self, -1, "Please Use the slider to select difficulty. The further to the right, the harder the game.") self.difficultyDescriptor = wx.StaticText(self, -1, "Game Difficulty: 75 - A little challenging") self.difficultySlider = wx.Slider(self, self.ID_DIFFICULTY_SLIDER, 75) self.okButton = wx.Button(self, wx.ID_OK, "Set Difficulty") # Insert all the widgets into a BoxSizer to lay them out neatly on the screen. self.layout = wx.BoxSizer(wx.VERTICAL) self.layout.Add(self.prompt, 1, wx.EXPAND) self.layout.Add(self.difficultyDescriptor, 1, wx.EXPAND) self.layout.Add(self.difficultySlider, 3, wx.EXPAND) self.layout.Add(self.okButton, 2, wx.EXPAND) self.SetSizer(self.layout) self.Fit() # Event bindings. For those who aren't familiar with wxPython, wx includes built in ID constants. # One of these was assigned to the button: wx.ID_OK. It wasn't created here. self.Bind(wx.EVT_COMMAND_SCROLL, self.diffSelectionChanged, id = self.ID_DIFFICULTY_SLIDER) self.Bind(wx.EVT_BUTTON, lambda evt: self.EndModal(wx.ID_OK), id = wx.ID_OK) self.Bind(wx.EVT_CLOSE, lambda evt: self.EndModal(wx.ID_CANCEL)) def diffSelectionChanged (self, event = None): """ SelectDifficultyDialog.diffSelectionChanged(self, event = None) This callback displays the selected difficulty in self.difficultyDescriptor, a StaticText widget along with a brief description of the difficulty currently selected. """ currentDifficulty = self.difficultySlider.GetValue() if currentDifficulty in range(0, 26): self.difficultyDescriptor.SetLabel("Game Difficulty: {} - Childs play".format(currentDifficulty)) elif currentDifficulty in range(25, 51): self.difficultyDescriptor.SetLabel("Game Difficulty: {} - My cat could do it.".format(currentDifficulty)) elif currentDifficulty in range(50, 76): self.difficultyDescriptor.SetLabel("Game Difficulty: {} - A little challenging".format(currentDifficulty)) elif currentDifficulty in range(75, 101): self.difficultyDescriptor.SetLabel("Game Difficulty: {} - Only you can win!".format(currentDifficulty)) else: self.difficultyDescriptor.SetLabel("Kyle, you have some debugging to do! Unexpected output: {}".format(currentDifficulty)) def getCurrentDifficulty (self): return self.difficultySlider.GetValue() class HelpWindow(wx.Dialog): """ A simple dialog class for displaying help information to the user. """ def __init__ (self, parent, helpText): wx.Dialog.__init__(self, parent, -1, helpText.split("\n")[0]) self.SetMinSize(wx.Size(400, 400)) self.topExitButton = wx.Button(self, wx.ID_CLOSE, "Close Help") self.helpDisplay = wx.TextCtrl(parent = self, id = wx.ID_ANY, value = helpText, style = wx.TE_MULTILINE | wx.TE_READONLY) self.bottomExitButton = wx.Button(self, wx.ID_CLOSE, "Close Help") self.layout = wx.BoxSizer(wx.VERTICAL) self.layout.Add(self.topExitButton, 1, wx.EXPAND) self.layout.Add(self.helpDisplay, 10, wx.EXPAND) self.layout.Add(self.bottomExitButton, 1, wx.EXPAND) self.SetSizer(self.layout) self.Fit() self.Bind(wx.EVT_BUTTON, self.closeHelp, id = wx.ID_CLOSE) def closeHelp(self, event = None): self.EndModal(wx.ID_OK) if __name__ == "__main__": app = wx.App() theApp = OthelloGameFrame(parent = None, id = wx.ID_ANY, size = (700, 800), title = "wxOthello") app.MainLoop()I think this is possibly my best bot yet; yes it's still a suicidal idiot but it does often make me think about what I'm doing, so I feel I'm definitely headed in the right direction. The issue is though that the bot is also taking its sweet time and it's blocking the event loop. I still don't understand threading very well. I would greatly appreciate it if any of you could point me in the direction of a good tutorial on the subject.