# Reversi/Othello Board Game using Minimax and Alpha-Beta Pruning # https://en.wikipedia.org/wiki/Reversi # https://en.wikipedia.org/wiki/Computer_Othello # https://en.wikipedia.org/wiki/Minimax # https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning # https://en.wikipedia.org/wiki/Negamax # https://en.wikipedia.org/wiki/Principal_variation_search # FB36 - 20160831 import os, copy n = 8 # board size (even) board = [['0' for x in range(n)] for y in range(n)] # 8 directions dirx = [-1, 0, 1, -1, 1, -1, 0, 1] diry = [-1, -1, -1, 0, 0, 1, 1, 1] def InitBoard(): if n % 2 == 0: # if board size is even z = (n - 2) / 2 board[z][z] = '2' board[n - 1 - z][z] = '1' board[z][n - 1 - z] = '1' board[n - 1 - z][n - 1 - z] = '2' def PrintBoard(): m = len(str(n - 1)) for y in range(n): row = '' for x in range(n): row += board[y][x] row += ' ' * m print row + ' ' + str(y) print row = '' for x in range(n): row += str(x).zfill(m) + ' ' print row + '\n' def MakeMove(board, x, y, player): # assuming valid move totctr = 0 # total number of opponent pieces taken board[y][x] = player for d in range(8): # 8 directions ctr = 0 for i in range(n): dx = x + dirx[d] * (i + 1) dy = y + diry[d] * (i + 1) if dx < 0 or dx > n - 1 or dy < 0 or dy > n - 1: ctr = 0; break elif board[dy][dx] == player: break elif board[dy][dx] == '0': ctr = 0; break else: ctr += 1 for i in range(ctr): dx = x + dirx[d] * (i + 1) dy = y + diry[d] * (i + 1) board[dy][dx] = player totctr += ctr return (board, totctr) def ValidMove(board, x, y, player): if x < 0 or x > n - 1 or y < 0 or y > n - 1: return False if board[y][x] != '0': return False (boardTemp, totctr) = MakeMove(copy.deepcopy(board), x, y, player) if totctr == 0: return False return True minEvalBoard = -1 # min - 1 maxEvalBoard = n * n + 4 * n + 4 + 1 # max + 1 def EvalBoard(board, player): tot = 0 for y in range(n): for x in range(n): if board[y][x] == player: if (x == 0 or x == n - 1) and (y == 0 or y == n - 1): tot += 4 # corner elif (x == 0 or x == n - 1) or (y == 0 or y == n - 1): tot += 2 # side else: tot += 1 return tot # if no valid move(s) possible then True def IsTerminalNode(board, player): for y in range(n): for x in range(n): if ValidMove(board, x, y, player): return False return True def GetSortedNodes(board, player): sortedNodes = [] for y in range(n): for x in range(n): if ValidMove(board, x, y, player): (boardTemp, totctr) = MakeMove(copy.deepcopy(board), x, y, player) sortedNodes.append((boardTemp, EvalBoard(boardTemp, player))) sortedNodes = sorted(sortedNodes, key = lambda node: node[1], reverse = True) sortedNodes = [node[0] for node in sortedNodes] return sortedNodes def Minimax(board, player, depth, maximizingPlayer): if depth == 0 or IsTerminalNode(board, player): return EvalBoard(board, player) if maximizingPlayer: bestValue = minEvalBoard for y in range(n): for x in range(n): if ValidMove(board, x, y, player): (boardTemp, totctr) = MakeMove(copy.deepcopy(board), x, y, player) v = Minimax(boardTemp, player, depth - 1, False) bestValue = max(bestValue, v) else: # minimizingPlayer bestValue = maxEvalBoard for y in range(n): for x in range(n): if ValidMove(board, x, y, player): (boardTemp, totctr) = MakeMove(copy.deepcopy(board), x, y, player) v = Minimax(boardTemp, player, depth - 1, True) bestValue = min(bestValue, v) return bestValue def AlphaBeta(board, player, depth, alpha, beta, maximizingPlayer): if depth == 0 or IsTerminalNode(board, player): return EvalBoard(board, player) if maximizingPlayer: v = minEvalBoard for y in range(n): for x in range(n): if ValidMove(board, x, y, player): (boardTemp, totctr) = MakeMove(copy.deepcopy(board), x, y, player) v = max(v, AlphaBeta(boardTemp, player, depth - 1, alpha, beta, False)) alpha = max(alpha, v) if beta <= alpha: break # beta cut-off return v else: # minimizingPlayer v = maxEvalBoard for y in range(n): for x in range(n): if ValidMove(board, x, y, player): (boardTemp, totctr) = MakeMove(copy.deepcopy(board), x, y, player) v = min(v, AlphaBeta(boardTemp, player, depth - 1, alpha, beta, True)) beta = min(beta, v) if beta <= alpha: break # alpha cut-off return v def AlphaBetaSN(board, player, depth, alpha, beta, maximizingPlayer): if depth == 0 or IsTerminalNode(board, player): return EvalBoard(board, player) sortedNodes = GetSortedNodes(board, player) if maximizingPlayer: v = minEvalBoard for boardTemp in sortedNodes: v = max(v, AlphaBetaSN(boardTemp, player, depth - 1, alpha, beta, False)) alpha = max(alpha, v) if beta <= alpha: break # beta cut-off return v else: # minimizingPlayer v = maxEvalBoard for boardTemp in sortedNodes: v = min(v, AlphaBetaSN(boardTemp, player, depth - 1, alpha, beta, True)) beta = min(beta, v) if beta <= alpha: break # alpha cut-off return v def Negamax(board, player, depth, color): if depth == 0 or IsTerminalNode(board, player): return color * EvalBoard(board, player) bestValue = minEvalBoard for y in range(n): for x in range(n): if ValidMove(board, x, y, player): (boardTemp, totctr) = MakeMove(copy.deepcopy(board), x, y, player) v = -Negamax(boardTemp, player, depth - 1, -color) bestValue = max(bestValue, v) return bestValue def NegamaxAB(board, player, depth, alpha, beta, color): if depth == 0 or IsTerminalNode(board, player): return color * EvalBoard(board, player) bestValue = minEvalBoard for y in range(n): for x in range(n): if ValidMove(board, x, y, player): (boardTemp, totctr) = MakeMove(copy.deepcopy(board), x, y, player) v = -NegamaxAB(boardTemp, player, depth - 1, -beta, -alpha, -color) bestValue = max(bestValue, v) alpha = max(alpha, v) if alpha >= beta: break return bestValue def NegamaxABSN(board, player, depth, alpha, beta, color): if depth == 0 or IsTerminalNode(board, player): return color * EvalBoard(board, player) sortedNodes = GetSortedNodes(board, player) bestValue = minEvalBoard for boardTemp in sortedNodes: v = -NegamaxABSN(boardTemp, player, depth - 1, -beta, -alpha, -color) bestValue = max(bestValue, v) alpha = max(alpha, v) if alpha >= beta: break return bestValue def Negascout(board, player, depth, alpha, beta, color): if depth == 0 or IsTerminalNode(board, player): return color * EvalBoard(board, player) firstChild = True for y in range(n): for x in range(n): if ValidMove(board, x, y, player): (boardTemp, totctr) = MakeMove(copy.deepcopy(board), x, y, player) if not firstChild: score = -Negascout(boardTemp, player, depth - 1, -alpha - 1, -alpha, -color) if alpha < score and score < beta: score = -Negascout(boardTemp, player, depth - 1, -beta, -score, -color) else: firstChild = False score = -Negascout(boardTemp, player, depth - 1, -beta, -alpha, -color) alpha = max(alpha, score) if alpha >= beta: break return alpha def NegascoutSN(board, player, depth, alpha, beta, color): if depth == 0 or IsTerminalNode(board, player): return color * EvalBoard(board, player) sortedNodes = GetSortedNodes(board, player) firstChild = True for boardTemp in sortedNodes: if not firstChild: score = -NegascoutSN(boardTemp, player, depth - 1, -alpha - 1, -alpha, -color) if alpha < score and score < beta: score = -NegascoutSN(boardTemp, player, depth - 1, -beta, -score, -color) else: firstChild = False score = -NegascoutSN(boardTemp, player, depth - 1, -beta, -alpha, -color) alpha = max(alpha, score) if alpha >= beta: break return alpha def BestMove(board, player): maxPoints = 0 mx = -1; my = -1 for y in range(n): for x in range(n): if ValidMove(board, x, y, player): (boardTemp, totctr) = MakeMove(copy.deepcopy(board), x, y, player) if opt == 0: points = EvalBoard(boardTemp, player) elif opt == 1: points = Minimax(boardTemp, player, depth, True) elif opt == 2: points = AlphaBeta(board, player, depth, minEvalBoard, maxEvalBoard, True) elif opt == 3: points = Negamax(boardTemp, player, depth, 1) elif opt == 4: points = NegamaxAB(boardTemp, player, depth, minEvalBoard, maxEvalBoard, 1) elif opt == 5: points = Negascout(boardTemp, player, depth, minEvalBoard, maxEvalBoard, 1) elif opt == 6: points = AlphaBetaSN(board, player, depth, minEvalBoard, maxEvalBoard, True) elif opt == 7: points = NegamaxABSN(boardTemp, player, depth, minEvalBoard, maxEvalBoard, 1) elif opt == 8: points = NegascoutSN(boardTemp, player, depth, minEvalBoard, maxEvalBoard, 1) if points > maxPoints: maxPoints = points mx = x; my = y return (mx, my) print 'REVERSI/OTHELLO BOARD GAME' print '0: EvalBoard' print '1: Minimax' print '2: Minimax w/ Alpha-Beta Pruning' print '3: Negamax' print '4: Negamax w/ Alpha-Beta Pruning' print '5: Negascout (Principal Variation Search)' print '6: Minimax w/ Alpha-Beta Pruning w/ Sorted Nodes' print '7: Negamax w/ Alpha-Beta Pruning w/ Sorted Nodes' print '8: Negascout (Principal Variation Search) w/ Sorted Nodes' opt = int(raw_input('Select AI Algorithm: ')) if opt > 0 and opt < 9: depth = 4 depthStr = raw_input('Select Search Depth (DEFAULT: 4): ') if depthStr != '': depth = int(depth) print '\n1: User 2: AI (Just press Enter for Exit!)' InitBoard() while True: for p in range(2): print PrintBoard() player = str(p + 1) print 'PLAYER: ' + player if IsTerminalNode(board, player): print 'Player cannot play! Game ended!' print 'Score User: ' + str(EvalBoard(board, '1')) print 'Score AI : ' + str(EvalBoard(board, '2')) os._exit(0) if player == '1': # user's turn while True: xy = raw_input('X Y: ') if xy == '': os._exit(0) (x, y) = xy.split() x = int(x); y = int(y) if ValidMove(board, x, y, player): (board, totctr) = MakeMove(board, x, y, player) print '# of pieces taken: ' + str(totctr) break else: print 'Invalid move! Try again!' else: # AI's turn (x, y) = BestMove(board, player) if not (x == -1 and y == -1): (board, totctr) = MakeMove(board, x, y, player) print 'AI played (X Y): ' + str(x) + ' ' + str(y) print '# of pieces taken: ' + str(totctr)