# Dice of Doom Game in Elixir, Optimized Version 1, Human & AI Players
# EXPERIMENTAL USE OF AGENTS NOT FULLY SUCCESSFUL
# CSci 556: Multiparadigm Programming, Spring 2015
# H. Conrad Cunningham, Professor
# Computer and Information Science
# University of Mississippi

#234567890123456789012345678901234567890123456789012345678901234567890

# 2015-02-27: Began development following Land of Lisp
# 2015-03-01: Prototyped eager version with human players only
# 2015-03-08: Prototyped eager version with AI opponent
# 2015-03-12: Added use of Agent to memoize neighbors function;
#             Cleaned the code in various ways and added comments

# This Elixir game program implements the functionality of the Dice of
# Doom program, version 1, described in Chapter 15 (Dice of Doom, A
# Game Written in a Functional Style) of the book: Conrad Barski,
# _Land of Lisp: Learn to Program in Lisp, One Game at a Time_, No
# Starch Press, 2011.  See that chapter for more information about
# this game.

# I structured this Elixir program to use a set of functions similar
# modeled on Barski's Common Lisp functions, but the Elixir
# implementations of the functions differ considerably from the Common
# Lisp implementations. 

# The data structures in this Elixir program are similar to those in
# the Common Lisp program, except tailored to Elixir.  In general,
# Elixir tuples replace the fixed length Common Lisp lists used
# several places in the Land of Lisp program. In particular, this
# Elixir program represents:

# the players by nonnegative integers assigned consecutively from 0
#   (but which are printed as lowercase alphabetic characters
#   beginning with "a").  This is the same as in the Land of Lisp
#   version.

# the game "board" by a grid of hexagons with each hexagon indexed by
#   an integer in the range from 0 to board_hexnum - 1. This is the
#   same as the Land of Lisp version.

#   The board uses an Elixir Dict (i.e., map) instead of a Common
#   Lisp array.

#   The value stored for each hexagon is an Elixir tuple
#   pairing the player owning the hexagon with the number of dice at
#   that location.

# the "game tree" by a three-component tuple consisting of the current
#   player, the current game board, and a list of possible moves from
#   this configuration.  This is the same general structure as the
#   Land of Lisp version.

#   Each entry on the set of possible moves consists of a tuple paring
#   the move with the resulting game tree.  The move itself is denoted
#   by a tuple paring the source and destination hexagon indexes.

#   a nil for the move represents a pass.

# This implements a very limited, two-layer game, as does the Land of
# Lisp version 1 program.

# NOTE ON MEMOIZATION

# The optimizations of the neighbors, game_tree, and rate_position
# functions in Land of Lisp, Chapter 15, use the memoization
# technique. This technique stores previously computed values of the
# function to avoid recomputing them when the function is called again
# with the same arguments.

# In particular, the approach in Land of Lisp introduces a new
# (memoized) version of the function that wraps the original
# (non-memoized) version.  The new function has a mutable hash table
# in its closure.  The function first checks whether desired result is
# in the hash table.  If so, it simply returns it.  If not, it calls
# the original version of the function to compute the result and also
# stores it in the hash table. The hash table retains its value from
# one call of the function to the next.

# Unfortunately, Elixir does not directly support this approach.  The
# only way to retain state is to use an Elixir/Erlang process
# (actor). This approach probably works well in situations where small
# amounts of data need to be communicated among the processes (i.e.,
# the function's arguments and return values), but it likely does not
# work well when large data structures must be passed

# This Elixir program uses a process (specifically, an Agent) to
# implement the memoization of the neighbors function.  A similar
# approach does not seem effective in memoizing the game_tree and
# rate_position functions, which involve large data structures.


# Module Neighbors encapsulates an agent that caches lists of neighbor
# hexagons for any hexagon on the Dice of Doom game board. This agent
# is used to memoize the Dice of Doom function neighbors.
# Neighbors.start_link must be called to initialize the agent.

defmodule Neighbors do
  @name __MODULE__

  def start_link do
    Agent.start_link(fn -> HashDict.new end, name: @name)
  end

  def set_neighbors(pos,nabors) do
    Agent.update(@name, &(Dict.put(&1,pos,nabors)))
  end

  def get_neighbors(pos) do
    Agent.get(@name, &Dict.get(&1,pos))
  end

end


# Module GameTrees encapsulates an agent that caches game trees
# corresponding to game configurations. This agent is used to memoize
# the Dice of Doom function game_tree.  GameTrees.start_link must be
# called to initialize the agent.

defmodule GameTrees do
  @name __MODULE__

  def start_link do
    Agent.start_link(fn -> HashDict.new end, name: @name)
  end

  def set_tree(config,tree) do
    Agent.update(@name, &(Dict.put(&1,config,tree)),20000)
  end

  def get_tree(config) do
    Agent.get(@name, &Dict.get(&1,config))
  end

end


# Module Dice1 -- main module for Dice of Doom Version 1
# Includes experimental modification for use of Agents.

defmodule Dice1 do

  # Set game size constants
  @num_players  2
  @max_dice     3
  @board_size   3
  defp board_hexnum do @board_size * @board_size end

  # Create an empty new board, which must be a Dict.
  def new_board() do HashDict.new end

  # Generate a random board. This directly uses Erlang :random module.
  def gen_board() do
    Enum.into(0..board_hexnum-1, new_board(),
      fn n -> { n, { :random.uniform(@num_players)-1,
                     :random.uniform(@max_dice)      } } end) 
  end

  # Map player integer identifier to matching lowercase letter.
  def player_letter(n) do
    String.at("abcdefghijklmnopqrstuvwxyz",n)
  end

  # Print the game board as text.
  def draw_board(board) do
    IO.puts board_as_string(board)
  end

  # board_as_string was factored out of draw_board.
  def board_as_string(board) do
    Enum.map_join(0..@board_size-1, "\n",
      fn y ->
        String.duplicate("  ",@board_size-y) <>
        (Enum.map_join(0..@board_size-1,
          fn x -> {p,d} = board[x + (@board_size * y)]
                  "#{player_letter(p)}-#{d} "
          end))
      end)
  end

  # Generate a game tree for the current game configuration. Boolean
  # argument first_move indicates whether this is the player's first
  # move (in which passing is not allowed). This memoized version uses
  # an Agent to cache the previously calculated game trees.
  
  def game_tree(board, player, spare_dice, first_move) do
    # b = Dict.to_list(board) |> List.keysort(0)
    config = {board,player,spare_dice,first_move}
    moves  = GameTrees.get_tree(config)
    if moves != nil do
      {player,board,moves}
    else
      new_tree = orig_game_tree(board,player,spare_dice,first_move)
      {_,_,ms} = new_tree
      GameTrees.set_tree(config,ms)
      new_tree
    end
  end
  
  # Original game_tree function memoized above. It builds and returns
  # a game tree for the given game configuration. 
  
  defp orig_game_tree(board, player, spare_dice, first_move) do
    { player,
      board,
      add_passing_move(board, player, spare_dice, first_move,
                       attacking_moves(board, player, spare_dice))
    }
  end

  # Add a passing move (nil) to the list of possible moves if allowed.
  def add_passing_move(_,_,_,true,moves) do
    moves  # first_move argument true, cannot pass
  end
  
  def add_passing_move(board,player,spare_dice,_,moves) do
    # first_move argument false, can pass
    [ { nil, game_tree(add_new_dice(board, player, spare_dice-1),
                       rem(player+1,@num_players), 0, true       ) }
      | moves ]
  end

  # Add all attaching moves for the current board, player, and spare
  # dice configuration.
  
  def attacking_moves(board, cur_player, spare_dice) do
    Enum.filter_map(board,
      fn {_,{p,_}} -> p == cur_player end,
      fn {src,{p0,d0}} ->
        Enum.map(neighbors(src),&({&1,board[&1]}))
        |> Enum.filter_map(
            fn {_,{p1,d1}} -> p0 != p1 and d0 > d1 end,
            fn {dst,{_,d1}}->
              { {src,dst}, 
                game_tree(
                  board_attack(board,cur_player,src,dst,d0),
                  cur_player, spare_dice + d1, false )      }
            end
          )
      end)
    |> Enum.concat()
  end
  
  # Return a list of all neighbors of hexagon pos on the board. This
  # memoized version uses an Agent to cache the previously calculated
  # lists.  
  
  def neighbors(pos) do
    nabors = Neighbors.get_neighbors(pos)
    if nabors != nil do
      nabors
    else
      new_nabors = orig_neighbors(pos)
      Neighbors.set_neighbors(pos,new_nabors)
      new_nabors
    end
  end

  # Original neighbors function memoized above. It calculates and
  # returns a list of all neighbors of hexagon pos in the board.
  
  defp orig_neighbors(pos) do
    up   = pos - @board_size
    down = pos + @board_size
    up_left =
      if pos >= @board_size and rem(pos,@board_size) != 0
      do [up-1] else [] end 
    up_right  =
      if pos >= @board_size do [up] else [] end
    left =
      if rem(pos,@board_size) != 0 do [pos-1] else [] end
    right =
      if rem(pos+1,@board_size) != 0 do [pos+1] else [] end

    down_left =
      if pos < (board_hexnum - @board_size)
      do [down] else [] end
    down_right =
      if  pos < (board_hexnum - @board_size) and
          rem(pos+1,@board_size) != 0
      do [down+1] else [] end
    up_left ++ up_right ++ left ++ right ++ down_left ++ down_right
  end
  
  # Update game board based on results of attack from src to dst.
  def board_attack(board, _, src, dst, dice) do
    {p0,_} = board[src]
    board |> Dict.put(src,{p0,1}) |> Dict.put(dst,{p0,dice-1})
  end

  # Redistribute the dice to the capturing player.
  def add_new_dice(board,player,spare_dice) do
    changes =
      Enum.filter_map(board,
          fn {_,{p,d}} -> p == player and d < @max_dice end,
          fn {i,{p,d}} -> {i,{p,d+1}} end)
        |> Enum.take(spare_dice)
        |> Enum.into(new_board())
    Dict.merge(board,changes)
  end

  # The code below is for human players,

  # Main game loop for only human players.
  def play_vs_human(tree) do
    print_info(tree)
    {_,board,moves} = tree
    case moves do
      [] -> IO.puts announce_winner(board)
      _  -> play_vs_human(handle_human(tree))
    end
  end

  # Print current player and game board.
  def print_info(tree) do
    {player,board,_} = tree
    IO.puts "\nCurrent player = #{player_letter(player)}"
    draw_board(board)
  end

  # Display menu, get move selection from human player, and move to
  # the new configuration by returning the new game tree.
  
  def handle_human(tree) do
    {_,_,moves} = tree
    menu = Enum.zip(1..board_hexnum,moves)
             |> Enum.map_join("\n",
                  fn {n, {{src,dst},_}}-> "#{n}:  #{src} -> #{dst}"
                     {n, {nil,_}}      -> "#{n}:  end turn"
                  end)
    IO.puts menu
    sel = IO.gets("Choose your move:  ")
            |> String.strip
            |> String.downcase
            |> String.split(" ", trim: true)
            |> List.first
            |> String.to_integer
    selmove =
      if sel < 0 or sel > length(moves) do
        IO.puts "Invalid choice #{sel}. Forcing choice 1."
        0
      else
        sel-1
      end
    moves |> Enum.at(selmove) |> elem(1)
  end

  # Return a list of winners.
  def winners(board) do
    init = List.duplicate(0,@num_players)
    sums = Enum.reduce(board,init,
             fn {_,{p,_}}, acc -> List.update_at(acc,p,&(&1+1)) end)
    best = Enum.max(sums)
    Enum.zip(0..(@num_players-1),sums)
      |> Enum.filter_map(&(elem(&1,1) == best),&(elem(&1,0)))
  end

  # Return a string to announce the list of winners.
  def announce_winner(board) do
    w = winners(board)
    if length(w) > 1 do
      "The game is a tie among: " <>
        Enum.map_join(w,", ", &("#{player_letter(&1)}"))
    else
      "The winner is #{player_letter(List.first(w))}"
    end
  end

  # The code below adds the AI player.

  # Rate a possible move using the minimax algorithm.
  def rate_position(tree, player) do
    {p1,board,moves} = tree
    case moves do
      [_|_] -> if p1 == player do
                 Enum.max(get_ratings(tree,player))
               else
                 Enum.min(get_ratings(tree,player))
               end
      _    ->  w = winners(board)
               if Enum.member?(w,player) do 1/length(w) else 0 end
    end
  end

  # Return a list of the numeric ratings for all possible moves.
  def get_ratings(tree, player) do
    {_,_,moves} = tree
    Enum.map(moves, fn {_,t} -> rate_position(t,player) end)
  end

  # Select best rated move for the AI player. Return the new game
  # tree.
  
  def handle_computer(tree) do
    {player,_,moves} = tree
    ratings     = get_ratings(tree,player)
    bestrating  = Enum.max(ratings)
    bestindex   = Enum.find_index(ratings,&(&1 == bestrating))
    {m,newtree} = Enum.at(moves,bestindex)
    case m do
      nil       -> IO.puts "Computer passes."
      {src,dst} -> IO.puts "Computer moves #{src} -> #{dst}."
    end
    newtree
  end              

  # Main game loop for game with an AI player.
  def play_vs_computer(tree) do
    print_info(tree)
    {player,board,moves} = tree
    cond do
      moves == [] -> IO.puts announce_winner(board)
      player == 0 -> play_vs_computer(handle_human(tree))
      true        -> play_vs_computer(handle_computer(tree))
    end
  end

  # Textual user interface to overall game.  There is no equivalent in
  # Land of Lisp code.

  def play_game() do
    GameTrees.start_link
    Neighbors.start_link
    board = gen_board
    draw_board(board)
    IO.puts "Building game tree.  Please be patient."
    tree  = game_tree(board,0,0,true)
    ans   = IO.gets("Play against computer? ('y' or 'n') ")
              |> String.strip
              |> String.downcase
              |> String.split(" ", trim: true)
              |> List.first
    case ans do
      "y" -> play_vs_computer(tree)
      "n" -> play_vs_human(tree)
      _   -> IO.puts "Invalid input '#{ans}'. Playing against human."
             play_vs_human(tree)
    end
  end

end