#!/usr/local/bin/ruby -w

require 'optparse'
require 'ostruct'

require 'yaml'

DefaultPileSize = 10

class NimMove
    attr_reader :pieces

    def initialize(pieces)
        case pieces
            when 1, 2
                @pieces = pieces
            else
                raise StandardError, "Must choose 1 or 2 pieces"
        end
    end

    def eql? other
        pieces == other.pieces
    end

    def == other
        self.eql? other
    end

    def resigns?
        false
    end
end

class NimResignMove
    def resigns?
        true
    end
end

class NimGame
    attr_accessor :pieces, :players, :indexOfNextPlayerToMove, :debugInfo

    def initialize player0, player1, pieces = DefaultPileSize
        @pieces = pieces
        @players = [player0, player1]
        @indexOfNextPlayerToMove = 0
        @debugInfo = ""
    end

    def eql? other
        pieces                      == other.pieces     &&
        players                     == other.players    &&
        indexOfNextPlayerToMove     == other.indexOfNextPlayerToMove
    end

    def == other
        self.eql? other
    end
    
    def clone
        theClone = super
        theClone.players = players.clone
        theClone.debugInfo = debugInfo.clone
        theClone
    end

    def nextPlayerToMove
        @players[@indexOfNextPlayerToMove]
    end

    def previousPlayerToMove
        @players[1 - @indexOfNextPlayerToMove]
    end

    def transferFundsFromLoserToWinner
        winner  = nextPlayerToMove
        loser   = previousPlayerToMove

        loser.pay winner, 1
    end

    def applyMove! move
        if move.resigns?
            @pieces = 0
        elsif moveIsValid? move
            @pieces -= move.pieces
        else
            raise StandardError, "Illegal move."
        end

        nextTurn

        if isOver?
            transferFundsFromLoserToWinner
        end
    end

    def moveIsValid? move
        move.pieces <= pieces
    end

    def isOver?
        pieces <= 0
    end

    def exchangePlayer(newPlayer, price)
        newPlayer.pay nextPlayerToMove, price

        @players[@indexOfNextPlayerToMove] = newPlayer
    end
    
    def nextTurn
        @indexOfNextPlayerToMove = 1 - @indexOfNextPlayerToMove
    end

    def askPlayerToMove
        nextPlayerToMove.makeMove self
    end
end

class MoveStrategy
    # Abstract class

    def MoveStrategy.header_for_to_s
        "Pieces\t"
    end
end

class FixedMoveStrategy < MoveStrategy
    attr_reader :piecesToTake

    def initialize piecesToTake
        @piecesToTake = piecesToTake
    end

    def to_s
        "#{@piecesToTake}\t"
    end

    def getMove nimGame
        nimGame.pieces >= @piecesToTake ? NimMove.new(@piecesToTake) : NimMove.new(1)
    end
end

class ResignGameStrategy < MoveStrategy
    def getMove nimGame
        NimResignMove.new
    end
end

class AlwaysBidStrategy
    def getBid nimGame
        0.5
    end
end

class NeverBidStrategy
    def getBid nimGame
        nil
    end
end

class FixedPositionBidStrategy
    attr_reader  :positionToBidOn

    def initialize positionToBidOn, bidAmount
        @positionToBidOn    = positionToBidOn
        @bidAmount          = bidAmount
    end

    def FixedPositionBidStrategy.header_for_to_s
        "Amount\tPos\t"
    end

    def to_s
        alignedPositionToBidOn = sprintf("%2d", @positionToBidOn)

        "#{@bidAmount}\t#{alignedPositionToBidOn}\t"
    end

    def getBid nimGame
        nimGame.pieces == @positionToBidOn ? @bidAmount : nil
    end
end

