Apr-29-2019, 06:59 PM
It still makes some awfully dumb moves; it's far from perfect but this is the best I've been able to do so far going to minimax route. It beat me once and it was able to draw a game against me. Unfortunately, with Othello, I think this is as far as I think I can go using minimax. Despite its downsides; like knowing your ML code is buggy only after you spend countless hours training it only to find that it's as stupid as when you started training it; I think it's the only real way to make a bot that consistently wins against a Human opponent.
My code:
My code:
class PlayerBot:
.
.
.
def miniMax (self, gameState, depth, alpha, beta, maximizingPlayer):
"""
PlayerBot.miniMax(self, gameState, depth, alpha, beta, maximizingPlayer)
An implementation of the recursive miniMax algorithm with alpha-beta pruning.
This method returns the tuple (terminalScore, bestMove) where terminalScore is a value
used internally by the recursive algorithm and bestMove is the best move given the game state
passed to this method in its initial call. The parameter gameState is the state of the game
to be evaluated. The depth parameter is the maximizum recursion depth, alpha and beta are
passed initial values of infinity and negative infinity and maximizingPlayer should be passed
an initial value of True.
"""
# If the game reaches a terminal state or maximum recursion depth is reached, return a static evaluation of the final game state with the placeholder value (0, 0).
if depth == 0 or (not self.getAllValidMoves(gameState, self.p2Code, self.p1Code) and not self.getAllValidMoves(gameState, self.p1Code, self.p2Code)):
return self.scoreGameState(gameState, maximizingPlayer), (0, 0)
if maximizingPlayer: # - simulating a move by the bot
allValidMoves = self.getAllValidMoves(gameState, self.p2Code, self.p1Code)
maxScore = -inf
if not allValidMoves: # Handle the case of the bot losing its turn to the player.
return self.miniMax(gameState, depth - 1, alpha, beta, False)
bestMove = [ allValidMoves[0] ] # Select randomly from all moves with the highest terminal evaluation. This adds an element of unpredictability.
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 # alpha-beta cutoff
if moveScore > maxScore:
maxScore = moveScore
bestMove = [ move ]
elif moveScore == maxScore:
bestMove.append(move)
return maxScore, bestMove[random.randint(0, len(bestMove) - 1)]
else: # Minimizing player - simulating a move by the player
allValidMoves = self.getAllValidMoves(gameState, self.p1Code, self.p2Code)
minScore = inf
if not allValidMoves: # Handle the case of the player losing a turn to the bot.
return self.miniMax(gameState, depth - 1, alpha, beta, True)
bestMove = [ allValidMoves[0] ] # Select randomly from all moves with the lowest terminal evaluation. This adds an element of unpredictability.
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 # alpha-beta cutoff
if moveScore < minScore:
minScore = moveScore
bestMove = [ move ]
elif moveScore == minScore:
bestMove.append(move)
return minScore, bestMove[random.randint(0, len(bestMove) - 1)]
.
.
.
def scoreGameState (self, gameState, isBotsTurn):
"""
PlayerBot.scoreGameState(self, gameState, isBotsTurn)
Used by the minMax algorithm to score a game state using a series of heuristics to
compute the probability of the bot winning and return it as a floating point value
between 0 and 1.
"""
# This is a probability based scoring heuristic; one designed to calculate the probability
# of the bot winning rather than assigning arbitrary score values to various strategic successes
# and failures.
positionalScoringMap = ((0.25,-0.2,0,0,0,0,-0.2,0.25),
(-0.2,-0.25,0,0,0,0,-0.25,-0.2),
(0,0,0,0,0,0,0,0),
(0,0,0,0,0,0,0,0),
(0,0,0,0,0,0,0,0),
(0,0,0,0,0,0,0,0),
(-0.2,-0.25,0,0,0,0,-0.25,-0.2),
(0.25,-0.2,0,0,0,0,-0.2,0.25))
score = 0.5
me = self.p2Code
ILostMyTurn = False
oppLostTheirTurn = False
opponent = self.p1Code
myValidMoves = self.getAllValidMoves(gameState, me, opponent)
oppValidMoves = self.getAllValidMoves(gameState, opponent, me)
# A dictionary which stores the weights of all strategic variables on the probability of the bot winning.
# These aren't probabilities; they get converted into probabilities by the following logic
probDict = {
"shieldedPieces": 0.03,
"permanentPieces": 0.125,
"moveLost": -0.04,
}
if not myValidMoves:
if not oppValidMoves:
# The game is in a terminal state. If the bot won, return 1.0 for a 100% probability of
# winning and if the player won, return 0.0 for a 0% probability of the bot winning.
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
if myScore > oppScore:
return 1.0
elif myScore == oppScore:
return 0.5
else:
return 0.0
else:
# The bot has lost a turn to its opponent. It made a bad move.
ILostMyTurn = True
if not oppValidMoves: oppLostTheirTurn = True
if ILostMyTurn:
if isBotsTurn:
score += probDict["moveLost"]
elif oppLostTheirTurn:
if not isBotsTurn:
score -= probDict["moveLost"]
# Count up the positional scores for black and white tiles, add them to the sore if they're the
# bots tiles and subtract if they're the players tiles.
for row in range(8):
for col in range(8):
if gameState[row][col] == me:
score += positionalScoringMap[row][col]
if gameState[row][col] == opponent:
score -= positionalScoringMap[row][col]
score += self.findShieldedPieces(gameState, me, opponent) * probDict["shieldedPieces"]
score += self.findPermanentPieces(gameState, me, opponent) * probDict["permanentPieces"]
score -= self.findShieldedPieces(gameState, opponent, me) * probDict["shieldedPieces"]
score -= self.findPermanentPieces(gameState, opponent,me) * probDict["permanentPieces"]
return score
.
.
.
def findPermanentPieces (self, gameState, me, opponent): # TODO Complete this algorithm.
"""
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
# The previous algorithm I implemented produced wildly inaccurate numbers and counted permanent pieces that weren't there.
# I'll come back to this puzzle, but for now, the work of counting all the pieces that are on an edge and protected by a
# filled corner has already been halfway done. Let's just return that figure for now.
if topLeftHorizontalEdge != 8:
topEdge = topLeftHorizontalEdge + topLeftVerticalEdge
else:
topEdge = 8
if topLeftVerticalEdge != 8:
leftEdge = topLeftVerticalEdge + bottomLeftVerticalEdge
else:
leftEdge = 8
if topRightVerticalEdge != 8:
rightEdge = topRightVerticalEdge + bottomRightVerticalEdge
else:
rightEdge = 8
if bottomLeftHorizontalEdge != 8:
bottomEdge = bottomLeftHorizontalEdge + bottomRightHorizontalEdge
else:
bottomEdge = 8
# Add up all the edges:
permanentPieceCount += topEdge + leftEdge + rightEdge + bottomEdge
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
.
.
.
.I really want to us ML to make this bot now, but I have no idea where to start. As always, thank you for all your help. The bot wouldn't even have come this far without the advice I've received.