text: import random
  import itertools
  
  class Expert(object):
      """
      An expert that takes a list of previous plays
      and formulates a prediction for the next move.
      """
      def __init__(self, moves):
          self.moves = moves
          self.history = []
  
      def predict(self):
          """
          Return a move prediction based on the history
          received by the expert.
          """
          raise NotImplementedError
  
      def observeMove(self, move):
          pass
  
  class RandomExpert(Expert):
      """
      An expert that picks moves entirely at random.
      """
  
      def predict(self):
          """
          Return a random move from the choices.
          """
          return random.choice(self.moves)
  
  class ConstantExpert(Expert):
      """
      An expert who always guesses the same move
      """
  
      def __init__(self, moves, move):
          Expert.__init__(self, moves)
          self.move = move
  
      def predict(self):
          """
          Return the predetermined move
          """
          return self.move
  
  class KthLastMoveExpert(Expert):
      """
      An expert who picks the k-th last move.
      If there are fewer than k moves so far,
      pick a random move.
      """
  
      def __init__(self, moves, k):
          Expert.__init__(self, moves)
          self.k = k
  
      def predict(self):
          """
          Return the k-th move from the end of the list.
          If the list is less than size k, pick randomly.
          """
          if len(self.history) <= self.k:
              return random.choice(self.moves)
          else:
              return self.history[0]
  
      def observeMove(self, move):
          self.history.append(move)
          if len(self.history) > self.k + 1:
              self.history = self.history[1:]
  
  class DeterministicSequenceExpert(Expert):
      """
      An expert who looks at the last k moves, and
      picks the move which was most often played
      after that sequence
      """
  
      def movelistToKey(self, lst):
          ret = ""
          for move in lst:
              ret += move + ","
          return ret
  
      def __init__(self, moves, k):
          Expert.__init__(self, moves)
          self.occurrences = {self.movelistToKey(moves) : 0 for moves in
                              itertools.product(moves, repeat=k+1)}
          self.k = k
          #print(self.occurrences, self.k)
  
      def predict(self):
          """
          Return the k-th move from the end of the list.
          If the list is less than size k, pick randomly.
          """
          if len(self.history) < self.k:
              return self.moves[0]
          maxMove = self.moves[0]
          maxVal = 0
          for move in self.moves:
              #print(len(self.history), self.k)
              newVal = self.occurrences[self.movelistToKey(self.history + [move])]
              if newVal > maxVal:
                  maxVal = newVal
                  maxMove = move
          return maxMove
  
      def observeMove(self, move):
          self.history.append(move)
          if len(self.history) == self.k + 1:
              self.occurrences[self.movelistToKey(self.history)] += 1
              self.history = self.history[1:]
  
  
  class NondeterministicSequenceExpert(Expert):
      """
      An expert who looks at the last k moves, and
      picks the move which was most often played
      after that sequence
      """
  
      def movelistToKey(self, lst):
          ret = ""
          for move in lst:
              ret += move + ","
          return ret
  
      def __init__(self, moves, k):
          Expert.__init__(self, moves)
          self.occurrences = {self.movelistToKey(moves) : 0 for moves in
                              itertools.product(moves, repeat=k+1)}
          self.k = k
  
      def predict(self):
          """
          Return the k-th move from the end of the list.
          If the list is less than size k, pick randomly.
          """
          if len(self.history) < self.k:
              return random.choice(self.moves)
          weights = [self.occurrences[self.movelistToKey(self.history + [move])] for move in self.moves]
          return random.choices(self.moves, weights=weights, k=1)[0]
  
  
      def observeMove(self, move):
          self.history.append(move)
          if len(self.history) == self.k + 1:
              self.occurrences[self.movelistToKey(self.history)] += 1
              self.history = self.history[1:]
  
  class WeightedLastMovesExpert(Expert):
      """
      An expert who samples a move from a weighted history.
      The last move has weight alpha,
      """
  
      def __init__(self, moves, weights):
          Expert.__init__(self, moves)
          self.weights = weights
  
      def predict(self):
          """
          Return a randomly sampled move from the history
          as the prediction, weighing the last k moves
          using the given weights, where k = len(weights).
          If the list is less than size k, pick randomly.
          """
          if len(self.history) < len(self.weights):
              return random.choice(self.moves)
          else:
              return random.choices(self.history, weights=self.weights, k=1)[0]
  
      def observeMove(self, move):
          self.history.append(move)
          if len(self.history) > len(self.weights):
              self.history = self.history[1:]
  