class Player
    attr_accessor :funds, :moveStrategy, :bidStrategy, :lastAuctionWon

    def initialize(moveStrategy, bidStrategy, funds = 0)
        @bidStrategy    = bidStrategy
        @moveStrategy   = moveStrategy
        @funds          = funds
        @lastAuctionWon = -1
    end

    def pay(otherPlayer, amount)
        @funds -= amount
        otherPlayer.funds += amount
    end

    def roundedFunds
        sprintf("%5.2f", @funds)
    end

    def Player.header_for_to_s
        # We play spacing games to get things to line up with tabs set to 8.
        # We use tabs so that we can paste the output into Excel.
        bidHeader  = FixedPositionBidStrategy.header_for_to_s
        moveHeader = MoveStrategy.header_for_to_s

        "Player ID       \t#{bidHeader}#{moveHeader}Funds\n"
    end

    def to_s
        result = "#{super.to_s.gsub(/[<>]/, '')}  \t#{@bidStrategy}#{@moveStrategy}#{roundedFunds}"
        result.delete! '#'
        result
    end

    def getMove nimGame
        @moveStrategy.getMove nimGame
    end

    def bid nimGame
        funds > 0 ? @bidStrategy.getBid(nimGame) : nil
    end
    
    def makeMove nimGame
        move = getMove nimGame
        nimGame.applyMove! move
    end
end

class Shill < Player
    def initialize
        super ResignGameStrategy.new, NeverBidStrategy.new
    end

    def to_s
        myName = Object.instance_method( :to_s ).bind( self ).call
        myName.delete! '#'
        "#{myName}       \t\t\t\t#{roundedFunds}"
    end
end

# This is a helper class for GameShell.  We need to come up
# with a better name.
class GameHandler
    attr_reader :gameCount, :games, :auctioneer, :debugInfo

    def initialize(auctioneer)
        @auctioneer = auctioneer
        @games      = []
        @gameCount  = 0
        @debugInfo  = ""
    end
    
    def doOneMove
        nimGame = @games.pop

        winningBidders, winningBid = @auctioneer.conductAuction nimGame
		# Most auctioneer tie break strategies return 0 or 1 winning bidder.
		
        if winningBidders.empty?
            winningBidders  = [nimGame.nextPlayerToMove]
            winningBid      = 0
        end

		# The AwardTiesToAllBiddersStrategy can return more than one player
		# (up to 2) so in this case the game may be cloned multiple times.
        winningBidders.each { | player |
            newGame = nimGame.clone
            @gameCount += 1

            newGame.debugInfo << "#{newGame.pieces}\t#{winningBid}\t#{player}\n"

            newGame.exchangePlayer player, winningBid

            newGame.askPlayerToMove
            
            if newGame.isOver?
                debugInfo << newGame.debugInfo << "\n"
            else
                games.push newGame
            end
        }

        # Because nimGame is about to be garbage collected -- only its
        # clone or clones live on.
        @gameCount -= 1
    end

    def startAuction nimGame
        @gameCount += 1

        @games.push nimGame

        while ! @games.empty?
            doOneMove
        end
    end
end

class Auctioneer
    attr_reader :players

    def initialize(tieBreakStrategy = FirstInListTieBreakStrategy.new)
        @tieBreakStrategy   = tieBreakStrategy
        @players            = []
    end

    def registerPlayer player
        @players << player
    end

    def playerResources
        @players.collect { | player | player.funds }
    end

    def conductAuction game
        highBid  = nil

        highBidders = []

        @players.each { | player |
            bid = player.bid game

            if !bid.nil? && ( highBid.nil? or bid >= highBid )
                highBid = bid
                highBidders << player
            end
        }

        winningBidders = @tieBreakStrategy.chooseWinner highBidders
        
        [winningBidders, highBid]
    end
end

class FirstInListTieBreakStrategy
    def chooseWinner highBidders
        highBidders.empty? ? [] : [highBidders[0]]
    end
end

class BreakTiesByLotStrategy
    def chooseWinner highBidders
        highBidders.empty? ? [] : [highBidders[rand(highBidders.length)]]
    end
end

