chopsticks solution

chopsticks.py

"""
Solution for the game chopsticks (http://en.wikipedia.org/wiki/Chopsticks_(hand_game)) with even splitting only
Requrements: collections-extended

Future work:
  - find subset of tree where the game halts
  - remove "dumb moves", i.e. moves where a player COULD win but doesn't
  - investigate deterministic lines, e.g. when the "only intelligent" move leads on a deterministic path
  - investigate avoiding "dumb moves" with lookahead
"""

#!/usr/bin/env python3
from collections_extended import frozenbag
from functools import reduce

def newstate(*args):
  "State for 1 player"
  return frozenbag(args)

class Node:
  '''One game move.
  board: a tuple of 2 states containing 2 ints between 0 and 4 (inc).
    player1 is item 0, player2 is item1
  active_player: True -> player1, False -> player2
  children: a list of following game states
  '''
  def __init__(self, board, active_player, path=None, children=None):
    self.board = board
    self.active_player = active_player
    self.path = path + [self] if path else [self]
    self.children = children if children else []
    self.winner = None

  def __repr__(self):
    return "{}(board=({{{}}}, {{{}}}), active_player={}, children=({})), winner={})".format(
      self.__class__.__name__,
      ', '.join(map(str, self.board[0])),
      ', '.join(map(str, self.board[1])),
      1 if self.active_player else 2,
      len(self.children),
      "{{1: {}, 2: {}}}".format(self.winner[True], self.winner[False]) if self.winner else None
    )

class ReferenceNode:
  '''A reference to a sequence of plays that has already been explored.
  node: reference to actual node where play tree is
  winner: the results of the explored tree
  '''
  def __init__(self, node):
    self.node = node
    self.winner = None

  def __repr__(self):
    return "{}({})".format(self.__class__.__name__, repr(self.node))

def can_tap(hand1, hand2):
  "Can hand1 tap hand2?"
  return hand1 != 0

def tap_result(hand1, hand2):
  result = hand1 + hand2
  return result if result < 5 else 0

def can_split(state):
  "Is splitting a valid move?"
  #     1 hand is 0           other hand != 0             other hand is even
  return 0 in state and state.num_unique_elements() > 1 and max(state) % 2 == 0

def split(state):
  "Return a split move. Depends on can_split(state) == True"
  return newstate(*([max(state)/2] * 2))

def finished(state):
  "Is the game over?"
  return state == newstate(0, 0)

def moves(off_state, def_state):
  '''Return a list of boards after all valid moves.
  off_state: state of the offensive player2
  def_state: state of the defensive player
  '''
  results = []
  for hand1 in off_state:
    for hand2 in def_state:
      if can_tap(hand1, hand2):
        new_hand2 = tap_result(hand1, hand2)
        results.append((off_state, def_state - newstate(hand2) + newstate(new_hand2)))
  
  if can_split(off_state):
    results.append((split(off_state), def_state))

  return results

def play():
  #count = 0
  root = Node((newstate(1, 1), newstate(1, 1)), True)
  unprocessed = [root]
  reached = {root.board: root}

  #while unprocessed and count <= 10:
  while unprocessed:
    current_node = unprocessed.pop()
    if isinstance(current_node, ReferenceNode):
      continue

    board = current_node.board if current_node.active_player else tuple(reversed(current_node.board))
    
    if finished(board[0]):
      # if the game is done and it's my turn, you won
      current_node.winner = {current_node.active_player: 1, not current_node.active_player: 0}
      continue

    for move in moves(*board):
      if move in reached:
        current_node.children.append(ReferenceNode(reached[move]))
      else:
        new_node = Node(
          move if current_node.active_player else tuple(reversed(move)),
          not current_node.active_player,
          current_node.path
        )
        reached[move] = new_node
        current_node.children.append(new_node)

    unprocessed.extend(current_node.children)

    # count += 1

  return root

#------------Analysis----------------
def avg(dict1, dict2):
  "Return a key-by-key average of 2 dicts(key: number)"
  assert dict1.keys() == dict2.keys()
  return {k: (dict1[k] + dict2[k])/2 for k in dict1.keys()}

def bubble(node):
  "bubble win chances from leaves up their branches"
  if isinstance(node, ReferenceNode):
    if node.node.winner:
      print('dereferenced')
      node.winner = node.node.winner
    return

  a=1
  # if any(isinstance(c, Node) and c.winner is not None for c in node.children):
  #   import pudb; pudb.set_trace()

  todo = [child for child in node.children if child.winner is None]
  for child in todo:
    bubble(child)  #recurse

  #at this point, we've recursed fully and the only nodes with winner==None are those that recurse infinitely.
  children = [c.winner for c in node.children if c.winner is not None]
  if children:
    oldwinner = node.winner
    node.winner = reduce(avg, children)
    if node.winner != oldwinner: print("Changed: " + repr(node))


def walk(node, filterfn):
  if filterfn(node): yield node

  if not isinstance(node, ReferenceNode):
    for c in node.children:
      yield from walk(c, filterfn)


has_nowinner_refnode = lambda n: isinstance(n, ReferenceNode) and n.winner is None
has_nowinner = lambda n: n.winner is None
is_leaf = lambda x: hasattr(x, 'children') and len(x.children)==0

if __name__ == '__main__':
  root = play()

  ended = set(walk(root, is_leaf))
  bubble(root)

  # print(len(list(walk(root, is_nowinner))))
  # bubble(root)
  # print(len(list(walk(root, is_nowinner))))
  
  # parent = root
  # while True:
  #   if isinstance(parent, ReferenceNode):
  #     parent = parent.node
  #   elif parent.children:
  #     print(parent.board, parent.active_player)
  #     parent = parent.children[0]
  #   else:
  #     break