Python Project on Artificial Intelligence Alpha Beta pruning Algorithm
#!/usr/bin/python3
### CSCI-B 351 / COGS-Q 351 Fall 2021
### Framework code copyright 2020 B351/Q351 instruction team.
### Do not copy or redistribute this code without permission
### and do not share your solutions outside of this class.
### Doing so constitutes academic misconduct and copyright infringement.
import math
import random
from board import Board
class BasePlayer:
def __init__(self, max_depth):
self.max_depth = max_depth
##################
# TODO #
##################
# Assign integer scores to the three terminal states
# P2_WIN_SCORE < TIE_SCORE < P1_WIN_SCORE
# Access these with "self.TIE_SCORE", etc.
P1_WIN_SCORE = 100
P2_WIN_SCORE = -100
TIE_SCORE = 0
# Returns a heuristic for the board position
# Good positions for 0 pieces should be positive and
# good positions for 1 pieces should be negative
# for all boards, P2_WIN_SCORE < heuristic(b) < P1_WIN_SCORE
def heuristic(self, board):
'''
URL: https://www.researchgate.net/publication/261452468_Exploration_and_analysis_of_the_evolution_of_strategies_for_Mancala_variants
Help was taken from this url was used to understand relevant heuristics that can be used to reflect the "goodness" of the game.
score: Heuristic score.
Heuristics
H1: Keep as many seeds on the players own side
H2: To check how late into the game it is we will check
remaining moves possible from which to choose
H3: Maximise the amount of seeds in a players own store
'''
score = 0
p1_possible_moves = []
p2_possible_moves = []
if not board.game_over: # check if game is not over
H1 = sum(board.p1_pits) - sum(board.p2_pits)
for i in range(len(board.p1_pits)):
if board.p1_pits[i] != 0:
p1_possible_moves.append(board.p1_pits[i])
for i in range(len(board.p2_pits)):
if board.p2_pits[i] != 0:
p2_possible_moves.append(board.p2_pits[i])
H2 = len(p1_possible_moves) - len(p2_possible_moves)
H3 = board.p1_pot - board.p2_pot
score = 100 * ((1/3 * H1) + (1/3 * H2) + (1/3 * H3))
else: # otherwise if game is over
if board.winner == 0: # if player 1 wins the game
score = self.P1_WIN_SCORE
elif board.winner == 1: # if player 2 wins the game
score = self.P2_WIN_SCORE
else:
score = self.TIE_SCORE # if the game ends in a draw
return score
# You are not expected to implement anything here.
def findMove(self, trace):
raise NotImplementedError
class ManualPlayer(BasePlayer):
def __init__(self, max_depth=None):
BasePlayer.__init__(self, max_depth)
def findMove(self, trace):
board = Board(trace)
opts = " "
for c in range(6):
opts += " "+(str(c+1) if board.isValidMove(c) else ' ')+" "
while True:
if(board.turn == 0):
print("\n")
board.printSpaced()
print(opts)
pit = input("Pick a pit (P1 side): ")
else:
print("\n")
print(" " + opts[::-1])
board.printSpaced()
pit = input("Pick a pit (P2 side): ")
try: pit = int(pit) - 1
except ValueError: continue
if board.isValidMove(pit):
return pit
class RandomPlayer(BasePlayer):
def __init__(self, max_depth=None):
BasePlayer.__init__(self, max_depth)
self.random = random.Random(max_depth)
def findMove(self, trace):
board = Board(trace)
options = list(board.getAllValidMoves())
return self.random.choice(options)
class RemotePlayer(BasePlayer):
def __init__(self, max_depth=None):
BasePlayer.__init__(self, max_depth)
self.instructor_url = "http://silo.cs.indiana.edu:30005"
if self.max_depth > 8:
print("It refused to go that hard. Sorry.")
self.max_depth = 8
def findMove(self, trace):
import requests
r = requests.get(f'{self.instructor_url}/getmove/{self.max_depth},{trace}')
move = int(r.text)
return move
class PlayerMM(BasePlayer):
##################
# TODO #
##################
# performs minimax on board with depth.
# returns the best move and best score as a tuple
def minimax(self, board, depth):
# return null move and score for board's terminal state
# when game is over
if board.game_over == True:
move = 0
if board.winner == 0:
score = self.P1_WIN_SCORE
elif board.winner == 1:
score = self.P2_WIN_SCORE
else: # in case of tie
score = self.TIE_SCORE
return move, score
# return a null move and the heuristic value for board
# when non-end state and depth = 0
if depth == 0:
move = 0
score = self.heuristic(board)
return move, score
if board.turn == 0: # turn of maximising player
score = -math.inf
moves = board.getAllValidMoves()
for move in moves:
board = board.makeMove(move)
b_move, score = move, max(score, self.minimax(board, depth - 1))
board = board.undoMove()
return b_move, score
else: # turn of minimising player
score = math.inf
moves = board.getAllValidMoves()
for move in moves:
board = board.makeMove(move)
b_move, score = move, min(score, self.minimax(board, depth - 1))
board = board.undoMove()
return b_move, score
def findMove(self, trace):
board = Board(trace)
move, score = self.minimax(board, self.max_depth)
return move
class PlayerAB(BasePlayer):
##################
# TODO #
##################
# performs minimax with alpha-beta pruning on board with depth.
# alpha represents the score of max's current strategy
# beta represents the score of min's current strategy
# in a cutoff situation, return the score that resulted in the cutoff
# returns the best move and best score as a tuple
def alphaBeta(self, board, depth, alpha, beta):
# return null move and score for board's terminal state
# when game is over
if board.game_over:
move = 0
if board.winner == 0:
score = self.P1_WIN_SCORE
elif board.winner == 1:
score = self.P2_WIN_SCORE
else: # in case of tie
score = self.TIE_SCORE
return move, score
# return a null move and the heuristic value for board
# when non-end state and depth = 0
if depth == 0:
move = 0
score = self.heuristic(board)
return move, score
if board.turn == 0: # turn of maximising player
score = -math.inf
moves = board.getAllValidMoves()
for move in moves:
board = board.makeMove(move)
b_move, score = b_move, max(score, self.alphaBeta(board, depth - 1, alpha, beta))
if score >= beta:
break # beta cutoff
alpha = max(alpha, score)
return b_move, score
else:
score = math.inf
moves = board.getAllValidMoves()
for move in moves:
board = board.makeMove(move)
b_move, score = b_move, min(score, self.alphaBeta(board, depth - 1, alpha, beta))
if score <= alpha:
break # alpha cutoff
beta = min(beta, score)
return b_move, score
def findMove(self, trace):
board = Board(trace)
move, score = self.alphaBeta(board, self.max_depth, -math.inf, math.inf)
return move
class PlayerDP(PlayerAB):
''' A version of PlayerAB that implements dynamic programming
to cache values for its heuristic function, improving performance. '''
def __init__(self, max_depth):
PlayerAB.__init__(self, max_depth)
self.resolved = {}
##################
# TODO #
##################
# if a saved heuristic value exists in self.resolved for board.state, returns that value
# otherwise, uses BasePlayer.heuristic to get a heuristic value and saves it under board.state
def heuristic(self, board: Board):
if board.state in self.resolved.keys():
return self.resolved.get(str(board.state))
else:
score = BasePlayer.heuristic(board)
self.resolved{str(board.state)} = score
return score
class PlayerBonus(BasePlayer):
''' This class is here to give you space to experiment for your ultimate Mancala AI,
your one and only PlayerBonus. This is only used for the extra credit tournament. '''
def findMove(self, trace):
raise NotImplementedError
#######################################################
###########Example Subclass for Testing
#######################################################
# This will inherit your findMove from above, but will override the heuristic function with
# a new one; you can swap out the type of player by changing X in "class TestPlayer(X):"
class TestPlayer(BasePlayer):
# define your new heuristic here
def heuristic(self):
pass