class BreakTiesByTimeStrategy
    @@serialNumber = 0

    def chooseWinner highBidders
        if highBidders.empty?
            []
        else
            # The Player who won an auction least recently will be first in the list.
            # If none has ever won an auction we don't care which is first.
    
            @@serialNumber += 1
    
            highBidders.sort! { |x, y| x.lastAuctionWon - y.lastAuctionWon }
    
            winningBidder = highBidders[0]
            
            winningBidder.lastAuctionWon = @@serialNumber
    
            [winningBidder]
        end
    end
end

class AwardTiesToAllBiddersStrategy
    def chooseWinner highBidders
        highBidders
    end
end

class CommandLineHandler
    def CommandLineHandler.executeCommandLine args
        options = NimOptions.parse(args)
        GameShell.executeCommandOptions(options)
    end
end

class GameShell
    attr_reader :handler, :initialPileSize
    attr_accessor :auctioneer

    def initialize(tieBreakStrategy = FirstInListTieBreakStrategy.new, initialPileSize = DefaultPileSize)
        @auctioneer = Auctioneer.new tieBreakStrategy
        @handler     = GameHandler.new auctioneer

        @p1 = Shill.new
        @p2 = Shill.new
        
        @initialPileSize = initialPileSize

        setUpPlayers
    end

    def setUpPlayers
        for stonesToTake in 1..2
            moveStrategy = FixedMoveStrategy.new(stonesToTake)

            for position in 1..@initialPileSize
                # Initially we tried 'for amount in [0.30, 0.60]'
                # This proved unnecessary.
                amount       = 0.60

                bidStrategy  = FixedPositionBidStrategy.new position, amount
                initialFunds = 1

                player = Player.new(moveStrategy, bidStrategy, initialFunds)

                @auctioneer.registerPlayer player
            end
        end
    end

    def executeOneGame
        @handler.startAuction(NimGame.new(@p1, @p2, @initialPileSize))
    end

    def eachPlayer 
        yield @p1
        yield @p2
        
        @auctioneer.players.each { | player | yield player }
    end

    def showPlayerResources
        s = ''

        s << Player.header_for_to_s

        s << @p1.to_s.gsub(/[<>]/, '') << "\n"
        s << @p2.to_s.gsub(/[<>]/, '') << "\n\n"

        @auctioneer.players.each { | player |
            s << player.to_s << "\n"
        }

        s
    end
    
    def moveForDisplay winningBidders
        if winningBidders.empty?
            "x"
        else
            winningBidders[0].moveStrategy.piecesToTake.to_s
        end
    end
    
    def moveForPileSize pileSize
        game = NimGame.new nil, nil, pileSize
        winningBidders, winningBid =
            @auctioneer.conductAuction game

        moveForDisplay(winningBidders)
    end

    def showMovesForEachPosition
        s =  "Position:  "
        for stones in 1..@initialPileSize
            s << "#{stones} "
        end
        s << "\n"
        s << "    Move:  "

        for stones in 1..@initialPileSize
            s << moveForPileSize(stones)

            digits = stones.to_s.length

            digits.times { s << " " }
        end

        s << "\n"

        s
    end
    
    def GameShell.didLearn oldPlayerResources, newPlayerResources
        return true if oldPlayerResources.length != newPlayerResources.length

        oldPlayerResources.each_index { |i|
            return true if newPlayerResources[i] < oldPlayerResources[i]
        }
        
        return false
    end

    def executeManyGames howMany=14
        roundCount = 0
        didBreak = false
  
        oldPlayerResources = []

        howMany.times {
            @handler.startAuction(NimGame.new(@p1, @p2, @initialPileSize))

            roundCount += 1
            
            newPlayerResources = @auctioneer.playerResources

            if ! GameShell.didLearn(oldPlayerResources, newPlayerResources)
                didBreak = true
                break
            end
            
            oldPlayerResources = newPlayerResources
        }

        [ roundCount, didBreak ]
    end
    
    def displayAuctions
        output = "Pieces\tBid\t#{Player.header_for_to_s}\n"

        output << handler.debugInfo << "\n"
        
        output
    end

