## Spring 2013 - Experimental Math - Pat Devlin  (I don't care about keeping my work private)
#  Homework 11 - From Class on February 28, 2013


Help:=proc():
  print(`Script to find legal moves in a backgammon game.`):
  print(`It is unclear why the parameter b is used.  It is kept as an optional parameter only to make the code meet the requirements.`):
  print(`LegalMoves(position, dice, b:=nops(position[1]), h:=6)`):
  print(`LegalMoves_Fixed_Order(position, dice, b:=nops(position[1]), h:=6)`):
  print(`can_we_do_this_move(position, piece_to_move, the_die, b:=nops(position[1]), h:=6)`):
  print(`IsBearOff(position, b:=nops(position[1]), h:=6)`):
end proc:



## Note: I completed the special challenge problem, and I "generalized" it to
#  the usual backgammon game where you roll two dice.
#  Then doubles are considered 4 of that value, and 
#  the usual backgammon rules are used to determine
#  if a move is legal (e.g., a player must use both dice if that's at all
#  possible [and all `four' for a double], but in the event that this is not
#  possible, a player must use the die with the highest value if possible, et
#  cetera)

#  My code generalizes rather naturally to rolling more than 2 dice, but the
#  rules of backgammon (what constitutes "doubles" and what dice rolls MUST
#  you use) do not!  So I did not implement this theoretical generalization.

#  (The code does however already generalize to boards of arbitrary length and such)



#############
# Problem 5 #
#############

# [Big Challenge, $20 donation to the OEIS foundation in honor of the people
# who will do it, it is OK to work in teams, and share the burden, and divide up the task]
# Finish procedure LegalMoves(POS,b,h,i) that we just started today for
# generalized Backgammon with board-size b, house-size h, where the roll (of one die) was i. 


##  We'll do some generalized backgammon!
#   We'll have 2 fair dice (r-faces), home-size h, and board-size b
#   (convention is r=6, h=6, b=24)
#   We'll have a thing   position = [L1, L2, bar1, bar2], which is:
#    where player 1's guys are [HIS home would be L1[0]]
#    where player 2's guys are [HIS home would be L2[0]]
#    how many player 1 guys are on bar (bar1)
#    how many player 2 guys are on bar (bar2)




## This function tries to have the player user ALL dice (in their given order).  If this is possible, then great.
#  But if it's not possible to use ALL the dice, then there's some care that
#  needs to be given to what is and is not a legal move.
#
#  For instance, if a player rolls  {2, 3}  and he can only use at most one
#  die, then he MUST use the 3 if possible.

LegalMoves_Fixed_Order:=proc(position, dice, b:=nops(position[1]), h:=6) local possible_moves, iter, result_of_possible_move: option remember:
  if(nops(dice)=0) then return {position}: fi:
  possible_moves:={}:
  for iter from 1 to (b+1) do   # iter is the piece we'll try to move.  The convention iter=b+1 corresponds to moving off a piece from the bar.
    result_of_possible_move:=can_we_do_this_move(position, iter, dice[1], b,h):
    if(result_of_possible_move[1]) then
      possible_moves:=possible_moves
        union LegalMoves_Fixed_Order(result_of_possible_move[2], [op(2..nops(dice), dice)],b,h):
    fi:
  od:
  return possible_moves:  # This could be empty if it's not possible to use all those dice in the order.
end proc:



## This is a wrapper function to find the set of all legal moves.  It could be
#  empty in the event that a player has no legal moves (in which case his turn is thrown away)

LegalMoves:=proc(position, roll, b:=nops(position[1]), h:=6) local moves, iter: option remember:  # This is currently only good for two dice rolled [which makes sense]
  if(nops(roll) < 2) then return LegalMoves_Fixed_Order(position, [op(roll)], b, h): fi: # This shouldn't ever happen

  if(roll[1] = roll[2]) then  # Rolled doubles!
    for iter from 0 to 3 do  # This silly for loop is to see how many dice you can actually use
      moves:=LegalMoves_Fixed_Order(position, [roll[1]$(4-iter)], b, h):
      if(not(moves = {})) then return moves: fi:  # This checks "if it was possible to use a bunch of dice, then do that!"  (Otherwise, try with fewer dice)
    od:
    return {}:
  fi:

  moves:=LegalMoves_Fixed_Order(position, [roll[1], roll[2]], b, h) union LegalMoves_Fixed_Order(position, [roll[2], roll[1]], b, h): # Try to use both dice (which must be different since we got here)
  if(not(moves ={})) then return moves: fi:  # If you COULD use both dice, then those are the only legal moves

  moves:=LegalMoves_Fixed_Order(position, [max({op(roll)})], b, h): # We couldn't use both dice, so try to use just the bigger die [as forced by rules]
  if(not(moves={})) then return moves: fi: # If we CAN use the bigger die, then those are the only legal moves
  return LegalMoves_Fixed_Order(position, [min({op(roll)})], b, h): # Try to use the smaller die, which is the only remaining possibility

