import random import turtle import math import copy """ Othello - Python Turtle Graphics Non-human player uses negamax to determine its next move. Auther: ... Date: 25th May 2014 """ #initialiseBoard(n) returns the initial board for an Othello game of size n. def initialiseBoard(n): board = [[0 for c in range(n)] for r in range(n)] low = int(n/2 -1) high = int(n/2) board[low][low] = 1 board[low][high] = -1 board[high][low] = -1 board[high][high] = 1 drawBoard(board) updateBoard(board,low,low,1) updateBoard(board,low,high,-1) updateBoard(board,high,low,-1) updateBoard(board,high,high,1) return board #drawBoard(b) displays the board b on the screen using turtle graphics. def drawBoard(b): size = len(b) tile = 50 turtle.setup(size * tile + 1*tile, size * tile + 1*tile) turtle.screensize(size * tile, size * tile) turtle.bgcolor('sienna') turtle.title("Othello") boarddrawer = turtle.Turtle() boarddrawer.penup() boarddrawer.speed(0) boarddrawer.hideturtle() boarddrawer.color("black", "forest green") boarddrawer.setposition(-size*tile/2,-size*tile/2) boarddrawer.begin_fill() for k in range(4): boarddrawer.pendown() boarddrawer.forward(tile*size) boarddrawer.left(90) boarddrawer.end_fill() for i in range(size+1): boarddrawer.setposition(-size*tile/2,tile*i-size*tile/2) boarddrawer.pendown() boarddrawer.forward(tile*size) boarddrawer.penup() boarddrawer.left(90) for j in range(size+1): boarddrawer.setposition(tile*j-size*tile/2,-size*tile/2) boarddrawer.pendown() boarddrawer.forward(tile*size) boarddrawer.penup() for l in range(size): boarddrawer.setposition(tile*(-size/2-1/10),tile*(l-size/2+1/3)) boarddrawer.pendown() boarddrawer.write(l, align ='right' , font=("Arial", 10, "normal")) boarddrawer.penup() boarddrawer.setposition(tile*(size/2+1/8),tile*(l-size/2+1/3)) boarddrawer.pendown() boarddrawer.write(l, font=("Arial", 10, "normal")) boarddrawer.penup() for m in range(size): boarddrawer.setposition(tile*(m-size/2+1/3),tile*(-size/2-1/3)) boarddrawer.pendown() boarddrawer.write(m, font=("Arial", 10, "normal")) boarddrawer.penup() boarddrawer.setposition(tile*(m-size/2+1/3),tile*(size/2)) boarddrawer.pendown() boarddrawer.write(m, font=("Arial", 10, "normal")) boarddrawer.penup() #updateBoard(b) updates the piece at a given r, c by colour p on board b. def updateBoard(b, r, c, p): size = len(b) tile = 50 piecedrawer = turtle.Turtle() piecedrawer.speed(0) piecedrawer.hideturtle() piecedrawer.penup() piecedrawer.setposition(tile*(c-size/2+1/2),tile*(r-size/2+1/10)) piecedrawer.pendown() if p == 1: piecedrawer.color("black", "black") if p == -1: piecedrawer.color("white", "white") piecedrawer.begin_fill() piecedrawer.circle(tile*4/10, steps = 100) piecedrawer.end_fill() if p == 1: piecedrawer.color("white", "white") if p == -1: piecedrawer.color("black", "black") piecedrawer.penup() piecedrawer.setposition(tile*(c-size/2+4/9),tile*(r-size/2+1/3)) piecedrawer.pendown() piecedrawer.write(abs(b[r][c]), font=("Arial", 10, "normal")) #move(b, m, p) updates the board b with all effects of the move m by player p, and it also updates the screen accordingly. def move(b, m, p, simulation=False): #can remove if simulation: move.counter += 1 new = b new[m[0]][m[1]] = p if not simulation: updateBoard(new,m[0],m[1],p) for i in range(len(m[2])): count = 1 while b[m[0]+m[2][i][0]*count][m[1]+m[2][i][1]*count]*p < 0: new[m[0]+m[2][i][0]*count][m[1]+m[2][i][1]*count] = p*abs(b[m[0]+m[2][i][0]*count][m[1]+m[2][i][1]*count]) + p if not simulation: updateBoard(new,m[0]+m[2][i][0]*count,m[1]+m[2][i][1]*count, p) count += 1 return new #legalDirection(r, c, b, p, u, v) returns True if a piece placed by player p on square (r, c) on board b would capture any pieces in the direction (u, v). def legalDirection(r, c, b, p, u, v): direction = [] size = len(b) count = 1 while 0 <= r+u*count and r+u*count < size and 0 <= c+v*count and c+v*count < size: direction.append(b[r+u*count][c+v*count]) count += 1 check = 0 for i in range(len(direction)): if p == 1: if direction[i] > 0 and check == 1: return True if direction[i] >= 0: return False if direction[i] < 0: check = 1 if p == -1: if direction[i] < 0 and check == 1: return True if direction[i] <= 0: return False if direction[i] > 0: check = 1 return False #legalMove(r, c, b, p) returns the list of directions in which a piece placed by player p on square (r, c) on board b would capture. def legalMove(r, c, b, p): legal = [] for i in range(-1,2): for j in range(-1,2): if i != 0 or j !=0: if legalDirection(r, c, b, p, i, j) and b[r][c] == 0: legal.append((i, j)) return legal #moves(b, p) returns the list of legal moves for player p on board b. def moves(b, p): moves = [] for r in range(len(b)): for c in range(len(b)): if len(legalMove(r, c, b, p)) > 0: moves.append((r, c, legalMove(r, c, b, p))) return moves #selectMove(ms, b, p) returns a move selected from the list ms for player p on board b. def selectMove(ms, b, p, horizon=False): move.counter= 0 value, bmoves = negamax(b, 4.9, -1e8, 1e8, p) pieces = sum([1 if c != 0 else 0 for r in b for c in r]) bonus = 2 while move.counter < 500 and bonus <= 6 and pieces > 0.5*len(b)*len(b) : move.counter= 0 value, bmoves = negamax(b, 4.9 + bonus, -1e8, 1e8, p) bonus += 2 fmt = 'Player {:2} utility: {:8g} {:4} moves' print (fmt.format(p,value,move.counter)) return random.choice(bmoves) #heuristics(board) returns the value of a game state. def heuristic(board, turn): #edgecase, checking for victory. if len(moves(board, 1)) == 0 and len(moves(board, -1)) == 0: b , w = scoreBoard(board) if b > w: return 1000000 elif b < w: return -1000000 else: return 0 #gives early game priority to sides and corners, with late game priority on score. #gives priority to sides which you own a corner to. value = 0 n = len(board) for r in range(n): for c in range(n): bvalue = 0 if r == 0 or r == n-1: bvalue += 40*math.log10(n*n/turn) if board[r][0] == 1 and board[r][c] > 0 or board[r][0] == -1 and board[r][c] < 0: bvalue *= 3/2 if board[r][n-1] == 1 and board[r][c] > 0 or board[r][n-1] == -1 and board[r][c] < 0: bvalue *= 3/2 if c == 0 or c == n-1: bvalue += 40*math.log10(n*n/turn) if board[0][c] == 1 and board[r][c] > 0 or board[0][c] == -1 and board[r][c] < 0: bvalue *= 3/2 if board[n-1][c] == 1 and board[r][c] > 0 or board[n-1][c] == -1 and board[r][c] < 0: bvalue *= 3/2 bvalue += abs(board[r][c]*turn/n/n) if board[r][c] > 0: value += bvalue if board[r][c] < 0: value -= bvalue return value #negamax(board, depth, alpha, beta, colour) returns the best value moves. Based off heuristic. def negamax(board, depth, alpha, beta, colour): turn = 0 for r in board: for c in r: if c != 0: turn += 1 if depth < 1 or turn == len(board)*len(board) or move.counter > 4000: return (colour * heuristic(board, turn), []) ms = moves(board, colour) if len(ms) == 0: val = -negamax(board, depth - 0.1, -beta, -alpha, -colour)[0] return (val, []) best = -1e8 bmoves = [] for m in ms: child = copy.deepcopy(board) move(child, m, colour, True) val = -negamax(child, depth - 1, -beta, -alpha, -colour)[0] if val > best: bmoves.clear() bmoves.append(m) if val == best: bmoves.append(m) best = max(best, val) alpha = max(alpha, val) if alpha >= beta: break return (best, bmoves) #scoreBoard(b) returns a pair holding the scores for Black and White on board b. def scoreBoard(b): black = 0 white = 0 size = len(b) for r in range(size): for c in range(size): if b[r][c] > 0: black +=b[r][c] if b[r][c] < 0: white +=b[r][c] return (black, abs(white)) #game(board, human) plays the game with 'human' number of players. def game(board, human): game.player = 0 if human == 1: game.player = int(turtle.numinput('Colour','Select a colour to play as (1 for black, -1 for white): ', 0, minval=-1, maxval=1)) game.colour = 1 game.skip = 0 game.pieces = 4 #getGridPosition(x, y) returns the clicked tile relavtive to the x and y postion of the mouse when clicked. def getGridPosition(x, y): click = [0, 0] for i in range(len(board)): if i*50-len(board)*50/2 < x and x < i*50+50-len(board)*50/2: click[1] = i for j in range(len(board)): if j*50-len(board)*50/2 < y and y < j*50+50-len(board)*50/2: click[0] = j return click #pc() plays a turn for the computer. def pc(): m = selectMove(moves(board, game.colour), board, game.colour) move(board, m, game.colour) game.colour *= -1 game.pieces += 1 #user() plays a turn for the player. def user(x, y): user.x = x user.y = y def playmaker(): row, col = getGridPosition(user.x, user.y) for i in moves(board, game.colour): if i[0] == row and i[1] == col: move(board, i, game.colour) game.colour *= -1 game.pieces += 1 break return playmaker #updateTitle() updates the title. def updateTitle(): if game.colour == 1: turn = 'Black' else: turn = 'White' turtle.title(turn + "'s Turn Black: " + str(scoreBoard(board)[0]) + " / White: " + str(scoreBoard(board)[1])) #updateGame() runs the game. Has checks for finished game. def updateGame(action=pc): if game.pieces < len(board)*len(board): if game.skip == 2: turtle.title("Final Score Black: " + str(scoreBoard(board)[0]) + " / White: " + str(scoreBoard(board)[1])) return if len(moves(board, game.colour)) != 0: game.skip = 0 action() else: game.skip += 1 game.colour *= -1 updateTitle() if game.colour == game.player or human == 2: turtle.onscreenclick(play) else: turtle.ontimer(updateGame) else: turtle.title("Final Score Black: " + str(scoreBoard(board)[0]) + " / White: " + str(scoreBoard(board)[1])) #play(x, y) turns off the click event and does the players turn. def play(x, y): turtle.onscreenclick(None) updateGame(user(x, y)) updateTitle() if game.colour == game.player or human == 2: turtle.onscreenclick(play) else: turtle.ontimer(updateGame) #main() prompts the user for the board-size, and number of player. def main(): n = 1 while n % 2 != 0: n = int(turtle.numinput('Board Size','Please enter the nxn board size(must be an even number): ', 8, minval=4, maxval=12)) human = int(turtle.numinput('Player','Number of human players: ', 0, minval=0, maxval=2)) board = initialiseBoard(n) game(board, human) turtle.done() #runs in terminal. if __name__ == '__main__': main()