#   def GameShell.execute(
#       tieBreakStrategy            = :first,
#       displayAuctions             = false,
#       displayFunds                = false,
#       numberOfTrainingRounds      = 100,
#       pileSize                    = 10,
#       makeMove                    = false,
#       showMovesForEachPosition    = false,
#       helpMessage         = nil)
    
    def GameShell.getTieBreakStrategy strat
        case strat
            when :first 
                FirstInListTieBreakStrategy.new
            when :byLot 
                BreakTiesByLotStrategy.new
            when :byTime    
                BreakTiesByTimeStrategy.new
            when :awardToAll
                AwardTiesToAllBiddersStrategy.new
            else
                raise StandardError, "Unknown tie break strategy."
        end
    end

    def output options, roundCount, didBreak
        output = ''

        if options.displayAuctions
             output << displayAuctions
        end

        if options.displayFunds
            output << showPlayerResources << "\n"
        end

        if options.showMovesForEachPosition
            if didBreak
                output << "Terminated after #{roundCount} rounds (#{handler.gameCount} games)." << "\n"
            end

            output << showMovesForEachPosition
        end

        if options.makeMove
            output << moveForPileSize(initialPileSize)
        end
        
        output
    end
    
    def GameShell.executeCommandOptions options
        return options.helpMessage if options.helpMessage
        
        tieBreakStrategy = getTieBreakStrategy options.tieBreakStrategy

        gameShell = GameShell.new tieBreakStrategy, options.pileSize

        roundCount, didBreak = gameShell.executeManyGames options.numberOfTrainingRounds

        gameShell.output options, roundCount, didBreak
    end

    # Deprecated
    def GameShell.executeCommandLine args
        CommandLineHandler.executeCommandLine(args)
    end
end

class NimOptionValues < OpenStruct
    def initialize
        super
        
        self.tieBreakStrategy           = :first
        self.displayAuctions            = false
        self.displayFunds               = false
        self.numberOfTrainingRounds     = 100
        self.pileSize                   = 10
        self.makeMove                   = false
        self.showMovesForEachPosition   = false
        self.helpMessage                = nil
    end
end

class NimOptions
    def self.parse(args)
        options = NimOptionValues.new

        opts = OptionParser.new do |opts|
            programName = __FILE__ == $0 ? $0 : 'agoricNim'
            opts.banner = "Usage: #{programName} [options]"

            opts.separator ""
            opts.separator "Options:"
    
            opts.on("-s", "--srand S", Integer, "Set the pseudo-random seed to S") do |s|
                srand s
            end

            opts.on("-n", "--numberOfTrainingRounds N", Integer, "Terminate after N games") do |n|
                options.numberOfTrainingRounds = n
            end

            opts.on("-p", "--pileSize P", Integer, "Start each game with P stones") do |p|
                options.pileSize = p
            end

            opts.on("-t", "--tieBreakStrategy [STRATEGY]", [:first, :byLot, :byTime, :awardToAll], "Select tie break strategy (first, byLot, byTime, awardToAll)") do |t|
                options.tieBreakStrategy = t
            end

            opts.on("-m", "--makeMove", "Make a move (after training rounds, if any)") do
                options.makeMove = true
            end

            opts.on("-e", "--showMovesForEachPosition", "Show moves that would be made after training") do
                options.showMovesForEachPosition = true
            end

            opts.on("-d", "--displayAuctions", "Display auctions for debugging") do
                options.displayAuctions = true
            end

            opts.on("-f", "--displayFunds", "Display player's funds for debugging") do
                options.displayFunds = true
            end

            # No argument, shows at tail.  This will print an options summary.
            opts.on_tail("-h", "--help", "Show this message") do
                options.helpMessage = opts.to_s
            end
        end

        opts.parse!(args)

        if  !options.displayFunds &&
            !options.displayAuctions &&
            !options.showMovesForEachPosition &&
            !options.makeMove
                options.helpMessage = opts.to_s
        end

        options
    end
end

if __FILE__ == $0
    puts GameShellHandler.executeCommandLine(ARGV)
end