from abc import ABC, abstractmethod import copy from math import log from random import choice import time def current_ms_time(): return round(1000 * time.time()) class GameNode(ABC): """Abstract Base Class for game tree nodes.""" # constant integers designating player MAXimizing and MINimizing utility MAX, MIN = 0, 1 # undefined move constant UNDEFINED_MOVE = -1 def __init__(self, other=None): """Initialize a root node or create a copy of GameNode other (default=None).""" if not other: # first player MAXimizer by default self.player = GameNode.MAX # previous move applied to reach this node is UNDEFINED_MOVE for root self.prev_move = GameNode.UNDEFINED_MOVE # root has no parent self.parent = None else: self.player = other.player self.prev_move = other.prev_move self.parent = other.parent def get_player(self): """Return current GameNode player.""" return self.player @abstractmethod def expand(self): """Return a list of successor GameNodes to this GameNode.""" pass @abstractmethod def child_copy(self): """Return a copy of this GameNode with this GameNode as its parent.""" pass @abstractmethod def is_game_over(self): """Return whether or not this GameNode represents a terminal game state.""" pass @abstractmethod def utility(self): """Return the MAX player utility of this game state.""" pass class GameTreeSearcher(ABC): """Abstract Base Class for game tree searching algorithms.""" @abstractmethod def eval(self, node): """Return the estimated minimax value of the given GameNode.""" pass @abstractmethod def get_best_move(self): """Return the best move for the node most recently evaluated.""" pass @abstractmethod def get_node_count(self): """Return the number of nodes searched for the previous node evaluation.""" pass # Depth-Limited Minimax Searcher class MinimaxSearcher(GameTreeSearcher): """Depth-limited minimax game tree searcher.""" def __init__(self, depth_limit): """Create a minimax searcher with a given depth limit.""" self.depth_limit = depth_limit self.node_count = 0 self.best_move = GameNode.UNDEFINED_MOVE def eval(self, node): """Return the depth-limited minimax value of the given node.""" self.node_count = 0 return self.minimax_eval(node, self.depth_limit) def minimax_eval(self, node, depth_left): """Return recursive node evaluation of minimax algorithm.""" local_best_move = GameNode.UNDEFINED_MOVE maximizing = (node.get_player() == GameNode.MAX) best_utility = float('-inf') if maximizing else float('inf') self.node_count += 1 # Return utility if game over or depth limit reached if node.is_game_over() or depth_left == 0: return node.utility() # Otherwise, generate children children = node.expand() # Evaluate the depth-limited minimax value for each # child, keeping track of the best for child in children: child_utility = self.minimax_eval(child, depth_left - 1) # update best utility and move if appropriate if (maximizing and child_utility > best_utility) or (not maximizing and child_utility < best_utility): best_utility = child_utility local_best_move = child.prev_move # Before returning utility, assign local best move to # instance variable. The last value assigned in the # recursive evaluation will be the best move from the # root node. self.best_move = local_best_move return best_utility def get_best_move(self): return self.best_move def get_node_count(self): return self.node_count # Mancala-Specific Code: fairkalah_states = [ [4, 4, 5, 4, 3, 4, 0, 4, 4, 4, 4, 4, 4, 0], [4, 4, 5, 4, 4, 4, 0, 4, 3, 4, 4, 4, 4, 0], [4, 5, 4, 4, 4, 4, 0, 4, 4, 3, 4, 4, 4, 0], [2, 4, 4, 4, 4, 4, 0, 4, 4, 4, 4, 4, 5, 1], [2, 4, 4, 4, 4, 4, 0, 4, 4, 4, 5, 4, 5, 0], [2, 4, 4, 4, 4, 5, 0, 4, 4, 4, 4, 4, 5, 0], [2, 5, 5, 4, 4, 4, 0, 4, 4, 4, 4, 4, 4, 0], [3, 3, 5, 4, 4, 4, 0, 5, 4, 4, 4, 4, 4, 0], [3, 4, 4, 4, 4, 3, 0, 4, 4, 4, 4, 6, 4, 0], [3, 4, 4, 4, 4, 4, 0, 4, 4, 3, 4, 4, 4, 2], [3, 4, 4, 4, 4, 4, 0, 4, 4, 3, 4, 4, 5, 1], [3, 4, 4, 4, 4, 4, 0, 4, 4, 3, 4, 5, 5, 0], [3, 4, 4, 4, 4, 4, 0, 4, 4, 3, 5, 4, 4, 1], [3, 4, 4, 4, 4, 4, 0, 4, 4, 3, 5, 4, 5, 0], [3, 4, 4, 4, 4, 4, 0, 4, 4, 3, 6, 4, 4, 0], [3, 4, 4, 4, 4, 4, 0, 4, 4, 4, 3, 6, 4, 0], [3, 4, 4, 4, 4, 4, 0, 5, 4, 3, 4, 4, 4, 1], [3, 4, 4, 4, 4, 4, 0, 5, 4, 3, 4, 5, 4, 0], [3, 4, 4, 4, 4, 4, 1, 4, 4, 3, 4, 5, 4, 0], [3, 4, 4, 4, 4, 5, 0, 4, 4, 3, 4, 4, 4, 1], [3, 4, 4, 4, 4, 5, 0, 4, 4, 3, 4, 4, 5, 0], [3, 4, 4, 4, 4, 5, 0, 4, 4, 3, 4, 5, 4, 0], [3, 4, 4, 4, 5, 4, 0, 4, 4, 3, 4, 4, 4, 1], [3, 4, 4, 4, 5, 4, 0, 4, 4, 3, 4, 4, 5, 0], [3, 4, 4, 4, 5, 4, 0, 4, 4, 3, 5, 4, 4, 0], [3, 4, 4, 4, 5, 5, 0, 4, 4, 3, 4, 4, 4, 0], [3, 4, 4, 4, 6, 4, 0, 4, 4, 3, 4, 4, 4, 0], [3, 4, 4, 5, 4, 4, 0, 4, 4, 3, 4, 4, 4, 1], [3, 4, 4, 5, 4, 4, 0, 4, 4, 3, 4, 4, 5, 0], [3, 4, 4, 5, 4, 4, 0, 4, 4, 3, 4, 5, 4, 0], [3, 4, 4, 5, 4, 4, 0, 4, 4, 3, 5, 4, 4, 0], [3, 4, 4, 6, 4, 4, 0, 4, 4, 3, 4, 4, 4, 0], [3, 4, 5, 4, 3, 4, 0, 4, 4, 4, 4, 4, 4, 1], [3, 4, 5, 4, 3, 4, 0, 4, 4, 4, 4, 5, 4, 0], [3, 4, 5, 4, 3, 4, 0, 4, 4, 4, 5, 4, 4, 0], [3, 4, 5, 4, 3, 4, 0, 5, 4, 4, 4, 4, 4, 0], [3, 4, 5, 4, 3, 5, 0, 4, 4, 4, 4, 4, 4, 0], [3, 4, 5, 4, 4, 4, 0, 3, 4, 4, 4, 4, 4, 1], [3, 4, 5, 4, 4, 4, 0, 3, 4, 4, 4, 4, 5, 0], [3, 4, 5, 4, 4, 4, 0, 3, 4, 4, 4, 5, 4, 0], [3, 4, 5, 4, 4, 4, 0, 4, 3, 4, 4, 4, 5, 0], [3, 4, 5, 4, 4, 4, 0, 4, 3, 4, 4, 5, 4, 0], [3, 4, 5, 4, 4, 4, 0, 4, 3, 4, 5, 4, 4, 0], [3, 4, 5, 4, 4, 4, 0, 4, 4, 4, 4, 3, 5, 0], [3, 4, 5, 4, 4, 4, 0, 4, 4, 4, 5, 3, 4, 0], [3, 4, 5, 4, 4, 5, 0, 4, 3, 4, 4, 4, 4, 0], [3, 4, 5, 4, 4, 5, 0, 4, 4, 4, 4, 3, 4, 0], [3, 4, 5, 4, 5, 3, 0, 4, 4, 4, 4, 4, 4, 0], [3, 4, 5, 4, 5, 4, 0, 3, 4, 4, 4, 4, 4, 0], [3, 4, 5, 5, 3, 4, 0, 4, 4, 4, 4, 4, 4, 0], [3, 4, 6, 4, 3, 4, 0, 4, 4, 4, 4, 4, 4, 0], [3, 4, 6, 4, 4, 4, 0, 3, 4, 4, 4, 4, 4, 0], [3, 5, 4, 4, 4, 4, 0, 4, 4, 3, 4, 4, 4, 1], [3, 5, 4, 4, 4, 4, 0, 4, 4, 3, 4, 4, 5, 0], [3, 5, 4, 4, 4, 4, 0, 4, 4, 3, 4, 5, 4, 0], [3, 5, 4, 4, 4, 5, 0, 4, 4, 3, 4, 4, 4, 0], [3, 5, 4, 4, 5, 4, 0, 4, 4, 3, 4, 4, 4, 0], [3, 5, 5, 4, 3, 4, 0, 4, 4, 4, 4, 4, 4, 0], [3, 5, 5, 4, 4, 4, 0, 4, 4, 4, 3, 4, 4, 0], [3, 6, 4, 4, 3, 4, 0, 4, 4, 4, 4, 4, 4, 0], [3, 6, 4, 4, 4, 3, 0, 4, 4, 4, 4, 4, 4, 0], [3, 6, 4, 4, 4, 4, 0, 4, 4, 4, 3, 4, 4, 0], [4, 2, 5, 4, 4, 4, 0, 4, 4, 4, 4, 4, 5, 0], [4, 2, 5, 4, 4, 4, 0, 4, 4, 4, 4, 5, 4, 0], [4, 2, 5, 4, 4, 4, 0, 5, 4, 4, 4, 4, 4, 0], [4, 2, 5, 4, 4, 4, 1, 4, 4, 4, 4, 4, 4, 0], [4, 2, 5, 5, 4, 4, 0, 4, 4, 4, 4, 4, 4, 0], [4, 2, 6, 4, 4, 4, 0, 4, 4, 4, 4, 4, 4, 0], [4, 3, 4, 4, 4, 4, 0, 4, 4, 3, 4, 5, 4, 1], [4, 3, 4, 4, 4, 4, 0, 4, 4, 3, 4, 5, 5, 0], [4, 3, 4, 4, 4, 4, 0, 4, 4, 3, 4, 6, 4, 0], [4, 3, 4, 4, 4, 4, 0, 4, 4, 3, 5, 4, 4, 1], [4, 3, 4, 4, 4, 5, 0, 5, 4, 3, 4, 4, 4, 0], [4, 3, 4, 4, 5, 4, 0, 4, 4, 3, 4, 5, 4, 0], [4, 3, 4, 5, 4, 4, 0, 4, 4, 3, 4, 4, 4, 1], [4, 3, 4, 5, 4, 4, 0, 4, 4, 3, 4, 5, 4, 0], [4, 3, 4, 5, 4, 5, 0, 4, 4, 3, 4, 4, 4, 0], [4, 3, 4, 5, 5, 4, 0, 4, 4, 3, 4, 4, 4, 0], [4, 3, 5, 4, 3, 4, 0, 5, 4, 4, 4, 4, 4, 0], [4, 3, 5, 4, 4, 3, 0, 4, 5, 4, 4, 4, 4, 0], [4, 3, 5, 4, 4, 3, 0, 5, 4, 4, 4, 4, 4, 0], [4, 3, 5, 4, 4, 4, 0, 4, 3, 4, 5, 4, 4, 0], [4, 3, 5, 4, 4, 4, 0, 4, 4, 3, 4, 4, 5, 0], [4, 3, 5, 4, 4, 4, 0, 4, 4, 3, 5, 4, 4, 0], [4, 3, 5, 4, 4, 4, 0, 4, 4, 4, 4, 3, 4, 1], [4, 3, 5, 4, 4, 4, 0, 4, 4, 4, 4, 3, 5, 0], [4, 3, 5, 4, 4, 4, 0, 4, 4, 4, 4, 4, 3, 1], [4, 3, 5, 4, 4, 4, 0, 4, 4, 4, 5, 3, 4, 0], [4, 3, 5, 4, 4, 4, 0, 4, 4, 5, 3, 4, 4, 0], [4, 3, 5, 4, 4, 4, 0, 5, 3, 4, 4, 4, 4, 0], [4, 3, 5, 4, 4, 4, 0, 5, 4, 3, 4, 4, 4, 0], [4, 3, 5, 4, 4, 4, 0, 5, 4, 4, 4, 3, 4, 0], [4, 3, 5, 4, 4, 4, 1, 4, 3, 4, 4, 4, 4, 0], [4, 3, 5, 4, 4, 4, 1, 4, 4, 3, 4, 4, 4, 0], [4, 3, 5, 4, 4, 5, 0, 4, 3, 4, 4, 4, 4, 0], [4, 3, 5, 4, 4, 5, 0, 4, 4, 4, 4, 3, 4, 0], [4, 3, 5, 4, 5, 3, 0, 4, 4, 4, 4, 4, 4, 0], [4, 3, 5, 4, 5, 4, 0, 4, 4, 3, 4, 4, 4, 0], [4, 3, 5, 5, 3, 4, 0, 4, 4, 4, 4, 4, 4, 0], [4, 3, 5, 5, 4, 4, 0, 4, 4, 3, 4, 4, 4, 0], [4, 3, 6, 4, 3, 4, 0, 4, 4, 4, 4, 4, 4, 0], [4, 3, 6, 4, 4, 4, 0, 4, 3, 4, 4, 4, 4, 0], [4, 3, 6, 4, 4, 4, 0, 4, 4, 3, 4, 4, 4, 0], [4, 4, 3, 4, 4, 4, 0, 4, 4, 4, 3, 4, 5, 1], [4, 4, 3, 4, 4, 4, 0, 4, 4, 4, 3, 4, 6, 0], [4, 4, 3, 4, 4, 4, 0, 5, 4, 4, 3, 4, 5, 0], [4, 4, 3, 4, 4, 4, 1, 5, 4, 4, 3, 4, 4, 0], [4, 4, 4, 4, 4, 3, 0, 4, 4, 4, 3, 4, 4, 2], [4, 4, 4, 4, 4, 3, 0, 4, 4, 4, 3, 4, 6, 0], [4, 4, 4, 4, 4, 3, 0, 5, 4, 4, 3, 4, 4, 1], [4, 4, 4, 4, 4, 4, 0, 4, 4, 4, 2, 4, 4, 2], [4, 4, 4, 4, 4, 4, 0, 4, 4, 4, 2, 4, 6, 0], [4, 4, 4, 4, 4, 4, 0, 5, 4, 3, 3, 4, 5, 0], [4, 4, 4, 4, 4, 4, 1, 5, 4, 3, 3, 4, 4, 0], [4, 4, 4, 4, 5, 4, 0, 5, 4, 4, 2, 4, 4, 0], [4, 4, 4, 5, 4, 3, 0, 4, 4, 4, 3, 4, 4, 1], [4, 4, 4, 5, 4, 4, 0, 4, 4, 4, 4, 2, 5, 0], [4, 4, 4, 5, 4, 4, 0, 5, 4, 3, 3, 4, 4, 0], [4, 4, 5, 4, 3, 3, 0, 5, 4, 4, 4, 4, 4, 0], [4, 4, 5, 4, 3, 4, 0, 3, 4, 4, 4, 5, 4, 0], [4, 4, 5, 4, 3, 4, 0, 3, 4, 4, 5, 4, 4, 0], [4, 4, 5, 4, 3, 4, 0, 4, 4, 3, 4, 5, 4, 0], [4, 4, 5, 4, 3, 4, 0, 4, 4, 4, 4, 4, 3, 1], [4, 4, 5, 4, 3, 4, 0, 5, 3, 4, 4, 4, 4, 0], [4, 4, 5, 4, 3, 4, 1, 3, 4, 4, 4, 4, 4, 0], [4, 4, 5, 4, 3, 4, 1, 4, 3, 4, 4, 4, 4, 0], [4, 4, 5, 4, 3, 4, 1, 4, 4, 3, 4, 4, 4, 0], [4, 4, 5, 4, 3, 5, 0, 3, 4, 4, 4, 4, 4, 0], [4, 4, 5, 4, 3, 5, 0, 4, 4, 4, 3, 4, 4, 0], [4, 4, 5, 4, 4, 2, 0, 4, 5, 4, 4, 4, 4, 0], [4, 4, 5, 4, 4, 3, 0, 4, 4, 3, 4, 5, 4, 0], [4, 4, 5, 4, 4, 3, 0, 4, 4, 3, 5, 4, 4, 0], [4, 4, 5, 4, 4, 3, 0, 5, 3, 4, 4, 4, 4, 0], [4, 4, 5, 4, 4, 3, 0, 5, 4, 3, 4, 4, 4, 0], [4, 4, 5, 4, 4, 3, 1, 4, 4, 3, 4, 4, 4, 0], [4, 4, 5, 4, 4, 3, 1, 4, 4, 4, 4, 3, 4, 0], [4, 4, 5, 4, 4, 3, 1, 4, 4, 4, 4, 4, 3, 0], [4, 4, 5, 4, 4, 4, 0, 3, 3, 4, 4, 4, 5, 0], [4, 4, 5, 4, 4, 4, 0, 4, 2, 4, 4, 4, 4, 1], [4, 4, 5, 4, 4, 4, 0, 4, 2, 4, 4, 5, 4, 0], [4, 4, 5, 4, 4, 4, 0, 4, 3, 3, 4, 4, 5, 0], [4, 4, 5, 4, 4, 4, 0, 4, 3, 3, 4, 5, 4, 0], [4, 4, 5, 4, 4, 4, 0, 4, 3, 4, 4, 3, 4, 1], [4, 4, 5, 4, 4, 4, 0, 4, 3, 4, 4, 5, 3, 0], [4, 4, 5, 4, 4, 4, 0, 4, 3, 4, 5, 3, 4, 0], [4, 4, 5, 4, 4, 4, 0, 4, 4, 2, 5, 4, 4, 0], [4, 4, 5, 4, 4, 4, 0, 4, 4, 3, 4, 3, 5, 0], [4, 4, 5, 4, 4, 4, 0, 4, 4, 3, 5, 3, 4, 0], [4, 4, 5, 4, 4, 4, 0, 4, 4, 5, 2, 4, 4, 0], [4, 4, 5, 4, 4, 4, 0, 4, 5, 4, 2, 4, 4, 0], [4, 4, 5, 4, 4, 4, 0, 4, 5, 4, 3, 3, 4, 0], [4, 4, 5, 4, 4, 4, 0, 4, 5, 4, 4, 2, 4, 0], [4, 4, 5, 4, 4, 4, 0, 5, 2, 4, 4, 4, 4, 0], [4, 4, 5, 4, 4, 4, 0, 5, 3, 3, 4, 4, 4, 0], [4, 4, 5, 4, 4, 4, 0, 5, 3, 4, 4, 3, 4, 0], [4, 4, 5, 4, 4, 4, 0, 5, 4, 3, 4, 3, 4, 0], [4, 4, 5, 4, 4, 4, 0, 5, 4, 3, 4, 4, 3, 0], [4, 4, 5, 4, 4, 4, 1, 3, 3, 4, 4, 4, 4, 0], [4, 4, 5, 4, 4, 4, 1, 3, 4, 3, 4, 4, 4, 0], [4, 4, 5, 4, 4, 4, 1, 4, 3, 3, 4, 4, 4, 0], [4, 4, 5, 4, 4, 4, 1, 4, 4, 2, 4, 4, 4, 0], [4, 4, 5, 4, 4, 4, 1, 4, 4, 3, 4, 3, 4, 0], [4, 4, 5, 4, 4, 4, 1, 4, 4, 3, 4, 4, 3, 0], [4, 4, 5, 4, 4, 5, 0, 4, 3, 4, 3, 4, 4, 0], [4, 4, 5, 4, 4, 5, 0, 4, 3, 4, 4, 3, 4, 0], [4, 4, 5, 4, 4, 5, 0, 4, 4, 2, 4, 4, 4, 0], [4, 4, 5, 4, 5, 3, 0, 3, 4, 4, 4, 4, 4, 0], [4, 4, 5, 4, 5, 3, 0, 4, 3, 4, 4, 4, 4, 0], [4, 4, 5, 4, 5, 3, 0, 4, 4, 3, 4, 4, 4, 0], [4, 4, 5, 4, 5, 3, 0, 4, 4, 4, 4, 4, 3, 0], [4, 4, 5, 4, 5, 4, 0, 4, 3, 3, 4, 4, 4, 0], [4, 4, 5, 4, 5, 4, 0, 4, 4, 2, 4, 4, 4, 0], [4, 4, 5, 4, 5, 4, 0, 4, 4, 3, 4, 4, 3, 0], [4, 4, 5, 4, 5, 4, 0, 4, 4, 4, 2, 4, 4, 0], [4, 4, 5, 5, 3, 4, 0, 3, 4, 4, 4, 4, 4, 0], [4, 4, 5, 5, 3, 4, 0, 4, 3, 4, 4, 4, 4, 0], [4, 4, 5, 5, 4, 3, 0, 3, 4, 4, 4, 4, 4, 0], [4, 4, 5, 5, 4, 3, 0, 4, 4, 4, 4, 4, 3, 0], [4, 4, 5, 5, 4, 4, 0, 3, 4, 3, 4, 4, 4, 0], [4, 4, 5, 5, 4, 4, 0, 4, 2, 4, 4, 4, 4, 0], [4, 4, 5, 5, 4, 4, 0, 4, 3, 4, 4, 3, 4, 0], [4, 4, 5, 5, 4, 4, 0, 4, 4, 3, 4, 3, 4, 0], [4, 4, 5, 5, 4, 4, 0, 4, 4, 3, 4, 4, 3, 0], [4, 4, 5, 5, 4, 4, 0, 4, 4, 4, 3, 4, 3, 0], [4, 4, 6, 4, 3, 4, 0, 4, 4, 3, 4, 4, 4, 0], [4, 4, 6, 4, 3, 4, 0, 4, 4, 4, 4, 3, 4, 0], [4, 4, 6, 4, 4, 3, 0, 3, 4, 4, 4, 4, 4, 0], [4, 4, 6, 4, 4, 3, 0, 4, 4, 3, 4, 4, 4, 0], [4, 4, 6, 4, 4, 3, 0, 4, 4, 4, 4, 4, 3, 0], [4, 4, 6, 4, 4, 4, 0, 3, 3, 4, 4, 4, 4, 0], [4, 4, 6, 4, 4, 4, 0, 3, 4, 3, 4, 4, 4, 0], [4, 4, 6, 4, 4, 4, 0, 3, 4, 4, 3, 4, 4, 0], [4, 4, 6, 4, 4, 4, 0, 4, 3, 4, 4, 3, 4, 0], [4, 4, 6, 4, 4, 4, 0, 4, 4, 2, 4, 4, 4, 0], [4, 4, 6, 4, 4, 4, 0, 4, 4, 3, 4, 3, 4, 0], [4, 4, 6, 4, 4, 4, 0, 4, 4, 3, 4, 4, 3, 0], [4, 5, 3, 4, 4, 4, 0, 4, 4, 3, 4, 4, 4, 1], [4, 5, 3, 4, 4, 4, 0, 4, 4, 3, 4, 5, 4, 0], [4, 5, 3, 4, 4, 4, 0, 4, 4, 3, 5, 4, 4, 0], [4, 5, 3, 5, 4, 4, 0, 4, 4, 3, 4, 4, 4, 0], [4, 5, 4, 4, 3, 4, 0, 4, 4, 3, 4, 4, 4, 1], [4, 5, 4, 4, 3, 4, 0, 4, 4, 3, 4, 4, 5, 0], [4, 5, 4, 4, 3, 4, 0, 4, 4, 3, 4, 5, 4, 0], [4, 5, 4, 4, 3, 4, 0, 5, 4, 3, 4, 4, 4, 0], [4, 5, 4, 4, 4, 3, 0, 4, 4, 3, 4, 4, 4, 1], [4, 5, 4, 4, 4, 3, 0, 4, 4, 3, 4, 5, 4, 0], [4, 5, 4, 4, 4, 4, 0, 4, 3, 3, 4, 5, 4, 0], [4, 5, 4, 4, 4, 4, 0, 4, 4, 3, 3, 4, 4, 1], [4, 5, 4, 4, 4, 4, 0, 4, 4, 4, 2, 5, 4, 0], [4, 5, 4, 4, 4, 4, 0, 5, 4, 3, 3, 4, 4, 0], [4, 5, 4, 4, 4, 4, 0, 5, 4, 4, 2, 4, 4, 0], [4, 5, 4, 4, 5, 3, 0, 4, 4, 3, 4, 4, 4, 0], [4, 5, 4, 4, 5, 4, 0, 4, 4, 3, 3, 4, 4, 0], [4, 5, 4, 5, 3, 4, 0, 4, 4, 3, 4, 4, 4, 0], [4, 5, 4, 5, 4, 4, 0, 4, 4, 3, 3, 4, 4, 0], [4, 5, 5, 4, 4, 4, 0, 3, 4, 3, 4, 4, 4, 0], [4, 5, 5, 4, 4, 4, 0, 4, 4, 2, 4, 4, 4, 0], [4, 5, 5, 4, 4, 4, 0, 4, 4, 3, 4, 3, 4, 0], [4, 5, 5, 4, 4, 4, 0, 4, 4, 3, 4, 4, 3, 0], [4, 6, 3, 4, 3, 4, 0, 4, 4, 4, 4, 4, 4, 0], [4, 6, 4, 4, 3, 4, 0, 4, 3, 4, 4, 4, 4, 0], [4, 6, 4, 4, 3, 4, 0, 4, 4, 3, 4, 4, 4, 0], [4, 6, 4, 4, 4, 3, 0, 4, 4, 3, 4, 4, 4, 0], [4, 6, 4, 4, 4, 4, 0, 3, 4, 3, 4, 4, 4, 0], [4, 6, 4, 4, 4, 4, 0, 4, 3, 3, 4, 4, 4, 0], [4, 6, 4, 4, 4, 4, 0, 4, 4, 2, 4, 4, 4, 0], [4, 6, 4, 4, 4, 4, 0, 4, 4, 3, 4, 3, 4, 0], [4, 6, 4, 4, 4, 4, 0, 4, 4, 3, 4, 4, 3, 0], [4, 6, 4, 4, 4, 4, 0, 4, 4, 4, 4, 2, 4, 0], [5, 3, 4, 4, 4, 4, 0, 4, 4, 3, 4, 4, 4, 1], [5, 3, 5, 4, 4, 4, 0, 3, 4, 4, 4, 4, 4, 0], [5, 3, 5, 4, 4, 4, 0, 4, 4, 4, 4, 4, 3, 0], [5, 4, 3, 4, 4, 4, 0, 4, 4, 3, 4, 4, 4, 1], [5, 4, 3, 4, 4, 4, 0, 4, 4, 3, 4, 4, 5, 0], [5, 4, 3, 4, 4, 4, 1, 4, 4, 4, 3, 4, 4, 0], [5, 4, 4, 4, 4, 3, 0, 4, 4, 4, 3, 4, 5, 0], [5, 4, 4, 4, 4, 3, 1, 4, 4, 4, 3, 4, 4, 0], [5, 4, 4, 4, 4, 4, 0, 4, 4, 2, 4, 4, 4, 1], [5, 4, 4, 4, 4, 4, 0, 4, 4, 4, 2, 4, 4, 1], [5, 4, 4, 4, 4, 4, 0, 4, 4, 4, 2, 4, 5, 0], [5, 4, 4, 4, 4, 4, 0, 4, 4, 4, 2, 5, 4, 0], [5, 4, 4, 4, 4, 4, 0, 5, 4, 4, 2, 4, 4, 0], [5, 4, 4, 5, 4, 4, 0, 4, 4, 2, 4, 4, 4, 0], [5, 4, 5, 4, 3, 4, 0, 4, 4, 4, 4, 4, 3, 0], [5, 4, 5, 4, 4, 4, 0, 2, 4, 4, 4, 4, 4, 0], [5, 4, 5, 4, 4, 4, 0, 3, 4, 4, 4, 3, 4, 0], [5, 4, 5, 4, 4, 4, 0, 4, 3, 4, 4, 4, 3, 0], [5, 4, 5, 4, 4, 4, 0, 4, 4, 4, 4, 3, 3, 0], [5, 4, 5, 4, 4, 4, 0, 4, 4, 4, 4, 4, 2, 0], [6, 4, 3, 4, 4, 4, 0, 4, 4, 3, 4, 4, 4, 0], [6, 4, 4, 4, 3, 4, 0, 4, 4, 3, 4, 4, 4, 0], [6, 4, 4, 4, 4, 4, 0, 4, 4, 3, 3, 4, 4, 0], [6, 4, 4, 4, 4, 4, 0, 4, 4, 3, 4, 3, 4, 0], [6, 4, 4, 4, 4, 4, 0, 4, 4, 4, 2, 4, 4, 0] ] class MancalaNode(GameNode): """Representation of a Mancala game tree node. How to interpret the Mancala state variable: Let the mancala pits be notated thus: _ _ _ _ _ _ _ 1 2 3 4 5 6 s s 6 5 4 3 2 1 where 6-1 are the first player's (MAX's) play pits, s is the first player's (MAX's) score pit, _ _ 6-1 are the second player's (MIN's) play pits, and _ s is the second player's (MIN's) score pit. The numbers of pieces in each pit are stored in an array as follows: state[0] ... state[6] store the number of pieces in 6, 5, 4, 3, 2, 1, and s. _ _ _ _ _ _ _ state[7] ... state[13] store the number of pieces in 6, 5, 4, 3, 2, 1, and s. Each player's goal is to end the game with more pieces in one's own _ scoring pit. Thus a simple measure of utility would be (s - s).""" # Total play pits on a player's side PLAY_PITS = 6 # Index of first (south) player score pit, that is, "kalah" MAX_SCORE_PIT = PLAY_PITS # Index of second (north) player score pit, that is, "kalah" MIN_SCORE_PIT = 2 * PLAY_PITS + 1 # Total pits including both players' play and score pits TOTAL_PITS = 2 * (PLAY_PITS + 1) # Initial number of pieces (i.e. seeds, stones, etc.) per play pit INIT_PIECES_PER_PIT = 4 # Total number of pieces in play NUM_PIECES = 2 * PLAY_PITS * INIT_PIECES_PER_PIT def __init__(self, fairkalah_state_index=-1, other=None): """Construct a copy of other, if other exists. Otherwise, construct a default initial Mancala state with MAX to play if fairkalah_state_index = -1 (default). However, if fairkalah_state_index is 0-254, construct a FairKalah initial state with MAX to play and given FairKalah board number (1-254) or 0 fairkalah_board parameter for random FairKalah board selection.""" if other: super().__init__(other) self.state = other.state.copy() else: super().__init__() if fairkalah_state_index == -1: # Place four pieces initially in each pit... self.state = [MancalaNode.INIT_PIECES_PER_PIT] * MancalaNode.TOTAL_PITS # ...except scoring pits. self.state[MancalaNode.MAX_SCORE_PIT] = self.state[MancalaNode.MIN_SCORE_PIT] = 0 elif fairkalah_state_index < -1 or fairkalah_state_index > len(fairkalah_states): raise ValueError(f'MancalaNode(int): Invalid fairkalah_state_index {fairkalah_state_index}') elif fairkalah_state_index == 0: self.state = choice(fairkalah_states).copy() else: self.state = fairkalah_states[fairkalah_state_index - 1].copy() def expand(self): """Return an list of legal successor MancalaNode objects.""" children = [] for move in self.get_legal_moves(): child = self.child_copy() child.make_move(move) children.append(child) return children def child_copy(self): child = copy.copy(self) child.state = self.state.copy() child.parent = self return child def get_legal_moves(self): """Return a list of legal play pit indices, sorted by decreasing distance from the player's score pit.""" legal_moves = [] score_pit = MancalaNode.MAX_SCORE_PIT if self.player == GameNode.MAX else MancalaNode.MIN_SCORE_PIT for i in range(score_pit - MancalaNode.PLAY_PITS, score_pit): if self.state[i] > 0: legal_moves.append(i) return legal_moves def make_move(self, move): """Make the designated move, redistributing pieces from the indicated position and updating the player accordingly.""" position = move self.prev_move = move score_pit = MancalaNode.MAX_SCORE_PIT if self.player == GameNode.MAX else MancalaNode.MIN_SCORE_PIT opponent_score_pit = MancalaNode.MIN_SCORE_PIT if self.player == GameNode.MAX else MancalaNode.MAX_SCORE_PIT # Check for illegal move if position < score_pit - self.PLAY_PITS or position >= score_pit or self.state[position] == 0: raise ValueError(f'make_move: Illegal move {move}') # Take the pieces from the indicated pit. pieces = self.state[position] self.state[position] = 0 # Redistribute them around the pits, skipping the opponent's scoring pit. while pieces > 0: position = (position + 1) % MancalaNode.TOTAL_PITS # Skip over opponent's scoring pit if position == opponent_score_pit: continue # Distribute piece self.state[position] += 1 pieces -= 1 # If the last piece distributed landed in an empty pit on one's side, # capture both the last piece and any pieces opposite. # if last piece distributed in empty pit on own side if self.state[position] == 1 and (score_pit - position) > 0 \ and (score_pit - position <= MancalaNode.PLAY_PITS): # last piece into empty play pit opposite_pit = MancalaNode.MIN_SCORE_PIT - position - 1 # capture own pit self.state[score_pit] += 1 self.state[position] = 0 # capture opposite pit self.state[score_pit] += self.state[opposite_pit] self.state[opposite_pit] = 0 # If the last piece did not land in one's scoring pit, then the player changes. if position != score_pit: self.player = GameNode.MIN if self.player == GameNode.MAX else GameNode.MAX # Check for starvation according to U.S. Patent 2,720,362, lines 54-57: # "One single game or play is ended when all of the pits on one side of # the game board are empty. All game pieces remaining in the pits on # the opposite side go into the kalah on that side." ("Kalah" refers to # the scoring pit.) # Side note: This is different from starvation rules of some Mancala games # where the first player unable to play a legal move allows their opponent # to immediately score their remaining pieces. max_play_pit_pieces, min_play_pit_pieces = 0, 0 for position in range(MancalaNode.MAX_SCORE_PIT): max_play_pit_pieces += self.state[position] min_play_pit_pieces += self.state[position + MancalaNode.MAX_SCORE_PIT + 1] if max_play_pit_pieces == 0 or min_play_pit_pieces == 0: self.state[MancalaNode.MAX_SCORE_PIT] += max_play_pit_pieces self.state[MancalaNode.MIN_SCORE_PIT] += min_play_pit_pieces for position in range(MancalaNode.MAX_SCORE_PIT): self.state[position] = 0 self.state[position + MancalaNode.MAX_SCORE_PIT + 1] = 0 def is_game_over(self): """Return whether or not all pieces are in the score pits.""" return self.state[MancalaNode.MAX_SCORE_PIT] + self.state[MancalaNode.MIN_SCORE_PIT] == MancalaNode.NUM_PIECES def utility(self): """Return an estimation of game node utility. However, if the game is over, return the actual utility. TODO: In your implementation, you should create your own subclasses of MancalaNode (e.g. class UserID1MancalaNode(MancalaNode) and UserID1MancalaNode(MancalaNode):) and implement this utility method (inheriting all others).""" return 0 # Note: This is a placeholder so that this class can be instantiated, but this should be overridden. @classmethod def move_to_string(cls, move): """Translate move integer to a move string.""" move_string = ["6", "5", "4", "3", "2", "1", "INVALID MOVE", "6", "5", "4", "3", "2", "1"] if 0 > move >= MancalaNode.MIN_SCORE_PIT: # I hate this style, but PyCharm insisted on this "simplification". return 'INVALID MOVE' return move_string[move] def pieces_remaining(self): """Returns the number of pieces not yet captured in the given MancalaNode.""" pieces = 0 for i in range(0, 6): pieces += self.state[i] for i in range(7, 13): pieces += self.state[i] return pieces def __repr__(self): """String representation of current game state. Example (initial state): 1 2 3 4 5 6 ------------------------- | | 4| 4| 4| 4| 4| 4| | | 0|-----------------| 0| | | 4| 4| 4| 4| 4| 4| | <-- ------------------------- 6 5 4 3 2 1""" s = [' _ _ _ _ _ _\n 1 2 3 4 5 6\n-------------------------\n| '] for i in range(MancalaNode.MIN_SCORE_PIT - 1, MancalaNode.MAX_SCORE_PIT, -1): s.append('|' if self.state[i] > 9 else '| ') s.append(str(self.state[i])) s.append('| |') if self.player == GameNode.MIN: s.append(' <--') s.append('\n|' if self.state[MancalaNode.MIN_SCORE_PIT] > 9 else '\n| ') s.append(str(self.state[MancalaNode.MIN_SCORE_PIT])) s.append('|-----------------|') if self.state[MancalaNode.MAX_SCORE_PIT] <= 9: s.append(' ') s.append(str(self.state[MancalaNode.MAX_SCORE_PIT])) s.append('|\n| ') for i in range(MancalaNode.MAX_SCORE_PIT): s.append('|' if self.state[i] > 9 else '| ') s.append(str(self.state[i])) s.append('| |') if self.player == GameNode.MAX: s.append(' <--') s.append('\n-------------------------\n 6 5 4 3 2 1\n') return ''.join(s) class ScoreDiffMancalaNode(MancalaNode): def utility(self): """Return an estimation of game node utility. However, if the game is over, return the actual utility. In this simple implementation, we only consider the difference between the current MAX and MIN scores.""" # TODO: In your implementation, you should create your own subclasses of MancalaNode # (e.g. class UserID1MancalaNode(MancalaNode) and UserID1MancalaNode(MancalaNode):) and implement this utility # method (inheriting all others). return self.state[MancalaNode.MAX_SCORE_PIT] - self.state[MancalaNode.MIN_SCORE_PIT] class MancalaPlayer(ABC): @abstractmethod def choose_move(self, node, ms_remaining): """This is where your code takes over as a MancalaPlayer. You must implement this method. See SimpleMancalaPlayer for an example implementation with minimax. You are given the current MancalaNode and the time remaining in milliseconds. You are to return a legal move integer. Your game clock runs until you return your legal move, so budget your time well. You can need to first create a new node of your own type (say UniqueIDMancalaNode), and have your entire search work with your own node types and thus your own evaluation function.""" pass class SimpleMancalaPlayer(MancalaPlayer): def choose_move(self, node, ms_remaining): # TODO - WARNING: This is a simple time management effort to distribute search time over course of game. # It under-utilizes time, so you should design better time management in your implementation. depth_factor = 1.3 # Made-up number from a time and system far ago in history... depth_limit = int(depth_factor * log(ms_remaining / node.pieces_remaining())) if depth_limit < 1: depth_limit = 1 # Create a minimax searcher. searcher = MinimaxSearcher(depth_limit) # Create a new copy of the input node that uses the score difference heuristic evaluation function. search_node = ScoreDiffMancalaNode(other=node) searcher.eval(search_node) return searcher.get_best_move() class HumanMancalaPlayer(MancalaPlayer): """Prompts the user for move choices with a text interface. This code assumes a game played verbose, i.e. with printing of state, etc.""" def choose_move(self, node, ms_remaining): moves = node.get_legal_moves() print('PLAYER', '1:' if node.player == GameNode.MAX else '2:', f'{round(ms_remaining / 1000)} seconds remain.') # print legal moves move_strings = [] for move in moves: move_strings.append(MancalaNode.move_to_string(move)) print(' Legal moves:', move_strings) input_move = '' legal_move = False while not legal_move: input_move = input(' Your move? ').strip() legal_move = input_move in move_strings return moves[move_strings.index(input_move)] def play_fairkalah_game(player_max=HumanMancalaPlayer(), player_min=SimpleMancalaPlayer(), game_index=0, ms_per_game=300000, verbose=True): """Play a random FairKalah game (by default with game_index) for ms_per_game milliseconds (5 minutes default) between player_max and player_min (Human vs. Simple by default). The verbose parameter controls printed game output.""" if verbose: print(type(player_max), 'vs.', type(player_min)) player = [player_max, player_min] player_ms_remaining = [int(ms_per_game / 2), int(ms_per_game / 2)] clock = StopWatch() node = ScoreDiffMancalaNode(game_index) if verbose: print(node) winner, ret_val = 'DRAW', -1 while not node.is_game_over(): # request move from current player time_remaining = player_ms_remaining[node.player] clock.reset() clock.start() move = player[node.player].choose_move(node, time_remaining) time_taken = clock.stop() # deduct time taken player_ms_remaining[node.player] -= time_taken if player_ms_remaining[node.player] < 0: if node.player == GameNode.MAX: if verbose: print('Player 1 game timer expired.') winner, ret_val = 'PLAYER 2 WINS', GameNode.MIN else: if verbose: print('Player 2 game timer expired.') winner, ret_val = 'PLAYER 1 WINS', GameNode.MAX break # update game state and display progress if verbose: print(f'Player {1 if node.player == GameNode.MAX else 2} makes move {MancalaNode.move_to_string(move)}.') child = node.child_copy() child.make_move(move) node = child if verbose: print(node) # display winner and statistics if node.is_game_over(): if node.utility() > 0: winner, ret_val = 'PLAYER 1 WINS', GameNode.MAX elif node.utility() < 0: winner, ret_val = 'PLAYER 2 WINS', GameNode.MIN else: winner, ret_val = 'DRAW', -1 if verbose: print('Time taken (ms):') print('Player 1:', int(ms_per_game / 2) - player_ms_remaining[GameNode.MAX]) print('Player 2:', int(ms_per_game / 2) - player_ms_remaining[GameNode.MIN]) print(winner) return ret_val class StopWatch: """A simple millisecond stopwatch. start() sets stopwatch measure of time elapsed. stop() adds time elapsed since previous start() to total elapsed time and returns total elapsed time. reset() resets total elapsed time. lap() returns total elapsed time without "stopping" the stopwatch.""" def __init__(self): """Reset the millisecond stopwatch.""" self.total_ms = self.start_ms = self.stop_ms = 0 def reset(self): """Reset the millisecond stopwatch.""" self.__init__() def start(self): """Start millisecond stopwatch.""" self.start_ms = current_ms_time() def lap(self): """Return millisecond stopwatch time elapsed so far.""" return (current_ms_time() - self.start_ms) + self.total_ms def stop(self): """Stop millisecond stopwatch and return total time elapsed.""" self.stop_ms = current_ms_time() self.total_ms += self.stop_ms - self.start_ms self.start_ms = self.stop_ms = 0 return self.total_ms if __name__ == "__main__": play_fairkalah_game()