I've implemented some player action prediction in the bot and 2 algorithms designed to limit the players options to only the worst available to them. The problem is the bot is completely unable to set traps in the corners and create safe entrances to the corners for itself. I'm somewhat at a loss as to how to make it do these things algorithmically. The situation basically amounts to the bot sucks at endgame strategies. Any advice?
This is my PlayerBot class as it is currently. I think this is the final hurdle. The class now contains a suite of methods for getting information about the game state.
This is my PlayerBot class as it is currently. I think this is the final hurdle. The class now contains a suite of methods for getting information about the game state.
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 """ # These nested lists map various levels of desirability to different areas of the gameboard # where positive numbers indicate higher levels of desirability and negative numbers indicate # varying levels of undesirability. The larger the numbers absolute value, the more desirable/ # undesirable that area of the gameboard. priorityMap = [[200, -200, 99, 80, 80, 99, -200, 200], [-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], [200, -200, 99, 80, 80, 99, -200, 200]] 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 def __init__ (self, parent, difficulty): self.parent = parent self.difficulty = difficulty self.gameState = self.getInitialGameState() 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 = [] # Create a list of all valid moves available to the bot. for row in range(8): for col in range(8): if self.isValidMove(row, col, self.p2Code, self.p1Code, self.gameState): validMoves.append( (row, col) ) 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. strategicMoves = [ validMoves[0] ] for move in validMoves: if self.priorityMap[move[0]][move[1]] > self.priorityMap[strategicMoves[0][0]][strategicMoves[0][1]]: strategicMoves = [ move ] elif self.priorityMap[move[0]][move[1]] == self.priorityMap[strategicMoves[0][0]][strategicMoves[0][1]]: strategicMoves.append(move) profitableMoves = [strategicMoves[0]] player2Gain, gameStateAfterMove = self.scoreMove(strategicMoves[0], self.gameState, self.p2Code, self.p1Code) player1Gain = self.getMaxPlayer1Gain(gameStateAfterMove) currentBestKnownNetGain = player2Gain - player1Gain # Create a list of all the moves which produce the largest net gain assuming player 1 makes a move that captures the # most pieces possible during the next move. for move in strategicMoves: player2Gain, gameStateAfterMove = self.scoreMove(move, self.gameState, self.p2Code, self.p1Code) player1Gain = self.getMaxPlayer1Gain(gameStateAfterMove) if player2Gain - player1Gain > currentBestKnownNetGain: profitableMoves = [ move ] elif player2Gain - player1Gain == currentBestKnownNetGain: profitableMoves.append(move) # Find moves which limit or completely eliminate player 1 options on the next move. Add them to bestMoves and make any # move that completely eliminates player 1 options. movesLimitingP1Opt = [] for move in profitableMoves: _, gameStateAfterMove = self.scoreMove(move, self.gameState, self.p2Code, self.p1Code) if self.countPlayer1Options(gameStateAfterMove) == 2: movesLimitingP1Opt.append(move) elif self.countPlayer1Options(gameStateAfterMove) <= 1: self.parent.gameboardButtonClicked(row = move[0], col = move[1]) return # Try to make a move that eliminates options available to player 1: if len(movesLimitingP1Opt) != 0: randomMove = movesLimitingP1Opt[random.randint(0, len(movesLimitingP1Opt) - 1)] self.parent.gameboardButtonClicked(row = randomMove[0], col = randomMove[1]) return # Create a list of all the moves which produce a larger strategic gain for player 2 than for player 1 from all the moves # in profitableMoves. bestMoves = [] for move in profitableMoves: player2Gain = self.priorityMap[move[0]][move[1]] _, gameStateAfterMove = self.scoreMove(move, self.gameState, self.p2Code, self.p1Code) player1Gain = self.getMaxPlayer1StrategicGain(gameStateAfterMove) if player2Gain > player1Gain: bestMoves.append(move) # Select randomly from the best moves available and make that move. if len(bestMoves) != 0: # In this case, at least one move that produces a strategic gain for the bot is available. randomMove = bestMoves[random.randint(0, len(bestMoves) - 1)] self.parent.gameboardButtonClicked(row = randomMove[0], col = randomMove[1]) # In this case, no move that produces a strategic gain for the bot is available. else: randomMove = strategicMoves[random.randint(0, len(strategicMoves) - 1)] self.parent.gameboardButtonClicked(row = randomMove[0], col = randomMove[1]) else: # Make a 'mistake'. randomMove = validMoves[random.randint(0, len(validMoves) - 1)] self.parent.gameboardButtonClicked(row = randomMove[0], col = randomMove[1]) self.updateGameState() def getMaxPlayer1StrategicGain (self, gameState): """ PlayerBot.getMaxPlayer1StrategicGain(self, gameState) Given the state passed as gameState, returns the maximum strategic gain, accurding to PlayerBot.priorityMap available to player 1 if they should make a move. """ maxStrategicGain = -300 for row in range(8): for col in range(8): if self.isValidMove(row, col, self.p1Code, self.p2Code, gameState): if self.priorityMap[row][col] > maxStrategicGain: maxStrategicGain = self.priorityMap[row][col] return maxStrategicGain def countPlayer1Options (self, gameState): validMoveCount = 0 for row in range(8): for col in range(8): if self.isValidMove(row, col, self.p1Code, self.p2Code, gameState): validMoveCount += 1 return validMoveCount 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 def getMaxPlayer1Gain (self, gameState): """ PlayerBot.getMaxPlayer1Gain(self, gameState) Returns an integer corresponding to the maximum number of captures player 1 can achieve if they make a move in the given gamestate. """ validMoves = [] # Identify all the valid moves and store them in a list of tuples. for row in range(8): for col in range(8): if self.isValidMove(row, col, self.p1Code, self.p2Code, gameState): validMoves.append( (row, col) ) if validMoves == []: # If there are no moves available to player 1, player 1 cannot capture any pieces. return 0 strategicMoves = [ validMoves[0] ] # Narrow the list of possible moves to those of strategic value. Player 1 isn't likely to for move in validMoves: # deliberately throw the game and the bot does stupid things when it considers the possibility # that they would. if self.priorityMap[move[0]][move[1]] > self.priorityMap[strategicMoves[0][0]][strategicMoves[0][1]]: strategicMoves = [ move ] elif self.priorityMap[move[0]][move[1]] == self.priorityMap[strategicMoves[0][0]][strategicMoves[0][1]]: strategicMoves.append(move) maxGain = 0 for move in strategicMoves: # Identify the move that captures the most pieces and return the number of pieces captured. if self.scoreMove(move, gameState, self.p1Code, self.p2Code)[0] > maxGain: maxGain = self.scoreMove(move, gameState, self.p1Code, self.p2Code)[0] return maxGainIf we can perfect the bots endgame, we may be able to create a bot that plays a perfect game at max difficulty; one guaranteed to end either in a draw or a win for the bot. As always, any help will be greatly appreciated.