end proc:



##  Given inputs of position (with convention as above), an integer for what
#   piece we're trying to move,  an integer for how many spaces over we're
#   trying to move that piece,  and optional parameters of boardsize and home size,
#
#   it returns whether or not player 1 can move that piece in question, and
#   what the position would look like after that move
#
#   Output is of the form   [bool,  POS],  where bool is a boolean for if the
#   move is legal, and POS is what the resulting position would be

can_we_do_this_move:=proc(position, piece_to_move, the_die, b:=nops(position[1]),h:=6) local landing_spot_L1, landing_spot_L2:


  if((position[3]>0) and (not (piece_to_move > b))) then return [false, position]: fi: # If there's a guy on the bar, then no, you can't move something else!
  if((piece_to_move<1) or (the_die<1)) then return [false, position]: fi: # making sure we don't try to move from a spot that doesn't exist

  if(piece_to_move >b) then #if we're trying to move a guy from the bar...

    if(position[3]<=0) then return [false, position]: fi: # if you don't have anybody on the bar

    if(the_die>b) then  # if the die roll is SO big that you can move the guy from the bar directly off the board [then I say you're allowed to do so iff he's the only guy not already in the home]
      if(IsBearOff([position[1], position[2], position[3]-1, position[4]],b,h)) then #if that guy on bar is the ONLY guy not in home
        return [true, [position[1], position[2], position[3]-1, position[4]]]:
      fi:
      return [false, position]:
    fi:

    if( (position[2])[the_die] < 2) then # if the spot the guy on bar is aiming for is open...
      return [true,
        [
          [op(1..(nops(position[1])-the_die),position[1]), position[1][nops(position[1])-the_die+1]+1, op((nops(position[1])-the_die+2)..nops(position[1]), position[1])],
          [op(1..(the_die-1),position[2]), 0, op((the_die+1)..nops(position[2]), position[2])],
          position[3]-1, position[4]+position[2][the_die]
        ]]:
    fi:
    return [false, position]:
  fi:


  # Since we got here, that means that we're trying to move some guy not from the bar

  if(position[1][piece_to_move]<=0) then return [false, position]: fi: # this is we're trying to move from a spot that has nobody on it


  if(the_die >= piece_to_move) then  # then we're trying to bear off
    if( not (IsBearOff(position, b,h))) then return [false, position]: fi:
    if((piece_to_move = the_die) or (max({op((piece_to_move+1)..nops(position[1]),position[1])}) <= 0)) then
      return [true,
        [
          [op(1..(piece_to_move-1), position[1]), position[1][piece_to_move]-1, op((piece_to_move+1)..nops(position[1]), position[1])],
          position[2], position[3], position[4]
        ]]:
    fi:
    return [false, position]:
  fi:


  # Since we got here, that means we're trying to move a guy not from the bar,
  # and we're not trying to bear off
  landing_spot_L1:= piece_to_move - the_die:
  landing_spot_L2:= 1 + nops(position[2]) - landing_spot_L1:

  if(position[2][landing_spot_L2] < 2) then
    return [true,
      [
          [op(1..(landing_spot_L1-1), position[1]),
            position[1][landing_spot_L1]+1,
            op((landing_spot_L1+1)..(piece_to_move-1),position[1]),
            position[1][piece_to_move]-1,
            op((piece_to_move+1)..nops(position[1]), position[1])
          ],
          [op(1..(landing_spot_L2-1),position[2]), 0, op((landing_spot_L2+1)..nops(position[2]), position[2])],
          position[3], position[4]+position[2][landing_spot_L2]
        ]]:

  fi:
  return [false, position]:

end proc:




## IsBearOff returns true iff player 1 is able to start bearing off

IsBearOff:=proc(position, b:=nops(position[1]), h:=6):
  if(position[3]>0) then return false: fi: # this is false because player 1 has pieces on the bar
  if(h+1>nops(position[1])) then return true: fi:
  if(max({op((h+1)..nops(position[1]),(position[1]))}) <= 0) then return true: fi:
  return false:
end proc: