""" subtraction_game_search.py 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 called (say) white and black. * White moves first. * On each move, a player must take either 1, 2 or 3 stones. * The player who moves last loses. We'll need some sort of data structures (dictionaries, lists, or objects) to represent * a state of the game (who's turn it is, how many stones are left) * a possible move To build an AI search engine, we need define a value for board game positions. Here we'll choose * 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 is either * a big positive number (white wins), * a big negative number (black wins), or * zero (a draw, which never happens in this particular game.) 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 for white player) and smallest (min for black player) value from the nodes below. Here are the functions in the code below which implement the game and the search for the best move. (These could be made into object methods; here I chose to use a dictionary as the primary game data structure instead.) game = new_game(stones=10) # create a new game finished = is_finished(game) # boolean True or False value = game_value(game) # integer; positive is good for white moves = possible_moves(game) # list of moves (each move is 1, 2, or 3) new_game = make_move(game, move) move = user_move(game, depth) # ask user for a move and return it move = computer_white_move(game, depth) # start white's search of move tree value = white_value(game, depth) # continue down tree for white's move move = computer_black_move(game, depth) # start black's search of move tree value = black_value(game, depth) # continue down tree of black's move For an example of the tree of possible moves and how the search functions work, consider the situation with 4 stones remaining and white to move. 4 stones, white to move; computer_white_move(depth=6) ---------- / | \ 3 2 1 black to move black_value(depth=5) / | \ / \ | 0 1 2 0 1 0 white to move white_value(depth=4) | /\ | 0 1 0 0 black to move black_value(depth=3) | 0 white to move white_value(depth=2) At each node of the tree, the search algorithm chooses the best board position for the white or black player. Here "best" alternates between choosing the largest board value and the smallest, depending on whose move it is. Starting at the bottom, and filling in a letter for who wins, in that tree, with w=100, b=-100, and then assigning values based on choosing the "best" move for each player, the completely searched tree is : Of the three possible moves (take 1, take 2, take 3) the white computer player chooses to take 3, since that w node has the largest value. ------------- / | \ b=-100 b=-100 w=100 / | \ / \ | w b w w b w | /\ | b w b b | w Jim Mahoney | Dec 2013 | MIT License """ import random import sys debug = False win_value = 100 # value for board when white wins infinity = 1000 # bigger than any possible board value 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 win_value # white wins (black moved last) else: return -win_value # black wins else: # This is where a more sophisticated algorithm could 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 """ offset = 12 # should be bigger than max_depth * len(spaces) spaces = " " # depth = min(depth, offset) if debug: indent = spaces * (offset - depth) print indent + message def print_game(game): print "It is %s's move, and there are %i stones left." \ % (game['whose_move'], game['stones']) def leave(): print print "OK, bye." sys.exit() def computer_white_move(game, depth): """ Return move that gives highest game value, i.e. best for white """ white_best_move = None white_best_value = -infinity for move in possible_moves(game): value = black_value(make_move(game, move), depth - 1) if value > white_best_value: white_best_value = value white_best_move = move return white_best_move def computer_black_move(game, depth): """ Return move that gives lowest game value, i.e. best for black """ black_best_move = None black_best_value = infinity for move in possible_moves(game): value = white_value(make_move(game, move), depth - 1) if value < black_best_value: black_best_value = value black_best_move = move return black_best_move def white_value(game, depth): """Return best for white (largest) board value """ # search at most depth moves further down the tree of possible moves if depth <= 0 or is_finished(game): value = game_value(game) print_debug("white_value at end of game is %i" % value, depth) return value else: white_best_value = -infinity for move in possible_moves(game): # Recursively look at the rest of the tree value = black_value(make_move(game, move), depth - 1) if value > white_best_value: white_best_value = value print_debug("white_value new biggest=%i, move=%i" \ % (value, move), depth) return white_best_value def black_value(game, depth): """Return best for black (i.e. smallest) board value """ # search at most depth moves further down the tree of possible moves if depth <= 0 or is_finished(game): value = game_value(game) print_debug("black_value at end of game is %i" % value, depth) return value else: black_best_value = infinity for move in possible_moves(game): # Recursively look at the rest of the tree value = white_value(make_move(game, move), depth - 1) if value < black_best_value: black_best_value = value print_debug("black_value new smallest=%i, move=%i " \ % (value, move), depth) return black_best_value def user_move(game, depth): """Ask the user for a move, and return it.""" while True: try: move = raw_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 len(string) == 0 or string[0] in 'cC': return 'computer' else: return 'user' def get_params(): """Return (int, int, dict of functions) n_stones, max_depth, {'white': move_func, 'black': move_func} where move_func is user_move or computer_*_move """ print try: stones = input("How many stones? (i.e. 6) ") except: stones = 6 # As long as there are fewer than 20 stones, # search the whole game. (This is from a bit of trial'n'error # with what takes too long on my laptop.) depth = min(stones + 1, 20) # #try: # depth = input("Search depth? (i.e. 6) ") #except: # depth = 6 # player_functions = {} # initially empty dictionary white_player = raw_input("white (1st player) is user or computer? ") if user_or_computer(white_player) == 'user': player_functions['white'] = user_move else: player_functions['white'] = computer_white_move black_player = raw_input("black (2nd player) is user or computer? ") if user_or_computer(black_player) == 'user': player_functions['black'] = user_move else: player_functions['black'] = computer_black_move return (stones, depth, player_functions) def main(): print "== the subtraction game ==" (n_stones, max_depth, player_functions) = get_params() game = new_game(n_stones) while not is_finished(game): print_game(game) whose_move = game['whose_move'] move_func = player_functions[whose_move] # user_move or computer_*_move move = 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()