""" Searching for the best move in a game. To be specific, we'll look at a specific game, the "subtraction game"; see wikipedia's article on Nim * The game starts with N stones. * There are two players (say) white, black, with white going first. * On each move, a player can take 1, 2 or 3 stones. * The player who moves last loses. We'll need variables (typically dictionaries, lists, or objects) to represent * a state of the game (who's turn it is, how many stones are left) * a possible move And we define a "value" for (at least some) positions, with * good for white is positive, the bigger the better, * good for black is negative, the smaller the better. From a given game state, the possible moves form a tree that we'd like to search for the best move, with each node in the tree corresponding to a game position. * the tree branches end at "terminal" nodes, where the game stops. For those the value either * a big positive number (white wins), * a big negative number (black wins), or * zero (a draw) * the "depth" is how far down the tree we've searched. Typically we limit the search depth due to time or space constraints; in that case we typically guess a value for the the position based on the board state. For example, if the game is chess, and white has a queen advantage, then the value would likely be positive since white seems to be winning. * at each node, we'd like to choose the best move for the player whose turn it is to move, which means alternating picking the biggest (max) and smallest (min) value from the nodes below. Here are the functions (which could also be set up as object methods) used in the search itself: game = new_game(stones=10) # create a new game finished = is_finished(game) # boolean True or False value = game_value(game) # integer moves = possible_moves(game) # list of moves new_game = make_move(game, move) (move, value) = find_max(game) # white's best move & outcome (move, value) = find_min(game) # black's best move & outcome These last two functions can be wrapped up into one function, see the wikipedia articles Minmax, Alpha-Beta Pruning, and Negamax articles for details. Jim Mahoney mahoney@marlboro.edu | GPL | Nov 2011 """ import random import sys debug = True infinity = float('INF') other_player = {'white': 'black', 'black': 'white'} def new_game(stones=10, whose_move='white'): """Return a new game (white's turn to move) with the given number of stones """ return {'stones': stones, 'whose_move': whose_move} def is_finished(game): """Return true if game is finished""" return game['stones'] <= 0 def game_value(game): """Return value of game""" # best for white is big positive; best for black is big negative. # See the explanation at the top of the file. if is_finished(game): if game['whose_move'] == 'white': return 100 # white wins (black moved last) else: return -100 # black wins else: # This is where a more sophisticated algorithm # would do some sort of game analysis and try # to guess which player is winning (even though # the game isn't done yet) and from # that come up with a value. # But in this simple example, we just don't know. return 0 def make_move(game, move): """Return the game resulting from applying a move to a game.""" # Here move is just the number of stones to be taken. new_stones = game['stones'] - move next_player = other_player[game['whose_move']] return new_game(new_stones, next_player) def possible_moves(game): """Return possible moves from this board position""" # A move is taking 1, 2, or 3 stones, # up to the number of stones left. stones_left = game['stones'] if stones_left >= 3: moves = [1, 2, 3] elif stones_left >= 2: moves = [1, 2] else: moves = [1] # The search will work best if these are sorted # with better candidate moves first. Here I'm # shuffling so that if the search algorithm can't # distinguish between the moves, the first one it # likes will be a random one. random.shuffle(moves) return moves def print_debug(message, depth): """ debug printing with indentation """ depth = min(depth, 20) if debug: indent = " "*(20 - depth) print(indent + message) def find_max(game, max_depth): """Return biggest (move, value), searching at most max_depth moves""" if max_depth <= 0 or is_finished(game): value = game_value(game) print_debug("find_max end of game, value=%i" % value, max_depth) return ([], value) else: best_move = None best_value = -1000 # < smallest returned by game_value moves = possible_moves(game) for move in moves: new_game = make_move(game, move) # Recursively look at the rest of the tree (next_move, its_value) = find_min(new_game, max_depth - 1) if its_value > best_value: print_debug("find_max new best (%i, %i)" % \ (move, its_value), max_depth) best_move = move best_value = its_value return (best_move, best_value) def find_max_2(game, depth): # same, no debugging, a bit more terse if depth <= 0 or is_finished_game(game): return ([], game_value(game)) (best_value, best_move) = (-infinity, None) for move in possible_moves(game): (next_move, its_value) = find_min(make_move(game, move), depth-1) (best_value, best_move) = max((best_value, best_move), (its_value, move)) return (best_value, best_move) def find_min(game, max_depth): """Return smallest (move, value), searching at most max_depth moves""" if max_depth <= 0 or is_finished(game): value = game_value(game) print_debug("find_min end of game, value=%i" % value, max_depth) return ([], value) else: best_move = None best_value = 1000 # > biggest returned by game_value moves = possible_moves(game) for move in moves: new_game = make_move(game, move) # Recursively look at the rest of the tree (next_move, its_value) = find_max(new_game, max_depth - 1) if its_value < best_value: print_debug("find_min new best (%i, %i)" \ % (move, its_value), max_depth) best_move = move best_value = its_value return (best_move, best_value) def computer_move(game, depth): """Get the computer's move""" if game['whose_move'] == 'white': (move, value) = find_max(game, depth) else: (move, value) = find_min(game, depth) return move def print_game(game): print("It is {}'s move, and there are {} stones left.".format( game['whose_move'], game['stones'])) def leave(): print() print("OK, bye.") sys.exit() def user_move(game, depth): """Ask the user for a move, and return it.""" while True: try: move = int(input("How many stones would you like to take? ")) if move[0]=='q': leave() move = int(move) assert 1 <= move <= 3 return move except EOFError: leave() except: print("Illegal input; please type 1, 2, or 3.") def user_or_computer(string): """Return 'user' or 'computer' given user input string""" if string[0] in 'uU': return 'user' else: return 'computer' def get_params(): """Return (int, int, dict) n_stones, max_depth, {'white':'user' or 'computer', 'black': 'user' or 'computer'}""" print() try: stones = int(input("How many stones? (i.e. 6) ")) except: stones = 6 try: depth = int(input("Search depth? (i.e. 6) ")) except: depth = 6 white = user_or_computer(input( "white (1st player) is user or computer? ")) black = user_or_computer(input( "black (1st player) is user or computer? ")) players = {'white': white, 'black': black} print() return (stones, depth, players) def main(): print("== the subtraction game ==") (n_stones, max_depth, players) = get_params() game = new_game(n_stones) move_functions = {'user': user_move, 'computer': computer_move} while not is_finished(game): print_game(game) user_or_computer = players[game['whose_move']] get_move_func = move_functions[user_or_computer] move = get_move_func(game, max_depth) game = make_move(game, move) print() if game_value(game) > 0: print("white wins!") else: print("black wins!") if __name__ == "__main__": main()