use Game.frink /** This is a class to play the game of Othello/Reversi. It uses Game.frink which specifies the GameState interface that this implements to play the game. Official rules: https://www.worldothello.org/about/about-othello/othello-rules/official-rules/english The current implementation uses a naive static evaluation function which simply counts the number of pieces. There is more strategy available at: https://www.samsoft.org.uk/reversi/strategy.htm Also see: https://stackoverflow.com/questions/12334216/othello-evaluation-function where a suggestion is that a static evaluation function can just be a random number and that works effectively because "The logic is that the player with the most choices will be able to steer the game to get the highest random number, and so this approach again means that the AI will favour moves which give it lots of choices, and his opponent few." and the suggestion was found to be effective. */ /** */ class Othello implements GameState { /** A 2x2 array with integer values. */ var board /** A count of the number of filled spaces. */ var filled /** A function that sorts the goodness of moves. */ class var moveOrderer = {|a,b| distFromCorner[a] <=> distFromCorner[b] } /** Create a new starting board */ new[] := { board = new array[[8,8],0] board@3@3 = 1 board@3@4 = -1 board@4@3 = -1 board@4@4 = 1 filled = 4 } /** Copy constructor. */ new[orig is Othello] := { board = deepCopy[orig.board] filled = orig.filled } /** Distance from corner. The object is an OthelloMove. */ distFromCorner[move] := { val = 0 if move.row >= 4 val = 7 - move.row else val = move.row if move.col >= 4 val = val + (7 - move.col) else val = val + move.col return val } /** Returns true if this is a terminal state (e.g. a winning or losing position that cannot be followed any further.) TODO: Fix this. If a player cannot make a move, they forfeit their turn and the other player plays. The official rules state: "When it is no longer possible for either player to move, the game is over. Disks are counted and the player with the majority of their colour showing is the winner." "Note: It is possible for a game to end before all 64 squares are filled." */ isTerminal[player] := { return ! canMove[player] } /** Perform a static evaluation of the game state. This should always give a ranking for the win probability for player +1. TODO: This evaluation function is really naive and only counts the number of pieces on the board. This can be improved. THINK ABOUT: Should this take a player argument? That might allow it to use a different evaluation function for each player which would be interesting and allow different training functions. */ staticEvaluate[] := { sum = 0 for row = 0 to 7 sum = sum + sum[board@row] return sum } /** Generates the next moves for the specified player (+1 or -1.) The resultant types should be an instance of OthelloMove which implements GameMove. */ nextMoves[player] := { moves = new array ROW: for row = 0 to 7 { COL: for col = 0 to 7 if (board@row@col == 0) { ROWDIR: for rowdir = -1 to 1 { if (row <= 1 and rowdir == -1) or (row >= 6 and rowdir == 1) next ROWDIR // No capture possible this direction COLDIR: for coldir = -1 to 1 { if coldir==0 and rowdir==0 next COLDIR if (col <= 1 and coldir == -1) or (col>=6 and coldir == 1) next COLDIR // No capture possible this direction if testCapture[row, col, rowdir, coldir, player] == true { moves.push[new OthelloMove[row, col, player]] next COL // A move found in this space, try next space } } } } } moves.sort[moveOrderer] return moves } /** Checks to see if the specified player has any move at all. Returns true if they can. */ canMove[player] := { if filled == 64 return false for row = 0 to 7 for col = 0 to 7 if (board@row@col == 0) { ROWDIR: for rowdir = -1 to 1 { if (row <= 1 and rowdir == -1) or (row >= 6 and rowdir == 1) next ROWDIR // No capture possible this direction COLDIR: for coldir = -1 to 1 { if coldir==0 and rowdir==0 next COLDIR if (col <= 1 and coldir == -1) or (col>=6 and coldir == 1) next COLDIR // No capture possible this direction if testCapture[row, col, rowdir, coldir, player] == true return true } } } return false } /** Applies a move to this GameState and returns the next GameState. The move should implement GameMove. TODO: Make Frink specify that a interface method implements a constraint. */ applyMove[move] := { newBoard = new Othello[this] // Copy board if move != undef newBoard.doApplyMove[move.row, move.col, move.player] return newBoard } /** Applies a move to this GameState and returns the next GameState. */ doApplyMove[row, col, player] := { if (board@row@col == 0) { ROWDIR: for rowdir = -1 to 1 { if (row <= 1 and rowdir == -1) or (row >= 6 and rowdir == 1) next ROWDIR // No capure possible this direction COLDIR: for coldir = -1 to 1 { if coldir==0 and rowdir==0 next COLDIR if (col <= 1 and coldir == -1) or (col>=6 and coldir == 1) next COLDIR // No capture possible this direction if testCapture[row, col, rowdir, coldir, player] == true { r1 = row + rowdir c1 = col + coldir // println["playing \$row \$col \$rowdir \$coldir \$player"] while board@r1@c1 == -player { board@r1@c1 = player // Flip piece r1 = r1 + rowdir c1 = c1 + coldir } } } } } board@row@col = player filled = filled + 1 } /** Returns true if a capture can be made by the player playing at row, col and going in direction rowdir, coldir */ testCapture[row, col, rowdir, coldir, player] := { r1 = row + rowdir c1 = col + coldir if board@r1@c1 == -player // Opposite player's color adjacent, keep going { do { r1 = r1 + rowdir c1 = c1 + coldir if r1<0 or r1>7 or c1<0 or c1>7 // Off the board, not captured return false val = board@r1@c1 if val == 0 // Empty place before player's color return false if val == player // Found player's color again return true } while true } return false } /** If this position is a win for a player (-1 or +1), it returns that player's number, otherwise returns 0. */ winFor[] := { if ! canMove[-1] and ! canMove[1] return signum[staticEvaluate[]] else return 0 } /** Renders the game state in a human-friendly format (e.g. drawing the game board.) */ toString[] := { str = " 0 1 2 3 4 5 6 7\n" for r = 0 to 7 { str = str + "\$r " for c = 0 to 7 { v = board@r@c if v == 0 str = str + " ." else if v == -1 str = str + " O" else str = str + " X" } if r < 7 str = str + "\n" } return str } /** Turns a player number (-1 or +1) into the associated character. */ class playerToString[player] := { if player == 1 return "X" if player == -1 return "O" else return "nobody" } } /** This implements the GameMove interface to represent a move in an Othello game. */ class OthelloMove implements GameMove { /** The move is represented as a row, column, and player. */ var row var col var player new[r, c, p] := { row = r col = c player = p } /** Returns a human-readble string for logging and display. */ toString[] := { "Row: \$row Col: \$col Player: \$player" } } // The rest of this program actually plays the game by taking user input // and letting the computer calculate its move by calling Game.negamax[] // LOL thanks to the eval you can do WarGames-style "ZERO" for number of players players = eval[input["Number of players: ", 0]] board = new Othello[] println[board.toString[]] var row var col // Represents which player number moves next. In official Othello rules // black always moves first. movesNext = random[[-1,1]] while board.canMove[1] or board.canMove[-1] { p = Othello.playerToString[movesNext] if players==2 or (players==1 and movesNext == 1) // Human moves { if board.canMove[movesNext] { do { println[] [row, col] = eval[input["Enter move for \$p", ["row: ", "col: "]]] if board.board@row@col != 0 println["Try again."] } while board.board@row@col != 0 move = new OthelloMove[row, col, movesNext] } else { println["Player \$p has no moves!"] move = undef } } else // Computer moves { [move, value] = Game.negamax[board, movesNext==1 ? 8 : 6, movesNext] if move != undef println["\nComputer (\$p, \$movesNext) chose " + move.toString[] + ", perceived value = " + (value * movesNext)] else println["\nComputer player (\$p) apparently has no move!"] } if move != undef board = board.applyMove[move] println[board.toString[]] movesNext = -movesNext } println["Win for " + Othello.playerToString[board.winFor[]] + " by " + abs[board.staticEvaluate[]]]